acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

Abstract

Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.

Primary area:
optimization
Keywords:
Stochastic heavy ball, adaptive step sizes, convergence guarantee

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_6HPwOpenReview ↗
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
  1. 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.

  2. The standard results formally allow any fixed β<1\beta<1, but the admissible step-size bounds shrink strongly with β\beta. Thus, the claim of avoiding momentum restrictions should be interpreted carefully, since large momentum is compensated by increasingly conservative step sizes.

  3. The almost-sure convergence results for diminishing variants require ∑kβk<∞\sum_k \beta_k<\infty, implying that the momentum must vanish sufficiently fast. This condition excludes the practically dominant constant-momentum regime (e.g., β=0.9\beta=0.9), thereby substantially limiting the practical relevance of the strongest asymptotic results.

  4. 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.

  5. 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
  1. Can any of the established convergence results be extended to constrained optimization settings?

  2. What are the specific advantages of the proposed algorithms over standard SGD equipped with PS and ALS?

6 comments
AuthorsOpenReview ↗

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)\beta\in[0,1) with the step sizes scaling (1−β)2(1-\sqrt{\beta})^2. This helps remove an additional upper-bound restriction on the fixed momentum parameter. As momentum approaches 11, 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−β)(1-\beta) as used in MomSPS is insufficient to guarantee convergence across the full momentum range with a fixed cc. Moreover, this example requires the total coefficient multiplying the Polyak ratio to be O((1−β)2)\mathcal O((1-\beta)^2), matching the asymptotic order of our scaling (1−β)2(1-\sqrt\beta)^2 as β↑1\beta\uparrow1.

In two-dimensional polar coordinates θ=(rcos⁡ϑ,rsin⁡ϑ)\boldsymbol\theta=(r\cos\vartheta,r\sin\vartheta), 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.
AuthorsOpenReview ↗

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 1+βk1+\beta_k, and we use the summability of {βk}\{\beta_k\} 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 MomSPSmax⁡\mathrm{MomSPS}_{\max}, SHB-PS as defined in our paper corresponds exactly through a reparameterization of cc 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.
AuthorsOpenReview ↗

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.

Reviewer_pHYFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the stochastic heavy ball method equipped with a Polyak step size and with a modified Armijo line search. For a fixed momentum parameter, the authors establish convergence in expectation to a neighborhood of the solution for strongly convex, convex, and non-convex (weak growth) objectives. Under interpolation or strong growth, these results are strengthened to almost sure convergence. For diminishing step sizes and summable momentum, the authors prove almost sure convergence to the exact solution or to stationarity. Finally, the authors also conduct numerical results on small synthetic problems and on LIBSVM and CIFAR-10/100.

Critical strengths
  • The paper is well written, it is easy to follow the structure and main result of the paper.
  • The unified treatment of the Polyak step size and the Armijo line search through a single step-size inequality is simple and convenient.
  • The paper covers strongly convex, convex, and non-convex objectives, in expectation and almost surely, which gives a fairly complete picture.
Critical weaknesses
  • The guarantee for any momentum parameter β∈[0,1)\beta \in [0,1) relies on the scaling factor (1−β)2(1-\sqrt{\beta})^2 in (3) and (5), and the resulting bounds do not establish an acceleration advantage over the momentum-free case.
  • Condition (21) requires knowledge of LL and ρρ, which is at odds with the motivation for Polyak steps and line search. In this form, Theorem 3 is essentially the standard analysis of heavy ball with bounded step sizes.
  • The Polyak momentum method, although of independent interest, seems to be less interesting for real deep learning model/llm training. The practical value could be strengthened by comparing it with Adamw, muon and others.
Questions for authors
  • Under matched hyperparameters, in which regimes do the bounds improve on the β=0\beta=0 case after accounting for both the transient term and the residual error? How do they compare with MomSPSmax for values of β\beta satisfying its restriction?
  • Can you compare with MomSPS series for the empirical performance, as you claim they are the most related work?
6 comments
AuthorsOpenReview ↗

Response to Reviewer pHYF (Part 1/3)

Thank you for your careful reading and thoughtful feedback. We would like to reiterate that our main contribution is to establish more general convergence guarantees for existing adaptive step sizes for SHB. 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. The scaling factor (1−β)2(1-\sqrt{\beta})^2

