Adaptive gradient algorithms and regret limits

Fix a dimension $d\ge 1$, an initial vector $x_1\in {\mathbb{R}}^d$, a finite or infinite sequence of finite gradient vectors $g_t\in {\mathbb{R}}^d$, positive step sizes ${\eta }_t>0$, a decay parameter $\rho \in [0,1)$, and a denominator constant $ϵ>0$. Use one-based coordinate notation $z_i:=z(i-1)$ for every vector $z\in {\mathbb{R}}^d$ and $1\le i\le d$. Set $r_0=0$. At each integer round $t\ge 1$, update the second-moment estimate coordinatewise by

$r_{t,i}=\rho r_{t-1,i}+(1-\rho )g_{t,i}^2(1\le i\le d),$

and then set

$x_{t+1,i}=x_{t,i}-{\eta }_t\frac{g_{t,i}}{\sqrt{r_{t,i}}+ϵ}(1\le i\le d)\mathrm{.}$

For a finite gradient sequence of length $T\ge 0$, perform rounds $1\le t\le T$ and return the trajectory $(x_1,\dots ,x_{T+1})$; when $T=0$, return $(x_1)$. For an infinite gradient sequence, perform every round $t\ge 1$, thereby defining and returning the iterate sequence $(x_t{)}_{t\ge 1}$. The root, addition, and division in the update are coordinatewise. The procedure makes no convergence or regret claim.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: vectors in ${\mathbb{R}}^d$ have the stated real coordinates, and vector updates are interpreted coordinatewise.

Squares of nonzero elements are positive: every nonzero squared gradient coordinate is positive.

Multiplication by zero: $0\cdot a=0$: a zero gradient coordinate has square zero.

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 real has a unique nonnegative square root.

Ordered field

Sign rules for products and monotonicity of multiplication: the decay coefficients and their complements are nonnegative, so the moment recurrence preserves nonnegativity.

Bottou, Curtis, and Nocedal, RMSprop update

Reddi, Kale, and Kumar, adaptive-method setup

This is the no-momentum RMSProp variant with a positive constant added outside the square root. It has no bias correction and defines only an update procedure.

Fix a finite horizon $T\ge 1$, an initial scalar $x_1\in [-1,1]$, a step parameter $\alpha >0$, moment parameters ${\beta }_1\in [0,1)$ and ${\beta }_2\in (0,1)$, a denominator parameter $ϵ\ge 0$, and a sequence of scalar gradients $g_1,\dots ,g_T$. Set $m_0=v_0=0$. At round $t$, update

$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t,v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2\mathrm{.}$

The input is admissible only when $v_t+ϵ>0$ at every update. Set ${\alpha }_t=\alpha \mathrm{/}\sqrt{t}$, compute $y_{t+1}=x_t-{\alpha }_t{m}_t\mathrm{/}\sqrt{v_t+ϵ}$, and set $x_{t+1}=\max (-1,\min (1,y_{t+1}))$. Thus the iterate is projected onto $[-1,1]$ after the update. Return the trajectory $(x_1,\dots ,x_{T+1})$, whose final iterate is $x_{T+1}$. The denominator parameter is added inside the square root. No moment bias correction is applied.

The natural numbers $\mathbb{N}$ (von Neumann): the finite round indices are natural numbers.

Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length: $[-1,1]$ is the closed scalar interval used for initialization and clipping.

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 radicand 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 displayed clipping operation is the maximum and minimum of finite real sets.

Bias-corrected Adam update: the published bias-corrected Adam procedure instead divides by $\sqrt{{\widehat{v}}_t}+ϵ$; it is a distinct update convention.

Reddi, Kale, and Kumar, Algorithm 1 and the inside-root epsilon variant

Kingma and Ba, Adam Algorithm 1

This is the uncorrected scalar online variant used for the cited regret counterexamples. Its $ϵ=0$ mode is defined only on gradient sequences with positive $v_t$ at every round; the counterexample sequences in the theorem meet that condition. The fixed-$ϵ$ mode uses the source's addition inside the square root, not the published bias-corrected denominator convention.

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.

For every real $q\in [0,1)$, every $p\in \{1,2\}$, and every real $\delta >0$, there is an integer $N\ge 1$ such that $n^p{q}^n<\delta$ for every integer $n\ge N$.

The natural numbers $\mathbb{N}$ (von Neumann): the indices $n$ and $N$ are natural numbers.

Integer powers $a^m$: $q^n$ is the natural integer power.

For $\mathrm{\mid }r\mathrm{\mid }<1$ the sequence $r^k$ is null, and for $\mathrm{\mid }r\mathrm{\mid }>1$ the sequence $\mathrm{\mid }r{\mathrm{\mid }}^k$ diverges to $+\mathrm{\infty }$: if $0\le q<1$, then $q^n$ tends to zero.

Reddi, Kale, and Kumar, Appendix B

