Mirror descent and adaptive regularization

Let $d\ge 1$, let $K\subseteq {\mathbb{R}}^d$ be a nonempty bounded closed convex set with nonempty interior, and let $U\subseteq {\mathbb{R}}^d$ be an open convex set such that $\mathrm{int}(K)\subseteq U$ and $K\subseteq \bar{U}$. If a decision set is lower-dimensional in an ambient Euclidean space, take ${\mathbb{R}}^d$ to be orthonormal affine coordinates on its affine hull (the smallest affine subspace containing it); thus interior, gradients, Hessians, and norms are relative to that affine hull. A mirror regularizer on $(K,U)$ is a real-valued function $R$ on $K\cup U$ that is continuous on $K$, twice continuously differentiable on $U$, agrees on $K\cap U$, and has symmetric positive-definite Hessian $H_R(z):={\mathrm{\nabla }}^{2}R(z)$ for every $z\in U$. We call $R$ $m$-strongly convex on $K$ in the Euclidean norm if, for some $m>0$, all $x,y\in K$ and $\lambda \in [0,1]$ satisfy

$R((1-\lambda )x+\lambda y)\le (1-\lambda )R(x)+\lambda R(y)-\frac{m}{2}\lambda (1-\lambda )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2\mathrm{.}$

For $x\in K\cup U$ and $y\in U$, the Bregman divergence generated by $R$ is

$B_R(x\mathrm{\parallel }y):=R(x)-R(y)-⟨\mathrm{\nabla }R(y),x-y⟩\mathrm{.}$

For $z\in U$ and vectors $v,h\in {\mathbb{R}}^d$, define the squared local primal norm and local dual norm by

$\mathrm{\parallel }v{\mathrm{\parallel }}_z^2:=v^{\mathrm{\top }}{H}_R(z)v,\mathrm{\parallel }h{\mathrm{\parallel }}_{\ast ,z}^2:=h^{\mathrm{\top }}{H}_R(z{)}^{-1}h\mathrm{.}$

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convexity means that every segment between points of the set lies in the set.

Convex and strictly convex functions on Euclidean convex sets: defines ordinary and strict convexity; the displayed quantitative inequality defines strong convexity locally here.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the pairing and norm are the standard Euclidean inner product and norm.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\mathrm{\nabla }R$ is the vector of first partial derivatives.

The Hessian matrix and critical points of a scalar field: ${\mathrm{\nabla }}^{2}R$ is the Hessian matrix of second partial derivatives.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: open and closed use the Euclidean metric topology.

Interior, closure, boundary, limit point, isolated point and dense subset of a metric space: $\mathrm{int}(K)$ and $\bar{U}$ are the interior and closure in that topology.

Bounded subset, diameter, distance from a point to a set, and distance between two sets in a metric space: boundedness uses the Euclidean metric.

Let $d\ge 1$ and let $G\in {\mathbb{R}}^{d\times d}$ be symmetric and positive semidefinite, meaning $v^{\mathrm{\top }}Gv\ge 0$ for every $v\in {\mathbb{R}}^d$. Then there is a unique symmetric positive-semidefinite matrix $H$ such that $H^2=G$. If $G=Q\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)Q^{\mathrm{\top }}$ is an orthogonal diagonalization, this root is $H=Q\mathrm{diag}(\sqrt{{\lambda }_1},\dots ,\sqrt{{\lambda }_d})Q^{\mathrm{\top }}$.

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real self-adjoint matrix has an orthonormal eigenbasis.

In orthonormal bases, the matrix of the adjoint is the conjugate transpose of the matrix: for a real Euclidean matrix, self-adjointness is symmetry.

Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes: matrix products and transposes use ordinary finite-dimensional matrix algebra.

Matrix multiplication is associative, unital, distributive, and compatible with scalar multiplication: matrix multiplication is associative.

Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$: every nonnegative real eigenvalue has a unique nonnegative scalar square root.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the quadratic form and orthogonality use the standard Euclidean inner product.

Let $K\subseteq {\mathbb{R}}^d$, let $U\subseteq {\mathbb{R}}^d$ be open, and let $R$ be a mirror regularizer whose Bregman divergence is $B_R(x\mathrm{\parallel }y)=R(x)-R(y)-⟨\mathrm{\nabla }R(y),x-y⟩$ for $x\in K\cup U$ and $y\in U$. For $a\in K\cup U$ and $b,c\in U$,

