Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

On the Convergence of AdaBound and its Connection to SGD

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims AdaBound's published $O(\sqrt T)$ regret guarantee is invalid, and that a bounded-gap assumption restores an $O(\sqrt T)$ rate while dampened momentum SGD matches its CIFAR performance.

desk verdict A genuine correction to AdaBound's published regret proof, with a plausible counterexample and a useful revised guarantee; needs a referee, not a desk reject. read the letter →

arxiv 1908.04457 v2 pith:4TNNKGNR submitted 2019-08-13 cs.LG math.OCstat.ML

Pedro Savarese This is my paper · ORCID
classification cs.LGmath.OCstat.ML
keywords AdaBoundadaptivegradientmethodsregretstochasticconvexoptimizationnon-convergencemomentumSGDAdamCIFAR
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

AdaBound is an adaptive optimizer designed to start like Adam and degenerate to SGD by clipping the per-coordinate learning rate between two time-dependent bounds. This paper seeks to establish that AdaBound's published $O(\sqrt T)$ regret guarantee is invalid: for any horizon $K$, one can choose bound functions that satisfy all the assumptions of the original theorem and a stochastic convex problem on which AdaBound keeps $\mathbb{E}[f(x_t)] - f(x^*) \ge 1$ for every $t \le K$, even though the claimed bound would put average suboptimality below $0.01$. The failure mechanism is that the clipping operation can be the identity for an arbitrarily long initial segment, so AdaBound reproduces the known non-convergence of Adam on a simple one-dimensional problem. The paper repairs the theory with a new $O(\sqrt T)$ regret guarantee under a different assumption on the bound functions, and reports CIFAR experiments in which momentum SGD with dampening equal to its momentum matches AdaBound's accuracy with fewer hyperparameters and lower per-step cost.

What carries the argument

The central object is AdaBound's clipping operation $\mathrm{Clip}(\alpha/\sqrt{v_t}, \eta_l(t), \eta_u(t))$ and the two bound functions that keep each effective learning rate in a shrinking interval. The counterexample works by choosing the bounds so that the clip is the identity for $t \le K$, which erases the only difference between AdaBound and Adam and lets the known Adam divergence take over. The repair mechanism is the bounded-gap inequality $t/\eta_l(t) - (t-1)/\eta_u(t-1) \le M$, which controls how fast the inverse effective learning rate can change from one step to the next and makes the regret telescoping sum well behaved. The paper proves this inequality holds with $M = 3 + 2/\gamma$ for the originally recommended bound functions.

What would settle it

Simulate AdaBound with $\beta_1 = 0$, $\eta_l(t)=\alpha/C$, and $\eta_u(t;K)=\alpha/\sqrt{1-\beta_2}$ for $t \le K$ on the one-dimensional random objective where $f_t(x)=Cx$ with probability $(1+\delta)/(C+1)$ and $f_t(x)=-x$ otherwise, and check whether $\mathbb{E}[x_{t+1}] \ge \mathbb{E}[x_t]$ survives the extra $1/\sqrt{t}$ learning-rate decay; if the expected iterate instead drifts toward zero, the paper's key reduction to Adam fails and the counterexample collapses.

Watch

Extended reading notes

Core claim

On its own terms, the discovery is that the proof of AdaBound's main regret bound (Theorem 4 of the original AdaBound paper) is wrong, and that the statement can be outright false. The proof uses the monotonicity claim $\eta_{t,i}^{-1} \ge \eta_{t-1,i}^{-1}$, which the paper shows would require $\eta_l(t-1)/\eta_u(t) \ge \sqrt{1-1/t}$; even for the recommended functions $\eta_l(t)=1-1/(\gamma t+1)$ and $\eta_u(t)=1+1/(\gamma t)$, no $\gamma>0$ satisfies this. To show that this is more than a gap in a proof, the paper takes the known one-dimensional stochastic convex problem on which Adam fails to converge and chooses $\eta_l(t)=\alpha/C$ and $\eta_u(t;K)=\alpha/\sqrt{1-\beta_2}$ for $t\le K$, so the clipping is the identity and AdaBound produces exactly Adam's iterates for $K$ steps; the known Adam argument then gives $\mathbb{E}[f(x_t)] - f(x^*) \ge 1$ for all $t\le K$. Applying the original regret bound at $T=K$ would force the average suboptimality below $0.01$, so the original theorem cannot hold as stated. The positive replacement assumes $t/\eta_l(t) - (t-1)/\eta_u(t-1) \le M$ and derives an $O(\sqrt T)$ regret bound that does not need monotonic bounds or a common limit; for the recommended bounds $M = 3 + 2/\gamma$.

Load-bearing premise

