ON THE CONVERGENCE OF ADAM, REVISITED

STEVEN HEILMAN AND SAMPAD MOHANTY

Abstract. We show that projected Adam for online optimization with arbitrary moment decay parameters β_{1}, β_{2} ∈ [0, 1) can have average regret bounded away from zero. A similar result of Reddi-Kale-Kumar from 2018 required β_{1} < \sqrt{β_{2}}. Similar to their result, we use a three-periodic sequence of linear functions on [−1, 1] with slopes c, −1, −1, though we use c slightly larger than 2. This nonzero average regret result extends to Adam variants such as AdamW, RMSProp, NAdam, Adan, AdaMax, Muon, and to an i.i.d. variant of the three-periodic sequence of slopes for Adam.

1. Introduction

In online minimization on [−1, 1], we are presented with a sequence of functions f_{1}, f_{2}, … where f_{t}: [−1, 1] → ℝ for all t ≥ 1. At time t ≥ 1, we know f_{1}(x_{1}), …, f_{t−1}(x_{t−1}) and f′_{1}(x_{1}), …, f′_{t−1}(x_{t−1}), and we produce x_{t} ∈ [−1, 1]. For a fixed time horizon T ≥ 1, the goal is to minimize the regret R_{T} at time T against the best fixed comparator in [−1, 1], where

R_{T} := ∑_{t=1}^{T} f_{t}(x_{t}) − min_{x∈[−1,1]} ∑_{t=1}^{T} f_{t}(x).  (1)

In contemporary applications, f_{t} often depends on the t-th portion (or batch) of a large dataset. The most popular optimization method for these applications is Adam [KB15] (Adaptive Moment Estimation). Adam and its variants perform online optimization to train neural networks, transformers, large language models, etc. With nearly 250,000 citations,

[KB15] is currently one of the all time most highly cited scientific papers.

Under additional assumptions such as varying its parameters, Adam is known to converge, in the sense that R_{T} /T → 0 as T → ∞ [RKK18]. However, it is also known that Adam might not converge, i.e. there are examples of sequences of fairly reasonable functions f_{1}, f_{2}, … where projected Adam produces x_{1}, x_{2}, … with R_{T} /T not converging to 0 as T → ∞. However, these results only apply with restrictions on Adam’s parameters [RKK18]. In order to understand these parameters, let us define projected Adam.

Definition 1.1 (Adam Optimization Method [KB15]). Fix

b := β_{1} ∈ [0, 1),  q := β_{2} ∈ [0, 1),  ε ≥ 0,  α_{t} > 0, ∀ t ≥ 1.

Date: July 3, 2026.

Email: stevenmheilman@gmail.com, sbmohant@usc.edu S.H. is supported by NSF Grant CCF AF 2448108.

2020 Mathematics Subject Classification: 68W27, 65K10, 68Q32 Keywords: Adam, online optimization, regret Department of Mathematics, University of Southern California, Los Angeles, CA 90089.

Let x_{1} ∈ [−1, 1] be arbitrary. Define x_{2}, x_{3}, … ∈ [−1, 1] as follows.

m_{t} := bm_{t−1} + (1 − b)g_{t},  v_{t} := qv_{t−1} + (1 − q)g_{t}^{2},  g_{t} := f′_{t}(x_{t}),  ∀ t ≥ 1 (2)

with the standard initialization m_{0} = v_{0} = 0. The projected update with step sizes α_{t} > 0 is

x_{t+1} := Π_{[−1,1]} (x_{t} − α_{t}h_{t}) ,  h_{t} := \frac{m_{t}}{\sqrt{v_{t}} + ε},  ∀ t ≥ 1,  (3)

where Π_{[−1,1]}(x) := −1_{{x<−1}} + x1_{{−1≤x≤1}} + 1_{{x>1}} is projection of x ∈ ℝ to the nearest element of [−1, 1]. Here α_{t} is called the learning rate or step size. For example, one could use α_{t} := α/\sqrt{t} for some α > 0. Also, if ε = 0, then h_{t} is only defined when v_{t} ≠ 0.

Some authors may refer to Adam as the above optimization method, but with no projection term Π_{[−1,1]} appearing (3). We will not do that. Unless otherwise stated, we only refer to Adam as the method defined in Definition 1.1.

Remark 1.2. We define RMSProp to be the Adam optimization method with β_{1} = 0. Other implementations called RMSProp may include momentum, centering, different epsilon placement, or bias corrections; those variants require separate notation, although the same shortmemory denominator mechanism often persists.

Remark 1.3. We briefly contrast Adam with other optimization methods:

• x_{t+1} := x_{t} − α_{t}g_{t} (Gradient Descent)

• m_{t} := bm_{t−1} + g_{t}, x_{t+1} := x_{t} − α_{t}m_{t} (Heavy Ball)

• m_{t} := bm_{t−1} + f′_{t}(x_{t} − α_{t}m_{t−1}), x_{t+1} := x_{t} − α_{t}m_{t} (Nesterov Accelerated Gradient)

• m_{t} := bm_{t−1} + (1 − b)g_{t}, v_{t} := max(qv_{t−1}, |g_{t}|), h_{t} := \frac{m_{t}}{v_{t}+ε}, x_{t+1} as in (3) (AdaMax)

• Same as Adam with x_{t+1} := Π_{[−1,1]} ((1 − λα_{t})x_{t} − α_{t}h_{t}) for some λ ≥ 0 (AdamW)

• Same as Adam, but with h_{t} := \frac{β_{1}m_{t}+(1−β_{1})g_{t}}{\sqrt{v_{t}}+ε} (NAdam)

• Same as Adam, with q changing over time (NosAdam)

The main parameters that can adjust the behavior of Adam are β_{1} and β_{2}. From the recursion (2), we see that β_{1} quantifies the amount of exponentially decaying “memory” of past derivatives of f_{t} (where b = β_{1} close to 1 is a “larger” amount of such memory), since m_{t} is approximately a function of 1/ log(1/b) previous time steps. Likewise, q = β_{2} quantifies the amount of “memory” of past squared gradients of f_{t}.

Here are some cited examples of Adam used to train large language models, together with their parameter descriptions.

• BERT was trained with Adam “with learning rate of 10^{−4}, β_{1} = 0.9, β_{2} = 0.999, L2 weight decay of 0.01, learning rate warmup over the first 10,000 steps, and linear decay of the learning rate.” [DCK+19].

• GPT-3 was trained with Adam “with β_{1} = 0.9, β_{2} = 0.95, and ε = 10^{−8}, we clip the global norm of the gradient at 1.0, and we use cosine decay for learning rate down to 10% of its value” [BMR+20].

• Llama 2 was trained “using the AdamW optimizer [LH19], with β_{1} = 0.9, β_{2} = 0.95, ε = 10^{−5}. We use a cosine learning rate schedule, with warmup of 2000 steps, and decay final learning rate down to 10% of the peak learning rate. We use a weight decay of 0.1 and gradient clipping of 1.0.” [TMS+23].

• DeepSeek-V3 “employ[s] the AdamW optimizer [LH19] with hyper-parameters set to β_{1} = 0.9, β_{2} = 0.95 and weight decay 0.1.” [D24]

Despite the empirical success of Adam, it is known that it might not converge to its optimum. The main result of Reddi, Kale, and Kumar [RKK18] showed that Adam might not converge to its optimum for a sequence of linear functions on [−1, 1].

Theorem 1.4 ([RKK18, Theorem 2]). Let β_{1} < \sqrt{β_{2}}, let α > 0 and let α_{t} := α/\sqrt{t}, for all t ≥ 1. Then there exists a sequence of functions f_{1}, f_{2}, …: [−1, 1] → ℝ such that the Adam optimization method has regret satisfying: R_{T} /T does not converge to zero as T → ∞.

The example used was f_{t}(x) = −x for all t ≥ 1 except t mod c = 1, in which case f_{t}(x) = cx, for all x ∈ [−1, 1]. That is, the slope of f_{t} is c-periodic, where c is chosen to be a sufficiently large number, as a function of β_{1}, β_{2}. The idea is that the large positive slope that appears once is sufficient to offset the other smaller negative slopes.

Theorem 1.4 was also extended [RKK18, Theorem 3] to the setting where the f_{t} have random dependence on t. That is, f_{t}(x) = −x with probability 1 − p, and f_{t}(x) = cx with probability p for some appropriate 0 < p < 1, with f_{1}, f_{2}, … i.i.d. random functions. In [RKK18, Theorem 5], it is also shown that Adam can converge to its optimum if the parameters β_{1}, β_{2} change over time.

As pointed out in [RKK18], the paper that introduced Adam [KB15, Corollary 4.2] mistakenly claimed that Adam does converge, i.e. it has R_{T} /T converging to zero as T → ∞. Investigating this issue then led to Theorem 1.4.

Note that in the above four examples of BERT, GPT-3, Llama 2 and DeepSeek-V3, they already choose β_{1} < \sqrt{β_{2}}, i.e. they choose parameters where Theorem 1.4 applies.

Nevertheless, the results of [RKK18] left open the question of the existence of similar counterexamples for β_{1} ≥ \sqrt{β_{2}}. Moreover, the choice of slope c can be arbitrarily large when β_{1} or β_{2} are close to 1, i.e. c ≈ max(1/ log(1/β_{1}), 1/ log(1/β_{2})) is required in [RKK18]. So, it was not clear if an example for Adam with nonzero average regret could be constructed with uniformly bounded slopes, even when β_{1} < \sqrt{β_{2}}.

1.1. Our Contribution. In this work we provide such a family of examples with nonzero average regret for Adam for all parameters β_{1}, β_{2} ∈ [0, 1) and with uniformly bounded gradients.

Theorem 1.5 (Main). Let α_{t} > 0 with lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1, ∑_{t=1}^{∞} α_{t} = ∞. ∀ β_{1}, β_{2} ∈ [0, 1), ε ≥ 0, ∃ f_{1}, f_{2}, …: [−1, 1] → ℝ with 1 ≤ |f′_{t}(x)| ≤ 3, ∀ t ≥ 1, x ∈ [−1, 1] such that Adam has regret satisfying: R_{T} /T does not converge to zero as T → ∞.

The example we use is simply f_{t}(x) = −x for all t ≥ 1 except t mod 3 = 1, in which case f_{t}(x) = (2 + δ)x, for all x ∈ [−1, 1], where δ > 0 is chosen to be sufficiently small, depending on β_{1}, β_{2}, ε. That is, the slope of f_{t} is 3-periodic.