Our scaling factor indeed decreases as momentum increases. This choice allows us to establish convergence guarantees for any fixed β∈[0,1)\beta\in[0,1), subject to the corresponding step-size conditions. Intuitively, as β\beta approaches 11, historical gradients persist for longer in the update, and smaller step sizes may be needed to maintain stability.

We can make this requirement precise through an example in which even the linear scaling (1−β)(1-\beta) is insufficient for a fixed cc. Consider the following smooth, strongly convex stochastic problem satisfying interpolation. In polar coordinates θ=(rcos⁡ϑ,rsin⁡ϑ)\boldsymbol\theta=(r\cos\vartheta,r\sin\vartheta), 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$. This construction 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 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$. 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$, the mean recurrence is unstable for a fixed $\beta$ sufficiently close to $1$. 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)$ does not guarantee convergence across the full range of momentum parameters with a fixed $c$. More generally, denote the total coefficient multiplying the Polyak ratio by $\lambda_\beta$. Stability 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, a coefficient of $\mathcal{O}((1-\beta)^2)$ is necessary in the worst case over the problem class considered in our paper. Our scaling has this same asymptotic order. ## 2. Problem-specific constants in the convergence conditions In our non-convex analysis, the sufficient conditions for convergence depend on $L$ and $\rho$. Given $c$, $\gamma_{\max}$, and $\beta$, however, neither the per-iteration PS computation nor the Armijo condition requires these constants as explicit inputs. The underlying issue is that an adaptive step-size condition imposed on a sampled objective does not automatically ensure expected descent of the population objective. The analysis uses $L$ to control the curvature term and $\rho$ to control the second moment of the stochastic gradient. This issue is not specific to momentum. For example, the non-convex SPS theorem under weak growth includes the requirement $c>\rho L/(4L_{\max})$ [Loizou et al.]. Likewise, the non-convex SLS theorem under strong growth requires $c>1-L_{\max}/(\rho L)$ [Vaswani et al.]. We have added this discussion in the revised manuscript.
AuthorsOpenReview ↗

Response to Reviewer pHYF (Part 2/3)

3. Relationship to bounded step-size SHB analysis

Our non-convex analysis proceeds in three steps. First, Lemma 4 decouples the historical dependence introduced by momentum. Second, we use the step-size bounds to control the resulting terms, including the correlation between the adaptive step size and the current stochastic gradient. Third, we combine these estimates with the SHB recursion and weak growth to derive explicit convergence conditions and rates. The second step indeed follows a bounded step-size analysis. Consequently, our argument also applies to other, possibly sample-dependent, scalar step-size rules satisfying the same bounds and the resulting positivity condition for the descent coefficient.

We also acknowledge that this non-convex analysis exploits the specific structure of PS and ALS less directly than convex analysis. In the convex setting, convexity connects sample objective gaps to the gradient inner products in the distance-to-solution recursion, allowing us to use these rules more directly. By contrast, weak growth only controls the second moment of the stochastic gradient and does not provide an analogous geometric relation. Our general non-convex analysis therefore uses the bounds guaranteed by PS and ALS to control step-size correlations and momentum history. Additional structure, such as a PL condition, can support stronger guarantees and better align with these step-size rules [Loizou et al.]. But our general non-convex theorem does not assume this structure. We have added this discussion to clarify the scope of the result.

4. Comparison with β=0\beta=0 and \text{MomSPS}_\max under matched hyperparameters

With a common step-size cap, choosing cβ=(1−β)2c0c_\beta=(1-\sqrt{\beta})^2c_0 matches the two PS rules, and the constant in the convergence rates improves when cβ>1/βc_\beta>1/\sqrt{\beta}. The residual coefficient is larger, however, so the full bound improves under interpolation, or beyond interpolation only when the reduction in the convergence term outweighs the increase in the residual term. We acknowledge that our theory does not provide uniformly better convergence constants under matched cc. We have also included the β=0\beta=0 curves in the numerical experiments in the main text.

The absence of an acceleration guarantee is partly due to the more conservative step-size scaling (1−β)2(1-\sqrt{\beta})^2 used with momentum, which enables convergence guarantees in more general settings. We refer back to Point 1 for why such scaling can be necessary. Beyond the constants discussed here, the following counterexample shows that a uniformly faster worst-case convergence order is also impossible under the prescribed sampling scheme. We have included these discussions in the revised manuscript.