Let $n\in \mathbb{N}$ with $n\ge 1$, let $x_0\in [-1,1]$, and let $k\in \{0,\dots ,n\}$. Let real increments ${\delta }_1,\dots ,{\delta }_n$ satisfy ${\delta }_j\le 0$ for $j\le k$ and ${\delta }_j\ge 0$ for $j>k$. Define $c(y)=\max \{-1,\min \{1,y\}\}$ and $x_j=c(x_{j-1}+{\delta }_j)$. Then

$x_n\ge \min \{1,x_0+{\sum }_{j=1}^n{\delta }_j\}\mathrm{.}$

Maximum and minimum of a set: maximum and minimum of finite real sets define the clipping map $c$.

Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length: $[-1,1]$ is the closed interval with endpoints $-1$ and $1$.

Reddi, Kale, and Kumar, Appendix B

For every finite admissible run of the RMSProp, uncorrected Adam, or uncorrected AMSGrad procedures defined on this page, all moment coordinates are finite and all second-moment coordinates are nonnegative. Every denominator specified by the procedure is positive. For AMSGrad, a zero historical-maximum coordinate has zero current and previous first moments, and the raw second moment is positive whenever its historical maximum is positive; the zero-ratio convention is therefore consistent. Each weighted minimization over the compact feasible set attains a minimum.

RMSProp with an exponential second-moment estimate: defines the exponential second-moment recurrence and positive stabilizer.

Uncorrected Adam for online convex losses: defines the uncorrected scalar moment recurrences, admissible denominators, and clipping update.

Uncorrected AMSGrad with a coordinatewise historical maximum: defines the raw-moment recurrence, historical maximum, zero-coordinate convention, and compact-set minimization.

Reddi, Kale, and Kumar, adaptive-moment procedures

Bottou, Curtis, and Nocedal, RMSprop recurrence

At an AMSGrad round, let $F\subseteq {\mathbb{R}}^d$ be nonempty, compact, and convex, let $x_t,x_{t+1}\in F$, let ${\mathrm{\ell }}_t:F\to \mathbb{R}$ be convex, and let $g_t\in \mathrm{\partial }{\mathrm{\ell }}_t(x_t)$. Take ${\alpha }_t>0$ and ${\beta }_{1,t}\in [0,1)$. Write $q_{t,i}=\sqrt{{\widehat{v}}_{t,i}}$, $Q_t=\mathrm{diag}(q_{t,1},\dots ,q_{t,d})$, and $\mathrm{\parallel }z{\mathrm{\parallel }}_{Q_t}^2:={\sum }_i{q}_{t,i}{z}_i^2,E_t(z):={\sum }_{i:q_{t,i}>0}\frac{z_i^2}{q_{t,i}},$ with zero contribution from coordinates where $q_{t,i}=0$. For the AMSGrad update, every such zero coordinate has $m_{t,i}=m_{t-1,i}=0$. Then for every comparator $u\in F$, ${\mathrm{\ell }}_t(x_t)-{\mathrm{\ell }}_t(u)\le \frac{\mathrm{\parallel }{x}_t-u{\mathrm{\parallel }}_{Q_t}^2-\mathrm{\parallel }{x}_{t+1}-u{\mathrm{\parallel }}_{Q_t}^2}{2{\alpha }_t(1-{\beta }_{1,t})}+\frac{{\alpha }_t}{2(1-{\beta }_{1,t})}{E}_t(m_t)+\frac{{\beta }_{1,t}{\alpha }_t}{2(1-{\beta }_{1,t})}{E}_t(m_{t-1})+\frac{{\beta }_{1,t}}{2{\alpha }_t(1-{\beta }_{1,t})}\mathrm{\parallel }{x}_t-u{\mathrm{\parallel }}_{Q_t}^2\mathrm{.}$

Uncorrected AMSGrad with a coordinatewise historical maximum: defines the raw-moment recurrence, weighted minimization, and zero-coordinate convention.

RMSProp, Adam, and AMSGrad moment updates are well-defined: zero historical maximum implies zero current and previous first moments.

Subgradients and the subdifferential of a convex function: a subgradient gives the supporting inequality for the loss.

Cauchy-Schwarz $\mid ⟨x,y⟩\mid \le \parallel x{\parallel }_2\parallel y{\parallel }_2$ with its equality case, the triangle inequality for $\parallel \cdot {\parallel }_2$, the parallelogram law and polarisation: Cauchy–Schwarz and the Euclidean norm identities used in the weighted Young bound.

Reddi, Kale, and Kumar, Appendix D

