A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization

Chuan He

REVIEW 2 major objections 3 minor 27 references

A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization

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

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

Pith's one-line read This paper proposes a stochastic first-order method whose multi-extrapolated momentum exploits Lipschitz continuity of the pth-order derivative of the objective, and proves a sample and first-order operation complexity of…

desk verdict The multi-extrapolated momentum idea is real and the main rate is proved properly, but the global L_p-Lipschitz assumption and the experimental reporting keep this at conditional rather than full accept. read the letter →

arxiv 2412.14488 v4 pith:QNWUMLWG submitted 2024-12-19 math.OC cs.AIcs.LG

Chuan He This is my paper · ORCID

classification math.OCcs.AIcs.LG MSC 49M0549M3790C2590C30

keywords stochasticfirst-ordermethodmulti-extrapolatedmomentumhigher-ordersmoothnesssamplecomplexitynonconvexoptimizationvariancereductionnormalizedgradientupdateVandermondesystem

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 asks whether a stochastic first-order method can use higher-order smoothness of the objective function to reduce the number of noisy gradient evaluations needed to reach an $\epsilon$-stationary point. It answers yes: for any $p\ge 2$, performing $p-1$ extrapolated gradient evaluations per iteration and combining them with a momentum update lets the method cancel Taylor expansion terms through order $p$, shrinking the gradient-estimation error faster than prior first-order methods. Under standard unbiased-gradient and bounded-variance assumptions plus a global Lipschitz bound on the $p$th derivative, the method reaches $\mathbb{E}[\|\nabla f(x)\|]\le\epsilon$ in $\tilde{O}(\epsilon^{-(3p+1)/p})$ iterations and gradient evaluations. This improves the known $\epsilon^{-4}$ rate for gradient-Lipschitz objectives and the $\epsilon^{-7/2}$ rate for Hessian-Lipschitz objectives, and it does not require the mean-squared smoothness condition on the stochastic estimator.

What carries the argument

The load-bearing object is the set of $p-1$ extrapolation points together with a Vandermonde linear system for the momentum weights $\{\theta_{k,t}\}$. The coefficient matrix has entries $1/\gamma_{k,t}^r$ for $r=1,\dots,p-1$ and right-hand side all ones; solving this system makes the weighted combination of Taylor expansions of $\nabla f$ at the extrapolated points cancel, term by term, the Taylor expansion of $\nabla f$ at $x_{k+1}$ through order $p-1$. Lemma 4 identifies the unique solution explicitly, records the alternating signs of the weights, and gives the sum used to tune the momentum decay; the residual after cancellation is bounded by $L_p\|x_{k+1}-x_k\|^p/p!$, producing the $\eta_k^{2p}$ term in the variance recurrence. This cancellation is what converts the objective's $p$th-order Lipschitz constant into faster decay of the gradient-estimation error inside the potential-function descent.

What would settle it

Run Algorithm 1 with $q=p-1$ on a one-dimensional polynomial $f(x)=x^{p+1}/(p+1)!$ (which has $L_p=1$ and all higher derivatives zero) with Gaussian additive noise, and measure the gradient-estimation error $\mathbb{E}[\|m_k-\nabla f(x_k)\|^2]$ along the run. The proof's recurrence (28) predicts this error contracts by the factor $1-\sum_t\theta_{k,t}$ plus an $\eta_k^{2p}$ term; if the measured decay follows $\eta_k^2$ instead of $\eta_k^{2p}$, the Taylor-cancellation identity is not doing the claimed work.

Watch

Extended reading notes

Core claim