$⟨a-b,\mathrm{\nabla }R(c)-\mathrm{\nabla }R(b)⟩=B_R(a\mathrm{\parallel }b)-B_R(a\mathrm{\parallel }c)+B_R(b\mathrm{\parallel }c)\mathrm{.}$

Mirror maps, Bregman divergence, and local Hessian norms: defines $B_R(a\mathrm{\parallel }b)=R(a)-R(b)-⟨\mathrm{\nabla }R(b),a-b⟩$ whenever $a\in K\cup U$ and $b\in U$.

Let $(K,U,R)$ be a mirror regularizer, and suppose $R$ is $m$-strongly convex on $K$ for some $m>0$. For $x,y\in U$,

$B_R(x\mathrm{\parallel }y)\ge 0,$

with strict inequality when $x\mathrm{\ne }y$. For $x\in K$ and $y\in K\cap U$,

$B_R(x\mathrm{\parallel }y)\ge \frac{m}{2}\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2\mathrm{.}$

Mirror maps, Bregman divergence, and local Hessian norms: defines the Bregman formula, the positive-definite Hessian on $U$, and strong convexity on $K$.

Multivariable Taylor formula with a Lagrange remainder along a line segment: gives a second-order Taylor formula with a Hessian evaluated at an intermediate point of the segment.

Let $n\ge 2$. Coordinates in ${\mathbb{R}}^{n-1}$ use the library's function-space convention: for $v\in {\mathbb{R}}^{n-1}$ and $1\le i<n$, write $v_i:=v(i-1)$. Let

$K_n:=\{q\in {\mathbb{R}}^{n-1}:q_i\ge 0\text{ for all }1\le i<n,{\sum }_{i=1}^{n-1}{q}_i\le 1\},$

and for $q\in K_n$ put $p_i=q_i$ for $1\le i<n$ and $p_n=1-{\sum }_{i=1}^{n-1}{q}_i$. Define $R(q)={\sum }_{i=1}^n{p}_i\log p_i$, with $0\log 0:=0$. In the independent coordinates $q_1,\dots ,q_{n-1}$, $R$ is continuous on $K_n$, is twice continuously differentiable on its interior, is $1$-strongly convex in the Euclidean norm, and satisfies

$-\log n\le R(q)\le 0.$

The minimum $-\log n$ is attained at $p_i=1\mathrm{/}n$ for every $i$, and the maximum $0$ is attained at each vertex of the simplex.

Mirror maps, Bregman divergence, and local Hessian norms: defines strong convexity by the displayed Euclidean quadratic inequality and defines the interior Hessian norms used by this regularizer.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convexity means every segment between simplex points remains in the simplex.

Let $d\ge 1$ be an integer and let $K\subseteq {\mathbb{R}}^d$ be nonempty, bounded, closed, and convex; let $x_1\in K$, let $T\ge 1$ be an integer, and fix a step size $\eta >0$. Coordinate and matrix-entry subscripts in this procedure are one-based labels: for $i,j\in \{1,\dots ,d\}$, write $g_i=g(i-1)$ and $G_{ij}=G(i-1,j-1)$ in the underlying zero-based Euclidean and matrix conventions, and use the same relabeling for the other vectors and matrices. Initialize $G_0=0$. For each round $t=1,\dots ,T$, play $x_t$, then receive the full current loss information and its prescribed gradient vector $g_t\in {\mathbb{R}}^d$, and set

$G_t=G_{t-1}+g_t{g}_t^{\mathrm{\top }}={\sum }_{s=1}^t{g}_s{g}_s^{\mathrm{\top }}\mathrm{.}$

The accumulated matrix $G_t$ is symmetric and positive semidefinite. Choose either the full-matrix scale $H_t=G_t^{1\mathrm{/}2}$, the unique positive-semidefinite square root, or the diagonal scale $H_t=\mathrm{diag}(\sqrt{(G_t{)}_{11}},\dots ,\sqrt{(G_t{)}_{dd}})$. Define $H_t^{†}$ to be the Moore–Penrose pseudoinverse and update

$y_{t+1}=x_t-\eta H_t^{†}{g}_t,x_{t+1}\in \arg {\min }_{x\in K}(x-y_{t+1}{)}^{\mathrm{\top }}{H}_t(x-y_{t+1})\mathrm{.}$

A minimizer exists; if it is not unique, select any minimizer. Return $x_1,\dots ,x_T$. The matrix seminorm notation in the objective means $\mathrm{\parallel }v{\mathrm{\parallel }}_{H_t}^2=v^{\mathrm{\top }}{H}_{t}v$. The diagonal scale here is formed by taking each diagonal entry of $G_t$ and then its scalar square root; in general it is not $\mathrm{diag}(G_t^{1\mathrm{/}2})$. This is an update definition only and asserts no regret bound.

