Pith. sign in

REVIEW 3 major objections 3 minor 2 cited by

The Fastest Known First-Order Method for Minimizing Twice Continuously Differentiable Smooth Strongly Convex Functions

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

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

Pith's one-line read C2M is a globally convergent first-order method that reduces the worst-case iteration count for twice differentiable smooth strongly convex problems to $(\sqrt{\kappa}/\sqrt{2})\log(1/\epsilon)$, a factor $\sqrt{2}$ better than Triple…

desk verdict A plausible sqrt(2) speedup over Triple Momentum on twice-differentiable strongly convex functions, but the global-convergence proof leans on unshown algebra that needs independent verification. read the letter →

arxiv 2506.01168 v1 pith:OIXJZCZI submitted 2025-06-01 math.OC cs.SYeess.SY

Bryan Van Scoy , Laurent Lessard This is my paper
classification math.OCcs.SYeess.SY MSC 90C2590C30
keywords C2-Momentumfirst-orderoptimizationstronglyconvexfunctionstwicecontinuouslydifferentiableworst-caseconvergencerateintegralquadraticconstraintsiterationcomplexity
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

This paper proposes C$^2$-Momentum (C2M), a first-order iterative algorithm for minimizing functions that are smooth, strongly convex, and twice continuously differentiable. The main claim is that C2M converges globally on this class and has a worst-case root-convergence factor $\rho$; for condition numbers $\kappa \ge 9+4\sqrt{5}$, the paper proves $\rho < 1 - \sqrt{2/\kappa}$, which yields an iteration complexity of roughly $(\sqrt{\kappa}/\sqrt{2})\log(1/\epsilon)$. That is a factor $\sqrt{2}$ faster than Triple Momentum, the previous fastest globally convergent method for the larger class of merely smooth strongly convex functions, and C2M costs the same per iteration. The extra assumption of bounded second derivatives is therefore not idle regularity: it opens a provably faster convergence regime, and the exact minimax rate for this smoother class remains open.

What carries the argument

The argument is carried by representing the two-point momentum iteration (2) as a linear time-invariant system with scalar transfer function $g(z) = -\alpha((1+\eta)z-\eta)/((z-1)(z-\beta))$ in feedback with the gradient. The C2M parameters are the unique solution to three root-locus equations: the closed-loop root locus of $1 - q g(z)$ has a double root at $z=\rho$ when $q=m$ and a root at $z=-\rho$ when $q=L$, which keeps the worst-case local eigenvalues inside the $\rho$-disk. Global convergence is certified by the frequency-domain inequality (11) with multiplier $h(z)=z^{-1}$; substituting the C2M parameters reduces it to checking that the polynomial $p(\kappa,\rho)$ is negative on an interval, and Lemma 1 locates the root of this polynomial. The local convergence statement is then completed by a discrete-time stability test applied to the closed-loop characteristic polynomial.

What would settle it

Using exact computer algebra for a fixed large condition number such as $\kappa=10^3$, recompute the real-root-counting sign changes asserted in Lemma 1 and verify that (11) with $h(z)=z^{-1}$ implies (12) for all $z$ on the unit circle; alternatively, run C2M on the paper's worst-case test function and search over initializations for an observed root-convergence factor larger than $\rho$.

Watch

Extended reading notes

Core claim

The paper's central discovery is Theorem 1: on the class $S^2_{m,L}$ of twice continuously differentiable functions whose Hessians satisfy $m I \preceq \nabla^2 f(x) \preceq L I$, the C2M algorithm with parameters given by (5) and $\rho$ chosen by (6) has worst-case root-convergence factor at most $\rho$. For $\kappa < 9+4\sqrt{5}$, C2M coincides with the Heavy Ball method and attains the quadratic minimax rate $(\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$. For larger condition numbers, $\rho$ is chosen just above the smallest positive root of the degree-7 polynomial $p(\kappa,\rho)$ in (7), and the paper shows $\rho_{C2M} < 1-\sqrt{2/\kappa}$, so C2M is strictly faster than Triple Momentum's $1-1/\sqrt{\kappa}$ in the worst case. The proof establishes global convergence by verifying a frequency-domain inequality obtained from integral quadratic constraints, and establishes the local rate by linearizing the iteration around the minimizer and applying a discrete-time stability criterion.