The central discovery is that higher-order smoothness of $f$ can be converted into faster variance reduction in a stochastic first-order method. At each iteration, Algorithm 1 forms $q=p-1$ extrapolated points $z_{k,t}=x_k+\frac{1-\gamma_{k-1,t}}{\gamma_{k-1,t}}(x_k-x_{k-1})$ and evaluates the stochastic gradient at each; the momentum weights $\theta_{k,t}$ are chosen so that the weighted sum of Taylor expansions of $\nabla f$ at those points matches the Taylor expansion of $\nabla f$ at $x_{k+1}$ up to order $p-1$. Lemma 5 shows the remaining error in the estimator recurrence is proportional to $\eta_k^{2p}$ rather than $\eta_k^2$, so the variance-reduction recurrence damps estimation error at a much faster rate. With step sizes $\eta_k=(k+p)^{-(2p+1)/(3p+1)}$ and $\gamma_{k,t}=1/(t(k+p)^{2p/(3p+1)})$, Theorem 4 yields $\mathbb{E}[\|\nabla f(x_{\iota_K})\|]\le\epsilon$ after $K=\tilde{O}((M_p/\epsilon)^{(3p+1)/p})$, i.e. sample complexity $\tilde{O}(\epsilon^{-(3p+1)/p})$. This is the first stochastic first-order method whose acceleration comes from arbitrary-order smoothness of the objective rather than from mean-squared smoothness of the stochastic gradient estimator.

Load-bearing premise

The load-bearing premise is a global Lipschitz bound on the $p$th-order derivative of $f$: a single finite $L_p$ valid for all pairs $x,y$. If that bound is infinite, or holds only on a bounded region, the Taylor-cancellation argument that produces the faster variance-reduction recurrence no longer applies, and the stated rate is unsupported.

Editorial extensions

If this is right

For $p=2$, the rate reduces to $\tilde{O}(\epsilon^{-7/2})$, matching the best known Hessian-Lipschitz result, and for $p=3$ it gives $\tilde{O}(\epsilon^{-10/3})$.
As $p$ grows, $\tilde{O}(\epsilon^{-(3p+1)/p})$ approaches $\tilde{O}(\epsilon^{-3})$, the rate previously attainable only under mean-squared smoothness of the stochastic estimator.
The parameter schedules in Theorem 4 do not require explicit knowledge of $L_p$, $L_1$, or $\sigma$, making the method easier to tune than earlier Hessian-Lipschitz accelerations.
The total first-order operation complexity equals the sample complexity, because each iteration uses exactly $q=p-1$ stochastic gradient evaluations.

Reading between the lines

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

This suggests the Taylor-cancellation mechanism may generalize to proximal or composite stochastic optimization, potentially yielding rates near $\tilde{O}(\epsilon^{-3})$ under higher-order smoothness without mean-squared smoothness; the paper does not analyze that setting.
The alternating signs of the momentum weights connect the construction to finite-difference and Hermite interpolation formulas, so one testable extension is whether choosing extrapolation points as roots of orthogonal polynomials improves the hidden constants or removes logarithmic factors.
A restarted or high-probability variant of Algorithm 1 might also yield guarantees for second-order stationarity under Hessian or higher-order smoothness, although only first-order stationarity is proven here.

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.

Desk Editor's Note

read the letter

Side with the reader's conditional verdict. The central thing is real: this is the first stochastic first-order method I know that uses arbitrary-order smoothness of f, and the price is a family of sample complexities eO(epsilon^-(3p+1)/p) shrinking from epsilon^-4 toward epsilon^-3 as p grows. The Vandermonde-based multi-extrapolated momentum is a natural but genuinely new extension of the NIGT Hessian-Lipschitz trick, and the proof is properly done: the weights (34) solve the interpolation system (24), the error recurrence (28) and potential descent (31) close, and the parameter schedules are explicit analytic sequences rather than fitted to hit the rate. No circularity, no invented constants. I checked the algebra in the key substitutions and it holds up.

The soft spots, in order. First, Assumption 2 demands a global Lipschitz bound on the p-th derivative. The authors state it and use it consistently, so it is not a proof error, but it is the load-bearing premise; if it holds only locally, the Taylor cancellations in Lemma 1 fail and you are back to the gradient-Lipschitz rate. That limitation is structural and should be highlighted more prominently than it is. Second, the experiments are genuinely preliminary: no code, no seeds, no error bars, and the parameters are 'tuned' without saying how. The plots show the expected ordering but are not evidence beyond that. Third, the normalized update (15) is undefined when m_k = 0. This is likely measure zero under continuous noise and patchable anyway, but it should be acknowledged rather than left implicit. Fourth, there is a small typo: Theorem 4 writes 'forall k' in the K bound, and the proof's summation index slips between (73) and (75); cosmetic.

