Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Efficient globalization of heavy-ball type methods for unconstrained optimization based on curve searches

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Curve-search backtracking globalizes heavy-ball methods without discarding their momentum steps.

desk verdict Solid general curve-search framework with a genuinely new nonmonotone convergence result; the advertised optimal heavy-ball complexity rests on an assumption the paper never proves for the heavy-ball direction. read the letter →

arxiv 2505.19705 v1 pith:EBHJHECL submitted 2025-05-26 math.OC

Federica Donnini , Matteo Lapucci , Pierluigi Mansueto This is my paper · ORCID
classification math.OC MSC 90C2690C3065Y20
keywords curvesearchheavy-ballmethodglobalconvergencenonmonotoneArmijoconditionworst-casecomplexitynonconvexoptimizationmomentummethodsparaboliccurves
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper addresses the unconstrained minimization of a smooth function by iterative methods whose tentative update may not be a descent direction, notably Polyak's heavy-ball step. Its proposal is to globalize such methods with a curve search: evaluate the objective at the tentative heavy-ball point first, and only if the Armijo-type decrease condition fails, backtrack along a quadratic curve that bends smoothly back toward a gradient-related direction. The authors prove that this framework is globally convergent under mild assumptions, that the nonmonotone version also converges, and that for parabolic curves it reaches approximate stationarity in $O(\epsilon^{-2})$ evaluations in the nonconvex $L$-smooth case. The practical payoff claimed is that the curve search accepts pure heavy-ball steps in strongly convex problems instead of discarding them before evaluation, so the momentum acceleration is not lost.

What carries the argument

The machine is the two-direction quadratic search curve $\gamma(t;x,d,s)=x+td+t^2(s-d)$, read as a degree-2 Bézier curve with control points $x$, $x+\tfrac12 d$, and $x+s$. Its defining properties are that it starts at $x$, has initial velocity $d$, and ends at the tentative point $x+s$ at $t=1$, so the heavy-ball direction $s_k=-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1})$ is never preemptively altered: it is the first point evaluated, and backtracking along the curve smoothly blends the update back to the gradient direction $d_k$ when decrease fails. The argument is carried by the gradient-relatedness of the initial velocities, boundedness of the second directions, and a new smoothness estimate for the composed function $\phi_k(t)=f(\gamma_k(t))$, which yields a uniform lower bound on acceptable stepsizes.

What would settle it

Run the parabolic curve-search algorithm on an $L$-smooth nonconvex problem with a large fixed momentum coefficient and record, at each accepted iterate, whether $\|s_k\| \le c\|\nabla f(x_k)\|$ for a fixed $c$; if the inequality is violated infinitely often while the algorithm still finds approximate stationarity, then the stated complexity proof's hypothesis is not satisfied by the heavy-ball choice, and a separate argument would be needed.

Watch

Extended reading notes

Core claim

The central claim is that a heavy-ball type method can be globalized without ever discarding the momentum step when it is acceptable. The algorithm builds the quadratic curve $\gamma_k(t)=x_k+t d_k+t^2(s_k-d_k)$ with $d_k$ gradient-related and $s_k$ the heavy-ball direction; since $\gamma_k(1)=x_k+s_k$, the first point checked is exactly the pure heavy-ball update. If $f(x_k+s_k)$ satisfies the sufficient decrease condition, that step is accepted unchanged; otherwise a backtracking loop moves a smaller $t$ along the same curve, which reverts the motion toward the gradient-related initial direction. The authors prove that every accumulation point of the generated sequence is stationary, that a nonmonotone Armijo-type version still has a stationary accumulation point, and that under the bounded-direction assumption the parabolic case needs at most $O(\epsilon^{-2})$ function evaluations to reach $\|\nabla f(x_k)\|<\epsilon$.

Load-bearing premise

The load-bearing premise is Assumption 4: at every iteration both the search-direction size $\|d_k\|$ and the second-direction size $\|s_k\|$ must stay within a constant multiple of $\|\nabla f(x_k)\|$; for the heavy-ball direction this means the momentum term must not outgrow the gradient, which is not proved for general nonconvex problems.

Editorial extensions

