Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees

Alexander Gasnikov; Artem Agafonov; Martin Tak\'a\v{c}; Samuel Horv\'ath; Slavomir Hanzely; Vladislav Ryspayev

REVIEW 4 major objections 7 minor 30 references

Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees

T0 review · 4 major / 7 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2508.19712 v1 pith:7XKHT4KL submitted 2025-08-27 math.OC cs.LG

Artem Agafonov , Vladislav Ryspayev , Samuel Horváth , Alexander Gasnikov , Martin Takáč , Slavomir Hanzely This is my paper

classification math.OCcs.LG MSC 90C5390C25

keywords quasi-NewtonmethodsglobalconvergencecubicregularizationconvexoptimizationexplicitstepsizeinexactHessiansemi-strongself-concordanceadaptive

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 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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

The 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.

The 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.

Also 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.

On 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.

Referee Report

4 major / 7 minor

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.

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 (4)

[Eqs. (5)–(6), Algorithm 1, Theorem 3 proof] 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.
[Theorem 3, Eq. (31); Corollary 3; Theorem 4, Eq. (13)] 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 < ∞.
[Assumption 2; Section 5.1, Hessian Approximation; Corollary 2] 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.
[Lemma 7; Lemma 8; Corollaries 1–4] 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.

minor comments (7)

[Algorithm 2 / Algorithm 5, Line 5] 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 2.1, derivation of Eq. (6)] 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.
[Theorem numbering] 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.
[Theorem 3 and Lemma 7, parameter conditions] 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.
[Definitions of D] 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.
[Abstract and Contributions] 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 5, Experiments] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the convergence analysis is self-contained given Assumptions 1-2, although Eq. (6) contains an algebraic mismatch that is a correctness issue, not a circularity.

full rationale

I examined the derivation chain from model (5) to stepsize (6), Theorem 1/3, Lemma 7, Corollaries 1-4, and the adaptive scheme. The convergence bounds involve the trajectory-dependent constant D = max_k ||x_k - x^*||_{B_k}; this is a standard bounded-region constant and does not define the objective residual in terms of itself, so it is not circular. Corollary 2's condition alpha_k <= L||x_{k+1}-x_k||_{B_k} is a sufficient condition on the state after the step; it is not a fitted parameter or a renamed prediction, and the rate is not asserted to follow from its own conclusion. The citations to Hanzely et al. [2022] supply the semi-strong self-concordance lemmas; those are prior results with stated assumptions that do not include the CEQN claim, so they are independent support rather than circular self-citation. I did find a serious non-circular internal inconsistency: the first-order condition for model (5) yields 1 - theta*eta - L*eta^2*||g||_H = 0, whose positive root is 2/(theta + sqrt(theta^2 + 4L||g||_H)), whereas Eq. (6) and Algorithm 1 use 2/(theta + sqrt(theta^2 + L||g||_H)). Hence Algorithm 1 is not the minimizer of model (5), and Theorem 3's opening identity f(x_{k+1}) = min_y model(y) does not hold for the printed algorithm. This means the proof may apply to a different (model-minimizing) method; but that is a correctness gap, not a circular reduction of the claim to its inputs. I therefore find no significant circularity and assign score 0.

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

The theoretical results rest on two domain assumptions (semi-strong self-concordance of the objective and relative Hessian approximation error) plus an implicit boundedness of the iterate-dependent diameter. The constants L, θ/α, and the adaptive schedule parameters are free knobs tuned in practice, and the theory does not tell the user how to set them without extra knowledge (e.g., L_semi).

free parameters (4)

L (cubic regularization constant) = L=100 on a9a, L=0.112 on real-sim for adaptive CEQN (tuned via grid search)
L controls the cubic term in the model and must satisfy L ≥ (1+α)^{3/2} L_semi/2; it is not known from theory and is tuned numerically in the experiments.
θ (or α = θ-1) = θ=1+α with α tuned per dataset (e.g., α=31.6 on a9a for CEQN LSR1)
The quadratic regularization strength should match the unknown Hessian approximation error α; in practice θ/α is a tuned hyperparameter.
α0, γinc, γdec (adaptive schedule) = α0=1, γinc=2, γdec=0.5
Initial inexactness and update multipliers are chosen by hand; only the monotone-increase variant has a global rate, the practical variant with decay does not.
initial Hessian scaling c (H0 = cI) = c=10^-4
The initial inverse Hessian approximation is set by hand and is not covered by the theoretical analysis.