5. General assumptions do not guarantee an improved convergence order

Following point 4, we further give a simple interpolating quadratic family showing that SHB with arbitrary adaptive step sizes cannot uniformly improve the worst-case convergence order under the prescribed independent sampling scheme. Consider

\qquad f(\boldsymbol\theta;2)=\tfrac12\theta_2^2, \qquad \mathbb P(i_k=2)=p\in(0,1/2].$$ The population objective and its minimizer are $$F_p(\boldsymbol\theta) =\tfrac12[(1-p)\theta_1^2+p\theta_2^2], \qquad \boldsymbol\theta^\star=\mathbf0.$$ Both components are convex, $1$-smooth, and interpolating. Initialize $\boldsymbol\theta_{-1}=\boldsymbol\theta_0=(1,1)$, so the initial velocity is zero, the initial squared distance is $2$, and the objective gap is $1/2$. For SHB with any fixed $\beta\in[0,1)$ and arbitrary adaptive scalar step sizes, consider the event $$\mathcal E_K=\\{i_0=\cdots=i_{K-1}=1\\}, \qquad \mathbb P(\mathcal E_K)=(1-p)^K.$$ On this event, the sampled gradient has zero second coordinate at every step. Since the initial velocity in this coordinate is also zero, the SHB recursion gives $\theta_{k,2}=1$ for all $0\le k\le K$, regardless of the step-size choices. The last iterate, or any convex average $\widehat{\boldsymbol\theta}_K$ of these iterates, consequently satisfies $$\mathbb E[F_p(\widehat{\boldsymbol\theta}_K)-F_p(\mathbf0)] \ge\frac p2(1-p)^K.$$ For each horizon $K\ge1$, choosing $p=1/(K+1)$ yields $$\mathbb E[F_p(\widehat{\boldsymbol\theta}_K)-F_p(\mathbf0)] \ge\frac1{2(K+1)}\left(\frac K{K+1}\right)^K \ge\frac1{2e(K+1)}.$$ Thus, even arbitrary adaptive step-size tuning cannot give SHB a uniformly faster worst-case order over this smooth convex problem class. Momentum-free PS already admits a matching $\mathcal O(1/K)$ guarantee for averaged iterates. Therefore, under the general assumptions considered in this paper, adding momentum cannot uniformly improve the worst-case convergence order over the momentum-free counterpart.
AuthorsOpenReview ↗

Response to Reviewer pHYF (Part 3/3)

6. Comparison with \text{MomSPS}_\max

SHB-PS is exactly a reparameterization of MomSPSmax⁡\mathrm{MomSPS}_{\max}. The two rules correspond through

=\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, momentum, initialization, and sample sequence, this parameter mapping produces exactly the same iterates. Regarding theoretical rates, for convex objectives, both analyses establish an $\mathcal O(1/K)$ rate to a noise-dependent neighborhood. The original MomSPS\$_{\max}\$ bound can have more favorable constants within its admissible parameter regime. The distinction is in the theoretical guarantees and parameter conditions, rather than a different PS algorithm family. The original MomSPS parameterization gives a larger coefficient ($1-\beta$) multiplying the Polyak ratio, whereas our parameterization uses more conservative scaling $(1-\sqrt{\beta})^2$. MomSPS's convex guarantee restricts the admissible momentum range, while our analysis accommodates any fixed $\beta\in[0,1)$ under the corresponding step-size conditions. We recall that Point 1 explains why additional control of the effective step size can be necessary to obtain such a guarantee. Our contribution for PS is to establish broader convergence guarantees for this existing algorithm family. ## 7. Practical experiments complement the theoretical analysis We reiterate that our main contribution is a more general convergence theory for existing adaptive step sizes for SHB methods. The controlled experiments in the main text illustrate convergence behavior directly corresponding to the theoretical results. Experiments on practical learning tasks complement this analysis by demonstrating how these methods behave in applications, rather than establishing superiority over other optimizers. In response to the reviewer's suggestion, we have also added comparisons with AdamW and Muon. These results are included in the revised PDF. Finally, as explained in Point 6, SHB-PS and $\mathrm{MomSPS}_{\max}$ are the same algorithm under the corresponding reparameterization. Matching their parameters, initialization, and sampling produces identical iterates, so an experimental comparison under exact matching would duplicate the same trajectory. Our contribution relative to $\mathrm{MomSPS}_{\max}$ concerns the convergence guarantees and their parameter conditions. We also additionally include comparisons with MomDecSPS and MomAdaSPS under the same experimental protocol. We thank the reviewer again for the detailed comments. We have uploaded the revised PDF, incorporating the counterexamples, clarifications of the theoretical conditions and algorithmic relationships, and the additional experimental results. ------ [Loizou et al.] Loizou, Nicolas, et al. "Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence." *AISTATS*, 2021. [Vaswani et al.] Vaswani, Sharan, et al. "Painless stochastic gradient: Interpolation, line-search, and convergence rates." *NeurIPS*, 2019.
Reviewer_auxfOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper developed a unified convergence analysis for stochastic heavy ball methods with Polyak step size or a modified Armijo line search rule. For smooth convex optimization problems with finite optimial difference, the objective value of the uniform averages of the iterates achieve an O(1/k)\mathcal O(1/k) convergence to the a neighborhood of optimal value governed by the optimal difference in expectation. For smooth strongly convex optimization problems with finite optimial difference, the iterate converges linearly to a neighborhood of the optimum determined by the optimal difference in expectation. For non-convex objective with the weak growth condition, the best iterate approaches a neighborhood of stationarity at an O(1/k)\mathcal O(1/k) rate in expectation. With addtion interpolation, the strong growth condition or diminishing step sizes, almost sure convergence are established for convex and non-convex cases, respectively.