If this is right

  • Any iterative method whose tentative direction sequence is bounded and whose curve initial velocities are gradient-related inherits global convergence from this curve-search rule.
  • The nonmonotone Armijo-type curve search—new in this paper—keeps a stationarity guarantee while allowing the objective to rise over short windows.
  • For parabolic curves satisfying the bounded-direction condition, reaching $\|\nabla f(x_k)\|<\epsilon$ costs at most $O(\epsilon^{-2})$ function evaluations, the optimal order for nonconvex smooth problems, and the same bound covers gradient evaluations when the gradient is computed only at current points.
  • In strongly convex problems with optimal heavy-ball parameters, the curve-search variants reproduce the pure heavy-ball trajectory rather than replacing it with a perturbed direction, so the fast linear rate is not sacrificed.
  • Numerical comparisons on nonconvex problems indicate the curve-search version is competitive with or better than restart-based and adaptive-momentum safeguards.

Reading between the lines

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

  • The authors do not draw this conclusion, but the optimal complexity bound rests on Assumption 4, which requires the momentum part $\beta(x_k-x_{k-1})$ to shrink at least as fast as the gradient; the paper does not prove this for general nonconvex heavy-ball runs, so the $O(\epsilon^{-2})$ guarantee should be read as conditional for the heavy-ball variant.
  • A testable extension not pursued in the paper is to make the curve's initial-velocity parameter, such as $g_f$, adaptive so that Assumption 4 can be enforced or cheaply verified at every iteration, potentially turning the conditional complexity result into an unconditional one.
  • By the same logic, the nonmonotone acceptance window may also apply to stochastic or inexact gradient settings, where the pure heavy-ball step is even more likely to fail a strict decrease test yet the curve can absorb the failure without abandoning momentum entirely.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. This paper proposes a curve-search globalization framework for unconstrained optimization, aimed primarily at Polyak's heavy-ball method. At each iteration, a tentative point x_k + s_k is tested through an Armijo-type search along a quadratic Bézier curve whose initial velocity is a gradient-related direction d_k; if the tentative step is not acceptable, the algorithm backtracks along the curve instead of discarding the momentum step outright. The authors prove convergence of the general framework under gradient-relatedness of d_k and boundedness of the auxiliary directions (Proposition 2), give a weaker convergence result for a nonmonotone Armijo rule (Proposition 4) and a stronger variant under an additional curve-displacement condition (Proposition 5), and then specialize to quadratic curves. Under Assumption 4, which bounds both d_k and s_k by a constant multiple of the gradient norm, they derive an O(ε^{-2}) worst-case complexity bound for reaching approximate stationarity (Propositions 6–8). Section 4 applies the framework to the heavy-ball direction s_k = -α∇f(x_k) + β(x_k - x_{k-1}), and Section 5 reports experiments on a strongly convex example and on CUTEst problems.

Significance. If the results hold as stated, the paper offers a genuinely useful way to globalize heavy-ball-type methods: pure momentum steps can be accepted when they decrease the objective, while the curve search provides a fallback to a gradient-related path. The general convergence proof (Proposition 2) is clean and is a parameter-free derivation from explicit assumptions, and the proposed nonmonotone curve-search convergence result appears to be new. The public code and the reproducible experimental setup are welcome strengths. The main caveat is that the advertised optimal complexity bound is not actually established for the heavy-ball method, because Assumption 4 is not verified for the momentum direction; the bound applies to the abstract parabolic-search framework only. In addition, the abstract's wording overstates the nonmonotone convergence result, which in Proposition 4 guarantees only the existence of a stationary accumulation point, not stationarity of every accumulation point.

