{"id":"e504a19f-2adf-42b3-b152-ece3c1d44a13","arxiv_id":"2508.15071","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"NGN-M, a momentum variant of the NGN step-size, provably converges at O(1/sqrt(K)) under milder assumptions and shows wider step-size stability than Adam, Momo, and SGDM in vision and language tasks.","lead":"This paper adds momentum to the NGN adaptive step-size rule and tests a coordinate-wise version, aiming for optimizers that keep working across a wide range of learning rates. If the results hold, deep learning practitioners could spend less time tuning learning rates and still match Adam-level performance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main convergence theorem only covers momentum β = O(1/√K), while the practically used β = 0.9 lies outside the proven regime; this gap is structural, not merely technical, because the batch-optimum gap term fails to vanish when λ is constant.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Theorem 1's parameter regime excludes the β = 0.9 configuration used in all experiments. This is explicitly acknowledged in Section 4 item (iv) and Appendix F, and the review rules require such self-flagged limitations to be weighed. The concern is not merely that the proof has not been pushed to larger β; the IMA proof structure shows why a constant λ is problematic in non-interpolation settings: the mismatch Δ between the global optimum value and the average per-batch optimum value enters through the momentum cross-term and would not vanish in the rate unless λ is O(1/√K). Consequently, the headline theoretical contribution does not cover the empirically recommended algorithm, and the claimed stability at β = 0.9 rests on experiments plus a special 1D result. I did not find a flaw in the small-β theorem itself: the proof's main steps are coherent, the cited Lemma B.6 is from prior work, and the rate has the expected form. The conditional verdict is therefore appropriate: the central claim should either be qualified to the small-momentum regime or supplemented with a large-β analysis in general convex settings.","tokens_in":49361,"tokens_out":26034,"duration_ms":237088,"concrete_test":"Construct a one-dimensional convex quadratic without interpolation, e.g. f(x) = E_S[(a_S x − b_S)^2] with random (a_S, b_S) having no common root, so that Δ = f^* − E[f_S^*] > 0 and Assumptions 1–2 hold. Run NGN-M (Algorithm 1) for K up to 10^6 with c = 1/√K and two momentum settings: (i) β = cL/(1+cL), the theorem's regime, and (ii) β = 0.9. Track E[f(x_bar) − f*] over K with multiple seeds. If the β = 0.9 curve plateaus above the small-β curve while the small-β curve decays as 1/√K, then the practical regime is genuinely outside the proven guarantee; if both decay as 1/√K, the small-β restriction is only a proof artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 (Section 4) proves E[f(x_bar)−f(x*)] ≤ O(1/√K) only under the parameter condition λ ≤ min{cL, 0.5(1+cL)^{-1}(1+2cL)^{-1}}, with β = λ/(1+λ). Since the rate requires c = O(1/√K), this forces β = O(1/√K): e.g. for K=10^4 and L=1, the allowed β is about 0.01. The paper's experiments, however, use the standard β = 0.9 (λ = 9) throughout (Appendix J), a value that violates the theorem's condition by orders of magnitude. This is not merely a benign proof gap. In the IMA proof, the momentum cross-term in Eqs. (24)–(26) produces a contribution E[f_S(x_{k-1}) − f_S^*] = A_{k-1} + Δ, where Δ = f^* − E[f_S^*] > 0 in non-interpolation settings. To make this term decay at the O(1/√K) rate, the proof needs λ = O(c); a constant λ leaves a non-vanishing noise floor proportional to Δ. Thus the central claim that NGN-M attains O(1/√K) without interpolation is established only in a regime where momentum is negligible, while the practically recommended and tested configuration β = 0.9 is supported only by experiments and by a special 1D analysis (Appendix F), not by Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes NGN-M, a momentum variant of the NGN adaptive step-size method, along with two coordinate-wise extensions (NGN-MDv1/v2) and a diagonal-only variant (NGN-D). The main theoretical claim is that under convex L-smooth losses and bounded variance of per-batch optimal values, NGN-M achieves the standard O(1/√K) convergence rate without interpolation, bounded stochastic gradients, or bounded iterates (Theorem 1, Section 4). This is supported by a proof using the iterative moving average (IMA) formulation and a decomposition of the NGN step-size into constant and fluctuating parts. The paper further gives a diminishing-step-size variant (Theorem 4, Appendix E) and a special 1D large-momentum stability result (Appendix F). Empirically, the authors evaluate NGN-M and NGN-MDv1 across CIFAR, ImageNet, and Transformer language models up to 1B parameters, demonstrating improved robustness to step-size hyperparameter choice and competitive or better performance than Adam, Momo, and related optimizers.","tokens_in":49826,"tokens_out":5818,"duration_ms":58455,"significance":"If the claims hold, this is a useful contribution to adaptive step-size methods: it extends the non-divergence and robustness properties of NGN to a momentum variant and to diagonal preconditioning, and it does so under weaker assumptions (no interpolation, no bounded gradients) than prior SPS-with-momentum analyses. The empirical study is unusually extensive for this line of work, covering up to 1B-parameter language models, and consistently shows that NGN-M/NGN-MDv1 tolerate a wider range of step-size hyperparameters than baselines. The proof of Theorem 1 is self-contained given standard smoothness and variance assumptions, and the paper transparently states its limitations, including the restricted momentum regime and the lack of large-scale parallelization support. The main weakness, discussed below, is that the central theoretical result is proven only for asymptotically vanishing momentum, whereas all experiments use the standard β=0.9, leaving the practically relevant regime supported only by experiments and a 1D special case.","major_comments":[{"comment":"","section":"Section 4, Theorem 1; Eqs. (26)–(29)"},{"comment":"","section":"Section 5, first paragraph"}],"minor_comments":[{"comment":"","section":"Section 3, Ver.1/Ver.2 design"},{"comment":"","section":"Appendix J, hyperparameters"},{"comment":"","section":"Section 4, Theorem 1 statement"},{"comment":"","section":"Appendix F"},{"comment":"","section":"Assumption 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is an honest and substantial piece of work, but the main theorem's regime (β=O(1/√K)) is far from the evaluated β=0.9. The authors already acknowledge the gap, and I think it is a fixable presentation/scope issue rather than a fatal error: the abstract and contribution list should explicitly qualify the O(1/√K) claim with the small-momentum condition, and the empirical section should make clear that the large-momentum behavior is an experimental finding supported only by the 1D result. If the authors can add at least a non-vanishing-error analysis or a stability argument for constant β, the contribution would be significantly stronger. I would not reject on this basis, but the current framing overstates the theory relative to practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper for two things: a sensible combination of the NGN step-size with heavy-ball momentum (NGN-M) and a diagonal variant (NGN-D/MD), plus a very wide empirical study showing step-size robustness on CIFAR, ImageNet, and language models up to 1B parameters. The headline theoretical claim is an O(1/√K) rate for NGN-M under convexity, bounded variance of per-batch optima, and no interpolation/bounded gradients/iterates. That proof is coherent, follows standard IMA/SGD machinery, and uses lemmas from Orvieto–Xiao correctly.\n\nThe soft spot is exactly what the stress-test says: the theorem requires λ = O(c) = O(1/√K), so the allowed momentum is tiny (β ≈ 0.01 for K = 10^4). The paper's experiments use β = 0.9 throughout. That is not a minor technicality—in the proof the cross-term leaves a non-vanishing noise floor proportional to f* − E[f_S*] when λ is constant. So the theoretically supported regime is not the practical one. To the authors' credit, they state this explicitly in Section 4(iv) and point to a 1D stability result for large β (Appendix F). But that is a restricted class, not a general convex answer.\n\nThe diagonal variants have no convergence guarantees at all; NGN-D's theory requires per-coordinate constants c_j, and the practical implementation sets them via an RMSprop preconditioner, which is an unanalyzed mismatch. The paper is also honest about the 2.5x runtime overhead versus AdamW and the lack of support for advanced parallelism. Still, no code is released, which hurts reproducibility for such a large empirical component.\n\nWhat is genuinely valuable: the empirical phenomenon is consistent and visually strong—NGN-M and NGN-MDv1 tolerate step-sizes one to two orders of magnitude larger than Adam or Momo, across many architectures and scales. That is a useful data point for the community, and it may survive even if the theory is narrower than the abstract implies.\n\nWho is this for: researchers working on Polyak-type step-sizes or on stable optimizers for deep learning. It deserves a serious referee—not because the theory is complete, but because the empirical claims are broad and the paper is open about its own limitations. I would send it to review, with expectation of major revision: the abstract and intro should stop saying 'NGN-M attains O(1/√K)' without the small-momentum caveat, and the practical β = 0.9 regime should be framed as empirical with only partial theory. If code appears, the empirical part becomes even more usable. I would not cite it in my own work this year, but I'd bring it to reading group to debate the value of a theorem that covers a non-practical regime.","headline":"The main theorem only covers negligible momentum (β ≈ 0.01), while the paper's own experiments use β = 0.9; the gap is real and structural, but the paper admits it and the empirical robustness results are substantive.","tokens_in":50249,"tokens_out":1836,"would_cite":false,"duration_ms":21637,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding heavy-ball momentum to the curvature-adaptive NGN step-size preserves its convergence rate and step-size robustness under far weaker assumptions than earlier momentum-plus-Polyak analyses required.","keywords":["NGN step-size","heavy-ball momentum","adaptive step-size","stochastic convex optimization","convergence rate","step-size robustness","coordinate-wise preconditioning","deep learning optimizers"],"falsifier":"Run NGN-M with $\\beta = 0.9$ and $cL$ around 5 to 10 on a convex $L$-smooth problem with visible batch noise — for instance a separable quadratic with varied per-coordinate curvature and small mini-batches — and record whether the function values stay bounded over many iterations. The theorem's momentum condition fails for these settings, so divergence would refute the practical stability claim, while bounded convergence near the predicted $O(cL\\sigma^2)$ neighborhood would indicate that the small-$\\lambda$ requirement is an artifact of the proof technique, exactly as the paper conjectures.","tokens_in":49128,"feed_emoji":"📉","tokens_out":21581,"duration_ms":184596,"temperature":0.7,"pith_summary":"This paper claims that heavy-ball momentum and the curvature-adaptive NGN step-size can be combined without giving up the step-size's best property: robustness to the choice of the learning-rate hyperparameter. The new algorithm, NGN-M, is proved to converge at the standard $O(1/\\sqrt{K})$ rate on convex $L$-smooth losses under only bounded variance of the per-batch optimal values, with no interpolation condition, no bounded stochastic gradients, and no bounded iterates — all of which earlier momentum-plus-Polyak-step-size analyses needed. Two coordinate-wise extensions, NGN-MDv1 and NGN-D, bring the same idea to the diagonal-preconditioning regime dominated by Adam. The paper acknowledges that the main theorem holds only for small momentum, while the recommended setting $\\beta = 0.9$ lies outside the proven regime, with a one-dimensional stability result as the only theoretical bridge to large momentum. In experiments on CNNs, vision transformers, and transformers up to a billion parameters, the proposed optimizers tolerate step-sizes one to two orders of magnitude larger than the optimum, matching or beating Adam and Momo-Adam.","feed_headline":"Momentum joins a curvature-adaptive step-size without losing stability","feed_subtitle":"Proved convergence under weak noise assumptions; step-sizes a hundred times too large still train.","key_machinery":"Two devices carry the proof. The first is the Iterative Moving Average (IMA) reformulation of momentum: with $\\beta = \\lambda/(1+\\lambda)$, the update is equivalent to $z_{k+1} = z_k - \\gamma_k \\nabla f_{S_k}(x_k)$ followed by $x_{k+1} = \\frac{\\lambda}{1+\\lambda} x_k + \\frac{1}{1+\\lambda} z_{k+1}$, which turns a second-order recursion into a contraction inequality in squared distances to the optimum. The second is a splitting of the NGN step-size into a fixed baseline $\\rho = c/((1+cL)(1+2cL))$ and an adaptive fluctuation $\\tilde{\\gamma}_k$ bounded by $O(c^2 L)$: the baseline drives the descent term, while the fluctuation contributes only noise terms weighted by $c^2$ times the variances $\\sigma^2_{f*}$ and $\\sigma^2_f$. The small-momentum condition $\\lambda \\le \\min\\{cL, \\tfrac12(1+cL)^{-1}(1+2cL)^{-1}\\}$ is exactly what makes $\\rho - c\\lambda > 0$, so the momentum-induced error telescopes away and the bound closes on the $O(1/\\sqrt{K})$ rate.","core_discovery":"The central claim is that the NGN step-size, which in its scalar form reads $\\gamma_k = c / (1 + \\tfrac{c}{2 f_S(x_k)} \\|\\nabla f_S(x_k)\\|^2)$ and automatically shrinks when the batch loss or the gradient is large, can be wrapped in the heavy-ball update $x_{k+1} = x_k - (1-\\beta)\\gamma_k \\nabla f_{S_k}(x_k) + \\beta (x_k - x_{k-1})$, and the resulting NGN-M provably satisfies $\\mathbb{E}[f(\\bar{x}_K) - f(x^*)] \\le O(1/\\sqrt{K})$ when $c = O(1/\\sqrt{K})$. The theorem assumes each $f_i$ is convex and $L$-smooth, and that the variances $\\sigma^2_{f*} = \\mathbb{E}[(f^* - f^*_S)^2]$ and $\\sigma^2_f = \\mathbb{E}[(f^*_S)^2]$ of the per-batch optimal values are finite; it holds with $\\beta = \\lambda/(1+\\lambda)$ and $\\lambda \\le \\min\\{cL, \\tfrac12 (1+cL)^{-1}(1+2cL)^{-1}\\}$. For any fixed $c$, the iterates provably reach and stay within a neighborhood of the optimum whose size scales with $c$ and $c^2$ times the two variances, so momentum inherits rather than destroys the non-divergence property of NGN. The paper also claims the first diagonal Polyak-type step-size, NGN-D, with an $O(1/\\sqrt{K})$ guarantee under standard smoothness and variance assumptions, without interpolation or bounded gradients.","pith_inferences":["If the small-$\\beta$ restriction turns out to be an artifact, as the paper's own 1D result hints, then the practical recipe $\\beta = 0.9$ would be backed by theory; the likely route is to exploit that near a minimizer the NGN step-size collapses to order $c/(1+cL)$, which would damp the momentum drift automatically.","The baseline-plus-fluctuation splitting is a transferable template: any adaptive step-size of the form $\\rho + \\tilde{\\gamma}$ with $|\\tilde{\\gamma}| \\le O(c^2 L)$ and a known lower bound could inherit the same momentum analysis, potentially covering RMSprop- or Adam-style rules.","The paper's own timing data show the naive implementation of NGN-MDv1 is about 2.5 times slower per update than a tuned AdamW implementation, leaving an open question the paper does not resolve: whether fused implementations or the wider stable hyperparameter range close that wall-clock gap in practice.","The empirical success at 1B scale suggests a workflow the paper does not spell out: fix one step-size hyperparameter per model family and scale model size without retuning, a form of hyperparameter transfer that the automatic shrinkage of the NGN step-size could provide for free."],"forward_implications":["Users can run NGN-M on convex or convex-like problems without ever checking interpolation, gradient boundedness, or iterate boundedness: any convex $L$-smooth problem with finite per-batch optimal-value variance qualifies for the $O(1/\\sqrt{K})$ guarantee.","Momentum does not ruin NGN's safety property: for every fixed step-size hyperparameter $c$, the iterates enter and stay in a neighborhood of the optimum whose radius vanishes as $c \\to 0$, so a too-large $c$ degrades accuracy without causing divergence.","NGN-D extends the same guarantee to coordinate-wise (diagonal) step-sizes, the regime where Adam operates, and is claimed to be the first diagonal Polyak-type method with an $O(1/\\sqrt{K})$ rate under standard smoothness and variance assumptions.","In the reported experiments, the stable step-size window of NGN-M and NGN-MDv1 is one to two orders of magnitude wider than that of SGDM, Adam, Momo, and Momo-Adam, with equal or better best-case accuracy or perplexity across CIFAR, ImageNet, and SlimPajama-trained transformers up to 1B parameters.","The effective step-size of NGN-MDv1 self-schedules: it rises, peaks early, and decays over training, resembling cosine annealing without any scheduler, which the paper identifies as the mechanism behind the resilience."],"supporting_citations":[{"why":"Defines the NGN step-size that NGN-M adapts, contributes the non-divergence property, and supplies the step-size bounds and squared-gradient lemmas that the proof reuses.","marker":"[Orvieto and Xiao, 2024]"},{"why":"Introduces the Momo and Momo-Adam momentum-plus-Polyak baselines whose step-size robustness motivates this work and against which NGN-M is compared in every experiment.","marker":"[Schaipp et al., 2024]"},{"why":"Provides the Iterative Moving Average (IMA) formulation of momentum that converts NGN-M's recursion into a contractive distance inequality.","marker":"[Sebbouh et al., 2021]"},{"why":"The MomSPS algorithm, the closest prior momentum-plus-Polyak method, which converges only to a non-vanishing neighborhood without interpolation; NGN-M's exact rate is contrasted with it.","marker":"[Oikonomou and Loizou, 2024]"},{"why":"Sets up the Stochastic Polyak Step-size framework and its interpolation requirement, which the new analysis drops.","marker":"[Loizou et al., 2021]"},{"why":"Standard SGD convergence theory whose $O(1/\\sqrt{K})$ rate NGN-M matches, and the source of the summation lemma used in the decaying-step-size variant.","marker":"[Garrigos and Gower, 2023]"},{"why":"The heavy-ball momentum update that NGN-M combines with the adaptive step-size, and the classical stability analysis used in the one-dimensional large-$\\beta$ result.","marker":"[Polyak, 1964]"}],"fun_headline_variants":["Momentum plus adaptive step-size for stable optimization","Adaptive step-size optimizer with momentum defies tuning","NGN-M: momentum meets adaptive step-size, stays stable","Robust training: momentum with curvature-adaptive step-size","Step-size sensitivity solved by momentum-adapted NGN"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the convergence proof only covers small momentum — with $\\lambda \\le \\min\\{cL, \\tfrac12(1+cL)^{-1}(1+2cL)^{-1}\\}$ and $\\beta = \\lambda/(1+\\lambda)$ — whereas the momentum value used in every deep-learning experiment, $\\beta = 0.9$ (that is, $\\lambda = 9$), violates this condition for any realistic $cL$; the paper explicitly acknowledges this and supports large momentum only with a one-dimensional stability theorem, so the headline stability of the practical configuration rests on experiments rather than on the main proof.","fun_headline_variants_meta":{"raw":{"variants":["Momentum plus adaptive step-size for stable optimization","Adaptive step-size optimizer with momentum defies tuning","NGN-M: momentum meets adaptive step-size, stays stable","Robust training: momentum with curvature-adaptive step-size","Step-size sensitivity solved by momentum-adapted NGN"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1762,"prompt_tokens":1127,"completion_tokens":635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":743,"completion_tokens_details":{"reasoning_tokens":566}},"tokens_in":743,"tokens_out":635,"duration_ms":5956,"temperature":1.0,"reasoning_tokens":566,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:43:27.010151+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run NGN-M with $\\beta = 0.9$ and $cL$ around 5 to 10 on a convex $L$-smooth problem with visible batch noise — for instance a separable quadratic with varied per-coordinate curvature and small mini-batches — and record whether the function values stay bounded over many iterations. The theorem's momentum condition fails for these settings, so divergence would refute the practical stability claim, while bounded convergence near the predicted $O(cL\\sigma^2)$ neighborhood would indicate that the small-$\\lambda$ requirement is an artifact of the proof technique, exactly as the paper conjectures.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Momo and Momo-Adam momentum-plus-Polyak baselines whose step-size robustness motivates this work and against which NGN-M is compared in every experiment."}],"review_version":1}