Critical strengths

The framework provides a more comprehensive theoretical understanding for stochastic heavy ball methods with the Polyak step size or a modified Armijo line search.

Critical weaknesses

In most cases, the convergence rate recovers the results of stochastic gradient descent. The momentum step size β\beta decreases the convergence rate and enlarges the deviation determined by the optimal difference.

Questions for authors
  • rr in Table 1 is not defined until Section 3.2

  • Can the Heavy-ball method preserve acceleration under stochastic settings? If not, what are the advantages of adding the momentum term, in terms of the convergence rates obtained by the paper?

6 comments
AuthorsOpenReview ↗

Response to Reviewer auxf (Part 1/3)

Thank you for your careful reading and thoughtful feedback. We'd like to highlight that our main contribution is a unified and general convergence analysis of stochastic heavy-ball methods with existing Polyak step sizes and Armijo line search, covering different objective classes and noise regimes. 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. General assumptions do not guarantee acceleration from momentum.

We note that, under the general assumptions as considered in our paper, momentum cannot uniformly improve the worst-case convergence order over the smooth convex problem class. For constant step sizes, [Kidambi et al.] establish a related negative result: there exist interpolating stochastic least-squares problems on which no choice of fixed step size and momentum allows SHB to improve the order of the condition-number dependence over SGD.

Here, we give a simple interpolating quadratic family showing that SHB with arbitrary adaptive step sizes cannot uniformly improve the worst-case convergence order under the prescribed independent sampling scheme. Consider

\qquad f(\boldsymbol\theta;2)=\tfrac12\theta_2^2, \qquad \mathbb P(i_k=2)=p\in(0,1/2].$$ The population objective and its minimizer are $$F_p(\boldsymbol\theta) =\tfrac12[(1-p)\theta_1^2+p\theta_2^2], \qquad \boldsymbol\theta^\star=\mathbf0.$$ Both components are convex, $1$-smooth, and interpolating. Initialize $\boldsymbol\theta_{-1}=\boldsymbol\theta_0=(1,1)$, so the initial momentum is zero, the initial squared distance is $2$, and the objective gap is $1/2$. For SHB with any fixed $\beta\in[0,1)$ and arbitrary adaptive step sizes, consider the event $$\mathcal E_K=\\{i_0=\cdots=i_{K-1}=1\\}, \qquad \mathbb P(\mathcal E_K)=(1-p)^K.$$ On this event, the sampled gradient has zero second coordinate at every step. Since the initial momentum in this coordinate is also zero, the SHB recursion gives $\theta_{k,2}=1$ for all $0\le k\le K$, regardless of the step-size choices. The last iterate, or any convex average $\widehat{\boldsymbol\theta}_K$ of these iterates, consequently satisfies $$\mathbb E[F_p(\widehat{\boldsymbol\theta}_K)-F_p(\mathbf0)] \ge\frac p2(1-p)^K.$$ For each horizon $K\ge1$, choosing $p=1/(K+1)$ yields $$\mathbb E[F_p(\widehat{\boldsymbol\theta}_K)-F_p(\mathbf0)] \ge\frac1{2(K+1)}\left(\frac K{K+1}\right)^K \ge\frac1{2e(K+1)}.$$ Thus, even arbitrary adaptive step-size tuning cannot give SHB a uniformly faster worst-case order over this smooth convex problem class. Momentum-free PS already admits a matching $\mathcal O(1/K)$ guarantee for averaged iterates. Therefore, under the general assumptions considered in this paper, adding momentum cannot uniformly improve the worst-case convergence order over the momentum-free counterpart. ##
AuthorsOpenReview ↗