assumptions (3)

domain assumption f is convex and semi-strongly self-concordant (Assumption 1)
Used to bound the Taylor model error via Lemmas 4 and 5; restricts the class beyond plain convexity.
domain assumption Relative Hessian inexactness (1-α)B_x ⪯ ∇²f(x) ⪯ (1+α)B_x with known α, αbar (Assumption 2)
The core premise for all rates; not shown to hold for standard L-BFGS/L-SR1 updates used in the experiments.
domain assumption Bounded iterate-dependent diameter D = max_{k≤K+1} ∥x_k-x*∥_{B_k} (Eq. 31)
The convergence bounds contain D; if iterates are not bounded in B-norm, the guarantee degrades or is vacuous.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees." pith.science (2026). https://pith.science/paper/7XKHT4KL

@misc{pith2026250819712,
  author       = {Pith},
  title        = {Pith review of: Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7XKHT4KL}},
  note         = {Machine review of arXiv:2508.19712}
}

abstract

Quasi-Newton methods are widely used for solving convex optimization problems due to their ease of implementation, practical efficiency, and strong local convergence guarantees. However, their global convergence is typically established only under specific line search strategies and the assumption of strong convexity. In this work, we extend the theoretical understanding of Quasi-Newton methods by introducing a simple stepsize schedule that guarantees a global convergence rate of ${O}(1/k)$ for the convex functions. Furthermore, we show that when the inexactness of the Hessian approximation is controlled within a prescribed relative accuracy, the method attains an accelerated convergence rate of ${O}(1/k^2)$ -- matching the best-known rates of both Nesterov's accelerated gradient method and cubically regularized Newton methods. We validate our theoretical findings through empirical comparisons, demonstrating clear improvements over standard Quasi-Newton baselines. To further enhance robustness, we develop an adaptive variant that adjusts to the function's curvature while retaining the global convergence guarantees of the non-adaptive algorithm.

Figures

Figures reproduced from arXiv: 2508.19712 by the authors.