Load-bearing premise

The global-convergence claim rests on the assertion that the complicated frequency-domain inequality (11) can be reduced, without error, to the polynomial sign condition controlled by $p(\kappa,\rho)$; the paper states this reduction and the needed root counts rather than displaying them, so if either algebraic step is wrong, C2M is only known to converge locally.

Editorial extensions

If this is right

  • For every function in $S^2_{m,L}$, C2M converges from any initialization, whereas Heavy Ball is only locally convergent on this class.
  • Asymptotically, C2M reaches $\epsilon$-accuracy in at most $(\sqrt{\kappa}/\sqrt{2})\log(1/\epsilon)$ iterations, a factor $\sqrt{2}$ improvement over Triple Momentum with the same per-iteration cost.
  • Below the condition-number threshold $9+4\sqrt{5}$, C2M reduces to Heavy Ball and inherits its optimal quadratic rate, so the method covers both regimes smoothly.
  • The class $S^2_{m,L}$ includes regularized logistic loss, bounded-parameter exponential family negative log-likelihoods, and Moreau-envelope smoothings, so the speedup applies to common objectives.
  • Since the minimax rate for $S^2_{m,L}$ is unknown, C2M provides the current best upper bound and sharpens the open question of whether a faster method exists.

Reading between the lines

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

  • An extension the authors leave implicit is that the root-locus design rule--double root at the low-curvature end and single root at the high-curvature end--should transfer to any function class whose Hessian eigenvalues are known to lie in a fixed interval, as long as the corresponding frequency-domain inequality can be verified.
  • The $\sqrt{2}$ advantage is an asymptotic-in-$\kappa$ statement; at finite condition numbers, especially near $9+4\sqrt{5}$, the practical gap between C2M and Triple Momentum will be smaller and is worth measuring directly.
  • The proof pattern suggests a template for automated method design: choose a parameterized iteration, enforce root-locus conditions, and certify global convergence by symbolic reduction of the frequency-domain inequality to a polynomial sign condition.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper proposes C2-Momentum (C2M), a three-parameter momentum method of the form (2), for minimizing smooth strongly convex functions that are twice continuously differentiable. The main result, Theorem 1, gives an upper bound of ρ on the worst-case root-convergence factor over the class S^2_{m,L}; for κ ≥ 9+4√5, ρ can be chosen just above the smallest positive root ρ_C2M of the degree-7 polynomial (7), which satisfies ρ_C2M < 1−√(2/κ). This corresponds to an iteration complexity with leading term √(κ/2) log(1/ε), a factor √2 better than the Triple Momentum rate on S^1_{m,L}. The proof combines a Zames–Falb IQC argument for global stability with a Jury-criterion analysis of the linearized dynamics for the local rate. A numerical example illustrates faster convergence than TM on a C^2 function.

Significance. If fully verified, the result is a clean and meaningful contribution: it shows that the additional C^2 assumption on the objective permits a provable strict improvement over the minimax-optimal rate for S^1_{m,L} without changing the per-iteration cost. The algorithm is simple, the IQC-plus-linearization proof architecture is appropriate, and the paper is appropriately cautious in stating that no lower bound for S^2_{m,L} is known. The main weakness is that the proof currently depends on several large symbolic reductions that are asserted rather than displayed; these reductions are checkable and likely correct, but they must be made available for the theorem to be considered established.

