Constant-Step Adam Does Not Reach Stationarity: An Explicit Noise Floor and a Variance-versus-Standard-Deviation Separation from SGD

This paper proves that constant-step RMSProp (and, empirically, full Adam) never reaches a stationary point on the one-dimensional quadratic f(x)=x^2/2 under bounded i.i.d. noise, gives the matching exact floor for constant-step SGD, and argues the two floors separate because the adaptive step is normalized by the noise's root-mean-square (~s) rather than accumulating its variance (~s^2).

I checked every proof line by line. Lemma 1 (bounded per-step displacement), Lemma 2 (bounded iterates/gradients by induction), Lemma 3 (a guaranteed 'kick' of size >= eta*s/(2(G+eps)) whenever |x_t| falls below s/2) and the resulting Theorem 3 floor eta^2 s^2/(32(G+eps)^2) are all correct; the ping-pong argument (either |x_t| or |x_{t+1}| exceeds r) is a clean, standard device and the algebra checks out at each step, including the eta <= 2(G+eps) sub-claim used to keep r <= s/2. Theorem 4's exact SGD floor eta*s^2/(2-eta) via the AR(1) fixed point is textbook-correct. The rigorous separation in Theorem 5 is real but is stated only in a narrow, conservative corner of parameter space (s^2 < eta/800); the paper is honest that this bound is loose and that the real 1/s separation is only established heuristically (AR(1) linearization) plus numerically for full Adam and a non-convex objective -- an appropriate and clearly flagged limitation rather than an overclaim.

Where the paper is weaker is novelty. The underlying mechanism -- that normalizing by an RMS turns additive noise into a roughly sign/constant-magnitude perturbation, producing a noise floor that scales with the noise's standard deviation rather than its variance -- is the same mechanism behind the known signSGD / normalized-GD noise-floor literature (e.g. Balles & Hennig's 'the sign of the noise', or the general folklore that adaptive methods behave like sign descent near convergence), none of which is cited. What is genuinely new is the sharp, explicit, non-asymptotic constant and the fully rigorous (if narrow) separation regime. That is a real but incremental contribution, not a new mechanism.

Significance is modest: the result lives entirely on a 1D quadratic with two-point noise and beta1=0; the multivariate, ill-conditioned, and full-momentum cases -- the ones that actually matter for practitioners tuning Adam -- are explicitly left open (Limitations ii-iii), and the rigorous regime of Theorem 5 requires noise far smaller relative to eta than typical training regimes. Practitioners already know empirically that Adam's late-training noise floor is worse than well-tuned SGD's (Wilson et al. 2017, cited); this paper explains why with a clean toy model rather than changing what anyone builds.

Clarity is excellent: full pseudocode, explicit constants, and a short, reproducible NumPy simulation whose reported numbers are plausible and internally consistent (the SGD floor tracks eta*s^2/(2-eta) to two significant figures, and the RMSProp/Adam floors fall far more slowly as s shrinks, as the theory predicts).

The paper presents a crisp theoretical analysis of constant-step Adam/RMSProp on a simple one-dimensional quadratic with bounded noise. The main result is that, unlike decaying-step schedules, a fixed step size prevents convergence to stationarity, yielding a strictly positive lower bound on the time-averaged squared gradient. The proof is elementary yet effective, leveraging a bound on the normalized step size and a "kick" near the optimum. In contrast, the exact floor for SGD scales with noise variance, leading to a separation that diverges as noise decreases. The mechanism—that adaptive preconditioning normalizes by the noise standard deviation—is clearly explained and illustrated with a reproducible simulation.

Strengths: The paper is well-motivated and fills a gap by isolating constant step size as a sufficient cause of non-convergence, independent of non-convexity or adversarial gradients. The explicit constants and the variance-vs-standard-deviation scaling provide a novel quantitative insight. The mathematical development is clean, with lemmas and theorems precisely stated and proved. The authors are transparent about limitations, and the simulation effectively supports the theory.