Since 1 ≤ |f′_{t}(x)| ≤ 3 for all t ≥ 1, x ∈ [−1, 1], the derivatives of the functions are uniformly bounded above and below, for all β_{1}, β_{2}.

This same example showed nonzero regret of the β_{1} = 0 case (known as RMSProp) of Adam in [RKK18, Theorem 6] and [HWD19, Lemma 1], inspiring Theorem 1.5.

Despite the similarity of our example to the one from [RKK18], our analysis is different and arguably simpler.

As in [RKK18, Theorem 6] in the β_{1} = 0 case of Adam, we show that every three iterations of Adam leads to a net positive movement of x_{1}, x_{2}, … towards the point x = 1, whereas the regret minimizer is x = −1. However, we depart from [RKK18] by using an elementary fixed point argument via the contractive mapping theorem. A related perspective was used in [BW19], albeit for quadratic functions.

This example also shows nonzero average regret for AdamW, RMSProp, NAdam, Adan, AdaMax, and Muon.

One might naturally ask if Theorem 1.5 holds when the highly structured periodic f_{1}, f_{2}, … is changed to a less structured i.i.d. variant of the above example, e.g. if for any t ≥ 1, f_{t}(x) = ax with probability 1/3, and f_{t}(x) = −x with probability 2/3, where f_{1}, f_{2}, … are all i.i.d. We show the same nonzero average regret conclusion does hold in this case. We present this result in the Appendix, Section A. Consequently, the 3-periodicity of the example used in Theorem 1.5 is not required to obtain the theorem’s conclusion.

The proof of Theorem 1.5 is written for the uncorrected moments. The same projected update with standard bias-corrected moments, with

m̃_{t} = \frac{m_{t}}{1 − b^{t}} ,  ṽ_{t} = \frac{v_{t}}{1 − q^{t}} ,  h_{t} := \frac{m̃_{t}}{\sqrt{ṽ_{t}} + ε},

has the same asymptotic properties, since (1 − b^{t})^{−1} and (1 − q^{t})^{−1} tend to one as t → ∞. Therefore the same asymptotic argument applies to the bias-corrected case.

1.2. Outline of Proof of Theorem 1.5.

• Let a ≥ 2. Let f_{3k+1}(x) = ax and f_{3k+2}(x) = f_{3k+3}(x) = −x for all k ≥ 0, x ∈ ℝ.

• A contractive mapping argument shows (m_{3k+1}, m_{3k+2}, m_{3k+3}) and (v_{3k+1}, v_{3k+2}, v_{3k+3}) from (2) converge to (M_{1}(a), M_{2}(a), M_{3}(a)) and (V_{1}(a), V_{2}(a), V_{3}(a)), as k → ∞.

• Verify that the negative mean drift S(a) := ∑_{i=1}^{3} \frac{M_{i}(a)}{\sqrt{V_{i}(a)}+ε} of x_{1}, x_{2}, … from three

iterations of Adam, is negative when a = 2.

• A continuity argument shows, for δ > 0 small enough, S(a) = S(2 + δ) < 0, so the negative mean drift is still negative for such a.

• Conclude then that lim_{t→∞} x_{t} = 1.

• Since ∑_{t=1}^{3} f_{t}(x) = δx, ∑_{t=1}^{T} f_{t}(x) is minimized at x = −1 for T large, so

lim_{T →∞} R_{T} /T = 2δ/3 > 0, thereby completing the proof. This argument is flexible enough to extend to other variants of Adam.

Theorem 1.6. Theorem 1.5 also holds for: AdamW, NAdam, Adan, AdaMax and Muon

Theorem 1.7. Let α > 0. Then Theorem 1.5 holds almost surely for Adam with i.i.d. selection of the functions f_{1}, f_{2}, . . .. and with step size α_{t} = α/\sqrt{t} for all t ≥ 1

1.3. Organization. Theorem 1.5 will be proven in Section 5, by combining the previous Sections 2, 3 and 4.

Theorem 1.6 will be stated more formally as separate versions of Theorem 1.5, spread across the following sections: 6 for AdamW; 7 for NAdam; 8 for Adan; 9 for AdaMax; and 10 for Muon. Theorem 1.7 is proven in Section A.

1.4. Further Discussion and Related Work.

1.4.1. Adam Alternatives such as AMSGrad. Due to the convergence issues they found for Adam, Reddi et al. [RKK18] proposed AMSGrad, which adds an additional parameter v̂_{t} to Definition 1.1, and then changes (3) to

x_{t+1} := Π_{[−1,1]} (x_{t} − α_{t}h_{t}) ,  h_{t} := \frac{m_{t}}{\sqrt{v̂_{t}} + ε},  v̂_{t} := max(v_{t}, v̂_{t−1}) ∀ t ≥ 1,

With this change, the previous periodicity issues for the squared gradient are removed. AMSGrad then has provable regret bounds of the form R_{T} = O(T^{1/2}), so in particular R_{T} /T → 0 as T → ∞ [AMM+20], assuming β_{1} < \sqrt{β_{2}}. ([RKK18] also proved a regret bound of this form, but it needed to assume that β_{1} decreased over time.)

Despite the superior theoretical guarantees of AMSGrad when compared to Adam, it appears that Adam is still more widely used in practice.

Subsequent variants, including Yogi [ZRS+18] and AdaBound/AMSBound [LXL+19], were partly motivated by overcoming Adam’s convergence issues found in [RKK18].

1.4.2. Adam divergence with unbounded gradients. In this work, we fix the parameters β_{1}, β_{2} ∈ [0, 1), and then produce an example of nonzero average regret for Adam with derivatives uniformly bounded above and below. One might make these choices in the opposite order, i.e. fixing a function sequence (with possibly large derivatives) and then choosing β_{1}, β_{2} to obtain a convergent method. The latter perspective is taken in [ZCS+22, ZLC+26]. They show it is possible to choose β_{1}, β_{2} (after the functions being optimized are fixed) such that Adam converges.

They also show that, for any 0 ≤ β_{1}, β_{2} < 1, there are functions such that Adam on the real line (without projection) diverges. Their example [ZLC+26, Equation (3.1)] is the following quadratic modification of [RKK18]: for any x ∈ ℝ, a > 0, 1 ≤ i ≤ n − 1, n ≥ 4,

f_{0}(x) := \begin{cases}(1 + (n − 1)a)x & , if x ≥ −1 \\ \frac{(1+(n−1)a)}{2}(x + 2)^{2} − \frac{3n}{2} & , if x < −1. \end{cases} f_{i}(x) := \begin{cases}−ax & , if x ≥ −1 \\ −\frac{a}{2}(x + 2)^{2} + \frac{3}{2} & , if x < −1. \end{cases}

There are, however, some issues with this example, namely these functions are discontinuous unless a = 1, and the proof of [ZLC+26, Theorem 3.5] is only provided when a = 1 and when the step size is constant in each training epoch. These issues are fixable, but more importantly condition C1 [ZLC+26, Equation (8.3)] seems to require β_{1} < \sqrt{1 − β_{2}}, i.e. not all β_{1}, β_{2} ∈ [0, 1) are covered by their proof for the a = 1 case; similarly, the suggested choice of a = (n − 1)^{−2} does not seem to allow all β_{1}, β_{2} values in condition C1. Also, condition C3 [ZLC+26, Equation (8.5)] requires choosing a suitably small step size. In any case, [ZLC+26, Theorem 3.5] is incomparable to our Theorem 1.5 since their functions have quadratic components with unbounded gradients on an unbounded domain, whereas our functions have gradients bounded above and below on the bounded domain [−1, 1] with projection onto that domain. Despite the above issues, the following modification should reproduce the result of [ZLC+26, Theorem 3.5]: f_{i}(x) = −x^{2} for 0 < i < 2n/3 and f_{i}(x) = 16x^{2} for 2n/3 ≤ i ≤ n − 1, where n is chosen sufficiently large depending on β_{1}, β_{2}, since on the set [0, ∞) we have m_{i}/\sqrt{v_{i}} ≈ −1 for most 0 < i < 2n/3 and m_{i}/\sqrt{v_{i}} ≈ 1 for most 2n/3 ≤ i ≤ n − 1, so that x_{1}, x_{2}, … tends toward +∞ while the true minimum occurs at 0.

A different perspective for Adam is taken in Ahn, Zhang, Kook, and Dai [AZK+24] where they interpret Adam as a discounted Follow-the-Regularized-Leader method.

1.4.3. Dynamical Systems Approach. Da Silva and Gazeau [BG20] derive a continuous-time ODE system for adaptive first-order methods and analyze the convergence and stability of the limiting dynamics.

Bai, Zhao, Zhou, Xu, and Zhang [BZZ+26] study Adam on highly degenerate polynomials and give a hyperparameter phase diagram containing stable convergence, spikes, and SignGD-like oscillation regimes. These papers concern related adaptive optimizers and stability phenomena, but not the bounded online-linear regret setting of Theorem 1.5.

1.4.4. Nonconvergence in traditional stochastic optimization frameworks. The results below concern traditional stochastic optimization, instead of online optimization.

Wang and Klabjan [WK22] give stochastic divergence examples for Adam in unconstrained strongly convex optimization, including examples that diverge in expectation or with high probability and examples that persist for large mini-batches. They also propose a variancereduced Adam-type method and prove convergence under a variance-reduction assumption.

Dereich, Graeber, and Jentzen [DGJ24] prove a nonconvergence result for Adam and other adaptive stochastic-gradient methods when the learning rates are asymptotically bounded away from zero.

Dereich, Do, Jentzen, and von Wurstemberger [DDJ+25] prove an Adam symmetry theorem for stochastic strongly convex quadratic problems. In their formulation, Adam converges to the true minimizer if and only if the data distribution is symmetric.

Jentzen and Riekert [JR25] prove that Adam and SGD-type methods can fail with high probability to converge to global minimizers in shallow ReLU-network training landscapes. Do, Hannibal, and Jentzen [DHJ24] prove analogous high-probability nonconvergence to global minimizers for a broad class of SGD methods, including Adam, in data-driven supervised deep learning with ReLU activations. Do, Jentzen, and Riekert [DJR25] show nonconvergence of the true risk to the optimal risk for a large class of SGD-type methods, again including Adam.

Toint [Toi23] gives a very simple deterministic one-dimensional example showing that fixed-stepsize Adam can diverge on a smooth function with Lipschitz continuous gradient, without gradient noise, irrespective of the method parameters.