Overall, the theoretical contribution is meaningful, the proof appears sound, and the flaws are fixable. This deserves peer review, not desk rejection. I would send it to a referee who can check the recurrences carefully, with a request to tighten the experiments and address the m_k = 0 edge case. I would also ask the authors to discuss the globality of Assumption 2.

Referee Report

2 major / 3 minor

Summary. The paper studies unconstrained stochastic optimization of a function whose p-th derivative is Lipschitz continuous. It proposes Algorithm 1, an SFOM that performs q = p - 1 extrapolations per iteration and combines the associated stochastic gradients with a Polyak-type momentum update, followed by a normalized step. Under Assumptions 1 and 2, Theorem 4 claims a sample and first-order operation complexity of O-tilde(epsilon^{-(3p+1)/p}) for finding an epsilon-stochastic stationary point. The proof is organized around a Taylor-based bound on the gradient (Lemma 1), a variance-reduction recurrence for the momentum estimator (Lemma 5), and a potential-function descent (Theorem 3). The parameter schedules (33)-(34) are explicit analytic sequences, and the p = 2 case recovers the O(epsilon^{-7/2}) rate of Cutkosky and Mehta [6].

Significance. If the proof is correct, the paper delivers the first stochastic first-order method that accelerates via arbitrary-order smoothness of the objective, improving on the gradient-Lipschitz rate O(epsilon^{-4}) without imposing the mean-squared smoothness condition (5). The analysis is self-contained, the algorithm's parameters do not require knowledge of L_p, sigma, or the initial suboptimality, and the numerical experiments support the qualitative benefit of multi-extrapolation. The main caveat is the global L_p-Lipschitz assumption on D^p f, which is structural and cannot be verified from the stochastic gradient oracle; this limitation is clearly stated in Assumption 2.

major comments (2)

[Algorithm 1, Eq. (15)] The normalized update x_{k+1} = x_k - eta_k m_k / ||m_k|| is undefined when m_k = 0. The paper should specify a convention for this case (e.g., set x_{k+1} = x_k when m_k = 0) or explicitly exclude such realizations. The proofs currently use the equality ||x_{k+1} - x_k|| = eta_k from (15); with the convention the equality becomes an inequality, and the subsequent bounds remain valid. This is a formal gap that does not affect the asymptotic rate but must be fixed for the algorithm and theorems to be well-defined.
[Section 5.3, Lemma 10, Eq. (67)] The displayed chain in (67) containing '... <= 1 - 1/(k+p)^{2p/(3p+1)} + 1 <= 1 - 1/(2(k+p)^{2p/(3p+1)})' is invalid: the middle expression is greater than 1 for all admissible k and p, while the final bound is below 1, so the second inequality cannot hold as written. The claimed upper bound on the product is true, but it needs a correct proof, for instance via a binomial expansion or a Weierstrass product inequality; please replace the garbled middle term.

minor comments (3)

[Theorem 4, Eq. (35)] The quantifier in (35) reads 'for all k >= max{...}' but the left-hand side involves K; it should read 'for all K >= max{...}'.
[Section 4] In Sections 4.1 and 4.2, 'we stimulate the noisy gradient evaluations' should read 'we simulate the noisy gradient evaluations'.
[Figure 1] The contour plot in Fig. 1 is not reproducible from the text; consider adding the specific parameter values used to generate the visualization.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the sample-complexity bound is proved from the stated smoothness and noise assumptions via explicit recurrences, with no fitted parameters and no load-bearing self-citations.

full rationale

The derivation chain is self-contained. Lemma 1 derives bound (9) directly from Assumption 2 via Taylor's theorem with integral remainder. The recurrence (28) and the potential descent (31) follow by expanding mk+1 - grad f(xk+1), inserting the cancellation condition (24), applying (9) to each extrapolation point, and using Young's inequality and the variance bound (7). The parameter schedules (33)-(34) are explicit analytic sequences in k and p; they are chosen to make the summed potential inequality yield the averaged-gradient bound (75), and no constant is fitted to the target epsilon-rate. The complexity statement (35) is a consequence of Lemma 7 applied to (75), with the smoothness and noise constants entering only through the explicit constant Mp. The paper's own prior work cited as [13] and [14] concerns different constrained and augmented-Lagrangian settings and is not used to justify the main theorem or to forbid alternative algorithms. Assumption 2 is a genuine structural premise, not a restatement of the conclusion; the proof applies it at every iteration to the iterates and extrapolation points, whose locations are not bounded a priori. No equation reduces to the conclusion by definition, and no fitted parameter is renamed as a prediction. The minor edge case that the normalized update (15) is undefined when mk = 0 is a patchable technicality and is not a circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof relies on standard smoothness and noise assumptions rather than fitted numbers. The algorithm parameter sequences are explicit functions of k and p, and the constants L1, Lp, sigma enter only through the final bound M_p; no parameter is tuned to experimental data.

