{"id":"ae43b38b-47ed-4f2b-9e58-50cb36527afc","arxiv_id":"2412.14488","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A multi-extrapolated momentum stochastic first-order method achieves O-tilde(epsilon^-(3p+1)/p) sample complexity for epsilon-stationarity when the objective's p-th derivative is Lipschitz.","lead":"This paper proposes a stochastic optimization method that looks at several nearby points at each step and combines them with carefully chosen weights. It proves that the smoother the objective function, the fewer noisy samples are needed to find a point with near-zero slope.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof of Theorem 4 is internally consistent and the stated O-tilde(epsilon^{-(3p+1)/p}) rate follows from the recurrences.","rationale":"The reader's weakest assumption—the global Lp-Lipschitz bound on D^p f—is exactly the condition that makes the acceleration possible, and I agree that it is structural and unverifiable from the oracle alone. But it is an explicit assumption of the theorem, not a hidden or inconsistent step. I traced the proof chain: Lemma 1 is a standard Taylor bound under Assumption 2; Lemma 5 uses (24) to cancel Taylor terms at x_{k+1} and each z_{k+1,t}, and the resulting recurrence (28) is algebraically sound; Theorem 3's potential descent follows from Young's inequality and the condition (30); Lemma 10's bounds on the parameter sums and theta_t are consistent with (33)-(34); and Theorem 4's final complexity count uses Lemma 7 correctly. The numerical experiments are preliminary and lack code, seeds, and error bars, but that does not affect the correctness of the theoretical result. The m_k = 0 edge case in (15) is a genuine but minor gap: the algorithm is undefined on that event, though it can be patched without altering the rate. Overall, the central claim holds under its stated assumptions, so the conditional verdict is unchanged.","tokens_in":27665,"tokens_out":31287,"duration_ms":246941,"concrete_test":"Symbolically or numerically verify the key recurrence (28) and the potential descent (31) for p = 3 and p = 4 using the exact schedules (33)-(34): confirm that the constants in (73) are valid and that the bound (64) on theta_k,t holds at representative k. Independently, run Algorithm 1 on a scalar polynomial with known Lp and check that the empirical average gradient norm decays as K^{-p/(3p+1)} (up to log factors) for p = 2, 3, 4; if the observed exponent deviates, the recurrence or parameter bounds are incorrect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing flaw found in the central claim. The theorem is explicitly conditional on Assumption 2, which requires a global Lp-Lipschitz bound on D^p f; this is indeed the structural premise that lets p-1 extrapolations cancel Taylor terms through Lemma 1's bound (9), and it cannot be verified from the stochastic gradient oracle alone. However, the assumption is stated and used consistently: the proof applies (9) at every iteration to the actual iterates and extrapolation points, whose locations are not a priori bounded. The variance recurrence (28), the potential descent (31), and the parameter bounds (63)-(64) are algebraically coherent with the choices (33)-(34), and the final complexity calculation K = O((M_p/epsilon)^((3p+1)/p) log(...)) is valid. The only technical gap is that the normalized update (15) is undefined when m_k = 0; this is a patchable edge case that does not change the asymptotic rate for continuous noise or generic discrete noise of measure zero.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":27858,"tokens_out":23645,"duration_ms":169779,"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":[{"comment":"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":"Algorithm 1, Eq. (15)"},{"comment":"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.","section":"Section 5.3, Lemma 10, Eq. (67)"}],"minor_comments":[{"comment":"The quantifier in (35) reads 'for all k >= max{...}' but the left-hand side involves K; it should read 'for all K >= max{...}'.","section":"Theorem 4, Eq. (35)"},{"comment":"In Sections 4.1 and 4.2, 'we stimulate the noisy gradient evaluations' should read 'we simulate the noisy gradient evaluations'.","section":"Section 4"},{"comment":"The contour plot in Fig. 1 is not reproducible from the text; consider adding the specific parameter values used to generate the visualization.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The central result appears correct and is a solid contribution to stochastic nonconvex optimization. The required revisions are modest: the algorithm must be made well-defined when m_k = 0, and the garbled inequality in Lemma 10 needs a correct derivation. There is no novelty or scope concern; the paper fits the journal's readership."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOverall, 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.","headline":"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.","tokens_in":28383,"tokens_out":2777,"would_cite":true,"duration_ms":22392,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49M05","49M37","90C25","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["stochastic first-order method","multi-extrapolated momentum","higher-order smoothness","sample complexity","nonconvex optimization","variance reduction","normalized gradient update","Vandermonde system"],"falsifier":"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.","tokens_in":27465,"feed_emoji":"📉","tokens_out":8161,"duration_ms":64930,"temperature":0.7,"pith_summary":"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.","feed_headline":"Smoother objectives mean fewer samples in this stochastic method","feed_subtitle":"It exploits Lipschitz pth derivatives to reach epsilon-stationarity in O-tilde(epsilon^{-(3p+1)/p}) gradient evaluations.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the lower bounds showing $\\epsilon^{-4}$ and $\\epsilon^{-3}$ optimality, defining the baselines the new rate improves upon.","marker":"[2]"},{"why":"Proposes the normalized SGD with Polyak momentum and the implicit gradient transport baseline that Algorithm 1 extends.","marker":"[6]"},{"why":"Establishes the $O(\\epsilon^{-3})$ rate under mean-squared smoothness, the property Algorithm 1 avoids needing.","marker":"[7]"},{"why":"Supplies the SPIDER estimator, another $O(\\epsilon^{-3})$ mean-squared-smooth baseline.","marker":"[8]"},{"why":"Gives the Hessian-Lipschitz $O(\\epsilon^{-7/2})$ saddle-escaping method, a predecessor baseline for $p=2$.","marker":"[9]"},{"why":"Provides the classical stochastic gradient complexity $O(\\epsilon^{-4})$ under gradient Lipschitz continuity.","marker":"[11]"},{"why":"Supplies PAGE, an optimal mean-squared-smooth gradient estimator whose rate the new method approaches as $p$ grows.","marker":"[19]"},{"why":"Gives the polynomial interpolation uniqueness and Lagrange formula used to solve the Vandermonde system for the momentum weights.","marker":"[17]"}],"fun_headline_variants":["Exploiting higher-order smoothness cuts sample needs in stochastic optimization","Higher smoothness, fewer samples: multi-extrapolated momentum","Using p-th order smoothness to cut stochastic gradient calls","Multi-extrapolated momentum exploits p-th derivatives for faster convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exploiting higher-order smoothness cuts sample needs in stochastic optimization","Higher smoothness, fewer samples: multi-extrapolated momentum","Using p-th order smoothness to cut stochastic gradient calls","Multi-extrapolated momentum exploits p-th derivatives for faster convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001279,"raw_usage":{"total_tokens":5300,"prompt_tokens":1085,"completion_tokens":4215,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":701,"completion_tokens_details":{"reasoning_tokens":4144}},"tokens_in":701,"tokens_out":4215,"duration_ms":27598,"temperature":1.0,"reasoning_tokens":4144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:12:06.369137+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Cutkosky and F","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(\\epsilon^{-3})$ rate under mean-squared smoothness, the property Algorithm 1 avoids needing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SPIDER estimator, another $O(\\epsilon^{-3})$ mean-squared-smooth baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Hessian-Lipschitz $O(\\epsilon^{-7/2})$ saddle-escaping method, a predecessor baseline for $p=2$."},{"cited_title":"Ghadimi and G","cited_arxiv_id":null,"evidence_quote":"Provides the classical stochastic gradient complexity $O(\\epsilon^{-4})$ under gradient Lipschitz continuity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies PAGE, an optimal mean-squared-smooth gradient estimator whose rate the new method approaches as $p$ grows."},{"cited_title":"Humpherys and T","cited_arxiv_id":null,"evidence_quote":"Gives the polynomial interpolation uniqueness and Lagrange formula used to solve the Vandermonde system for the momentum weights."}],"review_version":1}