Gradient-Normalized Smoothness for Optimization with Approximate Hessians
Authors: Andrei Semenov
Martin Jaggi
Nikita Doikov
Venue: ICLR 2026 Poster (2026)
Keywords: optimization
second-order methods
Hessian approximations
Primary area: optimization
TL;DR: Gradient-Normalized Smoothness enables second-order algorithms to automatically achieve global rates across different problem classes and Hessian approximations.

Abstract: In this work, we develop new optimization algorithms that use approximate second-order information combined with the gradient regularization technique to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is a novel notion called Gradient-Normalized Smoothness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalized Smoothness does not depend on the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method. This new concept equips approximate second-order algorithms with universal global convergence guarantees, recovering state-of-the-art rates for functions with Hölder-continuous Hessians and third derivatives, quasi-self-concordant functions, as well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as in non-convex optimization using Fisher and Gauss-Newton approximations.

Published as a conference paper at ICLR 2026
GRADIENT-NORMALZEER SMOOTHNESS S FOR OPTIMIZATION WITH APPROXIMATE HESSIANS
Andrei Semenov EPFL
Martin Jaggi EPFL.
Nikita Doikov Cornell University
ABSTRACT
In this work, we develop optimization algorithms that approximate second- order information combined with the gradient regularization technique to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is novel notion called Grudient-Normalizee Smooth- ness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalin the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method. This new concept equips approximate sccond-order algo- rithms with universal global convergence guarantees, recovering state-of-the- art rates for functions with Hölder-comtinuous Hessians and third derivatives, Quasi- Self-Concordant functions, well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as non-convex optimization using Fisher and Gauss-Newte approximations.
Smoothness does not depend on
INTRODUCTION
Motivation. Numerical optimization methods that use preconditioning second-order information such Newton-type methods- are extensively applied in machine learning, artificial intelligence. and scientific computing. While gradient-based methods-such as Gradient Descent-foom form solid foundation for many large-scale applications due to their low per-iteration cost and well-established convergence theory, second-order methods are known to significantly accelerate convergence by taking into account the curvature information of the objective function. However, although the modern theory of second-order optimization establishes strong complexity guarantees for the Newton method with appropriate regularization techniques (Nesterov 2018 Nesterov & Polyak] 2006 Cartis et al. 2011a| Doikov et al.) 2024a), the theory for inexact Hessians usually much more limited, suggesting that errors coming from the Hessian inexactness might drastically slow down convergence, causing the method converge slowly as Gradient Descent (Agafonov al.) 2204]] Chayti et al.) 2023). In this work, we aim to develop new convergence theory for second-orde -oder methods with approximate Hessians, that matches state-of-the-ard rates for the exact Newton method and bridges the geometry of the objective function with conditions on the Hessian approximation. The form of our method very simple. For unconstrained minimization of the function f, using the standard Euclidean norm, we perform:
#1+1 = IC
H [
V (xx))
2
where H₃ 2 0 is Hessian approximation matrix, and 7/k >> 0 is (second-order) step-size. This parametrization ensures that each step is bounded, || xx < 7k and for H; = 0 we obtain iterations of the normalized gradient descent (Nesterov 2024 Moreover, in the case of the exact
"Machine Learning and Optimization Laboratory. Email: andrii. swwenov8epfl.cc
Machine Learning and Optimization Laboratory. Email: martin. jwg.igepgg.gg...ooo Work primarily carried out while the author was EPFL. Email: ni kita doi kovecreeel edduu

---

Published as a conference paper at ICLR 2026
Hessians, H fZ((z)) the gradient regularization
shown to achieve both very fast
quadratic local convergence, as for the classical Newton method (Polyak] 2007). and strong global
rates for wide range of convex problem classes (Polyak) 2009 Doikov et al. 2024a Doikov 2023).
In this paper, we relax H₂ 2 V2 (xxx) to be a Hessian approximation in We consider the following condition for method:
| f(x)) HHll < C. C1+CalV
0 0<8<L
(2)
for certain C₁ C2 2 O, and B is a fixed approximation degree. This condition appears to be essentially satisfied by many natural approximations of the Hessian, such as Fisher or Gauss-Newton approximations. For example, for the finite-sum structure of the objective f(x) > i==1 fa that is popular in applications from machine learning and statisties, one can take the Fisher approximation,
(3) For simplicity, we consider here all gradients computed at the same point Zg. while in practice the gradients can be taken from the past (Frantar et al. (021) (see also (Martens 2020) and (Kunstner al. 2019) for an in-depth analysis of the Natural Gradient Descent and variants). appears that this approximation (3), e.g., for the logistic regression problem or softmax with linear models (Examples 6 (8 satisfies (2) with 3 = and C₁ = f* (the global optimum), which can be small or even zero for the well-separable data.
Hg
Σ (xrk V (xxx))
As a direct consequence of our new theory, we show that method using the approximate Hessian (3). exhibits the global linear rate, contrast to classical gradient methods, which typically achieve only sublinear convergence rates, unless additional assumptions-suu
f is sufficiently small. This stands in stark
strong or uniform convexity- are imposed. Notably, our method remains formally first-order, relying solely on access to the first-order oracle.
2 even with C and B 0, where H₃ is a specific combinations of Gauss-Newton and Fisher matrices (see Examples 7 g We show that in these cases, when the degree 33 of Hessian approximation is smaller than the degree of smoothness a (see the formal definition in Section 4 the errors coming from Taylor's 'ss approximation dominate the Hessian inexactness, In these situation (C₃ O. C2 > and a 2 3), our method with inexact Hessians has the same global rate as the full Newton method (C₃ = C2 0), see Figure
Other examples include nonconvex problems with nonlinear operators, which satisfy
Degree of Grodont- Nonnt-Normalzadd Smoot hisooo,
Bounded Hes, variation
Contributions. In this work, we develop new frame- work for describing the global behavior of second-order methods using universal (problem-class free) local char- acterization of the objective's gradient field and Hessian approximation, called Bondiinnt-Nomaaiice Smoothness (Section 2). We propose a unified treatment for the er- rors coming from both Hessian inexactness and Taylor's s approximation, thereby showing an intrinsic connection between them. Our theory provides method (I) with universal step-size rule for 7k. which adapts automatically to the right problem class (which is described by the de- gree of smoothness. 0 < a < 1. introduced in Section 4) and the Hessian approximation error (2). See Table for the summary of the complexity results covered by our Gradient- Normali-- Smoothness, for particular problem classes.
Dominanen the Smoothness Class
a>B B
Lip. Hess.
αK < B
Lip. v's
Dominance Hossian Inexactness
Quasi-SC
Degroe of Hessian Inexactness,, ,9
Figure 1: Global Convergence Diagram for Algu- rithm see that,
9, the prohlem class of dominates the Hessian inexactness, and our method achieves the same rate as full Newton.
(I) For the case of Exact Newton, H 2 (*rk) ). we ultimately recover the state-of-the-an rates obtained in (Doikvv et al.) 2024a Doikov 2023) for functions with Hölder continuous Hessian functions (a 0). Our theory also extends to generalized Self-Concordant functions (Sun & Tran- Dinh 2018), which correspond to < a < 1. establishing novel global rates in this range. Beyond that, the Sradient-Normalizae
( S a < 1),, Hölder continuous third derivative ( E a S ( and Quasi-Seff-CConorree
Smoothness framework allows to treat (Lo, L2 -smoohh functions (Zhang et al. 2019 Xie et al. 2024) from both first-order and second-ordes optimization (see examples in Section 2). Our convergence theory works both in convex and nonconvex cases (Theorems 112
(II) For the Inexact Hessian, we use condition to control the approximation errors, which is automatically covered by our notion of Gradient-Normaale Smoothness and provides with the
2

---

Published as a conference paper at ICLR 2026
Problem class
Exact Case (C1 C2 = 0)
Inexact Hess. (ours)
Bounded Hess. variation
Mr
(Nesterov. 2018)
0 [M6 CajD" -.D"'
Mi/2 e:72
+ C.D²)
Lip. Hess,
Nesterov & Polyak
2006
D4/s eirs
o( 0(1M61s + C2)Dus C1D²) c1/a
Lip. viy
Doikov al. 2024a
Gen.-SC, < 1/2 o
Mi Dl
(ours)
[M (M) C 0
Quasi-SC, =
(M,
Doikov 2023
(2) C
Table I: Global complexities for our Algorithm on different problem classes with convex objectives and using inexact Hessian. We show the number of iterations roquired to find e-solution to our problem: (() - f S e. Note that we recover state-of-the-art rates Jor the exact Newlon (C2 C2 = () in all purticular Self- Concordant (Gen. (C)) functions, introduced in (Sun & Tran-Dinh 2018), are also novel in the exact case.
and exlend thei the inexact Hessians. The global rates for the Generalized
corresponding convergence rates. An interesting observation from our theory is that, in the regime 2 B and C₁ 0, the smoothness class of the objective dominates the Hessian approximation. and we recover the same rates as for the exact Hessian (see Fig. [T. As by-product, we establish new global convergence rates for several practical problems (see Section 55 particularly when using approximate Hessian information, such as Fisher and Gauss-Newton matrices, which are popular in machine learning.
(III) Numerical experiments (Section and Appendix B) illustrate our theory and confirm excellent performance of method (2) with our step-size selection and Hessian approximations.
Related Work. Using a scalable approximation of the Hessian matrix in Newton's 's method remains an attractive and popular approach to addressing the ill-conditioning of the function by better capturing the problem's 's geometry. Various examples include: low-rank approximations of the Hessian or quasi-
Newton methods (Dennis & Moré
1977 Jorge & Stephen, 2006; RRooomanov & Nesterov 1021
Rodomanov] [022] Jin & Mokhtari 2023). ) spectral preconditioning (Ma et al.[] [Zhang et al.
2023
Doikov et al. 2024b), first- and zeroth-order approximatoo (Cartis et al. [212]] Grapiglia et al.
2022 Doikov & Grapiglia 2025), the Fisher and Gauss-Newton approximations (Nesterov) 2007]
Kunstner et al. 2019
Arbel et al. (2023), stochastic subspaces or sketches (Cartis & Scheinberg 2018
Gower al. 2019 Fuji et al. [2022] Zhao al. 2025 Hanzely 2025). and many others. Modern
techniques to globalize Newton's method, include the cubic regularization (Griewank) 1981 Nesterov
Polyak 2006) Cartis al. 201 la and gradient regularization (Polyak [2099 [Mshhhenko]] [202]]
Doikov & Nesterov [203] Doikov et al., 2024a; Doikov 2023), that constitute the main basis of our
work. Another popular approach consists trust-region methods (Conn et al. 2000; Jiang et al.,
1023,Xie et al. (2024). the notion Hessian stability (Karimireddy et al. 2018). and Newtin
methods with global convergence (Kamzolov et al., 2023] [Scier [2024] Rodomanoy 2024: Jin et al.
2024). In recent years, we have seen more and more interesting deviations from the classical picture of complexity theory (Nemirovski & Yudin 1983), with new important problem classes emerging from modern applications. These include the notion of relative smoothness (Bauschke al. 2017 Lu
ct al. 2018). or (Lo, L, )-smoothness (see (Zhang et al. 2019 Koloskova et al. [023 Gorbunov et al.
2024 Vankov et al. (024)) and references therein), especially motivated by empirical smoothness properties of neural networks. While each of these new problem classes typically requires special new method and establishing the corresponding convergence theory- it is becoming increasingly evident that the most natural optimization schemes are universal, in the sense that they can automatically adapt to the appropriate degree of smoothness without requiring knowledge of any specific parameters (Nesterov 2015 2024).
cecention-dssignne
Notation. Let us consider unconstrained minimization problem,
min f(x), eEE"
(4)
where f: _ + R is a differentiable function, that can be non-conver. Let f :- inf f(x), which we assume to be finite: f -0. We denote by ff(x) E R" the gradient vector at point R=x* the Hessian, which is a symmetric matrix. The third derivative,
E R" and by f²) V²f(x) is a tri-linear symmetric form. We denote by V f(x h2 ha] E R its action onto arbitrary directions h,, , h2, h RR. Let us fix symmetric dositive-definite matrix B > 0, which
3

---

Published as a conference paper at ICLR 2026
use to define pair of global Euclidean norms in our space:
||lll == (Bh,h) || == (s, 19.B-1s
h, E RR,
which satisfy the Cauchy-Schhie Schwarz inequality: (ss, h)] Σ ||||||||a|.. We use the dual norm to measure the size of the gradients. In the simplest case, can set B =- (identityy matrix), which gives the classical Euclidean norm, while, in some cases, the use of a specific B can significantly improve the global geometry and convergence of our methods (see Section examples). Correspondingly, we use the induced spectral norm for symmetric matrices and multi- forms, c.g.
[()]l :
|| (V((),, h)),
= maxpi fa h].
also define the following local norm (Nesterov & Nemirovski 1994), which is induced by the Hessian of the objective, for any æ E R": | := (V*(z)). h), h E R". Note that we use this notion even for points where the Hessian is not positive definite. However, || || is a well-defined norm for x: where f²x(x)) > O, which holds for strictly convex functions.
Along with the global norm in our space,
2 GRADIENT-NORMAIIE
SMOOTHNESS
Our aim is to characterize and approximate the behavior of the gradient field ff(-), induced by objective. Along with it, we denote by H(-) E Ra** the matrix field which assigns to every point x E Rn a symmetric positive-semidefinin matrix which serves as our Hessian approximation, H(x)) R 22 f(x). We will use this matrix directly in our algorithms (see Section and corresponding examples), We would like to use it for the following linear approximation of the gradient field in neigbourhood of the current point:
vf R Vf(x) + H(z)h.
(5)
The examples include: H 42 J, exact Hessian, which provides us with the Newton approximation in 5) or H = 0, zero matrix. The latter case corresponds to first-order methods.
Definitions. For given y > we denote the ball B.y := { hb] S 77. Moreover, employing the local norm, we define the following local region, at point x and for an arbitrary direction g E R":
On.g = { : | + (g. S 0}.
Note that for f²)(x) > 0 this set is an ellipsoid centered around the Newton direction: Oz.g < 191..- = (g. (2x(2=-'gg)) g) ). and its geometry depends on the properties of the objective. For non-convex functions, Oz.g can be unbounded. Nevertheless, we always intersect it with the Euclidean ball By, thus working solely with bounded directions. Using Smoothness:
(h. || 1V=
our local regions, we introduce new characteristic, called the
Definition For any x E RD and direction g E IR", denote
7 g) = maxx {7 2 0 [V + h)) - V (=)) H <
|gll. vh E B, (0
Thus, quantity ((x g) describes the maximal radius of the Euclidean ball around point æ. within which the error of linear approximation of the gradient field (5) is relatively small across all feasible directions h. Note that the local region Oz.g only restricts the set of possible directions, and hence can only improve y(2, g). It appears that including set Oz.g in the definition is crucial to make the modulus of smoothness 7(-) large enough, for second-orded problem classes that we present below.
In order to better understand the definition. let us introduce the fol- lowing univariate function, at a given point æ E R": p(7) := h) ff(x) - H(x>) h1l [ where y 2 Clearly, p(-) is monotonically decreasing. starting from some large limit V value p()). Its graph is shown in Fig. 2 Then, the value of ((xg)) is the intersection of p(-) with the main diagonal. These obser- vations also demonstrate monotonicity in 7: if the inequality from the definition holds for some ? 2 0, then it also holds for all 0 < r S 7, and, by definition, 7(x g) is the maximal possible radius. Among all
f[ minpe
p(>)
(
Vigure 2: plot p(-) for
f(x) e.. In this 7(2)
(e 2) 2) a 1.39 for all x R.
'The limit always exists when f is sufficiently smooth at ac.
4

---

Published as a conference paper at ICLR 2026
possible directions æ, the most important is fx()). For that, naturally define:
((x) = 7(2, Vf(x)).
As we will see in Section 3 (ax) provides us with the right step-size in our algorithm, that automati- cally adjusts the best problem class and the degree of the Hessian approximation V f(x) s H(
at the current point. It is possible to generalize our results to Composite Optimization Problems (Appendix C. which includes constrained optimization and non-smooth regularizers. In this case, we need to use for g perturbed gradient direction, that depends on the composite component.
Basic Properties First, let us consider a stationary point x* which is strict local minimum, so it holds: Vf(=*) O and f(x") ) > 0. Then, by our definition we have ((=") +oo, which means no regularization in our method. This implies that being in a neighborhood of the solution, the algorithm will switch to pure Newton steps, which confirms the intuition that the classical Newton's '
method has the best local behavior. Note that for quadratic functions and setting := V² the
lincarization (5) is exact, and we also have 7 too. At the same time, when ((x) is small, it indicates need for regularization.
Now, we can state how the Gradient-Normalized Smoothness 7(-) changes under simple operations
1. Scale-invariance. Let (2:) be the Gradient-Normalizee Smoothness for function and let g == c.f f for some с 0. Accordingly, we set Hg := cHy. Then, 7/g (2(2)) = (z). Affine substitution. Let g xx) == f(Ax + b) for some invertible A R=** and b R". Set Hz = A H A Aæ x + A. Then, (a(()) 2 (z: ||||
3. Sum of functions. Let f = Ei= fi. Then, 7 is bounded by the Harmonic mean:
(5(x. Z (Ei 7 (x,
T, 9 IR.
Hessian inexactness. Let 7/1 (z)) be the Pradient-Normaliin Smoothness of f when using matrix field H, Let H2 be such that ( H2(æ))l S [V((]]] (12(2)) for certain function 712. Then, the H2 is bounded by the Harmonic mean: (2(xr) 2 (m) + -12(x)-11 -|-1
Smoothness of when using
Examples. Let us study the behavior of 7()) when using the exact Hessian matrix, H 2 under classical global second-order assumptions. Then, employing the known properties, we can translate arbitrary Hessian approximation.
Example (Hölder Hessian). Assume that f has Hölder continuous Hessian of degree E [0, 1]: f(²)(z)) - 22 f(y)ll S L2 - yll",, for all x, y E R Then,
(
1+v L2.-
x.
R
The most interesting are extreme cases: V/ = (functions with bounded variation of the Hessian) and (functions with Lipschitz Hessian) that gives, correspondingly:
(xx) (xx V fz))
[[](]]]
and
(x) = <x, f(x))
/
L2.0
The following problem class was initially attributed to the third-order tensor methods (Birgin et al.
2017: Cartis al. 2019 Nesterov 2021a Agafonov et al.) 2024). Later on, as was shown
in [Nsterov] 202 lb Grapiglia & Nesterov 2021 Doikov et al. 2024a). it appears to be appropriate
for second-order optimization.
Example (Hölder Third Derivative). Assume that is convex and its third derivative is Hölder of degree e [0, 1]: || f(x) - f'y(i)) S La, | - yll", for all x, y E R". Then,
gx, 2
2 L ||11l-)
1+v
2, E R".
Missing proofs provided in the appendix.
5

---

Published as a conference paper at ICLR 2026
Example (quusi-Sef-CConcotlanee)) Assume that is Quasi-Self-Concordee with parameter M 0: (V"f(z) h. u) I M hle a|l. for all æ, h u E R Then,
((x)
M
The following examples of (Lo 1 smoothh functions are popular in the context of studying smooth- ness properties of neural networks, gradient clipping, and trust-region methods (Zhang et al. 2019
Koloskova et al.)
2023 Xie al. 2024).
Example 4 (LL, -m)-shotth functions ZZhang et al. 2019)). Assume that [|V Lo I [z) all a E R Then,
1g Lothi Melll.. (1 + exp
19ll ())))
a; g. E R
Example 5 (Second-order (Mo, -smoohh functions (Xie et al. 2024 Assume that [(²)(x) f (Mo (=)]\[ for all æ, y R" Then,
> z
2 2| [ )² 2, g RR.
In practice, the objective function can belong to several of problem classes simultaneously, and optimal parameters can vary with æ. Therefore, is important that the definition of 7(-) is local, just adjusting universally to the best of these cases. This allows the method to achieve the fastest rate.
3 ALGORITHM
The method is very simple.
Algorithm 1 Gradient- RegullentReguularized Newton with Approximate Hessians
Initialization: E R". for k 2 do 2: Choose H(xx)) ž O and "/k > 0.
b In practice, use adaptive search for (Alg. 3
3: Perform update: F641 < Fg. H(x))) + [ B
f((x))
4: end for
In this algorithm, H(xx)= = H(xx) > 0 could be the Hessian or its approximation, and 7/k > is a second-order step-size. Our theory suggests set 7 = (xx)) which takes into account both the right problem class and the level of Hessian approximation. We can also use an adaptive search to choose the parameter ?/ automatically, that we describe Appendix D
For simplicity of presentation, we assume that at each iteration 2 0 we solve the linear system exactly, which can be done easily in case the matrix H(xx) has simple structure, e.g. low-rank decomposition. We present several practical examples in Section [ In general, using a linear system solver such as the conjugate gradient method, will require only compute matrix- -vecto products of the form Hxx;)) h, for an arbitrary h IR.. Such linear solver will typically have linear rate of convergence due strong convexity of the objective, and therefore it will require only a few matrix-vector products each iteration.
Using the first power of gradient norm normalizing constant is very natural due to several reasons:
This ensures: | æx S Tkk so the steps normalized to be bounded in the Euclidean ball of a fixed radius 7k. as in trust-region methods (Conn al. 2000).
When H f. the first power of the gradient norm ensures local quadratic convergence, as for classical Newton's 's method, and we are interested to choose (locally, being close to solution, we admit 7 +o0, no regularization).
large as possible
When H 0, we obtain the normalized gradient method with fixed preconditioning B:
Øb+1
[
B - f(xx
In this case, theory recovers the standard rates of the first-order smooth optimization.

---

Published as a conference paper at ICLR 2026
Global Progress. With Definition 1
prove the progress for each iteration of Algorithm
!
Lemma 1. Let S 7 S 7(m)). Then
f(ma) [(x++1)
(8)
Inequality ( does not depend on the structure of 7(x)),, showing that Algorithm converges for an arbitrary well-defined Yk- It also important that this method converges for any problem class and for any Hessian approximation, as we did not specify them yet. Notably, for specific problem class and for a specific H, we can lower bound 7()) globally as in the previous section, which yields state-of-the-an global convergence rates. Let us present direct consequence of (8). which is convergence for our algorithm a general non-convex case.
Theorem (Non-Convex Functions). Let K > be a fixed number of iterations and let for every step. Assume that min [[V 2 & and let 7 = min 7 > Then, 15i5K
8 hold
151SK
KL
SFo 7,
+ log Vf(x))ll.
where Fo = f(xa) f
Note that to now we did not say anything about smoothness assumptions on our objective, thus the result 9 very general. Let us assume that (xx)) V2 fxxx) ž O, and that the Hessian is Hölder continuous of degree v E [0, 1], which according to ensures that 7 2 [(1 + v) 11(+()+)) Plugging this bound immediately provides us with the complexity of O(1/e(2t))/00
iterations to find a point such that [*)|| S E. For y = it gives 0 which corresponds to the rate of the cubically regularized Newton method (Nesterov & Polyak 2006). and for every 0 v S this complexity is strictly better than O11/=²) ) of the gradient descent (Nesterov) 2018). In the next sections we show the advanced convergence rates for our methods, under structural assumption on (-)), that will recover state-of of-the-art rates in all particular cases and allow for inexact Hessians.
4 GLOBAL CONVERGENCE THEORY
Structural Assumption on 7()). Let us assume that the Gradient-Norrmalized Smoothness 7(-) from Definition | admits the following structural lower bound, which is the harmonic mean of monomials of the gradient norm.
For i, there exist fixed degrees 0 S a, S and nonnegative coefficients (Mi- such that:
(x) 2 <([V[()))1+) =
Σ
d
M Mi-0; [[V(@))
min Isdd
[( Mi a
(10)
Here, the coefficients [M Josazı serve the main complexity parameters. Note that all our
Examples from Section 2 satisfy this assumption. Examples 123 x (+)((=)))..) | [x))))
M for a [0, 1). is a simple monomial, and the structure 10 is preserved under all basic operations with functions, such as summation. In what follows, show that the lowest of the degrees of π (-) characterizes the class of smoothness, while additional exponents contribute to inexact Hessian (see basic properties in Section 2 and examples in Section 5). Defining the coefficients of a (IIV (=))l)) from the set (M,- 0 a S 1}. where M₁-a corresponds to the smoothness constant of some problem class, we automatically set the state-of-the thethe--trrrrrrree art convergence rates for many
partial (see Table
Functions), Let us choose " (xxx) in Algorithm or by perform- ing adaptive search. Under assumption (10), we can bound 7, 2 T()). Therefore, ensure min fx:))) < & is enough to perform a number of iterations of
Corollary
ISKK
K
[&dFo
max Mi-a; ISiEd ctt, + log
| [[a))
gisa og and introduce the following complexity Convex Minimization. Let define mini
7

---

Published as a conference paper at ICLR 2026
C(e)
max 1sid
Mi Mi-a, Docti
#/2 F
for a > 0,
(11)
and for - 0, we have the limit C(e) = d dmxxi Mi-o, Dr
gd log ( For the particular
cases H V and H 0, thus performing the full Newton method or performing the gradient descent, we denote the corresponding complexity by CNEWTON and by Can(E). Note that our theory covers these two important cases well. We show that complexity C(e) is the number of iteration required by Algorithm| to find the global solution, reflecting dynamics of Algorithm 1 and its ability adapt to the right problem class. We denote by D == {sup | x=1| f(x) S f(zo)) the diameter of the initial sublevel set, which we assume to be bounded. We establish the main result.
Theorem (Convex Functions). Let us choose T 7(xx) in Algorithm [ or by using an adaptive search. Let f be convex. Then, for any > 0, to ensure f(xx) xx5 it is enough to perform a number of iterations of
C((=) + 2 log [
K
We extend this result for more general classes of gradient- domdintted functions, that include strongly convex objectives and functions satisfying PL-condition, as well as improved rates for the gradient norm minimization, which we include in Appendix
Recovering Rates for Particular Problem Classes with >(x). To highlight the power of our result, let us consider a simple monomial 7(x) 2 =(IVV(())Il)) = [V] for some
a and M1 - >> For simplicity, we always assume K log |/(a)]||_D Then, in view of Theorem 2 and (II). we have the complexity of O(L/E"), for a 0, that corresponds to the convergence rate inherent to problem classes from Examples I complexity K (M, D) yields the rate of the Newton method with the Gradient Regularization on Quasi-Self- Quasi-Self-Concordaan functions (Doikov) (023). As we see, Theorem allows to obtain variety of convergence rates by plugging an appropriate global lower bound for 7(xx). Appendix G show how the lower bound x ([] [xx))] varies with the problem class. Corollary 7 shows how state-of-the- the-hh--ttrttt art rates for different problem classes are unified by our choice of (xxx) in Algorithm
In case a = 0, the
EFFECTIVE HESSIAN APPROXIMATIONS
Our theory automatically covers setup with inexact Hessian. From Corollary we see what happens to the rate when (xx) is lower bounded by simple monomial. However, the case where v[[V f=)]l=) is not monomial is also interpretable with our theory. Corresponding convergence rate aligns with that of a second-order method with approximate Hessian, where the approximation already covers this case with the complexity of 11 for ((x) being bounded as in (10). However, some important practical cases of
error is bounded by some polynomial of / [=(()] Theorem 2
Hessian approximations can be described with much simpler condition
- < C1 +2+C211())11++
0 0
(12)
We provide examples of such H(x)) that are particularly useful for machine learning applications. See extended examples in Appendix
Example (Separable Optimization). Let for convex nonnegative loss function. Consider logistic regression, E(t) = log(1 + exp(t). Set B = Ein 1 a.a.T Then, for the following Hessian approximation
f((x), where f((x) := ((a,, x) b,),
H(x)
= Σ Vf(())Vf((xT = Σ (e((a,,)) - (a))²aaa = 0,
we have 1 H(x)ll S f(x) DIV[S(>)11 + for Fo
8

---

Published as a conference paper at ICLR 2026
Example 7 (Nonlinear Equations), Let E= - R be nonlinear operator, and set f(x) == ||[u())]l* (Gu(z), u(z)) for some G = G 0 and p 2. For this objective, use:
(())
[ (u(z))ll~2u(((a Vul GVu(x)
バKm v(())V((2)
= 0. (13)
Assuming Pu = p and [[)'( S L1 for some μ4, & 0, we have: [V))(x)) H()) s G//u())11=1
s & (VV(())]
(14)
Example 8 (Soft Maximum). In applications with multiclass classification, graph problems, and matrix games, we use f(x)) : s(u(x)), where RR - Id is an operator (e.g. a linear or nonlinear model), and s(y) == log Li=1 eV: is the LogSumExp loss. Note that s(-) is
ea Quasi-Self-Conen Concordat (Ex.) 3) and [Vs(y)], Ei=re 55 is softmax. For this objective, we can use the following approximation of the Hessian in our algorithm:
H(x) = Vu(x) (3s(u(z))VVu(a) = 0.
Assuming that Vu(z:BB č μt and (x))l S E1, for some &,, O, we have:
f(x) H())l s {][Vs(u(())] I vp [f(x))l.
Connection between Gradient-Normallin Smoothness and the Hessian bound 12 According to the "Hessian inexactness" property of 7(),, assuming 12 the Gradient Normalized Smoothness is bounded as: ((x) 2 (x) + [
where 71 (x) is the Gradient Normalized Smoothness for the exact Hessian. In other words, if we know the lower bound T for the exact Hessian (c.g. any of the problem classes above), then TT-) for the method with inexact Hessian can be computed in form that satísfies the structural assumption TO] And immediately obtain the complexity result for the method with inexact Hessian (Corollaries) 2 and (3.. We see that the total complexity of the method becomes the sum of the complexity for the exact case plus two additional terms that depend on C₁ C2, and the degree of approximation 3. Fig. shows the interaction of the minimal degree of the monomial in (-) and from Equation 12) And Corollary finalizes Table !
C,
C.
holds. Then, for any E > 0, to ensure f(xx) - S E, it enough to perform a number of iterations of
Corollary 2 (Inexact Hessian: Convex Functions). Assume that condition 12
K = Ö(CNEWTON(E) + C2 + Canita
where Ō(-) hides logarithmic factors.
Corollary (Inexact Hessian: Non-Convex Functions), Assume that condition 12) holds. Therefore, to ensure min [|V I it is enough to perform a number of iterations of 19SK
88F. (a max Mi-a;
K [
Isidd elta. + C2 + git8 52
+ +log [VV[(=))]
6 EXPERIMENTS
Let us present illustrative numerical experiments that validate our theoretical findings. Extra experi- ments are in Appendix and the code available at: httpp://githhb.... httpss//gthuu..cm//ppmm//gggggg http.//ppim/gggaaoooonnmmoemeoo
Exact Hessian. In Figure 3 (a), we show convergence of Algorithm I with exact Hessian on
the Softmax problem (LogSumExp) with linear models. We compare our adaptive search rule 7h = ><<x) (see Lemma [} with the strategies from Doikov et al. (2024a). We see that our theory predicts the best value of 7/k- which also serves an upper bound on empirical values of other adaptive search procedures (b). In (c), compare our method with the gradient descent the problem from Example Our adaptive search denoted by "Func. Search". As a Hessian approximation for LogSunExp, use Equation [19

---

Published as a conference paper at ICLR 2026
Exg
LouSunnEpp
Nonlinent Equations
101
by brats boaad breTisST
10"1
10--2
5,
10-1
10-
10-4
Pout too Puer Stach
101"
Fraeh
22-4
Boant
10-1
Post Mow. Der
Fraes Crudl 1/M
23-1
Pout too (Deil Boarc (10
Free Mine Crull Soare zu 2
100
200 300
402
302
100
200
300
300
300
20 Benkars
76
206
(a)
(b)
(c)
Figure 3: Convergence of our methods. We see that the second-onde methods show outstanding performance, confirming our choice of the step-size *kk
Inexact Hessian. Our theory is compatible with different Hessian approximations we present Ta- 2 In Appendix H we prove the bounds of || [=x) H(x))ll for these approximations, Notably, condition 12 does not necessarily hold for all approximations considered; however, Theorem 2 allows us to derive the right convergence rate. We extensively evaluate methods on both convex and non-convex benchmarks, including extensions of the Rosenbrock function Rosenbrock (960) and difficult problems that involve Chebyshev polynomials Güübüüballban & Overton (2012); Cartis ett al. 2013). In Appendix [B] we also examine adaptive search, convergence, wall-clock time, and the numerical stability of our method with inexact Hessian all problems from Table 2
Table 2:
Hessian upprosimations aligned with our theory, evaluated on convex and non-convex problems. Importamly, when (1))) is linear operntor, the "Inexact Hessian" turns
full Hessian. Thus, we use "Fisher Term H." that case.
Problem
Naming
Approximation
LogSumExp 15
Weighted Gauss-Newton
LA Diag (solimax (A, A
Equations with lincar operator
Fisber Term H
(()
Nonlinear Equations & Rosembrock
Inexact Hessian (Example
[[(aa] GVu(a) [لE V(a)
Nonlincar Equations & Chebyshev polynomials 24
Inexact Hossian (Example
[u[e]]" TT(eaaTTVVaa GVu(a) (uuC V((x)//aa)
7 DISCUSSION
We introduced the notion of Graaieet-NNormalized Smoothness, 7(x), which treats the level of smoothness and the Hessian approximation error in unified manner, leading to fast global rates for both convex and non-convex problems, and recovering various smoothness assumptions such as Quasi-Self-Conoordan objectives. is interesting to note that, in the
Hölder continuous Hessian case where the Hessian approximation satisfies bound (12) with 3 0 and C₁ ~ O, the convergence rate of the method with an inexact Hessian is the same as that one of the full Newton method.
For example, for the logistic regression with the Fisher approximation of the Hessian (Example 6). we are able to establish the global linear rate of convergence the case where the data is well- separable (f* z 0), complementing previously known results for gradient descent methods (Axiotis)
Sviridenko 2023) and for Newton-type methods (Karimireddy et al.) 2018 Carmon al. 2020
Doikov 2023 Our theory extends beyond this setting to soft max and of non-linear models.
Another interesting example the power loss function, f(x) = || As we show in Section
this function is both generalized self self-concordant and uniformly convex. These properties ensure an automatic global linear rate of our method for all p 2 2.
While in this work we discuss only basic versions the method, it is known in Convex Optimization that algorithms can be accelerated, achieving optimal convergence rates (Nesterov) 2018). Developing accelerated versions of our methods that automatically adapt to the problem's 's smoothness, as in (Carmon al.] 2022), while simultaneously adjusting to the potential inexactness in the Hessian, is an interesting direction that we leave for future research. It is also interesting to compare our results with recently proposed anisotropic smoothness (Laude & Patrinos 2025). Æ-smoothness (Li eet al. 22023 Tyurin 22024), and recent advances on global convergence rates for the damped Newton method (Hanzely al. 2024). We leave these comparisons for further investigation.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the Swiss State Secretariat for Education, Research and Innovation (SERT) under contract number 22.00133.
REFERENCES
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáč. Inexact tensor methods and their application to stochastic convex optimization. Optimization Methods and Software, 39(1):42-55) 2024.
Michael Arbel, Romain Menegaux, and Pierre Wolinski. Rethinking Gauss-Newton for learning over-parameterized models. Advances in neural information processing systems, 36:33379-33402 2023.
Kyriakos Axiotis and Maxim Sviridenko. Gradient descent converges linearly for logistic regression separable data. In International Conference Machine Learning, pp. 1302-1319, PMLR, 2023.
Francis Bach. Self-concordant analysis for logistic regression. 2010.
Heinz Н Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-344 348, 2017.
Ernesto G Birgin, JL Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Ph Toint. Worst- case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Progrumming, 163:359-368, 2017.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33: 33:19052-19063, 2020.
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive Monteiro-Svaiter acceleration. Advances in Neural Information Processing Systems, 35: 20338-20350 2022.
Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming, 169:337-375, 2018.
Coralia Cartis, Nicholas IM Gould, and Philippe I. Toinn. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming, 127(2)225--255, 2011a.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity. Mathematical programming. 130m)in 130(2):295-311 201
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the oracle complexity of first-order and derivative-fiee algorithms for smooth nonconvex minimization. SIAM Journal on Optimization, 22 (1):66-86, 2012.
Coralia Cartis, Nicholas L.M. Gould, and Philippe Toint. note about the complexity of minimizing Nesterov's ' smooth 451 457, 2013. doi: 10. 100.100000005778..0000 inward/ www.://reerrr..oo uri 2012. 222e2222000000000000000000033333
function. Optimization Methods and Software, 28(3):
201.5777788.11222226633 / http:://wwwwwwww....pptt com/
Cited by: 1; All Open Access, Green Open Access.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Universal regularization methods: varying
the power, the smoothness and the accuracy. SIAM Journal on Optimization, 29(1):595 -155, 2019.
11

---

Published as a conference paper at ICLR 2026
Chih-Chune Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol., 2(3), May 2011. ISSN 2157-6904. doi: 181144//999119999611111 198899999999999 URL
httpss:/doo www./r/g.oooo 1Tt...11111111111.1111 1961199
El Mahdi Chayti, Nikita Doikov, and Martin Jaggi. Unified convergence theory of stochastic and variance-reduced cubic Newton methods. arXiv preprint arXtv:2302.11962. 2023.
Andrew Conn, Nicholas IM Gould, and Philippe Toint. Trust region methods. SIAM, 2000.
John E Dennis, Jr and Jorge J Moré. Quasi-Newton methods, motivation and theory. SIAM review, 19(1):46-8) 89, 1977.
Nikita Doikov. Minimizing quasi-sell-cooccrrdant functions by gradient regularization of Newton method. arXiv preprint arXiv:2308. |4742, 2023.
Nikita Doikov and Geovani Nunes Grapiglia. First and zeroth-order implementations of the regular- ized Newton method with lazy approximated hessians. Journal of Scientific Computing. 103(1):32, 2025.
Nikita Doikov and Yurii Nesterov. Minimizing uniformly convex functions by cubic regularization of Newton method. Journal of Optimization Theory and Applications, 189(1):317-33, 2021.
Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. Mathematical Programming, pp. 1-25, 2023.
Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. Mathematical programming, 204(1):1-22 2024.
Nikita Doikov and Anton Rodomanov. Polynomial preconditioning for gradient methods, 2023. URL https://erxiv: owg.oogg///oooo.oooo atsp////s/2211
http://arxx...orr////////3//// 13194
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized Newton method. SIAM Journal on Optimization, 34(1):27-56, 2024a.
Nikita Doikov, Sebastian U Stich, and Martin Jaggi. Spectral preconditioning for gradient methods on graded non-convex functions. In ICMI., 2024b.
Ilyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimiza- tion under global Systems, 35: 15:15566-188 2022.
inequality. Advances in Neural Information Processing
Curtis Fox, Aaron Mishkin, Sharan Vaswani, and Mark Schmidt. Glocal smoothness: Line search can really help! arXiv preprint arXiv:2506. 2025.
Elias Frantar, Eldar Kurtic, and Dan Alistarh. M-fac: Efficient matrix-free approximations of second-order information. Advances in Neural Information Processing Systems, 34:44833-14886, 2021.
Terunari Fuji, Pierre-Louis Poirion, and Akiko Takeda. Randomized subspace regularized Newton method for unconstrained non-convex optimization. arXiv preprint 0440: 2022.
Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (I 0, / 1) -mosohh optimization: Clipping, acceleration, and adaptivity. arXiv preprint arXiv:2409. /4989, 2024.
Robert Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. Rsn: randomized subspace Newton. Advances in Neural Information Processing Systems, 32, 2019.
Geovani Nunes Grapiglia and Yurii Nesterov. On inexact solution of auxiliary problems in tensor methods for convex optimization. Optimization Methods and Software, 3601):145-170. 2021.
Geovani Nunes Grapiglia, Max LN Gonçalves, and GN Silva. A cubic regularization newton's method with finite difference hessian approximations. Numerical Algorithms, pp. 1-24, 2022.
12

---

Published as a conference paper at ICLR 2026
Serge Gratton, Sadok Jerad, and Philippe L Toint. A fast Newton method under local lipschitz smoothness. arXiv preprint arXiv:2505.0453 2025.
Andreas Griewank, The modification of Newton's 's method for unconstrained optimization by bounding cubic terms. Technical report, Technical report NA/12, 1981.
Mert Gürbüzbalaban and Michael L Overton. Nesterov's nonsmooth Retbyyshv--Roenbbooe functions. Nonlinear Analysis: Theory, Methods & Applications, 15(3):1282-1289, 2012.
Slavomír Hanzely. Sketch-and -ndreejeeddtttetttte meets Newton method: Global O(1/k22) convergence with low-rank updates. The 28th International Conference on Artificial Intelligence and Statisties, 2025.
Slavomir Hanzely, Dmitry Kamzolov, Dmitry Pasechnyuk, Alexander Gasnikov, Peter Richtárik, and Martin Takác. A damped newton method achieves global o(1/k-2) and local quadratic convergence rate. Advances in Neural Information Processing Systems, 35:25320 25333444,3,, 2022.
Slavomir Hanzely, Farshed Abdukhakimov, and Martin Takáe. Newton method revisited: Global convergence rates up to o(k33) for stepsize schedules and linesearch procedures. arXiv preprint arXiv:2405. 18926, 2024.
Florian Jarre. On Nesterov's smooth Chebyshexv-Rosenbrock function. Optimization Methods & Software, iFirst, 12 2011. doi: (0.1080000556788.011...33
Yuntian Jiang, Chang He, Chuwen Zhang, Dongdong Ge, Bo Jiang, and Yinyu Ye. Beyond non- convexity; A universal trust-region method with new analyses. arXiv e-prints, pp. arXiv-2311, 2023.
Qiujiang Jin and Aryan Mokhtari. aon-asymptotic superlinear convergence standard quasi-Newton methods. Mathematical P Programming, 200(1):425-473, 2023.
Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of BFGS with the Armijo-Wor Wolfe line search. arXiv preprint arXiv:2404. 16731, 2024.
Nocedal Jorge and J Wright Stephen. Numerical optimization. Spinger, 2006.
Alireza Kabgani and Masoud Ahookhosh. Moreau envelope and proximal-point methods under the lens of high-order regularization, 2025. URL
C4577
Dmitry Kamzolov, Klea Ziu, Artem Agafonov, and Martin Takáč. Cubic regularization is the key! the first accelerated quasi-Newton method with a global convergence rate of O(k"-2) for convex functions. arXiv preprini arXiv:2302.049985 2023.
Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Global linear convergence of New- ton't 's method without strong-convexin or Lipschitz gradients. arXiv preprint 1806.0080 2018.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343-1736; PMLR, 2023.
Frederik Kunstner, Philipp Hennig, and Lukas Balles, Limitations of the empirical fisher approx- imation for natural gradient descent. Advances in neural information processing systems, 32, 2019.
Emanuel Laude and Panagiotis Patrinos. Anisotropic proximal gradient. Mathematical PwtptnaatiaaaPoPPaaeaia Programming, pp. 1-45, 2025.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 012400238402777 2023.
Haihao Lu, Robert Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal Optimization, 28(1):333-3555 3544, 2018.
13

---

Published as a conference paper at ICLR 2026
Cong Ma, Xingyu Xu, Tian Tong, and Yuejie Chi. Provably accelerating ill-conditioned low- rank estimation via scaled gradient descent, even with overparameterization. arXiv preprint arXiv:2310.06159, 2023.
James Martens. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 21(146):1-76, 2020.
A Woodbury Max. Inverting modified matrices. In Memorandum Rept. 42, Statistical Research Group, pp. 4. Princeton Univ., 1950.
Konstantin Mishchenko. Regularized Newton method with global O(1/k²) convergence. SIAM Journal on Optimization, 33(3):1440-1462 2023.
Aaron Mishkin, Ahmed Khaled, Yuanhao Wang, Aaron Defazio, and Robert M. Gower. Directional smoothness and gradient methods: Convergence and adaptivity. Advances in Neural Information Processing Systems, 2025.
http//bb//2/333 04081
Arkadi Nemirovski and David Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Modified Gauss-Newton scheme with worst case guarantees for global performance. Optimisation methods and software, 22(3):469-443, 2007.
Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, 152(1):381-40) 2015.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programminng 186:157-183, 201aa.
Yurii Nesterov. Superfast second-order methods for unconstrained convex optimization. Journal of Optimization Theory and Applications, 191:1-30, 2021b.
Yurii Nesterov. Primal subgradient methods with predefined step sizes. Journal of Optimization Theory and Applications, pp. 1-33, 2024.
Yurii Nesterov and Arkadi Nemirovski. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical programming. 108(1):177-20S, 2006.
Boris Polyak. Newton's method and its use in optimization. European Journal of Operational Research, 1896) 2007.
Roman Polyak. Regularized Newton method for unconstrained convex optimization. Mathematical programming, 120:125- 2009.
Anton Rodomanov. Quasi-Newton methods with provable efficiency guarantees. PhD thesis, PhD thesis, UCL-Université Catholique de Louvain, 2022.
Anton Rodomanov. Global complexity analysis of BFGS. arXiv preprint arXiv:2404.1505) 2024.
Anton Rodomanov and Yurii Nesterov. New results superlinear convergence of classical quasi-
Newton methods. Journal of optimization theory and applications, 188:744-769, 2021.
H. H. Rosenbrock. An automatic method for finding the greatest or least value of a function. The Computer Journal, 3(3): 01 1960. ISSN 0010-4620. doi: 10.1099/commjm/33..17. URL
https://dbi..om 1ttt:///0...13//ooooooooooo.. 3.155
Damien Scieur. Adaptive quasi-Newton and Anderson acceleration framework with explicit global (accelerated) convergence rates. In International Conference on Artificial Intelligence and Statistics, pp. 891. PMLR, 2024.
14

---

Published as a conference paper at ICLR 2026
Tianxiao Sun and Quoc Tran-Dinh Generalized selo-coonordannt functions: A recipe for newton-type methods, 2018. URL
Alexander Tyurin. Toward a unified theory of gradient descent under generalized smoothness. arXiv preprint arXiv:2412.1177,, 2024.
Kenji Ueda and Nobuo Yamashita. A regularized Newton method without line search for uncon- strained optimization. Technical Report, 2009.
Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U Stich. Optimiz- ing (L-0, smoohh functions by gradient methods. arXiv preprint arXiv:2410.1003 10000000000000, 2024.
Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust region methods for nonconvex stochastic optimization beyond Lipschitz smoothness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 16049-16057, 2024.
Gavin Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for overparame- terized nonconvex Burer-Monteiro factorization with global optimality certification. Journal of Machine Learning Research, 24(163): 2023.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv: 2019.
Jim Zhao, Aurelien Lucchi, and Nikita Doikov. Cubic regularized subspace Newton for non-convex optimization. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
15

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
2
Gradient-Vormalize Smoothness
Algorithm
Global Convergence Theory
5
Effective Hessian Approximations
Experiments
7
Discussion
10
Extended Related Work
18
Experiments
19
B.
Comparison of Adaptive Search Approaches
20
B.2
Inexact Hessian: LogSumExp
20
B.3
Nonlinear Equations: Studying the Degree of Smoothness
................................
24
B.4
Non-Convex Objectives
27
B.5
Comparison with Adaptive and Universal Methods
31
Composite Optimization Problems
32
Composite Newton Step with Hessian Approximation
32
The Algorithm for Composite Optimization
34
The Choice of the Regularization Parameter
35
D.I
The Constant Rule
................................
35
D.2 The Method with Adaptive Search
36
Convergence for Non-Convex Functions
38
E.1 Convergence for Inexact Hölder Hessian
39
Improved Rates for Dominated F Functions
39
Applications
42
G.1
Functions with Hölder Hessian
43
Convex Functions with Hölder Third Derivative
43
G.3
Quasi-Self-Concordant Functions
44
Generalized Self-Concordant Functions
45
G.5
(Tn, [.) -moothh Functions
47
16

---

Published as a conference paper at ICLR 2026
G.6
Second-Order (Mo. M1) -mmoohhh Functions
48
Bounds on Effective Hessian Approximations
49
H.1
Soft Maximum
49
Nonlinear Equations
H.3
Separable Optimization
53
Recovering Complexities for Practical Approximations
54
17

---

Published as a conference paper at ICLR 2026
A EXTENDED RELATED WORK
Connections and differences with other methods with gradient regularization.
We propose Algorithm| [] with the only hyperparameter seraaraameeee--ssdd--reeeeeee this step-size has an immediate natural interpretation of the radius of the ball within which we can rely on our approximate model, similarly in spirit trust-region methods (Conn al. 2000). However, instead of directly adding the ball constraints into minimization of the model, we apply the gradient regularization technique, considered in (Polyak] 2009; Ueda & Yamashita 2009 Mishchenko) [003] Doikov & Nesterov 2024). This technique simplifies every step of the method, requiring to solve only one linear system per iteration. As compared these previous works, we do not require to use an exact Hessian. We show that the inexactness condition on the matrix aligns well with the smoothness condition of the problem class, and our method works a universal manner among the widest possible range of smoothness conditions.
second-order step-size 7k- Importantly,
In (Doikov et al. 2024a), it was shown that the Newton method with gradient regularization and adaptive search automatically adjusts to the problem classes with Hölder second third derivative, and in (Doikov] 2023), the global linear rate of convergence on Quasi-Sell Sonf-CConc functions was proven for similar method. In contrast to these works, prove universal global rates for
method with inexact Hessian, both unifying analysis from (Doikov et al. 2024a Doikov 2023) and
extending it beyond to the generalized Self- Self-Concordant functions (Sun & Tran- Dinh- 2018 To the
best of our knowledge, our global rates for generalized self-concordant functions are new.
An interesting insight from our analysis is that for different smoothness classes of the objective, we can allow different degrees of Hessian inexactness. Moreover, for popular choices of the Hessian approximations, such as the Fisher or Gauss-Newton approximations, the resulting methods perform as well as for the method with the exact Hessian. Using such approximations ultimately allows us to extend the gradient regularization technique for non-convex problems.
For the choice of the second-orde step-size Nko we consider three possible strategies:
The theoretical choice 7/k (x F" (xx:)) which is the best local value at æ& following our Definition
The constant choice, "'k- = Y, for a certain value of 7 > O (see Section D.I). Our value of 7+ is defined for wide range of classes. However, despite seemingly conservative, this rule recovers all state-of-the-art rates for the Newton method with gradient regularization, including those from (Doikov et al. 2024a Doikov 2023). To the best of our knowledge, this constant choice is new.
Adaptive search to ensure the progress from Lemma I We discuss this strategy deeply in Appendix D.2 Importantly, our Algorithm [ with adaptive search is equivalent to the Super-Universa Newton Method from (Doikov et al., (2024)). However, we use a different stopping condition in the adaptive search: we follow the condition based on the function value, while Doikov et al. (2024)) ensures different inequality condition is also suitable for non-convex problems.
Thus, our stopping
From the theoretical perspective, equipped with the notion of Gradient-Normallnn -oormalized Smoothness, we cover the complexity results of the Universa method, and extend the analysis to the Quasi- Self-Concordant functions (Doikov) (023) and furthermore, to the generalized Self-Concordant func- tions (Sun Tran-Dinh] 2018). Thus, even for the exact Hessians, we cover all results from (Doikoy et al., 2024a Doikov 2023). and enhance them with the undiscovered rates for the generalized Self-Concordant class. Our framework also covers recently popular for the first-order methods (Lo. L (i)ffuccions (Zhang et al. 2019), and beyond. The breadth of rates for second-order methods covered by our framework (see Table I is unmatched in the existing literature.
First state-of-the-art rates for inexact Hessians.
The main power of our framework is the ability to automatically obtain the best rates for inexact Hessians. Moreover, thanks to Gradient-Normaliznn
Smoothness and the structural assumption 100
we derive these results for convex (Theorem 2 and non-convex (Corollary D objectives for free. We
additionally use condition (12 that connects the eиror coming from the Hessian inexactness with the gradient norm. We find such a condition very appealing for some practical Hessian approximations
on fundamental problems such as logistic regression and softmax. Condition (12) allows to write
18

---

Published as a conference paper at ICLR 2026
complexity results with inexact Hessian in compact and feasible manner. Combining both * and
Eq. (12)
we study the interplay between the smoothness class and the Hessian approximation Figure also new result.
Discussions of other types of smoothness.
notion for characterizing smoothness of the objective, we should mention previously established relative (Lu et al., 2018) and anisotropic (Laude & Patrinos 2025) smoothness. While being theoretically appealing, these concepts designed specifically for the first-order methods. Indeed, given a function that is anisotropic smooth or relative smooth (w.r.t. some reference function), and adding quadratic function to this, will generally change the smoothness parameter of the objective. However, our Definition iis insensitive to such perturbations because of the second-order formulation. We also would like to highlight very recently proposed, for the first-order, methods Glocal (Fox et al. 2025) and directional (Mishkin et al. 2025) smoothness. While we define Tradient-Noomaaizee smoothness independently of the problem class in the way use the local information to judge the global behaviour of the method, the authors of Glocal smoothness are inspired by a similar plot. With their framework, occurs that near the solution the curvature is much milder and line search or adaptive step-sizes can take advantage of that by increasing the steps. yielding faster progress in that region. Glocal smoothness allows a fair comparison between complexity results of many gradient-basee based methods, and the authors obtain better peeratiioncompllent bounds compared to using global smoothness only. The authors also claim that Gradient Method with line search can beat the accelerated gradient. These studies worth further investigation.
Since introducing
B EXPERIMENTS
In this section, we explore two main aspects:
how our adaptive search approach aligns with theoretical findings and with the previously established adaptive search variant (Doikov al. 2024a) (see Appendix B.] for experimental details); and
the convergence behavior of Algorithm for inexact and true Hessians (see Appendices B.2 B.4).
B.3
We open-source our code at: httpp::/gghhub.cco/////m///////p norm -oo-ssooooooo----
Setup. We consider two well-adopted problems: LogSumExp and Nonlinear Equations. We use very simple setup for both. We define the LogSumExp problem as:
((x)
plog Σ exp
(a.,
(15)
/
here denotes the i-th row of the design matrix A, and is a smoothing parameter varied across experiments (see Figure (). The Nonlinear Equations problem is:
f(x) 5 |||u()))|P,
where the choice of the operator u(x)) ranges from the linear model (Appendix B.3). non-convex problems - Rosenbrock function, Chebyshev polynomials (Appendix B.4).
For the basic examples in the main part and in Appendix BB33 that can be run on real datasets, we utilize the linear operator uxx) Ax - b. The design matrix A and the vector of labels b may represent a real or synthetic dataset. we randomly generate both A and b, we do this by sampling their entries independently from uniform distribution U [1,1, 1]. In all experiments, our method is run with an adaptive search procedure (see Appendix D) which ensures the inequality (8) and thus selects the best value of 7ik Furthermore, the values of % obtained through this adaptive scheme also serve as upper bounds for the empirical values obtained by the alternative adaptive search strategy studied that Algorithm | with inexact Hessians performs
in (Doikov et al.) 2024a). In particular, similarly to the method with true Hessian on the LogSumExp problem, which also highlights the power of our theoretical result: Indeed, the functions consider in experiments correspond to Examples 7 and 8 and in both cases, this aligns with the C 0 scenario in Table
'We emphasize that there is no need for an extensive comparison between Algorithm and variants of the Newton Method with alteraatiee adaptive search procedures, as the practical improvement primarily lies in obtaining better constant within the adaptive scheme, while the overall convergence pattern remains unchanged.
19

---

Published as a conference paper at ICLR 2026
We the following naming throughout the experiments:
1. Exact Hess., Func. Search or Exact Newton: stands for the partial case of Algorithm ! using our adaptive search procedure (16), and H(x) = fx).
2. Inexact Hess., Func. Search or Weighted Causs-Newton: refers to the variant of Algo- rithm with Hessian approximation of the form (13 or combined with our adaptive search (16p.
3. Exact Hess., Grad. Search, 7k = M. denotes the Gradient- Regdient-egguaaiized Newton Method
with adaptive search as in (Doikov al. 2024a), using * Mr and Mg chosen to satisfy the condition [17.
4. Exact Hess., Grad. Search, 7 = [V[(x))]
denotes the Sradient-Regularre Newton 11 [amx)l- and Mj. is
Method with adaptive search as in Doikov et al. 2024a), using chosen to satisfy the condition
M2
5. Gradient Method: is partial case of Algorithm where ((x) = and B = I, using our adaptive search strategy (16).
6. Gauss-Newton: the Gradient Method with preconditioning matrix B A A, also combined with our adaptive search (16).
To demonstrate that theoretical findings reflected in practice, validate the effects observed in (Fig. (a, b, c)) on additional standard classification problems from Libsvm (Chang & Lin 2011).
We elaborate further the connection between theory and experiments in the following sections.
B. COMPARISON OF ADAPTIVE SEARCH APPROACHES
First, we compare two different adaptive search procedures. Our approach, that is described in Appendix D and uses condition based on the function value:
f f(x++1)
2
(16)
[V
And the adaptive search strategy from Doikov et al. order to ensure the following condition
2024a where the sequence Mj is selected in
(V 24 2x+1)
Vf II 4M (=())
where Le [
(17)
Importantly, our theory covers this adaptive search scheme as a special case. Specifically, by selecting Ykk as simple monomial æ (Il V (=)]l.) = Mr | f(x))]] we recover the behavior of the method
from (Doikov et 2024a). This connection is formally established in Section 4
From our experiments, we observe nice property of yk: it tends to remain nearly constant throughout the iterations of our method (T). Moreover, our value of Yı. is typically larger than the one obtained by the alternative adaptive search procedure proposed in (Doikov et al. 2024a). For representing 10000000 and set a large factor μ 1, which simplifies the problem and yields more numerically stable and smooth approximation of the maximum function. By varying both μ and the data size, we present in Figures 4 and 5 a comparison of convergence behavior and the training. These results further support our theoretical findings by illustrating how %kk computed via adaptive search procedure, either increases over time remains sufficiently large constant. In both cases, it provides an upper bound for the corresponding ? values observed under other variants of the Newton Method and the Gradient Method (i.e., when H(x) 0).
(Fig. 3 (a)), we use a randomly generated matrix
Smoothness values measured throughout
B.2 INEXACT HESSIAN: LOGSUMEXP
We see that our theory correctly predicts the behavior of the Gradient-Normalizee Smoothness across various practical problems. Now, let us focus on the performance of our Algorithm [ with inexact Hessian. Our goal is to show that our method with inexact Hessian achieves the rate of the full Newton Method and, thus, significantly outperforms the Gradient Method. is known, that preconditioning the gradient descent direction with an informative matrix substantially improves the
20

---

Published as a conference paper at ICLR 2026
convergence of first-order methods. For instance, may consider using method with the inverse curvature matrix B 1 or a family of polynomials (Doikov & Rodomanov (023) as preconditioner
in 1k++1 = 4 7 B
instead of the standard Gradient Method that does not take into
account the physies of the problem and uses B I. Building this insight, outline the method we call the Causs-Newton as our algorithm with
H
ATA.
(18)
Note that the Newton Method with matrix 18) corresponds to the classical Gauss-Newton method for linear models, where the Jacobian is simply A. In [igures[6jand] we show that the Gauss-Newton algorithm significantly outperforms the plain Gradient Method with =
However, our theory suggests that Algorithm | with Hessian approximation that satisfies condition (2) with C₁ 0 should achieve the same convergence rate the full Newton and outperform both the Gradient and Gauss- Newton methods on the LogSumExp problem. For that, we consider the following approximation that we call the Weighted Gauss-Newton:
expl ((a) -
H(x)
1 A Diag (smax (A,z)) A, [smax (A, a))l
(19)
(1a
In other words, Equation (19) corresponds to Equation
(18
with entries of A, weighted by smax (.)
Rdd Since the Hessian of the LogSumExp objective 15 given by
(2((x)
LAT (Diag (smax (A, x)) sinax (A, x) smax (A, xx) )) A H(x) [V(
H(x) #
LAT smax (A, x)) smax (A, x)
we see that with such approximation H (x) we can perfectly match the condition (2) (refer to Appendix H for more details). This is one of the main examples of approximations that are covered
by our analysis.
We show that the Newton Method with Hessian approximation 19 and with 7 selected by an adaptive search (Algorithm 33). performs comparably the Newton Method with the exact Hessian and the same adaptive search procedure, see Figure 6 Moreover, our theory suggests, the LogSumExp objective corresponds to the case C₁ = 0 with C2 > being some constant (see Example S Thus, according the results in Table I which are also visualized in Figure D it places us in the regime where the smoothness of the objective dominates the Hessian inexactness, i.e., we should observe the rate of the full Newton Method for our Algorithm I with approximation (19). We actually this behavior in further examples as well.
21

---

Published as a conference paper at ICLR 2026
a9ta (A R 120011122 0.05)
6Sa (A 18 18
0.06)
10"1
109
10-3
10
10-3
10"
[69)
10
10-1
Exrct Box., Fine Sonth
Insoart Hoe, Pine: Snarch
10-2
10-9
Exsd Bos. Cind. Scurch, //M
Gradieal Method
10-3
ltrtioons
Iterations
Randkm Duta (A & guonxieto 1 1)
Random Data (A 2100001000
109
10a
10a
10-2
10'
10a
[(a)]
Exnct Eiva Finc. Soarh
10
Insoaet Hon. Finr. Seazcs
10:
10
Exect lims, Goad. Smotth, (V MM
Eisa, Sourhh 7
10-2
10
Giadeni Methed
10
300 Herrations
100
200
300
400
500
[terations
Gradient-Normalin Normalized Smoothness (right), An interesting effect we observe Figure 4: LogSumExp objective. Convergence (eet)) Dextibbs eexhibiss sharper convergence the log-scaled plot, corresponding the ligure that. e.g. the ala datase, since Algaritim values start increasing more rapidly than those produced by other adaptive search procedures. Additionally, a9a, we observe an almost perfect
simplicity problem Newton Method only 8 iterations to converge). Notably, we also observe a predictable, rapid decrease in 7 for the Gradient Method on a relatively hard problem 30 herations of Newton Method converge).
between
approximation, likely
Racidom Data (A E R 1000
0.1)
Bandom Data (A B2 12000000000 0.1)
102
10a
Reset Hine.,
109
Gonss Swadh
Inssect Hass. Puik
Gradient Method
<
10
10-4
10a
10-4
Dost Hees, Fune, Sourch
Ineset Hoss, Func. Smorth
10-8
Genni-Neraan Goallent Mieled
10
200
300
400
500
600
3000 Iterations
600
Iterations
Figure 5: LogSumExxp objective. Convergence (left) and the Gradient- Normalized Smoothness (right). In the left figure, may observe almost identical performance of Gradient Method and Gauss-Newtion on sufficiently hard task (>> 150 itcrations of Newton Method to converge). However, sluwly tham those lore Gradient Method. For our future experiments, this indicates particular power of Gradient Method with Causs Causs-Newiod preconditioner adupts better to physies the problem.
Gradient-Normalzzed
the empirical values of Gradient-Normalzzed Smoothness for Gauss-Newton decrease significantly more
22

---

Published as a conference paper at ICLR 2026
covtype (A 22000121
22 0.30)
lncos--comer (A 3253K 0.06)
Randomn Data [A cB g.ndudes 0.11
10-1
Weigooad Caass Neattn
10
10-3
Grulast Methad
2020
10-5
10-7
10-7
10-5
Wriginad Chean Secton
10
Wrighted Gares Nouttoo Cazzo-Nexdte
Garae-Neatttn Netaton
10-11
Gualiaa Mellae
10-12
00-6
Gradiez Mielooi
20:0
UK:
010)
900
10.0
0
100
200
2101
400
100
800
1000 2000 3000 4000 5000 6003 7000 Bbenttoon
Teerstions
Bendlions
adto [A R 122
0.05)
jonoephice (A 2
0.06)
Random Data (A ga0x11) 0.05)
10-2
Fort Nexdon
10'
10-3
Weigfoa Nesten
Graaso Nortoe.
-0-3
10-5
Gradiett Metlad
10-4
-0-2
1000
10m7
Pose Neaton Nexton
10
Post Nowton
10:10
Weighte Novton
Cazano Noutto
-0-1
Garao-Nexttan Gralier Mielhor
13
Gradiee Methoo
200
UKC
600
900
1000
25
75
100
125
150
175
200
0
1000
2000
3030 1030 5000 5000 lrenstoor
Incritioss
Bondiias
plishhng e Qul0dseeaa el (.06)
gaeesa3) f 0.05)
Random Data (A Ruonerre
1
10
Esset Neston
10'
10
Gaaan- Nor
Weidiia Neato-ootto
10-1
10-
10-5
Gradans Meilaol
10-3
((0))
10-7
Boot Noston
10
Exxct Neeben
10
Wisglted
Nowtin
10:11
Curuo:
Wrightal Carpe Neator
13:11
10-3
Gradinet Mirlaed
Crodisa Methed
000)
Iicrutious
[teeations
Itcnotions
1700-777
mushrooms (A Raror (L0G)
102
13
10:1
10-2
13-3
10
10-7
Eost Seeliu
Exaci Novion
30
Weiteel Seylin
13-7
Weeshad Carten
Gazzo Nowtts
Grodasi
10
Glackall Michod
10-3
175
Vigure LogSumExp oljjcttvve method with approximation noticeably oulperforms both Gradient Method its Gauss-Newton preconditioned variant, According to theoretical results, this problem falls into regime where the convergence rate matches that of the Jull Newion method. Indeed, we observe consistent convergence behavior between the Exact and Inesact variants of our method actoss a wide range of examples.
23

---

Published as a conference paper at ICLR 2026
B.3 NONLINEAR EQUATIONS: STUDYING THE DEGREE OF SMOOTHNESS
Let us consider a setup with the Nonlinear Equations objective defined in Example 7
(xx c [ = 1 p (G((x)) u(x))
= > 0, p 2 2.
The Exact Case. First, we study the case of the linear operator u(.). We elaborate the nonlinear case in Appendix B.4 Here, the Hessian approximation H(x) suggested by our theory is equal to the true Hessian if the operator u(x²) is linear. Indeed, from Example 7 and taking into account that
u (r)
Aa b and V 0, we have
f(x() = [u(=)]| T GA
p-2 || |
Vf(z)Vf(()T = H(x).
(20)
Thus, we demonstrate the comparison of the exact Newton Method with the Gradient Method and the Gauss-Newton Importantly, if 2. H(x) appears to be the scaled Gauss-Newton matrix, while for any p > 2 also have an additional rank-one term. As increasing p complicates our problem, in this experiment we vary the power p. starting with a simple quadratic problem, p = 2, and extending up to p 5. Our results show that, for all values p considered, the Gradient Method preconditioned with the curvature matrix B = A A performs comparably to, or even outperforms, the variant of our algorithm that uses the full Hessian V2 H(z). This observation highlights significant consequence of our theoretical analysis, particularly in relation to Example
Towards Inexact Hessians for Linear Operators. Nevertheless the Hessian approximation H(x) suggested in Example 7 equivalent to the exact Hessian when the operator u(-) is linear, one still can treat this matrix as a sum of two: a rank-one term [u(e]]
p-2 V (=)) [(x)) and the summand with
Jacobians [u( ( ||0- A BA. The latter term can be viewed as the Gauss- Newton preconditioner
scaled by [u(r)) p-2 while the last ferm corresponds to the Fisher approximation up to multiplica- tive factor [[[=]]| Hence, can consider those chunks of the Hessian H(x)) from Example 7
a potential approximations. While usage of the scaled Gauss-Newton term of H(x) resembles the Causs-Newton method from our previous experiments, the Fisher term of H(x) arouses interest. Therefore, in this part of our experimental validations, we consider the Exact Newton Method, Gradient Method and the following algorithm
3b+1
[ 1 V ((x))
A ATA)
V((x)).
(21)
7k
Le.. the derived update corresponds to the Gauss-Newton method with rank-one correction. In experiments, we call this method Fisher Term of H.
We run the comparison of methods on the same the Nonlinear Equations problem on MNIST and a small, randomly generated dataset. Note, that for the random dataset, we chose exactly the same runs of the Exact Newton and the Gradient Method as in Figure 7 Results for this experiment are Importantly, our version of Algorithm with Fisher approximation not only achieves the comparable convergence as the Exact Newton, but also way more faster in terms of the wall-clock time. In Figure 8 we show that our method with the Fisher-type approximation consistently outperforms the Gradient Method and, in some cases, even the Exact Newton Method, while having almost as cheap per-iteration cost as the Gradient Method, especially if the problem is a small dimensional.
in Figures g and 9
We pose that, in practice, the most time-consuming part of computations for Algorithm with approximation from (2)) are in the inverting of the A A. however the overall computational time can be significantly accelerated via the usage of the Woodbury-Sherme See-Saa-MMorrssoo formula (Max 1950) to exactly compute the invert in Equation (T). We do this in practice and achieve almost the same speed on small-scale problems, while having an insignificant slowdown on large-scale ones.
Besides the results in Figure X we also investigate the behavior of our method with Fisher-like ap- proximation on the Nonlinear Equations problem varying the power p. Throughout those experiments with modifications of p. we observe a consistent improvement of our method with approximation over the Gradient Method and the comparable performance of it compared to the Exact Newton Method. We summarize our experimental observations in Figure D This result suggests that one of the approximations suggested by our theory (see Appendix H not only resembles the converge of the full Newton, but also is very cheap in per-iteration costs (compared to the Gradient Method), which makes it powerful tool for such problems and verifies theoretical findings.
24

---

Published as a conference paper at ICLR 2026
covtype (A 3 2=
mishrrocus 2
Randam Data. 2.000000 p
107
102
10P
10"
10
1077
10-
Gupee
10
Needon
Gosse Gesse-ierre
10
Gradlen Meihoa
20m32
Groflest Metiall
10-1
Grallen Mittod
10
100
101
wortype (A 5910006
mushhtowoms (A glliie111
Random Data (A pancdon 3)
10+
167
10
Foust Neston
107
104
10P
102
Grxlane Methad
107
[000
10
Gasm Gaamm-Nette
Newtle
10-
Grarbee Methael
10
20
Crodiet Nethoo
10
Ioraliuse
covtype (A C. CARERNA p
comshtooms (A gaiste
Randons Data (A 2 00-500 4)
16f1
169
Nexton
Guse Veutte
20
Geuduet Nithod
10
Gracker Methed
108
1(3g)
20
1GP
10-
L0P
Bost Norton
10-4
10
10-9
100
10
Denciion
Toeatioe
Dermiioos
cowtyper E gatnnze p
meshhrooms (A
p
Randren (A 12
5)
11F
1014
10F
Bazt
10f1
Cralint Metiaal
Griker Method
1013
Bast Bostos
10/
107
10a
10
10
80
89
100
60
50
1000
0
20
21
33
40 Ircnacion
50
50
70
Seratoos
Tterations
Figure 7: Objective with Linear Operator: In this setting, our method identical when using either the exact or inexact Hessian given (0). Notably, the Gauss-Newton presonditioning cnables Gradient Method achiove performance comparable Newton Method. In contrast, the Gradient Method with our adaptive search exhibits significantly slower convergence for large values of
25

---

Published as a conference paper at ICLR 2026
MNIST (A 2200 5)
MINIST (A B R
5)
109
1620
1377
Foot Nexton
Foder
1017
1344
Grudica
1044
4071
101
107
10"
Bbout Novton
100
10
Fiidar Ters of Grubect Mackod
10-3
5
15 Time
20
25
Random Data [A guaian 5)
Random Data (A R 100000
107
Exst Nodtos
Boxt Nexton
107
Videe Tomr I
10P
Grodent Mechel
5.
105
Grodeet Metiod
10F
0
15 Time
20
25
Figure 8: Objective with Linear Operator: Our method with the inexact Hessian of Fisher-type form 21 performs comparably to the
Exact Newion Methud. In this experiment, we compare method [1] with the Exact Newton Method with the Hessian of [0) and the Gradient Method, We utilize objective from Example[] consider instead of the full Hessian 20) only its rank one Fisher type lenn T=(=)77" V ((x) V f(x)) " If additionally we set B = A A inverted fast with by Woodtury-Shermm-MMonn Morrissn formola. Moreover, It appears that such a method performs relauvely similar to the Exact Newton. Indeed, in all cases with large p. both exact and inexact algorithm significantly outperform
large values of which complicates the problem.
our theory suggests, one
Algorithim[]iie the approximation aDove, then wC get matrix
Gradient Method, well the Fisher-type approximation works much faster than the Exact Newton in the wall-clock time companssons. Interestingly, that we also can observe how the difference in the wall-clock time perforaance for the Inctact Newton and the Gradient Method increases with dimensionality of the problem (MNIST versus small synthetic dataset). We that this difference diminishes when the problem small-dimensione since the inversion in 21 happens much faster.
moderate powers p Figure
same time, Algorithm with
Randers Data 12100000 p- 2)
Ratdom Data (A C 1 p-2
10P
13-2
10
1ta)
80-5
60-
10-1
10
Fidar Tina H
Post Nextre
10-11
Exsct Palver Them of Gualise Melled
14
20
30
ED
80
100
0.5
18
1.5
20
25
Turationn
Time
Randers
B 1000000
p-
Racsiom Data (A e giassan p
10
bout Nentre
Bood Ncelou
Gradiee Melhol
Folar Tau of
10
Foler
Grudina Milied
10
10
[ttal
60-5
Roo)
10:
10
10-31
10
20
30
60
100
25
5.0
12.5 159 lia 2008 Time
Deciatioss
Random Data (A 12000200 p
Rondom Data iA gueear
10a
Edaci Nocios
199
Bloot Newten
10a
Grutian Mellad
Foker Ten
10P
Goulusz Matheol
Fedaz Tam of
107
13
10
10
10-3
20 43
120
50
15
Incrsttone:
TTmae
Figure 9: Objective with Linear Operator. Our method with the inexact Hessian of a Fisher-type form 21 performs comparably to the Exact Newton Melhod. this experiment. we that problem in Example 7 with linear operator u(x))
b can also considered via the inexact Hlssiins perspective. Indeed, the update rule for the Exact Newton Method with (20) in this case, resembles comhination of the Gauss-Newton tem and the rank-one Fisher update. However. if one would use the matrix B == A A in Algorithm [] then it is possible gel rid of the Newion lerm use only rank- one correction in (2T) Thus, must computationally expensive part in the algorithm inversion A A. But, with the Woodbury-Shee Sawtur--Shhaa---oriiii done relatively East. As we see, our algorithm with the inexact Hessian not only remains the convergence of the Exact Newion in this case. but also works almost as
formula this inversion becomes particularly cheap operation and can
Gradient Method the wall clock time comparison.
26

---

Published as a conference paper at ICLR 2026
B.4 NON-CONVEX OBJECTIVES
Let us also delve into numerical experiments on non-convex functions. In this part, we consider a simple yet widespread problem of the optimization of the Rosenbrock function (Rosenbrock 1960). And the the Nonlinear Equations problem with the operator being from family of Chebyshev polynomials. The latter example is particularly novel for the experiments and, to the best of our knowledge, has been investigated in practice in the non-smooth case in (Kabgani & Ahookhosh 2025 Gürbüzzalabaa & Overton 2012) (a so-called Chebyshev oscillator problem), and in the smooth case in (Cartis et al., 2013). We extend all prior experimental results on these objectives to the Nonlinear Equations problem with different powers p and usage of the inexact Hessian.
Two-Dimensional Rosenbrock Function. We utilize non-convex smooth objective of the following form
f(z) (1 (1-zx) =1)² 100 (z2 =a)² where == (I1, x22) R
(22)
smooth variant of the Westeroy-Chcbyshen Roweerroosseoockkko func- tion (Gürbüzbalaban & Overton 2012). In scientific computing, this function is used as a bench- marking problem for optimization algorithms. It has unique global minimizer (1, where f 0. This global minimum is inside a parabolic-shaped valley (Figure 12 that is easy to find, but, for the Gradient Method, it takes thousands of iterations to approach the vicinity of the solution (Figure [O).
Note that (22) be
Nonlinear Equations with the Rosenbrock Function. To follow our theoretical justifications, we not only investigate the convergence of Algorithm on the plain Rosenbrock function, but also introduce a new objective that relates to our previous finding and to Example 7
We formalize it as
f(x) = (=)),, where u(x) = (1 I1, 10(x2 =²))²
(23)
We call such operator uaa:) vector of the Rosenbrock residuals and refer the problem of minimizing 23 as Nonlinear Equations & Rosenbrock. For the case = 2, the objective (23
resembles (2 up constant factor 1. thus both problems have the same optimum and are similar
(see Figure TO However, reformulation (23) allows us to introduce the notion of Hessian inexactness
that we cover in our theoretical analysis. Thus, using our approximation from Example 7 we can approach problem (23) with Algorithm| | usiig an inexact Hessian. As theory suggests, our method should achieve the same convergence rate as the full Newton, which we observe in Figure I0 (b) and in Figure I1 when varying the power p, making the problem harder for the Gradient Method.
Furthermore, we see that the Gradient Method and our algorithm with exact and inexact Hessian follow the same optimization direction through this narrow parabolic-shaped valley of the Rosenbrock function - Figure I2 However, our method accelerates much when finds a sweet spot in this valley.
As an advantage of using the Hessian approximation in this setup, we pose the fact that the Newton Method with an exact Hessian fails to converge given some inappropriate starting point which can actually be close to the optimum Figure 13 Which happens due to the inability to invert the regularized Hessian of the objective at the beginning of the run. At the same time, Algorithm T with an inexact Hessian succeeds for any starting points we have tried.
Inexact Hessian and the Chebyshev Polynomials. We illustrate our theoretical finding on a new, particularly interesting problem Nonlinear Equations with Chebyshev polynomials. We formulate our objective as follows
f(x)
| where u(x) (ui(x),..... ..... ua(x))) such that
(24)
" (I( = {11 11), (x(x) = - (2(T) = 27 -
Where P2 is the Chebyshev polynomial of degree two. Clearly, for the case p 2, our objective (24) resembles the smooth 2013) up to a constant factor 2. Indeed,
function studied (Jarre) 2011 Cartis et al.
au (m)) = (1- 11-x))
Σ (a411 2x + +1
As for the plain Rosenbrock function (22 and our adaptation of it to the Nonlinear Equations problem 23 the only stationary point (1,.... of the Sheeoo--hhheyyeeeeeeeeeee
objective is the
27

---

stands Published as a conference paper at ICLR 2026
global minimizer. Although this function is very difficult for numerical methods in both its smooth (Jaree 2011) and non-smooth (Gürbüzbalaban & Overton 2012) variants.
In our experiments, extend the able to use the approximation of Example 7 in our method. We demonstrate the convergence of the full Newton, Algorithm with the inexact Hessian and the Gradient Method. And show how it depends on the effects that come from the increase in the dimensionality of the vector function u(-) and the increase of power p in our objective (24). We notice that our method with approximation performs remarkably well in all settings we have tried, as depicted in Figures 14 and In particular, both exact and inexact variants of Algorithm Algorithm[perrorn significantly better than the Gradient Method when is small enough (Figure [4), but when increasing (Figure 15), we observe that the Gradient Method also starts to perform better.
function 24 Thus,
Rosenbrock Scaction
Nonlinear Ecuntions & Resenbouck
16P
107
Eost Nerdees
Easrt Neeton
100
10ml
10--
Grachee
10
10
10-41
15
(30000
030001 00:00 Ianaliins
100000
2000
90000
R3:0
100000
Essnations
(b)
Figure 10: Optimization of the Rosenbrock function (a),, and the Noulinear Equation problem for p = with Rosenbrock residuals (b), theory (see Example With such
looks quite similar. For the second problem approximation our method in the regime where it has the same convergence as the Newton Method with the full Hessian. However, by using inekact Hessian, obtain more numerically stable algorithm with respect the choice starting iterate, depicted in Figure B
the Hessian upproximation suggested
Nealinasr Equationn Rosenhroek, --
Naniinear Equations & Resebbockk
Nonlinew Equntions & Rosenbook,
Rosr Nectin
107
Fext Nerter
10a
Doors Nection
5. 10-16
Grudier Merhed
10-3
Choleer Matha!
10
10
Grabbe Mirhed
10
10-47
10
10-30
11-21
10-17
10
10
700000
(0000 00000
8000 Tannaiooe
1000.0
0
70000
40000
60000
50000
10:000
20000
0000 00000 80000 100030 Toeoiioo
Turatione
Figure 1I: Varying the power in the Nonlinear Equations problem our method with an approtimation the Newton Method works quite sumilarly oven different values of p. Here, "Incxact Hessian" for the approximation suggested by theory Example 7
23 we complicate the convergence for the Gradient Method. However,
28

---

Published as a conference paper at ICLR 2026
700
50
10000
hoo
500
0
Exact Newton
-1
Inexact Hessian
Gradient Method
-2
Optimum (1,
2
1
2
Figure 12: Contour plot of the Nonlinear Equations problem with the Rosenbrock residuals in the two-dimensional case. In similar
way that the authors of (Kabgani & Alooohoohh
2025 Gürbüzbalaban & Overton 2012 do for the problems they consider, we plot the
level contours for the objective f(x) [u()]]
[= with operator (x))) :=
Zi. 10(2z =²]) being vector-function
Rosenbrock residuals the Nesterov-Chete Cheeoo--heeyshe--ee Chebyshee-Roseebooud Tunction from (Gürbüzaalabun & Overton 2012 However, our objective (25 remains nov-ccomer
Equation
The contour obtain for this objective also similar that the
variant
anooch function, thus, serves as good example complemeniing theory.
connected line segments
iterates generated by
Algorithm exact Hessian, Algorithm[] with upprosimation descrihed in Example and the Gradient Method. The markers for Fxact and Incxact methods are the same color because optimization trajectory of both algorichms is quite similar and their consecutive itcrates lie relatively close each other. For methodk utilize adaptive search procedure (see Equation [6] and Appendix (D). The comparison of exactly those methods in terms of the functional residual is depicted in Figure 10 and the starting point is (-2, 2). our contour plot. we see all three metbeds, when initialized outside parabolic valley of the objective, firstly tend find valley
as possible, and
then follow down to the global minimizer (1, 1). However, both Exact and Inexact methods move significanlly faster once they found the valley. returned by Gradient Method ahead of 500-th iterate of the Gradient Method.
Indeed, we
valley,
15
Algoritim variations
Exact Newton
Inexact Hessian
Optimuu
Optinunn (1,
1.5
1.5
1.0
Failure
1.0
Failure
0.5
0.5
0.0
0.0
-0.5
-0.
Success
Success
-1.5
-2.0
-20
2.0
1.5
1..
0.5
0.3
0.5
1.0
2.0
2.0
-1.0
-0.
0.0
0.5
1.0
1.5
2.0
Figure 13: Region of Starting Points Where Method Fails to Converge. In this experiment, we consider Algorithm D with exact Hessian and same method approximation descrihed in Example[]] employ our adaptive search procedure (see Equation
Appendix and run both methods the Nonlincar Equations problems with the Roscabrock residuals the two-dimensional case. Wc chose the starting point ao from grid in the range [ (-2, 2, 2) for both coordinates. Interestingly, the method with the full Hessian fails to converge given certain sturting points that relatively close the global minimizer. This happens due the conditionng issues with the exact Hessian matrix during the inversion. Fixing those issues with another choice of regularization or update rule means changing the algorithm. therefore we did not perform changes. However, our algurithm we considered. Therefore, our experimental validations suggests that Algorithm [ with inexact Hessian not only performs similarly the full Newton approximation is in accordance with our theory, also serves more numerically stable method.
inesact Hessian works remarkably well
for any staring iterate given
range
29

---

Published as a conference paper at ICLR 2026
Chelyshev Polynocuial (d 200,
Chedovlaer Polyzcouial (d 1900
10
10a
10
10-3
10--
10-4
Exsst Noston
10-11
Exsot Nostor
10-5
Inssect Uloarar.
Icessee Dooioo
10-4
Geudiver Methodl
10-7
Crather Metive
10-1e
10-13
10 15
10-14
10-11
25
50
75
100 Iremations
125
150
175
200
11
25
50
70
100 Berabions
125
150
175
200
Chelyohevv Polynocaial (d 200, p 3)
Chaebyrdher Polyroomial (d 1000 p
10r
10/
10
10-1
10-1
10
Nostur
10--7
Exst
laesuet Basia
Inssect Hackka
10-12
Gracherr Method
10-11
Gonlaen Matiael
10-16
10-13
10
10-11
100
125
150
175
700
25
50
20
100 Hordioons
125
150
170
Cleekyslav Polynocuial (d 200,
Cladloedurs Pulyzoonial (df 1000,
10P
Newtur
10:5
10-
Iroaat Hosis
10-6
10-5
Cradien Metiod
10-10
Exsc Nestor
10-
Inewsr Beornn
10-14
Geathern Medical
10
10-1s
10-37
10
10-35
10-33
25
50
75
100
125
150
170
201
25
50
70
180 Ttemalion
125
150
175
2000
Itorafion
Figure 14: Algorithm with the inexact Hessian noticeably outperforms both the full Newion and the Grudient Method on the Noulinear Equattins problem with Chebyshev polynomial objective. For this experiment, we utilize the objective (4). where stands the dimension of the voctor-function ex(-). Importantly, ||uu |f correspond to the smooth variant of the Nestenov-Chehysber Roooshobo-ooo function which is known as hard problem for numerical methods. Throughout this experiment, we vary both p and d to complicate the optimization of objective. Noticeably, all these Algorithm!] [ with approximation outperforms the full Newton.
Chebyshev Polynoraial (6 200,
Chicksihuss Polynomial (d 1000,
107
Fost Nextton
10a0
Exsct Nostoz
10²
Inasoad Hosiss:
10'
Icesse Denio
10-2
Gaudior Mothod
10-2
Gradver: Metied
11--11
10-1
10-17
10-23
10-2
55
10
10-32
25
50
75
100
125
150
175
200
75
50
75
100
125
150
175 200
Inceations
Iterations
Chelveshev Polynomial (al
Cheiryshev Polynomial (d = 1000. p 19
10f4
10a
Frown Nerton
Inssect Howie:
1070
1031
Benet Newton
Inssuct Newton
107
Gudiaai Methad
162
Gradion Method
4.
20-4
10F
10-39
10->
10-16
10
10
10-17
10-28
10-93
6
25
00
75
100
125
150
175
700
75
100 lerratinn
125
150
175
200
Henations
Figure 15: When increusing the power we see that the gap between Algorithm and the Gradient Method narrows. We run three
methods objective (24) and, same way Figure [4] we increase hoth y and dimension of (-). Clearly, we ohserve a dynamics that the gain of Algoritm M with and without approximation becomes less significant when the is large.
becomess
30

---

Published as a conference paper at ICLR 2026
B.5 COMPARISON WITH ADAPTIVE AND UNIVERSAL METHODS
In this section, we elaborate more on comparisons of our framework with other adaptive and universal methods. We experimentally study the Cubic Newton method (Nesterov & Polyak 2006) and
two more algorithms, Humely--Afine-nnvarria Cubic Newton ATCN (Hanzely et al. 2022) and
Gradient-Regulatd Line Search (GRLS) (Hanzely al., 2024). Both AICN and GRLS are instances of the Damped Newton method, but with different adaptive rules for the step-size selection. While for the Exact Newton method with gradient regularization and its version with the inexact Hessian, we use the adaptive search for parameter 7(-), which controls the regularization term in line 3 of Algorithm[] | We also compare their performance with the Fast Gradient Method (Nesterov) 2018) to observe the advantage from using (an approximate) second-order information. As problems for this comparison visualized in Figure 16, we choose: LogSumExp (a), Nonlinear Equations (b) on the a9a dataset, and Chebyshev polynomials (c). Their descriptions match those from prior sections. Subsequently, we employ the Weighted Gauss-Newts approximation (Eq. 19 for LogSumExp. Fisher Term of H (Eq. (2T for Nonlinear Equations, and the approximation from Example for Chebyshev polynomials.
Random
adu 220002222 3)
Cheloshey Polyncental
1000,
161
Pour Neatre
10"
Eaad Norton
10n7
10"1
10-1
-00
Gualiez
Calez Nerton
Weegined Gaze Necton
Grodial Metlaa]
Firu
103
10
Grodien Methedl
Fodee Tais
Eost Nertoas
10-1
10-1
10-5
Incced Hoskas
Gualive Metioal
CIRLS
Gradite Maathed
10-3
CRRLS
(0-3
Catsc Neuns
10-17
AICN
10-11
AICX
GRLS
10-13
AINN
10-21
2013
400
AX
500
2000
21
40
(0)
50
100
20
50
70
100
125
150
176 200
Ieeratoos
Ieanttion
Ibeaatinns
(a) LogSumExp & approx.
19
(b) Nonlincur Equations & approx.
21 (c) Chebyshev approx. from Example
Figure 16: Comparison with Cubic Newton and versions of the Dumped Newton method with aduptive step-size. all figures, demonstrate clear improvement of second-onks methods and Algorihhn with inexact Hessians and adaptive search over first-order methods both convex ((u.b) non cunvex objectives, important problems, comeeponding to Examples [nd Runs (a), follow the recipe from Appendix [122 where we used the Weighted Gauss. Newton approximation (Fq. [9] theoretical bounds for this kind of approximation are proven in Example I The only difference with sctup from the prior section, is that wc study more methods here: Cubic Newton, accelerated
gradient methed, and two versions the Damped Newton with adaptive step-sizes GRLS and AICN, In (b), replicate our experiments from Appendix [3.3 utilizing the Fisher Term of approximation (Eq [1] The main difference here, except For the methods, is new aDa
dataset that is presented in Figures о See proofs for the bounds on the apprximation in Example [2] Finally, (c), show results for
the non-convex smooth Chebyshev polynomials problem, studied in Appendix [44 When the operator is nonlinear, H(()) from Example
not resemble the Hessian and can explicitly
equation. For this case, extended bounds are also proven Example 12
31

---

Published as a conference paper at ICLR 2026
C COMPOSITE OPTIMIZATION PROBLEMS
Let us consider a more general formulation of the Composite Optimization Problem (Nestervv 2018
min F(x) := f(z) + v((z)) =EQ
(25)
where f: + R is a differentiable function, which can be non-convex, and v : Q - R is simple closed convex function with Q == dom 1b. This setup covers optimization problems with simple constraints, in which case to is {0, +00 -indiicator of a given closed convex set Q C IR".
We denote F* := inf F(x) -o which assume be bounded. =EQ
C.I COMPOSITE NEWTON STEP WITH HESSIAN APPROXIMATION
In case of the presence of the composite component J we have to modify our method accordingly.
Now, begin point E Q and for certain vector F" F'(x)) == V fz) where vf (x() dvb(x))
we compute the next iterate x as the solution to the following subproblem:
at = arg mink (V yEQ
x)) + (y - 2) x (==)ll by m/12 + (v)). (26)
where H(x)) H = 0 is positive semidefinite approximation of the Hessian of the smooth part, and is our step-size parameter. Note that the subproblem in (26) is strongly convex, and case v it corresponds to one iteration of Algorithm
In general, the solution to
26 satisfies the following optimality condition (Nesterov 2018
(F)()) + (())) + [=)]l B) (x - x))x x - x)) + (b)) 2 (xxx)),
Vy E Q. (27)
or, in other words, the vector
(a == (x) (xx)(x+ =x) [F B(x xx)
(28)
belongs the subdifferential of new point: (x**) (x
Let us derive useful incqualities for one step of the composite method. Note that for any stationary point x² problem (25). setting = x² have x+ x". it satisfies the optimality
condition (27). Therefore, without loss generality we can always assume that x + x=
Lemma 2. Let (x) E @b(x) be an arbitrary subgradient and denote F((x)= = Vf(x) +
(x:) + O. Then, for any y 0, it holds
(F) x+) > 0.
(29)
| xil 5 7,
(30)
and
||ae 20/2
(V2s(x)(x++ x)), xx -x) S (F'(z)) x xx
(31)
+ ||+ - x:| (I(V2](x) - (xxx))(x+= x)|l. [I'
Proof. Indeed, multiplying 28 by x æ and using convexity of th, we have
(H(x)((+ - x)) + x) [F'(z))l ||at æe|2 = (Vf(x) + (f(x+)(+++++)))))))) x²)
S (F'(z), x-
Therefore, taking into account that H(x) > O. we conclude that
|| (m)) Ir 20l2 < (F'( x a):;
32

---

Published as a conference paper at ICLR 2026
which proves we notice that
29
Applying Cauchy-Schward inequality also gives
30
Now, establish
(1
(V2 (a=)(a 2.) ax xt)
(H(x)((x x), xx) ((v2 H(x)))(++
x)) x²)
s (F) at> [x)(l)) la+ æ=| [1 H(xx))(xt =1)1_ a/|.
7
which completes the proof.
We see that according to definition (26). we ensure that every step remains bounded 300 by our parameter y > O. Let us recall our Definition the Gradient-Normalized Smoothness from the main part, for any
and g E R":
((. = max { 2
0 [Vʃ( + h) Vf(x) H(ll < | vh By nOz.)
where B., := {h: h S ? is the Euclidean ball, and Oz.g == {|]A + (g. h) I 0} is the local region. Note that this definition measures the local level of smoothness for our differentiable part I, and does not take into account the composite component tb. However, as we will see, in the composite case change the direction in our algorithm to define the step-size, by taking the perturbed gradient: = f(() + (x)).
First, let derive simple consequences of the definition of ()x
Lemma 3. Let 0 < 7 3.557 ((x,)) Then, for any h E B,, n Ox.g. it holds
[s(= h)) f(x) (VS(x), (H()),,A)) S
1
(32)
27
Proof. Indeed, have
Is( + h) -()) (Vf(x), - (H(()), h)
| + 7h) V/(m) H))
<
[h) Hx())//ll.dT
||gll- ||+1]
27
where we used the definition of 7(x, g) in the last inequality.
Lemma 4. Ler 0 < S 7(æ, g). Then, for any IR" s.f. ||s|| = 1 and (g. s) < 0 we have
[[) Hx))))ll
||ا||
(33)
Proof.
Let us take h = 78, where 0 < (xx Clearly, h E By, Moreover,
1 + hg T(<(V> s) (g 0,
for sufficiently small > 0. Hence, for sufficiently small т, we have:
1 [V rs) - H(z)s <
lal-
7
Taking the limit +0 completes the proof.
33

---

Published as a conference paper at ICLR 2026
Note that according to Lemma (g. 8) < 0 for g = Fx) (inequality 29p. Therefore, we obtain the following direct result.
normalized direction of method,
x=
satisfies
Corollary 4. Let < y s (a, (x)). Then, one composite step (26 satisfies
| 2
(F) x
(34)
Thus,
(35)
Due to inclusion (35). we show the following one step progress for our method. Note that Lemma simple direct consequence of this result, using vi 0.
Lemma 5. Ler < 7 (x))). Then,
F(w) F(x+)
(F I1?
(36)
(=)]]
Proof. Substituting the optimality condition we get
into global bound on the function progress
f(xt) S f(x) 1 (H())((+* x), xt x)
(x=) || ml
+ (v x²)
27
s F(x) (H(x((** - =x)x x))
=|1
(xxx))
27
which gives
F(x) - F(xt)
(37)
27
At the same time,
[|+'(x++++ (= B(x =))l--
[Vf(xt)) Vf(x)) H(x =))l-
where used the definition of 7ax Fxx))) 7 in the last inequality. Hence, applying triangle inequality, we obtain:
[F I|.
('
Combining this inequality with 37 gives the required bound.
C.2 THE ALGORITHM FOR COMPOSITE OPTIMIZATION
We ready to formalize method for the general composite case, as follows.
Algorithm 2 Composite Gradient-Regularizet Newton with Approximate Hessians
Initialization: wo E Q and (woo E (w))) Set F((x)) + Vf(x)) - (xo)).
I: for k do
2:
Choose H(x;)) > and 7hk > 0.
3: Compute
arg min min yEQ { (zx)) y- xx) + (H( œk), y =xx)
Ø6+1
|| F (xx)ll |y xx + v(y)
27a
4: Set v/ (xx+1) <- Vf(xx) H(xx)) (#x+1 xx) [' B (I&41 xk).
5: Set F'(x2+1) <- [((*++) + (xx
6: end for
In the sb 0. this method is the same as Algorithm
34

---

Published as a conference paper at ICLR 2026
D THE CHOICE OF THE REGULARIZATION PARAMETER
Note that the only parameter of Algorithm 2 is a (second-order) step-size > > that describes
the radius of the ball where the iteration belongs to: || 3 S 7k. similarly to trust-region approach (Conn et al. 2000).
Our theory suggests that the right choice of this parameter is provided by the Gradient-Normalized Smoothness (Definition Tb. that is, in the general composite case:
7k
(x,, F (xx)).
Then, according to Lemma 5 we ensure the following progress of each step:
F(xx) F(x++1)
7kk (m (xx))
(38)
Therefore, 76 (3xx) is the best value of step-size that use. However, in practice, it can be difficult to compute the exact value of the
Smoothness. In this section, we show two different strategies that can work for practical implementation of our method.
The first choice (Section D.I is the constant rule for selecting 7
7
4k
2 0,
where 7/4 > 0 is a certain value, fixed once for all iterations of the method. Hence, since this is perform simple grid search for choosing y. in similar spirit to
just one hyperparameter, step-size tuning for the stochastic gradient descent (SGD). However, we noticed in our experiments, that the value 7 1 is always good guess for second-order methods, which also ensures local quadratic convergence of the method with exact Hessian, as for the classical Newton's method.
The second choice (Section D.2) that will present is the of adaptive search to estimate "/k at each iteration, which is standard and cheap procedure, which also equips the method with fast global rates, without the need know the exact value of 7(x)) 7
In this section, for simplicity we focus on convex optimization problems, while our results can be generalized other classes of problems. We consider non-convex optimization in Section D and the gradient-dominated objectives in Section
D.1 THE CONSTANT RULE
Let assume that the desired accuracy > 0 is fixed. This assumption is not very restrictive. Additionally, it allows to have a stopping condition the method. Then, we denote the following set of function suboptimality:
3z == {o=Q: F(x) - F* 25.
and, for a fixed initialization E 3c, we denote the sublevel set by
Fo = {xEQ F(x) s F(
which assume be bounded, i.e., D diam(Fo) t00. Note that by convexity, obtain, for any subgradient F'(x) E (F(x), with æ E 82 nFFo:
[F(()]]
>
F
> 8 = 5
(39)
We ready formulate main result, for the constant selection of qh in algorithm.
35

---

Published as a conference paper at ICLR 2026
Theorem Let & be fixed, and assume that there exists 7/+ > satisfying
7/ S <inf 7(2, (x))
x BE
Fo, (( E @F
(40)
Consider K iterations of Algorithm 2 with
7kk
7
(41)
and assume that 23 E S for all 0 S k S K. Then,
SD In F( F
+ In (2o))l
(42)
Proof. Indeed, by Lemma 5 our constant choice of "/k ensure the following progress of every
iteration, denoting F& F F(xx)
F* and gk: = (aax
FR Pk+1
gi+1
9N
In
8
gx-1
9h
873
9hi
2
Pk-
(43)
Then, using concavity of the logarithm, we have
In Fu
Tu+1
43
7/a
g++1
(44)
F
877
9h
Telescoping this bound for the first K iterations of the method, and using the inequality between arithmetic and geometric means, we obtain
K
In
Fu
J.K SD
11+11
No
k=
96
87
90
39
8D
17
8D
exp
2 K
In
J.K 8D
1
2 K
D
Rearranging the terms proves the required bound.
Note that the result of Theorem 3 is very general, as it does not assume any particular smoothness conditions, except separation from of the Normmllz-- Smoothness 7(-) the bounded
set G. n Fo: Pxx >> O. Under this condition, we show that our method with a constant rule 7/-- = 7 needs
K OT='D)
(45)
iterations to solve the problem, up to logarithmic terms.
Despite the constant rule 41 seems too conservative, appears that it recovers the correct rates in all particular cases. For example, for the functions with Lyp-iisschtz Hessian, we have
F(()))
(x)
39
Ln
7
Substituting this value 7 into 045
gives the complexity of Ö(
L2De)
which matches the
complexity of the Cubic Newton Nesterov & Polyak (006) on convex functions, up logarithmic factor.
In Section F we develop more refined analysis that covers convex functions as particular case, and allows us to avoid logarithmic factor in some particular cases.
D.2 THE METHOD WITH ADAPTIVE SEARCHI
In this section, provide another practical choice for %k which is to adaptively ensure inequal- ity 38) We present this strategy in the following algorithmic form. This method needs a parameter 5 which is desired accuracy in terms of the gradient norm. It is used for the stopping condition.
This is the same method as Algorithm but with a specific adaptive procedure to choose parameter 2k 0. It is clear that the method is well defined, as for sufficiently large 2 0 ensure
36

---

Published as a conference paper at ICLR 2026
Algorithm 3 Adaptive Method with Approximate Hessians
Initialization: Do Q, v/' (xo) (zu) "/o O, and 5 > 0. Set F'(oo) Vf(zz) + 1/ (zx).
1: for k 2 do
2: If [xxx)()))))+ S ó then stop and return ag.-
3: Choose H(x;)) = O.
4: Find the smallest integer
0 such that for == 2- k. 7h and T(7). g(() computed as
T(t)
arg min NEQ
(Vf())))
y xx) + (H( (1 æk), -xx)
(xx))= I1l |1 x 2 (1)
24
and
g(>)
Vf(T(n)) ff(())) H(xx)(T((>) xx,) (F 1l B(T(?) xrk)
holds
F(mx)) F(T(7))
|g(ا
119(1)]1- 5
(xx]I
5: Set #K+1 + T(2 t2 7kk and (2(4411 f g mk).
6: Set 7++1 f- 2 2-4+1 7ik-
7:
end for
that 2- YK I yark, Fxxx))) and therefore the condition of the adaptive search will be satisfied. At the same time, the total number Nx of oracle calls during K 2 O iterations is bounded as
NK (1+t2) = 2K +
loga 7241
-KK
log2 7K-1
2K loga
20 7x"
(46)
where `KK minosisK-1 Tkk
Note also that Algorithm with H( = 2 f(x())) (exact Hessian) is equivalent to the Super- Universal Newton Method from (Doikov et al. 2024a), using a different stopping condition in the adaptive search. Even in the exact case, out theory enhances the complexity results from (Doikov al. 2024a) to the broader classes of generalized Self-Concordant functions (Sun & Tran-Dinhe and beyond, including problems with (To, In fufuncions (Zhang et al. 2019)).
2018
Moreover, our results allow us to use an arbitrary positive semidefinite approximation H(x;) x V f=x())) of the Hessian in methods, and all our algorithms are applicable to possibly non-convex problems as well, while the method in (Doikov et al. 2024a) works primarily for convex optimization, using the exact Hessian.
We establish the following result about this algorithm.
Theorem 4. Let be fixed, and assume that there exists 7 > O satisfying
% < inf Fnf(
x FF F*(x) e AF(x)).
Let 8 b. Assume that Algorithm T& for all < k S K. Then,
3 does not stop for the first K 2 iterations, and that
K.
16D F F" 2 [F')))))
(47)
minn 70.77
:
and the total number of oracle calls during these iterations is bounded as
No
2K loga 7.
Proof. First, we note that the method is well-defined. Indeed, by our assumption, there exists a global value of y, such that the first stopping condition of the adaptive search will be satisfied at least for t 2 such that 2 7 < 7.s unless [F (xx))=)) < 5. The last incquality implies that we solved the problem with the desired accuracy and stop the algorithm.
37

---

Published as a conference paper at ICLR 2026
Therefore, by induction have the following lower bound values of our step=sizes:
Ykk 2
mio 7+
0 S K.
(48)
Hence, for every iteration k 2 0 of the method, we ensure
F( F(x++1)
1kil 1G
( [
min (7. 20 | 1
(
Now, repeating the reasoning from the proof of Theorem 3 we establish immediately obtain the bound the total number of oracle calls,
(47 and using
(46) wc
E CONVERGENCE FOR NON-CONVER FUNCTIONS
First, let us formulate Theorem for more general composite optimization problems Theorem is direct consequence of this result for x O.
25 Then,
Theorem 5.
Let K 2 be fixed number of iterations of Algorithm and let
(5) hold for every
step. Assume that minj gisk || (xx))l 2 s and let 7 min
7
Then,
1SiSK
8Fg.
log
[xo))l
where Fu = F(xu) F*.
(49)
7,5
Proof. According
we have for every iteration the method,
F(x+) F(*++1) z
The [I
2 7.E (
8 [xx)]]]]
[[x]]]]]]
Telescoping this bound and using the inequality between arithmetic and geometric means, we get
F(mo) F
F( F((K)
(x.)) F
[ 1/b
F
1/k
kive
kove exp & log |F
W
log [P
Rearranging the terms proves the required complexity bound.
We that this result is very general: did not specify anything about the problem class function belongs to. Theorem 5) shows that for general composite objectives, with possibly non- convex smooth part, our method will have global convergence a stationary point. To quantify the convergence rate further, we need to impose some structural assumption on the Smoothness 7(-)) of the function. Following our assumption 10 from the main part, assume that 7(-) is lower bounded by the harmonic mean of monomials of (sub)gradient norms:
7(x, (2())) (x)l'(
Σ
Mi-op
min 1<i5d
[F Mi
(50)
(x))
where for all S a: describing the complexity of the problem. Note that this assumption holds for all particular examples of problem classes that we consider (see Section 2. Substituting this bound into Theorem 5 immediately obtain the following corollary.
fixed degrees and {Mi-a
non-negative coefficients
Corollary 5. Let us choose "ik
( in Algorithm 2 or by performing an adaptive
search. Under assumptions of Theorem we can bound % 2 π(E). Therefore, to ensure min [[F"() I & it is enough to perform number of iterations of ISiSK
K = 8dFo
max I3iA
Mi-at
log
F' ||
38

---

Published as a conference paper at ICLR 2026
E.1 CONVERGENCE FOR INEXACT HÖLDER HESSIAN
Let us consider a particular important consequence of our result. For simplicity, we set / = 0 (unconstrained minimization). We assume that the Hessian of is Hölder continuous of certain degree 0 & I I (Example DT. Then, according to 7 the Gradient- Smoothness (NEWTON()) using the exact Hessian, bounded by
"NEWTON(2) 2 (()))l))
(51)
At the same time, in out method inexact Hessian matrix, with the following general guarantee (see Section 5):
- H(x)ll- <
(52)
for certain 0 3 S 1. Then, according to the basic properties,
lower bound the Gradient- Normalized Smoothness 7() for our problem and with inexact Hessian, as follows:
(()) (7NEWTON(2)- [f
(53)
Therefore, substituting our condition 51 Normalized Smoothness, that matches the structure of (50):
obtain the following lower bound for the Gradient-
(()) 2
I2 (II+
[V
Therefore, out theory immediately provides us with the following complexity result.
Corollary Let us choose "Is = (xxk) in Algorithm 2 or by performing an adaptive search,
using inexact Hessian that satisfies (52 enough perform number of iterations of
Then, to ensure minigigk [V,((; S it
K = o
0 Fo
L 2210
L + log [V
For example, for (Lipschitz continuous Hessian), we obtain the complexity of
Fo O L2a1
up to additive logarithmic term. Note that the first term corresponds to the state-of-the-art rate of the Cubically regularized Newton method (Nesterov & Polyak] 2006 Cartis et al. 2011a). We see that when C₁ & 0 and < 1/2, which corresponds to our examples, Algorithm with inexact Hessian has the same complexity as the exact Newton method. the following section, we show how to improve these complexity bounds further, under additional assumptions on our objective, such as convexity.
F IMPROVED RATES FOR GRADIENT-DOMINATEED FUNCTIONS
In this section, let us assume additionally that the objective function F satisfics the following inequality. for certain 0 < << 1 and constant D. (see (Nesterov & Polyak] 2006 Fatkhullin
et al. 2022 Doikov et al. 2024a)):
[+*'))))!!+ +D
F& = F(æx) F*.
k k 0.
(54)
Let us denote by Fo the initial level set of the function
{ { F(x) F(zo))
Fo
Note that due to Lemma 5 all iterations of our method belong to this set: {0+Ja20 C. Fo. Then, denote by Do the diameter of this set, which we assume to be bounded:
Do =
sup
| yl
+00.
F.
39

---

Published as a conference paper at ICLR 2026
Convex Functions, Assume that F is convex. Then,
F(xx) -
(F*) Tt - x²) I (1+ x²|l
F< Do
Therefore, inequality
54 is satisfied with c: 0.
Uniformly Convex Functions. Assume that satisfies the following inequality, for a certain 2 and op 0 (see (Nesterov 2018)):
F F(x)+ + (F' x) + du fly x
(55)
p
Then 54 is satisfied with
and D. := Pa-l
c
Strongly Convex Functions correspond the previous case, when p 2.
We are ready to establish improved global convergence rates for our method under condition (54) of gradient-dominance, Then, Theorem 2 from the main part is direct consequence of this result for 2 = 0 and 0 (Convex Unconstrained Minimization).
Theorem 6.
Let us choose ((xx)) in Algorithm or by performing an adaptive search, Let the Gramdiet-Normalized Smoothness 7(-) satisfies our structural assumption 50 and denote
a == mini Assume that F is pradient-dominaet
(54) of degree
a.
(56)
Then, for E > O, ensure F(*K) F* S E, it enough to perform a number of iterations of
K [C(E) 2og [Fa)]]] Do
where
C(e) =
8d max
Mi
D Lta cda-a
I4c
for 11 = amc Itc
> 0,
To
1sisd
and, for = 0, we have the limit:
C(e) = 8d max
M1-a;
M
T#c
Fu log
(57)
15i5d
gai-a
E
Proof. Let us fix some & 2 0 and assume that FA = F((x)) - F. 2 E. Let 9k = [F+x))))] By
assumption 500. have
2
Fx
(58)
De
Then, from Lemma 5 obtain
Fr F+41
gh-1
g
ge+t 9b
min Isidd
91 Mi-a;
(59)
54
1404 T+c
96++1
min
Fy
8d
81
15i
My oz
Recall that a : min Og. Denote 7) =
a=e I+c
Applying the Mean Value Theorem for
15idd
((x) x we get
67 a
51 2 a)
> > 0.
(60)
40

---

Published as a conference paper at ICLR 2026
Thus, have, assuming that 17 > 0:
( F k+1
F2 F
G0 F
F2
F E
FL FLPE+1
ge+s
min Isisd
1
r aa
8d
gk
P2+1
Mi-n;
Dotoi
A(e)
gh+1
Fe
Pk-1
where
A(e)
min
ISid
Mi-os
Telescoping this bound and using the inequality between arithmetic and geometric means, we obtain
F3 1
A(e)
9++1
F kA(e)
92
91
96
kA(e).
p
kA(e) (x0
kA(E) exp - log
Dn
2 kA(E) (1
log Do
Rearranging the terms, we get
1 1
+ 2 log Do
nA(e)
Fo
Note that for 0, we can use the following limit
lim 1
+ log b
a, > 0.
Therefore, in this case, we obtain
log Fu + 2 log Dn
Ale)
which completes the proof.
Let us consider an important particular case of convex functions (c = 0), and for specific assump- tions on smoothness. In these cases and for the exact Hessian, we have that 7( F (*xx))) 2 T ([))"( (*x)))) M, thus (-)) a simple monomial of degree
< 1.
Corollary 7 (Convex Function), Consider exact Newton method: H(xx) = V (xxx) Let the Hessian have bounded variation (Ex.
0), then L, Mo L2,0 and we get:
K = ( MoDa
Let the Hessian be Lipschitz continuous (Ex. our method has the same rate as the Cubic Newton (Nesterov & Polyak 2006):
1
1), then 1/2, M /2 LL and
K O MinD
Let the third derivative be Lipschitz continuous (Ex. 1), then 1/3, and we obtain the rate as that of the third-order tensor method (Nesterov) 2021a)
M2/3
L
1/3
0(
Marn D 2173
= [1. 1/3
=
K
Let f be Quasi-Self-Concordam Concordant (Ex. 3) then a O, and we obtain the global liner rate (Doikov
2023
K = o( log F
41

---

Published as a conference paper at ICLR 2026
We that our theory covers all the known tfte-offthhear global convergence rates of the Newton method in a unified manner.
Now, assume that the corresponding Merdeentt-ommalzeedd Smoothness 7(-) will be changed accordingly
inexact Hessian, H(z+) = V (xxx), that satisfies condition 52
Then,
53 and
Theorem leads us the following result. We assume 15 0 (unconstrained minimization).
Corollary 8 (Inexact Hessian). Let us choose = (xx)) in Algorithm by performing adaptive search, using an inexact Hessian that satisfies (52). Assume that e S B. Then, to ensure f(oK) - it is enough to perform a number of iterations of
K K=Ō k= (OCEEWTOO)()) C1
D
C2 c
(61)
where ONEWTON (5) is the complexity of the method with exact Hessian.
According (61). see that large degree 0 of gradient dominance helps accelerate the method. Thus, for e = 0 (convex functions), we obtain
K Ö(CrEwTOX(e) C1 D C22
D
At the same time, for c c: 1/2 (c.g., uniformly convex functions of degree 3), we already obtain complexity of
K = Ö(CKEWTON(E) + C1
D4/a 2173 + C2
D++a 6/-1/2
which is much better in terms of dependence E, etc. Is important that all these rates correspond to the same algorithm, with a universal step-size selection. Therefore, the method able to automatically adapt the best degree of smoothness and gradient dominance.
Combining Corollary with Corollary 7 we obtain the following classification complexities, for Convex Unconstrained Minimization (c 0, sb 0), with inexact Hessians.
Corollary 9 (Inexact Hessian: Convex Functions). Consider inexact Hessians
Let the Hessian have bounded variation, and a 1, Then,
K 0 (Mo+C2)Do O + C2
Let the Hessian be Lipschitz continuous, and = =3 1/2. Then,
K ==0
(2))2+C2)DD22
C,D² Da
Let the third derivative be Lipschitz continuous, and 1/3. Then
(
o Ca)
C2
2173
Let f be Slasi-SSef-Cooccrdame and a 0. Then
K o ([(M: C2) Do
C D
log Fu =
G APPLICATIONS
In this section, we provide concrete examples of problems that satisfy our assumptions smoothness and Hessian approximation, and that offer direct, practical applications of our theory.
Let us study the case of the exact Hessian: H(x)= = V fxx), and consider some standard assumptions on the smoothness of our objective. We demonstrate that any such global assumption can be effectively translated into appropriate bounds on our -iriientt-Nmmaiizeddd Smoothness 7(.). As a consequence, by Theorems and 6 immediately obtain global convergence guarantees for our algorithms.
42

---

Published as a conference paper at ICLR 2026
For simplicity of presentation, always assume that K 2 2 log bounds, to omit an additive logarithmic term.
[[ in complexity
G.1 FUNCTIONS WITH HÖLDER HESSIAN
Let us assume that the Hessian of f is Hölder continuous of degree v E [0, 11, with some constant L2, > 0:
[<2 - r v T2 - yil', x; E R".
(62)
Therefore, by direct integration, obtain the following bound, for any R":
IV + h) (f(x) (=))))i S
T+u |||| =
La
(63)
- for an arbitrary fixed E R and consider E By =
Now, let us choose 7 = 1+v [1gll.) T.
(h E R |All S ?). We have
[Vf
I2. 1+0
|
Iell ||A
(64)
where the last equation holds due to our choice 7. By our definition 7(x,, g) is the maximal such value that (64) holds. Hence, we obtain the following bound.
Proposition 1. Ler f satisfy (62) for some v E [0, 1] and Lz > 0. Then,
7 (x g)) 2
Plugging this estimate into Theorem 5 we obtain the complexity to find [Fx'() of order
of
K
21240)/(1-0)
for our algorithms, up additive logarithmic terms. For 1, this corresponds the complexity of the Cubic Newton method (Nesterov & Polyak| 2006),, and for / 0. this is the same rate as for the Gradient Descent on general non-convex problems (Nesterov) 2018). At the same time, for
convex problems (Theorem 0 = 0), we get the complexity to find global solution in terms of the
functional residual, F(æK)
F I of order
K o[
D 2+
G.2 CONVEX FUNCTIONS WITH HÖLDER THIRD DERIVATIVE
Now, we assume that function f is convex and its third derivative is Hölder continuous of degree E [0, 1J, with constant L3 >
|| f(v) V f(x)]| < Ta,u| yll",
x. R
(65)
Following [Nesterov] 202 Doikov et al.] 2024a), we can integrate this inequality and, using convexity, obtain, for an arbitrary directions R and u E R":
< +
< (v2f(z) h) V f2) h oa
La. T40
||/| 1|
Now, substituting e = tru, for some > 0 and R we get
Tar I+ V f uill < 1 f()) h)) + ~"
(1T)))")(())A)))
Balancing the right hand side, choose
which gives:
3 (3)( h u|l
5
La T+v
2
f h) - ||||| + -ull
(66)
2.
La. I+
h
|||||
h u MuEl R..
43

---

Published as a conference paper at ICLR 2026
Then, using Taylor's formula for the gradient approximation, obtain
[+ Vf(x)
{ h|]l
(1+21(2+2) ||
Ls
Hence, applying the triangle inequality and our bound
66
conclude that
[V + + Vf(x)
(a>
(67)
L (2+v) |1||2t
Ls.0 1+y
2v
|||||| 340.
Now, for arbitrary g R and fixed y > consider only the directions h B,, n Oz.g. i.e. holds:
||||| s ? and For such directions, we can continue our bound, follows:
|| S (g. v ||
VV + h)
Vf(x) f(x))/l I
Lau (1+0)22+z)
|||||
+
1a I+u
I+o
7 9
hh|l
Now, we notice that ensure
La (1+v)(2+u) (+v)
Law
Itv
11gl 140
+
IIv
is sufficient to choose
stc
1+0
g|||
21 L1
Therefore, we finally conclude the following bound.
Proposition 2. Let be convex and satisfy (65 for some v/ E [0, 1] and L3, >> O. Then,
7 (, g)
2
1+v 21 La. ||ا||_)
F
Using this estimate with Theorem 6 for convex problems (c = 0), we get the complexity to find global solution in terms of the functional residual, F(xx) P of order
K =0((
(68)
for our algorithm. For v = 1. this gives O( (1) This result recovers fast rates for the Super-
Universal Newton method from (Doikov al. 2024a). Note that algorithms and theory generalize these rate to the case of inexact Hessian (see Corollaries g and
G.3 QUASI-SELF
CONCORDANT QUAST-SELF-COONCRDAANT FUNCTIONS
Important in applications with softmax problems, logistic and exponential regressions, matrix balanc- ing and matrix scaling problems, convex objectives that satisfy the following condition (Bach)
2010 Sun & Tran-Dini 2018 Karimireddy et al. 2018 Carmon et al. 2020 Doikov 2023). with
some parameter Mi 0:
(( u) < M1 h 12 /ull.
x. h, a E R
(69)
By integrating this inequality, obtain (see, e.g., Lemma 2.7 in (Doikov 2023 for any x, h E R":
Vf + h) vf(x) f2 < M1 1 (Mal|
(70)
where (l)) := ااييع > is a convex and monotone function. Now, let us assume that
B. n Oz.g . for arbitrary 7 and R
|
and
|A/12 < (g < ||g|-|||||.
(71)
Substituting these bounds into
70 we get
[ + h) v f(()) - - M1lloll11A| (f))M),
44

---

Published as a conference paper at ICLR 2026
and for = Mi ensure M1ς(yMM) < ?
3. Hence, we have established the following result.
Proposition 3. Let f be Caaasi-Self-Concooe (69 for some M1 O. Then,
(y g)
M1
Using this bound on -orbient--ormalized Smoothness in our Theorem for convex functions (c 0) immediately gives the global linear rate of convergence for our method, and to achieve F(xK) - F* < is enough to perform
K -oMMioo log
iterations of the algorithm.
Note that this is the same rate established in (Doikov) 2023) for the Newton method with gradient regularization. This result shows that the Newton method can achieve global linear rate of conver- gence without any additional assumptions of uniform or strong convexity on the objective. In contrast, first-order methods attain only sublinear rates on these problems unless additional regularization applied.
In this work, generalize this result to methods with inexact Hessian. It appears that, soon as C s O and 3 = 0 in condition (12). the method with an inexact Hessian has the same fast global rate the full Newton method. Remarkably,
show, this holds-for example-for the logistic regression problem (Example 6). where the Fisher approximation of the Hessian yields C₁ = f (the global optimum), which can be close to zero in well-separable case.
G.4 GENERALIZED CONCORDATT FUNCTIONS
Combining the previous two examples, let consider the following class of convex Generalized Self-Concordant functions (Sun & Tran-Dinh, 2018), for some degree 0 S q < and Gg 2 0:
8 f(x) h u] < 4 1 1/],
x,, h, u E R.
(72)
Note that g = 2 corresponds to Quasi-Self-Concordam functions 69 and for the convex functions
with Hölder continuous third derivative (66) of degree [0. 1]. have g I+ the following example that provides us with all intermediate powers 0 < 2.
2v Let us present
Example 9, For p 2 2. consider
f(x) =
1 p
||12:|PP.
Then, 72 is satisfied with q 2(p-3) and G2 = (p 1)(p - -2). p
Proof. Indeed, for arbitrary h, IR", we have:
(V)(w),
Bæx ht)
(V)(()),,h)
(p
h22 ||>||~~||||)
| h|l?
12 = 2(p - 2)|(=|| ((B h) (Bu, h))
+ (p (p -> (Be, u) (Bx, h/2
+ (p 2) o | (Bru
< (p 1)(p 1
2(r
< (p 1)(p 2) 2>|1|||""
1 |u]|
which is the required bound.
45

---

Published as a conference paper at ICLR 2026
Using direct computation, also immediately obtain the following simple proposition.
Proposition 4 (Affine Substitution). Let I satisfy (72 for some S < 2 and Gg > O. Then, g(x) == a(Ax b) satisfy
(22
with the same degree q and constant Gg. by correcting the
global norm accordingly: B' A BA.
Now, let us fix a point x E R For arbitrary given directions u. h E IR"", we denote the following univariate function
((T)
2- V V2 rugh, h) 2
Then,
(x)(())
f(a +T)++T)ll n..h.u.
G2
(73)
/=/latru)b.b)3
Hence, for arbitrary x, y, h E IR", setting u := y E, we have
||h13-- 11 2 Therefore, for an arbitrary h E IR and IR" such that || = 1 we have
2 (p(1) (())
2 G. G,lln112- f1 x||.
(74)
VV + - - - 22 (ar)h, u) = f(1 - -- + Th) h uddr
Gg|lhl12 2- f(1 12 +
22/1 [( T) |1 - + 2 Gg 1- - dr
م (2, -/ h
S 2 G |101 (1 - 7) d)
[(1 (1-T)) T) dr
2( = 2 2-4 G + (2-g) - 2-(1-g) G7 -
|2| |/
Therefore, we have proved the following bound.
Proposition 5. Let satisfy (2) for some 0 S q < and Gg > Then,
|V + h V v2 f(x))
ci Ggll/ 2-9 h112 02
G |h| [b|
+ (75)
with e : and 02 := (2 (2-g)== -
2)++1)
2-(1 9)
Note that in view of (66). this inequality recovers up to numerical constants the bound
67 for the
convex functions with Hölder third derivative, which correspond to q : T+ S S S covers the interval 0 S q S 1.
2v
GG := L and
It remains to establish the bound for the Gradient Normalized Smoothness 7(-). We fix an arbitrary
g E R.t and 7 > O, and consider the directions B., n Oz.g. i.e.
|h| <
and
| < - -(g. h) < ||و|| [h].
For such h. our bound
75 leads to ff(x)
[V h
2 f(z)h|/
I GGG 7
2ي || 7
|||||| + Gz 2/. /
We notice that to ensure
GG
y 2
|g
c2
-
llll-
is sufficient to choose
S+
|
2
G2
46

---

Published as a conference paper at ICLR 2026
and thus establish the following result.
Proposition 6. Let f satisfy (2) for some 0 2 q < 2 and Gq > 0. Then,
842g (--0)(1-))
Igll
Y (g( g)
This bound generalizes that one from Proposition as particular case 0 S q S 1. We also that, ignoring the numerical constant and substituting formally == provides us with the right power that coressonds to the Quasi-Self-Cor Ceff-Concordant functions from Proposition 3
Using this bound in our Theorem 6 with the following complexity find F(ax) 1 < & of order
2-4 for convex functions (c 0) immediately gives
I-4
24
2-
K
o(l
Gr
Do
(76)
for our algorithm, minimizing Generalized Quasi-Self-Concordae functions (72) of degree O S q 2. To the best of our knowledge, this global complexity is completely and has not been covered in the prior literature. This result recovers complexity (68) as a particular case and naturally interpolates the complexities for convex functions with Hölder continuous third derivative and Quasi-Self-Coocorddee functions (see also Table
To illustrate the power of results, return to Example of our theory.
to examine the direct consequences
Example 10. Let f(x) = | bl for some p 2 2, and || ll2 is the standard Euclidean
norm. Let us choose the norm in our space with B = A A, assuming B 0. Then, according to previous observations, funnciinoons,unniio belongs class (72) with
2(p-31 p-2
and
Gg == (p 1)(p 2).
According to Proposition O the PradiiettNormmllee Smoothness for this function is bounded
(5(x)
2
Mi-o
with a := 2= and Mi-a == ((p - 1)(p 2)230-7 p-1
At the same time, this objective
is uniformly convex (55) of degree p with constant op 22-P
Doikov & Nesterov 2021). Hence,
the gradient- crudient-dominance condition (44 is satisfied with
and De
Therefore, since by Theorem 6 our algorithm has the global linear rate, and the number of iterations achieve f(xxx is bounded
K
D. f(xo)-f"
0 ((
where O(-) hides numerical constant that depends only on p.
G.5 (Lo, Lio- FUNCTIONS
Let us assume that f satisfies the following inequality (Zhang et al. 2019):
[<>](>)]
Lo Ta (z)))
E R
(77)
47

---

Published as a conference paper at ICLR 2026
Then, for such functions, we have the following bound (see Lemma 2.5 in Vankovv et al. 2024)), for any æ, I=:
IV + h) Vf(x) V2f(2)/l = [V + h) v)(())]++ + f(x)) ||A|||
[L L1 L,
||||||| - b1
1 [ L |
||]||| (1 + efallAl).
We fix 0, R", and consider h By. Then, have upper bound
VV + h) Vf(=)) fax)/l]
S ||
as soon as
Lo + L)
+ ( v |lall-
it easy check that is satisfied for y 1+exp' all [((])l)) have established the following lower bound.
Lo 1
Therefore, we
Proposition 7. Let satisfy (77) for some Lo, L1 > Then,
lg [gl- (2(2. g) 2 Lo+Li VotaiVV(aa]
1g (()))))))) (1 + exp(
and for g fxx)), we obtain
(x
|V/())|- b [V)
where = 2 3.718.
Using these bounds directly in our Theorems
D and 2 we obtain the following complexity results:
For unconstrained minimization of non-convex function f()), to achieve || [V(xx))) S it is enough to perform
K Fo 06 + +1)
iterations of our algorithm.
For unconstrained minimization of convex function f(.), to achieve f(øk) - f S it enough perform
K =o[ Lo ([L
L, Do log Fu
iterations of our algorithm.
Therefore, we see that our method has a global convergence guarantee, at least as strong as that of first-order methods on (Lo, L1 )-mmoohh functions. Moreover, these convergence rates are achieved automatically, and the actual speed of the method will be the best within these problem classes.
G.6
SECOND-ORDER (M) (MMM-M)STOOTHH FUNCTIONS
Following
Xie al. 2024 Gratton et al. 2025 let us assume that f satisfies the following inequality:
f(x
f < (Mo + Mi [(]])(())))+]]] -vll-
E. R"
(78)
for some constants Mo. M1 2 Then, we have the bound, for all h E T
[v + h) Vf(x) fzx()//| I
My M
1212.
2
Restricting our direction onto a ball, h E B,, we have that
V h) Vf(z) v²f(w)
y Mo+M [[()]]
||a||
||lll [|]]]
where the last equation holds for the particular choice = Mo+ [[]]] the following statement.
2|gll
Therefore, we obtain
48

---

Published as a conference paper at ICLR 2026
Proposition Let satisfy (78) for some Mo, M1 > O. Then,
1/2
(5(2. g)
21lø11 Mo+Mi
Using this bound our Theorems [and 2
we obtain:
For unconstrained minimization, in the non-convex case, to achieve [V [I+ S is enough perform
M1/2 M
K
Fo O
23/2
iterations of our algorithm.
For unconstrained minimization, in the convex case, to achieve [(xx) - S- S e, it enough perform
K = <=[[[MM) 1/2 + /2 DD] log %
iterations of algorithm.
We see that a stronger second-order (Mo, M1) Mmmmothhssssss condition allows for improved complexity
results compared to first-order (Lo, L1 smmoohh functions. is important that all these problem classes are covered by our framework, which also allows for inexact Hessians.
H BOUNDS ON EFFECTIVE HESSIAN APPROXIMATIONS
H.1 SOFT MAXIMUM
Example 11 (Soft Maximum: Extended). In applications with multiclass classification, graph problems, and matrix games, we have
f(x) = s(u(x)),
where + is the LogSumExp loss. Note that s(.) Quasi-Self Concordant (Section G.3), and its gradient is the softmax: [Vs cth. -E e²t) Assume that
- Rd is an operator (e.g. linear or nonlinear model). and s(y) == log Σd e
Vu(x))l Eo.
[v2u(x)) S E11
x IR"
for some Eo. &1 2 0, and that operator u(.) is non-degenerate for some P > 0:
Vuux))= > =ula, x E R
(79)
introduce the following approximations and derive corresponding bounds:
Hf(()) = Vu(x) VF (u(()))))((())))) = O. we have
[V² H(*))
EL V)((())
I/H(()) = Vu(a)) Vu(x) > 0 (Gauss-Newton), we have
[V)((z) H(x)]l < c + (Eo + $ [V}
(f)(()) = Vu(x) Diag (Vs (u(x))) Vu(x)) ž 0 (Weighted Gauss-Newton), we have
[V' H())] < (5o + 5x) [V](())).
This assumption relaxed. holds, for example, when the model overparametrized (i.c. d).
49

---

Published as a conference paper at ICLR 2026
Proof. Note that
Vf(z) Vu(x) Vs (u(x)),
where Vu(x) Rdx= denotes the Jacobian of mapping u, and
f2f(2) = Vu(x) (u(z)) Vu(x) + (s (2u((x)
Vu(a)) (Vs Vs (u(x)) (o(())) Vu(x)
+ Σ [u(()))) (u(())
where (2)( is the tensor second derivatives or u, which we assume to bounded.
Consider the approximation
(xx) = Vu(x:) (u(x))TV(C) (u(=)) Vu(x)) = 0.
Note that when operator u(-) linear, H(x) is the exact Hessian. In general non-linear case, can bound
[2) H(x))
Σ Vs (u(x))), Vul(())
s Vl\Vs(u(
On the other hand,
[+)())
(V)(s))
Valla (s(())))
P [
where in the last inequality we used the non-degeneracy condition and the standard Euclidean norm Rdd Thus, we have the following bound [Vs(u(x))] v ff()).... that yields
[[())
2. Consider the approximation
H(x) = (u(a))Tul(e 7 0.
Then, as in the previous case, we have:
[V3)(z) - H(x)] = (V2) - Ia) Vu(x) + Σ V (s( vu((z)
Vu( (V²s(u(>)) - 1a) +
and it remains to bound the following term:
[V((x) (V²s(u(x)) - Ia) Vu(x)]
Vu(a)) Diag (Vs(u(x))) L. Vu(x)) (ale) Vu(x)
< V Diag (V<((<)))) I& Vu(z)) + [\<(m)
The first term can be bounded as follows:
T Diag (Vs(u(x))) - La Vu(x)]l s || |u(())] Diag (Vs (u(())) - Ial < 2
where we used the fact that max I
[Vs (u(x))), 1 S and assumption regarding the bound- edness of [u(x)]]. For the second term, we notice that
[V](x)]| <
Vu(z)] [ < Eo.
50

---

Published as a conference paper at ICLR 2026
since Vs(u(=)) is from the simplex. Hence,
VV(x))V(<)) IVVf(=))1 Σ fo)lVf(=))l..
and we finally obtain the following bound:
- - S c + (Eo + $1 ||Vf())]l.
Consider the approximation
((x) = Vu(Φ:) Diag (Vs (u(æ))) Vu(x)) o.
Repeating the reasoning from the previous case, it follows immediately that
f2)( H(x)ll
I
(5o + 5/) [VV
which is the required bound.
H.2 NONLINEAR EQUATIONS
Example 12 (Nonlinear Equations: Extended). Let u R2 -> RRd be nonlinear operator, and f(x) = )1 ;; (Gu(2), u(x))
for some G G >- O, and p 2 Note that -lll ||P a generalized self-concordant loss function (Section G.4). As the previous example, we assume that
|uu(x)] S Eo. [|Vau(x)] I E1,
RR
for some Eo, 2 and that the operator is non-degenerate, for some μ 0:
Bu( =PG1, E Rd
(80)
We introduce the following approximations and derive corresponding bounds:
If (((()) = ||]())| |= (G
[ V(()) = O, we have
[(²) H(x)
E vp
Vf(x)l--
HfH(x)) = ||(0)) {2) (Gu(z) 2 0, we have
[[2)(.)) xz)] < (p ( - [Vf(2) &
JP
IfH((z) = - vf
(Fisher-type), we have
[v2 H(x)]
Ep [V + ([)))
Proof. Note that
Vs(x) = [[(x))|p~VV((()) Gu(x),
where Vu(x)= E gddxn denotes the Jacobian matrix of mapping u, and, for any direction E R", have (v²)()),,
( Vu( (uta))
+ 2) (=)) vu(=)
where v²u(#) is the tensor of second derivatives of u, which we assume to be bounded.
1. Consider the approximation
H(:) = [|u(z)))-~Vu(()) TGVu(a) + |
0.
(81)
51

---

Published as a conference paper at ICLR 2026
Note that it resembles combination of the Gauss-Newter and Fisher approximation matrices, and for = it gives the classic Gauss-Newton approximation. Moreover, when the operator u is linear, the problem is convex, and č O. Thus (8I) gives exact Hessian in this case. Let us consider
(v (w)h, h) (H( (,) h)
(Gu(2), Vau(w) [h, hb)
therefore
[V2 - -H(2)
((v - H(()) h. h)
max h:||||=11
E []]|(<)]|==1 E1 (pf(2))
Using our non-degeneracy condition, we can further bound
[f(()) ||(x)) 2 Vu(x)) Gu(x)] [u(x)]
|[(=))] ((tp)) (Gu( Vu(z)B- Tu(()))
Thus, we have ||u())| P-1 < [ Il.. which gives us the following bound on the approxima- tion error:
|f()))|
vp
Consider the approximation
(xx) = Vul= 7 o.
Using observations from the previous step,
[V²f(x)
H(z)
max h:]1/=|11
((V2f(z) H(z)) h.h
(p 20=2)](((
max (Gu(z), Vu(x)h)²
h: h|=1
+ |[(
max (Gu(#)) Pun (h. h|) h:|AA||1
(p (1)))))))
max (Gu(z).Vuzz)h)) + [Vxx))]
4: h|=1
It remains to notice that, for | = 1, we have:
[u(x)))PA(Gu(()) Vu(2)))2 =
Vu(x)h) (Cub] [u(x))
|- (Gu(z)) (V()
$ 30 1
which gives the desired bound.
Consider the approximation
H(x)
P-2 v(xx) 1 0. ||(>|||
Note this matrix can be equivalently represented as
H(x) (p- [V] Gu(z)u(()) (u(())))) (TV())) GVu(x).
52

---

Published as a conference paper at ICLR 2026
Therefore, have
[ H())
max h: A
Vu(a)h) + & vR Vulle)
(V/()]l $1 [])
|vf
H.3 SEPARABLE OPTIMIZATION
Example 13 (Separable Optimization: Extended), Consider the following structure of the objective,
((z) = Σ M(x). i=1
:= l (x,()),, for a convex nonnegative loss function and mappings u, : R + R. Consider logistic regression, E(t) == log(1 exp(t). and the following Fisher-type Hessian approximation:
where f=(x))=
H
Σ [((+)\V(()) =0. O.
Let each ui be nonlinear mapping, and f be gradient-dominate that, for some Eo. E 2 0: [V,,( S to. [V),(x))| S &,, v1 sis
54
function. Assume Then, we have
|V2 H())ll - ( (1) (f* + Del Del (()))t
If the mappings (x) = (a,, x)) - by are linear models, then, by setting B = Er= a.a we have
V H(x:)l S f(x) s S (x)|l
for E Fo.
Proof. Note that
Vf(x) = VV.(z) = Σ e (ux(x) Vu(xx)
and
{()(2) Σ [e" (u(())))v(())Vv(() & (v,())))))))) (w.(z))
Consider approximation
H(x)) V[(x)VV\()) = d ( 2 0.
Then, we have
-xx))
Σ ( (e" (ux())) E ( (u(x)))²) Vu((z)Vu,(z) l' (u(())
20 Σ e' 21 (ou 8' (u((x)) (2)
(m) 28 (
+ Σ l (u((z)) (2 (x)
53

---

Published as a conference paper at ICLR 2026
where we used that (t) (t) (1 (t)) and [V((z)Vu((z)
Applying our bounds on [a)( and (22(()) for any i, and using the fact that || - 26' (t) <
for any f, we have
[V2
(cé E1) Σ l (u,())) s (48 + f(z),
where in the last inequality we used that E' (t) {(t) for all t. Now, consider two important cases.
Let (x( be non-linear mappings and let f()) be gradient-dominate, i.e., condition 54h holds. Then, we have the bound:
[ H(x)ll s +1+ f(x) S (c +1) [s + +
D.ll[[(()) 0
2. Another important case is when (a, x) b; are linear models, where {a, J given data. Note that this case, the Gauss-Newton matrix is constant, and we can set
d B E Vu(e))u(()) = Σ a.a
d
= 0,
and natural use as our choice of the Euclidean norm. At the same time, our Fisher approximation becomes
((x) V[(x))V[( Σ El((())aaaa = 0.
Therefore, result in bound
[V*)(x) - H(x)ll
11 (t" (u((x) 1' (u(()))) a.
==1
Σ ( 28 (ux(=)))
1
Σ (u,(x)) & f(x)) 1=1
which corresponds to the previous case with 5o = 1 and & = Due to convexity of f. we have
| H(z)]l s f(x) s +*+ D f
for all points from the initial sublevel set: Fo. where all iterates of algorithm belong to.
H.4 RECOVERING COMPLEXITIES FOR PRACTICAL APPROXIMATIONS
Contribution of the Degrees of π. As we saw, the general form of our lower bound is given by structural assumption (10.. for problem cases, it appears to be harmonic mean of simple
monomials: x
Σi == Mi-a,t t-s, where a; E [0, 1] are some degrees that depend on
the problem class and on the level of Hessian approximation 3. For example, let assume that
(1) is the harmonic mean of two monomials (as, e.g. for (Lo, L1 -funntioos
(77):: =(1)
(M + -2)- for some M2 > 0 and 0 a1,02 < 1. Then, for the non-convex the global complexity of the method is (Corollary solve the problem, where E > 0 the target accuracy for the gradient norm. We show that the fastest
K = O (Fo |_M__ + Ma_ iterations to
possible rate corresponds to the smallest degree, == min a; while the other exponents correspond ISidd
additional slow terms. Notably, our proof is based on first selecting the smallest a, to establish the progress, which highlights its importance.
The definition of (-). This paragraph is an extended version a short note in Section 5 The notion of π 110 is structural assumption the global behavior of the r(-). It is needed to translate our knowledge of a problem class to the complexity bounds in their standard form. Formally there could be many choices for while 7(-) is defined in unique way. However, is important that our method does not need to know the particular problem class or the particular n, and by implementing simple adaptive search (Algorithm 3) the method becomes
Smoothness
54

---

Published as a conference paper at ICLR 2026
parameter-free. Let consider several important examples of known structures of the lower bound π.
Function with I--Lipschitz Hessian (Example with v = 1). Then, 7(x) 2 ( Hence, (() = () and the corresponding global complexity in the convex case (Theorem) 2 is
LD3
where & > O is the target accuracy for the functional residual, and is the diameter of the initial sublevel set.
Convex functions with L-Lipschitz Third Derivative (Example 2 with 1). Then,
(x) 2 2r ( Hence, (l) (1) The corresponding complexity of the method (Theorem is
LD* 1/3
o
8
Crasi-Self-Concorddee functions (Example and the corresponding complexity (Theorem is
Then, 7(x)
1 M
Hence, =(t) = M
o M MD !)
(global linear rate of convergence).
(Lo, Li)-smooth functions (Example
4h.
Hence, Then, 7(x) 2 1tc Lo [abbaa
[f(2)
(t)
14c Lo + L Note that this expression also matches the structural assumption æ in (10). And the corresponding complexity of the method becomes (Theorem
o (L, D
log
We see that we recover the right complexities all known special cases. Every particular problem class leads to the specific structure of the lower bound (-). However, the power of result is that we do not need to know and fix the problem class the method, adapting to the best possible bound.
One interesting example follows from the basic properties of ? under simple operations (Section 2). Let us assume that our objective is represented as finite sum of functions: f(x) = Σ f((r). Every function in the
different problem class, and therefore, every function fi might have a different lower bound (t) (e.g. as in the above examples). In this case, the whole objective does belong to any 'standard' problem class, and therefore, simple assumptions such as Lipschitzness of the Hessian are not applicable in this case. However, the lower bound TT-) for the whole objective can be computed as the Harmonic mean of the lower bounds for the components:
might belong
7() >
Σ (1(
The effect of inexact Hessian. This paragraph also an extension of Section S designed to show how we derive complexities for method with inexact Hessian using condition (12) If we assume (2)), then the Gradient-Normalized Smoothness, when using the Hessian approximation, is bounded according to our rules, as:
(x) 2 (x) |لा(াा
C, + (V(
where Yi (x) is the know the lower bound (-) for the exact Hessian (c.g. any of the problem classes above), then T(-) for the method with inexact Hessian can be computed in a form that satisfies the structural assumption
Smoothness for the exact Hessian. In other words, if we
-1
(()
(.( + S
C. 78
55

---

Published as a conference paper at ICLR 2026
And immediately obtain the complexity result for the method with inexact Hessian (Corollaries and 3). We see that the total complexity of the method becomes the sum of the complexity for the exact case plus two additional terms that depend on C₁. C2. and the degree of approximation S.
One important consequence our theory is that when C₁ R 0 is very small or zero, and [ < a, where is the minimal degree of the monomial in the expression for æ, then the rate of convergence not affected by the Hessian inexactness (see also Figure D We see that these conditions hold, e.g.. for the Fisher and Causs-Newton approximations in several applications (Examples we have 3 = 0. Therefore, in these applications, the use of the inexact Hessian will give us the same global rate as the exact Newton method, while computation of every step much more efficient.
8.. where
Let us consider the concrete example with the logistic regression problem and the Fisher approxima- tion matrix (3). The logistic regression is Quasi-Self-Concordaae and hence я (t) M7 (Example where (t) is the bound for the Gradient-Normalizze Smoothness with exact Hessian. When using the Fisher approximation, we have (2) satisfied with C₁ f*, C2 D. and B (Example 6) Therefore, the Gradient-Normalicn
Smoothness for the Fisher approximation is bounded as:
( 2 и ([[V[(())I)) with T()) +
and the corresponding complexity becomes:
O ([MDD MMND+D D2 na
log
If f se 0 (well separated data), this gives very fast global linear rate. To the best of our knowledge, we are the first to establish such rate for the inexact Newton method with the Fisher approximation matrix. Similar reasoning also work for applications with Nonlinear Equations (Example 7 and Soft
Maximum (LogSumExp) (Example 8) with Gauss-Newton approximations.
Below, we present formal statement, serving good example of the practical applicability of our notion. In Proposition y we show that our method achieves global linear rate of convergence on the logistic regression problem.
Proposition 9 (A global linear rate of convergence for the inexact Hessian.). Consider the logistic regression objective f(x) Σ.= (xx), where f((x) = log (1 + exp ((a,, x) b;)). Then, for Algorithm 7 with
((x)
[()))\ = 0, (Fisher approximation matrix)
the corresponding complexity is
([MD+ + D2
p' log
If the data is well separated (f* sz 0), this gives a global linear rate.
Proof. Assuming bounded as
12p the Gradient-Normalized Smoothness when using inexact Hessian
7(x) 2 (z) + [ [V )
(The "Hessian inexactness" property)
where 7'1 (xx is the Gradient-Normalizer Smoothness for the exact Hessian. Since f(x) Quasi-Self-
Concordant, 7/ (x) > According to Example 6 H(x:) satisfies condition 12 with C₁ f*,
C2 = D. and B = 0. Then, we result the following bound:
(x)) 2 (M+DD) (M+D++ D+ M
According to Corollary 2 complexity for the method with inexact Hessian becomes:
K = o <[MD+ p' -
Here, the term MD log corresponds to the previously established complexity for the method with exact Hessian (see Table []. When the optimal value f zs O. we result in the global linear rate of converge.
56


Reviews:
[{"review_id": "ijOul3TYg1", "reviewer": "Reviewer_F4Yq", "summary": "This paper introduces the concept of Gradient-Normalized Smoothness (GNS) as a new local characterization of the gradient field and Hessian approximation in optimization, particularly for the design and convergence analysis of second-order methods with approximate Hessians. Building on this notion, the authors propose a global convergence framework for both convex and non-convex optimization, unifying the treatment of smoothness and approximate second-order information under a single analytic lens. The work claims to recover state-of-the-art complexities for a wide range of problem classes—including Hölder-smooth, self-concordant, and generalized smoothness settings—and demonstrates the practical advantages and competitive empirical performance of the approach in numerous experiments, particularly with logistic regression, softmax, and non-convex losses.", "questions": "**Q1.** The main challenge in second-order optimization lies in the high cost of computing the Hessian matrix. However, in practice, the Hessian–vector product can be computed efficiently without forming the full matrix by simply applying automatic differentiation twice. Could the authors briefly explain why such techniques are not suitable or sufficient for the tasks considered in this paper?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**1. Unified Theoretical Framework**: The introduction and analysis of Gradient-Normalized Smoothness offers a conceptually appealing unification of smoothness and Hessian approximation error, allowing the same framework to recover or extend the best known rates for several classes of optimization problems.\n\n**2. Strong Experimental and Visual Evidence.**: The paper provides thorough experimental validation with clear visualizations, which is easy to follow, and I like the layout of the paper (e.g., highlighting of some important examples and definitions).", "weaknesses": "I am not an expert in optimization; therefore, from my perspective, the paper does not exhibit any specific weaknesses. I will finalize my rating after reviewing other reviewers’ comments and the authors’ responses.", "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": "0vqywjgOsu", "reviewer": "Reviewer_tjcC", "summary": "The paper introduces Gradient Normalized Smoothness as a unifying device to analyze approximate Newton methods. The framework couples objective smoothness with Hessian approximation quality and shows when an approximate Hessian can match exact Newton rates. The analysis recovers state of the art rates across several function classes and provides applications to logistic regression with Fisher and to softmax problems. The experiments are small but consistent with the theory.", "questions": "1. Could you clarify what makes the gradient-based normalization introduced in Definition 1(i.e., the term (1/γ) ||g||* ||h||) conceptually novel or more powerful than the traditional smoothness bounds used in analyses of cubically regularized Newton or trust-region methods? In particular, what analytical challenges does this specific normalization address or simplify that previous formulations do not?\n\n2. Could you provide more intuition for why the harmonic mean structure is considered the “right” formulation? Does it emerge naturally from combining different smoothness assumptions, or is it primarily introduced as a flexible, unifying model chosen to encompass all the examples presented in the paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces a powerful new theoretical framework for developing optimization algorithms that leverage approximate second-order information while guaranteeing fast global convergence for both convex and non-convex objectives. The central innovation is the Gradient-Normalized Smoothness (GNS), a novel, universal notion that locally characterizes the maximum radius of a ball around the current point where the gradient field is well-approximated. This concept provides a unified mechanism to connect errors stemming from Hessian inexactness and Taylor's approximation, effectively translating local properties into the method's global performance without relying on predefined problem class specific parameters.\n\n2. Algorithm 1 uses a simple gradient regularization structure where the step-size ($\\gamma_k$) is chosen based on the GNS quantity, allowing it to adapt automatically to the objective's characteristics and the degree of the Hessian approximation. The theory successfully handles inexact Hessians $H_k$ provided they satisfy a condition related to the gradient norm (Equation 2). When the Hessian is exact, the framework recovers state-of-the-art global convergence rates for various function classes, including those with Hölder-continuous derivatives and quasi-Self-Concordant functions. Notably, the paper demonstrates that if the objective's smoothness degree ($\\alpha$) dominates the approximation degree ($\\beta$), the method with inexact Hessians achieves the same global rate as the full Newton method.\n\n3. The practical effectiveness is validated using specific approximate Hessians popular in machine learning, such as Fisher and Gauss-Newton matrices, which satisfy the derived bounds and yield new global convergence results. Furthermore, experimental results suggest that Algorithm 1 using an inexact Hessian approximation (when aligned with the theory) is more numerically stable than the Exact Newton method, which can fail to converge on non-convex objectives due to ill-conditioning issues.", "weaknesses": "1. The notion of Gradient-Normalized Smoothness is defined mathematically but not well-motivated in terms of optimization geometry or curvature behavior. The crucial element appears to be the specific gradient-based normalization ((1/γ) ||g||* ||h||). The paper should elaborate on why this specific normalization is the key that unlocks the unified analysis. It is also unclear how this notion of smoothness compares to established notions like relative or anisotropic smoothness. \n\n3. The theoretical framework fundamentally relies on the existence of γ(x_k), which is defined via a maximization condition but cannot be computed in practice. While the paper acknowledges this limitation and proposes an adaptive search procedure (Algorithm 3 in Appendix D) for implementation, the authors should be more upfront in the main text about this fact.\n\n4. The structural assumption (equation 10) is key to connecting the local definition of GND to the global rates, but its introduction in section 4 feels abrupt and unexpected. It would help if it was alluded to and motivated in earlier sections.", "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": "xAHmHp9yYO", "reviewer": "Reviewer_C1PU", "summary": "The paper introduces a new assumption on Hessian inexactness and gradient-normalized smoothness. Under the gradient-normalized smoothness assumption, they provide the best-known rates of the Gradient-Regularized Newton method for (a) bounded Hessian, (b) Lipschitz Hessian, (c) third-order Lipschitz smoothness, (d) quasi self-concordant functions, and new rates for generalized self-concordant functions. Additionally, they introduce Gradient-Regularized Newton with Approximate Hessians and prove new convergence rates.", "questions": "No questions.", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very well-written, accurate, and clear. The results are correct, new, and interesting for the community. It is an outstanding paper. I list several strengths of the paper:\n\n1. The paper proposes new concepts of smoothness that generalize and easily connect many well-known and modern classes of functions. For this class of gradient-normalized smooth functions, they provide examples of functions satisfying it. For classical function classes, they provide a lower bound on the smoothness constant $\\gamma(x)$.\n\n2. The method with proposed step-sizes is universal and adapts to the problem class, achieving the best-known rates with second-order information. Moreover, the same method works with only first-order oracles by using inexact Hessians, and the paper provides new rates in this setting.\n\n3. The experiments show the effectiveness of the proposed step-sizes.", "weaknesses": "I couldn’t find any major weakness in the paper. Minor:\n1. While the numerical experiments show the effectiveness of the Gradient-Regularized Newton method with the proposed stepsizes, it would be beneficial to compare it with other adaptive or universal methods, both with exact and inexact Hessians.", "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": "b1VyvR5nns", "reviewer": "Reviewer_scSv", "summary": "The paper present a very impressive general theory for gradient regularized Newton methods. The key observation is characterizing the amount of regularization $\\gamma(x)$ through an implicit definition. What is also noteworthy is the many instantiations including Holder smooth Hessians, quasi-Self-Concordant,  $(L_0,L_1)$--smoothness, all of which provide a lower bound on this implicitly defined $\\gamma(x),$ which is needed to execute the algorithm. The main issues I see are regarding computing $\\gamma(x)$ and generally the fit within ICLR.", "questions": "*Questions*\n\n1. Implicitly defined $\\gamma(x)$ and lower bounds. \nIn general, $\\gamma(x,g)$ is implicitly defined, and needs to be computed or bounded to be used. The paper is clear about this, and gives many useful lower bounds for certain problem classes. But still seem some awkward issues around this. For instance, you give a type of adaptive line search procedure in Algorithm 3, and bound the number of oracle calls to $\\mathcal{O}(K)$ where $K$ is the number of iterations of Algorithm K. But here you rely on the $\\gamma_k$ computed by Algorithm 3 will satisfy the lowers bounds you give for $\\gamma(x_k, F'(x_k)).$ Here I think you need a formal statement about the complexity of this adaptive line search, you can use it to guarantee that Algorithm 3 will have a meaningful complexity. Another clear issue is with your main result for convex functions in Theorem 2, which relies on the exact computation $\\gamma_k = \\gamma(x_k).$ Here I assume it is hard to characterize the complexity of solving this equation, and of course, exact solutions are probably inaccessible. \n\n\n\n\n2. Lines 069-065: You claim that you will present a linear convergence result for when using inexact Hessians, and no strong convexity type assumptions. But where exactly is this result? The only linear convergence I see in the main paper is the instantiation of Theorem 2 for the class of Quasi-Self-Concordant functions, which relies on using the exact Hessian. Could you clarify this statement and/or correct it?\n\n\n*Minor* \n\n1. A small mistake you repeat is to write \"...method equation 1\" where all prepositions have been dropped. It should be \"... the method in equation 1\".\n\n2. At a high level, it seems your gradient normalized smoothness does to Newton, what Directional smoothness, has done for gradient descent methods. That is, you identity an implicitly defined stepwise, that always guarantees descent, and generalizing other notations of smoothness including $(L\\_0, L\\_1)$-smooothness. This is exactly what the claims of the paper [] are, but for gradient based methods. So this in no way diminishes your contributions, it just seems it could be an interesting connection.\n\n3. The assumption in eq (10) should be formally stated as such. It's a bit confusing how it is now stated. It would be much clearer if you have\n\nAssumption 1.  There exists $0 \\leq \\alpha\\_i \\leq 1$ and $M_{1-\\alpha\\_i} \\geq 0$ for $i=1, ..., d$ such that Eq (10) holds.\n\nThe same things goes for its counterpart eq (40) in the appendix.\n\n4. Corollary 1. You \"Under assumptions of Theorem 1 we can bound ...\" But don't you mean, if equation (8) holds and Assumption 1 (above) hold? This is exactly one of the reasons I'm a bit confused about (10) being an assumption or not.\n\n5. There are a few type-Os, quite a few missing prepositions, and similar minor mistakes throughout. You should take a pass with LLM or grammar check to fix theses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is elegant work in deterministic optimization for Newton type methods. Both unifying previous theories, extending to in-exact Hessians, and developing many examples.", "weaknesses": "This seems to be mostly a follow up work of Doikov2023 and Doikov 2024a, which allows for inexact Hessians, and unifies some of these previous results. It's a dense literature, and difficult from reading this paper to know exactly what is new and what is not. Here I think the authors should write a more extensive background/related work section in the appendix, which makes it clear which parts are taken from which papers, and which parts are entirely new. The main paper itself does not make this very clear, and I had to open some of the prior work to get a sense of what had been done.\n\nAnother weakness is generally the fit with ICLR, its reviewing process, and to a lesser degree the audience.  Your paper and theory look very solid. But I regret to say, having it reviewed by ICLR is not a good fit. First the topic, which is full batch optimization. Even convex learning problems, such as GLMs, are only difficult to solve when there is so much data we need stochastic gradients. Your theory depends heavily on being in the deterministic setting. Furthermore, your result rely on the proofs, and your paper is (including proofs+ appendix), 48 pages long.  The turn around time of ICLR does not permit reviewers to go over your proofs in detail. I for one have only sampled your proofs. You would be much better served by submitting this substantial piece of work to an optimization journal (SIOPT, Math programming ...etc) where you would get a proper review.\n\n\nNot really clear/transparent on limitations of Newton's method in machine learning. You introduction frames it as if Newton methods  are extensively used in ML. But the issues around dealing with stochastic estimates and non-convexity, makes most Newton type approach inapplicable.", "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)