assumptions (3)

domain assumption Assumption 1(a)-(c): f is bounded below, grad f is L1-Lipschitz, and the stochastic gradient G is unbiased with bounded variance sigma^2.
Used throughout Lemma 2 and all recurrences; standard in stochastic first-order optimization.
domain assumption Assumption 2: D^p f is Lipschitz for some p >= 2 with constant L_p.
The entire acceleration mechanism relies on this; if only p=1 holds, the complexity degrades to O(epsilon^-4).
standard math Taylor's theorem with integral remainder and standard norm inequalities.
Used to derive Lemma 1 and the p-th order Taylor expansions in Lemmas 3 and 5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization." pith.science (2026). https://pith.science/paper/QNWUMLWG

@misc{pith2026241214488,
  author       = {Pith},
  title        = {Pith review of: A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QNWUMLWG}},
  note         = {Machine review of arXiv:2412.14488}
}

abstract

In this paper, we consider an unconstrained stochastic optimization problem where the objective function exhibits high-order smoothness. Specifically, we propose a new stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum update based on these extrapolations. We demonstrate that the proposed SFOM can accelerate optimization by exploiting the high-order smoothness of the objective function $f$. Assuming that the $p$th-order derivative of $f$ is Lipschitz continuous for some $p\ge2$, and under additional mild assumptions, we establish that our method achieves a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-(3p+1)/p})$ for finding a point $x$ such that $\mathbb{E}[\|\nabla f(x)\|]\le\epsilon$. To the best of our knowledge, this is the first SFOM to leverage arbitrary-order smoothness of the objective function for acceleration, resulting in a sample complexity that improves upon the best-known results without assuming the mean-squared smoothness condition. Preliminary numerical experiments validate the practical performance of our method and support our theoretical findings.

Figures

Figures reproduced from arXiv: 2412.14488 by the authors.

**Figure 1.** Visualization of the updates for {z k,t}1≤t≤3 (left) and mk (right) on a contour plot. Before proceeding, we present the following lemma regarding the descent relation of f on iterates generated by Algorithm 1. Its proof is deferred to Section 5.1. Lemma 2. Suppose that Assumptions 1 and 2 hold. Let {(x k , mk )}k≥0 be generated by Algorithm 1 with step sizes {ηk}k≥0. Then, f(x k+1) ≤ f(x k ) − ηk∥∇f(x k )∥ + 2ηk∥∇f… view at source ↗

