Gram-matrix AdaGrad with full or singular diagonal metrics

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.