Uncorrected AMSGrad with a coordinatewise historical maximum

Fix a dimension $d\ge 1$, a finite horizon $T\ge 1$, a nonempty compact convex set $F\subseteq {\mathbb{R}}^d$, an initial point $x_1\in F$, positive step sizes ${\alpha }_t>0$, a fixed parameter ${\beta }_2\in (0,1)$, and parameters ${\beta }_{1,t}\in [0,1)$ for $1\le t\le T$. Use one-based coordinate notation $z_i:=z(i-1)$ for every vector $z\in {\mathbb{R}}^d$ and $1\le i\le d$. At round $t$, receive a finite subgradient vector $g_t\in {\mathbb{R}}^d$. Set $m_0=v_0={\widehat{v}}_0=0$ and update coordinatewise by

$m_{t,i}={\beta }_{1,t}{m}_{t-1,i}+(1-{\beta }_{1,t})g_{t,i},v_{t,i}={\beta }_2{v}_{t-1,i}+(1-{\beta }_2)g_{t,i}^2,$

${\widehat{v}}_{t,i}=\max \{{\widehat{v}}_{t-1,i},v_{t,i}\}\mathrm{.}$

If ${\widehat{v}}_{t,i}>0$, set $y_{t+1,i}=x_{t,i}-{\alpha }_t{m}_{t,i}\mathrm{/}\sqrt{{\widehat{v}}_{t,i}}$; if ${\widehat{v}}_{t,i}=0$, set $y_{t+1,i}=x_{t,i}$. Choose any minimizer

$x_{t+1}\in {\mathrm{argmin}}_{x\in F}{\sum }_{i=1}^d\sqrt{{\widehat{v}}_{t,i}}(x_i-y_{t+1,i}{)}^2\mathrm{.}$

Return the trajectory through $x_{T+1}$. The procedure uses the uncorrected first and second moments and the coordinatewise running maximum of the raw second moment. It contains no denominator stabilizer.

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

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

Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$: each nonnegative second-moment coordinate has a unique nonnegative square root.

Maximum and minimum of a set

Every nonempty finite set of reals has a maximum and a minimum: the maximum of the two real second-moment values exists.

For a nonempty subset of ${\mathbb{R}}^n$ with $n\ge 1$, compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: a continuous real-valued function on the nonempty compact feasible set attains its minimum.

Bias-corrected AMSGrad update: the published procedure instead maxes bias-corrected second moments; it is not this raw-moment update.

Reddi, Kale, and Kumar, AMSGrad Algorithm 2 and Theorem 4

This is the source-matched online AMSGrad procedure for the regret theorem on this page. It is distinct from the published bias-corrected procedure. The moment well-definedness result justifies the zero-coordinate convention and existence of each finite minimization step.