Weaknesses: The analysis is confined to a 1D quadratic with Rademacher noise, which, while illustrative, limits immediate practical applicability. Extensions to higher dimensions, general noise, or non-quadratic losses would strengthen the message. The rigorous separation (Theorem 5) holds only in a restricted parameter regime, and a tight bound for RMSProp over a broader range is missing. The theoretical treatment of full Adam (with momentum) remains open. Additionally, the practical significance may be tempered by the simplicity of the setting, though the paper's contribution is primarily theoretical.

Questions for the authors: (1) Can you extend the analysis to multi-dimensional quadratics with diagonal preconditioning? How would the separation depend on the condition number? (2) The AR(1) linearization suggests a floor of approximately eta*s/2 for RMSProp. Is it possible to prove a matching upper bound under mild assumptions? (3) How does the inclusion of beta1 affect the lower bound? Numerical experiments suggest a similar floor; can you prove it? (4) The paper assumes eps <= s. In practice, eps is often a small constant (e.g., 1e-8) while s may be much smaller; does the floor significantly degrade in that case?

Overall, the paper is a well-crafted theoretical contribution that offers a clear and insightful explanation of a known empirical phenomenon. I recommend acceptance.

This paper tackles the timely question of why constant-step Adam, as commonly used in practice, fails to converge to a stationary point even on simple problems. The authors elegantly show that for a one-dimensional strongly convex quadratic with bounded symmetric noise, constant-step RMSProp (β1=0) has a strictly positive lower bound on the time-averaged expected squared gradient. This stands in contrast to constant-step SGD, whose exact floor scales with the noise variance and can be arbitrarily small. The key insight is that the adaptive step normalization converts additive noise of scale σ into an effective step of size ~ η, preventing the optimizer from reducing the gradient magnitude below a threshold proportional to ησ. The paper includes a rigorous proof, a separation theorem, and supporting simulations.

Strengths: The exposition is exceptionally clear and well-motivated. The theoretical arguments are kept simple and self-contained, using only elementary probability and induction. The explicit floor for RMSProp and exact floor for SGD are valuable reference results. The comparison vividly demonstrates how the preconditioner's root-mean-square normalization causes the adaptive method's floor to scale with the noise standard deviation rather than the variance. The numerical experiments are reproducible and convincingly show the predicted scaling, including for full Adam and a non-convex example.

Weaknesses: The analysis is limited to a 1D quadratic and Rademacher noise, which, while sufficient to make the point, leaves a gap between theory and the high-dimensional non-convex objectives of deep learning. The rigorous separation theorem (Thm. 5) requires a conservative parameter regime and does not recover the 1/σ scaling except heuristically. The absence of a formal extension to Adam with momentum (β1>0) is a noticeable omission, although the simulations suggest the phenomenon persists. The lower bound for RMSProp is likely loose, and the paper does not explore tightness.

Questions for the authors:

• Could the RMSProp floor be tightened to a two-sided bound that matches the linearized prediction ησ/2 in the small-η regime? What are the main obstacles?
• What would be the expected behavior in the multidimensional case, particularly when the noise covariance and the Hessian are not aligned? The preconditioner might differentially scale the step along different eigendirections, potentially leading to anisotropic stationarity floors.
• Do you see a feasible path to proving a similar bound for full Adam (β1>0) using momentum bounds, and what technical challenges would arise?

Novelty: The explicit constant-step non-convergence result and the variance-vs.-standard-deviation separation are novel and sharpen the existing understanding of adaptive methods' failure modes. While it is known that constant steps can prevent convergence, the precise scaling and the comparison with SGD are not present in prior work.

Rigor: The proofs are sound within the stated model assumptions. The derivation of the boundedness lemmas and the kick lemma are tight; the final lower bound for RMSProp is valid, though not necessarily tight. The SGD floor is exact. The separation theorem, while narrow, is correctly stated.

