Adam can have nonzero average regret on a one-dimensional convex sequence

First take $ϵ=0$. Every input gradient is either $C$ or $-1$, so $v_1=(1-{\beta }_2)C^2>0$ and $v_{t+1}\ge {\beta }_2{v}_t>0$; thus every no-epsilon denominator is positive. Put $\gamma ={\beta }_1\mathrm{/}\sqrt{{\beta }_2}<1$ and $H=\frac{(1-{\beta }_1)(1+\gamma \mathrm{/}(1-\gamma ))}{\sqrt{1-{\beta }_2}}\mathrm{.}$ Choose an even $C\ge 2$ so large that $C\ge \frac{{\beta }_1}{1-{\beta }_1},{\beta }_1^{C\mathrm{/}2}\le \frac{1}{2},(1-{\beta }_1)C{\beta }_1^{C\mathrm{/}2}\le \frac{1}{4},C^2{\beta }_2^{C\mathrm{/}2}\le 1,$ $(1-{\beta }_1)C{\beta }_1^{C-1}\le 1-{\beta }_1^{C-1},\frac{C}{16}>H,\frac{\sqrt{C}}{8\sqrt{2}}>H\mathrm{.}$ Such an even integer exists by [F3], using $n=C\mathrm{/}2$ for the half-period powers and then increasing $C$ to satisfy the remaining linear and square-root bounds.

Let $s=kC$ be a period start and let $m_s$ be its first moment. Induction over periods gives $-1\le m_s\le 0$: it holds at $m_0=0$; if it holds at $s$, then $m_{s+1}={\beta }_1{m}_s+(1-{\beta }_1)C$ lies in $[0,(1-{\beta }_1)C]$, while after the following $C-1$ gradients equal to $-1$, $m_{s+C}={\beta }_1^{C-1}{m}_{s+1}-(1-{\beta }_1^{C-1})\mathrm{.}$ The last choice inequality gives $m_{s+C}\le 0$, and $m_{s+1}\ge 0$ gives $m_{s+C}\ge -(1-{\beta }_1^{C-1})\ge -1$. Thus every high-gradient update has $m_{s+1}\ge 0$. At the later positions $j=2,\dots ,C$, $m_{s+j}={\beta }_1^{j-1}(m_{s+1}+1)-1,$ which is nonincreasing in $j$. Hence the update increments ${\delta }_{s+j}=-{\alpha }_{s+j}{m}_{s+j}\mathrm{/}\sqrt{v_{s+j}}$ have a nonpositive prefix and a nonnegative suffix.

At the high-gradient round, $v_{s+1}\ge (1-{\beta }_2)C^2$ and $m_{s+1}\le (1-{\beta }_1)C$, so its negative increment has magnitude at most $\frac{\alpha (1-{\beta }_1)}{\sqrt{1-{\beta }_2}\sqrt{s+1}}\mathrm{.}$ For a low-gradient position $j\ge 2$, the high-gradient contribution gives $v_{s+j}\ge (1-{\beta }_2){\beta }_2^{j-1}{C}^2$. If its increment is negative, then $m_{s+j}>0$ and the displayed moment formula gives $m_{s+j}\le (1-{\beta }_1)C{\beta }_1^{j-1}$. Therefore the sum of all negative increments at low-gradient positions is at most $\frac{\alpha (1-{\beta }_1)}{\sqrt{1-{\beta }_2}\sqrt{s+1}}{\sum }_{j=2}^C{\gamma }^{j-1}\le \frac{\alpha (1-{\beta }_1)\gamma }{(1-\gamma )\sqrt{1-{\beta }_2}\sqrt{s+1}}\mathrm{.}$ Indeed, multiplying the finite geometric sum by $1-\gamma >0$ gives ${\sum }_{r=1}^{C-1}({\gamma }^r-{\gamma }^{r+1})=\gamma -{\gamma }^C\le \gamma$, by [F5], [F6], and [F10]. The total magnitude of negative increments in a period is thus at most $\alpha H\mathrm{/}\sqrt{s+1}$.