Run uncorrected AMSGrad for a finite horizon $T\ge 1$ with ${\alpha }_t=\alpha \mathrm{/}\sqrt{t}$, $\alpha >0$, ${\beta }_2\in (0,1)$, $0\le {\beta }_{1,t}\le {\beta }_1<\sqrt{{\beta }_2}$, and $\gamma ={\beta }_1\mathrm{/}\sqrt{{\beta }_2}$. For each coordinate, interpret $m_{t,i}^2\mathrm{/}\sqrt{{\widehat{v}}_{t,i}}$ as zero when ${\widehat{v}}_{t,i}=0$. Then ${\sum }_{t=1}^T{\alpha }_t{\sum }_{i=1}^d\frac{m_{t,i}^2}{\sqrt{{\widehat{v}}_{t,i}}}\le \frac{\alpha }{(1-{\beta }_1)(1-\gamma )\sqrt{1-{\beta }_2}}{\sum }_{i=1}^d{\sum }_{t=1}^T\frac{\mathrm{\mid }{g}_{t,i}\mathrm{\mid }}{\sqrt{t}}\mathrm{.}$

Uncorrected AMSGrad with a coordinatewise historical maximum: gives the moment recurrences, historical maximum, and time-varying first-moment weights.

RMSProp, Adam, and AMSGrad moment updates are well-defined: all moment coordinates are finite and all second-moment coordinates are nonnegative; a zero second-moment coordinate has zero first moment.

Cauchy-Schwarz $\mid ⟨x,y⟩\mid \le \parallel x{\parallel }_2\parallel y{\parallel }_2$ with its equality case, the triangle inequality for $\parallel \cdot {\parallel }_2$, the parallelogram law and polarisation: finite-coordinate Cauchy–Schwarz.

Reddi, Kale, and Kumar, Appendix D

For the scalar Adam update on $[-1,1]$ with step sizes ${\alpha }_t=\alpha \mathrm{/}\sqrt{t}$, fixed parameters ${\beta }_1\in [0,1)$ and ${\beta }_2\in (0,1)$, no bias correction, and clipping after every update, define the best-comparator regret by $R_T={\sum }_{t=1}^T{\mathrm{\ell }}_t(x_t)-{\min }_{u\in [-1,1]}{\sum }_{t=1}^T{\mathrm{\ell }}_t(u)\mathrm{.}$ For every $\alpha >0$ and every ${\beta }_1<\sqrt{{\beta }_2}$, there is an even integer $C\ge 2$ such that, with $ϵ=0$, $x_1=1$, and the periodic linear losses ${\mathrm{\ell }}_{kC+1}(x)=Cx,{\mathrm{\ell }}_{kC+j}(x)=-x(2\le j\le C,k\ge 0),$ the algorithm receives their slopes $g_{kC+1}=C$ and $g_{kC+j}=-1$, and its regret satisfies ${\mathrm{lim\hspace{0.17em}inf}}_{T\to \mathrm{\infty }}{R}_T\mathrm{/}T\ge 2\mathrm{/}C>0$.

For every fixed $ϵ>0$, there is also a counterexample for the update with denominator $\sqrt{v_t+ϵ}$: set $\alpha =1\mathrm{/}10$, ${\beta }_1=0$, ${\beta }_2=1\mathrm{/}45$, $x_1=1$, and repeat the losses ${\mathrm{\ell }}_{3k+1}(x)=3\sqrt{ϵ}x,{\mathrm{\ell }}_{3k+2}(x)={\mathrm{\ell }}_{3k+3}(x)=-\sqrt{ϵ}x(k\ge 0)\mathrm{.}$ The algorithm receives the corresponding slopes $g_{3k+1}=3\sqrt{ϵ}$ and $g_{3k+2}=g_{3k+3}=-\sqrt{ϵ}$. Then ${\mathrm{lim\hspace{0.17em}inf}}_{T\to \mathrm{\infty }}{R}_T\mathrm{/}T\ge 2\sqrt{ϵ}\mathrm{/}3>0$. In both cases the losses are convex on $[-1,1]$, and the comparator is selected separately for each finite horizon.

Uncorrected Adam for online convex losses: defines the uncorrected moment recurrences, inside-root denominator parameter, step schedule, and clipping update used in both constructions.

Polynomial factors times a geometric rate decay to zero: ensures that a sufficiently large even period satisfies the finitely many geometric-moment inequalities in the zero-epsilon construction.

Clipping a negative prefix followed by a positive suffix: bounds the clipped endpoint of a period whose update increments have a nonpositive prefix and a nonnegative suffix.

Limit superior and limit inferior of a real sequence as ${\inf }_n{\sup }_{k\ge n}{x}_k$ and ${\sup }_n{\inf }_{k\ge n}{x}_k$ in $\bar{\mathbb{R}}$: defines the limit inferior in the two average-regret conclusions.

Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length: $[-1,1]$ is the closed interval on which the losses and clipping operate.

Reddi, Kale, and Kumar, Appendix B and Appendix F

Adam diverges on a periodic bounded-gradient loss sequence: the published bias-corrected periodic example is a distinct update convention and is not used as a proof of either local Adam branch.