The counterexample assumes without a separate proof that the known non-convergence argument for Adam still holds after AdaBound's extra $1/\sqrt{t}$ decay is applied to the update, so that erasing the clipping really leaves the same divergent dynamics.

Editorial extensions

If this is right

  • The original $O(\sqrt T)$ regret guarantee for AdaBound must be withdrawn or corrected, because there are admissible bound functions for which the average suboptimality stays above $1$ for arbitrarily many initial steps.
  • Under the new bounded-gap assumption, AdaBound (and the same argument covers AMSBound) regains an $O(\sqrt T)$ regret bound without requiring the bounds to be monotone or to converge to the same limit.
  • For the recommended bound functions, the new regret bound is minimized as $\gamma$ tends to infinity, which is exactly the limit in which AdaBound degenerates to SGD; the paper reads this as theoretical support for simpler SGD-like updates.
  • The CIFAR experiments show that momentum SGD with a dampening factor equal to its momentum matches AdaBound's final test accuracy (about $94.0\%$ vs $93.9\%$) while using fewer per-step operations and only two hyperparameters instead of five.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An immediate extension, not claimed by the paper, is that the same clipping-identity construction should refute the online convex regret claim as well, and should carry over to AMSBound, since the paper shows AMSBound also fails the monotonicity condition.
  • The bounded-gap condition suggests a design criterion for future adaptive optimizers: any clip schedule whose inverse learning-rate gap grows no faster than $M/\sqrt{t}$ preserves the $O(\sqrt T)$ rate, so one could deliberately choose non-monotone or quickly-decaying bounds without losing the guarantee.
  • The dampened-SGDM result can be read as a testable hypothesis that the practical benefit of Adam-style clipping on image tasks comes largely from reweighting the momentum, not from per-coordinate normalization; testing dampened SGDM against Adam on other benchmarks would isolate that effect.
  • Because the counterexample exploits arbitrarily long identity phases of the clip, it also implies that finite-horizon transients, not just asymptotic behavior, must be controlled when certifying clipped adaptive methods.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies AdaBound (Luo et al., 2019), an adaptive gradient method that clips the per-coordinate learning rate with time-dependent bounds. Section 3 claims to identify a flaw in the proof of AdaBound's O(√T) regret bound (Theorem 4 of Luo et al.) and constructs a one-dimensional stochastic convex problem in which, for any K, the upper bounding function can be chosen loose enough that AdaBound's clipping is the identity for the first K iterations; the paper then argues that AdaBound produces the same iterates as Adam and inherits the non-convergence of Reddi et al.'s Theorem 3, yielding E[f(x_t)]−f(x*) ≥ 1 for all t ≤ K. Corollary 1 derives an explicit contradiction with Luo et al.'s Theorem 4. Section 4 proposes a new sufficient condition, t/ηl(t)−(t−1)/ηu(t−1) ≤ M, under which an O(√T) regret bound is proved, and shows that the condition holds for the bound functions used in the original AdaBound paper. Section 5 reports CIFAR experiments comparing AdaBound with a dampened form of momentum SGD.

Significance. If the counterexample is correct, the paper demonstrates that the published AdaBound regret guarantee is invalid, which is a substantive finding for the adaptive-optimizer literature. The paper also contributes a corrected sufficient condition for an O(√T) regret bound, and it makes an explicit empirical connection between AdaBound and a specific form of momentum SGD, with public code and reproducible experiments. The central theoretical claims are, however, burdened by an unverified equivalence with Reddi et al.'s Adam counterexample and by an unstated monotonicity assumption in the new theorem; these issues are load-bearing and prevent the results from being accepted in their current form.

major comments (3)
  1. [Section 3, proof of Theorem 2] The argument that AdaBound 'produces the same iterates as Adam' is the load-bearing step: it transfers the monotonicity E[x_{t+1}] ≥ E[x_t] from Reddi et al.'s Theorem 3 to AdaBound. The manuscript neither states the exact update rule to which Reddi et al.'s theorem applies nor verifies that AdaBound's update x_{t+1} = Π(x_t − α/(√t√v_t)m_t), with the extra 1/√t from η_t = η̂_t/√t and without bias correction, matches that variant. If Reddi et al.'s Adam uses a different step-size normalization or includes bias correction, the inherited monotonicity may fail, and the lower bound E[f(x_t)]−f(x*) ≥ 1, together with Corollary 1's contradiction, collapses. Please quote the exact algorithm used in Reddi et al.'s Theorem 3, or prove the monotonicity directly for AdaBound's exact update; also verify explicitly that the β1=0 case used in Corollary 1 is covered.
  2. [Section 4, Theorem 3, Eq. (15)] The proof of the S1 bound uses the inequality 0 ≤ β1,(t+1) ≤ β1,t < 1 in the second inequality of Eq. (15), but the theorem statement only assumes β1t ≤ β1 for all t. The stated assumptions do not imply that β1t is non-increasing, and without that monotonicity the displayed telescoping inequality need not hold. Theorem 3 as stated is therefore unproven. Corollary 2's schedule β1t = β1/t is non-increasing, so the corollary can be salvaged, but the theorem should either add the monotonicity assumption or supply a proof that avoids it.
  3. [Section 4, Lemma 1] Lemma 1 is stated as a starting point for Theorem 3, but its proof is only a reference to an intermediate result in the proof of Theorem 4 of Luo et al. (2019) 'up to (but not including) Equation 6'. Since the paper's main point is that Luo et al.'s proof contains an error, the reader cannot verify whether the cited intermediate result is sound, and no equation number or derivation is provided. Please give a self-contained proof of Lemma 1, or explicitly reproduce the relevant equations from Luo et al., so that the new O(√T) guarantee can be checked independently.