For $j\ge C\mathrm{/}2+1$, the moment formula and the choice of $C$ give $m_{s+j}\le (1-{\beta }_1)C{\beta }_1^{C\mathrm{/}2}-(1-{\beta }_1^{C\mathrm{/}2})\le -\frac{1}{4}\mathrm{.}$ Also $v_{s+1}\le C^2$, since the second-moment recurrence averages values in $[0,C^2]$, and subsequent unit-gradient updates give $v_{s+j}={\beta }_2^{j-1}{v}_{s+1}+1-{\beta }_2^{j-1}\le 1+C^2{\beta }_2^{C\mathrm{/}2}\le 2$. There are $C\mathrm{/}2$ such updates. Their positive increments sum to at least $\alpha C\mathrm{/}(8\sqrt{2}\sqrt{s+C})$. For $k\ge 1$, $s+C\le 2(s+1)$, so this is at least $\alpha C\mathrm{/}(16\sqrt{s+1})$; for $k=0$ it is at least $\alpha \sqrt{C}\mathrm{/}(8\sqrt{2})$. The final two conditions on $C$ therefore show that the sum $D_k={\sum }_{j=1}^C{\delta }_{s+j}$ of the period's increments is positive for every $k$, and for $k\ge 1$ it satisfies $D_k\ge \frac{\alpha (C\mathrm{/}16-H)}{\sqrt{kC+1}}\mathrm{.}$

Now fix $ϵ>0$ and use the second construction, with $b=1\mathrm{/}45$, $c=44\mathrm{/}45$, and $w_t=v_t\mathrm{/}ϵ$. Since $g_t^2\mathrm{/}ϵ$ is either $9$ or $1$, the recurrence $w_t=b{w}_{t-1}+c(g_t^2\mathrm{/}ϵ)$ gives $0\le w_t\le 9$ by induction. At a high-gradient time $3k+1$, $w_{3k+1}\ge 9c=44\mathrm{/}5$, so the magnitude of the negative update is at most $\frac{3\alpha }{\sqrt{3k+1}\sqrt{49\mathrm{/}5}}=\frac{3\sqrt{5}\alpha }{7\sqrt{3k+1}}\mathrm{.}$ At the following two low-gradient times, the recurrence and $w_{3k+1}\le 9$ give $w_{3k+2}\le 53\mathrm{/}45<5\mathrm{/}4$ and $w_{3k+3}\le 2033\mathrm{/}2025<5\mathrm{/}4$. Their denominator roots are therefore less than $3\mathrm{/}2$, so their positive increments sum to at least $\frac{2\alpha }{3}(\frac{1}{\sqrt{3k+2}}+\frac{1}{\sqrt{3k+3}})\mathrm{.}$

Apply [F4] to each period using the sign pattern from step 1.2. It gives $x_{(k+1)C+1}\ge \min \{1,x_{kC+1}+D_k\}\mathrm{.}$ The positive lower bounds in step 1.4 have divergent sum: for every $N\ge 1$, ${\sum }_{k=1}^N\frac{1}{\sqrt{kC+1}}\ge \frac{N}{\sqrt{NC+1}}\ge \frac{\sqrt{N}}{\sqrt{C+1}},$ which is unbounded by [F9]. Iterating the endpoint inequality, the boundary iterate therefore reaches $1$ after finitely many periods and equals $1$ at every later period boundary.