**Figure 2.** Comparison of different Quasi-Newton methods with BFGS updates. [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗

**Figure 3.** Comparison of different Quasi-Newton methods with SR1 updates. [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Comparison of LBFGS and LSR1 approximations across different Quasi-Newton methods [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]

**Figure 5.** Figure 5: Comparison of LBFGS and LSR1 approximations across different Quasi-Newton methods [PITH_FULL_IMAGE:figures/full_fig_p030_5.png]

**Figure 6.** Figure 6: Comparison of the best-performing Quasi-Newton methods with adaptive CEQN stepsizes [PITH_FULL_IMAGE:figures/full_fig_p030_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 23 canonical work pages

[1]

An accelerated second-order method for dis- tributed stochastic optimization

Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kamzolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for dis- tributed stochastic optimization. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2407–2413. IEEE,

work page 2021
[3]

(19) Lemma 4 (Hanzely et al

Convex function f ∈ C 2 is called semi-strongly self-concordant if ∇2f (y) − ∇2f (x) op ≤ Lsemi∥y − x∥x, ∀y, x∈ Rd. (19) Lemma 4 (Hanzely et al. [2022]). If f is semi-strongly self-concordant, then |f (y) − Qf (y; x)| ≤Lsemi 6 ∥y − x∥3 x, ∀x, y∈ Rd. (20) Consequently, we have upper bound for function value in form f (y) ≤ Qf (y; x) +Lsemi 6 ∥y − x∥3 x. (2...

work page 2022
[5]

For the function f : Rd → R and the preconditioner schedule Bk, there exist constants θ, Lare such that and all x, y∈ Rd holds f (y) ≤ f (xk) +⟨∇f (xk), y− xk⟩ + θ 2 ∥y − xk∥2 Bk + L 3 ∥y − xk∥3 Bk . (67) 26 This assumption can be satisfied under various conditions, or in particular: • For Lsemi-semi-strong self-concordant functions [Hanzely et al., 2022]...

work page 2022
[9]

Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search

Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence rates of BFGS with exact line search, 2024a. URL https://arxiv.org/abs/2404.01267. Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of BFGS with the Armijo-Wolfe line search. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paqu...

work page Pith review arXiv 2024
[10]

Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of $O(k^{-2})$ for Convex Functions

Springer International Publishing. ISBN 978-3-030-58657-7. Dmitry Kamzolov, Klea Ziu, Artem Agafonov, and Martin Takáˇc. Cubic regularization is the key! The first accelerated quasi-Newton method with a global convergence rate of O(k−2) for convex functions. arXiv preprint arXiv:2302.04987,

work page Pith review arXiv
[12]

Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis

Tianyi Lin, Panayotis Mertikopoulos, and Michael I Jordan. Explicit second-order min-max opti- mization methods with optimal convergence guarantee. arXiv preprint arXiv:2210.12860,

work page Pith review arXiv
[13]

Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al

URL https://openreview.net/forum?id= 3xHDeA8Noi. Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is scalable for llm training.arXiv preprint arXiv:2502.16982,

arXiv
[16]

URL https://doi.org/10.1080/10556788.2020.1854252

doi: 10.1080/10556788.2020.1854252. URL https://doi.org/10.1080/10556788.2020.1854252. Yurii Nesterov and Arkadi Nemirovski. Interior-Point Polynomial Algorithms in Convex Program- ming. SIAM,

arXiv 2020

Show all 30 references

[18]

doi: https://doi.org/10

ISSN 0377-2217. doi: https://doi.org/10. 1016/j.ejor.2005.06.076. URL https://www.sciencedirect.com/science/article/pii/ S0377221706001469. Roman Polyak. Regularized Newton method for unconstrained Convex optimization. Mathematical Programming, 120(1):125–145,

2005
[22]

doi: 10.1007/s10107-019-01405-z

ISSN 1436-4646. doi: 10.1007/s10107-019-01405-z. URL https://doi.org/10.1007/ s10107-019-01405-z . Haishan Ye, Dachao Lin, Xiangyu Chang, and Zhihua Zhang. Towards explicit superlinear conver- gence rate for SR1. Mathematical Programming, 199(1):1273–1303,

doi
[25]

Then Ak = (1− ηk)At−k. Dividing both sides of (33) by Ak, we get 1 Ak (f (xk+1) − f (x∗)) ≤ (1−γk) Ak (f (xk) − f (x∗)) +α+α 2 γ2 k Ak D2 + 2L 3 γ3 k Ak D3 = 1 Ak−1 (f (xk) − f (x∗)) +α+α 2 γ2 k Ak D2 + 2L 3 γ3 k Ak D3. Summing both sides of inequality above from k = 0, . . . ...

2017
[26]

Algorithm 4 with parameters θ = 1 +α ≥ 1 +αmax, L≥ (1 +α)3/2Lsemi converges with the rate f (xk+1) − f (x∗) ≤ 270(1 +α)3/2LsemiD 3 k2

Let Assumptions 3, 4 hold and f be a convex function. Algorithm 4 with parameters θ = 1 +α ≥ 1 +αmax, L≥ (1 +α)3/2Lsemi converges with the rate f (xk+1) − f (x∗) ≤ 270(1 +α)3/2LsemiD 3 k2 . until it reaches the region ∥∇f (xk+1)∥∗ Bk ≤ 4α2 9L2(1+α)3/2 , where D def = max k∈[0;...

2022
[27]

Furthermore, by convexity, we get f (x∗) ≥ f (xt+1) +⟨∇f (xt+1), x∗−xt+1⟩ ≥f (xt+1) − ∥∇f (xk+1)∥∗ Bk ∥x∗ − xk+1∥Bk

Once ∇f (xk) = 0, we have xk+1 = x∗ and the method converged. Furthermore, by convexity, we get f (x∗) ≥ f (xt+1) +⟨∇f (xt+1), x∗−xt+1⟩ ≥f (xt+1) − ∥∇f (xk+1)∥∗ Bk ∥x∗ − xk+1∥Bk . Hence, ∥∇f (xk+1)∥∗ Bk ≥ f (xt+1) − f (x∗) ∥x∗ − xk+1∥Bk . (51) By the definition of CEQN step, η...

2022
[29]

For the convex functionf : Rd → R satisfying bounded level set assumption of the form R def = maxk∈[0,...K] ∥xk − x∗∥Bk < ∞, and the Quasi-Newton preconditioner scheduleBk satisfying Assumption 5, the CEQN method converges globally to point a xk such that ∥∇f (xk)∥∗ Bk ≤ 2θ L ...

2022
[30]

(81) D Experiments Our code is available at https://anonymous.4open.science/r/ceqn-stepsizes/

Nesterov [2022][Lemma A.1] shows that the sequence {βk}∞ k=0 for 0 ≤ βk ≤ 1 decreases as O(k−2), so denote c constant satisfying βk ≤ ck−2 for all k (Mishchenko [2023][Proposition] claims that c ≈ 3 is sufficient), then for k at least k ≥ r c τ 2ε = r c8LθR3 ε = O r LθR3 ε ! (...

2022
[1697]

Gluon: Making muon & scion great again!(bridging theory and practice of lmo-based optimizers for llms)

Artem Riabinin, Egor Shulgin, Kaja Gruntkowska, and Peter Richtárik. Gluon: Making muon & scion great again!(bridging theory and practice of lmo-based optimizers for llms). arXiv preprint arXiv:2505.13416,

arXiv
[1972]

Gradient regularization of Newton method with Bregman distances

Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. arXiv preprint arXiv:2112.02952,

arXiv
[1993]

Understanding gradient orthogonalization for deep learning via non-euclidean trust-region optimization

Dmitry Kovalev. Understanding gradient orthogonalization for deep learning via non-euclidean trust-region optimization. arXiv preprint arXiv:2503.12645,

arXiv
[2007]

Regularized Newton method with global O 1 k2 convergence

Konstantin Mishchenko. Regularized Newton method with global O 1 k2 convergence. arXiv preprint arXiv:2112.02089,

arXiv
[2008]

Inexact high-order proximal-point methods with auxiliary search procedure

Yurii Nesterov. Inexact high-order proximal-point methods with auxiliary search procedure. SIAM Journal on Optimization , 31:2807–2828, 2021a. doi: 10.1137/20M134705X. URL https: //doi.org/10.1137/20M134705X. Yurii Nesterov. Implementable tensor methods in unconstrained convex...

doi
[2009]

Complexity of the regularized Newton method

Roman Polyak. Complexity of the regularized Newton method. arXiv preprint arXiv:1706.08483,

arXiv
[2015]

Research in this area typically addresses two main aspects: local convergence properties and globalization strategies

16 Appendix A Other Related Works Second-order methods have a long and rich history, tracing back to the pioneering works [Newton, 1687, Raphson, 1697, Simpson, 1740, Bennett, 1916]. Research in this area typically addresses two main aspects: local convergence properties and g...

1916
[2017]

Boris Teodorovich Polyak

URL https: //arxiv.org/pdf/1505.02250.pdf. Boris Teodorovich Polyak. Newton’s method and its use in optimization. European Journal of Operational Research , 181:1086–1096,

arXiv
[2019]

Saeed Ghadimi, Han Liu, and Tong Zhang

URL https://proceedings.mlr.press/v99/gasnikov19b.html. Saeed Ghadimi, Han Liu, and Tong Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1710.05782,

arXiv
[2020]

Sketch-and-project meets Newton method: Global O(1/k2) convergence with low-rank updates

Slavomír Hanzely. Sketch-and-project meets Newton method: Global O(1/k2) convergence with low-rank updates. arXiv preprint arXiv:2305.13082,

arXiv
[2021]

Flecs-cgd: A federated learning second-order framework via compression and sketching with compressed gradient differences

Artem Agafonov, Brahim Erraji, and Martin Takáˇc. Flecs-cgd: A federated learning second-order framework via compression and sketching with compressed gradient differences. arXiv preprint arXiv:2210.09626, 2022a. Artem Agafonov, Dmitry Kamzolov, Rachael Tappenden, Alexander Ga...

arXiv
[2022]

doi: https://doi.org/10.1016/j.ejco.2022.100045

ISSN 2192-4406. doi: https://doi.org/10.1016/j.ejco.2022.100045. URL https://www.sciencedirect.com/science/article/pii/S2192440622000211. Roger Fletcher. A new approach to variable metric algorithms. The Computer Journal , 13(3): 317–322,

2022
[2023]

Inexact tensor methods and their application to stochastic convex optimization

Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáˇc. Inexact tensor methods and their application to stochastic convex optimization. Optimization Methods and Software, 39(1):42–83, 2024a. Artem Agafonov, Petr Ostroukhov, Roman Mozhaev, Ko...

arXiv
[2024]

Florian Jarre and Philippe Toint

URL https://arxiv.org/abs/2405.18926. Florian Jarre and Philippe Toint. Simple examples for the failure of Newton’s method with line search for strictly convex minimization. Mathematical Programming, 158(1):23–34,

arXiv
[2025]

15 Shida Wang, Jalal Fadili, and Peter Ochs

URL https://openreview.net/ forum?id=IDxZhXrpNf. 15 Shida Wang, Jalal Fadili, and Peter Ochs. Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems. arXiv preprint arXiv:2410.11676,

arXiv

Pith tools

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

[1] [1]

An accelerated second-order method for dis- tributed stochastic optimization

Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kamzolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for dis- tributed stochastic optimization. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2407–2413. IEEE,

work page 2021

[2] [3]

(19) Lemma 4 (Hanzely et al

Convex function f ∈ C 2 is called semi-strongly self-concordant if ∇2f (y) − ∇2f (x) op ≤ Lsemi∥y − x∥x, ∀y, x∈ Rd. (19) Lemma 4 (Hanzely et al. [2022]). If f is semi-strongly self-concordant, then |f (y) − Qf (y; x)| ≤Lsemi 6 ∥y − x∥3 x, ∀x, y∈ Rd. (20) Consequently, we have upper bound for function value in form f (y) ≤ Qf (y; x) +Lsemi 6 ∥y − x∥3 x. (2...

work page 2022

[3] [5]

For the function f : Rd → R and the preconditioner schedule Bk, there exist constants θ, Lare such that and all x, y∈ Rd holds f (y) ≤ f (xk) +⟨∇f (xk), y− xk⟩ + θ 2 ∥y − xk∥2 Bk + L 3 ∥y − xk∥3 Bk . (67) 26 This assumption can be satisfied under various conditions, or in particular: • For Lsemi-semi-strong self-concordant functions [Hanzely et al., 2022]...

work page 2022

[4] [9]

Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search

Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence rates of BFGS with exact line search, 2024a. URL https://arxiv.org/abs/2404.01267. Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of BFGS with the Armijo-Wolfe line search. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paqu...

work page Pith review arXiv 2024

[5] [10]

Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of $O(k^{-2})$ for Convex Functions

Springer International Publishing. ISBN 978-3-030-58657-7. Dmitry Kamzolov, Klea Ziu, Artem Agafonov, and Martin Takáˇc. Cubic regularization is the key! The first accelerated quasi-Newton method with a global convergence rate of O(k−2) for convex functions. arXiv preprint arXiv:2302.04987,

work page Pith review arXiv

[6] [12]

Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis

Tianyi Lin, Panayotis Mertikopoulos, and Michael I Jordan. Explicit second-order min-max opti- mization methods with optimal convergence guarantee. arXiv preprint arXiv:2210.12860,

work page Pith review arXiv

[7] [13]

Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al

URL https://openreview.net/forum?id= 3xHDeA8Noi. Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is scalable for llm training.arXiv preprint arXiv:2502.16982,

arXiv

[8] [16]

URL https://doi.org/10.1080/10556788.2020.1854252

doi: 10.1080/10556788.2020.1854252. URL https://doi.org/10.1080/10556788.2020.1854252. Yurii Nesterov and Arkadi Nemirovski. Interior-Point Polynomial Algorithms in Convex Program- ming. SIAM,

arXiv 2020