major comments (3)
  1. [Section III-A, Eq. (12)] The proof of global stability for the fast regime rests on two algebraic assertions that are not demonstrated. After setting h(z)=z^{-1} and substituting the C2M parameters into the FDI (11), the text states that the FDI 'straightforwardly' reduces to the quadratic inequality (12), and then states that maximizing the right-hand side of (12) shows the inequality holds exactly when p(κ,ρ)<0. Neither the denominator-cleared expansion of the FDI nor the maximum-of-quadratic computation is displayed. Because a single sign or coefficient error in this reduction would destroy the global-convergence claim, and with it the distinction from locally convergent Heavy Ball, this step must be verifiable. Please provide the intermediate algebra or a machine-checked exact computation.
  2. [Appendix A, Lemma 1] Lemma 1 is load-bearing because it guarantees p(κ,ρ)<0 on the interval used in the FDI verification. Its proof applies Sturm's theorem but only states that the Sturm sequence has 5 sign changes at ρ=0 and 3 at ρ=1; the Sturm sequence itself, the resulting endpoint sign patterns, and the verification for all κ≥9+4√5 are omitted. This is not a routine bookkeeping detail: the polynomial coefficients depend on κ, and the threshold κ≥9+4√5 is exactly where the sign behavior is being claimed. Please include the Sturm sequence and its sign table, or provide a reproducible exact algebra script.
  3. [Section III-B, Lemma 3 and Jury reduction] Lemma 3 is used to convert global convergence into the claimed worst-case root-convergence factor. The proof cites the linear convergence theorem as if it applies directly to the generated sequence, but that theorem is local to a neighborhood of the equilibrium; the proof should first invoke the already-established global convergence to ensure the sequence eventually enters such a neighborhood. In addition, after substituting the C2M parameters, the four Jury inequalities are asserted to reduce to (√κ−1)/(√κ+1) ≤ ρ ≤ (κ−1)/(κ+1) with no derivation. Both steps are needed for the conclusion that the worst-case root factor is ρ.
minor comments (3)
  1. [Section III-C] The asymptotic expansion bounds for ρ_C2M are stated without derivation; since they are used only for the leading iteration-complexity constant, a brief derivation or a supporting reference would make the paper self-contained.
  2. [Section IV] The numerical experiment does not report the value of ε used for ρ = ρ_C2M + ε; adding this value would make the simulation reproducible.
  3. [Section II-B] The sentence 'we in general want to pick ρ as small as possible' could be made precise by stating in Theorem 1 that the rate bound is valid for every ρ in (6), with the fastest choice being the limit ρ↓ρ_C2M.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the C2M rate is a design parameter whose global-stability and local-rate properties are proved independently; the unshown algebraic reductions are omissions, not circular steps.

full rationale

The claimed derivation chain is not circular. Definition 1 introduces C2M with a free parameter rho, and (6) selects rho based on kappa. Theorem 1 then asserts an upper bound of rho, but the proof does not take rho as an externally observed rate and repackage it as a prediction. Instead, Section III proves two independent conditions: global asymptotic stability via the IQC/FDI verification in Proposition 3 and Section III-A, and a local spectral-radius bound via Lemma 3 and the Jury criterion in Section III-B. The rate rho is therefore an input design target whose feasibility is established by the proof, not a fitted quantity. The comparison with TM is an analytic consequence of the chosen interval rho <= 1 - sqrt(2/kappa), not a forced fit. The paper's self-citations, notably [3] for the IQC framework and [8] for TM, provide standard published tools and baseline results with independent external support; they are not used as an unverified uniqueness theorem to forbid alternatives. The skeptical concern about the reductions from FDI (11) to the quadratic (12) and about Lemma 1's Sturm sign counts is an omission of computational detail, which affects verifiability and correctness risk, but not circularity: those steps are algebraic consequences of the stated polynomials and the external Sturm theorem, not restatements of the theorem being proved. The root-locus discussion in Section II-D is explicitly labeled as intuition, with the rigorous Jury verification following in Section III-B. No equation is defined in terms of the theorem's conclusion, and no fitted parameter is renamed as a prediction. Therefore the paper is self-contained against external benchmarks for the purpose of circularity analysis, and the appropriate finding is no circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The proof relies on standard results from control (IQC stability theorems, Zames-Falb multipliers), standard numerical analysis (Ortega-Rheinboldt), and real algebraic geometry (Sturm's theorem). These are accepted external facts. The only hand-chosen object is the rate parameter rho, which is fixed by a root condition rather than fitted to measurements. No new entities are postulated. The omitted algebraic steps, not the ledger entries, are the main trust burden.