Clarity: The paper is a pleasure to read. The narrative is well-structured, notation is consistent, and the core ideas are explained intuitively before diving into proofs. Figures and code are not provided in the abstract but the description is clear.

Significance: The result provides a clean theoretical explanation for a commonly observed practical behavior: constant-step Adam can stall at a higher loss than well-tuned SGD. It underscores the necessity of learning-rate decay for exact stationarity. However, the practical impact is moderated by the fact that many deep learning tasks do not require exact stationarity and that the 1D setting is far from real-world use. Nonetheless, it serves as a valuable contribution to the optimization theory literature, clarifying the role of step-size scheduling.

Overall, this is a well-executed piece of work that makes a clear and important point. I recommend minor revision to discuss the potential for tighter bounds, to elaborate more on the multidimensional extension, and to include a more thorough discussion of the momentum case, even if only speculatively. The paper is essentially sound and would be a strong contribution to the conference.

This paper addresses a real and underappreciated gap: Adam's convergence theory is almost universally stated for a vanishing step size, while practitioners run Adam with fixed hyperparameters, and the paper asks what can be said rigorously in that regime. On the simplest possible carrier—f(x)=x^2/2 in one dimension with bounded, unbiased, i.i.d. (Rademacher) gradient noise—the authors prove that constant-step RMSProp (Adam with beta1=0) never reaches a stationary point: the time-averaged expected squared gradient is bounded below by an explicit positive constant for any fixed step size, decay rate beta2, and epsilon. They give the matching exact floor for constant-step SGD, and argue that the two floors scale differently in the noise scale s: SGD's floor is proportional to the noise variance s^2, while RMSProp's floor is proportional to the noise standard deviation s, so that in the low-noise regime SGD strictly outperforms RMSProp, with the gap growing as 1/s.

The technical core is elementary but well executed. Lemma 1 shows the RMSProp step is bounded independently of the gradient magnitude (D = eta/sqrt(1-beta2)); Lemma 2 uses this to derive an almost-sure bound M on the iterates and G on the gradients via an induction; Lemma 3 shows that whenever the iterate is within s/2 of the optimum the next step is forced to be at least kappa = eta*s/(2(G+eps)) in magnitude (because the noise term dominates the true gradient there); and Theorem 3 combines these into a clean pigeonhole argument showing that for every t, at least one of x_t^2, x_{t+1}^2 exceeds r^2 = (kappa/2)^2, yielding a Cesàro-average floor of eta^2 s^2 / (32 (G+eps)^2). This proof is correct as far as I can check, and I appreciate that the authors explicitly disclaim any contradiction with decaying-step positive results by noting the floor is O(eta^2) and vanishes as eta -> 0.

Theorem 4 is a standard exact computation for the AR(1)-type SGD recursion and is unobjectionable. The interesting content is in Section 6, where the authors attempt to make the 'variance vs standard deviation' separation precise. Theorem 5 is a genuinely rigorous statement, but its scope is quite narrow: it requires s^2 < eta/800 together with other constraints tying eta, s, and beta2 together, and the authors themselves flag that 'this rigorous statement is deliberately conservative because the lower bound of Theorem 3 is loose.' The sharper and more compelling claim—that floor_RMSProp ~ eta*s/2 versus floor_SGD ~ eta*s^2/2, giving a genuine 1/s divergence—is derived from an informal AR(1) linearization around the noise-dominated regime, not a theorem, and is only checked against three simulated noise levels (s = 1e-1, 1e-2, 1e-3). This is a significant gap between what is titled/abstracted as the main contribution (a 'provable separation... that diverges as the noise shrinks') and what is actually proven with full rigor. A more careful treatment would either tighten Theorem 3/5 to close this gap, or explicitly demote the sharper scaling to a conjecture supported by simulation, which the current framing somewhat blurs (the abstract states the separation 'we prove' in a way that overstates what Theorem 5 alone delivers).

