AMSGrad has an online convex regret bound under decaying first-moment weights

By [F5] and the one-step inequality [F3], sum over $t=1,\dots ,T$. With $q_{t,i}=\sqrt{{\widehat{v}}_{t,i}}$, ${\mathrm{\Phi }}_t={\sum }_i{q}_{t,i}(x_{t,i}-u_i{)}^2$, and ${\mathrm{\Psi }}_t={\sum }_i{q}_{t,i}(x_{t+1,i}-u_i{)}^2$, the resulting bound is $R_T(u)\le {\sum }_{t=1}^T[\frac{{\mathrm{\Phi }}_t-{\mathrm{\Psi }}_t}{2{\alpha }_t(1-{\beta }_{1,t})}+\frac{{\alpha }_t{E}_t(m_t)}{2(1-{\beta }_{1,t})}+\frac{{\beta }_{1,t}{\alpha }_t{E}_t(m_{t-1})}{2(1-{\beta }_{1,t})}+\frac{{\beta }_{1,t}{\mathrm{\Phi }}_t}{2{\alpha }_t(1-{\beta }_{1,t})}]\mathrm{.}$

The moment recurrence and $\mathrm{\mid }{g}_{t,i}\mathrm{\mid }\le G_{\mathrm{\infty }}$ give $0\le v_{t,i}\le G_{\mathrm{\infty }}^2$ by induction; since ${\widehat{v}}_{t,i}$ is the maximum of the raw second moments through round $t$, $q_{t,i}\le G_{\mathrm{\infty }}$. Also ${\sum }_{t=1}^T\frac{\mathrm{\mid }{g}_{t,i}\mathrm{\mid }}{\sqrt{t}}\le G_{\mathrm{\infty }}{\sum }_{t=1}^T\frac{1}{\sqrt{t}}\le 2G_{\mathrm{\infty }}\sqrt{T},$ because $1\mathrm{/}\sqrt{t}\le 2(\sqrt{t}-\sqrt{t-1})$ for $t\ge 1$. Thus the first and third terms in the bound are $O(\sqrt{T})$.

Since $q_{t,i}$ is nondecreasing and ${\alpha }_t$ is nonincreasing, $E_t(m_{t-1})\le E_{t-1}(m_{t-1})$ and ${\alpha }_t\le {\alpha }_{t-1}$ for $t\ge 2$; the $t=1$ previous-moment term is zero. Also ${\beta }_{1,t}\mathrm{/}(1-{\beta }_{1,t})\le {\beta }_1\mathrm{/}(1-{\beta }_1)$. Thus the two energy sums in step 1.1 are at most $(\frac{1}{2(1-{\beta }_1)}+\frac{{\beta }_1}{2(1-{\beta }_1)}){\sum }_{t=1}^T{\alpha }_t{E}_t(m_t)\le \frac{1}{1-{\beta }_1}{\sum }_{t=1}^T{\alpha }_t{E}_t(m_t)\mathrm{.}$

In the potential sum of step 1.1, drop the final nonpositive term $-{\mathrm{\Psi }}_T\mathrm{/}(2{\alpha }_T(1-{\beta }_{1,T}))$, since ${\mathrm{\Psi }}_T\ge 0$. Fix coordinate $i$ and put $r_{t,i}=q_{t,i}\mathrm{/}{\alpha }_t$, with $r_{0,i}=0$. The unpaired first positive potential is at most $D_{\mathrm{\infty }}^2{r}_{1,i}\mathrm{/}(2(1-{\beta }_1))$. For each $t\ge 2$, pair the positive potential at round $t$ with the negative potential from round $t-1$. Its coefficient difference is $\frac{q_{t,i}}{{\alpha }_t(1-{\beta }_{1,t})}-\frac{q_{t-1,i}}{{\alpha }_{t-1}(1-{\beta }_{1,t-1})}=\frac{r_{t,i}-r_{t-1,i}}{1-{\beta }_{1,t-1}}+r_{t,i}(\frac{1}{1-{\beta }_{1,t}}-\frac{1}{1-{\beta }_{1,t-1}})\mathrm{.}$ The first difference $r_{t,i}-r_{t-1,i}$ is nonnegative by [F1], [F7], and ${\alpha }_t=\alpha \mathrm{/}\sqrt{t}$. The reciprocal difference is nonpositive when ${\beta }_{1,t}\le {\beta }_{1,t-1}$; otherwise it equals $({\beta }_{1,t}-{\beta }_{1,t-1})\mathrm{/}((1-{\beta }_{1,t})(1-{\beta }_{1,t-1}))\le {\beta }_{1,t}\mathrm{/}(1-{\beta }_1{)}^2$. Thus the sum of all first coefficient differences, including the first-round term, is at most $D_{\mathrm{\infty }}^2{r}_{T,i}\mathrm{/}(2(1-{\beta }_1))$, because $r_{1,i}+{\sum }_{t=2}^T(r_{t,i}-r_{t-1,i})=r_{T,i}$. Summing coordinates gives $\frac{D_{\mathrm{\infty }}^2}{2{\alpha }_T(1-{\beta }_1)}{\sum }_i{q}_{T,i}\mathrm{.}$ The coefficient correction and the explicit last term of step 1.1 together contribute at most $\frac{D_{\mathrm{\infty }}^2}{2(1-{\beta }_1{)}^2}{\sum }_{t,i}\frac{{\beta }_{1,t}{q}_{t,i}}{{\alpha }_t}+\frac{D_{\mathrm{\infty }}^2}{2(1-{\beta }_1)}{\sum }_{t,i}\frac{{\beta }_{1,t}{q}_{t,i}}{{\alpha }_t}\le \frac{D_{\mathrm{\infty }}^2}{(1-{\beta }_1{)}^2}{\sum }_{t,i}\frac{{\beta }_{1,t}{q}_{t,i}}{{\alpha }_t},$ because $2-{\beta }_1\le 2$.

Apply [F4] to the energy bound in step 2.1 and combine with step 2.2. Since $1\mathrm{/}{\alpha }_T=\sqrt{T}\mathrm{/}\alpha$, this gives the displayed regret inequality.

The cumulative loss $u\mapsto {\sum }_{t=1}^T{\mathrm{\ell }}_t(u)$ is continuous by [F12], so [F9] gives a minimizer on $F$. The bound proved for arbitrary $u$ is uniform in $u$, hence it also holds for the best comparator. For any $r\in [0,1)$, [F10] gives the finite geometric identity $(1-r){\sum }_{k=0}^N{r}^k={\sum }_{k=0}^N(r^k-r^{k+1})=1-r^{N+1}\le 1$. For ${\beta }_{1,t}={\beta }_1{\lambda }^{t-1}$, use $\sqrt{t}\le t$ and reindex the finite sum to obtain ${\sum }_{t=1}^{T}t{\lambda }^{t-1}={\sum }_{j=1}^T{\sum }_{t=j}^T{\lambda }^{t-1}\le \frac{1}{1-\lambda }{\sum }_{j=1}^T{\lambda }^{j-1}\le \frac{1}{(1-\lambda {)}^2}$ so ${\sum }_t{\beta }_{1,t}\sqrt{t}$ is bounded independently of $T$. For ${\beta }_{1,t}={\beta }_1\mathrm{/}t$, it is at most ${\beta }_1{\sum }_{t=1}^{T}1\mathrm{/}\sqrt{t}\le 2{\beta }_1\sqrt{T}$ by step 1.2. Therefore the second term is bounded by a constant for the geometric schedule and by a constant times $\sqrt{T}$ for the reciprocal schedule; both give $R_T=O(\sqrt{T})$.