{"id":"570d24bb-559e-4c63-bcec-259f7e5e551d","arxiv_id":"2508.19712","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An explicit stepsize schedule for quasi-Newton updates achieves O(1/k) global convergence on convex functions, and O(1/k^2) when Hessian approximation error is controlled.","lead":"This paper derives a closed-form stepsize rule for quasi-Newton optimization methods that guarantees global convergence on convex problems, and a faster convergence rate when the Hessian approximation stays accurate. It gives optimizer designers a simple, tuning-light way to make second-order methods provably stable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stepsize formula (6) misses a factor of 4: it is not the minimizer of the regularized model (5), so the proof of Theorem 1 does not apply to Algorithm 1 as written.","rationale":"The most load-bearing problem is not Assumption 2 itself (strong but explicit) but an internal mismatch in the core derivation: the stepsize formula (6) does not satisfy the optimality condition of the very regularized model (5) used to justify it. Since Theorem 1's proof begins with x_{k+1} being the minimizer of that model, the theorem as stated does not follow for Algorithm 1/4. The same erroneous formula is used in Lemma 7, Corollary 4, and the adaptive algorithms, so the accelerated guarantees are also impacted. The issue is repairable by adjusting the constant (using 4L under the square root, or equivalently rescaling the cubic coefficient), which is why I do not recommend changing the reader's CONDITIONAL verdict: the paper needs a revision that corrects the stepsize formula/reparameterization and re-verifies the constants. The reader's weakest-assumption concern about Assumption 2 being unverified for practical QN updates is legitimate but secondary; the factor-4 error is more fundamental and is not mentioned in the reader's verdict. Hence partial agreement, with verdict unchanged.","tokens_in":30423,"tokens_out":27344,"duration_ms":301321,"concrete_test":"Substitute the published η into the optimality condition. Let s = sqrt(θ^2 + L||g||_H). For g≠0, 1 - θη - Lη^2||g||_H = L||g||_H/(θ+s)^2 - 4L||g||_H/(θ+s)^2 = -3L||g||_H/(θ+s)^2 ≠ 0. Equivalently, for f(x)=x^2/2, B=H=1, θ=L=1, the correct minimizing stepsize is (√5-1)/2 ≈ 0.618, while Eq. (6) gives 2/(1+√2) ≈ 0.828. Replacing L by 4L in the formula and re-checking the proof of Theorem 1 is the first concrete test.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.1 defines the CEQN update as the minimizer of model (5). Its first-order condition is g_k + θB_k h_k + L||h_k||_{B_k} B_k h_k = 0. With h_k = -η_k H_k g_k and ||h_k||_{B_k} = η_k ||g_k||_{H_k}, this reads 1 - θη_k - Lη_k^2 ||g_k||_{H_k} = 0, whose positive root is η_k = 2 / (θ + sqrt(θ^2 + 4L||g_k||_{H_k})). The paper instead states η_k = 2 / (θ + sqrt(θ^2 + L||g_k||_{H_k})) in Eq. (6) and Algorithm 1. The printed formula is the root of 1 - θη_k - (L/4)η_k^2||g_k||_{H_k} = 0. Consequently, x_{k+1} is not the minimizer of the regularized model used in the proof; the identity f(x_{k+1}) = min_y model(y), which is the starting point of Theorem 1's proof, is false. All subsequent O(1/k) and O(1/k^2) bounds inherit this mismatch. This is an internal consistency failure, independent of whether Assumption 2 is verified in practice.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a quasi-Newton method with an explicit stepsize, called Cubically Enhanced Quasi-Newton (CEQN), obtained from a B-norm cubic regularization of the quasi-Newton model. The main theoretical claim is that, under a two-sided relative Hessian approximation condition (Assumption 2) and semi-strong self-concordance (Assumption 1), the method converges globally for convex functions with rate O(1/k), and with rate O(1/k^2) when the inexactness is suitably controlled or adaptively adjusted. An adaptive variant is analyzed and experiments on logistic regression compare L-SR1/L-BFGS variants against standard quasi-Newton and cubic-regularized quasi-Newton baselines. The central proof, however, contains a mismatch between the stated stepsize formula and the minimizer of the regularized model, and the convergence statements depend on a path-defined quantity D, so the guarantees as written are not established.","tokens_in":30736,"tokens_out":11938,"duration_ms":120402,"significance":"If the technical issues were repaired, this would be a valuable contribution: an affine-invariant, explicit stepsize for quasi-Newton methods with a global non-asymptotic rate for convex functions would address a real gap in the literature, and the connection to affine-invariant cubic Newton is elegant. The paper also provides code and experiments, which is a strength. However, the main theorem as written is not internally consistent with the algorithm, and the rates are stated in terms of a trajectory-dependent diameter that is not shown to be uniformly bounded. Because these issues are load-bearing, the current version does not substantiate the advertised global convergence guarantees. With a corrected derivation, a careful restatement of the D-dependence, and verification of the inexactness assumption for the implemented updates, the work could become a solid contribution.","major_comments":[{"comment":"The stepsize (6) is not the minimizer of the model (5). The first-order condition of (5) is g_k + θB_k h_k + L‖h_k‖_{B_k} B_k h_k = 0. Substituting h_k = −η_k H_k g_k gives 1 − θη_k − Lη_k²‖g_k‖_{H_k} = 0, whose positive root is η_k = 2 / (θ + sqrt(θ² + 4L‖g_k‖_{H_k})). The formula used in Eq. (6) and Algorithm 1, η_k = 2 / (θ + sqrt(θ² + L‖g_k‖_{H_k})), is the root of 1 − θη − (L/4)η²‖g‖ = 0. Therefore x_{k+1} from Algorithm 1 is not the minimizer of (5), and the first line of the proof of Theorem 3, f(x_{k+1}) = min_y model(y), is false. The O(1/k) and O(1/k²) claims inherit this issue. This is an internal consistency failure that must be fixed, either by changing (6) and all algorithms to include 4L under the square root or by changing the model coefficient accordingly.","section":"Eqs. (5)–(6), Algorithm 1, Theorem 3 proof"},{"comment":"The convergence bounds are expressed in terms of D = max_{k∈[0;K+1]} ‖x_k − x*‖_{B_k}. This quantity is defined by the algorithm's own trajectory and, for each fixed K, is trivially finite but may grow with K. The proofs do not show that D is uniformly bounded along the iterates. Consequently, the statement “f(x_{K+1}) − f(x*) ≤ C(D)/K” is not an a priori global convergence guarantee: if the iterates were to diverge, D would simply become larger and the bound could remain vacuous. The same issue affects Corollary 3 and Theorem 4, where D additionally contains ‖∇f(x_k)‖*_{B_k}. To claim global convergence, the authors need a uniform bound on D (e.g., from a uniform control on B_k and bounded sublevel sets) or must explicitly present the result as conditional on D < ∞.","section":"Theorem 3, Eq. (31); Corollary 3; Theorem 4, Eq. (13)"},{"comment":"Assumption 2 is the key condition linking the approximate Hessian B_k to the true Hessian, but the paper does not show that any standard quasi-Newton update—such as the L-SR1 or L-BFGS variants used in the experiments—satisfies it. The experiments approximate H_k via sampled or history curvature pairs but never verify (1−α)B_k ⪯ ∇²f(x_k) ⪯ (1+α)B_k. The “verifiable criterion for inexactness” advertised in the contributions is Corollary 2, but its condition α_k ≤ L‖x_{k+1}−x_k‖_{B_k} depends on the next iterate and is a sufficient condition for the accelerated rate, not a certificate of Assumption 2. As written, the theoretical guarantees do not cover the implemented algorithms; the experiments should either verify the assumption or be presented as heuristic validation.","section":"Assumption 2; Section 5.1, Hessian Approximation; Corollary 2"},{"comment":"There are internal inconsistencies in the constants and derivative calculations used for the one-step decrease. Lemma 7 states the condition L ≥ (1+α)^{3/2} L_semi, whereas Theorem 3 requires L ≥ (1+α)^{3/2} L_semi/2; the proof of Lemma 7 sets L = (L_semi/2)(1+α)^{3/2} and α = θ−1, conflicting with its statement. In Lemma 8, the optimality condition is written as 0 = ∇f(x_k) + θB_k(x_{k+1}−x_k) + (2L/3)‖x_{k+1}−x_k‖_{B_k}B_k(x_{k+1}−x_k), but the derivative of the cubic term in model (5) is L‖h‖_{B_k}B_k h, not (2L/3)‖h‖_{B_k}B_k h. These mistakes propagate into (65) and the claimed decrease (62). The one-step decrease, and hence Corollaries 1–4, are not reliably proven as stated.","section":"Lemma 7; Lemma 8; Corollaries 1–4"}],"minor_comments":[{"comment":"The while condition uses the undefined index t in ∇f(x_{t+1}); it should be ∇f(x_{k+1}) in both the main text and the appendix.","section":"Algorithm 2 / Algorithm 5, Line 5"},{"comment":"The equation after substitution is written with a plus sign on the L term; it should be 1 − θη_k − Lη_k²‖∇f(x_k)‖_{H_k} = 0. The displayed root also does not match the quadratic as noted in the major comment.","section":"Section 2.1, derivation of Eq. (6)"},{"comment":"The paper uses duplicate numbering: Theorem 1 in the main text is Theorem 3 in the appendix, Algorithm 1 is Algorithm 4, Algorithm 2 is Algorithm 5. This should be unified in the final version.","section":"Theorem numbering"},{"comment":"The condition θ ≥ 1+α is ambiguous because Assumption 2 has both a lower α and an upper ᾱ. Lemma 7 requires θ = 1+α ≥ 1+α_max. The authors should consistently use α_max or state explicitly which α appears in each condition.","section":"Theorem 3 and Lemma 7, parameter conditions"},{"comment":"Theorem 3 defines D as max ‖x_k−x*‖_{B_k}, while Corollary 3 and Theorem 4 define D as max(‖x_k−x*‖_{B_k} + ‖∇f(x_k)‖*_{B_k}). The notation is reused with different meaning; please use separate symbols or state the definition in each statement.","section":"Definitions of D"},{"comment":"The abstract claims O(1/k²) when inexactness is controlled within a prescribed relative accuracy, but Corollary 2’s condition α_k ≤ L‖x_{k+1}−x_k‖_{B_k} is not a static prescribed accuracy; it involves the next iterate. The wording should be adjusted to match the actual theorem.","section":"Abstract and Contributions"},{"comment":"There is a typo “Algotrithm” in the text before Algorithm 3. Also, the reference [Jordan et al., Liu et al., 2025] in the bibliography is incomplete.","section":"Section 5, Experiments"}],"recommendation":"major_revision","confidential_remarks":"The paper is a preprint with many typographical and notational inconsistencies. The factor-of-4 mismatch between the stated stepsize and the minimizer of the model is not a superficial typo because it appears consistently in the algorithm, the derivation, and the proof. The dependence of all rates on the trajectory-dependent D is a more fundamental issue that will need to be honestly reframed or supplemented with uniform bounds. I nonetheless recommend major revision rather than rejection because the underlying idea is promising and the technical obstacles appear addressable within the scope of the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this paper gives a clean closed-form stepsize for generic quasi-Newton updates with global rates, but as written the stepsize formula doesn't match the model being minimized in the proof. That's a load-bearing inconsistency, though probably a fixable typo.\n\nThe idea is to take the cubic-regularized QN model and solve for the stepsize explicitly, preserving the QN direction. Under a two-sided relative Hessian error assumption and semi-strong self-concordance, they get O(1/k) and conditional O(1/k^2). That's a real contribution to the QN global-convergence literature, which mostly has line-search or cubic-subproblem results. The paper also gives a practical adaptive variant and is upfront in Section 6 that a global rate for that practical variant is open.\n\nThe stress-test note is correct. The first-order condition of model (5) gives 1 - θη - Lη^2||g||_H = 0, whose root is 2/(θ + sqrt(θ^2 + 4L||g||_H)). The paper's Eq. (6) is missing the 4. So the update in Algorithm 1/4 is not the minimizer of (5), and Theorem 1's proof, which starts from f(x_{k+1}) = min_y model(y), doesn't apply to the algorithm as written. If they intended the minimizer, the formula needs a 4; if they intend the printed formula, the model needs L/4 and the proof's estimates change. Either way the main theorem's statement and the algorithm are inconsistent.\n\nAlso worth flagging: the rate depends on D = max_k ||x_k - x*||_{B_k}, which is path-dependent, so the guarantee is not fully a priori. And Assumption 2 (relative Hessian accuracy) is never verified for L-SR1/L-BFGS; experiments use those but don't check the condition. The adaptive variant's complexity proof is for Algorithm 5, not the practical Algorithm 3, and the paper admits this. Experiments show gains but no error bars, which is minor.\n\nOn balance: the paper is honest, the machinery is standard, and the bug is likely a typo rather than a deep flaw. But as submitted the central claim is not supported for the stated algorithm. I'd send it to review — a good referee can catch the factor 4 and require a corrected version. The idea deserves a chance.","headline":"Useful closed-form stepsize for quasi-Newton methods, but the printed formula misses a factor of 4 relative to the model in the proof — a fixable bug that currently invalidates the main theorem as stated.","tokens_in":31340,"tokens_out":4723,"would_cite":false,"duration_ms":45258,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C53","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For convex functions with a known quality of Hessian approximation, the quasi-Newton update with this closed-form stepsize converges globally at O(1/k), and at O(1/k²) when the approximation error is controlled.","keywords":["quasi-Newton methods","global convergence","cubic regularization","convex optimization","explicit stepsize","inexact Hessian","semi-strong self-concordance","adaptive stepsize"],"falsifier":"Take a convex problem with a known Hessian, run CEQN with L-BFGS or L-SR1, and at each iterate check whether (1-α)B_k ⪯ ∇²f(x_k) ⪯ (1+αbar)B_k holds for the α used. Finding an iterate where the inequality fails while the algorithm still converges would show the assumption is not necessary; finding a case where D grows without bound would make the stated rate vacuous.","tokens_in":30267,"feed_emoji":"📉","tokens_out":6843,"duration_ms":62176,"temperature":0.7,"pith_summary":"This paper shows that a single explicit stepsize formula turns the standard quasi-Newton update into a globally convergent method for convex problems, without line searches or subproblem solves. The stepsize is derived from a cubic-regularized model with the norm aligned to the approximate Hessian: it is the closed-form minimizer of that model, so it inherits global convergence guarantees while keeping the usual quasi-Newton direction. Under a two-sided relative-error bound on the Hessian approximation, the method converges at rate O(1/k) for general convex functions, and at the accelerated rate O(1/k²) when the approximation error is controlled. An adaptive version tunes the inexactness parameter automatically and matches the same guarantees. If correct, this closes a gap: classical quasi-Newton methods have strong local theory but only recently acquired non-asymptotic global rates, usually with line search and strong convexity.","feed_headline":"A simple stepsize gives quasi-Newton methods O(1/k) convergence","feed_subtitle":"For convex functions with inexact second-order models, the same rule reaches the accelerated O(1/k²) rate when error is controlled.","key_machinery":"The load-bearing object is the CEQN stepsize η_k = 2/(θ+sqrt(θ²+L||∇f(x_k)||_{H_k})). It comes from solving the first-order optimality condition of the regularized model f(x_k)+⟨∇f(x_k), y-x_k⟩ + θ/2 ||y-x_k||²_{B_k} + L/3 ||y-x_k||³_{B_k}, where the norms use the approximate Hessian B_k, so the update direction remains the quasi-Newton direction. The analysis combines this affine-invariant geometry with two assumptions: semi-strong self-concordance (an affine-invariant second-order smoothness bound) and the relative inexactness condition (1-α)B_k ⪯ ∇²f(x_k) ⪯ (1+αbar)B_k. The rate depends on D = max_{k≤K+1} ||x_k-x*||_{B_k}, and the one-step decrease lemma drives both the monotonicity and t","core_discovery":"The central claim is that the quasi-Newton step x_{k+1}=x_k - η_k H_k ∇f(x_k), with η_k = 2/(θ+sqrt(θ²+L||∇f(x_k)||_{H_k})), is the exact minimizer of a cubically regularized quadratic model in the B_k-norm. As a result, it inherits the global convergence theory of cubic-regularized Newton methods. For convex functions that are semi-strongly self-concordant and whose Hessian approximations satisfy (1-α)B_k ⪯ ∇²f(x_k) ⪯ (1+αbar)B_k, the paper proves f(x_{K+1})-f(x*) ≤ (α+αbar)/2 · 9D²/(K+3) + (1+αbar)^{3/2} · 3L_semi D³/((K+1)(K+2)), giving O(1/K) in general and O(1/K²) when α=αbar=0, matching accelerated gradient and cubic Newton rates. A verifiable condition α_k ≤ L||x_{k+1}-x_k||_{B_k} gua","pith_inferences":["The paper's experiments use L-SR1 and L-BFGS approximations, but the theory requires the relative-error condition on B_k; verifying whether those update rules satisfy or violate it at each iterate is the immediate test of applicability.","If the relative-error condition holds, the CEQN stepsize should transfer to other preconditioned or sketched second-order schemes, since the proof only uses the error bound and the model upper bound.","The global O(1/k²) result suggests a parameter-free interpolation between gradient descent and cubic Newton: the same schedule transitions from the cubic regime to the gradient regime at most once.","A natural extension is to relax the upper-bound model to allow adaptive L or θ, potentially removing the need to tune L while retaining a global rate."],"forward_implications":["A quasi-Newton method can be run with no line search and no cubic subproblem while retaining a global non-asymptotic convergence rate for non-strongly convex objectives.","Matching the O(1/k²) rate of accelerated gradient descent and cubic Newton is possible with only approximate second-order information when inexactness is controllable, e.g., via sampled curvature pairs or stochastic Hessians.","The adaptive variant removes the need to know the inexactness level α ahead of time; it inflates α only as needed to certify a decrease, so the same schedule can be used across problems.","The convergence proof is affine-invariant, meaning the guarantees do not depend on coordinate scaling or the conditioning of the problem.","The verifiable criterion α_k ≤ L||x_{k+1}-x_k||_{B_k} gives a practical rule for achieving the fast rate when the approximation error can be adjusted."],"supporting_citations":[{"why":"Supplies the semi-strong self-concordance assumption and the affine-invariant damped/cubic Newton stepsize that CEQN generalizes.","marker":"[Hanzely et al., 2022]"},{"why":"Introduces the cubic regularization model whose upper-bounding property yields the global convergence mechanism.","marker":"[Nesterov and Polyak, 2006]"},{"why":"Gives the accelerated cubic Newton rate that the paper matches in the exact-Hessian case.","marker":"[Nesterov, 2008]"},{"why":"Provides the summation bounds used in the O(1/K) convergence proof.","marker":"[Ghadimi et al., 2017]"},{"why":"Analyzes cubic regularization with inexact Hessians, the template for the relative-error model.","marker":"[Agafonov et al., 2024a]"},{"why":"The cubic-regularized quasi-Newton method with O(k^{-2}) rate that CEQN extends and compares against.","marker":"[Kamzolov et al., 2023]"},{"why":"Recent global non-asymptotic rate for BFGS with Armijo-Wolfe line search, a comparison point for the line-search-free guarantee.","marker":"[Jin et al., 2024b]"},{"why":"The L-BFGS method used as a standard quasi-Newton baseline in the experiments.","marker":"[Liu and Nocedal, 1989]"}],"fun_headline_variants":["Simple stepsize makes quasi-Newton globally convergent","Quasi-Newton with cubic-inspired stepsize hits O(1/k²)","One stepsize rule matches accelerated gradient rates","Quasi-Newton stepsize guarantees O(1/k) and O(1/k²)","Cubic-regularized stepsize for quasi-Newton methods"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"At every iterate, the approximate Hessian must be within a known multiplicative factor of the true Hessian, and the convergence bounds involve a diameter D that must stay bounded; the paper does not show that standard L-BFGS or L-SR1 updates satisfy the first condition, and the experiments do not verify it.","fun_headline_variants_meta":{"raw":{"variants":["Simple stepsize makes quasi-Newton globally convergent","Quasi-Newton with cubic-inspired stepsize hits O(1/k²)","One stepsize rule matches accelerated gradient rates","Quasi-Newton stepsize guarantees O(1/k) and O(1/k²)","Cubic-regularized stepsize for quasi-Newton methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000911,"raw_usage":{"total_tokens":3794,"prompt_tokens":827,"completion_tokens":2967,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":2879}},"tokens_in":571,"tokens_out":2967,"duration_ms":22318,"temperature":1.0,"reasoning_tokens":2879,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:32:30.335006+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a convex problem with a known Hessian, run CEQN with L-BFGS or L-SR1, and at each iterate check whether (1-α)B_k ⪯ ∇²f(x_k) ⪯ (1+αbar)B_k holds for the α used. Finding an iterate where the inequality fails while the algorithm still converges would show the assumption is not necessary; finding a case where D grows without bound would make the stated rate vacuous.","supporting_citations":[],"review_version":1}