Scope and generality are the other main concern. All fully rigorous claims are specific to: one dimension, the single quadratic f(x)=x^2/2, symmetric bounded (Rademacher, not just bounded-variance) noise, and beta1=0. The extension to full Adam (beta1=0.9) and to a non-convex objective (log cosh) is entirely numerical, with the authors candidly noting in the limitations that a momentum version of Lemma 1 would require 'messier constants' but is not actually worked out. Given that the paper's title and message are framed as being about 'Adam' broadly, and that real deep learning use cases are high-dimensional, ill-conditioned, and non-i.i.d., the practical reach of the rigorous results is modest; the authors are appropriately explicit about this in Section 9, which I credit, but it does limit the paper's significance as currently written.

On novelty: that constant-step SGD converges only to a noise-dependent neighborhood is classical (as the paper acknowledges), and it is intuitively unsurprising that an algorithm whose step size does not shrink near a stationary point (because it normalizes by an estimate of the noise's RMS) cannot converge to that point exactly. The paper's contribution is to make this intuition rigorous and quantitative for RMSProp, and to identify the variance-vs-std-deviation scaling difference as the source of a provable (if narrowly stated) separation from SGD. This is a nice, clean point, worth publishing, but it is more a careful formalization of an expected phenomenon than a surprising new insight, and the related-work section does not sufficiently engage with existing stochastic-approximation or SDE-based analyses of adaptive methods' stationary behavior under fixed step sizes, which likely contain related or overlapping observations.

Presentation is a clear strength: the paper is well organized, proofs are short and readable, the numerical validation is reproducible with included code, and the limitations section is unusually candid about what is and is not established. I recommend major revision: the authors should either (a) prove a tight, general two-sided floor for RMSProp that directly yields the eta*s scaling claimed informally in Section 6, closing the gap between the 'sharp' scaling and the loose rigorous Theorem 5, or (b) reframe the abstract/claims to more accurately reflect that the eta*s vs eta*s^2 separation is a validated conjecture rather than a proven theorem outside the narrow regime, and (c) extend or at least sketch a rigorous argument for beta1>0, since 'full Adam' is repeatedly invoked as empirically confirming the mechanism. Engaging with existing literature on constant-step adaptive method dynamics would also strengthen the paper's positioning.

This paper presents a crisp theoretical result: constant‑step Adam does not reach a stationary point, even on the simplest 1D quadratic with bounded noise. It proves an explicit positive floor for the time‑averaged squared gradient of RMSProp (β₁=0) and contrasts it with the exact floor for SGD. The key observation is that adaptive normalization turns additive noise into steps of constant magnitude, leading to a stationarity floor that scales with the noise standard deviation, whereas SGD's floor scales with the noise variance. This yields a provable separation in the low‑noise regime.

Strengths:

• The result is clean, intuitively motivated, and mathematically rigorous within the stated model.
• Proofs are elementary and self‑contained, using only basic probability and induction, yet they deliver explicit, interpretable constants.
• The variance‑vs‑standard‑deviation separation is a novel and insightful contribution.
• The writing is clear and well‑structured, with a careful discussion of prior work.
• Reproducible numerical experiments confirm the theoretical scaling and extend the observation to full Adam and a non‑convex objective.

Weaknesses:

• The analysis is limited to a one‑dimensional quadratic, Rademacher noise, and β₁=0. While the authors argue this is the strongest negative case, a proof for β₁>0 and higher dimensions remains missing.
• The rigorous separation bound (Theorem 5) is conservative and requires a small‑η, small‑s regime; a tight characterization for general hyperparameters is open.
• The paper does not discuss potential fixes (e.g., large ε or step decay) to reclaim convergence.
• The lower bound constants are loose, leaving a gap between theory and simulation.

Overall, this is a solid contribution that clearly communicates a fundamental limitation of constant‑step adaptive methods. I recommend minor revision to address the limitations more explicitly and perhaps add a short discussion on how the mechanism might extend to higher dimensions.