free parameters (1)
  • rho (worst-case rate / momentum parameter) = smallest positive root of p(kappa,rho) in ((sqrt(kappa)-1)/(sqrt(kappa)+1), 1-sqrt(2/kappa))
    rho parameterizes alpha, beta, eta via (5) and is chosen to make the root locus pass through +/-rho and the FDI (12) hold. It is a design parameter, not fitted to data, but it is a hand-chosen parameter that the central rate claim depends on.
assumptions (5)
  • standard math Discrete-time IQC stability theorem of Fetzer and Scherer [17, Thm. 2] and O'Shea-Zames-Falb IQC characterization of gradients [1,2,6,7]
    Invoked in Proposition 2 and Proposition 1 to reduce global stability to a frequency-domain inequality. These are published external results assumed as background.
  • standard math Linear convergence theorem of Ortega and Rheinboldt [15, Thm. 10.1.4] relating root-convergence factor to the spectral radius of the linearization
    Used in Lemma 3 to reduce worst-case rate on S^2 to the maximum spectral radius of A+qBC over q in [m,L].
  • standard math Sturm's theorem for real root counting [22, Thm. 2.62]
    Used in Lemma 1 to prove the polynomial p(kappa,rho) has a root in the required interval. The theorem is standard, but the sign-change counts are asserted without showing the Sturm sequence.
  • domain assumption For f in C^2, m-strong convexity and L-smoothness imply mI <= grad^2 f <= LI
    This characterizes the class S^2_{m,L} and is used to justify the interval [m,L] for the Hessian eigenvalues in the root locus and Lemma 3. It is a standard fact.
  • domain assumption The gradient operator of any f in S^1_{m,L} satisfies the Zames-Falb IQC with a causal multiplier h having nonnegative impulse response with l1 norm at most one
    Invoked via Proposition 1 to justify the FDI approach. The specific multiplier h(z)=z^{-1} is chosen and must satisfy these conditions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Fastest Known First-Order Method for Minimizing Twice Continuously Differentiable Smooth Strongly Convex Functions." pith.science (2026). https://pith.science/paper/OIXJZCZI

@misc{pith2026250601168,
  author       = {Pith},
  title        = {Pith review of: The Fastest Known First-Order Method for Minimizing Twice Continuously Differentiable Smooth Strongly Convex Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OIXJZCZI}},
  note         = {Machine review of arXiv:2506.01168}
}
abstract

We consider iterative gradient-based optimization algorithms applied to functions that are smooth and strongly convex. The fastest globally convergent algorithm for this class of functions is the Triple Momentum (TM) method. We show that if the objective function is also twice continuously differentiable, a new, faster algorithm emerges, which we call $C^2$-Momentum (C2M). We prove that C2M is globally convergent and that its worst-case convergence rate is strictly faster than that of TM, with no additional computational cost. We validate our theoretical findings with numerical examples, demonstrating that C2M outperforms TM when the objective function is twice continuously differentiable.

Figures

Figures reproduced from arXiv: 2506.01168 by the authors.