AdaGrad accumulated Gram matrices and both scales are positive semidefinite ↗: proves the accumulated matrix is symmetric positive semidefinite and both full and diagonal scales are well-defined positive-semidefinite matrices.

Online decision protocol: the learner plays $x_t$ before receiving round-$t$ feedback.

Adversary and feedback models: full-information feedback reveals the full current loss function after the choice. The prescribed gradient vector is an additional input explicitly required by this procedure.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: vectors use the standard Euclidean inner product.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $g_t$ is a vector in the standard coordinate basis.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: every segment between points of $K$ lies in $K$.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: closedness uses the Euclidean metric topology.

Bounded subset, diameter, distance from a point to a set, and distance between two sets in a metric space: boundedness uses the Euclidean metric.

Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes: the outer product $g_t{g}_t^{\mathrm{\top }}$ and matrix sums use ordinary finite-dimensional matrix multiplication.

In orthonormal bases, the matrix of the adjoint is the conjugate transpose of the matrix: for real Euclidean matrices, the adjoint matrix is the transpose.

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix admits an orthonormal eigenbasis.

Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$: every nonnegative real has a unique nonnegative scalar square root.

The Moore--Penrose pseudoinverse $A^{+}$ as the solution of the four Penrose equations: $H_t^{†}$ is the Moore–Penrose pseudoinverse, including for singular $H_t$.

Every finite real or complex matrix has a unique Moore--Penrose pseudoinverse: every finite-dimensional real matrix has a unique Moore–Penrose pseudoinverse.

A positive-semidefinite matrix has a unique positive-semidefinite square root: proves the unique symmetric positive-semidefinite matrix root from the real spectral theorem and scalar square roots.

For the AdaGrad inputs, at each round $t\in \{0,\dots ,T\}$ the accumulated matrix $G_t={\sum }_{s=1}^t{g}_s{g}_s^{\mathrm{\top }}$, with $G_0=0$, is a finite real symmetric positive-semidefinite matrix. More precisely, for every $v\in {\mathbb{R}}^d$, $v^{\mathrm{\top }}{G}_{t}v={\sum }_{s=1}^t(g_s^{\mathrm{\top }}v{)}^2\ge 0,(G_t{)}_{ii}={\sum }_{s=1}^t{g}_{s,i}^2\ge 0.$ Here the coordinate and matrix-entry labels $i,j\in \{1,\dots ,d\}$ are one-based: $g_{s,i}=g_s(i-1)$ and $(G_t{)}_{ij}=G_t(i-1,j-1)$ in the underlying zero-based conventions. Empty sums have value zero. Therefore both the full-matrix scale $G_t^{1\mathrm{/}2}$ and the diagonal scale $\mathrm{diag}(\sqrt{(G_t{)}_{11}},\dots ,\sqrt{(G_t{)}_{dd}})$ exist and are finite real symmetric positive-semidefinite matrices. Singular and zero accumulated matrices are allowed.

Gram-matrix AdaGrad with full or singular diagonal metrics: defines the accumulated gradient outer products and the two choices of scale.

Let $(K,U,R)$ be a mirror regularizer with $R$ $m$-strongly convex on $K$ for some $m>0$. Fix an integer horizon $T\ge 1$ and a step size $\eta >0$. Admissibility requires the unique minimizer of $R$ on $K$ to lie in $U$; initialize $x_1$ at this minimizer. At each round $t=1,\dots ,T$, play $x_t$ before observing the full current loss $f_t$, with losses and gradients written in the same affine coordinates used for $K$. Use either of these feedback cases:

1. $f_t$ is differentiable and convex on an open convex set containing $K$, and $g_t=\mathrm{\nabla }{f}_t(x_t)$.
2. $f_t$ is convex on a convex set containing $K$, and a supplied vector $g_t$ satisfies $f_t(u)\ge f_t(x_t)+⟨g_t,u-x_t⟩$ for every $u\in K$.

For each round require that there is a unique $y_{t+1}\in U$ satisfying

$\mathrm{\nabla }R(y_{t+1})=\mathrm{\nabla }R(x_t)-\eta g_t\mathrm{.}$