1.4.5. Contrast with NosAdam, AMSGrad, AdaGrad. The one-dimensional counterexample we presented for the nonzero average regret of Adam and its relatives does not extend in a straightforward way to Adam variants with “longer long-term memory” such as AdaGrad, AMSGrad, NosAdam, etc. For example, instead of using the iteration for v_{t} from (2), AMS-Grad keeps track of the maximum of v_{t} with the additional parameter v̂_{t} := max(v_{t}, v̂_{t−1}), and it then uses h_{t} := \frac{m_{t}}{\sqrt{v̂_{t}}+ε} in (3). This eliminates the periodicity issue of v_{t} that occurs for these counterexamples. And indeed, these other methods often have better provable regret bounds than Adam.

2. Steady-state Moments via Contraction

We now prepare to prove Theorem 1.5. We first show the promised convergence of m_{3k+i} and v_{3k+1} as k → ∞ using the contractive mapping theorem.

Throughout this paper, we assume the gradients g_{t} = f′_{t}(x_{t}) from (2) satisfy

g_{3k+1} = a = 2 + δ,  g_{3k+2} = −1,  g_{3k+3} = −1,  ∀ k ≥ 0  (4)

where δ > 0 will be chosen sufficiently small.

Lemma 2.1. Assume (4) holds. Then there exist unique triples (M_{1}, M_{2}, M_{3}) and (V_{1}, V_{2}, V_{3}) that are fixed points of three iterations of (2). Moreover, |m_{3k+i} − M_{i}| ≤ O(b^{3k}) and |v_{3k+i} − V_{i}| ≤ O(q^{3k}) for all k ≥ 0, 1 ≤ i ≤ 3.

Note that, by (4), the iteration (2) does not depend on x_{t}.

Remark 2.2. We will show using elementary algebra that

M_{1}(a) = \frac{a − b − b^{2}}{1 + b + b^{2}} ,  M_{2}(a) = \frac{ab − b^{2} − 1}{1 + b + b^{2}},  M_{3}(a) = \frac{ab^{2} − b − 1}{1 + b + b^{2}}.  (5)
V_{1}(a) = \frac{a^{2} + q + q^{2}}{1 + q + q^{2}} ,  V_{2}(a) = \frac{a^{2}q + q^{2} + 1}{1 + q + q^{2}},  V_{3}(a) = \frac{a^{2}q^{2} + q + 1}{1 + q + q^{2}}.  (6)

Here we added the parameter a to our notation to emphasize the dependence of M_{i}, V_{i} on a.

Proof. Let M_{1} ∈ ℝ. Recall g_{1} = a, g_{2} = g_{3} = −1, by (4), so two iterations of (2) give

M_{2} =^{(2)} bM_{1} − (1 − b),  t = 2  (7)
M_{3} =^{(2)} bM_{2} − (1 − b) =^{(7)} b^{2}M_{1} − (1 − b)(1 + b),  t = 3.  (8)

If we have a fixed point (M_{1}, M_{2}, M_{3}), then (2) for t = 4 should return to M_{1}, i.e. M_{1} would be equal to (using g_{4} = a)

bM_{3} + (1 − b)a =^{(8)} b^{3}M_{1} + (1 − b)(a − b − b^{2}).

Thus the one-period return map for M_{1} is the affine contraction Φ_{b}: ℝ → ℝ defined by

Φ_{b}(M) := b^{3}M + (1 − b)(a − b − b^{2}),  ∀ M ∈ ℝ.  (9)

Since b ∈ [0, 1), we have b^{3} < 1, so Φ_{b} has a unique fixed point by the contractive mapping theorem (|Φ_{b}(M)−Φ_{b}(M′)| ≤ b^{3}|M −M′| < |M −M′| for all M, M′ ∈ ℝ). Similarly, M_{2}, M_{3} are each the unique fixed point of a contraction, each of the form M ↦ b^{3}M + constant. Solving for M_{1} in Φ_{b}(M_{1}) = M_{1} gives the first part of (5), then (7) and (8) yield the last part of (5). The contraction property for Φ_{b} implies |m_{3k+i} − M_{i}| ≤ O(b^{3k}), ∀ k ≥ 0, 1 ≤ i ≤ 3.

The argument for (V_{1}, V_{2}, V_{3}) is analogous. Since g_{t} does not depend on x_{t}, three iterations of (2) for v_{t} results in a contractive mapping of the form Ψ_{q}(V) := q^{3}V + constant, i.e.

Ψ_{q}(V) := q^{3}V + (1 − q)(a^{2} + q + q^{2}),  ∀ V ∈ ℝ.  (10)

Since q ∈ [0, 1), this map has a unique fixed point V_{1}, by the contractive mapping theorem. Solving for Ψ_{q}(V_{1}) = V_{1} produces the first equation in (6), and then (2) yields the last two parts of (6). The contraction property implies |v_{3k+i} − V_{i}| ≤ O(q^{3k}), ∀ k ≥ 0, 1 ≤ i ≤ 3.

□

3. Drift Away from the Minimizer

In Lemma 2.1, we found exponential convergence of the m_{3k+i} and v_{3k+i} terms from (2) to their limiting values as k → ∞, ∀ 1 ≤ i ≤ 3. In this section, we then deduce the “drift” of the iterates x_{t} themselves to the right endpoint x = 1. This “drift” will be quantified by

S(a) := ∑_{i=1}^{3} \frac{M_{i}(a)}{\sqrt{V_{i}(a)} + ε}.  (11)

If S(a) < 0, then the Adam update x ↦ x − α_{t}h_{t} has positive net drift toward x = 1.

Lemma 3.1. There exists d ∈ (0, 1) such that, for all 0 ≤ δ ≤ d, a := 2 + δ satisfies

S(a) < 0,  M_{1}(a) > 0,  M_{2}(a) < 0,  M_{3}(a) < 0.  (12)

Proof. Let a = 2. Since b ∈ [0, 1), we have by (5) that

M_{1}(2) = \frac{(1 − b)(2 + b)}{1 + b + b^{2}} > 0, M_{2}(2) = −\frac{(1 − b)^{2}}{1 + b + b^{2}} < 0, M_{3}(2) = −\frac{(1 − b)(1 + 2b)}{1 + b + b^{2}} < 0.

(13)

Moreover,

M_{1}(2) + M_{2}(2) + M_{3}(2) = 0.  (14)

For the second moment, we have by (6)

V_{1}(2) = \frac{4 + q + q^{2}}{1 + q + q^{2}} ,  V_{2}(2) = \frac{1 + 4q + q^{2}}{1 + q + q^{2}} ,  V_{3}(2) = \frac{1 + q + 4q^{2}}{1 + q + q^{2}} .  (15)

Since q < 1,

V_{1}(2) − V_{2}(2) =^{(15)} \frac{3(1 − q)}{1 + q + q^{2}} > 0, V_{1}(2) − V_{3}(2) =^{(15)} \frac{3(1 − q^{2})}{1 + q + q^{2}} > 0.

Therefore

\sqrt{V_{1}(2)} + ε > \sqrt{V_{2}(2)} + ε,  \sqrt{V_{1}(2)} + ε > \sqrt{V_{3}(2)} + ε.  (16)

Let

A := −M_{2}(2) >^{(13)} 0,  B := −M_{3}(2) >^{(13)} 0.  (17)

Since M_{1}(2) = A + B by (14), we obtain

\begin{aligned}S(2) & =^{(11)} \frac{A + B}{\sqrt{V_{1}(2)} + ε} − \frac{A}{\sqrt{V_{2}(2)} + ε} − \frac{B}{\sqrt{V_{3}(2)} + ε} \\ & = A (\frac{1}{\sqrt{V_{1}(2)} + ε} − \frac{1}{\sqrt{V_{2}(2)} + ε}) + B (\frac{1}{\sqrt{V_{1}(2)} + ε} − \frac{1}{\sqrt{V_{3}(2)} + ε}) <^{(16)∧(17)} 0. \end{aligned}

(18)

This strict negativity holds for every b, q ∈ [0, 1) and every ε ≥ 0.

By continuity of S(a) via (11), (5) and (6), there exists d > 0 such that (12) holds for all 0 ≤ δ ≤ d. Replacing d by min(d, .9) completes the proof. □

4. A projection lemma

The net drift result of Section 3 does not immediately apply to Adam, due to the projection term Π_{[−1,1]} in (3). In this section, we therefore analyze this projection term applied thrice.

Lemma 4.1. Let P = Π_{[−1,1]} so P (x) = −1_{{x<−1}} + x1_{{−1≤x≤1}} + 1_{{x>1}} for all x ∈ ℝ. If u_{1} ≤ 0, u_{2} ≥ 0, u_{3} ≥ 0, and U := u_{1} + u_{2} + u_{3}, then for every x ∈ [−1, 1],

P (P (P (x + u_{1}) + u_{2}) + u_{3}) ≥ P (x + U).  (19)

Consequently, if U ≥ c > 0, then

P (P (P (x + u_{1}) + u_{2}) + u_{3}) ≥ min(1, x + c).  (20)

Proof. Let x ∈ [−1, 1]. Since x ≤ 1 and u_{1} ≤ 0, we have x + u_{1} ≤ 1, hence

P (x + u_{1}) = max(−1, x + u_{1}) ≥ x + u_{1}.

Also, for any z ∈ ℝ and any w ≥ 0,

P (P (z) + w) ≥ P (z + w).  (21)

Indeed, if z ≤ 1, then P (z) ≥ z, and the claim follows from monotonicity of P; if z > 1, both sides are equal to 1 since P (z) = 1 and w ≥ 0. Applying (21) twice (using u_{2}, u_{3} ≥ 0)

P (P (P (x + u_{1}) + u_{2}) + u_{3}) ≥ P (x + u_{1} + u_{2} + u_{3}) = P (x + U).

So (19) holds. Now, assume U ≥ c > 0. Then monotonicity of P gives

P (x + U) ≥ P (x + c) = min(1, x + c),

where the last equality uses x ∈ [−1, 1] so that x + c ≥ −1. □

5. Main theorem

We now prove Theorem 1.5, restated as Theorem 5.1 below.

Theorem 5.1. Fix b, q ∈ [0, 1), ε ≥ 0, and α_{t} satisfying lim_{t→∞} α_{t} = 0, lim_{t→∞} α_{t+1}/α_{t} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. There exists δ > 0, depending only on b, q and ε, such that for every initial point x_{1} ∈ [−1, 1], projected Adam on [−1, 1] applied to