Figure 1
Figure 1. Venn diagram of different function classes. Blue region: strongly convex functions. Red region: twice continuously differentiable functions. This letter focuses on the shaded intersection of these sets, S2m,L. The class Fm,L consists of continuously differentiable func￾tions with sector-bounded gradients. Specifically, there exists x⋆ ∈ R d (the optimal point) and constants 0 < m ≤ L such that L(x − x⋆) − ∇f(x) T ∇… view at source ↗
Figure 2
Figure 2. Root locus of C2M. The locus has a double root at z = ρ at gain m and a single root at z = −ρ at gain L. have a positive root, and (ii) provides bounds on this root that will be used in the analysis. The proof is in Appendix A. Lemma 1: Suppose κ ≥ 9 + 4√ 5. The polynomial p(κ, ρ) defined in (7) has exactly one real root ρC2M in the open interval  √ κ−1 √ κ+1 , 1 − q 2 κ  . Moreover, ρC2M is the smallest positive … view at source ↗
Figure 3
Figure 3. Iteration complexity of several iterative methods applied to S2m,L. The proposed C2M method outperforms TM [8], which is min￾imax optimal on S1m,L, by exploiting a faster local convergence rate. Similarly, GAG [14] outperforms GD, which is minimax optimal on Fm,L. IV. NUMERICAL VALIDATION We simulate our proposed algorithm C2M along with sev￾eral other first-order methods on a function chosen to showcase worst-case … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Simulation results for a function f ∈ S2m,L (see Section IV). Solid lines are simulation results for the specified method; black lines are minimax rates for different function classes (see Table I); the dotted purple line is our theoretical upper bound (worst-case) rat…

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. HNAG$^{++}$: An Accelerated Gradient Method with a Refined Asymptotic Rate for Strongly Convex Optimization

    math.OC 2025-10 conditional novelty 7.0 of 10

    A Lyapunov/ODE-based analysis yields HNAG+ (rate 1-2/√κ) and HNAG++ (asymptotic rate 1-2√(2/κ) under Hölder Hessians).

  2. Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

    eess.SY 2025-08 conditional novelty 6.0 of 10

    All regular linearly convergent algorithms to a fixed point set can be written as a baseline optimizer plus an exponentially decaying learned perturbation, and any such perturbation preserves linear convergence.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages · cited by 2 Pith papers

  1. [1]

    On the oracle complexity of smooth strongly convex minimization,

    Y . Drori and A. Taylor, “On the oracle complexity of smooth strongly convex minimization,” J. Complexity, vol. 68, p. 101590, 2022

    work page 2022

  2. [2]

    Smooth strongly convex interpolation and exact worst-case performance of first-order methods,

    A. B. Taylor, J. M. Hendrickx, and F. Glineur, “Smooth strongly convex interpolation and exact worst-case performance of first-order methods,” Math. Program., vol. 161, pp. 307–345, 2017

    work page 2017

  3. [3]

    Analysis and design of opti- mization algorithms via integral quadratic constraints,

    L. Lessard, B. Recht, and A. Packard, “Analysis and design of opti- mization algorithms via integral quadratic constraints,” SIAM J. Optim., vol. 26, no. 1, pp. 57–95, 2016

    work page 2016

  4. [4]

    The analysis of optimization algorithms: A dissipativity approach,

    L. Lessard, “The analysis of optimization algorithms: A dissipativity approach,” IEEE Control Syst. Mag. , vol. 42, no. 3, pp. 58–72, Jun. 2022

    work page 2022

  5. [5]

    Robust and structure exploiting optimisation algorithms: An integral quadratic constraint approach,

    S. Michalowsky, C. Scherer, and C. Ebenbauer, “Robust and structure exploiting optimisation algorithms: An integral quadratic constraint approach,” Int. J. Control , vol. 94, no. 11, pp. 2956–2979, 2021

    work page 2021

  6. [6]

    Convex synthesis of accelerated gradient algorithms,

    C. Scherer and C. Ebenbauer, “Convex synthesis of accelerated gradient algorithms,” SIAM J. Control Optim. , vol. 59, no. 6, pp. 4615–4645, 2021

    work page 2021

  7. [7]

    Direct synthesis of iterative algorithms with bounds on achievable worst-case convergence rate,

    L. Lessard and P. Seiler, “Direct synthesis of iterative algorithms with bounds on achievable worst-case convergence rate,” in Proc. Amer. Control Conf., Jul. 2020, pp. 119–125

    work page 2020

  8. [8]

    The fastest known globally convergent first-order method for minimizing strongly convex functions,

    B. Van Scoy, R. A. Freeman, and K. M. Lynch, “The fastest known globally convergent first-order method for minimizing strongly convex functions,” IEEE Control Syst. Lett. , vol. 2, no. 1, pp. 49–54, 2017

    work page 2017