minor comments (4)
  1. [Section 4, Theorem 3 and Proposition 1] The assumption t/ηl(t) − (t−1)/ηu(t−1) ≤ M involves ηu(0) at t=1, which is undefined; please define ηu(0) or state that the term is interpreted as 0 when t=1.
  2. [Section 4, Eq. (22)] In the first displayed inequality of Corollary 2's proof, the expression 'd sum_i [1 + β1 Σ ...]' appears to multiply by the dimension twice; it should be a single d (or a single sum over i).
  3. [Figure 1] The caption's 'AdaBound = 10 10' and 'AdaBound = 10 3' should read γ = 10^{-10} and γ = 10^{-3}; the superscripts are missing.
  4. [Throughout] There are several typographical issues, including 'F or' for 'For' before Theorems 1 and 3, 'whichis not accounted' in the abstract, and inconsistent ordering of 'stochastic convex' versus 'convex stochastic'; these should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: the counterexample is built from an external non-convergence result, and the new regret proof proceeds from stated assumptions without assuming its conclusion.

full rationale

The paper's central claims do not reduce to their inputs by construction. Theorem 2's counterexample is not derived from the target guarantee; it constructs bound functions for which the AdaBound clipping is the identity on a specific stochastic convex problem, and then invokes Reddi et al. (2018) Theorem 3 as an external non-convergence result. The sentence 'Therefore, in this setting, AdaBound produces the same iterates {x_t}_{t=1}^K as Adam. We can then invoke Theorem 3 of Reddi et al. (2018)' shows that the load-bearing premise is an external theorem rather than a fitted parameter or a renamed conclusion of Luo et al. (2019). Whether Reddi et al.'s theorem applies verbatim to AdaBound's extra 1/sqrt(t) factor is a correctness risk about external premises, not circularity. The new guarantee in Theorem 3 starts from an intermediate lemma of Luo et al. (2019) but replaces the assumption on the bound functions with t/eta_l(t) - (t-1)/eta_u(t-1) <= M and proves the O(sqrt(T)) bound from that assumption; it does not assume the original Theorem 1 or its conclusion. The one self-citation, to Savarese et al. (2019) in the introduction, is contextual and is not used to justify any later theorem. The empirical section comparing AdaBound to SGDM with dampening is an experimental observation, not a renamed known result. Therefore no circular step is present, and the appropriate score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard online convex optimization assumptions and on Reddi et al.'s black-box non-convergence theorem. The constants C, K, delta, and gamma are hand-chosen in the construction or experimental setup, not fitted to data; no new entities are introduced.

free parameters (4)
  • C = large; C > max(1, alpha), depends on delta, beta1, beta2
    Chosen by hand in Theorem 2 to make Reddi et al.'s Adam counterexample apply to AdaBound; also sets the gradient bound and the lower clipping bound alpha/C.
  • K = arbitrary positive integer; chosen large in Corollary 1
    The horizon over which AdaBound stays Adam-like in Theorem 2; arbitrarily slow convergence is parameterized by K.
  • delta = 1
    Determines the expected objective slope and the suboptimality threshold; setting delta=1 yields E[f(x_t)] - f(x*) >= 1.
  • gamma = 0.001, 1e-10, 100 in experiments; theoretical limit gamma -> infinity
    The bound-function slack in Luo et al.'s AdaBound; M = 3 + 2/gamma in Proposition 1 and the Corollary 2 regret bound depend on it. Not fitted to data, but a hand-set hyperparameter.