For $x,y\in [-1,1]$ and $\theta \in [0,1]$, the nonnegative coefficients $1-\theta$ and $\theta$ give $-1=(1-\theta )(-1)+\theta (-1)\le (1-\theta )x+\theta y\le (1-\theta )1+\theta 1=1$, so the interval is convex by [F7]. For every real slope $a$, the loss $\mathrm{\ell }(x)=ax$ satisfies $\mathrm{\ell }((1-\theta )x+\theta y)=(1-\theta )\mathrm{\ell }(x)+\theta \mathrm{\ell }(y)$; hence it is convex by [F7]. Every finite-horizon gradient sum is positive: a complete period sums to $1$, and a nonempty proper prefix of a period sums to one of $C,C-1,\dots ,2$. Thus $u=-1$ minimizes the cumulative linear loss on $[-1,1]$. In each complete period after the boundary iterate reaches $1$, the first round has regret $2C$ and each of the other $C-1$ rounds has regret at least $-2$, since every iterate lies in $[-1,1]$; each such period therefore contributes at least $2$. Each incomplete period contributes at least $-2C$, and the finitely many initial periods contribute a fixed finite amount. Hence there is a constant $K$ independent of $T$ such that $R_T\ge 2\lfloor T\mathrm{/}C\rfloor -K\ge 2T\mathrm{/}C-(2+K)$. For every $N$, all $T\ge N$ consequently satisfy $R_T\mathrm{/}T\ge 2\mathrm{/}C-(2+K)\mathrm{/}N$. By [F8] and the unboundedness in [F9], taking the supremum of these tail infima gives ${\mathrm{lim\hspace{0.17em}inf}}_{T\to \mathrm{\infty }}{R}_T\mathrm{/}T\ge 2\mathrm{/}C$.

For $k\ge 1$, $3k+2\le \frac{5}{4}(3k+1)$ and $3k+3\le \frac{3}{2}(3k+1)$. Also $2\mathrm{/}\sqrt{5}>8\mathrm{/}9$, $\sqrt{2\mathrm{/}3}>4\mathrm{/}5$, and $3\sqrt{5}\mathrm{/}7<27\mathrm{/}28$, so the low-gradient sum in step 1.5 exceeds the high-gradient magnitude by at least $\frac{\alpha }{\sqrt{3k+1}}(\frac{152}{135}-\frac{27}{28})>0.$ For the first cycle, its high update has magnitude $3\sqrt{5}\alpha \mathrm{/}7<\alpha =1\mathrm{/}10$, so $x_2>0.9$ and the two positive low updates ensure $x_4>0.9$. The displayed cycle lower bounds have divergent sum, since ${\sum }_{k=1}^N(3k+1{)}^{-1\mathrm{/}2}\ge N\mathrm{/}\sqrt{3N+1}\ge \sqrt{N}\mathrm{/}2$. The three update increments in every cycle have a nonpositive prefix and a nonnegative suffix. By [F4], their positive cumulative drift makes the boundary iterates reach $1$ and remain $1$ at cycle boundaries, as in step 2.1.

The convexity of the interval and of all linear losses follows from step 3.1, which covers every real slope. Every finite-horizon gradient sum is positive because every complete cycle sums to $\sqrt{ϵ}$ and the proper nonempty prefixes sum to $3\sqrt{ϵ}$ or $2\sqrt{ϵ}$. Hence $u=-1$ is a best comparator. A full cycle after the boundary iterate reaches $1$ has regret at least $6\sqrt{ϵ}-4\sqrt{ϵ}=2\sqrt{ϵ}$; every incomplete cycle has regret at least $-4\sqrt{ϵ}$, and the initial finite segment contributes a fixed amount. Thus there is a constant $K_{ϵ}$ independent of $T$ with $R_T\ge 2\sqrt{ϵ}\lfloor T\mathrm{/}3\rfloor -K_{ϵ}\ge 2\sqrt{ϵ}T\mathrm{/}3-(2\sqrt{ϵ}+K_{ϵ})$. Taking tail infima and then their supremum as in step 3.1 gives ${\mathrm{lim\hspace{0.17em}inf}}_{T\to \mathrm{\infty }}{R}_T\mathrm{/}T\ge 2\sqrt{ϵ}\mathrm{/}3$.