- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper established a unified and general convergence analysis for stochastic heavy-ball methods with Polyak step sizes and a modified Armijo line search. It covers strongly convex, convex, and non-convex objectives, and further studies almost-sure convergence under interpolation/strong growth and diminishing variants beyond interpolation.
Critical strengths
The manuscript is clearly written and well organized. The authors provide generalized convergence guarantees for SHB with PS and ALS. The analysis covers both convex and non-convex objectives and removes an explicit upper bound on the fixed momentum parameter in several non-diminishing results. By establishing two decoupling lemmas tailored to the convex and non-convex analyses, the authors effectively address the primary technical challenges inherent in analyzing SHB dynamics.
Critical weaknesses
-
Although the authors establish convergence guarantees for SHB with PS and ALS, the derived theoretical bounds lack further interpretative analysis, and the specific role of momentum in these bounds is not sufficiently clarified.
-
The standard results formally allow any fixed , but the admissible step-size bounds shrink strongly with . Thus, the claim of avoiding momentum restrictions should be interpreted carefully, since large momentum is compensated by increasingly conservative step sizes.
-
The almost-sure convergence results for diminishing variants require , implying that the momentum must vanish sufficiently fast. This condition excludes the practically dominant constant-momentum regime (e.g., ), thereby substantially limiting the practical relevance of the strongest asymptotic results.
-
The empirical evaluation is primarily based on low-dimensional synthetic problems, with deep learning experiments limited to ResNet-18 on CIFAR-10/100. Comparisons with closely related adaptive momentum methods (e.g., MomSPS, AdaHB [1]) and standard optimizers (e.g., SGD with Momentum and AdamW, Armijo-LS [2]) are needed to better assess the practical significance of the theoretical extensions. [1] The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods. ICLR 2021. [2] Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster. ICML 2025.
-
The deep learning experiments introduce an additional momentum-dependent stepsize rescaling and use (c=0.1) for SHB-ALS, which falls outside the conditions of several main theorems. The authors should clarify how these modifications affect the applicability of the theoretical guarantees and whether the empirical performance persists under theoretically admissible configurations.
Questions for authors
-
Can any of the established convergence results be extended to constrained optimization settings?
-
What are the specific advantages of the proposed algorithms over standard SGD equipped with PS and ALS?
6 comments
Response to Reviewer 6HPw (Part 2/3)
2. Further interpretation of the convergence guarantees and the role of momentum
Thank you for this valuable suggestion. We have expanded the discussion in the revised manuscript to explain how momentum affects the transient term, contraction factor, and residual term through both explicit coefficients and step-size scaling. We have also clarified the scope of the different results, including how the general non-convex analysis uses the adaptive step-size structure, the momentum requirements in the diminishing-step-size results, and the distinction between practical configurations and theoretical guarantees.
3. Summable momentum in the diminishing step-size results
We agree that this is a limitation of our current diminishing-step-size analysis, as already noted in the limitations discussion. The requirement arises from our current Lyapunov construction and supermartingale argument. Specifically, the recursion contains multiplicative correction factors of the form , and we use the summability of to control these momentum terms and apply the Robbins–Siegmund lemma to establish almost-sure convergence. Developing a more refined Lyapunov construction to accommodate constant or non-summable momentum is also an important direction for future work. We also note that almost-sure results under interpolation or strong growth do not require summable momentum. We have clarified the scope of these results in the revised manuscript.
4. Experimental scope and related baselines
We reiterate that our main contribution is a broader convergence guarantee for existing adaptive step sizes in SHB. The controlled experiments in the main text illustrate convergence behavior directly corresponding to the theoretical results, while experiments on practical learning tasks complement the analysis by showing how these methods behave in applications. We do not aim to establish their universal empirical superiority over other optimizers.
We agree that additional related baselines would help readers better understand their practical performance. Following the reviewer's suggestion, we include comparisons with AdaHB and AdamW in the revised manuscript and specify the corresponding experimental settings. The original manuscript already includes fixed-step SHB, as well as momentum-free SPS and SLS baselines. The stochastic part of the Armijo-LS work mentioned by the reviewer provides a more refined theoretical analysis of the same basic SLS method. We have clarified this relationship in the appendix.
For , SHB-PS as defined in our paper corresponds exactly through a reparameterization of and the step-size cap:
=\frac{2(1-\beta)}{(1-\sqrt\beta)^2} c_{\mathrm{SHB\text{-}PS}}, \qquad \gamma_b=\frac{\gamma_{\max}}{1-\beta}.$$ Here, $\gamma_b$ is the MomSPS truncation cap before multiplication by $(1-\beta)$. With the same objective lower bounds, initialization, momentum, and sample sequence, this parameter mapping produces exactly the same iterates. An experimental comparison under exact matching would therefore duplicate the same trajectory. Our contribution for PS is to establish more general convergence guarantees for this existing algorithm family. ## 5. Practical rescaling and the scope of the theoretical guarantees As explained above, the practical experiments in the appendix complement our analysis by illustrating the behavior of these existing methods on real machine learning tasks. They are not intended to establish that the reported configurations satisfy all the theoretical conditions, or that these methods necessarily converge faster than other optimizers. The controlled experiments in the main text use settings corresponding to the theoretical assumptions and step-size conditions to illustrate the associated convergence behavior. We have made the distinction between the practical configurations and the theoretical guarantees more explicit in the revised manuscript. Our controlled experiments in the main text strictly follow the theoretical assumptions and step-size conditions. In these settings, the momentum-free counterparts converge faster than the corresponding momentum methods. This behavior is consistent with the conservative momentum-dependent step-size scaling used to obtain our general convergence guarantees. Recall the PS counterexample in Point 1, which demonstrates why such control can be necessary in general settings. We again highlight that our contribution is to establish broader convergence guarantees for existing adaptive step-size methods with momentum, rather than to guarantee improved practical performance from adding momentum.Response to Reviewer 6HPw (Part 3/3)
6. Extension to constrained optimization
Thank you for suggesting this meaningful direction. Extending the SHB convergence analysis with PS and ALS to constrained optimization is worth investigating, but general constraints are not covered by a direct application of our current proofs. For example, projection onto a general closed convex set introduces an additional correction term in the update, changing the exact expansion of the SHB momentum history. The current decoupling relations and Lyapunov analysis would therefore require corresponding adjustments. We will consider projected or proximal extensions in future work.
7. Advantages over momentum-free PS and ALS
We would like to again clarify that our contribution is neither a new optimization algorithm nor a claim of accelerated convergence rates. In this context, the potential advantages of adding momentum are primarily empirical improvements on particular tasks, as illustrated by our appendix experiments. Related empirical benefits have also been investigated in prior work on SLS and MomSPS.
The value of our work lies in establishing broader theoretical guarantees and clarifying the conditions under which these existing methods (PS and ALS in SHB) converge. We have made this contribution more explicit in the revised manuscript.
We thank the reviewer again for the detailed comments. We have uploaded the revised PDF, incorporating the theoretical discussions, counterexample, additional experimental comparisons, and clarifications of the scope of our guarantees.
Response to Reviewer 6HPw (Part 1/3)
Thank you for your careful reading and valuable suggestions. We would first like to emphasize that our main contribution is a broader convergence-rate theory for existing adaptive step-size rules (PS and ALS) in stochastic heavy ball methods. We do not propose a new optimization algorithm or aim to establish the practical superiority of these methods over other optimizers. We address the concerns and questions below.
1. Arbitrary fixed momentum and step-size scaling
We note that our results allow any fixed β∈[0,1) with the step sizes scaling (1−β)2. This helps remove an additional upper-bound restriction on the fixed momentum parameter. As momentum approaches 1, the admissible step-size range indeed shrinks. This is also intuitive: larger momentum retains historical gradients for longer, so smaller step sizes may be needed to maintain stability.
Notably, we can construct a counterexample showing that, even for smooth, strongly convex objectives satisfying interpolation, the linear scaling (1−β) as used in MomSPS is insufficient to guarantee convergence across the full momentum range with a fixed c. Moreover, this example requires the total coefficient multiplying the Polyak ratio to be O((1−β)2), matching the asymptotic order of our scaling (1−β)2 as β↑1.
In two-dimensional polar coordinates θ=(rcosϑ,rsinϑ), let
\qquad f(\boldsymbol\theta;\phi) =\frac{r^2}{2}\exp\bigl(\psi(\vartheta-\phi)\bigr), \qquad \phi\sim\operatorname{Unif}[0,2\pi),$$ with independent samples at each iteration and $f(\mathbf0;\phi)=0$. All sample objectives share uniform strong-convexity and gradient-Lipschitz constants, and their common minimizer is $\mathbf0$. Thus, this construction falls within our stochastic objective setting and satisfies interpolation. Consider PS with the linear momentum scaling $(1-\beta)$ as used in $\mathrm{MomSPS}_{\max}$: $$\gamma_k =\frac{1-\beta}{c} \frac{f(\boldsymbol\theta_k;\phi_k)} {\\|\nabla f(\boldsymbol\theta_k;\phi_k)\\|^2}.$$ The normalized update is defined as zero at the origin. This example also permits a finite truncation cap that remains inactive: since $f/\\|\nabla f\\|^2\le e^{3/8}/2<1$ away from the origin, the original MomSPS cap $\gamma_b=1$ is inactive whenever $c\ge1$. The key observation is that the expected PS-normalized direction contains a rotational component: $$\mathbb E_\phi\left[ \frac{f(\boldsymbol\theta;\phi)} {\\|\nabla f(\boldsymbol\theta;\phi)\\|^2} \nabla f(\boldsymbol\theta;\phi) \right] =(AI+BJ)\boldsymbol\theta,$$ where $J$ denotes counterclockwise rotation by $90^\circ$, and $$A=\mathbb E_{U\sim\operatorname{Unif}[0,2\pi)} \frac{2}{4+\psi'(U)^2}, \qquad B=\mathbb E_{U\sim\operatorname{Unif}[0,2\pi)} \frac{\psi'(U)}{4+\psi'(U)^2}.$$ A direct calculation gives $8/17\le A\le1/2$ and $B\le-1/4096<0$, with both constants independent of $\beta$. Representing the mean iterate as the complex number $z_k=\mathbb E[\theta_{k,1}+i\theta_{k,2}]$, the SHB update yields the exact recurrence $$z_{k+1} =\left(1+\beta-\frac{1-\beta}{c}(A+iB)\right)z_k -\beta z_{k-1}.$$ Both characteristic roots lie strictly inside the unit disk if and only if $$c> \frac{A(1-\beta)}{2(1+\beta)} +\frac{B^2(1+\beta)}{2A(1-\beta)}.$$ The right-hand side diverges as $\beta\uparrow1$ and is asymptotic to $B^2/[A(1-\beta)]$. Therefore, for every fixed $c\ge1$, there exists a fixed $\beta$ sufficiently close to $1$ for which the mean recurrence is unstable. Any nonzero initialization with zero initial velocity excites the unstable mode, implying $$\mathbb E[F(\boldsymbol\theta_k)-F(\mathbf0)]\longrightarrow\infty.$$ Thus, even the linear scaling $(1-\beta)$ cannot guarantee convergence across the full momentum range with a fixed $c$. More generally, denote the total coefficient multiplying the Polyak ratio by $\lambda_\beta$. Asymptotic stability of the mean recurrence in this example requires $$0<\lambda_\beta< \frac{2A(1+\beta)(1-\beta)^2} {A^2(1-\beta)^2+B^2(1+\beta)^2} =\mathcal O\bigl((1-\beta)^2\bigr).$$ Our scaling satisfies $(1-\sqrt\beta)^2\sim(1-\beta)^2/4$. Hence, for PS updates whose cap is inactive, controlling the effective coefficient at the $\mathcal O((1-\beta)^2)$ scale is necessary in the worst case over the problem class considered in our paper, and our scaling matches this necessary asymptotic order. This demonstrates why accommodating arbitrary fixed momentum can require such conservative step-size control. Such control serves our goal of establishing more general convergence guarantees, though it can worsen the convergence constants and residual bounds. We have included this counterexample and discussion in the revised manuscript, while clarifying that arbitrary fixed momentum remains subject to the corresponding step-size conditions.