{"id":"2a72a85e-f28e-4fa2-af4e-fe6e0c924a3f","arxiv_id":"1908.04457","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"AdaBound's published O(sqrt(T)) regret guarantee is shown to be incorrect via a counterexample, a corrected guarantee is proved, and dampened SGDM is shown to match AdaBound on CIFAR.","lead":"This paper shows that AdaBound, a popular optimizer, can be arbitrarily slow on a simple stochastic convex problem, contradicting its published convergence guarantee. It then proves a corrected regret bound and shows that a simple dampened momentum SGD matches AdaBound on CIFAR with fewer hyperparameters.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Counterexample depends on an unverified equivalence between AdaBound's η_t=α/(√t√v_t) update and the Adam version in Reddi et al.'s Theorem 3; if the step-size schedule or bias correction differs, the inherited monotonicity E[x_{t+1}]≥E[x_t] may fail.","rationale":"The paper's headline contribution is the counterexample to Luo et al.'s Theorem 4, and that counterexample is only as strong as the imported Adam non-convergence result. The least secure point in the proof of Theorem 2 is the step that identifies AdaBound's iterates with Adam's iterates. AdaBound's extra division by √t in η_t is the kind of normalization that can change a non-convergence proof: for example, a faster-decaying step size can sometimes repair the failure mode that the counterexample exploits. The paper's proof is terse at exactly this point—it states that the clipping is an identity and then invokes Reddi et al.'s Theorem 3 without comparing the two algorithms line by line. This is a genuine verification gap, not a manufactured one. It is also the most load-bearing, because without the inherited monotonicity the lower bound E[f(x_t)]−f(x*)≥1 has no proof, and Corollary 1's arithmetic alone cannot yield a contradiction. A separate but secondary gap exists in Theorem 3: the proof of the S1 bound uses the monotonicity assumption 0≤β1,(t+1)≤β1,t, which is not stated in the theorem. I agree with the reader's conditional verdict: the central counterexample is likely correct, but it should be made self-contained at the point where Reddi's theorem is imported, and Theorem 3's statement should be amended or its proof adjusted. The concrete test proposed above would settle whether the Reddi-equivalence concern actually lands.","tokens_in":9550,"tokens_out":26958,"duration_ms":261012,"concrete_test":"Obtain the exact algorithm statement and proof of Reddi et al.'s Theorem 3 and check whether it sets the step size to α/√t and whether it includes bias correction. Then independently re-derive the monotonicity bound E[x_{t+1}]≥E[x_t] for the exact AdaBound update with η_t=α/(√t√v_t), no bias correction, and β1=0, on the stochastic problem in (5). If this monotonicity fails for any admissible C, δ, β2 for t≤K, Theorem 2 and Corollary 1 do not establish the contradiction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central contradiction with Luo et al.'s Theorem 4 rests on Theorem 2's assertion that AdaBound, when the clipping operation is the identity, 'produces the same iterates as Adam' and therefore inherits Reddi et al.'s Theorem 3 monotonicity E[x_{t+1}]≥E[x_t]. This inheritance is the load-bearing external premise, and the paper does not verify it for AdaBound's exact update. AdaBound's Algorithm 1 sets η_t = η̂_t/√t, so when clipping is the identity the effective update is x_{t+1} = Π(x_t − α/(√t√v_t)·m_t), with no bias correction in the algorithm as written. Reddi et al.'s Theorem 3 must be for exactly this normalization for the iterates to match. If Reddi et al. use a constant step size α rather than α/√t, or if their Adam includes bias correction terms, then AdaBound's iterates differ from the analyzed Adam iterates in a way that could break the non-decreasing expectation property. The paper neither quotes the precise algorithm in Reddi et al.'s theorem nor re-derives the monotonicity under AdaBound's factor 1/√t. Since Corollary 1 further specializes to β1=0, the applicability of Reddi's theorem at β1=0 should also be checked explicitly. If this monotonicity does not hold, the lower bound E[f(x_t)]−f(x*)≥1 collapses, and the contradiction with Luo et al.'s Theorem 4 is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9822,"tokens_out":26217,"duration_ms":239844,"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":[{"comment":"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.","section":"Section 3, proof of Theorem 2"},{"comment":"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.","section":"Section 4, Theorem 3, Eq. (15)"},{"comment":"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.","section":"Section 4, Lemma 1"}],"minor_comments":[{"comment":"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.","section":"Section 4, Theorem 3 and Proposition 1"},{"comment":"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).","section":"Section 4, Eq. (22)"},{"comment":"The caption's 'AdaBound = 10 10' and 'AdaBound = 10 3' should read γ = 10^{-10} and γ = 10^{-3}; the superscripts are missing.","section":"Figure 1"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the theoretical counterexample appears plausible and, if properly verified, would be a meaningful correction to a published ICLR result. The main risks are the unstated equivalence with Reddi et al.'s exact Adam variant and the missing monotonicity assumption in Theorem 3; both are fixable within the scope of the manuscript. I would not treat the empirical CIFAR results as the main selling point, as they are preliminary and focus on one architecture and dataset."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper finds a real flaw in the AdaBound convergence proof and gives a corrected O(sqrt(T)) regret bound under a different assumption. The central claim is likely right. The counterexample extends Reddi et al.'s Adam failure to AdaBound, and the contradiction with Luo et al.'s Theorem 4 is valid under the stated assumptions. The corrected theorem, while borrowing machinery from Luo et al., identifies a sensible quantity to control and is a useful contribution. The empirical observation about momentum SGD with dampening kappa=beta1 is a nice practical aside, and the paper does not oversell it.\n\nSoft spots, in proportion:\n\n1. Theorem 3's statement does not include the beta1t monotonicity that the proof actually uses. The proof says 'in the second inequality we used 0 <= beta1,(t+1) <= beta1,t', but the theorem only assumes beta1t <= beta1. Either add the assumption or change the proof. This is a genuine presentation gap, not a fatal one.\n\n2. The assumption in Theorem 3 references eta_u(0) when t=1, but bound functions are only defined for t>=1. The condition should be restricted to t>=2 or eta_u(0) should be defined. Minor but needs fixing.\n\n3. The bridge to Reddi et al. is stated as 'AdaBound produces the same iterates as Adam', without quoting the exact algorithm in Reddi et al.'s theorem. AdaBound has an extra 1/sqrt(t) factor and no bias correction. The stress-test note is right to flag this as an unverified external premise. I think the monotonicity E[x_{t+1}] >= E[x_t] likely survives because the step-size factor is positive and the proof only needs a signed expectation, but the manuscript should verify it explicitly rather than hand-wave.\n\n4. The experiments are preliminary, with a few runs and no code hash for the new experiments. Acceptable for a technical report, not a reason to reject.\n\nThe citation pattern is unremarkable; the self-citation is relevant prior work.\n\nThis paper is for optimization researchers and anyone relying on AdaBound's guarantee. It deserves a serious referee. I would send it out and expect revision on the theorem statement and the Reddi inheritance, with the central counterexample standing.","headline":"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.","tokens_in":10386,"tokens_out":4234,"would_cite":true,"duration_ms":44742,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["AdaBound","adaptive gradient methods","regret bound","stochastic convex optimization","non-convergence","momentum SGD","Adam","CIFAR"],"falsifier":"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.","tokens_in":9255,"feed_emoji":"🐌","tokens_out":10917,"duration_ms":97329,"temperature":0.7,"pith_summary":"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.","feed_headline":"AdaBound's regret bound is contradicted by a slow-to-converge example","feed_subtitle":"A constructed problem keeps suboptimality at least 1 for any K steps, so the claimed O(sqrt(T)) rate cannot hold.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines AdaBound and states the O(sqrt(T)) regret guarantee (Theorem 4) whose proof and truth the paper challenges; also supplies the recommended bound functions.","marker":"Luo et al. (2019)"},{"why":"Provides the one-dimensional stochastic convex problem and the Adam non-convergence result that the counterexample invokes once AdaBound's clipping becomes the identity.","marker":"Reddi et al. (2018)"},{"why":"Defines the Adam update that AdaBound builds on by adding clipping; its dynamics are what AdaBound inherits during the identity phase.","marker":"Kingma & Ba (2015)"},{"why":"Connects online regret bounds to stochastic convex expected suboptimality, the setting in which Theorem 2 and Corollary 1 are stated.","marker":"Cesa-Bianchi et al. (2006)"},{"why":"Supplies the Wide ResNet-28-2 architecture used in the CIFAR experiments that compare AdaBound with dampened momentum SGD.","marker":"Zagoruyko & Komodakis (2016)"}],"fun_headline_variants":["AdaBound regret bound disproved by slow-convergence case","AdaBound proof flaw: can take arbitrarily long to converge","Counterexample shows AdaBound's O(√T) regret guarantee fails","AdaBound's regret claim contradicted; new bound under relaxed assumptions","Momentum SGD matches AdaBound's performance with fewer hyperparameters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["AdaBound regret bound disproved by slow-convergence case","AdaBound proof flaw: can take arbitrarily long to converge","Counterexample shows AdaBound's O(√T) regret guarantee fails","AdaBound's regret claim contradicted; new bound under relaxed assumptions","Momentum SGD matches AdaBound's performance with fewer hyperparameters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1471,"prompt_tokens":1058,"completion_tokens":413,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":324}},"tokens_in":674,"tokens_out":413,"duration_ms":4716,"temperature":1.0,"reasoning_tokens":324,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:43:51.540762+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Wide residual networks","cited_arxiv_id":null,"evidence_quote":"Supplies the Wide ResNet-28-2 architecture used in the CIFAR experiments that compare AdaBound with dampened momentum SGD."}],"review_version":1}