major comments (2)
  1. [§3.1 (Assumption 4) and §4 (heavy-ball direction)] The O(ε^{-2}) complexity result of Proposition 8 is conditional on Assumption 4, but for the heavy-ball direction s_k = -α∇f(x_k) + β(x_k - x_{k-1}) introduced in Section 4, the required bound ‖s_k‖ ≤ c‖∇f(x_k)‖ is never established. This condition entails, in particular, that the past displacement ‖x_k - x_{k-1}‖ must shrink at least proportionally to the current gradient norm; compactness of the level set gives only a uniform bound on displacements, and neither the Armijo condition nor the curve-search backtracking rule forces such proportionality. For example, with f(x,y) = x^2/2, α = β = 1, x_0 = (ε, M), x_{-1} = (ε, 0), the unit heavy-ball step is Armijo-accepted, but ‖s_0‖/‖∇f(x_0)‖ ≈ M/ε is unbounded as M/ε grows. Consequently, the constant Δ_low in Proposition 7 and the constant interval of acceptable stepsizes in Proposition 8 may collapse, and the advertised optimal complexity bound for the heavy-ball variant is unsupported. The theorem should be stated only for the abstract parabolic-search framework satisfying Assumption 4, or Assumption 4 must be proved for a modified heavy-ball direction and the consequences for acceptance of pure momentum steps clarified.
  2. [Abstract and §2.2.1 (Proposition 4)] The abstract and the introduction claim “global convergence guarantees, even with a nonmonotone decrease condition.” Proposition 4, however, proves only that the sequence of iterates has at least one stationary accumulation point; the stronger conclusion that every accumulation point is stationary requires the additional curve-displacement forcing-function condition in Proposition 5. Since “global convergence” in the optimization literature normally means convergence of every accumulation point to stationarity, the advertised claim overstates Proposition 4. Please rephrase the nonmonotone claim as weak global convergence (existence of a stationary accumulation point), or present Proposition 5 as the main nonmonotone convergence theorem.
minor comments (5)
  1. [§1, Introduction] The word “nomonotone” appears in the sentence “the convergence result for a nomonotone curve search approach”; it should be “nonmonotone.”
  2. [§2.2.1, proof of Proposition 4] The phrase “all limit points of {x_{l(k)-1}}_K are stationary” is confusing because K was introduced as a specific subsequence in a contradiction argument; the argument actually applies to an arbitrary accumulation point of {x_{l(k)-1}}, so the wording should be adjusted accordingly.
  3. [§5, Computational experiments] The experimental parameter g_f (the scaling of the initial curve velocity) is not connected to any theoretical quantity. Please state explicitly that g_f is a fixed algorithmic parameter used in the experiments and that no proof depends on its value.
  4. [§5, stopping criterion] The stopping criterion uses the infinity norm ‖∇f(x_k)‖_∞ while the theoretical results use the Euclidean norm; this is standard in practice but should be stated so readers do not expect the same constants.
  5. [§3, Remark 4] The claim that the complexity bound is “optimal” would benefit from a reference to the known lower bound for first-order methods on nonconvex problems, or a sentence clarifying in which sense optimality is meant.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the convergence and complexity theorems are conditional derivations from stated assumptions; the unverified heavy-ball Assumption 4 is a correctness gap, not circularity.

full rationale

The paper's derivation chain is as follows: the Armijo-type curve search (Algorithm 1) is shown to terminate under Assumption 1; global convergence (Propositions 2 and 4) follows from the gradient-relatedness of the initial velocities and boundedness of the auxiliary directions; the complexity result (Proposition 8) follows from the L-smoothness of the objective and Assumption 4, which gives a uniform stepsize interval. These are all conditional theorems proved from explicitly stated hypotheses. No parameter is fitted to data and then renamed as a prediction, no result is imported from the authors' own prior work in a load-bearing way, and no quantity is defined in terms of the quantity it is supposed to establish. The numerical parameters (gf = 0.125, α = 1, β = 0.9, etc.) are tuned in unreported preliminary experiments, but they enter only the experiments, not the convergence or complexity proofs, so this is not a fitted-input-called-prediction issue. The only in-scope weakness is that for the heavy-ball direction sk = −α∇f(xk) + β(xk − xk−1), the paper never verifies Assumption 4 (∥sk∥ ≤ c∥∇f(xk)∥) or Assumption 3 (boundedness of the momentum terms), so the O(ε−2) complexity bound is not actually established for the advertised heavy-ball variant; that is a correctness/completeness gap, not a circular reduction, because Proposition 8 does not assume its conclusion and the proof does not rely on the heavy-ball update. The one self-citation ([15]) is used only as a pointer to related work and is not load-bearing. Therefore the paper is self-contained against its stated assumptions and no circular step can be exhibited.

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

The theoretical claims rest on standard smoothness and compactness assumptions, plus two structural assumptions on the search curves (gradient-relatedness and boundedness of the second direction). The optimal complexity result adds Assumption 4, which is the least justified for the heavy-ball application. No data were fitted to obtain the theorems; the experimental parameters are hand-tuned and reported without tuning details.

