{"id":"861bdba7-7727-4d7a-a1ae-cd7befeed852","arxiv_id":"2505.19705","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A curve search that starts at the heavy-ball point and backtracks along a quadratic path toward the gradient yields a globally convergent momentum method with optimal O(1/ε²) worst-case complexity.","lead":"This paper gives nonconvex optimization a new safety mechanism for momentum methods: try the fast heavy-ball step first, and if it fails, backtrack along a quadratic curve toward a gradient-related direction. The method comes with convergence proofs and optimal worst-case complexity guarantees, potentially making momentum methods both faster and safer in practice.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed O(epsilon^-2) complexity for parabolic searches is not established for the heavy-ball variant: Assumption 4 requires ||s_k|| <= c||grad f(x_k)||, and for s_k = -alpha grad f(x_k) + beta (x_k - x_{k-1}) the momentum term is never shown to decay with the gradient.","rationale":"The reader's conditional verdict is the right one. The global convergence results are sound: monotone Proposition 2 and nonmonotone Proposition 4 hold under boundedness of xi_k, and for the heavy-ball direction this boundedness follows because f(x_{k+1}) <= f(x_{l(k)}) <= f(x_0), so iterates stay in the compact level set. What is not established is the complexity half of the abstract. Proposition 8's uniform acceptance interval depends on Assumption 4, and Section 4 never checks it for s_k = -alpha grad f(x_k) + beta (x_k - x_{k-1}). A simple accepted heavy-ball step with f(x,y) = x^2/2 and a large initial y-displacement makes ||s_0||/||grad f(x_0)|| arbitrarily large while satisfying the Armijo condition, so the assumption is not a consequence of the other hypotheses. This does not falsify the algorithm; it means the optimal O(epsilon^-2) guarantee has been proven for the general parabolic-search framework but not for the advertised heavy-ball method. The concrete check above settles that the missing condition is a genuine gap, and the paper should either prove a momentum-decay bound or state the complexity result only for other choices of s_k.","tokens_in":17172,"tokens_out":23307,"duration_ms":243432,"concrete_test":"Run the provided code on the admissible instance f(x,y) = x^2/2 with alpha = 1, beta = 1, sigma < 1/2, x_0 = (epsilon, M), x_{-1} = (epsilon, 0), epsilon = 10^-6, M = 10^6; the unit heavy-ball step is accepted and R_0 = ||s_0||/||grad f(x_0)|| ~ 10^12. This violates the uniform bound in Assumption 4, so the O(epsilon^-2) proof in Proposition 8 cannot be invoked for the heavy-ball variant without an additional momentum-decay condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 8 is the main complexity result. Its proof uses Assumption 4 to bound L_k in Proposition 6 and to obtain a uniform acceptance interval [0, Delta_low]; without a finite c, the interval may collapse and the O(epsilon^-2) bound is unsupported. For the heavy-ball direction s_k = -alpha grad f(x_k) + beta (x_k - x_{k-1}), Assumption 4 reads alpha ||grad f(x_k)|| + beta ||x_k - x_{k-1}|| <= c ||grad f(x_k)||, i.e., the past displacement must be dominated by the current gradient norm. The paper never proves this, and it is not a consequence of Assumptions 1-3: compactness of the level set gives only a uniform bound on x_k - x_{k-1}, and nothing in the monotone or nonmonotone Armijo rule forces the displacement to vanish with grad f. For instance, with f(x,y) = x^2/2, alpha = beta = 1, x_0 = (epsilon, M), x_{-1} = (epsilon, 0), the unit heavy-ball step is Armijo-accepted and ||s_0||/||grad f(x_0)|| = beta M/epsilon, which is unbounded as M/epsilon grows. Section 4 introduces the heavy-ball direction but verifies only the convergence hypotheses and never returns to Assumption 4. Consequently the optimal complexity claim is established for the abstract parabolic-search framework but not for the advertised heavy-ball method. Global convergence (Propositions 2 and 4) is unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17569,"tokens_out":10736,"duration_ms":99303,"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":[{"comment":"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.","section":"§3.1 (Assumption 4) and §4 (heavy-ball direction)"},{"comment":"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.","section":"Abstract and §2.2.1 (Proposition 4)"}],"minor_comments":[{"comment":"The word “nomonotone” appears in the sentence “the convergence result for a nomonotone curve search approach”; it should be “nonmonotone.”","section":"§1, Introduction"},{"comment":"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.","section":"§2.2.1, proof of Proposition 4"},{"comment":"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.","section":"§5, Computational experiments"},{"comment":"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.","section":"§5, stopping criterion"},{"comment":"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.","section":"§3, Remark 4"}],"recommendation":"major_revision","confidential_remarks":"The general curve-search framework and the convergence proofs are sound and publishable in principle. The main issue is that the headline complexity result for heavy-ball methods is not established: the proof requires Assumption 4 for the auxiliary direction, which is not verified for the momentum term. This is fixable by either proving a stronger property for a modified heavy-ball step or by clearly separating the abstract complexity theorem from the heavy-ball application and softened claims. The nonmonotone convergence statement in the abstract also needs to be aligned with the actual theorem. I recommend major revision rather than rejection because the core framework is valuable and the issues are local to the interpretation and scope of the complexity result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Couple of things you should know. This paper gives a curve-search globalization for heavy-ball type updates: instead of rejecting non-descent directions, it backtracks along a quadratic curve whose endpoint is the tentative heavy-ball step, and only steps back toward a gradient-related curve if the tentative point fails an Armijo condition. The general convergence results are clean. The nonmonotone variant (Propositions 3-4) looks genuinely new, and the complexity analysis for quadratic curves (Proposition 8) gives the standard O(epsilon^-2) for reaching approximate stationarity under Assumption 4. The heavy-ball application is a nice framing: you recover pure heavy-ball steps in the strongly convex case where safeguard-based methods discard them.\n\nWhere it gets soft. The abstract and Section 3 advertise optimal complexity for parabolic searches, and Section 4 says the heavy-ball variant fits the framework. But Assumption 4 requires ||s_k|| <= c||grad f(x_k)||, and for s_k = -alpha grad f(x_k) + beta (x_k - x_{k-1}) the paper never shows the momentum term decays with the gradient. It is not a consequence of the other assumptions. Simple example: f(x,y)=x^2/2, alpha=beta=1, x0=(eps,M), x_{-1}=(eps,0). The heavy-ball step (-eps,M) is Armijo-accepted (f drops to 0) and ||s_0||/||grad f(x0)|| = M/eps, unbounded. So Proposition 8's bound applies to the abstract quadratic-curve framework, not to the advertised heavy-ball method. The convergence results (Prop 2 and 4) are unaffected because they only need bounded s_k. Also, the nonmonotone 'global convergence' in the abstract is weaker than the phrase suggests: Prop 4 gives at least one stationary accumulation point; getting all of them requires the extra forcing-function condition in Prop 5. That is not a fatal flaw, but the wording should be tightened. The numerics are solid but the parameters are tuned without reporting the tuning; less important given the code is public.\n\nBottom line: the general framework is a real contribution, the nonmonotone result is new, and the gap is addressable. I'd send it to a serious referee. The referee should ask for either a verification of Assumption 4 for heavy-ball or a clear statement that the optimal complexity applies only to methods that satisfy it.","headline":"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.","tokens_in":18040,"tokens_out":2453,"would_cite":true,"duration_ms":47323,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Curve-search backtracking globalizes heavy-ball methods without discarding their momentum steps.","keywords":["curve search","heavy-ball method","global convergence","nonmonotone Armijo condition","worst-case complexity","nonconvex optimization","momentum methods","parabolic search curves"],"falsifier":"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.","tokens_in":16989,"feed_emoji":"🎯","tokens_out":5485,"duration_ms":49259,"temperature":0.7,"pith_summary":"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.","feed_headline":"Curve searches tame heavy-ball momentum without killing its speed","feed_subtitle":"A quadratic backtracking path accepts the pure momentum step when it works, and still converges on nonconvex problems.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the heavy-ball iteration whose pure step the paper wants to globalize.","marker":"[19]"},{"why":"Gives the local convergence and optimal parameter values for the heavy-ball method that motivate preserving pure momentum steps.","marker":"[20]"},{"why":"Supplies the Armijo-type curve search rule and earlier convergence conditions that this paper extends.","marker":"[25]"},{"why":"Establishes the evaluation-complexity framework and the $O(\\epsilon^{-2})$ baseline for reaching approximate stationarity in nonconvex smooth optimization.","marker":"[4]"},{"why":"Provides the nonmonotone line search condition whose curve-search analogue is analyzed in the paper.","marker":"[12]"},{"why":"Introduces curved search methods and the general curve-search perspective used to frame the new algorithm.","marker":"[1]"},{"why":"Represents the adaptive-momentum safeguard approach that the paper contrasts with pure heavy-ball steps in experiments.","marker":"[6]"}],"fun_headline_variants":["Quadratic curve saves heavy-ball steps and still converges","Curve search keeps pure heavy-ball updates for nonconvex problems","Heavy-ball momentum accepted, then tamed by quadratic backtracking","Nonmonotone curve search guarantees convergence for heavy-ball","Globalize heavy-ball without rejecting its best steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic curve saves heavy-ball steps and still converges","Curve search keeps pure heavy-ball updates for nonconvex problems","Heavy-ball momentum accepted, then tamed by quadratic backtracking","Nonmonotone curve search guarantees convergence for heavy-ball","Globalize heavy-ball without rejecting its best steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00018,"raw_usage":{"total_tokens":1306,"prompt_tokens":948,"completion_tokens":358,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":276}},"tokens_in":564,"tokens_out":358,"duration_ms":4070,"temperature":1.0,"reasoning_tokens":276,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:09:59.430407+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the local convergence and optimal parameter values for the heavy-ball method that motivate preserving pure momentum steps."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Armijo-type curve search rule and earlier convergence conditions that this paper extends."},{"cited_title":"Cartis, N","cited_arxiv_id":null,"evidence_quote":"Establishes the evaluation-complexity framework and the $O(\\epsilon^{-2})$ baseline for reaching approximate stationarity in nonconvex smooth optimization."},{"cited_title":"Grippo, F","cited_arxiv_id":null,"evidence_quote":"Provides the nonmonotone line search condition whose curve-search analogue is analyzed in the paper."},{"cited_title":"Ben-Tal, A","cited_arxiv_id":null,"evidence_quote":"Introduces curved search methods and the general curve-search perspective used to frame the new algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents the adaptive-momentum safeguard approach that the paper contrasts with pure heavy-ball steps in experiments."}],"review_version":1}