f_{3k+1}(x) = (2 + δ)x,  f_{3k+2}(x) = −x,  f_{3k+3}(x) = −x,  (22)

satisfies

lim_{t→∞} x_{t} = 1.  (23)

For every horizon T ≥ 1, the best fixed comparator in [−1, 1] is x_{T}^{∗} = −1, and the average regret satisfies

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} > 0.  (24)

Proof. Choose δ > 0 so that (12) holds. Let a := 2 + δ. Since the m_{3k+i} and v_{3k+i} terms converge as k → ∞ by Lemma 2.1 ∀ 1 ≤ i ≤ 3, (3) implies that the h_{3k+i} terms also converge:

lim_{k→∞} h_{3k+i} = H_{i} := \frac{M_{i}(a)}{\sqrt{V_{i}(a)} + ε},  ∀ i = 1, 2, 3.  (25)

By (12),

H_{1} > 0, H_{2} < 0, H_{3} < 0, H_{1} + H_{2} + H_{3} = S(a) < 0. (26)

Let η := −S(a) > 0. Define the three unprojected increments

u_{k,i} := −α_{3k+i}h_{3k+i},  ∀ k ≥ 0,  i = 1, 2, 3.  (27)

Then for all k sufficiently large, (26) and (25) imply

u_{k,1} < 0,  u_{k,2} > 0,  u_{k,3} > 0.  (28)

Furthermore, using lim_{t→∞} α_{t+1}/α_{t} = 1,

U_{k} := u_{k,1} +u_{k,2} +u_{k,3} =^{(27)} − ∑_{i=1}^{3} α_{3k+i}h_{3k+i} =^{(25)} −α_{3k+1} ·(∑_{i=1}^{3} H_{i} + o_{k}(1)) = α_{3k+1}(η+o_{k}(1)).

Consequently, there are constants c > 0 and k_{0} ≥ 1 such that

U_{k} ≥ c · α_{3k+1} for all k ≥ k_{0}.  (29)

Let z_{k} := x_{3k+1} be the iterate at the start of a period, for all k ≥ 0. Applying Lemma 4.1 with u_{i} = u_{k,i} for each 1 ≤ i ≤ 3 which is valid by (28) and (29),

z_{k+1} ≥^{(3)∧(27)} min (1, z_{k} + c · α_{3k+1}),  ∀ k ≥ k_{0}.  (30)

Since z_{k} ≤ 1 for all k ≥ 1 and ∑_{k≥k_{0}} α_{k} = ∞, we have ∑_{k≥k_{0}} α_{3k+1} = ∞, which follows since lim_{k→∞} α_{k+1}/α_{k} = 1. Then iterating (30) forces z_{k} to equal 1 after finitely many periods. Indeed, once ∑_{k=k_{0}}^{k_{1}} c · α_{3k+1} > 1 − z_{k_{0}} for some k_{1} > k_{0}, (30) gives z_{k+1} ≥ 1, while projection onto [−1, 1] from (3) gives z_{k+1} ≤ 1. Then ∀ k > k_{1}, (30) gives z_{k+1} = 1 whenever z_{k} = 1.

This implies convergence of the full sequence (x_{t}) to 1, since the within-period moves have magnitude O(α_{t}). To see this, note by (2) that (m_{t}) is bounded since (g_{t}) is bounded, i.e. |m_{t}| ≤ max(|m_{t−1}|, |g_{t}|) ≤ 3 for all t ≥ 0. Also, since |g_{t}| ≥ 1 for every t,

v_{t} =^{(2)} qv_{t−1} + (1 − q)g_{t}^{2} ≥^{(2)} 1 − q > 0.

Hence

|h_{t}| =^{(3)} |\frac{m_{t}}{\sqrt{v_{t}} + ε}| ≤ \frac{3}{\sqrt{1 − q}} , ∀ t ≥ 1.

Therefore |x_{t+1} − x_{t}| ≤ |α_{t}|\frac{3}{\sqrt{1−q}}, ∀ t ≥ 1. Since x_{3k+1} → 1 as k → ∞ and lim_{t→∞} α_{t} = 0, this implies that x_{t} → 1 as t → ∞. That is, (23) holds.

It remains to prove (24). For any T ≥ 1, let

G_{T} := ∑_{t=1}^{T} g_{t}.  (31)

Writing T = 3k + r, r ∈ {0, 1, 2}, gives (recalling a = 2 + δ)

G_{T} =^{(4)} \begin{cases}kδ, & r = 0, \\ kδ + a, & r = 1, \\ kδ + a − 1, & r = 2. \end{cases}  (32)

All three quantities are positive since a = 2 + δ and δ > 0. Therefore the best fixed comparator is always x_{T}^{∗} = −1, and

min_{x∈[−1,1]} ∑_{t=1}^{T} f_{t}(x) =^{(22)∧(31)} G_{T} · min_{x∈[−1,1]} x = −G_{T} .  (33)

The regret is then

R_{T} =^{(1)∧(22)∧(33)} ∑_{t=1}^{T} g_{t}x_{t} + G_{T} =^{(31)} ∑_{t=1}^{T} g_{t} · (x_{t} + 1).  (34)

Since lim_{t→∞} x_{t} = 1 by (23) and (g_{t}) is bounded by (4),

lim_{T →∞} \frac{1}{T} ∑_{t=1}^{T} g_{t} · (x_{t} − 1) = 0.

Also lim_{T →∞} G_{T} /T = δ/3 by (32). Hence

\frac{R_{T}}{T} =^{(34)∧(31)} \frac{2G_{T}}{T} + \frac{1}{T} ∑_{t=1}^{T} g_{t}(x_{t} − 1) → \frac{2δ}{3} , as T → ∞.

This proves (24) and completes the proof. □

6. AdamW

We now define AdamW and extend Theorem 1.5 to AdamW.

Definition 6.1 (AdamW Optimization Method). Let x_{1} ∈ [−4, −2] be arbitrary. Define x_{2}, x_{3}, … ∈ [−4, −2] as follows. The first and second moment recursions of AdamW [LH19] with parameters b = β_{1} and q = β_{2} are the same as Adam, i.e. (2) holds, with the standard initialization m_{0} = v_{0} = 0. The projected update then adds a single extra term λ ≥ 0 to (3) as follows

x_{t+1} := Π_{[−4,−2]} ((1 − λα_{t})x_{t} − α_{t}h_{t}) ,  h_{t} := \frac{m_{t}}{\sqrt{v_{t}} + ε},  ∀ t ≥ 1.  (35)

Theorem 6.2 (AdamW Counterexample). Let α_{t} > 0 satisfy lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. Fix β_{1}, β_{2} ∈ [0, 1), ε ≥ 0 and λ ≥ 0. Consider projected AdamW on the domain F = [−4, −2]. Then there exists δ > 0, depending only on b, q, ε, such that for the linear functions (22), the iterates of AdamW satisfy

lim_{t→∞} x_{t} = −2.

However, the best fixed comparator is x^{∗} = −4, and

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

Proof. Define u_{k,i} from (27). The corresponding increments for AdamW are then

u_{k,i} − λα_{3k+i}x_{3k+i}.

On F = [−4, −2], we have x_{3k+i} ≤ −2, and hence

−λα_{3k+i}x_{3k+i} ≥ 0.

We now adapt the remaining parts of Theorem 5.1 to AdamW.

Put F = [−4, −2], and for any t ≥ 1, let

u_{t} := −α_{t}h_{t}.

For fixed t, g_{t} is a constant that does not depend on x_{t}, so (h_{t}) also does not depend on x_{t}. Since lim_{t→∞} α_{t} = 0, we may choose T = 3K + 1 sufficiently large that

0 ≤ λα_{t} ≤ 1, ∀ t ≥ T.

For any t ≥ T, define the one-step maps

A_{t}(x) := Π_{F}(x + u_{t}),  W_{t}(x) := Π_{F}((1 − λα_{t})x + u_{t}),  ∀ x ∈ [−4, −2].

The map W_{t} is nondecreasing since 1 − λα_{t} ≥ 0 and Π_{F} is nondecreasing. Furthermore, for every x ∈ F,

(1 − λα_{t})x + u_{t} = x + u_{t} − λα_{t}x ≥ x + u_{t},

since x ≤ −2 < 0. Therefore

W_{t}(x) ≥ A_{t}(x),  ∀ x ∈ F.  (36)

Let (y_{t})_{t≥T} be the auxiliary projected Adam sequence without weight decay, initialized by

y_{T} := x_{T} ,  y_{t+1} := A_{t}(y_{t}),  ∀ t ≥ T.

The period-three argument from Theorem 5.1, translated from [−1, 1] to F = [−4, −2], gives lim_{t→∞} y_{t} = −2. We claim that

x_{t} ≥ y_{t}, ∀ t ≥ T.

This holds at time T by definition of y_{T}. If it holds at any t ≥ T, then monotonicity of W_{t} and (36) give

x_{t+1} =^{(35)} W_{t}(x_{t}) ≥ W_{t}(y_{t}) ≥ A_{t}(y_{t}) = y_{t+1}.

Thus the claim follows by induction. Since both sequences lie in [−4, −2], −2 ≥ x_{t} ≥ y_{t} and lim_{t→∞} y_{t} = −2 imply that lim_{t→∞} x_{t} = −2.

The cumulative gradient over each period is still δ > 0, so the best fixed comparator on [−4, −2] is the left endpoint −4. Since the iterates converge to the right endpoint −2 and the interval length is 2, the same regret computation from (24) gives lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3}. □

7. NAdam

We now define NAdam and extend Theorem 1.5 to NAdam. Recall that projected NAdam is defined exactly as in Definition 1.1, but instead of the h_{t} from (3) we have

h_{t} := \frac{bm_{t} + (1 − b)g_{t}}{\sqrt{v_{t}} + ε} , ∀ t ≥ 1.

Theorem 7.1 (NAdam Counterexample). Let α_{t} > 0 satisfy lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. Fix b, q ∈ [0, 1), ε ≥ 0. Consider projected NAdam on the domain F = [−1, 1]. Then there exists δ > 0, depending only on b, q, ε, such that for the linear functions (22), the iterates of NAdam satisfy

lim_{t→∞} x_{t} = 1.

However, the best fixed comparator is x^{∗} = −1, and

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

Proof. The recursions for m_{t} and v_{t} are identical to Adam, so Lemma 2.1 applies, and the limiting values M_{i}, V_{i} from Lemma 2.1 are unchanged. For NAdam with a = 2, the limiting numerators of the h terms are U_{1}, U_{2}, U_{3} where

