Mirror descent and adaptive regularization — Examples

Use the diagonal AdaGrad scale in dimension $2$ with $K=[-1,1{]}^2$, $x_1=(0,0)$, one round, step size $\eta =1$, and supplied gradient $g_1=(1,0)$. Then $G_1=H_1=\mathrm{diag}(1,0)$, $H_1^{†}=\mathrm{diag}(1,0)$, and $y_2=(-1,0)$. For a decision vector $(a,b)\in K$, the metric projection objective is $(a+1{)}^2$, so its minimizers are all points $(-1,s)$ with $s\in [-1,1]$. In particular, one may select $x_2=(-1,0)$. The metric is singular and the projection is nonunique.

Gram-matrix AdaGrad with full or singular diagonal metrics: defines the diagonal scale, pseudoinverse update, and metric projection used in this calculation.

A singular AdaGrad metric still has a projection minimizer: proves that the projection objective has a minimizer even for a singular metric.

The diagonal AdaGrad scale is the coordinatewise square root: identifies the diagonal scale entry with the square root of accumulated squared coordinate gradients.

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

The Moore--Penrose pseudoinverse $A^{+}$ as the solution of the four Penrose equations: characterizes the pseudoinverse by four matrix equations.

Let $n\ge 2$, let $K_n$ be the probability simplex represented by independent coordinates $q_1,\dots ,q_{n-1}$ with $p_i=q_i$ for $1\le i<n$ and $p_n=1-{\sum }_{i=1}^{n-1}{q}_i$. Probability labels are one-based; for any independent-coordinate vector $v\in {\mathbb{R}}^{n-1}$, write $v_i:=v(i-1)$ for $1\le i<n$ in the library's function-space convention. Set

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

Use $U_n$ as the mirror domain and define $R(q)={\sum }_{i=1}^n{p}_i\log p_i$ on $K_n$, with $0\log 0:=0$. Initialize at the uniform distribution. At each round use the linear loss $f_t(p)={\sum }_{i=1}^n{p}_i{\mathrm{\ell }}_{t,i}$ for a full-information vector ${\mathrm{\ell }}_t\in [0,1{]}^n$ and a fixed step size $\eta >0$. In full probability coordinates, agile mirror descent updates

$p_{t+1,i}=\frac{p_{t,i}\exp (-\eta {\mathrm{\ell }}_{t,i})}{{\sum }_{j=1}^n{p}_{t,j}\exp (-\eta {\mathrm{\ell }}_{t,j})},i=1,\dots ,n\mathrm{.}$

Consequently its distribution sequence equals the normalized weight distributions of Hedge initialized at unit weights and using learning rate $ϵ=\eta$. Hedge then samples an expert from each shared distribution; mirror descent outputs the distributions themselves.

Agile online mirror descent: defines the agile gradient update and Bregman projection.

Compactness makes the Bregman projection well-defined: establishes existence, uniqueness, and the Pythagorean property of the Bregman projection.

Negative entropy on the simplex is strongly convex and has range log n: proves continuity, strong convexity, and the entropy range for this regularizer.

Mirror maps, Bregman divergence, and local Hessian norms: defines the Hessian geometry and Bregman divergence.

Interior, closure, boundary, limit point, isolated point and dense subset of a metric space: defines the interior and closure used for the simplex mirror domain.

Hedge: defines Hedge's unit initial weights, normalization, full-information loss update, and sampled expert.

The natural logarithm as the inverse of the exponential function: defines the natural logarithm and supplies the positive range of $\exp$ and its inverse relation with $\log$.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: supplies logarithm quotient and product laws.

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: supplies the derivative of $\log$ used to differentiate entropy.

The real exponential function and the number $e$ by a power series: defines the real exponential function used in both updates.

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

Sums, scalar multiples, products and quotients: $(f+g{)}^{\mathrm{\prime }}(c)=f^{\mathrm{\prime }}(c)+g^{\mathrm{\prime }}(c)$, $(\alpha f{)}^{\mathrm{\prime }}(c)=\alpha f^{\mathrm{\prime }}(c)$, $(fg{)}^{\mathrm{\prime }}(c)=f^{\mathrm{\prime }}(c)g(c)+f(c)g^{\mathrm{\prime }}(c)$, and $(f\mathrm{/}g{)}^{\mathrm{\prime }}(c)=(f^{\mathrm{\prime }}(c)g(c)-f(c)g^{\mathrm{\prime }}(c))\mathrm{/}g(c{)}^2$ when $g(c)\mathrm{\ne }0$: supplies the product rule used to differentiate $p_i\log p_i$.

The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g(c)$, then $f\circ g$ is differentiable at $c$ with $(f\circ g{)}^{\mathrm{\prime }}(c)=f^{\mathrm{\prime }}(g(c))g^{\mathrm{\prime }}(c)$: differentiates the affine coordinate substitutions in the entropy summands.

Let $d\ge 1$, let $K\subseteq {\mathbb{R}}^d$ be nonempty, bounded, closed, and convex with nonempty interior, choose $x_0\in {\mathbb{R}}^d$, and set $R(x)=\frac{1}{2}\mathrm{\parallel }x-x_0{\mathrm{\parallel }}_2^2$ on $U={\mathbb{R}}^d$. Initialize at a minimizer of $R$ on $K$. At any round with current decision $x_t\in K$ and gradient $g_t$, the agile mirror step with parameter $\eta >0$ has $y_{t+1}=x_t-\eta g_t$ and

$x_{t+1}=\arg {\min }_{x\in K}{B}_R(x\mathrm{\parallel }{y}_{t+1})=\arg {\min }_{x\in K}\frac{1}{2}\mathrm{\parallel }x-(x_t-\eta g_t){\mathrm{\parallel }}_2^2\mathrm{.}$

Thus its one-step update map is exactly the projected gradient update with the same step size. If $\eta$ is set to the current projected-gradient step size, the two displayed one-step maps agree.

Agile online mirror descent: defines the agile dual step and Bregman projection.

Compactness makes the Bregman projection well-defined: establishes existence and uniqueness of the minimizer over $K$.

Mirror maps, Bregman divergence, and local Hessian norms: defines the quadratic regularizer's Bregman divergence and Hessian norms.

Projected online gradient descent: defines the projected gradient update with the current step size.

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

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: supplies the segment condition for the decision set.

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 is in the Euclidean metric topology.

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