free parameters (4)
  • alpha (heavy-ball step size) = 1
    Fixed in experiments after unreported tuning; not used in theoretical proofs.
  • beta (momentum weight) = 0.9
    Fixed in experiments after unreported tuning; not used in theoretical proofs.
  • g_f (initial velocity scale) = 0.125
    Controls magnitude of the gradient-related direction d_k in experiments; tuned, not used in theory.
  • sigma, delta, Delta0 (search parameters) = sigma=1e-7, delta=0.5, Delta0=1
    Search hyperparameters set by tuning; theoretical proofs allow any sigma in (0,1), delta in (0,1), Delta0 in (0,1].
assumptions (6)
  • domain assumption f is continuously differentiable and L-smooth (gradient Lipschitz) for complexity results
    Used throughout; stated in Section 1 and Section 3 before Proposition 6.
  • domain assumption Level set L0 = {x | f(x) <= f(x0)} is compact (Assumption 2)
    Ensures bounded iterates and convergence of subsequences; stated before Proposition 2.
  • domain assumption The sequence of search directions d_k is gradient-related to {x_k}
    Definition 2; required for the Armijo-based decrease proof.
  • domain assumption The sequence of second directions xi_k is bounded (Assumption 3)
    Needed to extract convergent subsequence of curves; for heavy-ball follows from compact level set since iterates stay in L0.
  • ad hoc to paper The second direction satisfies ||s_k|| <= c||grad f(x_k)|| (Assumption 4)
    Introduced specifically to obtain the O(epsilon^{-2}) complexity bound; not verified for heavy-ball direction in nonconvex settings.
  • standard math Mean Value Theorem and standard descent lemma for smooth functions
    Used in proofs of Propositions 2, 6, and 7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient globalization of heavy-ball type methods for unconstrained optimization based on curve searches." pith.science (2026). https://pith.science/paper/EBHJHECL

@misc{pith2026250519705,
  author       = {Pith},
  title        = {Pith review of: Efficient globalization of heavy-ball type methods for unconstrained optimization based on curve searches},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBHJHECL}},
  note         = {Machine review of arXiv:2505.19705}
}
read the original abstract

In this work, we deal with unconstrained nonlinear optimization problems. Specifically, we are interested in methods carrying out updates possibly along directions not of descent, like Polyak's heavy-ball algorithm. Instead of enforcing convergence properties through line searches and modifications of search direction when suitable safeguards are not satisfied, we propose a strategy based on searches along curve paths: a curve search starting from the first tentative update allows to smoothly revert towards a gradient-related direction if a sufficient decrease condition is not met. The resulting algorithm provably possesses global convergence guarantees, even with a nonmonotone decrease condition. While the presented framework is rather general, particularly of interest is the case of parabolic searches; in this case, under reasonable assumptions, the resulting algorithm can be shown to possess optimal worst case complexity bounds for reaching approximate stationarity in nonconvex settings. Practically, we show that the proposed globalization strategy allows to consistently accept (optimal) pure heavy-ball steps in the strongly convex case, while standard globalization approaches would at times negate them before even evaluating the objective function. Preliminary computational experiments also suggest that the proposed framework might be more convenient than classical safeguard based approaches.

Figures

Figures reproduced from arXiv: 2505.19705 by the authors.