U_{i} = bM_{i}(2) + (1 − b)g_{i}, ∀ i ∈ {1, 2, 3}.

Since ∑_{i=1}^{3} M_{i}(2) = 0, by (5) and ∑_{i=1}^{3} g_{i} = 0, when a = 2, we have U_{1} + U_{2} + U_{3} = 0. Moreover U_{1} > 0 and U_{2}, U_{3} < 0, since both M_{i}(2) and g_{i} have these signs by (12) and (4). The remaining details follow those of Adam in Theorem 5.1 with S_{NAdam}(a) := ∑_{i=1}^{3} \frac{U_{i}(a)}{\sqrt{V_{i}(a)}+ε},

U_{i}(a) := bM_{i}(a) + (1 − b)g_{i} for all i ∈ {1, 2, 3}. For example, S_{NAdam}(2) < 0 by repeating the proof of (18) mutatis mutandis, so S_{NAdam}(a) < 0 for all a ∈ ℝ near 2, and so on. □

8. Adan

We define the Adan optimization method [XZL+24] and extend Theorem 1.5 to it. Let

b := β_{1},  q := β_{2},  r := β_{3},  b, q, r ∈ [0, 1).

Let g_{0} := −1, m_{0} = d_{0} = n_{0} := 0. For any t ≥ 1, define

m_{t} := bm_{t−1} + (1 − b)g_{t},
d_{t} := qd_{t−1} + (1 − q)(g_{t} − g_{t−1}),

n_{t} := rn_{t−1} + (1 − r)(g_{t} + q(g_{t} − g_{t−1}))^{2}.

x_{t+1} := Π_{[−1,1]} (x_{t} − α_{t}h_{t}) , h_{t} := \frac{m_{t} + qd_{t}}{\sqrt{n_{t}} + ε} .

This definition in terms of decay coefficients b, q, r may differ from other definitions.

Theorem 8.1 (Adan Counterexample). Let α_{t} > 0 satisfy lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. Fix b, q, r ∈ [0, 1), ε ≥ 0. Consider projected Adan on the domain F = [−1, 1]. Then there exists δ > 0, depending only on b, q, r, ε, such that for the linear functions (22), the iterates of Adan satisfy

lim_{t→∞} x_{t} = 1.

However, the best fixed comparator is x^{∗} = −1, and

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

Proof. Since g_{t} does not depend on x_{t}, three Adan iterations for m_{t} or d_{t} or n_{t} results in a contractive mapping. For example, m_{3k+1} ↦ m_{3(k+1)+1} corresponds to a map M ↦ b^{3}M + constant. Since this map is a contraction from ℝ to ℝ, it has a unique fixed point, by the contractive mapping theorem. Thus, lim_{k→∞}(m_{3k+1}, m_{3k+2}, m_{3k+3}) =: (M_{1}, M_{2}, M_{3}), lim_{k→∞}(n_{3k+1}, n_{3k+2}, n_{3k+3}) =: (N_{1}, N_{2}, N_{3}), lim_{k→∞}(d_{3k+1}, d_{3k+2}, d_{3k+3}) =: (D_{1}, D_{2}, D_{3}).

The first-moment values from (13) are

M_{1} = \frac{2 − b − b^{2}}{1 + b + b^{2}} , M_{2} = \frac{2b − b^{2} − 1}{1 + b + b^{2}}, M_{3} = \frac{2b^{2} − b − 1}{1 + b + b^{2}}.  (37)

The gradient-difference values are

D_{1} = \frac{3(1 − q^{2})}{1 + q + q^{2}} , D_{2} = −\frac{3(1 − q)}{1 + q + q^{2}} , D_{3} = −\frac{3q(1 − q)}{1 + q + q^{2}} .  (38)

Thus the limiting Adan numerators are

U_{i} := M_{i} + qD_{i},  ∀ i ∈ {1, 2, 3}.  (39)

From (37), (38) and q ≥ 0, they satisfy

U_{1} > 0,  U_{2} < 0,  U_{3} < 0,  U_{1} + U_{2} + U_{3} = 0.

Write

A := −U_{2} > 0, B := −U_{3} > 0,

so that U_{1} = A + B. Set

s_{1} := (2 + 3q)^{2},  s_{2} := (1 + 3q)^{2},  s_{3} := 1.

Then

N_{1} = \frac{s_{1} + r^{2}s_{2} + rs_{3}}{1 + r + r^{2}} ,  N_{2} = \frac{rs_{1} + s_{2} + r^{2}s_{3}}{1 + r + r^{2}} ,  N_{3} = \frac{r^{2}s_{1} + rs_{2} + s_{3}}{1 + r + r^{2}} .

Define

w_{i} := \frac{1}{\sqrt{N_{i}} + ε},  ∀ i ∈ \{1, 2, 3\}.  (40)

The limiting drift of three Adan iterations at a = 2 is

S_{Adan}(2) = ∑_{i=1}^{3} U_{i}w_{i} = A(w_{1} − w_{2}) + B(w_{1} − w_{3}).  (41)

We always have N_{1} > N_{3} since N_{1} − N_{3} = (1 − r)[(s_{1} − s_{3}) + r(s_{1} − s_{2})]/(1 + r + r^{2}) > 0. If N_{1} ≥ N_{2}, then w_{1} ≤ w_{2} and w_{1} < w_{3}, so S_{Adan}(2) < 0.

It remains to consider the case N_{2} > N_{1} > N_{3}. (In the case q = 0, we have s_{1} = 4, s_{2} = 1, and N_{1} − N_{2} = 3(1 − r)/(1 + r + r^{2}) > 0, i.e. this case cannot occur when q = 0, so we may assume q > 0.) The function ϕ: [0, ∞) → ℝ defined by

ϕ(x) = \frac{1}{\sqrt{x} + ε}, ∀ x ≥ 0

has −ϕ′(x) positive and decreasing. Hence using N_{2} > N_{1} > N_{3}

\frac{w_{3} − w_{1}}{w_{1} − w_{2}} =^{(40)} \frac{∫_{N_{3}}^{N_{1}} −ϕ′(x)dx}{∫_{N_{1}}^{N_{2}} −ϕ′(x)dx} ≥ \frac{N_{1} − N_{3}}{N_{2} − N_{1}} .  (42)

A direct calculation gives

\frac{N_{1} − N_{3}}{N_{2} − N_{1}} > \frac{1}{q}.  (43)

Indeed, after canceling the common (1 + r + r^{2})/(1 − r) factor, this is equivalent to

q((1 + r)s_{1} − rs_{2} − s_{3}) > (1 + r)s_{2} − s_{1} − rs_{3},

and the left side minus the right side is equal to

3(3q^{3} + 4q^{2} + 3q + 1 − r(q^{2} + q)) > 0.

On the other hand,

\frac{A}{B} ≤ \frac{1}{q}.

This follows since, using b, q ∈ [0, 1) and q ≠ 0

\frac{−M_{2}}{−M_{3}} =^{(37)} \frac{1 − b}{1 + 2b} ≤ 1 < \frac{1}{q},  (44)

while

\frac{−qD_{2}}{−qD_{3}} =^{(38)} \frac{1}{q}.  (45)

Therefore

\frac{A}{B} = \frac{U_{2}}{U_{3}} =^{(39)} \frac{−M_{2} − qD_{2}}{−M_{3} − qD_{3}} ≤^{(44)∧(45)} \frac{1}{q} <^{(42)∧(43)} \frac{w_{3} − w_{1}}{w_{1} − w_{2}} .

Rearranging this inequality gives

A(w_{1} − w_{2}) − B(w_{3} − w_{1}) < 0,

so by (41) we get (in all cases) that

S_{Adan}(2) < 0.

By continuity, there exists δ > 0 such that, with a = 2 + δ, the limiting Adan period sum ∑_{i=1}^{3} U_{i}(a)w_{i}(a) remains negative and the numerator signs remain

U_{1}(a) > 0,  U_{2}(a) < 0,  U_{3}(a) < 0.

The projection and regret argument from Theorem 5.1 then applies verbatim. □

9. AdaMax

We define the AdaMax optimization method and extend Theorem 1.5 to it. The AdaMax optimization method is defined by the following recursions:

m_{t} := bm_{t−1} + (1 − b)g_{t}, v_{t} := max(qv_{t−1}, |g_{t}|), h_{t} := \frac{m_{t}}{v_{t}+ε}, x_{t+1} as in (3), for all t ≥ 1. As usual, m_{0} = v_{0} = 0.

Theorem 9.1 (AdaMax Counterexample). Let α_{t} > 0 satisfy lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. Fix b, q ∈ [0, 1), ε ≥ 0. Consider projected AdaMax on the domain F = [−1, 1]. Then there exists δ > 0, depending only on b, q, ε, such that for the linear functions (22), the iterates of AdaMax satisfy

lim_{t→∞} x_{t} = 1.

However, the best fixed comparator is x^{∗} = −1, and

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

Proof. The steady-state values (M_{1}, M_{2}, M_{3}) from Lemma 2.1 apply here as well, since the m_{t} recursion for AdaMax is the same as Adam. To find the steady-state (V_{1}, V_{2}, V_{3}) we plug them into their recursion as follows:

V_{2} = max(qV_{1}, 1)
V_{3} = max(qV_{2}, 1) = max(q^{2}V_{1}, 1)

One more iteration gives

max(q^{3}V_{1}, a)

So the fixed point of V ↦ max(q^{3}V, a) must satisfy V = a. (Note that Φ(V) := max(q^{3}V, a) satisfies |Φ(V) − Φ(V′)| ≤ q^{3}|V − V′| for all V, V′ ∈ ℝ and 0 ≤ q < 1 implies that Φ is a contraction, so Φ has a unique fixed point.) The corresponding maps for V_{2}, V_{3} are also contractions. Then solving for V_{2}, V_{3} gives

V_{1}(a) = a, V_{2}(a) = max(qa, 1), V_{3}(a) = max(q^{2}a, 1),  (46)

and when a = 2 we have

V_{1} = 2, V_{2} = max(2q, 1), V_{3} = max(2q^{2}, 1).

Since q < 1 we therefore have

V_{1} > V_{2},  V_{1} > V_{3},  (47)

For any a ≥ 2, define S_{AdaMax}(a) := ∑_{i=1}^{3} \frac{M_{i}(a)}{V_{i}(a)+ε}. We then have

S_{AdaMax}(2) = ∑_{i=1}^{3} \frac{M_{i}(2)}{V_{i}(2) + ε}.