Response to Reviewer auxf (Part 2/3)

2. Momentum-dependent step-size control is necessary in the worst case.

Beyond the convergence order discussed in Point 1 above, we also agree that the constants and residual-neighborhood bounds in our guarantees generally become less favorable as β\beta increases. This reflects the momentum-dependent step-size scaling (1−β)2(1-\sqrt{\beta})^2 in Eqs. (3) and (6), which enables our analysis to accommodate any fixed β∈[0,1)\beta\in[0,1), including large momentum. Such scaling 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−β)(1-\beta) is insufficient to guarantee convergence across the full momentum range with a fixed cc. Moreover, this example requires the total coefficient multiplying the Polyak ratio to be O((1−β)2)\mathcal O((1-\beta)^2), matching the asymptotic order of our scaling (1−β)2(1-\sqrt\beta)^2 as β↑1\beta\uparrow1.

In two-dimensional polar coordinates θ=(rcos⁡ϑ,rsin⁡ϑ)\boldsymbol\theta=(r\cos\vartheta,r\sin\vartheta), 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. This 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.
AuthorsOpenReview ↗

Response to Reviewer auxf (Part 3/3)

3. Our convergence guarantees remain valuable.

We note that convergence guarantees for momentum-free methods do not automatically extend to SHB. PS and ALS select step sizes using the current sample, while momentum couples the current iterate with historical gradients. Establishing the convergence results of these methods with momentum remains an important theoretical problem.

To address these difficulties introduced by momentum, one of our main technical contributions is two decoupling lemmas that isolate the historical dependence introduced by heavy-ball momentum. These lemmas then enable a unified convergence analysis of SHB with PS and ALS and establish convergence-rate guarantees in general stochastic settings. This addresses a theoretical difficulty that does not arise in momentum-free analyses and is not fully addressed by existing analyses of momentum methods.

In particular, SHB-PS is a reparameterization of the existing MomSPSmax⁡\mathrm{MomSPS}_{\max} family. Our contribution is to establish convergence guarantees for this family and our Armijo scheme under the general conditions, including removing the restrictions on β\beta and extending to non-convex settings. Besides, the original analysis of MomSPSmax⁡\mathrm{MomSPS}_{\max} likewise observes that its bound constants can worsen with momentum and theoretically favor β=0\beta=0.

4. Can heavy-ball momentum preserve acceleration in stochastic settings?

Momentum often accelerates optimization empirically, but turning these observations into rigorous guarantees typically requires additional conditions on the objective structure, noise, or sampling scheme. Under the general assumptions considered in this paper, however, momentum cannot be guaranteed to uniformly improve the worst-case convergence order. Recall the example in Point 1: even with smooth convex interpolating objectives and adaptive Polyak step sizes, SHB is subject to an Ω(1/K)\Omega(1/K) worst-case expected objective lower bound, matching the O(1/K)\mathcal O(1/K) order attained without momentum. Identifying the additional conditions under which momentum accelerates, and establishing the corresponding theory, is still a separate and important research question.

5. Definition of rr in Table 1

Thank you for pointing this out. The symbol rr denotes the geometric contraction factor in Theorem 1, defined in Eq. (19) of Section 3.2. Table 1 summarizes all the convergence guarantees in this paper without repeating the full expressions for the constants. We have briefly explained the meaning of rr in the caption and added an explicit reference to Sections 3 and 4 for the detailed notation.

We thank the reviewer again for the constructive comments. We have uploaded the revised PDF, incorporating the counterexamples, additional discussions, and clarifications of the notation.


[Kidambi et al.] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M. Kakade. On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization. ICLR, 2018

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.