Show all 22 references
  1. [9]

    An optimal gradient method for smooth strongly convex minimization,

    A. Taylor and Y . Drori, “An optimal gradient method for smooth strongly convex minimization,” Math. Program., vol. 199, no. 1, pp. 557–594, 2023

    2023

  2. [10]

    Information-based complexity of linear operator equations,

    A. S. Nemirovsky, “Information-based complexity of linear operator equations,” J. Complexity, vol. 8, no. 2, pp. 153–175, 1992

    1992

  3. [11]

    Nesterov, Lectures on convex optimization

    Y . Nesterov, Lectures on convex optimization. Springer, 2018, vol. 137

    2018

  4. [12]

    Some methods of speeding up the convergence of iteration methods,

    B. T. Polyak, “Some methods of speeding up the convergence of iteration methods,” USSR Comput. Math. Math. Phys. , vol. 4, no. 5, pp. 1–17, 1964

    1964

  5. [13]

    Global convergence and asymptotic optimality of the heavy ball method for a class of nonconvex optimization problems,

    V . Ugrinovskii, I. Petersen, and I. Shames, “Global convergence and asymptotic optimality of the heavy ball method for a class of nonconvex optimization problems,” IEEE Control Syst. Lett., vol. 6, pp. 2449–2454, 2022

    2022

  6. [14]

    A generalized accelerated gradient optimization method,

    A. X. Wu, I. R. Petersen, V . Ugrinovskii, and I. Shames, “A generalized accelerated gradient optimization method,” in Proc. Amer. Control Conf., 2024, pp. 1904–1908

    2024

  7. [15]

    Ortega and W

    J. Ortega and W. Rheinboldt, Iterative solution of nonlinear equations in several variables . Academic Press, 1970

    1970

  8. [16]

    System analysis via integral quadratic constraints,

    A. Megretski and A. Rantzer, “System analysis via integral quadratic constraints,” IEEE Trans. Autom. Control , vol. 42, no. 6, pp. 819–830, 1997

    1997

  9. [17]

    Absolute stability analysis of discrete time feedback interconnections,

    M. Fetzer and C. W. Scherer, “Absolute stability analysis of discrete time feedback interconnections,” IFAC-PapersOnLine, vol. 50, no. 1, pp. 8447–8453, 2017

    2017

  10. [18]

    Zames–Falb multipliers for quadratic program- ming,

    W. Heath and A. Wills, “Zames–Falb multipliers for quadratic program- ming,” in Proc. IEEE Conf. Decis. Control , 2005, pp. 963–968

    2005

  11. [19]

    H. K. Khalil, Nonlinear systems . Upper Saddle River, N.J.: Prentice Hall, 2002

    2002

  12. [20]

    Tradeoffs between convergence rate and noise amplification for momentum- based accelerated optimization algorithms,

    H. Mohammadi, M. Razaviyayn, and M. R. Jovanovi ´c, “Tradeoffs between convergence rate and noise amplification for momentum- based accelerated optimization algorithms,”IEEE Trans. Autom. Control, vol. 70, no. 2, pp. 889–904, 2025

    2025

  13. [21]

    Fadali and A

    M. Fadali and A. Visioli, Digital Control Engineering: Analysis and Design. Academic Press, 2009

    2009

  14. [22]

    S. Basu, R. Pollack, and M. Coste-Roy, Algorithms in Real Algebraic Geometry, ser. Algorithms Comput. Math. Springer, 2007

    2007

Pith tools

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