Let A, B > 0 as in (17). Since M_{1}(2) = A + B by (14), we obtain

S_{AdaMax}(2) = \frac{A + B}{V_{1}(2) + ε} − \frac{A}{V_{2}(2) + ε} − \frac{B}{V_{3}(2) + ε}

= A (\frac{1}{V_{1}(2) + ε} − \frac{1}{V_{2}(2) + ε}) + B (\frac{1}{V_{1}(2) + ε} − \frac{1}{V_{3}(2) + ε}) <^{(47)} 0.

This strict negativity holds for every b, q ∈ [0, 1) and every ε ≥ 0. The remaining details follow those of Theorem 5.1, e.g. observing that V_{1}(a), V_{2}(a), V_{3}(a) are continuous functions of a by (46), so S_{AdaMax}(a) < 0 for a near 2, and so on. □

10. Muon

We define the Muon optimization method and extend Theorem 1.5 to it. The Muon optimization method is defined for functions of matrices f_{t}: K → ℝ ∀ t ≥ 1 where K ⊂ ℝ^{n×n}. The iterations satisfy

m_{t} = bm_{t−1} + (1 − b)∇f_{t}(x_{t}),  x_{t+1} = Π_{K} (x_{t} − α_{t} Polar(m_{t})) ,  ∀ t ≥ 1,

with m_{0} = 0, and Π_{K} denoting the projection to the nearest point in K, with respect to the Euclidean (Frobenius) metric on ℝ^{n×n}. Here m_{t}, x_{t} ∈ ℝ^{n×n} for all t ≥ 1 and

Polar(A) := A(A^{∗}A)^{−1/2}

is defined for any invertible n × n matrix A [PKC+26]. More generally, Polar(A) := UV when A is an n × n matrix with reduced singular value decomposition A = UDV (noting that the product UV is well-defined even though U, V are not uniquely determined by A). Also Polar(0) := 0. In practice, Polar(A) can be approximated by Newton-Schulz iterations.

In the case n = 1 with K := [−1, 1] ⊂ ℝ, Muon becomes a signed momentum method:

m_{t} = bm_{t−1} + (1 − b)f′_{t}(x_{t}),  x_{t+1} = Π_{[−1,1]} (x_{t} − α_{t}sign(m_{t})) ,  ∀ t ≥ 1,

(Here sign(0) := 0.) We will demonstrate this method has nonzero average regret. The n = 1 example can then be extended to the n > 1 case by choosing each f_{t} to be a function of one diagonal entry of its input matrix, e.g. K = {diag(x, 0, …, 0): x ∈ [−1, 1]}.

Theorem 10.1 (Muon Counterexample). Let α_{t} > 0 satisfy lim_{t→∞} α_{t} = 0, lim_{t→∞} \frac{α_{t+1}}{α_{t}} = 1 and ∑_{t=1}^{∞} α_{t} = ∞. Fix b ∈ [0, 1). Consider Muon on the domain F = [−1, 1]. Then there exists δ > 0, depending only on b, such that for the linear functions (22), the iterates of Muon satisfy

lim_{t→∞} x_{t} = 1.

However, the best fixed comparator is x^{∗} = −1, and

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

Proof. By Lemma 2.1, the steady-state momentum values are

M_{1}(a) = \frac{a − b − b^{2}}{1 + b + b^{2}} ,  M_{2}(a) = \frac{ab − b^{2} − 1}{1 + b + b^{2}},  M_{3}(a) = \frac{ab^{2} − b − 1}{1 + b + b^{2}}.

At a = 2,

M_{1}(2) > 0, M_{2}(2) < 0, M_{3}(2) < 0.

Therefore, by continuity, there exists δ > 0 such that, with a = 2 + δ,

M_{1}(a) > 0,  M_{2}(a) < 0,  M_{3}(a) < 0.

By Lemma 2.1, (m_{3k+1}, m_{3k+2}, m_{3k+3}) converges exponentially to this period-three steadystate as k → ∞. Hence, there is some k_{0} > 0 such that, for all k > k_{0},

sign(m_{3k+1}) = +1,  sign(m_{3k+2}) = −1,  sign(m_{3k+3}) = −1.

Thus the three unprojected scalar increments in the kth period are

u_{k,1} = −α_{3k+1},  u_{k,2} = α_{3k+2},  u_{k,3} = α_{3k+3}.

Since lim_{t→∞} α_{t+1}/α_{t} = 1, their sum satisfies

U_{k} := −α_{3k+1} + α_{3k+2} + α_{3k+3} = α_{3k+1}(1 + o(1)).

Denote z_{k} := x_{3k+1}. Lemma 4.1 as used for Adam then gives

z_{k+1} ≥ min(1, z_{k} + α_{3k+1}/2), ∀ k ≥ k_{0}.

Since z_{k} ≤ 1 for all k ≥ 1 and ∑_{k≥k_{0}} α_{k} = ∞, we have ∑_{k≥k_{0}} α_{3k+1} = ∞, which follows since lim_{k→∞} α_{k+1}/α_{k} = 1. So, the sequence (z_{k}) reaches 1 at some finite value of k. The within-period moves have size O(α_{3k}) = o(1) by assumption, so x_{t} → 1 as t → ∞.

Finally, every period has cumulative gradient

(2 + δ) − 1 − 1 = δ > 0.

Hence the best fixed comparator in [−1, 1] is −1. Since lim_{t→∞} x_{t} = 1, the same scalar regret computation as for Adam gives

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} .

□

Appendix A. Adam with i.i.d. Slopes

We now give a stochastic version of the Adam counterexample from Theorem 1.5. For simplicity, we only consider the step size α_{t} := α/\sqrt{t} for all t ≥ 1. Instead of presenting the gradients in the deterministic period-three order a, −1, −1, we draw them independently at each time t. The slope a appears with probability 1/3, and the slope −1 appears with probability 2/3.

More formally, let (X_{t})_{t≥1} be i.i.d. Bernoulli random variables with

ℙ(X_{t} = 1) = \frac{1}{3},  ℙ(X_{t} = 0) = \frac{2}{3},  ∀ t ≥ 1.

For any a > 0, define

g_{t}(a) := −1 + (a + 1)X_{t}, ∀ t ≥ 1.

Thus, for any t ≥ 1,

g_{t}(a) = a with probability 1/3, g_{t}(a) = −1 with probability 2/3.

The optimized functions are again

f_{t}(x) = g_{t}(a)x, ∀ x ∈ [−1, 1], t ≥ 1.

Theorem A.1 (Adam i.i.d. random-slope counterexample). Fix b, q ∈ [0, 1), ε ≥ 0, and α > 0. There exists δ > 0, depending only on b, q, ε, such that, with

a = 2 + δ,

projected Adam on [−1, 1], driven by the i.i.d. slopes

g_{t}(a) = \begin{cases}a, & with probability 1/3, \\ −1, & with probability 2/3, \end{cases}

satisfies

lim_{t→∞} x_{t} = 1 almost surely.

Moreover, the best fixed comparator is eventually −1, and the average regret satisfies

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} almost surely.

Proof. We first analyze the balanced value a = 2. It is convenient to work with a two-sided i.i.d. extension (X_{t})_{t∈ℤ}. For λ ∈ [0, 1), define the stationary weighted average

A_{λ,t} := (1 − λ) ∑_{ℓ=0}^{∞} λ^{ℓ}X_{t−ℓ}.  (48)

Then 𝔼[A_{λ,t}] = \frac{1}{3}. For a = 2, we have, for all t ∈ ℤ

g_{t}(2) = −1 + 3X_{t}, g_{t}(2)^{2} = 1 + 3X_{t}.

The stationary versions of the first and second Adam moments are therefore

m_{t}^{∗}(2) = (1 − b) ∑_{ℓ=0}^{∞} b^{ℓ}g_{t−ℓ}(2) = −1 + 3A_{b,t}, v_{t}^{∗}(2) = (1 − q) ∑_{ℓ=0}^{∞} q^{ℓ}g_{t−ℓ}(2)^{2} = 1 + 3A_{q,t}.

Define the stationary normalized Adam direction

h_{t}^{∗}(2) := \frac{m_{t}^{∗}(2)}{\sqrt{v_{t}^{∗}(2)} + ε} = \frac{−1 + 3A_{b,t}}{\sqrt{1 + 3A_{q,t}} + ε}.

Step 1. Proving a positive drift. In the proof of Theorem 5.1, we used (12) to show that S(2) < 0 and S(a) < 0 for a near 2. In the current proof, the analogous statement is that h_{t}^{∗}(2) has negative mean. That is, we claim that the following expression does not depend on t ∈ ℤ and

μ(2) := 𝔼[h_{t}^{∗}(2)] < 0.  (49)

Let ϕ(y) := \frac{1}{\sqrt{1+3y}+ε}, ∀ y ≥ 0. Then ϕ is strictly decreasing on [0, 1]. Since 𝔼[A_{λ,t}] = 1/3,

μ(2) = 𝔼 [(−1 + 3A_{b,t})ϕ(A_{q,t})] = 3 Cov(A_{b,t}, ϕ(A_{q,t})) .

The random variable A_{b,t} is an increasing function of the coordinates (X_{t}, X_{t−1}, X_{t−2}, …). The random variable A_{q,t} is also an increasing function of these same coordinates, and therefore ϕ(A_{q,t}) is a decreasing function of them. By the Harris correlation inequality for product measures,

Cov(A_{b,t}, ϕ(A_{q,t})) ≤ 0.

The inequality is in fact strict. For any t ≥ 1 define the σ-algebra

G_{t} := σ(X_{t−1}, X_{t−2}, …)

and define B_{t}, Q_{t} so that

A_{b,t} = B_{t} + (1 − b)X_{t}, A_{q,t} = Q_{t} + (1 − q)X_{t},

and such that B_{t} and Q_{t} are G_{t}-measurable. Set p := ℙ(X_{t} = 1) = 1/3. Conditional on G_{t},

𝔼[A_{b,t} | G_{t}] = B_{t} + p(1 − b), 𝔼[ϕ(A_{q,t}) | G_{t}] = (1 − p)ϕ(Q_{t}) + pϕ(Q_{t} + 1 − q),
Cov(A_{b,t}, ϕ(A_{q,t}) | G_{t}) = p(1 − p)(1 − b)[ϕ(Q_{t} + 1 − q) − ϕ(Q_{t})] < 0,

