Diagonal AdaGrad for online convex losses

Let d>=1 and let C be a nonempty closed convex subset of R^d, closed in the standard Euclidean metric topology of ${\mathbb{R}}^n$ as the set of functions $n\to \mathbb{R}$, and $d_1$, $d_2$, $d_{\mathrm{\infty }}$ are metrics on it and convex as in A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points. Use the one-based coordinate labels $z_j:=z(j-1)$ for $1\le j\le d$ for the vectors of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$. Fix x_1 in C, a constant eta>0, and epsilon>0. An admissible input consists of convex losses ell_t:C->R and a subgradient oracle that returns a finite vector g_t in partial ell_t(x_t) at each queried iterate, with subgradient convention Subgradients and the subdifferential of a convex function. On round t, observe ell_t and obtain g_t from this oracle. For j=1,...,d set

$s_{t,j}=\sqrt{{ϵ}^2+{\sum }_{k=1}^t{g}_{k,j}^2},A_t=\mathrm{diag}(s_{t,1},\mathrm{.}\mathrm{.}\mathrm{.},s_{t,d})\mathrm{.}$

For a positive diagonal matrix A, write ||z||A^2=z^TAz. Set x{t+1} to the unique minimizer

$x_{t+1}={\mathrm{argmin}}_{x\in C}\{\eta ⟨g_t,x⟩+\frac{1}{2}\mathrm{\parallel }x-x_t{\mathrm{\parallel }}_{A_t}^2\}\mathrm{.}$

Because epsilon>0, every diagonal entry s_{t,j} is positive. The displayed minimizer exists and is unique by Diagonal AdaGrad subproblem has a unique minimizer ↗, so the procedure is defined at each finite round. This is the proximal update in the diagonal metric A_t; after the coordinate scaling A_t^{1/2}, its subproblem is an ordinary Euclidean proximal problem in the sense of Proximal mapping.

Each nonzero $g_{k,j}$ has positive square by Squares of nonzero elements are positive, and the zero case has square zero by Multiplication by zero: $0\cdot a=0$. Clause 4 of Laws of finite sums and finite products makes its finite sum nonnegative, so ${ϵ}^2+{\sum }_{k=1}^t{g}_{k,j}^2\ge {ϵ}^2>0$. Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$ therefore supplies a nonnegative, nonzero root $s_{t,j}$, hence $s_{t,j}>0$. This verifies the positive diagonal hypothesis used by the subproblem result.