Figure 1
Figure 1. Quadratic search curve starting at x, ending at x + s and with initial velocity d. The points P0 = x, P1 = x + 1 2 d and P2 = x + s are the control points of Bézier’s expression of the curve. 3.1 Theoretical analysis We start the formal analysis showing that curves of the form (11) satisfy the assumptions of the more general case. Lemma 1. Curves of the form (11) satisfy Assumption 1. Proof. Continuity of γ(t; x, d,… view at source ↗
Figure 2
Figure 2. Plot of the distance between the current solution [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Performance profiles in terms of f ⋆ and T obtained by CS, GD, M_HB, M_RES and M_BETA on the CUTEst problems listed in [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 23 canonical work pages

  1. [1]

    Ben-Tal, A

    A. Ben-Tal, A. Melman, and J. Zowe. Curved search methods for unconstrained optimization. Optimization, 21(5):669–695, 1990

    work page 1990

  2. [2]

    D. P. Bertsekas. Nonlinear programming. Athena Scientific, Belmont, MA, 2 edition, 1999

    work page 1999

  3. [3]

    C. A. Botsaris. Differential gradient methods. Journal of Mathematical Analysis and Applications, 63(1):177–198, 1978

    work page 1978

  4. [4]

    Cartis, N

    C. Cartis, N. I. Gould, and P. L. Toint. Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. SIAM, 2022

    work page 2022

  5. [5]

    E. D. Dolan and J. J. Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201–213, 2002

    2002

  6. [6]

    C. Fan, S. Vaswani, C. Thrampoulidis, and M. Schmidt. MSL: An adaptive momentum-based stochastic line-search framework. In OPT 2023: Optimization for Machine Learning, 2023

    work page 2023

  7. [7]

    Farin and D

    G. Farin and D. Hansford. The essentials of CAGD. AK Peters/CRC Press, 2000

    work page 2000

  8. [8]

    Ghadimi, H

    E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson. Global convergence of the Heavy-Ball method for convex optimization. In 2015 European control conference (ECC), pages 310–315. IEEE, 2015

    work page 2015

Show all 26 references
  1. [9]

    Goldfarb

    D. Goldfarb. Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Mathematical programming, 18(1):31–40, 1980. 16 FEDERICA DONNINI , MATTEO LAPUCCI AND PIERLUIGI MANSUETO

    1980

  2. [10]

    N. I. Gould, S. Lucidi, M. Roma, and P. L. Toint. Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optimization methods and software, 14(1-2):75–98, 2000

    2000

  3. [11]

    N. I. Gould, D. Orban, and P. L. Toint. CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Computational Optimization and Applications, 60:545–557, 2015

    2015

  4. [12]

    Grippo, F

    L. Grippo, F. Lampariello, and S. Lucidi. A nonmonotone line search technique for newton’s method. SIAM journal on Numerical Analysis, 23(4):707–716, 1986

    1986

  5. [13]

    Grippo and M

    L. Grippo and M. Sciandrone. Introduction to methods for nonlinear optimization, volume 152. Springer Nature, 2023

    2023

  6. [14]

    Kassing and S

    S. Kassing and S. Weissmann. Polyak’s Heavy Ball method achieves accelerated local rate of convergence under Polyak-Lojasiewicz inequality. arXiv preprint arXiv:2410.16849, 2024

    2024

  7. [15]

    Lapucci, G

    M. Lapucci, G. Liuzzi, S. Lucidi, and M. Sciandrone. A globally convergent gradient method with momentum, 2024

    2024

  8. [16]

    Lee, P.-W

    C.-P. Lee, P.-W. Wang, W. Chen, and C.-J. Lin. Limited-memory Common-directions Method for Distributed Optimization and its Application on Empirical Risk Minimization, pages 732–740. SIAM, 2017

    2017

  9. [17]

    Lessard, B

    L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57–95, 2016

    2016

  10. [18]

    Z. Liu, Y . Ni, H. Liu, and W. Sun. A new subspace minimization conjugate gradient method for unconstrained minimization. Journal of Optimization Theory and Applications, 200(2):820–851, Feb 2024

    2024

  11. [19]

    B. T. Polyak. Some methods of speeding up the convergence of iteration methods.Ussr computational mathematics and mathematical physics, 4(5):1–17, 1964

    1964

  12. [20]

    B. T. Polyak. Introduction to optimization. New York, Optimization Software„ 1987

    1987

  13. [21]

    M. J. D. Powell. Restart procedures for the conjugate gradient method. Mathematical Programming, 12(1):241– 254, Dec 1977

    1977

  14. [22]

    Saab Jr, S

    S. Saab Jr, S. Phoha, M. Zhu, and A. Ray. An adaptive Polyak Heavy-Ball method. Machine Learning, 111(9):3245–3277, 2022

    2022

  15. [23]

    Shi and J

    Z.-J. Shi and J. Shen. A new descent algorithm with curve search rule. Applied mathematics and computation, 161(3):753–768, 2005

    2005

  16. [24]

    Tang, K.-C

    T. Tang, K.-C. Toh, N. Xiao, and Y . Ye. A Riemannian dimension-reduced second-order method with application in sensor network localization. SIAM Journal on Scientific Computing, 46(3):A2025–A2046, 2024

    2024

  17. [25]

    Z. Xu, Y . Tang, Z.-J. Shi, et al. Global convergence of curve search methods for unconstrained optimization. Applied Mathematics, 7(07):721, 2016

    2016

  18. [26]

    Zhang, D

    C. Zhang, D. Ge, C. He, B. Jiang, Y . Jiang, and Y . Ye. DRSOM: A dimension reduced second-order method, 2023. 17

    2023

Pith tools

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