since b, q < 1 and ϕ is strictly decreasing. Moreover, 𝔼[A_{b,t} | G_{t}] is an increasing function of the coordinates (X_{t−1}, X_{t−2}, …), whereas 𝔼[ϕ(A_{q,t}) | G_{t}] is a decreasing function of those coordinates. The Harris correlation inequality, now applied to the product measure of the past coordinates, therefore gives

Cov(𝔼[A_{b,t} | G_{t}], 𝔼[ϕ(A_{q,t}) | G_{t}]) ≤ 0.

The law of total covariance consequently yields Cov(A_{b,t}, ϕ(A_{q,t})) < 0. Thus

μ(2) = 3 Cov(A_{b,t}, ϕ(A_{q,t})) < 0.

Now consider general a near 2. Since for all t ∈ ℤ

g_{t}(a) = −1 + (a + 1)X_{t}, g_{t}(a)^{2} = 1 + (a^{2} − 1)X_{t},

the stationary moments are

m_{t}^{∗}(a) = −1 + (a + 1)A_{b,t},  v_{t}^{∗}(a) = 1 + (a^{2} − 1)A_{q,t}.  (50)

Define

h_{t}^{∗}(a) := \frac{m_{t}^{∗}(a)}{\sqrt{v_{t}^{∗}(a)} + ε}, μ(a) := 𝔼[h_{t}^{∗}(a)].

The denominator is bounded away from zero and the integrand is bounded and continuous in a in a neighborhood of 2. Hence, by dominated convergence, a ↦ μ(a) is continuous. Since μ(2) < 0, there exists δ > 0 such that, with a = 2 + δ, we still have

μ(a) < 0.  (51)

Decreasing δ if necessary, assume also δ ≤ 1.

Set γ := −μ(a) > 0. Thus the stationary Adam direction has negative mean: 𝔼[h_{t}^{∗}(a)] = −γ. Equivalently, the mean update direction −h_{t}^{∗}(a) is positive.

We next transfer this stationary drift to the actual Adam process initialized at m_{0} = v_{0} = 0. The actual moments m_{t} satisfy

m_{t} = (1 − b) ∑_{ℓ=0}^{t−1} b^{ℓ}g_{t−ℓ}(a), ∀ t ≥ 1,

while the stationary version is

m_{t}^{∗}(a) = (1 − b) ∑_{ℓ=0}^{∞} b^{ℓ}g_{t−ℓ}(a), ∀ t ∈ ℤ.

Since the gradients g_{t} satisfy |g_{t}| ≤ 3 for all t,

|m_{t} − m_{t}^{∗}(a)| ≤ 3b^{t}, |v_{t} − v_{t}^{∗}(a)| ≤ 9q^{t}.

Also v_{t}^{∗}(a) ≥ 1 for all t ∈ ℤ and, for the actual process,

v_{t} =^{(2)} qv_{t−1} + (1 − q)g_{t}^{2} ≥^{(2)} 1 − q > 0, ∀ t ≥ 1.

Therefore h_{t} := \frac{m_{t}}{\sqrt{v_{t}}+ε} satisfies

|h_{t} − h_{t}^{∗}(a)| ≤ Cρ^{t},  ∀ t ≥ 1,  (52)

for some C < ∞ and ρ ∈ (0, 1).

Step 2. We now prove the following tail excursion estimate. This technical Lemma has no determinstic analogue, i.e. it was not needed in the proof of Theorem 5.1.

Lemma A.2 (Weighted positive-drift estimate). Let (X_{t})_{t∈ℤ} be i.i.d. random variables, and let (Z_{t})_{t∈ℤ} be a bounded stationary Bernoulli shift of the form

Z_{t} := F (X_{t}, X_{t−1}, X_{t−2}, …), ∀ t ∈ ℤ,

where F is real-valued. Assume that there are constants C_{0} < ∞ and ρ ∈ (0, 1) such that, for every ℓ ≥ 0, changing only the coordinate X_{t−ℓ} can change Z_{t} by at most C_{0}ρ^{ℓ}. Suppose

z̄:= 𝔼Z_{t} > 0.  (53)

Let α > 0. Let α_{t} := α/\sqrt{t} for all t ≥ 1. Then as T → ∞,

∑_{t=1}^{T} α_{t}Z_{t} → +∞ almost surely,

and the uniform tail adverse excursion satisfies: as n → ∞,

Δ_{n} := sup_{n≤r≤s<∞} max ( − ∑_{t=r}^{s} α_{t}Z_{t}, 0) ⟶ 0  almost surely.  (54)

Proof. The weighted strong law follows from the ergodic theorem by Abel summation. Let

S_{n} := ∑_{t=1}^{n} Z_{t}, c_{n} := \frac{S_{n}}{n} .

By the ergodic theorem, c_{n} → z̄ almost surely as n → ∞. Write w_{t} = t^{−1/2} for all t ≥ 1 and W_{T} = ∑_{t=1}^{T} w_{t} for all T ≥ 1. Summation by parts gives

∑_{t=1}^{T} w_{t}Z_{t} = w_{T} S_{T} + ∑_{t=1}^{T −1}(w_{t} − w_{t+1})S_{t}.

Since S_{t} = tc_{t},

\frac{∑_{t=1}^{T} w_{t}Z_{t}}{W_{T}} = \frac{T w_{T}}{W_{T}} c_{T} + ∑_{t=1}^{T −1} \frac{t(w_{t} − w_{t+1})}{W_{T}}c_{t}.

The coefficients on the right are nonnegative and sum to one since

T w_{T} + ∑_{t=1}^{T −1} t(w_{t} − w_{t+1}) = ∑_{t=1}^{T} w_{t} = W_{T} .

So, the Toeplitz lemma implies that, as T → ∞,

\frac{∑_{t=1}^{T} w_{t}Z_{t}}{∑_{t=1}^{T} w_{t}} → z̄ almost surely.  (55)

Since ∑_{t=1}^{T} α_{t} ∼ 2α\sqrt{T}, this implies as T → ∞

∑_{t=1}^{T} α_{t}Z_{t} → +∞ almost surely.  (56)

It remains to prove (54). Fix η > 0, and for N ≥ 1 let

I_{N} := {N, N + 1, …, 2N − 1}.

For an interval [r, s] ⊆ I_{N}, set

m := s − r + 1,  Y_{r,s} := ∑_{t=r}^{s} α_{t}Z_{t}.  (57)

We will apply McDiarmid’s inequality to Y_{r,s}, regarded as a function of the independent coordinates (X_{j})_{j≤s}. By assumption, changing only X_{j} can change Y_{r,s} by at most

d_{j} := C_{0} ∑_{t=max{r,j}}^{s} α_{t}ρ^{t−j}, j ≤ s,

where an empty sum is interpreted as zero. Since α_{t} ≤ α/\sqrt{N} for t ∈ I_{N}, we have

d_{j} ≤ \frac{C_{0}α}{(1 − ρ)\sqrt{N}} , ∀ r ≤ j ≤ s,

d_{j} ≤ \frac{C_{0}α}{(1 − ρ)\sqrt{N}} ρ^{r−j}, ∀ j < r.

It follows that

∑_{j=−∞}^{s} d_{j}^{2} ≤ \frac{C_{1}(m + 1)}{N}

for a constant C_{1} < ∞ depending only on C_{0}, ρ, α.

McDiarmid’s inequality therefore gives

ℙ(Y_{r,s} − 𝔼Y_{r,s} ≤ −u) ≤ exp (−\frac{2u^{2}}{∑_{j=−∞}^{s} d_{j}^{2}} ) , ∀ u > 0.

One may justify its use for the countable family (X_{j})_{j≤s} by first fixing all coordinates before a finite time, applying the finite-dimensional inequality, and then sending that time to −∞. The assumed summable coordinate sensitivities make the corresponding approximation uniform. Since t ≤ 2N on I_{N} and [r, s] ⊆ I_{N},

𝔼Y_{r,s} =^{(57)∧(53)} \overline{z} ∑_{t=r}^{s} α_{t} ≥^{(57)} \frac{α\overline{z}}{\sqrt{2N}} m =: c_{0} \frac{m}{\sqrt{N}} >^{(53)} 0.

Consequently, using −η := −u + 𝔼Y_{r,s}, for N sufficiently large,

ℙ(Y_{r,s} ≤ −η) ≤ exp ( − c_{1}N(η + c_{0}m/\sqrt{N})^{2}/(m + 1)) ≤ exp(−c_{η}\sqrt{N}).

For the last inequality, use that η > 0 for N sufficiently large by definition of η,

(η + c_{0}m/\sqrt{N})^{2} ≥ 2ηc_{0}m/\sqrt{N},

and m/(m + 1) ≥ 1/2 by (57). Taking a union bound over the at most N^{2} intervals with integer endpoints in I_{N} gives, for all N sufficiently large

ℙ(∃ r, s ∈ I_{N}, r ≤ s: ∑_{t=r}^{s} α_{t}Z_{t} ≤ −η) ≤ N^{2} exp(−c_{η}\sqrt{N}).

This bound is summable along the dyadic sequence N = 2^{j}. Therefore, by the Borel–Cantelli lemma, almost surely there exists j_{0}(η) such that, for every j ≥ j_{0}(η), every subinterval of the dyadic block

B_{j} := {2^{j}, …, 2^{j+1} − 1}

has weighted sum greater than −η.

We also claim that every sufficiently late dyadic block has positive weighted sum. Define

A_{T} := ∑_{t=1}^{T} α_{t}Z_{t}.

The weighted strong law (55) proven above gives

A_{T} = \overline{z} ∑_{t=1}^{T} α_{t} + o(\sqrt{T}) almost surely.

Hence

A_{2^{j+1}−1} − A_{2^{j}−1} = ∑_{t=2^{j}}^{2^{j+1}−1} α_{t}Z_{t} = \overline{z} ∑_{t=2^{j}}^{2^{j+1}−1} α_{t} + o(2^{j/2}) > 0

for all sufficiently large j, since ∑_{t=2^{j}}^{2^{j+1}−1} α_{t} ≍ 2^{j/2}.

Now consider an interval [r, s] lying sufficiently far in the tail. If it is contained in one dyadic block, its weighted sum is greater than −η. Otherwise, decompose it into a terminal piece of its first dyadic block, a collection of complete dyadic blocks, and an initial piece of its final dyadic block. The complete dyadic blocks have nonnegative sum, and each of the two boundary pieces has sum greater than −η (almost surely, for sufficiently large j). Thus

∑_{t=r}^{s} α_{t}Z_{t} > −2η

for every sufficiently late interval [r, s].