Set $x_{t+1}$ to the minimizer of $B_R(x\mathrm{\parallel }{y}_{t+1})$ over $x\in K$, and require this minimizer to lie in $U$ so that the next dual update is defined. The Bregman minimizer exists and is unique under the stated strong-convexity and compactness hypotheses. Output the decisions $x_1,\dots ,x_T$; the final $x_{T+1}$ is the internal post-round iterate.

Mirror maps, Bregman divergence, and local Hessian norms: gives the domains, strong-convexity condition, Bregman divergence, and Hessian notation.

Online decision protocol: the learner chooses using only the previous history before the round's current loss is observed.

Adversary and feedback models: full-information feedback reveals the current loss after the learner's choice.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convex domains contain every segment between their points.

Convex and strictly convex functions on Euclidean convex sets: defines convexity of each loss function.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the pairing in the subgradient condition is the Euclidean inner product.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\mathrm{\nabla }{f}_t(x_t)$ is the Euclidean gradient vector.

Subgradients and the subdifferential of a convex function: a supplied vector satisfying the stated supporting inequality is a subgradient at $x_t$.

Differentiable convex functions are characterized by the gradient inequality: the smooth feedback case supplies the same supporting inequality for every comparator in $K$.

Let $d\ge 1$, let $K\subseteq {\mathbb{R}}^d$ be nonempty, bounded, closed, and convex, let $H$ be a fixed real positive-semidefinite matrix, and let $y\in {\mathbb{R}}^d$. The function $x\mapsto (x-y{)}^{\mathrm{\top }}H(x-y)$ attains a minimum on $K$. This conclusion allows $H$ to be singular and makes no uniqueness claim.

Gram-matrix AdaGrad with full or singular diagonal metrics: the AdaGrad update uses this quadratic objective with $H=H_t$ and $y=y_{t+1}$.

For the diagonal AdaGrad choice $H_t=\mathrm{diag}(\sqrt{(G_t{)}_{11}},\dots ,\sqrt{(G_t{)}_{dd}})$ with $G_t={\sum }_{s=1}^t{g}_s{g}_s^{\mathrm{\top }}$, the $i$th diagonal entry is

$(H_t{)}_{ii}=\sqrt{{\sum }_{s=1}^t{g}_{s,i}^2},i=1,\dots ,d\mathrm{.}$

Gram-matrix AdaGrad with full or singular diagonal metrics: defines the accumulated Gram matrix and the diagonal AdaGrad scale.

Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes: defines the coordinate formula for matrix products.

In orthonormal bases, the matrix of the adjoint is the conjugate transpose of the matrix: identifies the transpose entries used in the outer product.

Let $d\ge 1$, let $K\subseteq {\mathbb{R}}^d$ be nonempty, bounded, closed, and convex, and let $(K,U,R)$ be a mirror regularizer with $R$ $m$-strongly convex on $K$ for some $m>0$. Then $R$ has a unique minimizer on $K$, and for every $y\in U$ the function $x\mapsto B_R(x\mathrm{\parallel }y)$ has a unique minimizer $x_{+}(y)$ on $K$. If $x_{+}(y)\in U$, then for every $u\in K$,

$⟨\mathrm{\nabla }R(x_{+}(y))-\mathrm{\nabla }R(y),u-x_{+}(y)⟩\ge 0$

and

$B_R(u\mathrm{\parallel }y)\ge B_R(u\mathrm{\parallel }{x}_{+}(y))+B_R(x_{+}(y)\mathrm{\parallel }y)\mathrm{.}$

Agile online mirror descent: uses a minimizer of $R$ to initialize and a minimizer of $B_R(\cdot \mathrm{\parallel }y)$ for each dual point $y$.

Mirror maps, Bregman divergence, and local Hessian norms: gives continuity of $R$ on $K$, the strong-convexity inequality, and the Bregman formula.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the strong-convexity inequality uses the standard Euclidean norm.

The Bregman three-point identity: states the algebraic identity used for the Pythagorean inequality.

Upper and lower semicontinuity on subsets of ${\mathbb{R}}^n$: continuity implies lower semicontinuity on a Euclidean subset.

Let $d\ge 1$ and let $(K,U,R)$ be a mirror regularizer on $K\subseteq {\mathbb{R}}^d$, with $K$ nonempty, bounded, closed, and convex, $U$ open and convex, positive-definite Hessian on $U$, and $R$ $m$-strongly convex on $K$ for some $m>0$. Let $T\ge 1$ be an integer and $\eta >0$. Let $x_1\in K\cap U$ minimize $R$ on $K$. For every $t=1,\dots ,T$, suppose $x_t,x_{t+1}\in K\cap U$, $y_{t+1}\in U$, and