Newton Method Revisited: Global Convergence Rates up to $O(1/k^3)$  for Stepsize Schedules and Linesearch Procedures
Authors: Slavomir Hanzely
Farshed Abdukhakimov
Martin Takáč
Venue: ICLR 2026 Poster (2026)
Keywords: Damped Newton Methods
Tensor Methods
Linesearch Procedures
Global Convergence Guarantees
Primary area: optimization
TL;DR: We analyze the stepsized Newton method under various Holder continuity assumptions, including Holder continuity of third derivatives. We present the first stepsize schedule with $\mathcal O(k^{-3})$ global convergence rate.

Abstract: This paper investigates the global convergence of stepsized Newton methods for convex functions with Hölder continuous Hessians or third derivatives. We propose several simple stepsize schedules with fast global convergence guarantees, up to $\mathcal O( k^{-3} )$. For cases with multiple plausible smoothness parameterizations or an unknown smoothness constant, we introduce a stepsize linesearch and a backtracking procedure with provable convergence as if the optimal smoothness parameters were known in advance.
Additionally, we present strong convergence guarantees for the practically popular Newton method with exact linesearch.

Published as a conference paper at ICLR 2026
NEWTON METHOD REVISITED:
GLOBAL
CONVERGENCE RATES UP TO O (k-3) FOR STEPSIZE SCHEDULES AND LINESEARCH PROCEDURES
Slavomír Hanzely
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany Mohammed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE shanzelyf gmail. mamai.ccom com
Farshed Abdukhakimov & Martin Takáč Mohammed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE (farshed. abdukhakimov, martin. takac) @mbzuuua ac.
ABSTRACT
This paper investigates the global convergence of stepsized Newton methods for convex functions with Hölder continuous Hessians or third derivatives. We propose several simple stepsize schedules with fast global convergence guarantees, up to O (K=3)). For cases with multiple plausible smoothness parameterizations or an unknown smoothness constant, we introduce a stepsize linesearch and a backtracking procedure with provable convergence if the optimal smoothness parameters were known in advance. Additionally, we present strong convergence guarantees for the practically popular Newton method with exact linesearch.
INTRODUCTION
Second-order methods are fundamental to scientific computing. With its rich history that can be traced back works Newton (1687), Raphson ( (1697). (Simpson [740). they have remained widely used up to the present day (ypma) 1995] Conn al.) 2000). The main advantage of second-order methods their independence from the conditioning local quadratic convergence rate, where precision doubles with each iteration. Additionally, they are inherently invariant to rescaling and coordinate transformations, which greatly simplifics their implementation. In contrast, the convergence of first-order methods is highly dependent the problem's 's conditioning, resulting in a slower linear convergence rate and greater sensitivity to parameter choice. Despite their natural geometry and extremely fast local convergence, second-order methods often lack global convergence guarantees. Even the classical Newton method,
the underlying problem, enabling an extremely fast
h+1 1²
V2 f(x*))
can diverge when initialized far from the solution (Jarre & Toint 2016 Mascarenhas 2007). Global convergence guarantees are typically achieved through various combinations of stepsize schedules (Nesterov Nemirovski, [994), line search procedures (Kantorovich, 1948 Nocedal & Wright 1999). trust-region methods (Conn et al. 2000), and -aabburr-aaruurdt regularization (Levenberg
1944 Marquardt 1963). The simplest borsstgoooo globalization strategy is to employ stepsize schedules a%
k+1 -
oz [V*](>*)] Vz(**)
often based implicit descent conditions, requiring additional subroutine per iteration, such as exact linesearch (Cauchy 1847 Shea & Schmidi (2025), Armijo linesearch (Armijo) 1966). Wolfe condition (Wolfe 1969). Goldstein condition (Nocedal & Wright 1999.. However, those methods often lack global convergence guarantees achieved by simple stepsize schedules. Notably, Nesterov &
Nemirovski 1994 introduced a damped stepsize schedules with global rate O (A- Hanzely et al.
(2022) improved this result by discovering duality between Lavenberg- Marquurrdd regu arization and

---

Published as a conference paper at ICLR 2026
Newton stepsizes and proposing stepsize with global rate O (k- matching regularized Newton
methods (Nesterov & Polyak 2006 Mishchenko 2023 Doikov & Nesterov 2024).
Despite recent advances, existing guarantees still fall short of the optimal rate Ω k for functions
with Hölder-sontinuous Hessians (Gasnikov et al. 2019 Agarwal & Hazan 2018 Arjevani et al. 2019). leaving open the question of whether more efficient step-size schedules remain be discovered.
In the context of first-order methods, several nontrivial step-size schedules are known to improve the convergence of Gradient Descent. YYungg (1953) introduced a Chebyshev polynomial-ban paaed schedule that attains the optimal rate for quadratic objectives, Polyak] ( (1987) proposed a schedule that is optimal for nonsmooth convex functions, and Altschuler & Parrilo (2023); Grimmer et al. (2025) developed schedules achieving semi-accelerated rates for general convex, Lipschitz-smooth objectives. These results naturally prompt the question of whether improved stepsize schedules for Newton's ' method can be found.
We answer this positively. We show that stepsized Newton method be analyzed under alternative assumption - Hölder continuity of the third derivatives -yielding convergence guarantees reminiscent of third-order tensor methods, up to O(k Analyzing Newton's method through assumptions on third derivatives is, to the best of our knowledge, a novel and somewhat unexpected perspective, given that Newton's method is typically viewed as the canonical second-order method,
1.1 BENEFITS OF SIMPLE METHODS
While it is possible achieve optimal rates using acceleration techniques with more complex structure (Gasnikov et al. 2019), simple methods are often preferred in practice for several reasons.
Firstly, they are simple and easy to understand. They are also inherently robust, typically involving fewer hyperparameters, which minimizes the need of hyperparameter tuning. In contrast, accelerated methods often require multiple sequences of iterates and additional hyperparameters, significantly increasing the complexity of tuning.
Moreover, basic methods can seamlessly integrated with various techniques to enhance practical performance, such parameter searches, data sampling strategies, momentum estimation, and gradient clipping. Combining these techniques with accelerated methods, however, introduces significant challenges. In the context of first-order methods, acceleration with parameter searches provides limited improvement over Gradient Descent with stepsize linesearch (Shea & Schmidt 2024
Fox & Schmidi, 2024).
For second-order methods, the stepsized Newton method is popular due to its affine invariance (i.e., invariance changes in basis and scaling), making it efficient and convenient optimization tool.
1.2 NOTATION
For convex function f Rd IR, we consider the optimization objective
min fxx),
#ER4
where is twice differentiable with nondegenerate Hessians that is potentially ill-conditioned. We denote any minimizer of the function as x" E argmingegd f(x) and the optimal value
f. def f(x*). We define norms based on a symmetric positive definite matrix H E Rddd For all x, E d
H def (Hr, 2/2
lg H def (g. 19)
As special case H = I, we get l2 norm
||a||x (x, 1/2 We will be utilizing local Hessian norm
H 2 f(r) with a shorthand notation
[Mi]]_ def [[ ||اl| def [gal for h E Rd.
Under Hälder continuity of third derivatives, the attainable lower bound is S2 12(- (k-9) Gasnikov al. 2019
2

---

Published as a conference paper at ICLR 2026
For the Hessians and third derivatives will be measuring them in operator Given the iterate 2, operator norn of matrix H and three dimensional tensor are defined as
HHyl
ITy, 2, w| | 10ll |
H
def
sup
(T|
def
sup
llylla
yER
V.S.WER
In this work, use these operator norms exclusively with = x* and
xkt1 xt
1.3 STEPSIZES AS A FORM OF REGULARIZATION
Hanzely et al. 2022) demonstrated that a stepsize schedule for the Newton method is equivalent cubical regularization of the Newton method (Nesterov & Polyak] (006) if the regularization is measured in the local Hessian norms. As the regularized Newton methods leverage the Taylor polynomial, we denote the second-order Taylor approximation of fly by information at point as
def fxx) + (Vf(z). y - x) + lly - x: 11...
In particular, Hanzely al. (2022) showed that T(x*),
def T(x)
argmin
2 (v) + 3 ll =11
yERd
3
equivalent Newton method with stepsize AICN
- (x*"),
k+1 x
for OC
2
(4)
1
20 (w*
>|
Note that stepsize schedule preserves much larger stepsize when initialized from the solution.
V fz())) I| >> compared to the stepsize of Damped Newton method (Nesterov Nemirovski
++L.cllV((=*t) Aiming to extend these results beyond selffconncrdaance, in Section 2 we present algorithm RN that under much more general L, Hööder continuity (Definition 1 and q p v E [2, 4] supports stepsize matching AICN's 's asymptotic dependence on gradient norm and
1994), which sets stepsize for Leg-self-concorddat functions as ar
O*k
1+ (+T - ((at)))))
smoothness constant (for T2,1 L2.1-Hölder continuous functions, q 3) and constant stepsizes of Karimireddy et al. (2018); Gower et al. (2019a) (for Hööder continuous functions, q q= 2).
Remark. Stepsized Newton methods often enjoy much simpler analysis compared to Newton methods regularized in la norms, as they can seamlessly transition between gradients and model differences,
|
[f(x*)
Ork
1.4 HIGHER ORDER OF REGULARIZATION
Extending cubic regularization (Nesterov & Polyak 2006), tensor methods achieve better convergence
guarantees by regularizing p-th order Taylor approximations by (p 1)-th order regularization (see survey Kamzolov et al.) (2023). In particular, for third-order tensor methods, Nesterov (2021)
showed that regularization can avoid computation of third-order derivatives, and Doikov et al. 2024
simplified this regularization using technique of Mishchekko (2023) to
b++ T(**),
where T(x) argmin { (2) + vER"
2 1 x1 [
(6)
for 3, a 0. Combining insights about higher-order regularization with the regularization-ssepsize duality of Hanzely et al. (2022), we show that the higher-order regularization in local norms
x k+1 To,8 (I*).
where To.9 g (x)
argmin wERd
(v) + 2 3
(7)
-1 1+20 |420|| V
Hanzely et al. 2022) expressed the stepsize as au
we simplified this form.
[||
3

---

Published as a conference paper at ICLR 2026
Table 1: Global convergence guarantees of stepsized Newton methods under various notions of Hölder continuity (Definition I. For simplicity, we report dependence only on the number of iterations k.
Stepsize def
Smoothness assumption
Stepsize schedule
Global rate
Reference
V fx))l;
Damped Newton B
Lec
O (
Nesterov & Nemirovski
1994
AICN
L2,1
O 2k
Hanzely et al.
2022
14 1 214222.119
RN
Lp (3)
O (ptttt-)))
This work (Theorem
(Algorithm
14(97
GRLS
16
Linesearched
Lp, (unknown)
minp,e
k (ptv-l)
This work (Corollary)
UN (Algorithm
Backtracked
Lp.v
k (ptv-1) minp.r O
This work (Theorem
(unknown)
Greedy Newton
18)
Linesearched
(unknown)
Lp.
milly..
O k (p(tv--)) (3)
Rate: Corollary
Folklore
(new)
(8) Constant Lan represents self-concordance constant and is implied by L2,r-Hölder continuity.
( Authors show global decrease fx**+1)= S f(**)
for some > 0. Rate ((--a) is reported in Hanzely et al. 2022), but we were unable find prove the rate for Damped Newton of the form O ").
Authors expressed the stepsize -1+ /++/++/2.10 we present simplified equivalent form.
La,19a
(1) Parameters are fixed and satisfy E (2, E [0, and + v 1 E [1,3].
equivalent Newton method with stepsize og E (0, 1], and 0g. is the unique positive root of the polynomial P(a] 1 a++9 I [x*> I| Even though the polynomial P lacks an explicit formula for its roots, we derive algorithm RN with simple and exactly computed stepsize.
This method can leverage similarity of the derivvaeivsssees similarly to Nesterov| (2021] Lemma 3).
Lemma 1. Let function f : Rdd + IR be third-order La Bööler continuous (Definition Then
I.3.0 1
Tte ||
V f(*)) - - s
x.
Yark x k+1 E Rdd
Notably, formulation is very general, and it also encapsulates all polynomial upper bounds of polynomials P|[ı y with smaller exponents. We refer the reader for more details to Section F
1.5 CONTRIBUTIONS
We summarize contributions below, with detailed comparison to the most relevant literature discussed in Section 1.6
Newton method under third-order tensor similarity:
We analyze the stepsized Newton method for functions with Hölder continuous third-derivatives (Definition T. connecting the classical second-order Newton method to third-order tensor methods.
Simple stepsizes for fast global convergence:
We propose multiple stepsize schedules for the Newton method (RN, Algorithm Dp. leveraging various Hölder continuity assumptions (Definition] [].. Although the stepsize is chosen to be a root of non-quadratic polynomial, it surprisingly simple and directly computable.
Depending on the considered variant of the Hölder continuity assumption, they achieve a global convergence rate up to O (k-3) (Theorem 2). These are the first Newton method stepsizes improving upon the rate (}= of Hanzely et (002)). Additionally, we establish the following rates:
local superlinear convergence rate (Theorem
4

---

Published as a conference paper at ICLR 2026
global linear convergence (Theorems 8 9 under additional assumption of finite s-relative
size (Definition 2) (Doikov et al., 2024).
and global superlinear convergence (Theorem under the additional assumption of uniform star-convexity (Definition 3) of degree 2 2.
Stepsize linesearches for unknown parameters:
In practice, smoothness constants are often unknown, requiring approximation or fine-tuning, To address this, we introduce a theoretical linesearch procedure GRLS (16) and practical stepsize backtracking method UN (Algorithm 2) both of which provably converge as if the optimal Theorem 5
parameterization was known in advance (Corollary) D
Guarantees for popular Newton linesearch:
As byproduct of our analysis, obtain convergence guarantees for the popular Newton method Theorem 7 This is, to our best knowledge, the first such
with greedy linesearch (18) (Corollary result.
Experimental comparison:
Section 5 we compare the proposed algorithms (RN, UN, and GRLS) with existing methods and demonstrate that they outperform their counterparts in most of the considered scenarios. Also, show that the linesearch procedure GRLS resemble stepsizes of popular Greedy Newton linesearch.
1.6 DETAILED COMPARISON TO THE MOST RELEVANT LITERATURE
Our theoretical framework builds on several insights from Hanzely al. (2022) and Doikov et al. (022)). We now outline the key differences between these approaches and
Compared to our approach, the AICN method of Hanzely et al. (2022) is restricted to cubic regularization and achieves only ( convergence rate. In contrast, our schedules accommodate a broader range of smoothness notions, including Hölder continuity of the third derivative, enabling Algorithm 1 to achieve rates up to O (k-3). Moreover, while AICN requires prior knowledge of the smoothness constant, our backtracking linesearch Algorithm 2 provably converges if the optimal parametrization were known in advance.
Furthermore, while cubic regularization in Hanzely et al. 2022) lead to the stepsize defined as the root of quadratic polynomial, higher-order regularizations require stepsize given by root of a higher-order polynomial. Surprisingly, we show that even with higher-order regularization there exists unique positive root the interval (0, 1], and propose algorithms (Algorithm and Algorithm 2 that can operate without any additional linesearch.
In comparison to Doikov al. (2024), which utilizes standard le norms for regularization, our approach employs the local Hessian norms suggested by Hanzely et al. (202)). With local norms, the minimizers of the various regularization models 7 lie on the same line. This provides a natural geometric connection between different regularizations, and can be further formalized by the notion of cosstrransformation invariance (Shestakov et al., 2025). Local norms also yield simpler algorithm that is invariant under linear transformations (e.g., data scaling or change of basis), a highly practical property that reduces hyperparameter tuning.
From technical point of view, although proofs draw techniques from Doikov al. (2024), they cannot be directly adapted to the setting of local norms. The main difficulty is that the stepsize ag appears raised to the power 1 + 8, which propagates nontrivially throughout the analysis and complicates adaptation. Our key insight is a reparametrization (line 141) in which a single implicit parameter 8 encapsulates both / and a. This reparametrization allows recover proof structure [+.8
similar that of Doikov et (024) while avoiding direct manipulations of term a
We also emphasize that our results provide a theoretical explanation for the success of popular stepsize linesearch rules along the Newton direction. These insights have implications well beyond our newly proposed methods. By contrast, the results of Doikov et al. (2024) do not offer new theoretical explanation for any already established method.
NOVEL STEPSIZE SCHEDULE
Now we are ready to present our new stepsize schedule based on the higher-order regularization.
5

---

Published as a conference paper at ICLR 2026
Theorem 1. For any o, B 2 O, the following adjustments of the Newton method equivalent:
Regularization:
k+1 x² + argmin To,3 (x*),
(8)
yER
Damping:
x+1 x² aa f<*))
(9)
where Ta,9 (x)
argmin
Φ (v) + 2tglly lly =1 and on e (0, the only
positive root of polynomial P(a] Root Newton (RN), Algorithm
def a - - (| We call this algorithm
To simplify calculations, we reparametrize the RN via 0 def
a [[ where 0 2 0 is an implicitly defined regularization constant. Using 0, the polynomial P simplifies to Po[a] = 1-a --aaa at and for any fixed 8, the stepsize defined as Te (and fixed 3 and o), 0 and a are in one-to-one correspondence via Ps (specifying either 0 or a uniquely determines the other), so every admissible corresponds to a valid a. Fortunately, we theory only in terms of ( (without a), which will then in turn lead to guarantees for a corresponding stepsize a.
1 is the positive root of Ps. For given iterate
will be able to formulate
2.1 HÖLDER CONTINUITY ASSUMPTION
Our analysis rely assumption that the function has Hölder continuous Hessian third derivative.
Definition 1. For f R.d + I, and p E N, we say that p-times differentiable convex function is Hölder continuous of p-th order, for some [0, there exists constant Lg,, oc, that
- v(
S Lp f(y)llop
ylliz
Vx,y E R
(10)
We say that the I has Hölder continuous Hessian if T2,v < oo (for some E (0, 1) and Hölder continuous third derivative if T.3,v < oo (for some v E [0, 1)).
We would like to emphasize that Definition 1 is extremely general; the most general assumption for analysis of Newton methods. In particular, choice T220 covers standard Lipschitz smoothness, I3,0 covers constant bound on the third derivative, and T.211 is equivalent the semi-strong self-concordance (Hanzely et al.) 2022). Further discussion of smoothness constants can be found in Section D We will use the properties of the Hölder continuity summarized in the proposition below.
Proposition 1. function f Rdd R is Toüler continuous, then it satisfies
[V
Vf(x) f() =x]ll"= L2= lly x =1
function Rd R is L3, -Hölder continuous, then it satisfies
(イ()) -V()))((()) 2 f() - -00lo-=1']]" ==²
La, (1 lly - 21
To summarize the proof of the one-step loss decrease, we will show that Hölder continuity assumption with sufficiently large regularization O₁ implies (for e₁ E {1,2))
(V ( (((at)
1
V [[( ||
2
201 (1 ax))
which will in turn imply the one-step decrease as
((a*) - 1(a 2 - (VS(x*+)) ), x+ x²/ (VS [V2[(=>)] " '}((at)
20 (1 a4) V || 2c,0/
[f(**+1)) ||
(11)
Due to the level of technical detail, we defer lemmas for cases E (2,3) 3) to Section A.2
We directly
present their unification via reparametrization q def 4+ E [2,4] M, Lp.

---

Published as a conference paper at ICLR 2026
Theorem 2. Let [=) O. Hölder continuity (Definition with E (2,3), [0.1]
and q = p- for points x² xbt1 x²
[ [>]((> V (xx") where on the positive
rool of Pou. For Og such that
0 2 (9M,)=
(12)
holds
(f(( [(=h]] -
1
Vf(x >||
(13)
20
In particular, view of guarantees decrease
we have that the choice 02 (9M))= [f(x'*)
f(x*) 1(akt))
(14)
9M,
Theorem 2 quantifies the amount of regularization 0g needed for guaranteed decrease, leading to RN.
Algorithm 1 RN: Root Newton stepsize schedule
1: Requires: Initial point o0 Rd Hölder continuity exponent g [2, 4] and constant M, co.
2: for k = 0. 1, do
3: n V fx+
((*
Newton direction
4: gk (v ..nk)
9k f I[
5:
O2 (9M,) 4-1 9h
Sufficient regularization
6:
OA I+0
ork. the root of Po, [a]
7: k+1 I² 04.77
Step, x² = -oo.0 (x*)
8: end for
2.2 CONVERGENCE GARANTEES OF RN
Global convergence guarantees are based on a standard assumption that the initial level set has finite diameter. Denote the initial level ((x0) def { RRd f(x) s f(x") and its diameter iterations.
as def suPr.ye ((a0) ||x v1l.. Additionally, we need the Hessian not to change much between
Assumption 1. For the sequence {ak) Jim there exists constant 7 > 0 bounding Hessian of the consecutive points in gradient direction, Y |[(++)))
This assumption is also not novel, its variant has been used in Hanzely et al. (2022) for establishing
local convergence as well as for analysis of quasi-Newton methods. Required exists in many cases. K. For functions with è-stable Hessian (Karimireddy et al. 2018). 7 For -.--seff-concorda functions, holds when iterates are close to each other
For L-smooth μ--trongly convex functions,
(Nesterov & Nemirovski 1994) in the neighborhood of the solution (see proposition below).
Proposition 2 (Hanzely et al. (2022), Lemma 4). For convex L su--sff-coocodannt function and
iterate x such that (x*))
12c.+1)=-1 it holds V2 - - (1- v2 21= -
2hx
With assumptions clarified, we can jump straight to the convergence guarantees. First, we present superlinear local rate, which is expected for the stepsized Newton method.
7

---

Published as a conference paper at ICLR 2026
Theorem 3. Let function f _R + be convex. Hölder continuous for E {2,3}, E 0,, 1,11 p + with y-bounded Hessian change ① Algorithm 7 has superlinear local rate,
[ || < (9M))* f( (2- +-)
For the -Hölder continuous functions, the presented rate is suboptimal compared quadratic rate of AICN schedule (4). However, the rate of Theorem holds for any q, and its exponent increases with g (up 5/3 for 4).
For global convergence guarantees, we first quantify in general the decrease implied by Theorem This will provide plug-in guarantees for the RN and other algorithms.
Lemma 2. Let function f I.d R be convex with 7 -bounded Hessian change ① and the bound level sets with diameter D. If an algorithm A generates the iterates {z K for q z and Cs 2 as
kmm with one-step decrease
f(x²) - f(aht1) 2 C5
V
(15)
then A has the global convergence rate f(* So S
2(g-1) 7ook
K/4
Theorem Let function f Rd + R be convex. Hölder continuous for E {2,3], E 00, 111,9- = p with -y-bounded Hessian change ① and the bound level sets with diameter
D < cc. Algorithm
(RN) with known parameters q, Mg converges with rate O
M,D9 D
14-T
as
f(x)) - 9M,D
AD(g-1) 7k
8-1
De k/4
De k/4
Algorithm RN also achieves global linear and superlinear convergence rates under different assumptions. Due the space constraints, we deferred these results to Section
Note that the loss function can satisfy Hölder continuity (Definition I with multiple different Lp.e, and therefore different pairs (q. Mg) can be used. The best parametniztion might not be known.
3 UNKNOWN PARAMETRIZATION
To address unknown parameterization, propose to not rely Theorem 2 but to find point maximizing the bound 15 directly.
f(y) f(x²)
k+1 argmin
(16)
v
/
where Yh.r def
(V)( a shorthand for Newton's direction at point x. We call this Regulated Line Search (GRLS, Algorithm 4). Interestingly. this theoretical linesearch simultaneously minimizes loss and gradient norms. Its rate follows directly from Lemma 2
algorithm Gradient-BE Gradient-Regulatee
Corollary 1. Let function f : RR.d + IR, be convex, Hölder continuous with some M, < oc, with --oundddd Hessian change (1) and the bound level sets with diameter D Linesearch GRLS
converges as f(**) fo < minge 2.44 9M,,,,,,, (1D(g-1)
+I[Vf(z²)) De De-k/4
Observe that for small stepsizes as [0, a), for < 1, model differences small k+1 ~ . and ( ~ (s(a (). Therefore, expression (16) minimized by GRLS can be approximated as
f(v) f(a*)
((v) f(x))
(17)
|V V (x 1
8

---

Published as a conference paper at ICLR 2026
and the right- sidd- is minimized by the popular Newton method with greedy linesearch,
argmin
f(y).
(18)
ve fx* an lae(0,1))
which we will call Greedy Newton (GN). Our experimental evaluations will demonstrate that linesearches GN and GRLS use similar stepsizes (Figures 2c 3cb justifying (T7). Therefore while
GRLS enjoys strong convergence guarantees, method GN is preferable in practice due to its easier criterion. Nevertheless, this connection allows us to obtain the convergence rate for the Greedy Newton in the corollary below. We refer the reader for more detailed explanation Section
Corollary 2. Let function f Rd + R. be convex, Mg -ööler continuous for some Mg < cc, with y--oounedd Hessian change (T. and the bound level sets with diameter D < cc. If Greedy Newton linesearch (18 satisfies the inequality f= $ f
I| with some constant č 2 M, MgDe2((-1))
for all iterates z², then it has convergence guarantee mimgg[[244 O
De (ADT)I-I)
ADE (q - 9-1
fxx²) So S min MM,D (E(2.4]
7k
Remark. Corollary inttroduces assumption that the gradients norm measured in the local norms does not increase by more than a constant factor in between the iterates, || [ S
a|| V f(<=")]""" For any sequence {Ix } monotonically decreasing loss f. this holds for example for functioos with constant c.
In this section, established fast convergence guarantees for the novel but impractical linesearch method GRLS (T6) and for the popular GN scheme (18). both of which do not require prior knowledge of the smoothness parameters (y, M₃). However, their implicit nature may not be suitable for all practical scenarios. To address this limitation, in the next section we introduce practical stepsize backtracking procedure with matching convergence guarantees.
UNIVERSAL STEPSIZE BACKTRACKING
Our backtracking procedure is based on the observation that the knowledge of the parametrization (g, .M)) in RN is required only for setting 0z. We start with an estimate of 0g smaller than the true value and increase until achieves the theoretically predicted decrease. We claim that the resulting algorithm UN is well-defined with bounded number of backtracking steps.
To formalize this claim, we quantify the smallest plausible true 0g that will be estimated first. For q E [2, 4] and N 2 denote (x) def infge(2,41 (9M,)== [+) ( 8)
Lemma 3. Mr < 30 for some q E 4], and the initial estimate small enough, do S. H. (I²), then all iterations {-*}² Jn= UN, such that (V*()*)) > 0, satisfy a = 0
( S
H (a*). Moreover, the total number of backtracking steps during the first iterations, NK. is bounded as No S. 2k + logp (Hl (z=-))/00)
Theorem Let function ʃ Ted + IR, be convex, Hölder continuous for p E (2,3), v e 0. 1) = p- with bounded Hessian change (Assumption)) 7 and the bound level sets diameter
D < cc. Algorithm (UN) converges with the rate min
O
M R9
f(a²)- - S.S min 9M,D 4pp 1 (E(2.4]
De
+ |V
De-
RESULTS OF NUMERICAL EXPERIMENTS
The majority of figures and the detailed technical description were deferred Section A.I

---

Published as a conference paper at ICLR 2026
Algorithm 2 UN: Universal stepsize backtracking procedure for the Newton method
1: Input: Initial point æ² E RR, constants do > 0, 1, 2 B [
> Note B m -- 227 22 - for E [2,
2: for k 0, 2.. do
n² (x*)(
v((**)
Newton direction
4:
gk = (vf(x²) nn)
> 9k = \>(>>)
5:
for jks 0, 1, 1.2 2,2...do do
6:
OKj p a
Increase regularization Update stepsize
7:
ar 14 of x² Oni.
8:
D Step, 2fe Tpi 02. (x*)
9:
if (=]j)))) ),
20 UR.s [2 )| then
k+1 o
11: k++1 = p l0kk
12:
break
13:
end
14: end for
15: end for
Rosenbrock Function, d 40
Wexton, mm
Armio Nexton Dready
10
02-
30
10-12
100 150
100
350
Steps
Steas
Figure 1: Performance of Newton method stepsize lineserch procedures on the notoriously challenging nonconvex Rosenbrock function (2T). We plot mean standard deviation random initializations. We crop stepsize standard deviation at O.
compare higher-order methods without any linesearch procedures, namely RN. AICN (Hanzlly et al. 2022) and Gradient Regularization of Newton Method (GRN) (Doikov et al. the damped Newton method with fixed fine-tuned stepsize and classical first-order Gradient Method (GM) (Nesterov 2018). RN and AICN show similar performance while GRN has a slight disadvantage. Unsurprisingly. the first-order method GM has quicker iterations but slower per-iteration convergence.
In Figures 2a 3a
2024 Alg. 1). As additional baselines.
In Figures 2b 3b we compare higher-order regularization methods with smoothness constant estimation procedures, UN and Super-universal Newton method (Doikov et al.] 2024] Alg. 2). As an additional baseline, we use the damped Newton method with fixed but fine-tuned stepsize. We show that UN displays faster convergence than the Super-universal Newton method. Moreover, we show that the exponent of the regularization term 3 that appears in both UN and super-universal Newton method (6) does not have significant impact overall performance.
compare implicit linesearch procedures for Newton stepsizes, namely GRLS, Armijo stepsize, and Greedy Newton stepsize (GN) (Cauchy 1847; Shea & Schmidt (025). Our theory presents convergence guarantees for GRLS and GN with stepsizes limited to the interval [0, 1]. We go beyond this limitation and perform parameter linesearches over
Figures 2c 3c
R4 instead.
3c demonstrate that on logistic regression and polytope feasibility problems, linesearch procedures GRLS and GN use almost indistinguishable stespsizes and converge faster than Armijo linesearch and fixed stepsize Newton. On the Rosenbrock function (Figure I), GRLS outperforms all other linesearches procedures.
Figures 2c
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Agarwal, N. and Hazan, E. Lower bounds for higher-order convex optimization. In Conference On Learning Theory, pp. 774-792. PMLR, 2018.
Altschuler, and Parrilo, Acceleration by stepsize hedging Multi-step descent and the Silver stepsize schedule, 2023.
Arjevani, Y., Shamir, O., and Shiff, R. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, 178(1):327-360 2019.
Armijo, L. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3 1966.
Cauchy, A. Méthode générale pour la résolution des systemes d' l'équations simultanées. Comp. Rend. Sci. Paris, 25(1847) 1847.
Chang. C.-C. and Lin, C.-J. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Conn, A., Gould, N., and Toint, P. Trust Region Methods. SIAM, 2000.
Doikov, N. and Nesterov, Y. Gradient regularization of Newton method with Bregman distances. Mathematical programming, 1-):1 2024.
Doikov, N., Mishchenko, K., and Nesterov, Y. Super-universal regularized Newton method. SIAM Journal on Optimization, 34(1):27-56, 2024.
Fox, C. and Schmidt, M. Glocal smoothness: Line search can really help! In 2024: Optimization for Machine Learning, 2024.
Gasnikov, A., Dvurechensky, P., Gorbunov, E., Vorontsova, E., Selikhanovych, D., and Uribe, C. Optimal tensor methods smooth convex and uniformly convex optimization. Conference on Learning Theory, pp. 1391-1391. PMLR, 2019.
Gower, R., Kovalev, D., Lieder, F., and Richtárik, P. RSN: Randomized subspace Newton. In Wallach, H., Larochelle, H., Beygelzimer, A., d' Alché Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32, pp. 616-625. Curran Associates, Inc., 2019a.
Gower, R., Kovalev, D., Lieder, F., and Richtárik, P. RSN: randomized subspace Newton Advances in Neural Information Processing Systems, 32, 2019b.
Grimmer, B., Shu, K., and Wang, A. L. Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS Journal on Optimizationn 7(2):156- 169, 2025.
Hanzely, S. Sketch-and-projje meets newton method: Global (11/R²) convergence with low-rank
updates. In Li, Y., Mandt, S., Agrawal, S., and Khan, (eds.), Proceedings of The 28th International Conference Artificial Intelligence and Statistics, volume 258 of Proceedings
of Machine Learning Research, pp. 3205-3213, PMLR, 03-05 May 2025. URL https
//proceedings.oo ptreiiingsmmm..pessss....
www.prrssspeeeeee wwtp//258////// www.aaannnnaaa.....a /tt.a html
Hanzely, S., Kamzolov, D., Pascchnyuk, D., Gasnikov, A., Richtárik, P., and Takáč, M. A damped
Newton method achieves global O 2) and local quadratic convergence rate. Advances in Neural Information Processing Systems, 35:25320 25334,, 2022.
Jarre, F. and Toint, Simple examples for the failure of Newton's method with line search for strictly convex minimization. Mathematical Programming, 158(1):23-34, 2016.
Kamzolov, D., Gasnikov, A., Dyurechensky, P., Agafonov, A., and Takáč, M. Exploiting higher order derivatives in convex optimization methods. In Encyclopedia of Optimization, pp. 1-13. Springer, 2023.
Kamzolov, D., Agafonov, A., Pasechnyuk, D., Gasnikov, A., and Takáč, M. OPTAMI: Global superlinear convergence of high-order methods. 2025, URL https: http://pppweee.eeeeeeee net fformm? d=
11

---

Published as a conference paper at ICLR 2026
Kantorovich, L. Functional analysis and applied mathematics. Uspekhi Matematicheesiikh Nauk, (6):89-185) 185, 1948.
Karimireddy, S., Stich, S., and Jaggi, M. Global linear convergence of Newton's 's method without strong-convexity Lipschitz gradients. arXiv preprint arXiv:/806.0044 00400, 2018.
Levenberg, K. A method for the solution of certain non-linear problems in least squares. Quarterly of applied mathematics, 2(2):164-160 1944.
Marquardt, D. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Applied Mathematics, 11(2):431444, 1963.
Mascarenhas, W. On the divergence of line search methods. Computational & Applied Mathematics, 26(1):129-169, 2007.
Mishchenko, K. Regularized Newton method with global convergence. SIAM Journal on Optimization, 33(3):1440-1462, 2023.
Nesterov, Y. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 35799.
Nesterov, Y. Implementable tensor methods in unconstrained convex optimization. Mathematical Programminng 186:157-183, 2021.
Nesterov, Y. and Nemirovski, A. Interior-Point Polynomial Algorithmss in Convex Programming. SIAM, 1994.
Nesterov, Y. and Polyak, B. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
Newton, I. Philosophiae Naturalis Principia Mathematica. Jussu Societatis Regiae ac Typis Josephi Streater, 1687.
Nocedal, and Wright, S. Numerical Optimization. Springer, 1999.
Polyak, Introduction to Optimization., volume 1. Inc., Publications Division, New York, 1987.
Raphson, J. Analysis Aequationum Universalis Seu Ad Aequationes Algebraicas Resolvendas Methodus Generalis & Expedita, Ex Nova Infinitarum Serierum Methodo, Deducta Ac Demonstrata. Th. Braddyll, 1697.
Shea, B. and Schmidt, M. Why line search when you can plane search? SO-friendly neural networks allow per-iteration optimization of learning and momentum rates for every layer. arXiv preprint arXiv:2406. 11200..7990 17954, 2024.
Shea, B. and Schmidt, M. Greedy newton: Newton's method with exact line search: B. shea, m. schmidt. Optimization Letters, pp. 1-19, 2025.
Shestakov, A., Bohara, S., Horváth, S., Takáč, M., and Hanzely, S. Loss-transformation invariance in the damped Newton method. arXiv preprint arXiv:2509.255 25782, 2025.
Simpson, T. Essays Several Curious and Useful Subjects, in Speculative and Mix'd 'd Mathematicks. Illustrated by a Variety of Examples. Printed by H. Woodfall, jun. for J. Nourse, at the Lamb without Temple-Bar, 1740.
Wolfe, P. Convergence conditions for ascent methods. SIAM review, 11(2):226 235. 1969.
Young, D. On Richardson's method for solving linear systems with positive definite matrices. Journal of Mathematics and Physics, 32(1-4):243-25, 1953.
Ypma, T. Historical development of the Newton- Raphson method. SIAM Review, 374455311-55, 1995.
12

---

Published as a conference paper at ICLR 2026
A DETAILED DESCRIPTIONS
A.1 DETAILED DESCRIPTIONS OF EXPERIMENTS
LOGISTIC REGRESSION LOSS
In Figure 2 we compare the performance the proposed algorithms on binary classification on datasets from LIBSVM repository (Chang & Lin 2011). For datapoints {(a,, b,) where a, E Rd b, E 11,1,+1), and regularizer 10 10-3, we aim minimize
{f(z)
log (1 +l (ltaaaaa))) 1 ( 21
min ZERd
(19)
We initialize all methods at zo 10 [1, 1)ad IRd
POLYTOPE FEASIBILITY LOSS
In Figure 3 we compare proposed algorithms on polytope feasibility problem, aiming find point from polytope P (2 Rd (a;, I bi, 1 1 n reformulated as
min zERd
{(x))
(as, - bi)%
(20)
==0
where (t)+ def max 0} and p 2 We generate data points (a;, b;) and the solution x" synthetically as a,, x² NO, 1) and set by = (a,, x²) )
We initialize all methods at zo [1, 1, 11" E Rd.
ROSENBROCK LOSS
Linesearch procedures solve the abovementioned problems just few steps. For a more challenging lask, Figure presents the notorious d-dimensional Rosenbrock function,
min ((xz) #ERd
=
100(z;+11- - =²?)² (1 (1-2))
(21)
Notably, the Rosenbrock function 21 is nonconvex, which breaks assumptions in our convergence theorems.
The function 21 has the global solution at x² = [1...., 117, and therefore we choose the initial point from normal distribution, _ (O, Ta) 20.
TECHNICAL DETAILS
All hyperparameters were fine-tuned achieve the best possible performance for both objectives and every dataset. All experiments were conducted on a workstation with specifications: AMD EPYC 7742 64-Core Processor with 32Gb of RAM. Source code is available at httphhts//gttttaaeee com/ Exrshed/ http:/oootttttteeee
A.1.1 EXTENDED COMPARISON ON ROSENBROCK FUNCTION
In Figure we present an extended comparison of linesearch procedures on Rosenbrock function 21 (similar Figure []. with 10 random initializations and the limit of 1000 steps. We observe that none of the considered algorithms consistently converge to the exact solution for all of the random seeds, and that GRLS performs better than the other linesearch methods.
A.2 HÖLDER CONTINUITY TO ONE STEP DECREASE
Lemma 4. Let [V[(**]] 0, and x E Rdd, h+1 x Ork V22 [x+))
V((())) in RN.
13

---

Published as a conference paper at ICLR 2026
Log Segression, 414
Logid e Regression 17a
My 20
10
168 120
Logistic Regresioo, muahroots
Loghdic Regrassion, colon-cancer
(a) Performance of RN compared to other higher-order methods without any linesearch procedure.
Logitic Regression, sla
Loght c Regression, with
7a0m F1
Logietic
Logiticc Regression colon-cancer
(b) Performance of UN compared to other higher-order regularization methods with smoothness estimation procedures.
sic Nogressios, 2l3
Logldt c Regrossion, w7o
Duay magye
(agistic Regresdmm
Lnghtic
300
(c) Performance of Linesearch GRLS [6 compared to other linesearch procedures.
Figure 2: Binary classification logistic regression problem LIBSVM datasets.
14

---

Published as a conference paper at ICLR 2026
Pelytop Feaebiiyy.oo n= 200 d 1000.-100,p-2
My 28
Pelyopp Feaabiiyy 200, 1000p-10.p-
12-1
127
127
600 180 coos Bila san ann con toi cato
020
1.4
Pedytope Feaabltyy by,
Pelytope Feauiblity 200,
(a) Performance of RN compared to other higher-order methods without any linesearch procedure.
Polytope Peasiblity, n- 200 100.dd1100 p00.00
Polytope Feadiblity..o n 200, 20000=100.pp-
Polytope Feadibiity 200, 100,
Pelytope Feasibiiiy, 200, 100000
(b) Performance of UN compared to other higher-order regularization methods with smoothness estimation procedures.
Polytape Peasibllyy byyuibiltyy.e de 200 100,
PolyTope Feasibllyy d00 100,
Pelytope Feadbiliy, 2003
Pelytope Feadibity 200.0-100.p-5
(c) Performance of Linesearch GRLS [66 compared to other linesearch procedures.
Figure 3: Polytope feasibility problem (20) on a synthetic datasets.
15

---

Published as a conference paper at ICLR 2026
Algorithm 3 Line search backtracking procedures for the Newton direction
1: Inputs: Initial learning rate "Yu 0, constants c1, C2 (0, 1), shrinkage factor p (0, 1). current iterate x E IR, termination condition C' defined as
f(x+) S f(z) en an (=)) 22
Armijo
f(x4) S f(z) - er V/ +2 (n, Vf(+))) S {2ll((")); f(x+) f(z) -1 Vf 2 & Kn, Vf(x+))| (=)
Wolfe
Strong Wolfe
2: Compute Newton's direction n2 + [() ff(x
3: Initialize 7 <-
4: while Cxx + 7yg x) is satisfied do
5: <- PY
6: end while
7: Return next point x + 72
Algorithm 4 GRLS: Gradient Regularized Line Search
1: Requires: Initial point xº E R4.
2: for k 0. 1,2..... do
3: n = fx²)) ff(**)
> Newton direction
4: Compute next iterate
f(v) f(ah)
argmin yE( ve(x-an"JaE(0.) [e[(0.1]
[V
5: end for
Hölder continuity of Hessian (Def. a
with
2) implies that for On larger than O2
12
V/x*)) |[ holds 1tv
(Vf(a (V "V((")) 2 2(1 - on)) VV + )|
1
Hölder continuity of the third derivative (Definition) larger than
with p = 3) implies that for regularization On
Ou 2 as Vf(="))1 max
(6(L2)) L3,
14
V3L3,v
(ax (ax1ITf(=>>1>>))
(22)
(1+
holds
Vf(c [2*((²)] vf(z*))
4(1 as) (1 | 1112
In Lemma 4 requirements on 0₂ are inconveniently dependent on ay. We can use the following observation derive a bound dependent only on the norm of the gradient.
Lemma 5. For Cz, 8 > O, choice 0₂ 2 c3 + (
ensures 0g 2 cs (as (f(=)>)((a))
B GLOBAL (SUPER LINEAR CONVERGENCE RATE
Stepsized Newton method is known to be able to achieve a global linear rate the Hessian is bounded and stepsize is constant (Karimireddy al. 2018 Gower al. 2019b), or when the function is
Lg, -ööder continuous with stepsize following schedule AICN (Hanzely et al. 2022 proof in (Hanzely 2025)).
16

---

Published as a conference paper at ICLR 2026
Rosenbrock Function, d = 40
Newton, Ir=0.1
Armija Newton Greedy
GRLS
10
10
0.6
10
10
0.0
10-1
Steps
Steps
Figure 4: Performance of Newton method stepsize lineserch procedures on nonconvex Rosenbrock function (2 We plot mean + standard deviation of 10 random initializations. We crop stepsize standard deviation at 0.
line with those results, we present global linear rates for algorithms RN, UN, GRLS on Lööder continuous functions with finite (p + verelltivve size characteristic (Dikovv al. 2024). The proof
in Section G
Definition Doikkov et al. 2024 For strictly convex function f Rd we call s-relative
size characteristic
def D2 sup x.vER(=*))
|| - vll
Vs By( v)
where 3,(x, v) del (V((x) VI(v), v) > 0 and V def sup 2 (,(2,
Let function f be Lööder continuous, with finite relative size Dg < oo for p (Definition 2 and ry-bounded Hessian change (Assumption [ Algorithms RN, UN and GRLS find points in the s-neighborhood, f(**) f(x")= S in
Theorem
MgDg V
-
In fo
In |[
k 05O
iterations, implying global linear convergence rate.
Remark. In view of (17), analogous convergence guarantee (with worse constant) can be proven for GN.
Replacing relative size assumption with uniform star-convexity of degree (g > 2), guarantee global superlinear rate for RN and GN similarly to Kamzolov et al. 2025).
Definition 3. For 2 2 and μ₂ we call function Rd IR p.-uniformlly star-convex of degree in local norms with respect to a minimizer x" if E Rdd, Vn [0, 1] holds
17(1 n)ps | x= xl
f (Λæ + (1 1))") < nz(()) (1-
If this inequality holds for μt = O, we call function ff star-convex in local norms (w.nt. minimizer x²).
Theorem 7. Let the function f Rd + R be Lp., Hööder continuous (Definition 1 and
It-uniformly star-convex of degree in local norms (Definition) 3) and + 2 then
17

---

Published as a conference paper at ICLR 2026
RN and GN have global decrease in functional value suboptimality, A-1
1(x*) - S. (f(x²)
(-)
II fte);
t=
where in E [0, is the only positive root of Eạ(1) 17"-1 ( (1tt)) + ;) -1 9 5-
def
(1 11) _
xx x²
Ifq 8, then îis is constant throughout all iterations and the rate is globally linear.
decreases, 1 1 ni - 0, and If q then îie is monotonically increasing as | 1o0--x"la x21122
therefore, the resulling rate is globally superlinear.
Proof of Theorem written
We have that updates of RN with g = p v 2 B and any a N Mg can be
1(x s $ (2.tt1)
- G|1aAt1
1
(23)
q
min vERd
+
(v)
x11
(24)
q
using standard integration arguments from My Hölder continuity
Mg
S min
f(y) +
lll
x* 201 + Elle =0111
(25)
yERd
(p+ 1)!
Mg
) ;)) 110 - 8
min VERd
f(v)) +
(26)
(p+1)) 1)!
setting y f x + (x("" - x²) ) for arbitrary np E [0, 1],
I f (x* + me(x"- - 1²
+ n
Mg
+ 1 11 x ==1
(27)
(p + 1)! ④
assuming Ma-Strong star-convexity for q 2 s 2 2,
< (1 - (x²*
+ 13 nh mk)pp
(p+ 1 + 2) 110h - x²" =111
Mg
1x x² 11
+ 1/
(28)
denoting functional suboptimality de del f(x²t f
5x+1 I (1 -7
-mx 11||10=* - x= 1// (1- ma) n ( (w++1) 1)!
Mg
+ = |1 - -x =x11(3-² (29)
Denote expression E(n) def (1 M) 17011 ( (1A4i): + :) |x
x 20110== for 17 [0. 1]. Observe
that En(n and therefore monotonically decreasing on IR with E(O) > E(1) we can conclude that it has a unique root r on [0, 1]. With choice r7 + n in the last inequality we can conclude global convergence rate
J S vjx))r
(30)
Note that the root of the expression E is inversely proportional the distance from the solution ||æc - x: 1z. and therefore as the method converges, x² - x=, then the size its root increases
Ūh + 1. Therefore, the global convergence rate (30) is superlinear.
Unrolling the recurrence 30) yields the inequality from the Theorem 7
18

---

Published as a conference paper at ICLR 2026
Note that the decrease is based solely on the decrease in functional values, which allows to prove the identical guarantee for Greedy Newton linesearch GN. In particular, GN implies of f(zōN) S f( and we can analogically conclude
[( S. s (J(#GN) f.) (1 ina).
(31)
C FAST CONVERGENCE GUARANTEES FOR GREEDY NEWTON LINESEARCH
If the inequality IV S < [f range [a, 0i] holds
|| holds for constant 2 0, we have that for stepsizes in
f(v) f(a²) min [0. [K]
[(v) - s(at)
Se²
min a' E Lx,
(32)
y x of
proving that Greedy Newton minimizes the target metric of GRLS up to a constant xτ_ If we denote & constant with which GRLS satisfies Lemma 2 then Greedy Newton satisfies Lemma with constant ésc² and guarantee convergence similar to Corollary
Now we are going to discuss how constant can be found in different scenarios.
Remark (General -olHör continuous functions). To find e we note that Theorem 2 shows that (9M,) - [>>(>>>> for Mg-Hölder continuous function implies
def 1-ac-
stepsize 0k
1
< Vf )(=)) vf(=*))
2(1 a4))
which after rearranging yields [ - 2(1 ax) V I1 Therefore
(33)
1 (9M,) म
| f(**)(
or equivalently
ã x (1-
Vf ||
1+ sup (9M,) vE(2.4)
|
(34)
In such case, 7 can be set as 7 = 2(1 - a).
Note that (34g is satisfied by smaller stepsizes, which damped Newton methods use globully until they converge to the neighborhood of the solution.
Remark (Hölder continuity of Hessians). For L2 Lemma yields
Vf(E) S <11-a)
L2, a 1+
|[
(35)
1+
ensuring that without any limitation on a
def sup
1 al +
Lz, 1
V
(36)
aE (
1
L
max aE(a.
al
V ||
(37)
1+
For a +- 0, <- 1, we can sei
7 max {
L2 IV
< max (1,
Lz (")))) "
(38)
Remark (L2.0 Hööler continuity). For L functions with L 2 1, constant 7 simplifies to
def c
12,0 + |1 al. because
L200 2
- +1 a
L2a +12] fa
(39)
L2.0
+ 1
2 a
Laaa +
-1
L2 - ifal1.
2
2
19

---

Published as a conference paper at ICLR 2026
D CONNECTION BETWEEN STEPSIZES AND REGULARIZATION
We show connections of particular stepsizes to regularized Newton methods. For fixed o > 0,3 2 define regularized model
To, B (x) argmin
[(x) (VF 2)) + 221l x1 2 B lly x112+ 212
(40)
yERd
We can define optimization algorithm RN
+ del To (xt)
(41)
By first-order optimality condition, solution of model def To, 3 (x) - a satisfy
0|11"11 [2 = -
(42)
h* (1 +1+0|11111 [()) ff(x).
(43)
Now iterates of RN are in the direction of Newton method (for any and () and we write
h = -a [v'](=]]~ Vf(r,,
(44)
[)] = -aa((),
(45)
| [<]l>\>\\\<>>]>>>>
(46)
Substituting [>] h* back the first-order optimality conditions we get
0= Vf(x)) (1 a -
a -1-a-at+2
(47)
Thus, a defined as a root of the polynomial
P(a] 1-a a [[
(48)
satisfies first-order optimality condition. Note that P[O] 0 and P[1 < 0, hence P has root interval (0, 1]. This will the stepsize of our algorithm. Also note that P is monotone on R.,
P'la] -1 (1 + [[>>) <0.
(49)
and consequently, the positive root of P i'is unique.
E RELATIONS BETWEEN SMOOTHNESS CONSTANTS
First note that the parametrization I.p is log-convex in and hence for S 1 S V2 S 1, hold
Lpp. I [pp Lp.02]
and Lp. I 1,,00 -L
Lg
Consider any 7 E [0, 1]. From Hölders continuity, triangle inequality and definition of Lp
v f< =illop - [V2 V2 f2)( + La. lly = S 12,211 y1
(50)
I
L3.4
1+ |1 - 20
(51)
For y + x + Th, where |1b|, = 1, > 0, we can continue
Lza + Ls.v
\ < -1-7 #1+ 7"
(52)
2 +
I2
144-y
[2,n] 1+b-
Lz, 140-7
1/ 1/byT
(53)
+
Lz
3
<
2 1200..111
1/by + 0,0+1
(54)
20

---

Published as a conference paper at ICLR 2026
and summarize
L3,0 sup /
(')(())oop S sup
(1V Suup((>)(<))l +
(55)
xFy
(2L2,1 / L2,0,,1
2 /
(56)
Lemma 6. If L2, exists, for points ,", , = I ak [2f(2²)] -1 (I*)
holds decrease
L2
VV M1 S 0g I+ Vs(* Vs(x [|
and hence, v > 0 and 0₂ 2 [ff for O, and if the bound (17) exists (meaning that the Hessian does not change much), have guaranteed superlinear local rate.
Remark. Hanzely et al. (2022) shows that -2,i-rö continuity implies self-concordance, and
Nesterov 2018 Theorem 4.1.3) proves that self-concordance implies positive definiteness of Hessian f the domain of function f contains no straight line.
F GENERALITY OF HIGHER-ORDER REGULARIZATION
In this section we explain how (7) encapsulates polynomial upper bounds P[| ylla] with smaller exponents. Writing regularization as a polynomial,
fwv) S (v) + P[] - =1laah
(57)
this can be bounded as
(v) S (v) A + A2 -
(58)
where constants A2 and degree are expressed in the lemma below. Notably, the next iterate ++ set as the minimizer of the right-hand side of (58) is not affected by A₁, but the A₁ worsens guarantees functional value decrease, f(x+) I f(x + A
Lemma 7, polynomial with dp coefficients a₃ 2 and exponents bi S ... bdp-
dp
P def
k=0
satisfies following bound with any p maxke(1.....4 bN.
Piz] < A₁
A
where A₁ = Edr (x(p bk), A2 = dr
dr k hx
surprising remark: Similarly, we can replace even the quadratic term from Taylor polynomial, Ill - -= by an upper bound in the form A, A2lla y/l.. This further simplifies the regularization and results in the Newton method with the unbounded stepsize
148
x - ( (o+1)
As the gradient diminishes, the stepsize diverges to infinity. Yet, simultaneously, the functional value guaranteed not deteriorate by more than constant factor.
Proof of the remark. We can bound the majorization as
To.9 (x) argmin yERd
+ -110- x 11
σ
Ily x 2+
(59)
2
argmin
[(x) + (VI(x), +
0+1
1lv
x
2+8
(60)
2(B +2
2+ 3
yERd
[V Vf(x).
(61)
(o (
21

---

Published as a conference paper at ICLR 2026
where stepsize obtained as the positive root of polynomial
Plaj def = (o)
Surprisingly, stepsize is unbounded, and when [+)(" + 0, then +
This puzzling result
has a simple explanation such stepsize converges only to a neighborhood of the solution.
In practice, we could not observe stepsize larger than 5 any considered dataset. When close to the solution and the stepsize becomes larger than one, algorithm (61) stops converging closer to the solution, and functional values oscillate.
G ANALYSIS UNDER S-RELATIVE SIZE ASSUMPTION
In this section, we present global convergence guarantees under a novel characteristic called s-relative size recently proposed by Doikov al. (2024).
Striet convexity implies By v) > 0, we also have lim D, D, also Br(z.w)
V S 1, and
|x 1z-w1 -y112
(V V x - v) 2 Vs
(62)
De
Characteristic D3 is log-convex function in s, and if Ds, Des oo, then for 2 S1 5 82 holds
D2 S [D,,] - [D 12-01
(63)
and D2 is continuous on this segment.
Remark. For self-concordant functions, holds Bz y) 2 lly oll and D2 S D Vj.
Remark. For functions such that By(x,, v) 2 Hallx vll". it holds D. - self-concordant functions holds (z 3) 2 lly =Il and therefore D2 S /Vz Assumption 2. For some s 2 2, value of D is finite, D. < co.
Vi H.
In particular, for
Lemma 8. For any 2 S. S q, we have
Dg
D2 D
<
(64)
D
Proof of Lemma
Analogical to Doikov et al. (024)).
Now for any 2, Q(=%),
f(w) = f(x) + (Vf(z).g 2) + S'' 1 (((=)
x) dr
(65)
2 f(x)+ + (Vf(z). 2) + 1 v, ( | (15- 5|ا =
(66)
and minimizing both sides w.r.t. independently, we get s D. D.ILSWWI
f(x) - f.
(67)
Vj
Let us denote some constants that will appear in proofs.
der g(s 1)
2
q
2
and
1
(68)
(q 1)s
3
(q - 1)s
Wg.s def 1 ))
4
f
15-15A
giz-1i
--1
(69)
2 8
1-11/
9M,Di
2
8 1-1
9M,D!
Cg def 27(9 1)(9M) =
(70)
22

---

Published as a conference paper at ICLR 2026
(
Note that We. Cg 7(9-1)
D
De
Lemma 9, For q E 4] and a E 12, oo), we have
V (xx(++1))))))))))) 11
1
2 4i.
(71)
(f 1)
(f 1)f2
V1 (xxx))
Proof. Analogically to Doikov et al.
2024 denote ft. f(x²) fa.
(x**)) |1
Sk fk-1
| |1:
(72)
2 9M,,
V f ||
V.f(2*
V
8
S
(73)
2
9M4
[ ||
D
(74)
2 8
[
[[(x+t1)|1
||
wq.s
(75)
Vf((+)) )|
If 2 q, then 9 [1 and the function y(x) x- is concave. With monotonicity of {fx) we have
1
1 s
Sa Skt1
[ 1222
Wg,s
[V (76)
(f - 1)521 (9 - 1)52-1 (f
1152
1/
1 Still
2 < s < <g then v < and the function y(x)
del -- is concave. We have
1
fk
p1 fn
Lu sk+1
+2
2
wg.s
(77)
1-155 (9- 1)5
f2
Theorem 8. Let function f be Lp -Höldr continuous with finite s-relative size and y-bounded Hessian change, Map D, < so for some E [2, 4 and 2 q and sequence of iterates x², ..................... = by generated by one of the algorithms RN, UN, GRLS. If all iterates had function suboptimality fkr def f(x*)) worse than E > O, ft 2 e fort E (O,...k), then the algorithm did at most
7
2l
(78)
W (7 - 1)
fi-1
fx
g(v-1) 1a 1js
S 2% 5(g -1]
(s-1)
9M
2-
1(g11
fo
8 --0 q
Vi
Vf |ا D
2
(79)
8
23

---

Published as a conference paper at ICLR 2026
steps. If q, treating RHS limit together with lim b---- In (f) linear convergence rale
guarantees the
fo Remark. We can analogically guarantee the global linear convergence of Greedy Newton linesearch GN (8). but with slightly different constant.
9M, Dg
| D
k S 27
+ 2
(80)
Proof. Telescoping Lemma
9
Vf(x++1)
Wg.s
(81)
(5 1)52 9-1
(6 1).0
[VV((>))
1
z kwdy
(82)
[Vf()))
kewlg.s
fk
(83)
Vf(x0)] >I
kwoge exp
2 In
(84)
k
kiogge
2
||5(2>)||000
In
(85)
h
fk
kiwgg.
2wg In
V ff(2>>|o00
(86)
Sb
hence
7
k <
+ 2
(87)
Wg.0 ( - 1)
5k 9--1
fo f--1
fb
9
1
+ 2
(88)
Wg. ( -
5k
1--1
Theorem 9, Let funciton f be Lp.v Hölder continuous with finite s-relative size and y-bounded Hessian change, My. D3 < oo for some q E [2, 4] and 2 < q and sequence of iterates 20 .......2 I² by generated by one of the algorithms RN, UN, GRLS. all iterates were far from def and gt [V]((')) 2 f (0.... k)), then the algorithm did
solution, ft at most
19,,,,D'
s(g 1)
(1=-) 5
s-1
D
slg-1)
k
4-8
q
Vj
D
90 8
+ 2 In
(89)
steps. If
g, treating RHS as a limit guarantees linear convergence rate
q 1
(9M,Dg)
q
9-1
Vf D
90
1: 27
In
+ 2l
(90)
V1
q-11
D
24

---

Published as a conference paper at ICLR 2026
Proof. Note 1 6- s(g-1)
0. Let's split the analysis of the method into two stages, k
+
With Cg 27 1)(9
I we bound the first stage,
C
1 2 4
m
Jm
m exp
2 In
Im
(91)
fa-1
fe-1
fo
90
90
9m
Im
90
2 m + 21n
= m +
21n
21n
(92)
90
8
For the second stage, telescoping inequalities for = m. m.....k. ,,_-
[ 2
1
s1t1 St 11
(93)
Wi 7)
[V +2
we get
? Wg - -))
V (
9k
6
2
n
(94)
Jm
gm
9m 8
2 h
(95)
Expressing n, m from the inequalities above and adding them together yields
C.
1
Wg - 5) [5m - s'
7
2n
90
(96)
Note that 1 -- slg 1j. Minimizer of RHS in fm achieved
q
x(g=1)
f def Colig. 1/q -
V₂D* D D;
(97)
Substituting definitions of fm Wa.00 Cg. fy into the terms we get
(8-1) #
9M,
C.
27(9 -1)
fm -
V
?
fm (1-7) = s(q - 1) 1
y-4
fm
Wy.0(1 - 7)
s Wg.e
27 5(g 1)
8
D2
9
Vj
cl
2
8(g 1)
8
9M,D2
Wg. (1
9-
and plugging them back in, we conclude
< C
1 fm
p- - 8 |133]
+ 21 go
Wy.0 (1
1
9M, 9M,
D. DV--
? ---3 21 90
= =21(9
1)
q
s
V,
Wg 7)
q
1
19,,
D4
+ s(q - 1)
-7
x
9-8
V,D*
+ 2l 90
x
1
q
D
25

---

Published as a conference paper at ICLR 2026
H PROOFS
H.1 PROOF OF LEMMA 7
Proof of Lemma] 7
Using weighed AG inequality, for 0 S b < p. we have
2b 1 (p b) + bxo
(98)
We use this inequality for each term of the polynomial.
H.2 PROOF OF PROPOSITION 1I
Proof of Proposition
!
We can derive all of the inequalities straightforwardly
- V/t) V/0---//----//bb---- L' v
[y - z]dT
|V V --/ x|] - L.' || T x))
op 1/y x11,dr
S L2w - x112t0 L/ 7"
Lz 118 -x11 xx|ltt
1+
(') V'(())y - x| x|= /'' (V* 2)) -v)((-)))v>(((())) lv z/dr
/0) (² {5) =1|lp - / | + T(y - x)) )0)( loo 1ly x11_dr
s Ls, x1| 1+v S d'
L3, |19 xx1l 1+v
1 + v
Vf(8) - -|
1 v f(z)ly - x|² 2
= =f / (V2 - x)) - v3(())) by 2o
=
(9 v/()) --/()) lor 1 (x>) =Pll"
S.' / | s(x +(xx - x)) V [(0)]]] - dl
S Lawllyy - -x11 2-v f/² { d'd
Lg 11y 2t
(1+ + v)
26

---

Published as a conference paper at ICLR 2026
H.3
PROOF OF LEMMA I
Proof of Lemmal
7
For any x. h, y E E and taking y = Tu for > 0,1|ul1== =1
L
5 |m1 S (V .リ - x) +
bly -=1l 11 l
+ v
Σ - ||1l1² + (V>)(>))) + L3
1+ 11Al1
{> < { + L3
1m6l2
1+ v/
Setting
+ v L3.0
1-0
we get
L3,
{<>) 2
1+ 1/
Setting x² = x. h skt1 2.th we get
+
|| [20)) k+1 - =0/1/1 $
LaN
|| - x²1 12. =
af
1 +
1 14
H.4 PROOF OF LEMMA 6
Proof. Proof of Lemma 6
V (2 1,+ = [f(x (2((t( [1,t1 -2 241 - ar vf(x*) ||
[f(x++l) ff((t) - v²f(x** [2 k+1 1 x*1 + (1 (1-aa a..) ff(x*) M|
S [ [)((*) V2 ((*( (x 1x++1
x*
x* || + (1 - (4+) f (a*) |[*
T22 | - x² |1
1t + (1 (4 ||
(if L2 exists)
I+v v
L2 Ok
1+v [> (2+t)
||
+ +(1 (w) </< ||
I+v
Tz,
1 1- 0% + 1+
o% \
|
Lav o% V ff {((=)))( an (f(+tt))
0x +
I+v v
Hence
2 Lz. 1+v
I+v ok
V [5(x [| (1+t))
if 0
12.
[+ 0
20 V vf(x*)
if 0g
La
H.5 PROOF OF LEMMA 4
We provide separate proofs for cases p 2 and p
3.
27

---

Published as a conference paper at ICLR 2026
Proof of Lemma 4 case p 2. We rewrite the Hölder continuity for points x², gh+ s.t. xbttl
x² 04 (V2((x²)) -1 ((((a)
T2
1+t 2
1 +
1+ ||
L2n
|ottt] xz1 =
2
(f(xtt)) Vf(**) - v²*(x*) [1 - ==*]|12-
V)(('*) + oz (/((²)))) 11,22
V (1 (x)) V)(x'') ||
= | ||2 + (1 - ) [)(()))
| 2(1 - axx) (V) -
We are going to set a so that
1 ak
L2, (axl (a=l(V((+>)l 1tt 2 ) )
(99)
2(1 - aa)
[+v
and hence, we conclude the proof by rearranging,
V
vs(at))
V V.(lx
|| + 1-
Vf(**>/] 11
1
12,,
(aul (aul| )mmy)
2(1 ak)
2
2(1 [{]=a) (1+v
V + 1|
2(1 m
Now we are going to choose a to satisfy
99 Because 0g a root of polynomial P, we have
1+0
1
d+ = 0, ax
so the equation (99) is equivalent to
12, 0%
O4k = Ok
1+3
2 2
[f(x*))
v
L2, ax
02 2
V [f(x"))
v
Proof of Lemma 4 case p 3.
We rewrite the Hölder continuity for points 2t k+1 s.t. xb+
x - a (V2f(x*))
Vf((tt
La,
|x [0>||V{<>>>)) 2-
(100)
(1 + 12 + +v)
Ls,
| x² 2//1
(101)
(1 + (2 v)
-V((t) -
- (at
241 - f(a
xp2
(102)
2t
(S(att)) - oz V/(+t) 1
1 v |z: 2412
(103)
28

---

Published as a conference paper at ICLR 2026
Squaring, then using Chauchy-Schwaar inequality twice and then, lastly, Lemma I
L3 (1 + w](
(al (001|(/(=\)11))) 2 2
2 [ -1- - - x 2/2 ak
|V M1. + (1 ax 33 + 1 1 ((x [a -
-2(1 anD (V/(a [1>"" (V((a)))
+(1 anD (17
V f(0 - 2473)
(1V')(**))
1
) - 113)) f(z A+1 11
-2(1
}((("))
-
(
L3, +
af
1 (1t
2211 -as)
LIN
-2 (1 (1 a4) (f
Rearranging yields
[V' 'V)(a))))
vf(z*))
2 4(1 a(1) [f
x2 zt
1 1-ak
[f(at)
+2
L3,
+ at
+
2
2 (1
1-ay
L3, a
(1+ )
La,
2
(axl (.=1\ 2(222)
(Tt))
2(1 - am)
Finally, we are going to set 0% so that
La.
riv
a
(104)
6
2
1+
1 aj
0%k
|1
L3,
V f (z |
(105)
6
1+v)
0Kk
||
x2
2 (1++))2++)) )
La.
( (aul)T((at)))))) 2(2+()
(106)
6
2(1 an)
(1+
and then we can conclude
[(²}))
2
1
||
4(1 (
Note that the choice of stepsize implies
1 0% 0g 1+8 Ak
29

---

Published as a conference paper at ICLR 2026
and
(04).
105
(06)
satisfied
1 ork
ak
1+8 Ax=
2
v3
11
0 2 v3
Lae
V
6
La
fz
||
if f 2 6 1+1
L3.
Vf(x*)
1+v
V3LT.
(1++)
if 2
v3L3.
Vf
|| (11
(1++][++))
[1+0](2+V)
We can ensure 104
105
106 by
La,
V3L3,
8y 2 0/
Vf(x*
max
0
L+
(1 (2 +v
H.6 TOWARDS THE PROOF THEOREM
We unify cases 2, with the Lemma 5
Corollary 3. Lemma with = implies that choice 02 =
100=-110 1t
L2,
Vf(x*) 1 satisfies 0g
requirement of Lemma for p = 2 and therefore implies decrease as Doikov et al. (2024).
1+
V Vs [((++11]
f(x²) f(ahtl)
(107)
0x
L
V [f(x>)]
TTv
Lemma with E {1, + w implies that the choice
02 2
V I1 max
G
20+00
V3L3,
XFC
[V ||
(108)
1+v
v12
satisfies
22
and therefore Lemma for porp- implies decrease
f(a*)
1(*
1
[S(a
(109)
20
v v(a
(110)
21+0j
vāLa [1+1)12+D)
max
1+v
On the other hand, choice of 0g decrease as Doikov al. 22244
( Toll 1+v
ZF
||
in Lemma 4 (p = 3 case) implies
24. [
f(x²) - f(aht(] >
V
||
1+
(111)
20
61+v1a.7
142
H.6.1 PROOF OF THEOREM 2
We combine previous corollaries.
Proof of Theorem
For p = 2, choice 02 = Lpwu
p-1+v
7 (x+
implies
1-1+v
[
p- +V
f(a*) f(art|)
(112)
Li..
[V[(
30

---

Published as a conference paper at ICLR 2026
For = 3, choice 02 =
Lop 3(p-1+1)
|| | 7-1 2-2+=
implies
V [)((*++1]| ||
1
3(p 13pp-1+10 11+
f(x²) -s(xtt1
2
(113)
12
Ixp
Vf(x** |1
And for any p (2 have that 02 =
Lpw
[ 2 implies
3[p-1+v]
1
3(p + 1)
p-1+0
V V5
1(x*) - s(xht1) 2
(114)
12
Iep.e
H.7
PROOF OF LEMMA
5
Proof of Lemma Consider any C2 6 0. Inequality 02 c2 implies
1
02 2 C2
0₂
which is ensured by
1
0%
0k
02
or equivalently
0g 2
V )| I| guarantees that 0% 2 c3 पo.
||]
Now, choice
= cs
ensures 0g >
C3 ax V 111+))
H.8 PROOF OF COROLLARY 3
Proof of Corollary For the first part of (22). we use ag, [0, 1] to bound
2 a
ag
02 140
and
L3
Ls.
Vf
|| 2 6
a
0g
+
1tv
Now, the first part of (22 is ensured by 0g so that
L3,
14m
O2
6
1
or equivalently
161+ Li.v
02
|
1+
We ensure the second part of
22
directly using Lemma and together with first part we have
( La,
V3L3,,
242
0x 2 max
|V
1+
(1+
L3,F
Z4r
1+ max
v3
V ||
6
14
2 V
(6247 La.
34
V ||
1+ -1
31

---

Published as a conference paper at ICLR 2026
H.9
PROOF OF LEMMA
2
Proof of Lemma 2 For 0 f 3 S 1, function y(z) = x², 2 0 is concave, which implies
B a² (a b), va b 2 0,
a b
(115)
which we will be using for 3 def f(x²)
(0, 1].
We rewrite functional value decrease with Se def
fa
k+1
B(fx - fk+1)
3og
1
(116)
fk
fk
fg fhtt
frfk+1
(((*)) ||
[
1
Bcs
M Bcs
(117)
V { (2-
D1+#
f ||
where in the last step we used the convexity of in the form fo s ( We can continue by summing it for lo O,..., 1,
1
Bes
Vs(*
(118)
Jo
D2+3
[f k ||
AG
Benn
V fx
z
(119)
D1+3
V f (x
k=
Bon
V [f((*)
|
210
(120)
D1+3
[V
BBc5n
fn
(121)
D1+8
BBe5n
(_2 ln
V [f(x>)
D1+3 exp
(122)
fn
7885n
[>)('>) ||:0 D
2
1 ln
(123)
DI+3
Sn
V |V(<")||;02
We can bound fn based on the size of
&
In
1. If 2 ln 12
2 1, then fn S |/(x>)|| D exp (-4).
In
|V
2. If 2 ln
3. then
In
1
1
B3cn
2D2+2
1 (2(g 1))
+ Sn
(124)
f
fh
fo
2
7B83n
79-1e39-1111
Hence
D (2(g - 1))*
fn <
+ Vf(2 exp
(-4)
(125)
78 1----111
129-1 1--
32

---

Published as a conference paper at ICLR 2026
H. PROOF OF THEOREM! 3
Proof of Theorem Cauchy-Schwartz inequality together with condition 13) in Theorem imply
inequality
| 2 (V (
[F][(>*)]
2
1 [f(x+tt)]
20
(126)
which together with bounded Hessian change assumption yields
[f(x
11
||
2
20
20
(127)
This for 0g from
guarantees local superlinear rate for q >
H.11 PROOF OF THEOREM
Proof of Theorem
Theorem implies that Algorithm satisfies requirements of Lemma 2 with
correspondent q and c5
The convergence rate follows.
9M.
H.12
PROOF LEMMA
Proof of Lemma! We will prove the statement by induction. The base for do holds. For k-th iteration, consider cases based on the number of iterations of the inner loop.
Algorithm continues after ja 0 inner iterations. Note that if 0R.i satisfied (2)) Theorem guarantees the continuation condition to be satisfied for jk 1. Consequently, 0v.ix does not satisfy (22) for any q E [2, 4], and hence
OR [V
0k+1
inf (6R.4]
(9M,)
(o*))
(128)
2. Algorithm continues after j iterates, then from
127 we have
k++1 P < H (z
H (s*) s H (x*).
(129)
17
For the total number of oracle calls Nk,
K-1 Nk
K-1
Σ (1+ jv) = K KK +
log,
2K + log,
OK
(130)
0%
k=0
k=0
H ||
< 2K log
(131)
50
H.13 PROOF OF THEOREM 5
Proof of Theorem
5 Algorithm 2 sets k+ = 2y so that
(V[(c ),nk)
V mm
(132)
20rk.in OK
(Vf(z)) ),nt 2 200 On.sn
Vf(af 11
(133)
33

---

Published as a conference paper at ICLR 2026
From Theorem 2 that while (k.je- Ok.je/ p does not satisfy 13 for any g [2, 4] and
jk satisfies for some q, therefore
On 2 (9M4)
3q [2
(134)
0k.je
<p - V
Vy [2,4]
(135)
0k.j.
inf g6[2,4
(9Mg)
नं
V
#
(136)
hence estimate Okii is at most constant times worse than any plausible parametrization of (q, Ma). and therefore, even the best plausible parametrization. In particular, for
def argmin 9M,D (E[2.4)
4p² D(q 1) 4-1
| Dexp (-4
k
(137)
we have that from Theorem
V
f(xt) - f( 2 p
((=)-f((*h))
(138)
9M
Vff
The of the proof is analogous the proof of Theorem 4
34


Reviews:
[{"review_id": "ZQ6WdXKtfX", "reviewer": "Reviewer_2vmp", "summary": "In this paper, the authors study the damped Newton's method for convex functions whose Hessians or third derivatives are Hölder continuous. The key idea is to apply higher-order regularization to Newton's method in the local norm induced by the Hessian, which is shown to be equivalent to using a specific damped step size. Under the assumption of bounded Hessian variation, they establish a suplinear local rate and a global sublinear rate up to $O(k^{-3})$. Since the derived step size depends on the unknown Hölder continuity exponent and constant, they further propose both exact and backtracking line search schemes that achieve the same global rate without prior knowledge of these parameters.", "questions": "I find the proofs in the appendix somewhat difficult to follow and suggest that the authors improve their presentation. For example, in the proof of Lemma 4 for the case $p=3$, it is unclear to me how the inequality in line 1527 is derived.  I assume Lemma 1 is used in this step, but additional clarification would be helpful.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper builds on Doikov et al. (2024), who proposed Newton's method with higher-order regularization in $\\ell_2$-norm and proved an $O(k^{-3})$ rate when the third derivative is Lipschitz continuous. However, that approach sacrifices affine invariance due to the use of $\\ell_2$-norm. To address this limitation, similar to Hanzely et al. (2022), the authors adopt regularization in the local norm, thereby restoring affine invariance while retaining the same accelerated rate under higher-order smoothness. The convergence analysis is thorough and includes line-search variants that eliminate the need for prior knowledge of problem parameters.", "weaknesses": "- My main concern lies in Assumption 1, which appears somewhat restrictive. \n   - The authors cite Hanzely et al. (2022) for this assumption. However, in my understanding, their global sublinear rate does not rely on such an assumption, and a similar condition is only used to establish local quadratic convergence near the solution. In contrast, both the global and local convergence results in this paper depend on this assumption.\n  - The authors argued that this assumption is satisfied when the function is $L$-smooth and $\\mu$-strongly convex, or when it has a stable Hessian. Yet, in both cases, one would typically expect a faster global linear convergence rate, rather than the slower sublinear rate obtained here. \n  - The authors also noted that this assumption holds for self-concordant functions when iterates are close to each other or in the neighborhood of the solution. However, it remains unclear whether this condition is applicable for global analysis, since the iterates may move far in a single step. \n- I think the prior work by Doikov et al. (2024) is highly relevant and deserves a more detailed discussion in the main text. Specifically, their regularized Newton method achieves a comparable rate of $O(k^{q-1})$ under (the more standard) smoothness assumption in the $\\ell_2$-norm. It will also be helpful if the authors can elaborate on how their proof techniques differ from those in that work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1RcEGtJyfH", "reviewer": "Reviewer_jsfd", "summary": "This paper revisits the global convergence properties of **Newton-type methods** under general **Hölder continuity** assumptions on the Hessian (or higher derivatives).  \nBuilding on the **AICN framework of Hanzely et al. (2022)**, the authors propose a family of **stepsize rules** derived from solving a polynomial equation that relates gradient and Hessian norms.  \nThis formulation can be interpreted as a *third-order extension* of damped or regularized Newton methods, leading to improved global convergence rates up to **O(k⁻³)** without requiring explicit Hölder constants.  \nThe paper also introduces adaptive variants (GRLS and UN) that use backtracking or linesearch strategies to estimate stepsizes in practice. Experiments on convex and mildly nonconvex problems support the theoretical findings.", "questions": "1. Could the authors clarify **how the dependence between \\( \\theta \\) and \\( \\alpha \\)** was handled in both analysis and implementation?  \n   - Is \\( \\theta \\) treated as an implicit function of \\( \\alpha \\), or is it estimated independently?  \n   - How sensitive is the method to errors in estimating or initializing \\( \\theta \\)?  \n2. The results are presented for **convex deterministic** objectives.  \n   - How might the proposed analysis or algorithms extend to **non-convex** settings, where the Hessian might not be positive definite?  \n   - Could the same framework apply to **stochastic** optimization, where gradients and Hessians are noisy?  \n3. In adaptive variants (GRLS and UN), what is the **practical computational overhead** of the backtracking procedure, and how does it scale with problem dimension?  I believe you should be able to have a theoretical guarantee for the backtracking approach.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- **Solid theoretical foundation:** The work extends and generalizes the ideas in AICN to broader Hölder-smooth settings.  \n- **Interesting parametrization:** The introduction of the parameter \\( \\theta \\) to implicitly define the stepsize \\( \\alpha \\) is mathematically elegant.  \n- **Adaptive schemes:** The GRLS and UN variants are practical contributions that make the theory more broadly applicable, removing dependence on unknown Hölder constants.", "weaknesses": "- **Dependence on prior work:** Much of the structure and analysis builds directly on **Hanzely et al. (2022)**, with limited new conceptual ideas beyond the general Hölder extension.  \n- **Clarity issues:**  \n  - The role of the **parametrization \\($\\theta$ \\)** and how it determines the stepsize \\( $\\alpha$ \\) is not clearly explained. This deserves more detailed discussion, since it is central to the contribution.  \n  - The main problem is that $\\theta$ depends on $\\alpha$ but in the algorithm it does not.  \n- **Adaptive method overhead:** The adaptive (backtracking) procedures may add nontrivial computational cost. The paper would benefit from an explicit discussion or empirical measurement of this overhead.  \n- **Scope limitation:** The analysis and guarantees are developed specifically for **convex deterministic functions**, and it is unclear how (or whether) these results extend to **non-convex** or **stochastic** optimization settings.  \n- **Experimental scope:** The experiments are relatively small and primarily illustrative. Additional comparisons with standard baselines such as L-BFGS or trust-region Newton methods would strengthen the empirical section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gv6gThU29h", "reviewer": "Reviewer_tDN2", "summary": "This paper investigates globalization strategies for the Newton method under Hölder-type smoothness assumptions, including Hölder continuity of Hessians and third-order derivatives. The authors make three key contributions: (i) reinterpreting stepsize-controlled Newton methods as higher-order (third-order) regularized methods; (ii) proposing a new class of stepsize schedules (Root Newton — RN) along with corresponding line-search and backtracking procedures (GRLS and UN) that do not require exact knowledge of smoothness constants; and (iii) establishing global convergence rates up to $\\mathcal{O}(k^{-3})$ under appropriate Hölder conditions. The work also provides local superlinear and linear convergence guarantees under additional assumptions, supported by numerical experiments comparing RN/UN/GRLS against existing Newton globalization techniques. The manuscript positions its main contribution as improving the best-known global rate for Newton stepsize methods from $\\mathcal{O}(k^{-2})$ to $\\mathcal{O}(k^{-3})$ by leveraging Hölder continuity of higher-order derivatives.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper achieves an improved global convergence rate of $\\mathcal{O}(k^{-3})$ under Hölder continuity of higher-order derivatives, advancing the state-of-the-art for stepsize-based Newton methods.\n2. The proposed GRLS and UN procedures eliminate the need for known smoothness constants while retaining theoretical guarantees, enhancing practical applicability.\n3. A comprehensive set of convergence results is established, including local superlinear, global linear (under additional assumptions), and global sublinear rates.\n4. Experimental results validate the theoretical claims and demonstrate the effectiveness of the proposed methods.", "weaknesses": "1. On Page 3, Line 132, the authors claim that the RN stepsize schedule generalizes the AICN stepschedule when $p=2$, $\\nu=1$ (i.e., $q=3$). However, substituting these parameters yields $$\\alpha_k = \\frac{1}{1 + (9L_{2,1})^{1/2} \\|\\nabla f(x^k)\\|_{x^k}^{*\\frac12}},$$\n\nwhich differs structurally from the AICN stepsize $$\\alpha_k = \\frac{2}{1 + \\sqrt{1 + 2\\sigma \\|\\nabla f(x^k)\\|_{x^k}^*}},$$ even up to a constant factor. This claim requires clarification or correction.\n\n2. On Page 6, Line 320, the authors state that Assumption 1 has been used in [1], but this assumption does not appear explicitly in the referenced work.\n\n3. On Page 3, Line 158, the authors describe equation (6) as a \"third-order tensor method.\" It would be more accurate to characterize it as a second-order method with third-order regularization, since the subproblem in (6) involves only up to second-order derivatives.\n\n4. Minor typo: On Page 26, Line 1352, in the first equation, $\\nabla^2 f(x - \\tau(y - x))$ should be corrected to $\\nabla^2 f(x + \\tau(y - x))$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZlmZvGUmLU", "reviewer": "Reviewer_T7B3", "summary": "The paper studies various choices of step-size for Newton's method and the convergence guarantees they provide. It generalizes recent ideas (notably from Hanzely et al. 2022) that exploits the link between specific step-size choices and third-order regularization techniques. The main generalization revolves around higher-order regularity assumptions on the objective functions, considering in particular third-order H√∂lder continuity.\n\nThe paper provides various algorithms, the main ones called RN, when the smoothness parameters of the function are known, and UN when they are unknown. The authors provide various convergence results for functions that have bounded level sets (which is equivalent to coercivity for convex functions). The results essentially extend known results for twice differentiable functions to the case of 3rd order differentiable functions and considering any order $\\nu\\in[0,1]$ of Holder continuity (when often only the continuous case $\\nu=1$ is considered).\n\nThe contribution is good and interesting, yet the writing is, in my opinion, problematic at many points, which make the paper and the importance of various results unclear (see below), or sometimes misleading (for example I do not believe the paper improves the known results for the case $p=2, \\nu=1$, yet this is implictely implied in Sec. 1.5, see hereafter). \nAdditionnally, I have several important concerns regarding the practical usefulness of the main algorithms (RN, UN and GRLS) introduced in the paper, which I detail in the weaknesses section.\n\n\nOverall, the paper has merits and the contribution is fair and of interest to the community. Yet I belive that the paper needs significant improvements the writing and to give stronger arguments to convince the reader on the  the interest and impact of the main algorithms and results. It seems to me that it is yet to demonstrate how useful they are in practice compared to existing Newton's methods.\nI would welcome clarifications and feedback from the authors on these key points. I believe the paper is not ready for publication in its current state but I would increase my rating if the writing is improved to clarify several key points as recommended below.", "questions": "* In Section 1.1, what does \"basic\" methods means? Is there a rigorous definition of it?\n* Could the author clarify the global assumptions made on $f$ throughout the paper? Indeed, in Sec. 1.2, $f$ is convex twice differentiable and has non-degenerate Hessian. Since Holder continuity implies continuity, we later guess that it is actually $C^2$, or is this not correct? \n* The assumption in Sec 2.2 is equivalent to coercivity (because $f$ is convex), so adding the $C^2$ property and non-degeneracy discussed above, it seems that $f$ is actually strongly convex. If this is correct this should be more straightforwardly stated. \n* Similarly, the authors denote $x^\\star$ any element of $\\argmin_x f(x)$ but is this argmin assumed to be non-empty? Could the author clarify this sentence?\n* The rate obtained for $p=2$, $\\nu=1$ (so Holder-continuity of 2nd derivative) is no better than $O(k^{-2})$, so the current work does not improve on previous work for this case. Improvement require further assumptions. Yet the contribution section 1.5 makes it sound as it the case. I recommend reformulating or clarifying if I missed something, in the current form the contribution statement is misleading. \n* In Theorem 3, is the factor of the superlinear local rate always smaller than $1$? That is, is it guaranteed that $\\frac{2}{\\gamma} (9M_q)^{1/q-1}<1$? I recommend further discussing this result and its consequences.\n* In the case where smoothness parameters are unknown, the proposed Universal Newton (UN) method resorts to doing a line-search on $\\theta_k$ to then use a step-size $\\alpha_k = \\frac{1}{1+\\theta_k}$. Could the author clarify whether there are real advantages compared to  doing the line-search directly on $\\alpha_k$ as usually done?\n* In Section 4, regarding the UN algorithm, the authors say that the backtracking strategy consists in starting with an estimate of $\\theta_k$ that is smaller than the true value. How is it possible to ensure this since the true value is unknown?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* Strong theoretical results on several new variants of Newton's method.\n* Thorough analysis discussing all the main problems with Newton-like methods (line search or not, unknown regularization, etc.).\n* Generalization of previous results to higher-order smoothness and H√∂lder continuity.\n* Clear explanation of prior work\n* Overall rigor on the theoretical side (despite some clarifications needed in the writting, especially in the introduction section).\n* The RN algorithm is interesting and rather simple to implement when the smoothness constant is known. I have concerns regarding the other methods but RN is promissing.", "weaknesses": "* The introduction would be difficult to follow for reader not familiar with Newton's methods are many things are discussed without being properly defined (or often defined a few pages later). For example, Newton's methods is introduced in equation (1) without a step-size, but this step-size is then extensively discussed. \n* The original motivation given by the authors in the introduction was to improve the known rate for Newton's methods in the case $p=2$ and to bring it closer to the optimal rate. Yet the main contribution is in the end for $p=3$, as in the case $p=2$ the results do not improve the $O(k^{-2})$ previously known rate. \n* Some results would benefit from being further discussed to assert their usefulness in practice, a few examples are given in the questions below.\n* The GRLS method in Section 3 seems much more expensive that the Greedy Newton method, since it requires computing $\\langle \\nabla f(y),\\left(\\nabla^2 f(x_k)\\right)^{-1}\\nabla f(y)\\rangle$, possibly for several $y$ at each iteration. \nThe authors then explain the method empirically produces step-sizes close to those of Greedy Newton. Therefore I am not sure that the method has a practical interest due to its high computational cost compared to (GN)?    \n* The Universal Newton (UN) method is meant to be used on function where the smoothness constant $M_q$ is unknown, but it requires the value of $\\gamma$ which is also related to the smoothness of the problem and is likely to be unknown as well. Similarly (see the questions below), it is not clear how $\\theta_{k,0}$ is initialized sufficiently small (and it is not stated in the algorithm), since the true value is unknown. Therefore I am not sure that UN is more easy to use in practice than RN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OXQbeqvroy", "reviewer": "Reviewer_rUdG", "summary": "This paper presents new convergence guarantees for stepsized Newton methods under Holder continuity assumptions on the Hessian or third derivatives. The authors reinterpret the classical Newton method as a third-order tensor method and propose a family of stepsize schedules (RN), as well as linesearch and backtracking variants (GRLS, UN). These achieve global rates up to O(k^-3), improving upon the best-known O(k^2) results. The paper also provides convergence results for the “Greedy Newton” linesearch, supported by clear theoretical analysis and numerical experiments.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical contributions are solid and clearly positioned relative to prior work (notably Hanzely et al., Doikov et al., and Nesterov’s tensor methods).\n\n2. The paper successfully extends the analysis of Newton-type methods into the regime of Holder continuous third derivatives, showing rates that were previously thought unattainable for basic Newton variants.\n\n3. The exposition is mathematically rigorous and detailed, with clear structure and self-contained proofs.\n\n4. The proposed algorithms (RN, UN, GRLS) are simple, practical, and connect naturally to existing Newton variants.\n\n5.  The paper propose variants with adaptive sptesizes, which is important since we cannot \n\n6. Experimental results are well designed and demonstrate that the proposed methods are competitive, often outperforming baselines.", "weaknesses": "1. The experimental section, though helpful, remains somewhat limited in scope (mostly synthetic or classical problems). Stronger empirical validation on large-scale or nonconvex deep learning tasks would better support the practical relevance.\n\n2. The proposed linesearch requires evaluating the dual norm, which in turn involves an additional matrix inversion at each iteration. This cost is not discussed, and it can be significant in large-scale settings. \n\n3. The experimental section reports convergence in terms of iterations (steps) rather than the actual number of matrix inversions or Hessian factorizations, which makes the practical comparison somewhat misleading.\n\n4. The paper’s tone occasionally overstates its novelty. Conceptually, the main contribution builds on a straightforward observation: by substituting the Newton step into the Hölder continuity bound and optimizing the resulting inequality, one obtains improved global rates. This is an elegant and technically solid development, but the underlying idea remains relatively simple rather than transformative. The paper's strength lies in its clarity and rigor, not in a fundamentally new algorithmic principle.\n\n5. The claim that the method can be viewed as a “third-order” method feels overstated. The algorithm still uses only first and second derivatives; the “third-order” aspect comes only from the smoothness assumption and the resulting analysis. This is somewhat analogous to calling gradient descent a “second-order” method because it relies on a bound on the Hessian variation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)