Finally, apply the preceding argument simultaneously to the countable sequence η = 1/k, k ≥ 1. On the resulting probability-one event, for every k we have

Δ_{n} ≤ \frac{2}{k}

for all sufficiently large n. Therefore as n → ∞,

Δ_{n} ⟶ 0 almost surely.

□

Step 3. Applying Lemma A.2. Returning to the proof of Theorem A.1, we will apply Lemma A.2, so we verify its coordinate-sensitivity assumption. Let

Z_{t}^{∗} := −h_{t}^{∗}(a) = −\frac{m_{t}^{∗}(a)}{\sqrt{v_{t}^{∗}(a)} + ε}.  (58)

From (50) and (48), changing only X_{t−ℓ} changes the stationary moment m_{t}^{∗}(a) by at most

|Δm_{t}^{∗}(a)| = (a + 1)(1 − b)b^{ℓ}

and similarly v_{t}^{∗}(a) changes by at most

|Δv_{t}^{∗}(a)| = (a^{2} − 1)(1 − q)q^{ℓ}.

On the region \{(m, v) ∈ ℝ^{2} : |m| ≤ a, 1 ≤ v ≤ a^{2}\}, the function F (m, v) := −\frac{m}{\sqrt{v}+ε} satisfies

|\frac{∂F}{∂m}| ≤ 1,  |\frac{∂F}{∂v} | = \frac{|m|}{2\sqrt{v}(\sqrt{v} + ε)^{2}} ≤ \frac{a}{2}.

It then follows from (58) that the change in Z_{t}^{∗} from changing X_{t−ℓ} is at most

|ΔZ_{t}^{∗}| ≤ (a + 1)(1 − b)b^{ℓ} + \frac{a}{2}(a^{2} − 1)(1 − q)q^{ℓ}.

Choose any ρ_{0} ∈ (max(b, q), 1). Then there is a constant C_{0} < ∞ such that

|ΔZ_{t}^{∗}| ≤ C_{0}ρ_{0}^{ℓ}, ℓ ≥ 0.

Moreover, Z_{t}^{∗} is bounded, since for all 2 ≤ a ≤ 3

|m_{t}^{∗}(a)| ≤ a, v_{t}^{∗}(a) ≥ 1.

Thus Z_{t}^{∗} satisfies all the hypotheses of Lemma A.2.

We apply Lemma A.2 first to the stationary process Z_{t}^{∗} from (58). It has positive mean by (51). The actual process Z_{t} := −h_{t} differs from Z_{t}^{∗} by an exponentially decaying error by (52): |Z_{t} − Z_{t}^{∗}| ≤ Cρ^{t}. Consequently,

∑_{t=1}^{∞} α_{t}|Z_{t} − Z_{t}^{∗}| < ∞,  lim_{n→∞} sup_{n≤r≤s<∞} ∑_{t=r}^{s} α_{t}|Z_{t} − Z_{t}^{∗}| = 0.

Thus the two conclusions of Lemma A.2 also hold for Z_{t} = −h_{t}.

Step 4. Proving lim_{t→∞} x_{t} = 1. We now prove that lim_{t→∞} x_{t} = 1. The update is

x_{t+1} = Π_{[−1,1]}(x_{t} + α_{t}Z_{t}), ∀ t ≥ 1.

Suppose there exists m such that x_{t} < 1 for all t > m. Then for any n > m we have

1 > x_{n+1} ≥ x_{m} + ∑_{t=m}^{n} α_{t}Z_{t},

since projection on [−1, 1] can only increase x_{t} < 1 when t > m. But this contradicts (56). We therefore conclude that x_{t} = 1 for infinitely many times t.

Fix n, and let τ ≥ n be a time such that x_{τ} = 1. For all m ≥ τ, let

r_{m} := max{r ∈ [τ, m]: x_{r} = 1}.

If r_{m} = m, then 1 − x_{m} = 0. Otherwise, none of the iterates

x_{r_{m}+1}, …, x_{m}

equals 1. Hence projection to 1 does not occur for the indices from r_{m} through m − 1. Projection to −1 can only increase the iterate, so an induction gives

x_{m} ≥ 1 + ∑_{t=r_{m}}^{m−1} α_{t}Z_{t}.

Since x_{m} ≤ 1, we have − ∑_{t=r_{m}}^{m−1} α_{t}Z_{t} ≥ 0, so for all m ≥ τ ≥ n,

1 − x_{m} ≤ − ∑_{t=r_{m}}^{m−1} α_{t}Z_{t} = max ( − ∑_{t=r_{m}}^{m−1} α_{t}Z_{t}, 0) ≤^{(54)} Δ_{n}.

Since Δ_{n} → 0 almost surely by (54), for any η > 0 we may first choose n so large that Δ_{n} < η, and then choose a hitting time τ ≥ n. The preceding bound gives

0 ≤ 1 − x_{m} < η, ∀ m ≥ τ.

Therefore

lim_{t→∞} x_{t} = 1 almost surely.

Step 5. Regret bound. It remains to compute regret. By the strong law of large numbers and since a = 2 + δ,

lim_{T →∞} \frac{1}{T} ∑_{t=1}^{T} g_{t}(a) = 𝔼[g_{t}(a)] = \frac{a}{3} − \frac{2}{3} = \frac{δ}{3} almost surely.

Let G_{T} := ∑_{t=1}^{T} g_{t}(a). Then G_{T} /T → δ/3 > 0, and hence G_{T} > 0 for all sufficiently large T, almost surely. Therefore the best fixed comparator is eventually x_{T}^{∗} = −1, and for all sufficiently large T, R_{T} = ∑_{t=1}^{T} g_{t}(a)x_{t} + G_{T} . Equivalently,

R_{T} = 2G_{T} + ∑_{t=1}^{T} g_{t}(a)(x_{t} − 1).

Since x_{t} → 1 almost surely and the gradients g_{t} are uniformly bounded,

lim_{T →∞} \frac{1}{T} ∑_{t=1}^{T} g_{t}(a)(x_{t} − 1) = 0 almost surely.

Combining this with lim_{T →∞} G_{T} /T = δ/3, we obtain

lim_{T →∞} \frac{R_{T}}{T} = \frac{2δ}{3} almost surely.
□

Acknowledgement. ChatGPT 5.5 assisted in the preparation of this manuscript.

References

[AMM+20] Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. A new regret analysis for Adam-type algorithms. International Conference on Machine Learning (2020), 119, pp. 202– 210.

[AZK+24] Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding Adam optimizer via online learning of updates: Adam is FTRL in disguise. International Conference on Machine Learning (2024).

[BG20] André Belotto da Silva and Maxime Gazeau. A general system of differential equations to model first order adaptive algorithms. Journal of Machine Learning Research (2020), 21 (129), pp. 1–42.

[BMR+20] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. Advances in Neural Information Processing Systems (2020) 159, pp. 1877–1901.

[BW19] Sebastian Bock and Martin Georg Weiß. Non-convergence and limit cycles in the Adam optimizer. International Conference on Artificial Neural Networks (2019), vol 11728.

[BZZ+26] Zhiwei Bai, Jiajie Zhao, Zhangchen Zhou, Zhi-Qin John Xu, and Yaoyu Zhang. Towards understanding Adam convergence on highly degenerate polynomials. International Conference on Machine Learning (2026), to appear.

[D24] DeepSeek-AI. DeepSeek-V3 Technical Report. (2024), Preprint, arXiv:2412.19437.

[DCK+19] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. North American Chapter of the Association for Computational Linguistics (2019), pp. 4171–4186.

[DDJ+25] Steffen Dereich, Thang Do, Arnulf Jentzen, and Philippe von Wurstemberger. Adam symmetry theorem: characterization of the convergence of the stochastic Adam optimizer. (2025), Preprint, arXiv:2511.06675.

[DGJ24] Steffen Dereich, Robin Graeber, and Arnulf Jentzen. Non-convergence of Adam and other adaptive stochastic gradient descent optimization methods for non-vanishing learning rates. (2024), Preprint, arXiv:2407.08100.

[DHJ24] Thang Do, Sonja Hannibal, and Arnulf Jentzen. Non-convergence to global minimizers in data driven supervised deep learning: Adam and stochastic gradient descent optimization provably fail to converge to global minimizers in the training of deep neural networks with ReLU activation. Journal of Mathematical Analysis and Applications (2026), 130724.

[DJR25] Thang Do, Arnulf Jentzen, and Adrian Riekert. Non-convergence to the optimal risk for Adam and stochastic gradient descent optimization in the training of deep neural networks. (2025), Preprint, arXiv:2503.01660.

[HWD19] Haiwen Huang, Chang Wang, and Bin Dong. Nostalgic Adam: Weighting More of the Past Gradients When Designing the Adaptive Learning Rate. International Joint Conference on Artificial Intelligence (2019), pp. 2556–2562.

[JR25] Arnulf Jentzen and Adrian Riekert. Non-convergence to global minimizers for Adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks. SIAM/ASA Journal on Uncertainty Quantification (2025), 13 (3), pp. 1294–1333.

[KB15] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (2015). (Poster)

[LH19] Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. International Conference on Learning Representations (2019) (Poster).

[LXL+19] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations (2019).

[PKC+26] Tetiana Parshakova, Ahmed Khaled, Michael Crawshaw, Guillaume Garrigos, and Robert M. Gower. Muon Does Not Converge on Convex Lipschitz Functions. (2026), Preprint, arXiv:2605.08980.

[RKK18] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. International Conference on Learning Representations (2018).

[Toi23] Philippe L. Toint. Divergence of the ADAM algorithm with fixed-stepsize: a (very) simple example. (2023), Preprint, arXiv:2308.00720.

[TMS+23] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open Foundation and Fine-Tuned Chat Models. (2023), Preprint, arXiv:2307.09288.

[WK22] Ruiqi Wang and Diego Klabjan. Divergence results and convergence of a variance reduced version of Adam. (2022), Preprint, arXiv:2210.05607.

[XZL+24] Xingyu Xie, Pan Zhou, Huan Li, Zhouchen Lin, and Shuicheng Yan. Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models. IEEE Transactions on Pattern Analysis and Machine Intelligence (2024), 46 (12), pp. 9508–9520.

[ZCS+22] Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems (2022).

[ZLC+26] Yushun Zhang, Bingran Li, Congliang Chen, Zhi-Quan Luo, and Ruoyu Sun. Adam converges without any modification on update rules. (2026), Preprint, arXiv:2603.02092.

[ZRS+18] Manzil Zaheer, Sashank J. Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in Neural Information Processing Systems (2018).