**Figure 2.** Convergence behavior of the relative objective value for all SFOMs in solving problem ( [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Convergence behavior of the relative loss for all SFOMs in solving problem ( [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 20 canonical work pages

[6]

Cutkosky and H

A. Cutkosky and H. Mehta. Momentum improves normalized SGD. In International Conference on Machine Learning, pages 2260–2268, 2020

2020
[1]

Alacaoglu and S

A. Alacaoglu and S. J. Wright. Complexity of single loop algorithms for nonlinear programming with stochastic objective and constraints. In International Conference on Artificial Intelligence and Statistics, pages 4627–4635. PMLR, 2024

work page 2024
[2]

Arjevani, Y

Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023

2023
[3]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. 25

work page 2018
[4]

Convex until proven guilty

Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. “Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning, pages 654–663, 2017

work page 2017
[5]

F. E. Curtis and K. Scheinberg. Optimization methods for supervised machine learning: From linear models to deep learning. In Leading Developments from INFORMS Communities , pages 89–114. INFORMS, 2017

work page 2017
[7]

Cutkosky and F

A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems , volume 32, 2019

work page 2019
[8]

C. Fang, C. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems , volume 31, 2018

work page 2018

Show all 27 references

[9]

C. Fang, Z. Lin, and T. Zhang. Sharp analysis for nonconvex SGD escaping from saddle points. In Conference on Learning Theory, pages 1192–1234, 2019

2019
[10]

Y. Gao, A. Rodomanov, and S. U. Stich. Non-convex stochastic composite optimization with Polyak momentum. arXiv preprint arXiv:2403.02967 , 2024

2024 arXiv
[11]

Ghadimi and G

S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization , 23(4):2341–2368, 2013

2013
[12]

Ghadimi and G

S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59–99, 2016

2016
[13]

He and Z

C. He and Z. Deng. Stochastic interior-point methods for smooth conic optimization with applications. arXiv preprint arXiv:2412.12987 , 2024

2024
[14]

C. He, Z. Lu, and T. K. Pong. A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees. SIAM Journal on Optimization , 33(3):1734–1766, 2023

2023
[15]

R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge university press, 2012

2012
[16]

Huang, S

F. Huang, S. Chen, and H. Huang. Faster stochastic alternating direction method of multipliers for nonconvex optimization. In International Conference on Machine Learning , pages 2839–2848. PMLR, 2019

2019
[17]

Humpherys and T

J. Humpherys and T. J. Jarvis. Foundations of Applied Mathematics Volume 2: Algorithms, Approximation, Optimization. SIAM, 2020

2020
[18]

G. Lan. First-Order and Stochastic Optimization Methods for Machine Learning . Springer, 2020

2020
[19]

Z. Li, H. Bao, X. Zhang, and P. Richt´ arik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning , pages 6286–6295. PMLR, 2021. 26

2021
[20]

Li, P.-Y

Z. Li, P.-Y. Chen, S. Liu, S. Lu, and Y. Xu. Stochastic inexact augmented lagrangian method for nonconvex expectation constrained optimization. Computational Optimization and Applications , 87(1):117–147, 2024

2024
[21]

Z. Lu, S. Mei, and Y. Xiao. Variance-reduced first-order methods for deterministically con- strained stochastic nonconvex optimization with strong convergence guarantees. arXiv preprint arXiv:2409.09906, 2024

2024 arXiv
[22]

N. H. Pham, L. M. Nguyen, D. T. Phan, and Q. Tran-Dinh. ProxSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research , 21(110):1–48, 2020

2020
[23]

Q. Shi, X. Wang, and H. Wang. A momentum-based linearized augmented Lagrangian method for nonconvex constrained stochastic optimization. Mathematics of Operations Research, 2025

2025
[24]

Tran-Dinh, N

Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. A hybrid stochastic optimization framework for composite nonconvex optimization. Mathematical Programming, 191(2):1005–1071, 2022

2022
[25]

Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems , volume 32, 2019

2019
[26]

Xu and Y

Y. Xu and Y. Xu. Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization. Journal of Optimization Theory and Applications , 196(1):266–297, 2023

2023
[27]

Y. You, J. Li, S. Reddi, J. Hseu, S. Kumar, S. Bhojanapalli, X. Song, J. Demmel, K. Keutzer, and C.-J. Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In International Conference on Learning Representations , 2020. 27

2020

Pith tools

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

[1] [6]

Cutkosky and H

A. Cutkosky and H. Mehta. Momentum improves normalized SGD. In International Conference on Machine Learning, pages 2260–2268, 2020

2020

[2] [1]

Alacaoglu and S

A. Alacaoglu and S. J. Wright. Complexity of single loop algorithms for nonlinear programming with stochastic objective and constraints. In International Conference on Artificial Intelligence and Statistics, pages 4627–4635. PMLR, 2024

work page 2024

[3] [2]

Arjevani, Y

Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023

2023

[4] [3]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. 25

work page 2018

[5] [4]

Convex until proven guilty

Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. “Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning, pages 654–663, 2017

work page 2017

[6] [5]

F. E. Curtis and K. Scheinberg. Optimization methods for supervised machine learning: From linear models to deep learning. In Leading Developments from INFORMS Communities , pages 89–114. INFORMS, 2017

work page 2017

[7] [7]

Cutkosky and F

A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems , volume 32, 2019

work page 2019

[8] [8]

C. Fang, C. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems , volume 31, 2018

work page 2018