assumptions (4)
  • domain assumption Reddi et al. (2018) Theorem 3 is valid and applicable to AdaBound when clipping is the identity.
    Used without proof in Theorem 2 to assert E[x_{t+1}] >= E[x_t] for large C; this is an external theorem, not part of the current derivation.
  • standard math Online-to-stochastic conversion result of Cesa-Bianchi et al. (2006).
    Implicitly connects online regret bounds to stochastic convex suboptimality; standard result in the literature.
  • domain assumption Bounded domain and bounded gradient assumptions (D_inf, G_inf, R_inf) from Luo et al. are adopted for the regret bounds.
    Needed for both Theorem 1 and Theorem 3; standard assumptions for online convex regret.
  • ad hoc to paper The sequence beta1t is non-increasing in the proof of Theorem 3.
    The proof uses 0 <= beta1,(t+1) <= beta1,t < 1, but the theorem statement only assumes beta1t <= beta1; this is an extra unstated assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Convergence of AdaBound and its Connection to SGD." pith.science (2026). https://pith.science/paper/4TNNKGNR

@misc{pith2026190804457,
  author       = {Pith},
  title        = {Pith review of: On the Convergence of AdaBound and its Connection to SGD},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4TNNKGNR}},
  note         = {Machine review of arXiv:1908.04457}
}
abstract

Adaptive gradient methods such as Adam have gained extreme popularity due to their success in training complex neural networks and less sensitivity to hyperparameter tuning compared to SGD. However, it has been recently shown that Adam can fail to converge and might cause poor generalization -- this lead to the design of new, sophisticated adaptive methods which attempt to generalize well while being theoretically reliable. In this technical report we focus on AdaBound, a promising, recently proposed optimizer. We present a stochastic convex problem for which AdaBound can provably take arbitrarily long to converge in terms of a factor which is not accounted for in the convergence rate guarantee of Luo et al. (2019). We present a new $O(\sqrt T)$ regret guarantee under different assumptions on the bound functions, and provide empirical results on CIFAR suggesting that a specific form of momentum SGD can match AdaBound's performance while having less hyperparameters and lower computational costs.

Figures

Figures reproduced from arXiv: 1908.04457 by the authors.

Figure 1
Figure 1. Training curves for AdaBound and momentum SGD (SGDM) ( [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Method for Enhancing Generalization of Adam by Multiple Integrations

    cs.LG 2024-12 reject novelty 4.0 of 10

    MIAdam adds an n-th order integral term to Adam's gradient update for the first ζ steps, then switches to Adam, and is reported to improve test accuracy and label-noise robustness.

  2. Principled Approximation Methods for Efficient and Scalable Deep Learning

    cs.LG 2025-08 conditional novelty 3.0 of 10

    A thesis that synthesizes the author's published work on continuous approximations to discrete deep learning problems, with experiments showing efficiency gains, but offering little new beyond the author's prior papers.

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages · cited by 2 Pith papers

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Cesa-Bianchi, A

    N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theor., September 2006

    work page 2006

  3. [3]

    Bert: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv:1810.04805, 2018

    arXiv 2018

  4. [4]

    Improved regularization of convolutional neural networks with cutout

    Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv:1708.04552, 2017

    arXiv 2017

  5. [5]

    Duchi, E

    J. Duchi, E. Hazan, , and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. ICML, 2011

    work page 2011

  6. [6]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR , 2016

    work page 2016

  7. [7]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015

    work page 2015

  8. [8]

    Learning multiple layers of features from tiny images

    Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009

    2009

Show all 16 references
  1. [9]

    Liangchen Luo, Xiong, Yuanhao, Liu, Yan, and Xu. Sun. Adaptive gradient methods with dynamic bound of learning rate. ICLR (arXiv:1902.09843), 2019

    1902 arXiv

  2. [10]

    Reddi, Satyen Kale, and Sanjiv Kumar

    Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018

    2018

  3. [11]

    Domain-independent Dominance of Adaptive Methods

    Pedro Savarese , David McAllester , Sudarshan Babu , and Michael Maire . Domain-independent Dominance of Adaptive Methods . arXiv:1912.01823, 2019

    1912 arXiv

  4. [12]

    Tieleman and G

    T. Tieleman and G. Hinton. Lecture 6.5---RmsProp: Divide the gradient by a running average of its recent magnitude . COURSERA: Neural Networks for Machine Learning, 2012

    2012

  5. [13]

    Neural Discrete Representation Learning

    Aaron van den Oord , Oriol Vinyals , and Koray Kavukcuoglu . Neural Discrete Representation Learning . arXiv:1711.00937, 2017

    2017 arXiv

  6. [14]

    Wilson , Rebecca Roelofs , Mitchell Stern , Nathan Srebro , and Benjamin Recht

    Ashia C. Wilson , Rebecca Roelofs , Mitchell Stern , Nathan Srebro , and Benjamin Recht . The Marginal Value of Adaptive Gradient Methods in Machine Learning . NIPS, 2017

    2017

  7. [15]

    Wide residual networks

    Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. BMVC , 2016

    2016

  8. [16]

    Online convex programming and generalized infinitesimal gradient ascent

    Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML, 2003

    2003

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.