Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness
Authors: Konstantinos Oikonomidis
Jan Quan
Emanuel Laude
Panagiotis Patrinos
Venue: ICML 2025 oral (2025)
Keywords: nonconvex optimization
generalized smoothness
first-order methods
Primary area: optimization

Abstract: We analyze nonlinearly preconditioned gradient methods for solving smooth minimization problems. We introduce a generalized smoothness property, based on the notion of abstract convexity, that is broader than Lipschitz smoothness and provide sufficient first- and second-order conditions. Notably, our framework encapsulates algorithms associated with the gradient clipping method and brings out novel insights for the class of $(L_0,L_1)$-smooth functions that has received widespread interest recently, thus allowing us to extend beyond already established methods. We investigate the convergence of the proposed method in both the convex and nonconvex setting.

Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness
Konstantinos Oikonomidis 12 Jan Quan 12 Emanuel Laude Panagiotis Patrinos' 12
Abstract
where 6² .R" - IR is convex and is called the dual ref- erence function. The convex conjugate of ø", Φ is called the reference function and its properties are crucial to our analysis. This general framework was originally analyzed in (Maddison et al., 2021) under the so-called dual relative smoothness condition for convex and essentially smooth functions. In the general nonconvex and composite non- smooth setting, it was studied in (Laude & Patrinos, 2025) under a condition called the anisotropic descent property, which was itself first introduced in (Laude et al., 2023) and can be regarded as a globalization of anisotropic prox- regularity (Laude, 2021) for smooth functions.
We analyze nonlinearly preconditioned gradient methods for solving smooth minimization prob- lems. We introduce generalized smoothness property, based on the notion of abstract convex- ity, that is broader than Lipschitz smoothness and provide sufficient first- and second-order condi- tions. Notably, our framework encapsulates al- gorithms associated with the gradient clipping method and brings out novel insights for the class of (Lo, -smoshh functions that has received widespread interest recently, thus allowing us to extend beyond already established methods. We investigate the convergence the proposed method in both the convex and nonconvex set- ting.
Our analysis is mainly focused functions that are both generated by kernel function h R + R4 ((o)), }, thus resulting in two different families of algorithms. The first one is given by the composition with the Euclidean norm, i.e., Φ = o and referred to as the isotmpic reference function. iteration (2) takes the form of gradient descent with scalar stepsize that depends the iterates. The second is sep- arable sum obtained via o(x) Σ h(x,), henceforth called the anisotropic reference function. In this case, (2) becomes gradient descent with a coordinate-wise stepsize that depends on the iterates of the algorithm. We remark that although the anisotropic reference function makes the analysis of the method more challenging, generates more interesting algorithms, akin the ones that are often used in practice.
types of reference
this case, the main
1. Introduction and preliminaries
We consider minimization problems of the form:
min f(x).
(1)
#ER
where I is a continuously differentiable and possibly non- convex function. While gradient descent is reliable solver
for this type of problems, many cases it does not fully take advantage of the cost function properties and requires well-tuned costly stepsize strategies to converge.
In this paper we thus focus nonlinearly preconditioned gradient methods that are tailored to the properties of the cost function. Given stepsizes 7 > and > 0 and a starting point E IR", we consider the following iteration:
1.1. Motivation
Unifying framework for clipping algorithms. Gradient clipping and signed gradient methods have garnered atten- tion in recent years due to their efficiency in neural net- work training and other applications (Bernstein et al., 2018; Gorbunov et al., 2020; Zhang et al., 2020a;b;e; Koloskova et al., 2023; Kunstner et al., 2024). The intuition behind gradient clipping is straightforward, since by clipping one does not allow the potentially very large (stochastic) gradi- ents to hinder the training. Nevertheless, in many cases the clipping threshold and stepsize should be carefully tuned in practice, otherwise leading to suboptimal performance (Koloskova et al., 2023). While algorithms of this type
T (z
Vo (AV
(2)
'Department of Electrical Engincering (ESAT-STADIUS)) KU Leuven, Kasteelpark Areuberg 10, 3001 Leuven, Belgium Leuven.Al-KU Leuven Institute for AI, 3000 Leuven, Belgium Proxima Fusion GmbHL Flößergasse 2, 81369 Munich, Ger- many. Correspondence to: Konstantinos Oikonomidis <kon- cantinos.oikononiin @ kuleuven.be>.
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Nonlinearly Preconditioned Gradient Methods
Table 1. Examples of kernel functions along with the generated preconditioner and its (generalized) derivative in one dimension. The last column indicates whether Assumption 1.1 and Assumption 1.2 are satisfied, respectively.
h(x)
dom
(v)
h h²((y)
Assumption 1.1/1.2
cosh(x) -
I
arcsinh(y)
VIV
VI+y²
exp((xr) - ||x]
In(1 + | w))ggn(y)
VIV
I+lyl
- |||| In(1 - |x:))
(-1,1)
V14
++|=l
(1 (1+1b1)²
vI x²
[-1,1]
(1 + 1/2)
VI4
Vi+y²
aarctan((1) (2) - (n(cos((arctanh(n))
(-1,1)
tanh(y)
1 - tanh
VIV
x² + 6 (1)
[-1,1]
min max(11,)))
dc (1 ((T).))))
VIX
have been analyzed under various smoothness and stochas- ticity assumptions, there does not seem to exist simple unifying framework that encapsulates them. Motivated by this gap, propose framework that provides further in- sights into existing methods but also naturally generates new algorithms.
which states that a function is P-convex if it can be writ- ten as the pointwise supremum over family of nonlinear functions. Similarly to the fact that every proper, Isc and convex function can be expressed of its affine minorizers (Rockafellar & Wets, 1998, Theo- rem 8.13), anisotropic smoothness then requires that - is a pointwise supremum of nonlinear minorizers. This fact is once again in parallel to classical L-smoothness, which requires that -f the pointwise supremum over concave quadratics, and leads an envelope representation of f that is useful in studying the corresponding calculus. In that gard, anisotropic smoothness is straightforward extension of Lipschitz smoothness. A visualization of the concept of d-convexity is shown in Figure 1.
pointwise supremum
iniiorration-miiniizzttoi and (D-convexity. plethora of well-known optimization algorithms belong to the so- called majorization majorization-minimizztoooo framework in that they are generated by successively minimizing upper bounds of the objective function. As classical example, under Lipschitz smoothness of f, the celebrated gradient descent method with stepsize 1/L iteratively minimizes the follow- ing (global) quadratic upper bound around the current point e R":
f(x)
f(x) f() x + E|(2.
is straightforward that this inequality can be written as
f(x) < ( (0(((= - (( 9)). (3)
x
for o = 211-11 -= - V Going beyond the standard Lipschitzian assumptions, it natural to consider reference functions & that generate less restrictive descent inequalities thus allowing us to ef- ficiently tackle more general problems. This is exactly the anisotropic descent property (Laude & Patrinos, 2025, Def- inition 3.1) and minimizing this upper bound leads to the algorithm described in (2) (for À fixed). Considering (3), it is natural to examine reference functions that are strongly convex and grow faster than a quadratic in order to obtain a less restrictive descent inequality. It turns out that in many interesting cases, the preconditioner in (2) becomes simi- lar to sigmoid function and the algorithmic step takes the form of popular algorithms. We present examples of kernel functions and the corresponding preconditioners in Table 1.
Figure Visualization of the quadratic upper bounds of the func- tion f(z) at various points. By flipping the figure it can be seen that ff d-convex function: it is the pointwise supremum over concave quadratics of the form -0x y) + 3. with ø = / -|I-1* and y, Note that this function is not convex in the classical sense, as there are no linear functions supporting it.
1.2. Our contribution
Our approach departs from and improves upon existing works in the following aspects.
The abstraction discussed in the previous paragraph is in fact tightly connected to the notion of d--onvexity (also known c-coneavity the optimal transport literature),
We describe a common nonlinear gradient precon-
2

---

Nonlinearly Preconditioned Gradient Methods
ditioning scheme for the main iterates, i.e., without momentum nor exponential moving average mecha- nisms, of popular algorithms including gradient clip- ping, Adam, Adagrad and recently introduced meth- ods for (To, -mmooohssssssss. These precondition- ers are gradients of smooth convex functions and have sigmoid shape, reminiscent of common activa- tion functions in neural networks.
Furthermore, relaxed proximal point algorithm with non- linear preconditioning akin to (2) for solving monotone in- clusion problems was studied in (Laude & Patrinos, 2023).
Generalized smoothness. Our work is also connected to other notions of generalized smoothness, i.e., descent in- equalities beyond the standard Lipschitzian assumptions. To begin with, Bregman (relative) smoothness is pop- ular extension of Lipschitz smoothness (Bauschke et al., 2017a; Lu et al., 2018; Bolte et al., 2018; Ahookhosh et al., 2021) that can encapsulate wide variety of func- tions such as those whose Hessians exhibit a certain poly- nomial growth (Lu et al., 2018). Other notions of gen- eralized smoothness include Hölder smoothness (Bredies, 2008; Nesterov, 2015) and also higher-order smoothness where higher-order derivatives of f are Lipschitz continu- ous (Nesterov & Polyak, 2006; Doikov & Nesterov, 2020).
We introduce (I., -aanisooroii smoothness, which extends (Laude & Patrinos, 2025) allowing for two constants and a reference function & of possibly non- full domain and prove that it is less restrictive than L-smoothness. Through a novel technique we study necessary and sufficient first- and second-order con- ditions for (T,, T.)-anisotropic smoothness, in the pro- cess obtaining novel characterizations for the forward operator A, which in turn leads to new insights into the class of ( (Lo, L1 --mooth functions.
Recently, new concept of smoothness has been introduced in order to capture the cases where the norm of the Hes- sian is upper bounded by some function of the norm of the gradient (Zhang et al., 2020b; Chen et al., 2020; Li et al., 2024). This condition, which in its most popular form is called (Lo, -mmmooothsssss (Zhang et al., 2020b, Defini- tion 1), has received widespread attention. Various existing methods have been analyzed under this new smoothness condition (Wang et al., 2023; Faw et al., 2023; Koloskova et al., 2023), while also new ones have been proposed (Gor- bunov et al., 2024; Vankov et al., 2024). We remark that a number of these algorithms can actually be obtained in (2) via a suitable choice of the reference function. Neverthe- less, it is important to note that in contrast the aforemen- tioned types of smoothness, anisotropic smoothness is not obtained via a linearization of the cost function around a point and thus it is not straightforward to compare the ob- tained descent lemmas.
We analyze the convergence of (2) in the nonconvex setting, obtaining new results for our stationarity mea- sure. In the convex setting, we prove the sublinear rate of the method for a large family of isotropic ref- erence functions, utilizing only a simple dual charac- terization. In the more challenging case where é is anisotropie, we present an unconventional proof that is based on the envelope representation of anisotropic smoothness. We are thus able to obtain standard (()KK) convergence rates for large classes of func- tions.
1.3. Related work
Dual space preconditioning and anisotropic smooth- ness. The scheme described in (2) was originally intro- duced in (Maddison et al., 2021) in the convex setting, where it was analyzed under a condition called dual relative smoothness for which sufficient second-order conditions were provided. In (Laude& & Patrinos, 2025) the anisotropic smoothness condition was studied, which was shown to naturally lead to the convergence of the method in the non- convex and proximal case. Moreover, in (Léger & Aubin- Frankowski, 2023) the scheme was also analyzed under the general framework of d--onvexity and a sufficient second- order condition for anisotropic smoothness was provided. Nevertheless, this requires that Φ E C*(RR") satisfies the non non-negative cross curvature condition from optimal trans- port (NNCC) (see (Figalli et al., 2011, Assumption (B3)) and (Léger & which is a strong assumption that does not hold for many interesting reference functions. An accelerated version of the method for Lipschitz smooth problems was introduced and studied in (Kim et al., 2023). Recently, the method was also extended to measure spaces in (Bonet et al., 2024).
1.4. Notation
We denote by (.--) the standard Euclidean inner product on IR and by || the standard Euclidean norm on Iº as well as the spectral norm for matrices. For a square ma- trix A with real spectrum, (A) and Amin (A) denote the largest and smallest eigenvalue respectively. We de- note by (*(Y) the class of functions which are k times continuously differentiable on an open set Y S R". For proper function f F" + R and X 2 0 we define the episcaling (A fx) = Af(A-1a) for A > 0 and (A * [xx = ò0op (x) otherwise. We adopt the notions of essential smoothness, essential strict convexity and Leg- endre functions from (Rockafellar, 1997, Section 26): we say that a proper, Isc and convex function f R= + R is essentially smooth if int f) A 0 and ʃ is differ- entiable on int(dom) f) such that [[Vf(=") + co, when- ever int f) 3 x" + x E bdry dom f. and essen-
2023, Definition 2.8)).
3

---

Nonlinearly Preconditioned Gradient Methods
tially strictly convex, if / is strictly convex on every con- vex subset of dom 0f, and Legendre, if f is both essen- tially smooth and essentially strictly convex. In particular, a smooth convex function on R" is essentially smooth.
If. furthermore, h satisfies Assumption 1.2, then o² C² (R(T)).
We provide examples of interesting kemnel functions, along with the assumptions that they satisfy, in Table 1.
Let R + IR" be a locally Lipschitz function, we denote the (Clarke) generalized Jacobian as 0cF(()) - con - VF(x;) It & [ where Q2 is the set of points where F' fails to be differentiable. Ie denotes the projection on set C. For an f C2 (R*) we say that it is (Lo, L1) -mmooth for some Lo, L > 0 if it holds that [[)][ v Lo + V f(z)] for all æ E R". Otherwise we adopt the notation from (Rockafellar& & Wets, 1998).
1.6. Connections with existing methods
As already mentioned, the scheme presented in (2) encom- passes the basic iterations of various algorithms that are widely used in practice. In this subsection we thus provide some examples that showcase the generalizing properties of our framework.
Example 1.4. The standard gradient descent method can be obtained from (2) by choosing Ø = 1 12
For clarity of exposition, for a vector x E IR" we consider the function sgn(x)) 2/||a ||||||| for x E 12" {0} and 0
otherwise.
Example 1.5. Let x(x) Σ 1 v x becomes
Then, (2)
1.5. Assumptions on the reference function
Vif(x*)
k+1 2
= x
Our assumptions on the reference function & are formu- lated as follows.
V1/22 + (V.((*+))
and by choosing X x= E 1/2 form of Adagrad (Duchi et al., 2011) 1) without memory from (Défossez et al., 2022, Equation (3)) with B1 -2 = 0.
-12 for some E >> 0 we retrieve the
Assumption 1.1. The reference function &b : IR."" + RR is proper, Isc, strongly convex and even, i.e. xxx) = o(-x), with (00) = 0.
Example 1.6. Let ((x) E._ | In(11 [a.l). Then,
Assumption 1.1 is considered valid throughout the paper. Note that through the duality of strong convexity and Lips- chitz smoothness, it implies that o² E C² (I"). Moreover, from (Bauschke et al., 2017b, Proposition 11.7), {0} arg min & and thus o 2 O. Throughout the paper we also consider specifically the case where 6² E (RR),, for which we encode a sufficient condition in the following as- sumption, in light of (Rockafellar, 1977, p. 42).
the main iterate (2) takes the following form:
vef(a*)
k+1 = x 1/A
V [+*()"
and by choosing A = e for & > O, we retrieve the iterates
of Adam (Kingma & Ba, 2014, Algorithm 1) where both the exponential decay rates are set to 0, i.e. B1 = -33 = 0. Example 1.7. Let h(x) _ + and 6 = holl |l-
Assumption 1.2. 6 C² (int dom Φ) is essentially smooth.
Then, (2) becomes
It is important to note that through (Rockafellar, 1977, p. 42), under Assumptions 1.1 and 1.2, the Hessian matrix of 6² is positive-definite everywhere.
_+11 x min (>>/I/////>>>)ll>/>>>>>>>
Note that the gradient clipping method as presented in
(Zhang et al., 2020b. Equation (5)) is given by x =
Although we state both assumptions for the reference func- tion o we also use them throughout the paper by slight abuse of notation for the kernel function h which gener- ates ø.
x* - min mninnniefnn///// [|] choosing = Am and = 1/9 we can see that (2) en- compasses the gradient clipping method.
Therefore, by
When considering a kernel function h, in the anisotropic case, is straightforward that & inherits the properties of h and the preconditioner takes the form (x)( =
2. The extended anisotropic descent inequality
(h*' (az),..., h' (zx)). In the isotropic case, the differen- tiabiliit of o² depends the properties of h, show next.
In this section we extend the definition of anisotropic smoothness from (Laude & Patrinos, 2025) to our setting where & is potentially nonsmooth and provide sufficient conditions for smooth function ʃ to satisfy this gener- alized descent inequality. The proofs can be found in Ap- pendix B.
Lemma 1.3. Let h - IR satisfy Assumption 1.1. Then h" 2 0 is an even function and increasing on R., while hed (0) 0. Moreover, &- = h o || - is strongly convex,
6² h" o o|- and
We begin with the definition of our extension of anisotropic smoothness.
VΦl (v) = h²" ((el))))s)))))))
Vy E R.
4

---

Nonlinearly Preconditioned Gradient Methods
Definition 2.1 (L, La-anisotropic smoothness). Let E (AR)). We say that I is (T., I.) -anistroppicall smooth relative to & with constants L, L > 0 for all x, e IR"
sumption 1.2 then becomes VV
(V
(T) = 0, which does not normally imply the convex- ity of g. From the implicit function theorem, the above expression can be written as LL(V> (V-V((( VV((z)]- V f ł 0, which is the form that we consider through- out the paper. This condition becomes sufficient when S E (RR) are Legendre through (Laude & Patrinos, 2025, Proposition 4.1). Harnessing the connection with Φ- convexity, it is sufficient for general when e is a regular optimal transport cost in light of (Villani, 2008, Theorem 12.46). Nevertheless, the regularity of Φ is in general hard to verify, since its equivalent form requires the computa- tion of fourth-order derivatives (Villani, 2008, Definition 12.27), and quite restrictive, not holding for many inter- esting functions. We thus follow different strategy and study the minimization of g using tools from optimization and nonsmooth analysis.
f(x) s f()) + L [(L xx)xx - -))
(4)
-(L * (i- - 7)
where y = -
Note that inequality (4) is well-defined for & without full domain, but does not provide information for points x E IR such that L(x - y) & dom The intuition behind this extension of (Laude & Patrinos, 2025) is straightforward: allow for two different smoothness constants that play complementary role, while allowing dom & * R. leads to a more general descent inequality. It can be checked that for dom @ = R", Definition 2.1 reduces to (Laude & Patrinos, 2025, Definition 3.1) but w.r.t. Lt.
Definition 2.4. Let f E C²(RR). f satisfies the second- order characterization for (L, -a-aniootropi smoothness for all x E IR" and H (c (VVVVV"(( (L-\Vf()))
Our first result is an extension of the envelope representa- tion of f under anisotropic smoothness (Laude & Patrinos, 2025, Proposition 4.1) to our setting where é possibly does not have full domain.
Amax (HV) < T.T.
(5)
Proposition 2.2. Let f: RR" - R satisfy Definition 2.1. x Øz - y) + E(y) for some proper 5 Rm + R. Moreover, I = w/ + L- * 6²) for some Isc and convex v/ : :R" + R. implying that f
Then, fxx = inf yER" L(I-11
and lim|jall-oo ,T F. [z)] 00. In particular, (5) re- duces to Amax (V2 (L (L-1V)(<)))) [==)) < LL under
Assumption 1.2.
(I. + (²) is convex.
Note that, since o² is Lipschitz smooth and convex, from (Hiriart-Urruty et al., 1984, Example 2.2) we know that H is always a positive semi-definite matrix and thus from (Horn & Johnson, 2012, Theorem 1.3.22) with A H /2 and B = H we have that HV2 f(z) has real eigenvalues.
Note that Proposition 2.2 describes one direction of a con- jugate duality between anisotropic smoothness and Breg- man (relative) strong convexity (Lu et al., 2018, Definition 1.2). This result along with the envelope representation of f will be utilized later on in order to describe the conver- gence of the method in the convex setting.
The generalized Jacobian considered in the definition above can in fact be computed for many interesting refer- ence functions. As an example we study the inequality (5) for the reference function of Example 1.7 in Appendix D.2. The coereivity assumption on the forward operator in Def- inition 2.4 is very mild. For example consider a refer- ence function & with dom & C (O, 1) as the isotropic ones generated by the kernels in the four last rows of Ta- ble 1. Then, by standard convex conjugacy. ||VØ"|| < 1 and lim | (x)] = co always. We provide more results regarding the norm- norm-cceryivitt property of T in Appendix D.1. is important to note that when the ma- trix H 22 f(x) is symmetric, we can remove this extra con- dition on the forward operator,
In this paper we are mostly interested in cost functions that not covered by the classical L-smoothness assumption and thus study reference functions & that generate less restrictive descent inequality. Therefore, we next show that for strongly convex reference functions, the class of anisotropically smooth functions is at least as large as that of Lipschitz smooth ones.
Proposition 2.3. Let f IR" + K be Lipschitz smooth with modulo Lj and & satisfy Assumption 1.1 with strong con- vexity parameter p. Then f is (L5/ p, aniisorrropiil smooth relative to 6.
2.1. Second-order sufficient conditions
show in Appendix D.
Under Assumption 1.2 we obtain a condition that is more straightforward to check.
In contrast to Euclidean Bregman smoothness, anisotropic smoothness cannot in general be directly ob- tained via a second-order condition. This fact be- comes apparent by noting that (4) is equivalent to ã E fz)) The second- arg min, g(x) = L(L * ( - 9)
Lemma 2.5. Let & satisfy Assumption 1.2 and f C²(R"). Then, (5) holds and only for all x E R.
order necessary condition for the minimality of ā under As-
(2f(x) + &
(6)
5

---

Nonlinearly Preconditioned Gradient Methods
A sufficient condition for (6) is given by
Corollary 2.11. Let J E (R(RR) be (Lo, L1) (iogLLissmn -smooth.
Then, f is (ōI1, , Lo/ Ta Laaassoottrr smooth relative to <(x) =-|[]| - In(1 ||>]]) with d E (0,1).
Amax f()() < LLAmin 2Z (I-IV(())) (7)
Next, we show that under Definition 2.4 the forward op- erator is actually global homeomorphism (Facchinei & Pang. 2003, Definition 2.1.9), which we further utilize later on in proving our main result regarding the sufficiency of the sedond-order condition, Proposition 2.9.
2.2. How to compute the second-order condition
In this subsection demonstrate how the second-order condition of Definition 2.4 can be computed for the two different instances of our preconditioned scheme. We con- sider kernel functions that satisfy Assumptions 1.1 and 1.2 implying that the results of Lemma 1.3 hold, lifting thus the need to compute generalized Jacobians.
Proposition 2.6. Let E (²RR)) satisfy Definition 2.4. Then, _ _-1 is injective.
As a byproduct of our analysis, we obtain novel insights into the class of C² (IP)) (Lo. L.)-smooth functions.
Anisotropic reference functions. Thanks the sepa- rability of Φ, the condition is simple to compute, since is just diagonal matrix with ele-
Corollary 2.7. Let f E C² (R") be (Lo, ----moothh Then, T... = x Lo+L. [[ 5 = 1 and strongly monotone for < < 1.
(I(x) is monotone for
ments as given by
Ogi -L
Remark 2.8, Considering the forward operator as defined in Corollary 2.7, the main iteration (2) becomes:
Isotropic reference functions. As already mentioned in the introduction, in the isotropic case b = h the dif- ferentiability properties of ø² depend on those of h² In the setting considered in this subsection though, we have V (3) = (Ilvl )sgn(y) with o- E C²²(R²) and the Hessian is given by
5 x+1 x² to (a Vz(*
(8)
Note that in this case, (Gorbunov et al., 2024, Algorithm 1) can be viewed as (2) with a conservative choice of 8 S 0.57. This algorithm is in fact generated by h 11 with h(z)= ||x| In(1 - [x]).
Although Corollary 2.7 establishes new characterizations for (Tg. Iy)-smoothness the simplification used in the proof of the second-order condition is quite restrictive. We provide examples where we can obtain tighter constants utilizing directly Definition 2.4 in Appendix D.
( h- (Ibll
vy
M h- ([lvl)
+
I (T ("- yy
for y Th" (0) and [V2 (v)) 1/h""(]lvl) oth- erwise. We provide examples of this condition for kernel functions displayed in Table 1 in Appendix D.
Having obtained a sufficient condition for the injectivity of the forward operator Proposition 2.6, we now move on to providing sufficient conditions for to be (L, L)- anisotropically smooth.
3. Algorithmic analysis
In this section we study the convergence properties of the method in the nonconvex and convex setting. The follow- ing assumption is considered valid throughout the remain- der of the paper. The proofs of this section deferred to Appendix C.
Proposition 2.9. Let f C²2 and T-- be in- jective. Let moreover either (i) dom & be bounded or (ii) dom 6 = = and the following growth condition hold
Assumption 3.1. S E C²(RR) is (T, amiistrrpppl smooth relative to & and f = inf f > -cc
f(x) S L(r-1 (x))) 3
for all x E R and some r.3 E I such that 0 < < Then, is (L, anilotrprppll smooth relative Φ. Remark 2.10. The growth condition assumed in Proposi- tion 2.9 when dom & = _ is in fact not restrictive. Con- sider ø = cosh o|| || 1 and let ff be bounded above by some polynomial of the norm. Then, lim|| I(r-1 (x) - fx) = +0 for any fixed constants I,, r. implying that L(r ()() - f(x) is lower bounded.
3.1. Nonconvex setting
The convergence of the method to stationary points, in the composite case with an additional nonconvex, nonsmooth term, was established in (Laude Patrinos, 2025, Theo- rem 5.3) with fixed stepsize 7 S L-1 and in (Laude & Patrinos, 2025, Theorem 5.5) using an adaptive linesearch strategy for choosing 7, always under the assumption that à is of full domain. In the smooth setting studied in this pa- per, where & is also even, we can improve upon the afore- mentioned results and show that stepsizes up to 2L -1 can actually be used in the algorithm.
By combining Corollary 2.7 and Proposition 2.9 we can easily obtain the following result that describes the rela- tion between (L, --anisottroii smoothness and (Lo, L1)- smoothness.
6

---

Nonlinearly Preconditioned Gradient Methods
IC
10P
10P
11
10
11
10
10
116)
10
10
f(6
30-
10-14
10
10-14
100
Nambbr
iterations
iteeationn
Figure 2. Minimizing exp(I|=[|]- - ||||| 2| using (2). The figure on the left corresponds to di (2) cosh(]|==]) 1. the middle one to Φ2(x)
the one on the right (z()) = |||=||| In(1 [|=]]] choose values of set = I. and then compute == with L as in Appendix D.
Theorem 3.2. Let Assumption 3.1 hold and {NEN the sequence of iterates generated by (2) with y aL
IkEN be and convex. Then, the following inequality holds:
E 2), À T,-1 and let B have the following rate:
al. Then we
Vf(x))
Obtaining sublinear rates for the function values not a straightforward task. To the best our knowledge, there do not exist such guarantees for the full generality of the setting consider in this paper. Proposition 3.5 useful in that regard, since it allows for the suboptimality gap in the isotropic case, as we show next.
L(f(x)) (( < L3(K
min OSKSK
Using the result of Theorem 3.2 and specifying the ref- erence function o, can obtain convergence guarantees for the standard stationarity measure, V f> For Φ cosh oll - 1, this is captured in the following corollary.
show O(1/K) rate
Theorem 3.6. Let Assumption 3.1 hold, f be convex and & = holl-11 with satisfying Assumption 1.1. For {2* kkE% the sequence of ittrates generated by (2) with y = L- and
Corollary 3.3. Let Assumption 3.1 hold, ø = cosh o -1|
and (x* ) be the sequence of iterates generated by (2) with v = aL- a E (0, 2). X = - and 3 = - ox..
= L- the the following holds:
Then, the following holds for Po f(x²) f
l ---+1-x"111 -
x"11
(10)
2LLPo
LP.
min OSkCK
[V/(2*)
V B(K +1
+ B(K +1)
where x² E arg argminn S. i.e. fet JuEN, is Fejér monotone w.r. arg min f. Moreover the norm of the gradient of f monotonically decreases along the iterates of the algo- rithm:
3.2. Convex setting
[V S <[Vs(a")]l
In the convex setting, Proposition 2.2 establishes useful connection between anisotropic smoothness and the con- vexity f - (L i.c., the strong convexity of f relative to I. x0 with constant I.-1 in the Bregman sense. We utilize this connection in Proposition 3.5 and Theo- rem 3.6 in order to obtain standard sublinear convergence rates for the suboptimality gap in the isotropic case.
for all k No- If. in addition, h h²'x)// is decreasing function on R., have the following rate for the subop- timality gap:
f(x*)- - f L|V 1²1 +1)
(11)
h
Henceforth we make the following standard assumption, which we consider valid throughout the rest of the paper unless stated otherwise.
We remark that h²" h1'(x)/2 being a decreasing function on R4 is in fact mild assumption that holds for all the kernel functions presented in Table 1. The result above strength- ens the known results regarding the convergence of the method from (Maddison et al., 2021) and (Laude & Pa- trinos, 2025), while also answering the question posed in (Maddison et al., 2021, p. 17), regarding obtaining conver- gence guarantees for the suboptimality gap f(**)- We remark that although the obtained rate in (11) depends on
Assumption 3.4. arg min f +
Our first result is the following novel characterization re- garding the minimizers f.
Proposition 3.5. Let E R" and x* E arg migmin/ f. More- over, let f be (I,, T.) ai-aniootropccally smooth relative to o
7

---

Nonlinearly Preconditioned Gradient Methods
10F
0g
19P
6
10P
Cloppng
108
(MGD
(AGD
10-1
Cliplnx
10
Clipping
[
10
10-4
10-
10'1
20"
10-12
10-12
100
900
500
Number
Namber iteeationn
Figure 3. Nonconvex phase retrieval. di corresponds the isotropic reference function and d2 to the anisotropic one, both of which are generated by cosh(-) - 1. two figures on the compare the algorithms for one instance of the problem. The figure on right displays the results of gradient clipping and the isotropic version of (2) averaged across 100 random instances.
10A
10-1
Thining boe
Thining los
10-2
10-1
Thiiing
201
10-4
10-3
10-4
0.05,
250.0
10-1
7.
0.5.
90.0
10-4
0- 7.0
0.88
10
02, 10.0
10
2.0
05
10
100
1.0
Number
Number iteeationu
Number
Figure 4. Simple NN training. (left) results for (2) with (x:) cosh(]|=]]) 1; (middle) Φ2(x) -I|ar|l In(1 gradient clipping method as presented Example 1.7.
|| (right)
the initial norm of the gradient, one can use the techniques from (Vankov et al., 2024) or (Gorbunov et al., 2024) to achieve a better complexity when specifying the reference function Nevertheless, such an endeavor beyond the scope of this paper.
Theorem 3.7. Let Assumption 3.1 hold, f be convex and
(a*) keN, be the sequence of iterates generated by (2) with 7 = L- == L-1 and assume that dom & = IR,, More- over, let be 2-subhomogeneous i.e. such that d(0x) S @ (x) for all [0, 1). Then, for all K 2
Although Theorem 3.6 provides sublinear rate for the isotropic case, obtaining such guarantees for anisotropic reference functions is not straightforward: key in the proof of Theorem 3.6 is the fact that (I and therefore the con- vex gradient inequality for ff can directly be utilized to show the Fejér monotonocity of (=*))eN Nevertheless, able to prove the sublinear convergence rate for the suboptimality gap for subhomogeneous (Azé & Penot, 1995, p. 708) reference functions using different tech- nique based on generalized conjugacy. More precisely, we utilize the characterization of anisotropically smooth func- tions as (generalized) envelopes and interpret the algorithm as nonlinear proximal point method, generalizing thus the duality between gradient descent and proximal point in the Euclidean case (Laude, 2021, Theorem 3.8). Then, we combine the subhomogeneity of Φ with the proof tech- nique of (Doikov& & Nesterov, 2020, Theorem 1) for inexact tensor methods and obtain the claimed rate. This result is captured the following theorem.
4Do
f(x*) 5
(12)
K
where Do = sup([((L.)) * )) - x²) f(x) s [(x9)} for x² E arg
=
h" ""(([] (**)((( ([l))sgn(V[((r
In general the set Do might be unbounded, except if has bounded level-sets, which is the case if arg min f is bounded in light of (Bauschke et al., 2017b, Proposition 11.13). In theory, this dependence on the initial level-set can be eliminated by considering an averaging procedure akin to (Doikov & Nesterov, 2020, Algorithm 3), thus lead- ing to a convergence rate terms of some function of the initial distance to the solution. Nevertheless, such methods tend to underperform in practice compared to their more straightforward counterparts.
Examples of 2-subhomogeneous reference functions are those generated by cosh 11, as described in the following Lemma.
Lemma 3.8. The function h(x)) = cosh(x) 2-
8

---

Nonlinearly Preconditioned Gradient Methods
among all algorithms. In this experiment the two versions of the algorithm proposed in this paper outperform the rest (13) of the methods. subhomogeneous, i.e., the following inequality holds:
h(0z) S h((2),
for all 8 E [0. and R.
Moreover, we test the clipping and the isotropic algorithm over 100 random instances of the problem and plot the mean along with error bars representing one standard devi- ation on logarithmic scale. can be seen that the isotropic algorithm outperforms the clipping method across the tests for this particular tuning. Note that the tuning for both of the methods is quite robust.
4. Experiments
In this section we present some simple experiments that display the behavior of the proposed method on problems beyond traditional Lipschitzian assumptions. The code for reproducing the experiments is publicly available'.
4.3. Neural network training
4.1. Norm to power
In this experiment layer fully connected network with layer dimensions [28 x 28, 128, 64, 32, 32, 10] and ReLU activation functions on a subset of the MNIST dataset (Deng, 2012), using the cross-entropy loss. We consider a subset (m = 600) of the dataset order to efficiently use full gradient updates.
consider training simple four-
For the first part of our experiments we consider the toy example of minimizing f(x) f||==|| with x E R500 using different preconditioning schemes, We consider the reference functions c)sl( 1, exp([|=[I)- - |||||
and || In(1 [|= and remind that the algorithm generated by the latter function is tighter version of the algorithm proposed in (Gorbunov et al., 2024). In this ex- periment, we keep L fixed, compute L. according to the rules established in Appendix D and apply algorithm (2) with 7 L and X = -- The results are presented in Figure 2. For different values of L and L. there seems to be a trade-off between faster convergence medium accuracy and slower convergence to very good accuracy for all three preconditioned methods.
We compare the methods generated by (1)))
cosh([|==]]) 1, (2) -|a=||| - IIn[ ||=|]]) and the gra- dient clipping method (Zhang et al., 2020b), that can also be considered as an instance of (2) through Example 1.7, for various choices of the stepsizes and the clipping param- eters. The results are presented Figure 4. It can be seen that different combinations of y and À lead to different be- haviors for the compared methods.
4.2. Nonconvex phase retrieval
5. Conclusion and Future Work
In this experiment we consider the nonconvex phase re- trieval problem
In this paper we introduced and studied a new generalized smoothness inequality that is less restrictive than Lipschitz smoothness. We provided sufficient first- and second-order conditions through an unconventional technique that also leads to novel insights into the class of (Top, I.) )smooth functions. We moreover analyzed nonlinearly precon- ditioned gradient scheme that is tailored to the proposed smoothness condition and studied its convergence prop- erties both in the nonconvex and convex setting. This framework encapsulates a plethora of well-known meth- ods, while it also generates new algorithms.
min f(x) ZER
2m Σ (y - (a. 2)
with y E R, a, E R". The data is generated as in (Chen et al., 2023): n 100, m 3000 and a, a ~ (O, 0.5), Jo ~ A5. 0.5) generated element-wise with 2 denoting the true underlying object. The measurements are gener- ated as y = (a 2)² + n, with n, ~ (N,
We compare the algorithm (2) with the isotropic and anisotropic reference functions generated by cosh 11, de- noted respectively by Φ1 (x) cosh([|=]]) and (x)) = D cosh((:)) - against vanilla gradient descent, gradi- ent clipping (Zhang et al., 2020b) and (Chen et al.. 2023, Algorithm 1) with the tuning described in (Chen et al., 2023, Section 7). For the isotropic case of (2) we take 7 5/3 and x= 1/100, while for the anisotropic one
Our work paves the way for better understanding clip- ping and signed gradient methods from a majorization- minimization perspective. Possible interesting future work includes integrating momentum both in the convex and nonconvex regime and studying the stochastic setup. An- other interesting research direction is extending our conver- gence results for the suboptimality gap from the smooth to the additive nonsmooth setting where the nonsmooth term is handled similarly to (Laude & Patrinos, 2025). We be- lieve that this extension is not straightforward and requires additional effort compared to the standard Euclidean setup of gradient descent.
7 = 1/5 and = 1/14. The results are presented in Fig-
ure 3. We use as f the minimum value of the cost function
httpp::/ //tp:::://itii http::////tthhuu.com//////// com/JanO/
nonlinearl ieiiinnrryyaaae pryc--prrddiiio t oned- gradddg-rddntt...

---

Nonlinearly Preconditioned Gradient Methods
Acknowledgements
Chen, X., Wu, S. Z., and Hong. M. Understanding gra- dient clipping in private SGD: A geometric perspective. Advances in Neural Information Processing Systems, 33: 13773-13782, 2020.
Work supported by: the Research Foundation Flan- ders (FWO) research projects G081222N, G033822N, GOA0920N; Research Council KUL grant C14/24/103.
Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized- smooth nonconvex optimization is efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396-5427. PMLR, 2023.
The authors thank Thomas Moellenhoff for helpful conver- sations.
Impact statement
Clarke, F. H. Optimization and nonsmooth analysis. SIAM, 1990.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Défossez, A., Bottou, L.,, Bach, F., and Usunier, N. sim- ple convergence proof of Adam and Adagrad. Transac- tions Machine Learning Research, 2022.
References
Deng, The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):1411142, 2012.
Ahookhosh, M., Themelis, A., and Patrinos, P. A Breg- man forward-backwer linesearch algorithm for noncon- vex composite optimization: superlinear convergence to nonisolated local minima. SIAM Journal on Optimiza- tion, (1(11:663336511 685, 2021.
Doikov, N. and Nesterov, Y. E. Inexact tensor methods with dynamic accuracies. JCML, pp. 2577-2586, 2020.
Dontchev, L. and Rockafellar, R. T. Implicit functions
Azé, D. and Penot, J.-P. Uniformly convex and uniformly smooth convex functions. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 4, pp. 705-730, 1995.
and solution mappings, volume 543. Springer, 2009.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Bauschke, H. H., Bolte, J., and Teboulle, M. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Op- erations Research, 42(2):330-348, 2017a.
Facchinei, F. and Pang, J.-S. Finite-dimensional vari- ational inequalities and complementarity problems. Springer, 2003.
Faw, M., Rout, L., Caramanis, C., and Shakkottai, S. Be- yond uniform smoothness: A stopped analysis of adap- tive SGD. In The Thirty Sixth Annual Conference on Learning Theory, pp. 89-160. PMLR, 2023.
Bauschke, H. H., Combettes, P. L., and Bauschke. Correc- lion to: convex analysis and monotone operator theory in Hilbert spaces, Springer, 2017b.
Bernstein, J. Wang, Y.-.., Azizzadenesheli, K., and Anandkumar, A. signSGD: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pp. 560-569. PMLR, 2018.
Figalli, A., Kim, Y.-.,, and McCann, R. J. When is mul- tidimensional screening convex program? Journal of Economic Theory, 146(2):4544478, 2011.
Gorbunov, E., Danilova, M., and Gasnikov, A. Stochas- tic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Pro- cessing Systems, 33: 15053, 2020.
Bolte. J., Sabach, S., Teboulle, M., and Vaisbourd, Y. First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse prob- lems. SIAM Journal on Optimization, 21132,11,- 2018.
Gorbunov, E., Tupitsa, N., Choudhury. S., Aliev, A., Richtárik, P., Horváth, S., and Takáč, M. Meth- ods for convex (Lo, L -smoohh optimization: Clip- ping, acceleration, and adaptivity. arXiv preprint arXiv:2409. 14989, 2024.
Bonet, C., Uscidda, T., David, A., Frain-Frankowski, P.-C., and Korba, A. Mirror and preconditioned gra- dient descent in Wasserstein space. arXiv preprint arXiv:2406.0888 08938, 2024.
Hiriart- J.-B., Strodiot, J.-J,, and Nguyen, V. H. Generalized hessian matrix and second-order optimality conditions for problems with c 1, 1 data. Applied math- ematics and optimization, (1(1):43-56 1984.
Bredies, K. A forward backward splitting algorithm for the minimization of non-smooth convex functionals in Banach space. Inverse Problems, 25(1):015055, 2008.
10

---

Nonlinearly Preconditioned Gradient Methods
Horn, R. A. and Johnson, C. Matrix analysis. Cam- bridge university press, 2012.
Rockafellar, R. T. Higher derivatives of conjugate convex
functions. Int. J. Applied Analysis, (1):41-43, 1977.
Kim, J., Park, C., Ozdaglar, A., Diakonikolas, J., and Ryu, E. K. Mirror duality in convex optimization. arXiv preprint arXiv:2311.1722
Rockafellar, R. Convex analysis, volume 28. Princcton
university press, 1997.
2023.
Rockafellar, R. T. and Wets, R. J. Variational Analysis. Springer, New York, 1998.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 412.6982,, 2014.
Strichartz, R. S. The way of analysis. Jones & Bartlett Learning, 2000.
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisit- ing gradient clipping: Stochastic bias and tight conver- gence guarantees. In International Conference on Ma- chine Learning, pp. 17343-17363. PMLR, 2023.
Themelis, A., Ahookhosh, M., and Patrinos, P. On the Ac- celeration of Forward Backkaard Splitring via an Inex- act Newton Method, pp. 363 412. Springer International Publishing, Cham, 2019.
Kunstner, F., Yadav, R., Milligan, A., Schmidt, M., and Bietti, A. Hcavy-tailed class imbalance and why Adam outperforms gradient descent on language models. arXiv preprint ArXiv:2402. 19449, 2024.
Vankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. U. Optimizing (Lo, L1)-smotttott functions by gradient methods. arXiv preprint arXiv:2410. 10800, 2024.
Laude, E. Lower envelopes and lifting for structured non- convex optimization. PhD thesis, Technical University of Munich, 2021.
Villani, C. Optimal Transport: Old and New. Springer, 2008.
Laude, E. and Patrinos, Anisotropic proximal point al- gorithm. arXiv preprint arXiv:2312.09834, 2023.
Wang, B., Zhang, H., Ma, Z. and Chen, W. Convergence of Adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Anmual Con- ference on Learning Theory, pp. 161-190. PMLR, 2023.
Laude, E. and Patrinos, P. Anisotropic proximal gradient. Mathematical Programming, pp. 1-45, 2025.
Laude, E., Themelis, A., and Patrinos, P. Dualities for non-
Zhang, B., Jin, J., Fang, C., and Wang, L. Improved anal- ysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 15511-15521, 2020a.
Euclidean smoothness and strong convexity under the light of generalized conjugacy. SIAM Journal on Op- timization, 3314):2721-2749, 2023.
Léger, F. and Mubin-Frankowske P.-. Gradient descent with a general cost. arXiv preprint arXiv:230S.04917, 2023.
Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradi- ent clipping accelerates training: A theoretical justifica- tion for adaptivity. International Conference on Learn- ing Representations, 2020b.
Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, Convex and non-convex optimization under generalized smoothness, Advances in Neural Information Processing Systems, 36, 2024.
Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good for attention models? Advances in Newral Information Processing Systems, 33:15383-15393, 2020c.
Lu, H., Freund, R. M., and Nesterov, Y. Relatively smooth convex optimization by first-order methods, and appli- cations. SIAM Journal on Optimization, 2831)3333-354 2018.
Maddison, C. J., Paulin, D., Teh, Y. W., and Doucet, A.
Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 3101):991-1016, 2021.
Nesterov, Y. Universal gradient methods for convex op- timization problems. Mathematical Programming, 152 (1):381-400) 2015.
Nesterov, and Polyak, B. T. Cubic regularization of Newton method and its global performance. Mathemat- ical programming. 10711)177-2 2006.

---

Nonlinearly Preconditioned Gradient Methods
A. Missing proofs of Section
A.1. Proof of Lemma 1.3
Proof. To begin with, since is proper, Isc and convex, = hn" In light of (Rockafellar & Wets, 1998, Theorem 11.8), we have that min h (0) = -h(D) 0, implying that h" 2 Moreover, from the same theorem, arg min h (0)) further implying that h" (0)
and h (0) O. Since is even, we have from (Bauschke al., which means that h" is also even. Therefore, through (Bauschke
2017b, Example 13.8) that h (h -1) h"
et al., 2017b, Proposition 11.7) we get that h" is increasing on I....
Now, note that the function = h - 1 is proper, Isc and convex where μ is the strong convexity parameter of h. Moreover, is even as the difference two even functions. Therefore, from (Bauschke et al., 2017b, Proposition 11.7) an increasing function on R+ and thus g o || is a convex function on IR", This implies that [[[[==]]) - _ ||>||| convex is strongly convex with the same strong convexity parameter.
and thus that ø = h
Again from (Bauschke al., 2017b, Example 13.8), we have that Ø² h- || - and to get the gradient of ø* we can then utilize (Bauschke et al., 2017b, Corollary 16.72) to obtain V (v) = h² (1lv ([lv [sgg()))
Regarding the twice continuous differentiability of Φ", it follows from (Rockafellar, 1977, 42) that h-" c²²(R") and the claimed result follows from (Strichartz, 2000, Exercise 10.2.20), since h" is even.
A.2. Proof of Example 1.7
Proof. is straightforward that h(x)= = + is a proper, Isc, strongly convex and even function with h(0) = 0. Then, from (Rockafellar & Wets, 1998, Theorem 11.23) we have that h- (v) inf 1 (I) + 1 (y x)², where 1 is the support function of [] 1] and in light of (Rockafellar & Wets, 1998, Exercise 11.27), (v) = 1 (v). where I (1) = min(1, max( max(-1, (-1,g) is the projection on the closed convex set [-1, 1]. Using Lemma 1.3 we thus obtain
To"(u) (v) = min(1, [Ivll)sgg( and the algorithm becomes:
x+t x² min (1/IV[(""")
by pulling the norm inside the min.
B. Missing proofs of Section
B.1. Proof of Proposition 2.2
Proof. Consider the following quantities, which are generalized conjugates defined in (Rockafellar & Wets, 1998, Chapter 11L):
(-f)*(v)= = sup - -[( * (x - y) f(x) = - inf T( * 2)(x y) f(x), =ER"
xER"
(-f)
* +) -L(L-1 v) (w))
sup
yER"
Let 7 E RR. Since f is (L, L)LL-))-nnnoo anisotroppilll smooth, we have that
T E arg min I(I.- * Φ)(x 7) f(x),
=ER=
where ÿ = ==T--1(-11() = -- Vo-
(L- -- and thus
= ( +)+ ((x) E RR
(14)
which implies that (- is proper. Since T was arbitrary, this holds for any x E R" and y = Ty.11, (x). By the definition of (-f) for such pairs x and y we have that
ah
+ - y).
Substituting (14) in the incquality above, we obtain (-f) 0 ff(x) s (z)) Moreover, by the definition of (- we have that for any 2; H E R
$) - 9)
12

---

Nonlinearly Preconditioned Gradient Methods
Moving (y) to the other side and taking the supremum with respect to y we obtain -f(x) 2 (-f))t(x)) combined with the previous result means that f((x) (-f) 4 (+). Therefore, have
which
-f(x) = (-f) sup - LL o) y) - (-f)
yER*
inf L(L * x))( - 1) + (- yER"
which is the claimed result for 5 = (-f)a²
We now show the convexity of f 1-1
(I+ * x²). In light (Rockafellar & Wets, 1998, Theorem 11.23) and (Bauschke
al., 2017b, Proposition 13.23) we have
/
( inf TL (.(. - y) + (-1) = + (T(L.- x))) = + [Tx yER"
and as such the result follows for vb = e* which is Ise and convex, using moreover the fact that dom Ø = I since ø is strongly convex.
B.2. Proof of Proposition 2.3
Proof. Consider any points x; I E R If ((===+1--V6 & dom & then the bound holds trivially. Otherwise, from the Euclidean descent lemma for we have:
f(x) S 1 x||2.
Moreover, from the strong convexity of á between points
(VI())) and (V)((())))
1 + + a - -V = -000--0-----------0000001111111
2 [
aL? 1 x|2
+ (V
al 7) 2 77
where we have used the fact that rge V C dom ø along with ( E (V Therefore, the claimed result follows.
B.3. Proof of Lemma 2.5
Proof. Let Q = f²)(x) and note that H = V20' (Z > 0 from (Rockafellar, 1977, 42). Then
< LLH - 11 LLI + (1 222 < LL + Amax(11)) < LL,
where the first equivalence follows by (Horn Johnson, 2012, Theorem 7.7.2c) with 5 = H1/2 The last equivalence follows by noting that the (generally nonsymmetric) matrix HQ is similar to the symmetric matrix H!2QH' by using (Horn Johnson, 2012, Theorem 1.3.22) with A = H1/2Q and B H1/2 and noting that 11/2 is nonsingular. The sufficient condition follows from Weyl's inequality (Horn & Johnson, 2012, Theorem 4.3.1).
B.4. Proof of Proposition 2.6
Proof. We will prove that Tr, 1,6 1 = id id-L- (i-'vf) is global homeomorphism from 1 (Facchinei & Pang, 2003, Theorem 2.1.10).
1
using
Note that from Definition 2.4, lim I|T--1.--1x) = co, i.e. Tz-1 is norm-coercive, we only need to show that it is everywhere local homeomorphism. The mapping Ti.-1, is locally Lipschitz, since Vø* is globally Lipschitz and E C² (RR) and thus the generalized Jacobian is well-defined. Now, we have that (c = de (V o T.-vvf((x)) and light of (Clarke, 1990, p. 75),
-
Vc(V85 o (Vv)))(() S (
13

---

Nonlinearly Preconditioned Gradient Methods
for any e E I In order to show that - is everywhee local homeomorphism are going to use Clarke's inverse function theorem presented in (Dontchev & Rockafellar, 2009, Theorem 4D.4).. Consider thus any point R² and the mapping (a(z)= == T (Ø) + A(x T), where A E -c Now, from the reasoning above we have that
A(x -) 3) E - LL (V0
8)}
From Definition 2.4 have that for all H (V Vf(x)) -I f()) 0, implying that GA is an invertible linear mapping for any A E OcT₁ L. 1 (z). Therefore, from (Dontchev & Rockafellar, 2009, Theorem 4D.4), there exists a Lipschitz continuous mapping _ _-- such that - hoods U of E\t and V of T- (T). Since, moreover T I,1 is Lipschitz continuous, it is local homeomorphism at I in the sense of (Facchinei & Pang, 2003, Definition 2.1.9). Since this holds for any ह E R", it is everywhere local homeomorphism. This concludes our proof by using (Facchinei Pang, 2003, Theorem 2.1.10).
z for some neighbor-
B.5. Proof of Corollary 2.7
Consider ((x:) = ||r||| 1 1n(1 - || [)) this case, M(x) -|x|| (iel-In(1 (1/)) and thus from Lemma 1.3, Vg) 1- | We thus have
V = 1 11yll
I+
1
yy
(1 I|
1 +
1l
||y/|2
|1
2/1
I
1+ 1
(1 11v/l) |/
The term multiplying पमा since 1
is negative and as such Amax 2 (+(bt()) (v)) S I+Ml Moreover, (2)" is positive-defintte
|yll which then implies | 0 (y)ll S I+18 Therefore. I+lly]
Lo Lil1e|l"
Iv'' Wlll
L lvll
Lo
by choosing L = Lo/Li L1. By (Lo, smoothhnsss moreover have [(=)] Lo + [[]]((()) and thus
IV [
s Lo.
Choosing now L= L1 we further have
(E LL.
(15)
Now take any points x, E R and note that from the Cauchy Cauchy-Schwarz inequality:
(L
V -
- (16)
By the fundamental theorem of calculus for the mapping VΦ" (.-1/))
- (---)(--V/(++----))))))---311113 hrgp://www...aooa.rr....aaaannnn -x)) z)dt
and as such
| 42 + ((= ((x z)) z)dl
< 1-15 // (( f(-- =)))
4|| =||
14

---

Nonlinearly Preconditioned Gradient Methods
where the second inequality follows by (15). Putting this result back into (16), multiplying with -y 0 and adding ||0 2| to both sides obtain:
- - - 110001117700000000000000-0------
implying that
(T - T 5L 11 1111111))))) (T), x) 2 (1 - -)]| ==
since 7 = 6L-1
B.6. Proof of Proposition 2.9
Proof. Note that (4) is equivalent to I E arg min g(x) = L(L * () 5) f(x) for all F E g", where
y = V (f)).. In light of the modern version of Fermat's theorem (Rockafellar & Wets, 1998, Theorem 10.1), for E to be local minimizer of g. the following inclusion should hold: 0 E 0g(E). Through (Rockafellar & Wets, 1998, Exercise 10) this implies that
Vf(e) E a(L(L * 6)) - 7) Lao(L(E- -))
or that L(i - Vo' and since -- is injective, the only possible minimizer of g is T.
- ã (--
V. This means that T7.-1,E-1185) TT.-11,.-11())
Therefore, if we show that g has minimizer we are done.
Case dom & is bounded. light of (Rockafellar Wets, 1998, p. 91), g is coercive function and as is also proper and Isc, it attains its minimum.
Case 2: dom o R². By the assumption of the proposition have that
g(x) 2 L(L-1 * (x - ū) - -(r-- * (x)) + B.
(17)
Let y be the strong convexity parameter of then we have the following for all a E (0, 1):
L(r-1 * (x) = Lr- 6(xx)
-rr frr-6((r(z -ÿ) + rī)
-o ra I-
+ r(1 -a) -
1
a
< -r- aΦ (" (x--)) Lr alΦ (1 (1-av)
Lr 2r-1a(11 (0(11aa) a) (x (7)
r
13
2
where the inequality follows by the strong convexity inequality for between points [x 77 and - y. Choosing now = r----1 <1 1 we obtain:
- * (x) S I(I-1 * () - 7) + (1-1)))
4
2 L(1 - rL-1) 11( - r)) Lyl?
[[(I--
Substituting this inequality in (17) we get
/ I 2 L(1 - rL-1 [|(L r)x - Loll + 3 ((x).
g(x) 2 (1-
Note now that s is proper, Isc and strongly convex function and as such it has bounded level-sets. Due to the inequality, the level-sets of are contained in those of su and thus also has bounded level-sets. Since moreover is Isc, it attains its minimum.
We thus have showed that in both of the above cases, y has a minimizer and the proof complete.
15

---

Nonlinearly Preconditioned Gradient Methods
C. Missing proofs of Section 3
C.1. Proof of Theorem 3.2
Proof. From incquality (4) between points x=+1 and x²t we have:
Using the fact that @ is even, we have (1tp://0000000111100000030000310 and since & is convex,
we have
Φ(Ox) <( - 0)0 8z) - (1- - 0))(0) + fΦ(2) = 0x(x),
for any 0 E [0, 1]. Note now that |1 - al < and the previous inequality becomes:
f( 1 f(x*) - - (1-11-a))2=""00V""""111110
(18)
Therefore, summing up the above inequality we obtain
L (
L LB
(T.
(1(0))- -)),
L3
which leads to
L
(K + 1) min
o VV
S LB
(f(x²) - fr))
(19)
OSkER
Dividing now by K + we obtain the claimed rate.
C.2. Proof of Corollary 3.3
Proof. In light of Theorem 3.2, the following holds:
I(s(2)) - 8*)
min &f V (I= S OSkšK
(20)
LB(K +1)
Now, using the fact that cosh cash(arcin)((z)) = v1 x we have:
cosh (1 [aresin(())-V///(()))) V (5(OT))) -1
[V/((*)]
cosh (ashcssrsnnh
The function VI+ - is increasing for æ 2 0 and as such k* arg minogess (o ( is equivalent to 1s E arg min [1² Therefore, by taking I to the other side in (20) and taking the square, obtain:
1 + T, 2 1P (L(F(a))-1)) (B(KK+1) +
2L(f(2)) -f +1,
L3(K 18(K+1)
or that
[(F(E9)-
2LL()(49) - +
|Vf(<* )
3(K +1)
3(K + 1)
Taking the square root and using the fact that +a+ Vo + /B we obtain the claimed result.
16

---

Nonlinearly Preconditioned Gradient Methods
C.3. Proof of Proposition 3.5
Proof. To begin with, with similar arguments in the proof of Lemma 1.3 we have that o" (0) 0 and (Φ- 0.
In light of Proposition 2.2, -----'(22 Φ²) is convex function. By definition V f(x) dom åf C dom f for all
R" and as such we can consider the convex subgradient inequality for f LL Ø*) between points f((z) and
V fx=" and obtain:
+ (x", V l (z)),
(21)
0, (0) 0 and ( f()), since f is convex. Taking where we have used the fact that ff(=*) = 0, (0)
once again the convex gradient inequality between points Vz(=*) and (z(x), we now have:
f (Vf((=))) ((V(())) L (z))) (z - Vo の (L Vf(z)) fxx)),
(22)
with the same reasoning as before. Summing now (21) and (22) and rearranging we obtain the claimed result.
C.4. Proof of Theorem 3.6
Proof. We begin as in the classical analysis of gradient descent by using the Pythagorean theorem:
| - 20 1 x (o -*) -
x²)
(23)
We further have:
- ---' - x²) - h11 (01 (I-'V)(at) x²))
S --1,-2 11"h (1| (|1-~~//(<")) (T- Vo (o
= (
(24)
where in the inequality we used Proposition 3.5 and in the equalities the fact that -6"(L-'VfF ((-(L-'V((tt)
| ""(L= ((- from Lemma 1.3. In the inequality, we also used the fact that (1) 2 0 for 2 0.
Indeed, by convexity, we have that:
(0) 2 (111))-"00 + (()) 2 -1)))--000
implying that h (t) 2 0 for all t 2 0. Plugging now (24) into (23), we obtain
(25) which shows the Fejér monotonicity of (-** JKEN w.r.t. x² E arg min f. Since (Th)* = [ h² and h is an even function, we have that (Lo)* = L (h- - || II). In light of Proposition 2.2, we have that f f- L - is a convex function.
|| - 112 < || x 1| (L
x²) S 1| 1
Now, for any 2, T E IR",, from the convex subgradient inequality for this function, between points f E dom 0 and v f*)) dom 05* we have:
-
- (a - ( -(o) Vf()))
where we have moreover used the fact that 7 (f) Therefore,
D(Eo))(V((x), Vf(T)) = (VV[])))-(<(VVVVVVVVVVVVVVVV)>>- (V([)) V/(=) v/(})
= (TD((T,
where Dy denotes the Bregman divergence associated with g and the equality follows by the definition of the convex conjugate.
Thus, (Maddison al., 2021, Assumption 3.1) holds for i = (LØ)*. Therefore, substituting from (Maddison al., 2021, Equation (41)), we obtain (To))* (V](+++)) < (I.))* (V (V]()))) for all & E No and since hi" is an increasing function on R4 from Lemma 1.3,
Lh
< T. TT
[+ S |V
(26)
17

---

Nonlinearly Preconditioned Gradient Methods
and thus we proved that the norm of the gradient of monotonically decreases along the iterates. We now return to the Fejér-type inequality (25):
| x²112 S 1|x=* x²112 =0112-1,-11 -.-1
I V[(a")] (I. (T- (aa") xx²).
Using the convex gradient inequality for f we further have:
| ++ - x=' < 1| - 14' (
||-\(( (J(z*)- -
Summing up now the inequality above we obtain:
(f(z)) -) S $11=0 =x
|
k=0
which after utilizing the fact that
h-' h0' [V((+*))
1"(11--15("")
(L- s ||~")) vk V
Ak No.
|T- ||-1||[(>)|
since (xxx)) is decreasing on R4, implies that
(K + 1)L-1 1
min USKSK
(f(**) f*) S 1|x 1|?
|V/(2))]
This is the claimed result, since the function values decrease along the iterates of the algorithm from (18).
C.5. Proof of Theorem 3.7
In light of Proposition 2.2. f inf VER" L(L-' this setting and dom IR"" we can take & to be convex and Ise from (Laude & Patrinos, 2025, Proposition 4.1). In order to prove our result, we will resort nonlinear proximal point interpretation of (2) with strongly convex prox-kernel. We therefore consider the following iteration:
()) y) + E(y) for some & R" + F. Since f is moreover convex in
arg min L(L ()(x v) + E(v)- EER"
(27)
From (Laude & Patrinos, 2025, Proposition 3.9 (ii), since dom Φ = R", we have that
vf(x*) V inf İ(L * (x* y) + {(v) = LVo(L(E* - x*t1)),
yER"
which directly implies that =+1 x² - I
V Vs(+)) and the claimed equivalence between the schemes is
established. Using this result we can now prove certain three-point-like property for the iterates generated by (2).
Lemma C.1. Let JeEN be the sequence of iterates generated from (27). Then, the following inequality holds for all
x E I
E(I*+1) I E(x) - -I(L_' (a* 2111) (L- 0x) - x))
(28)
Proof. By the optimality conditions for (27), we have that
0 -ivoL((( - x x221 - + 0E(x
Now, by the convex subgradient inequality for &, with wht E ag(xt+l), we have that
E(x) {(x*+1) (11 x - x*t1
E(xk+1)+ + L(VØ(L(Z* x
)), - xh1l)
E(aktl) + L. (Vo(T<t* - ,b11)), I(x -x x² + I(xn - bltl))
2 ((chtt)) - (0)= - - (L- (at -x)]
18

---

Nonlinearly Preconditioned Gradient Methods
where the first equality follows by the inclusion above and the second by simple algebraic manipulations. The final inequality follows by using the convex gradient inequality for between points M( x) and L(x rl11). Therefore, the claimed result follows by rearranging.
Now, we move on to the proof of our main theorem. It is inspired by the proof of (Doikov & Nesterov, 2020), where we have also utilized the fact that ø is 2-subhomogeneous.
Proof. As established above, we consider the sequence of iterates generated by (27). In light of Lemma C.I and since 6 2 we have for any z E R":
(( S ((x) + L(L * (I* x).
(29)
Now consider an arbitrary increasing sequence {AA IREN with A& > 0 and Ao O. We denote by ak+1 Ak+1 A and by taking == "x.1 4 Agx" we have x² x 1ell (at x²). Plugging this in (29) and using the convexity of & we obtain:
Aet1
{(* S (1.t((x)) + Ar ((xh) L(L * (11l) (x* x²)).
Let 0g == 4x-1 S. 1. By the subhomogeneity of ø we have that Ax+1
{(xht1)= < ge+1 Ant1
(xtl((x") {(x*) +
As {(x + OGL(L-1 x0) -2))
Asti
Multiplying both sides with A&+1 we get since a+++ Ak+1 A&
of+1 i. * (0) - xx)). Azt1
As+1 (E(x - [(x*)) S AE(E(=")) - [(x*)) +
Summing the inequality from k = to k = K - 1 we obtain since Ao 0:
K-1
4uي Axi1
L(L x)(x -x*) x*).
(30)
Choosing = x²t in (29) we have
((x S ((
and thus {(x*) E(x')= & O, which implies that
f(**) S {(**) S E(x!) S E(x²) + L(L * )) - ==x==((('))
The first inequality in the above display follows by the envelope representation of f. which implies that f(x) < E(x) for all E R". The equality also follows from the envelope representation, since
f(x") inf L(L * 0)(" y) + E(v) L(L - + E(x²)
yER"
from (27). Thus we can further bound (30):
K-1
Ak (x(E(=K)- -((x))) S Do
Σ
2++
Aki1
k=0
We choose A& 2.2 and by using the fact that KK af < 4K (Doikov & Nesterov, 2020, Equation (35)):
Av
Ax (E(x [(xx)) < 4D,
Dividing by Ax we obtain:
4Do
E(x*) [(x*) <
K
Noting that f(**) < E)x from the envelope representation of f, and E(x*) = f(x*) we obtain the desired result.
19

---

Nonlinearly Preconditioned Gradient Methods
C.6. Proof of Lemma 3.8
Proof. Fix x R \ {0} and consider the function g(0) cosh(Ox)) - (ccohh(2) 1). If this function is at most nonpositive for 8 E [0, 1), then the claim is proven. Note that g(0) 0 and g(1) 0. Moreover, g' (0) z sinh(0z) 20(cosh(z) - and thus g' (0) O. Now, g0) x² cosh - 2 cosh(ar) + and thus g0) x² +2 2 cosh(4) < 0, which further implies that 0 is a local maximum. Therefore, there exists a A E (0. 1] such that g(t) < g(0) = 0 for all
0 E [0, 0). which implies that if we prove that g(0) o 0 for all 0 E (0, we are done.
Let us assume now that there exists a 0 E (0, 1) such that g(0)) = 0. Then, by Rolle's theorem, there must exist two critical points for g in (0, 1), one in (0, 8*) and one in (#", 1). We have that
cosh
g'()) = 0 + sinh 20
Setting y = Or the equation above is the same as
sinh(y) cosh(r)) (r) -
y = azy
x²
which has exactly three solutions: y1 < 0. 5/2 = 0, ys > 0, since 2 cosh(x)) + x² for o 0. Without loss of generality
assume that x > 0 and thus we get that there exists only one 0 > 0 such that g'(0) = 0. which is contradiction.
D. Details on the second-order condition
In this section we provide further details on the second-order condition Definition 2.4. We complement the discussion in Section 2 by showing that the norm-coercivity condition on the forward operator in Definition 2.4 is in fact mild even for functions é with full domain.
Proposition D.I. Let Φ = ho || such that h E (B) satisfies Assumption 1.1. If there exists some C >>> such that
[V)()) - [[L((L[|=|))
(31)
for all x such that || 2 C. then
lim
[T (x)] = =0,
[ +000
for all ó < I.
Proof. In the following we assume that || is large enough such that the assumption of the proposition holds. We have that
< L||=||-
(32)
The implication follows since h(0)) 2 ADD)= - 1 ((),, meaning that (1()) 2 0 for t > 0 and thus [W(O)) = h²(t)) on this
interval implying h²" (t)) = t. Now, by the reverse triangle inequality:
IT
||||||
SL (Z-
|| 5),
where the second inequality follows by (32). Therefore, since 8 1, lim 1T I.L 1 (x)]l = oo and the proof complete.
The fact that this condition is quite mild can be seen by choosing d(x) cosh((|=]]]) 1, where we allow [V to grow exponentially with ||=||]- It is straightforward that this condition holds for example when the norm of the gradient is bounded by some polynomial of the norm of x when ||=|||| is large enough.
We next show that when the matrix fV) is symmetric, the norm-coercivity property of the forward operator in Definition 2.4 is not required in order to obtain result similar to Proposition 2.6.
20

---

Nonlinearly Preconditioned Gradient Methods
Proposition D.2. Let f E (2R be such that for all R and H E dc oc(Vo))(L-vV((x))
mas Tmax ((V2f(=))) S LL
(33)
and HVZ is symmetric. Then, the following inequality holds:
(T,,I-1 (3)) T. (Z), F) (1 -T)| m1
(34)
for all x, IR... particular, for 7 I,-1, the forward operator is strongly monotone with parameter 7 and thus injective.
Proof. Note that the mapping Vœ" (T.- is locally Lipschitz, since V is globally Lipschitz and E (IR)). Then, can invoke the generalized mean value theorem in its summation form (Facchinei & Pang. 2003, Proposition 7. 7.1.16): for two points E I,", there exist n points E (x, R) and scalars a; 2 summing to unity such that
V vo'L = Σ avVi(z- 2),,
(35)
where Vi E (V o V-
Now, in light (Clarke, 1990, p. 75),
Vc(Vø" o -- (z)e S (o (V ((()))
for any E I. Therefore, any Vi -) can be written as L 8,,, =), for > O. with H, Oc (Vo")) ([.)v((x) and 3, 2 0 summing to unity.
Taking an inner product with (x 2), we have that
T,
Σ
8z(1 m.
z))
i=1
j=1
$ L-11
L|[ =1|
where we have used the fact that Amax ( f(x)) S Lİ. By multiplying the inequality above with - and then adding || - =1|2 to both sides we obtain:
- -
m) ž (1 (1- 1
implying that
(T, (xx) -T Tx (5), F) (1 - =113
which is the claimed result.
D.1. Examples
We now move on to providing examples of functions satisfying Definition 2.4. We consider the reference functions Φ1 (xx) cosh([|=]])) (2))) = exp(| [=]) |)- - ||^|||| - and saa (x)x)) = -- -Ix||-In(1- ||x [). which are generated by the (I-dimensional)
kernel functions h (z) = cash(z) hz(z) exp(I=l) - |z| 1 and h2(2)) - |z| In(1 |=]).
We first recall the preconditioner VΦ" and its Jacobian 2200 for general isotropic reference functions.
( = h3' ((ly)))sn(())
Vy R.
and
h:" (1ell)
Vy 10
h ((lvl)
(1
yy |>1
Ay E E" {0}
and (x) h;"(ll))) otherwise. For ease of presentation we denote (,(y) hh;" (Ilvll) and bx()) A-' (lv)) MMll
21

---

Nonlinearly Preconditioned Gradient Methods
Table 2. Anisotropic smoothness constants for the examples of Appendix D.1
Φ1
Φ
d3
2//3/3
23/3
24/3
norm
1,1/3
T,1/3
31,1/3
|x0112
||a||2
L||a=||2 + ||x]|
Aogistic
16L2 + |||l
4L
||l|
4(L + Iall)?
Example D.3 (Norm to power). Let f(x) = 3 ||]||* Then, f is (L, L) aniotrropicaly smooth relative to de for any > 0
and L > Lmorm from the first row of Table 2.
Proof. We first consider the more general f(x) = || with 2 4. The gradient and Hessian of f are given respectively
by
(x()) ||~||- 2x,
V /() = || (p 2)|1=111 txx_.
(36)
The second-order condition then involves the following quantity:
+ ++((--11V(()I) (
V V'o;(-~'V(<t)) = [<<="\\V(=)))
[V
=<:
T2
+ by 11111111111 (1
xT
|
|
We thus have:
V2 (Z (p 1), |2:11 (I= >>>>
| T.
b. b,
|=|||~"|||==100--
(1-
x..'
|
|
The largest eigenvalue of this (symmetric) matrix is
Amax V (L- (L = max {o- 1),,(L- ||-1||1111 (i (L -1=11111111 ||=1110-2
(1-
(37)
and for all the reference functions we consider in this subsection, (p- 1)a,(4 1| 2 (1--111=|1--)) Therefore
the inequality (5) dictates (p- 1)a, (ī. [T, [=]]====]]|]]>>]|||||==>> < LL for all æ E Rm.
Now we specialize to each of the reference functions we consider as well as take p = 4.
For Φ1, 62 and da, we obtain the conditions
3 3/201
3//2|
3T. < L
Φ1
< L,
Ø2 : L ||0||
< L,
Φ3
+ |
(L + ||0||3)2
for which the left-hand sides are maximized at ||^|| = (2T,2)166 ||]||| = (2T.) and || = ( respectively. Plugging these values in yields the resulting lower bounds Luorm Table 2.
Since in every case HV2 is symmetric matrix, follows from Proposition D.2 that the operator TSL- L- injective for any 5 < 1. This implies the anisotropic smoothness of relative to Φs in light of Proposition 2.9 since dom ds is bounded. For Φi and σb the result follows from Proposition 2.9 by the reasoning in Remark 2010.
We now move to the logistic loss function. Example D.4. Let ((x log(1 + exp(-ai Tx)). Then, f is (I, a.)a smooth relative to di for any T. and L > Llgisticc defined in the second row of Table 2.
Proof. The gradient and the hessian of f are given respectively by
ff(x) exp((a x))
V²f(x)
(38)
exp(-a x1 + exp(a Tx))²²
22

---

Nonlinearly Preconditioned Gradient Methods
In this case the second-order condition becomes
|all
a, (v(()))())) exp(-a x)(1 + exp(a x))²
< LL.
(39)
The results from Table for Φ1. @2 and Ø3 then follow respectively from
|a 2
||||
L,
(1 + exp(-a T x))
L2 exp(a z))² ||ll2
V16L2 + ||a||2
||a|1
||a||2
4L + ||o||| L,
(L(1 + exp(a x))
|[x])) + exp(-a Tx))
L||0|12
_|| + ||lls L.
(L(1 + expla x)) [x=])
4(I. + ||]l)2
Note that in this case as well, f(r) is a symmetric matrix and follows from Proposition D.2 that the operator T. injective for any The growth condition Proposition 2.9 satisfied automatically, since f bounded.
D.2. Gradient clipping
now consider case that Φ = 11ll 112 (())))()). By (Themelis et al., 2019, p. 404), the generalized Jacobian the preconditioner is given by
(1) con T, {ll//] -1,
|yy| < 1, if |yll 1, if |lv|| > 1.
(c(Vo")(v)
}.
where 1 denotes the projection matrix onto the orthogonal complement of the subspace spanned by y. The second-order condition (5) then becomes
Amnax (2f(x)) < LL,
if I < L. if if (x) L, if V > L.
Amax (aV2f(x)) + (1 - LIl -2f()) LL, fx)()) [V)( V
Amax
for all a E 1]. In particular, for a = 1, the second condition becomes (2f(x) x LLI, and using the fact that Amax (Il = 1, we also have Amax((aa + (1 - ) I Amax (V2 f()) such that this clause can be merged with the first case. To rewrite the last case in terms symmetric matrices, we note that Amax(ITvrta V² = Amax ((z) V (z)))))<<)))))) where the last equality follows by (Hom & Johnson, 2012.
Amax (112 f(2)4 (()) fz)(x))
Theorem 1.3.22). The second-order condition is therefore
V²f(z) LLI, (V) ( < [[V if [V(()) > L.
if [Vf()) < L.
Note that the first case is akin standard L-smoothness while the second case is reminiscent of (Lo, -m)-moothhnes with Lo 0 but restricted to some subspace. In particular, if V f(x) ((=) for some C' : R E. then the second case is always satisfied, and we only require that f2 L.I for [V[())] < T.. This is the case for both of the examples considered in Appendix D.I.
23


Reviews:
[{"review_id": "wIGcRnv375", "reviewer": "Reviewer_MxEp", "summary": "The studies a non-linearly preconditioned gradient descent method for optimizing some scalar functions $f:R^n\\to R$.\nThe iterations of the method are of \n$$x_{k+1}=x^k-\\gamma \\nabla \\psi^*(\\lambda \\nabla f(x^k)),$$\nwhich is similar to the approach of \"Dual Space Preconditioning for Gradient Descent\" by Maddison et al, although that paper did not consider the inclusion of the parameter $\\lambda$.\n\nThe original paper Maddison et al. only shown convergence results for convex functions $f$, and convex reference functions $\\psi$. \nRecent works Laude & Patrinos, 2022 and Laude et al., 2023 have shown convergence to stationary points for non-convex functions $f$ under a condition called the anisotropic descent property. \n\nThe key contribution of this paper is the development of a very general $(L,\\overline{L})$-anisotropic smoothness property, which is shown to be easily verifiable for a broad range of non-convex functions in Lemma 2.5.\nUnder this property, the algorithm is shown to converge to stationary points of $f$ with explicit rates. Additional sharper convergence results are also obtained for convex $f$ in terms of the optimality gap $f(x^k)-f(x^*)$, improving upon earlier results in Maddison et al. \n\nSome numerical results are also presented to show the practical performance of the algorithm compared to gradient clipping.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n\nAnswer to **Question 1**:\n\nThere are three major differences in the conditions considered in the current paper compared to (Laude & Patrinos, 2022):\n1. We consider reference functions $\\phi$ of possibly not full domain. This leads to a more general descent inequality that allows us to tackle larger problem classes. As an example of the significance of this extension, through Corollary 2.7 and Proposition 2.9 we obtain that functions $f \\in \\mathcal{C}^2(\\mathbb{R}^n)$ that are $(L_0, L_1)$-smooth are also $(L, \\bar L)$-anisotropically smooth relative to $\\phi(x) = -\\|x\\| - \\ln(1-\\|x\\|)$, a function which is defined for $\\|x\\| < 1$. We moreover focus on strongly convex reference functions in order to capture a function class that is wider than Lipschitz smoothness through Proposition 2.3.\n\n 2. We provide a sufficient second order condition for anisotropic smoothness in the form of Definition 2.4, combined with Proposition 2.9. Such a condition (as described in Lemma 2.5) was shown in (Laude & Patrinos, 2022) to be in general only necessary, while it was shown to be sufficient under Legendre convexity of $f$ in (Laude & Patrinos, 2022, Proposition 4.1). Thus we overcome a major limitation of (Laude, Patrinos, 2022) in that we provide a computable condition for anisotropic smoothness. Moreover, in Definition 2.4, we relax the continuous differentiability of $\\nabla \\phi^*$ to Lipschitz continuity thus allowing us to cover more interesting algorithms. Central to our analysis is the new result regarding the (strong) monotonicity of the forward operator.\n\n3. In our paper we study the convex case separately, obtaining for the first time sublinear convergence rates for large classes of reference functions of both the isotropic and the separable type.\n\nAnswer to **Question 2**:\n\nWe thank the reviewer for their suggestion. We performed a preliminary experiment for a subset of the MNIST dataset (600 data points) on a four-layer fully connected network with layer dimensions [28 × 28, 128, 64, 32, 32, 10] and ReLU activation functions, using the cross-entropy loss function. We compare the nonlinearly preconditioned gradient method generated by $\\phi_1(x) = -\\|x\\|-\\ln(1-\\|x\\|)$ and $\\phi_2(x) = \\cosh(\\|x\\|)-1$ and the gradient clipping method. We tuned the methods by performing a grid search on the hyperparameters. The results are presented in the following table, where we report the training loss every 30 iterations.\n\n| Method   | k=30     | k=60     | k=90     | k=120    | k=150    | k=180    | k=210    |\n|----------|----------|----------|----------|----------|----------|----------|----------|\n| $\\phi_1$ | 0.975662 | 0.440863 | 0.118921 | 0.096205 | 0.000098 | 0.000035 | 0.000020 |\n| clipping | 0.921261 | 0.277707 | 0.130072 | 0.145052 | 0.068124 | 0.054605 | 0.000012 |\n| $\\phi_2$ | 1.308716 | 0.593909 | 0.300052 | 0.101221 | 0.008348 | 0.001282 | 0.000670 |\n\nIn this experiment it seems that the method generated by $\\phi_1$ is the best performing, while the clipping gradient method speeds up towards the end to achieve better final accuracy. Due to the simplicity of the experiment we cannot conclude on the effectiveness of the compared methods in general. We believe that different reference functions lead to performance advantages on different architectures and loss functions.\n\n---\n\nReferences:\n\nLaude, E. and Patrinos, P. Anisotropic proximal gradient. arXiv preprint arXiv:2210.15531, 2022.", "claims_and_evidence": "This is a theory paper. The claims of the paper are well supported by the mathematical proofs. The numerical illustrations are of secondary importance, but they also show good empirical performance.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria seem reasonable to us. The method was evaluated both on a convex as well as a non-convex test problem, and compared to gradient clipping.", "theoretical_claims": "I have looked at the proofs, and checked the correctness of the main results (Theorems 3.2, 3.6 and 3.7). I believe that the presentation is clearly written and the proofs are correct and rather ingenious.", "experimental_designs_or_analyses": "The numerical experiments in the paper are appropriately designed, and the analysis of the numerical results is appropriate.", "relation_to_broader_scientific_literature": "This algorithm is closely related the algorithm presented in the paper \"Dual-space preconditioning for gradient descent\", as well as papers by Lu et al. and Bauschke et al.\nA variant of present algorithm has been studied before in the general non convex and composite non-smooth setting in Laude & Patrinos, 2022 different conditions. \nNevertheless, the theoretical results obtained in this paper are shown under much simpler conditions and the results are stronger.\nThe authors do a good job at citing relevant papers from the literature.", "essential_references_not_discussed": "I believe that all essential references have been discussed.", "other_strengths_and_weaknesses": "The key contribution of this paper is the development of a very general $(L,\\overline{L})$-anisotropic smoothness property, which is shown to be easily verifiable for a broad range of non-convex functions in Lemma 2.5.\n\nUnder this property, the algorithm is shown to converge to stationary points of $f$ with explicit rates. Additional sharper convergence results are also obtained for convex $f$ in terms of the optimality gap $f(x^k)-f(x^*)$, improving upon earlier results in Maddison et al. \n\nThese results are interesting as the assumptions on the function $f$ are very mild, the algorithm is simple, and the results are fully explicit.\n\nOne weakness of the paper is that the algorithm presented is not new, and it has been studied before in the general non convex and composite non-smooth setting in Laude & Patrinos, 2022 different conditions. \nNevertheless, the theoretical results obtained in this paper are shown under much simpler conditions and the results are stronger.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "Could you please further clarify the differences between the conditions in your current paper, and the conditions used in Laude & Patrinos, 2022?\n\nIn terms of numerical experiments, in the context of non-convex functions, it would be interesting to see a neural network example for a small dataset using full gradients (with sufficiently wide networks, the loss can be close to 0 on the training data). In particular, you could do a comparison with gradient clipping in such scenarios. Do you think that the performance advantages would be similar as in Section 4.2?", "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": "0ySMAsLbRD", "reviewer": "Reviewer_gkpC", "summary": "1. This paper introduces a unified preconditioning gradient descent scheme for some of the popular optimization algorithms including Adam, Adagrad, gradient clipping.\n2. The paper introduces the concept of anisotropic smoothness, which generalizes the relative smoothness. It gives 2nd order sufficient conditions of the concept.\n3. The paper gives proof of sub-linear convergence for several classes of reference functions, and verifies through numerical experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s time and effort in providing feedback.\n\nRegarding the stated **Weaknesses**:\n1. Our results cover both the convex and nonconvex setting. The convergence results in the nonconvex setting are presented in Section 3.1.\n2. The scope of the current manuscript is to lay the theoretical foundations of the framework. Therefore, we have provided indicative experiments on problems that are relevant in the generalized smoothness literature. Moreover, we note that the phase retrieval problem is nonconvex.\n3. As is standard for descent-type methods we provide a sufficient second order condition that allows us to compute the stepsizes of the method. In cases where the constants are difficult to compute, one can utilize a variation of the classical linesearch procedure to adaptively determine the stepsize sequence.\n4. We tend to disagree with the reviewer as we believe that looking at these algorithms under the lens of generalized convexity provides valuable intuition. This connection with generalized convexity is also the main ingredient for many of our proofs.\n\nConcerning item 3 of the **Claims And Evidence** section we would like to stress that our claim is that we prove with a novel technique the sublinear convergence rate for large classes of functions, a result which is presented in Theorem 3.7. Regarding item 1 of the **Claims And Evidence** section, see our response to Reviewer ZfYL. \n\nAnswer to **Question 1**:\n\nIndeed, the update defined in (2) bears similarities to mirror descent. In fact the scheme we analyze can be considered as left-preconditioning in contrast to mirror descent’s right-preconditioning (Maddison et al., 2021, p. 3). Nevertheless, the two methods produce different iterates while the descent inequalities used to analyze them also differ. Our paper relies on anisotropic smoothness, while mirror descent is analyzed using the relative smoothness condition. Thus, the nonlinearly preconditioned gradient scheme is used to tackle different problem classes than mirror descent.\n\nAnswer to **Question 2**:\n\nTo the best of our knowledge, Bregman gradient descent schemes under relative smoothness can be accelerated when the generated Bregman divergence satisfies some favorable properties (Hanzely et al., 2021). We believe that this is the case with the nonlinearly preconditioned gradient scheme as well, i.e. the method can be accelerated under specific conditions for the reference function $\\phi$. We believe that this is interesting future work.\n\nAnswer to **Question 3**:\n\nWe respectfully disagree with the reviewer. It is known that for convex and Lipschitz smooth functions, gradient descent with a fixed stepsize of $1/L$ monotonically decreases the norm of the gradient (Beck, 2017, Theorem 10.27). We thus believe that our Theorem 3.6 generalizes this result to the anisotropic smoothness framework for isotropic reference functions.\n\n---\n\nReferences:\n\nMaddison, C. J., Paulin, D., Teh, Y. W., and Doucet, A. Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1):991–1016, 2021.\n\nHanzely, F., Richtarik, P., & Xiao, L. (2021). Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Computational Optimization and Applications, 79, 405-440.\n\nBeck, A. First-order methods in optimization. SIAM, 2017.", "claims_and_evidence": "1. The suggested scheme is claimed to be a common framework for the popular algorithms. However, it recovers only special cases of parameter choices in those algorithms, and does not provide a framework to analyze them in general.\n2. Section 2 supports the claim that the new anisotropic smoothness covers a broader range of functions. In particular, Corollary 2.7 gives a new method of obtaining the forward iterates.\n3. Theorem 3.6 and 3.7 gives evidence of sub-linear convergence for nonlinearly preconditioned methods with (1) isotropic reference functions and (2) 2-subhomogeneous functions. However, the claim on general separable reference functions is not explicitly proved and justified. \n4. In the numerical experiments, the algorithm is only compared with other basic ones, such as GD and clipping, and results of other preconditioned gradient methods or Adam/Adagrad remain unreported.", "methods_and_evaluation_criteria": "The methods and theoretical proofs make sense, but the paper does not give realistic choices of parameters lambda, gamma for arbitrary objectives. This might be of trouble when the curvature of function is unknown or expensive to compute.", "theoretical_claims": "I checked the proofs of Theorem 3.2, Corollary 3.3, and Proposition 3.5. No issues were found in these proofs.", "experimental_designs_or_analyses": "The first experiment optimizes a norm-to-power-4 problem, and plots the results of algorithms with different reference functions (but all belong to the class of isotropic functions) and different parameters, though it might be better to give a comparison against other existing algorithms in smooth convex optimization. \n\nThe objective of the second experiment has overlap with the first one, as they share the same polynomial growth rate. It can be more convincing to choose other problems. Moreover, the results of the second experiment involves a specific choice of parameters, but in general parameters are unknown, and it might be important to show sensitivity to parameters, like the first experiment.", "relation_to_broader_scientific_literature": "The research is closely related to the existing study of non-linear preconditioned gradient descent/mirror descent.", "essential_references_not_discussed": "Relative smoothness is used a lot in the mirror descent method. \n\nAmir Beck, Marc Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, Volume 31, Issue 3, 2003, Pages 167-175.\n\nFilip Hanzely, Peter Richt´arik, and Lin Xiao. Accelerated bregman proximal gradient methods for relatively smooth convex optimization. Computational Optimization and Applications, 79:405 – 440, 2018.", "other_strengths_and_weaknesses": "Strengths :\n\n1. Writing is clear, the main idea is easy to understand\n2. Experiment settings are detailed and easy to implement\n\nWeaknesses:\n\n1. The proposed algorithm in the paper only solves smooth convex optimization problems, and did not touch wider area in optimization.\n2. The experimented objective functions are limited to small-scale smooth convex functions defined on the whole space. Non-convex problems and problems on a subset are not experimented.\n3. Parameter tuning are not discussed.\n4. The intution of some technical results is missing.", "other_comments_or_suggestions": "**Abstract:**\n\n- \"thus allowing us to go beyond already established methods.\" → \"thus allowing us to extend beyond already established methods.\" (\"go beyond\" is slightly informal)\n- \"in both the convex and nonconvex setting\" → \"in both the convex and nonconvex settings\" (plural for consistency).", "questions_for_authors": "1. The iteration in (2) and the analysis using relative smoothness resemble the mirror descent update:  \n   $$\n   \\nabla \\phi(x^{k+1}) - \\nabla \\phi(x^{k}) = -\\alpha_k \\nabla f(x_k).  \n   $$\n   What is the advantage of using nonlinear preconditioned gradient methods over mirror descent in this context?  \n\n2. Accelerated mirror descent methods have been designed and analyzed. Can the proposed nonlinear preconditioned gradient methods be accelerated in a similar manner?  \n\n3. In Theorem 3.6, it is claimed that the norm of the gradient of $f$ decreases monotonically along the iterates of the algorithm:  \n   $$\n   \\|\\nabla f(x_{k+1})\\| \\leq \\|\\nabla f(x_k)\\|, \\quad \\text{for all } k \\in \\mathbb{N}_0.  \n   $$\n   However, in the simplest case—when the reference function is the squared norm—the method reduces to the standard gradient descent method, for which no such monotonicity result holds. Could you clarify this discrepancy?", "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": "GU4YamBFi4", "reviewer": "Reviewer_riQT", "summary": "The paper studies non-linearly preconditioned gradient methods, analyzing algorithms of the form $x^{k+1} = x^k - \\gamma\\nabla\\phi^*(\\lambda \\nabla f(x^k))$, where where $\\phi^*$ is a convex dual reference function, and $f$ is continuously differentiable but potentially non-convex.\nThis general framework encompasses several widely used methods, including standard gradient descent, AdaGrad without memory (i.e., $\\beta_1 = \\beta_2 = 0$), Adam with exponential decay rates set to $0$ (i.e., $\\beta_1 = \\beta_2 = 0$) and clipped GD.\nThe paper provides theoretical guarantees under a new $(L, \\bar{L})$-anisotropic smoothness assumption, extending prior work on generalized smoothness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. \n\nOur answers for **Questions 1 and 2** are summarized in the following. Regarding the $(L, \\bar L)$-anisotropic smoothness condition, our contribution is threefold:\n- First and foremost, we describe a general setting where the second-order condition presented in Definition 2.4 is not only necessary but also sufficient for anisotropic smoothness. This condition was shown to be sufficient in (Laude & Patrinos, 2022) only when $f$ itself is a Legendre function, not applying to the general nonconvex setting we consider in our paper. Moreover, in Definition 2.4 we allow for $\\phi^*$ to be just Lipschitz smooth and not twice continuously differentiable, thus allowing us to study the interesting case where the update in Equation (2) takes the form of the popular gradient clipping method.\n- Second, we lift a major restriction of (Laude & Patrinos, 2022) by allowing ${\\rm dom} \\phi \\neq \\mathbb{R}^n$, which leads to a more general descent inequality by choosing a reference function $\\phi$ with faster growth. As an example, through Corollary 2.7 and Proposition 2.9, we get that functions $f \\in \\mathcal{C}^2(\\mathbb{R}^n)$ that are $(L_0, L_1)$-smooth are also $(L, \\bar L)$-anisotropically smooth relative to $\\phi(x) = -\\|x\\| - \\ln(1-\\|x\\|)$ which is defined for $\\|x\\| < 1$. Therefore we obtain novel characterizations for this class of functions (through Proposition 2.2 and Proposition 3.5) and we can tackle problems involving such functions with preconditioned gradient steps defined as in Corollary 2.7.\n- Third, we introduce flexibility by allowing for two different constants whose interplay might have a significant impact in practice, as also indicated by our preliminary experiments. \n\nAs for the convergence results, we provide the following novel findings:\n- In the nonconvex setting, our analysis leads to stepsizes up to $2/L$.\n- In the convex setting, we obtain the first sublinear convergence rate for the suboptimality gap $f(x^k)-f^\\star$ for large classes of reference functions $\\phi$. To the best of our knowledge, such a result does not exist in (Laude & Patrinos, 2022) or in the related literature. We would like to stress that this is not an easy task: in the isotropic case we utilize the star cocoercivity-like property described in Proposition 3.5 and study the problem as a rescaled gradient descent method. In the more challenging separable case we manage to obtain such a result by considering a nonlinear proximal point reformulation of the method and harnessing the subhomogeneity of the reference function.\n\nFor **Question 3**: Except for the toy example $f(x) = 1/p \\|x\\|^p$ considered in the paper, through the aforementioned relation between anisotropic and $(L_0, L_1)$-smoothness, examples of not globally Lipschitz smooth functions that are anisotropically smooth can be found in the $(L_0, L_1)$-smoothness literature (Zhang et al., 2019; Chen et al., 2023). Moreover, we would like to emphasize that examples of Lipschitz smooth functions that are anisotropically smooth with a different parametrization such as the logistic loss function studied in the paper are also of interest, since this can lead to faster algorithms.\n\n---\nReferences:\n\nLaude, E. and Patrinos, P. Anisotropic proximal gradient. arXiv preprint arXiv:2210.15531, 2022.\n\nZhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881, 2019.\n\nChen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.", "claims_and_evidence": "The claims are well-supported by theoretical analysis. The proofs appear sound, and the results align with existing literature.", "methods_and_evaluation_criteria": "The paper provides simple experiments for minimizing $\\frac{1}{4} \\|x\\|^4$ and a non-convex phase retrieval task on synthetic data. While limited in scope, these experiments highlight the properties of the proposed framework. Given the paper’s theoretical focus, this level of empirical validation is reasonable.", "theoretical_claims": "I reviewed the main theoretical results, including key theorems and lemmas. However, I did not verify all details in the supplementary material (additional examples etc).", "experimental_designs_or_analyses": "The experiments are designed to demonstrate key theoretical insights rather than provide extensive empirical validation. They are appropriate for this purpose, and the results appear consistent with the claims made in the paper.", "relation_to_broader_scientific_literature": "This work builds on prior studies of dual-space preconditioning and anisotropic smoothness. \nThe general framework considered in the paper was originally analyzed in [1] under the dual relative smoothness condition for convex and essentially smooth functions, and then analyzed in the general non-convex and composite non-smooth setting in [2] under the anisotropic descent property.\nThe authors extend the previous results by introducing the $(L, \\bar{L})$-anisotropic smoothness assumption. This new condition broadens the class of functions considered while reducing to previous formulation when ${\\rm dom} \\phi = \\mathbb{R}^n$.\n\nThere is a significant body of literature on generalized smoothness, and this work extends some of these notions.\n\n[1] Maddison, C. J., Paulin, D., Teh, Y. W., and Doucet, A. Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1):991–1016, 2021.\n\n[2] Laude, E. and Patrinos, P. Anisotropic proximal gradient. arXiv preprint arXiv:2210.15531, 2022.", "essential_references_not_discussed": "I do not see any major omissions.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- The paper is well-written, clearly structured, and engaging.\n- It presents an elegant theoretical framework that unifies and generalizes several known algorithms.\n\n**Weaknesses:**\n\n- The significance of the extension is not entirely clear. While mathematically interesting, it would be helpful to better motivate why this generalization is necessary or practically impactful.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "1. What exactly does the new framework cover that is not already addressed in [2]? A clearer distinction would help contextualize the novelty and significance o contributions.\n\n2. $(L, \\bar{L})$-anisotropic smoothness condition reduces to the one in [2] when ${\\rm dom} \\phi = \\mathbb{R}^n$. What additional benefits does this relaxation provide when ${\\rm dom} \\phi \\neq \\mathbb{R}^n$?\n\n3. Proposition 2.3 shows that for strongly convex reference functions, the class of anisotropically smooth functions is at least as large as that of Lipschitz smooth ones. What are the most relevant examples demonstrating that this class is strictly larger?", "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": "lEJIXYE5nf", "reviewer": "Reviewer_ZfYL", "summary": "This work studies nonlinearly preconditioned gradient methods. After comparison with existing methods and discussing the existing connections, an extension of anisotropic smoothness was proposed. For specific choices of the reference function (1- isotropic reference function and 2- separable reference function) the procedure of calculating a second order condition for $(L,\\bar{L})$-anisotropic smoothness was explained. Later, the convergence of the preconditioned gradient method (2) was studied under the settings: a) nonconvexity + smoothness and b) convexity. Simple experiments were conducted to evaluate the performance of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. \n\nRegarding the experimental design,  our paper is focused on theoretical analysis and thus we only provide preliminary experimental results on problems that are associated with generalized smoothness in the related literature (Chen et al., 2023; Gorbunov et al., 2024; Vankov et al., 2024).\n\nMoreover, in Theorem 3.6 we strengthen the results of (Laude & Patrinos, 2022) and  (Maddison et al., 2021) in the following ways: we show that for isotropic reference functions the sequence of iterates generated by the method is Fejér monotone and we obtain a sublinear rate for the suboptimality gap $f(x^k) - f^\\star$. To the best of our knowledge such results have not been shown before.\n\nRegarding the presentation of our paper, we agree that we can make some statements more self-contained and we will change this in a revised version of the paper. We would also like to point out that the quoted text contains typos that are not present in the paper.\n\nThe meaning of **Questions 1 & 2** is not entirely clear to us. In the following we answer the questions as we understood them. If the answers are not satisfactory, please provide some more clarification.\n\nAnswer to **Question 1**:\n\nAs already mentioned, in this paper we focus on theoretical analysis. Nevertheless, we believe that applying the nonlinearly preconditioned gradient method to training problems is interesting future work.\n\nAnswer to **Question 2**:\n\nWe conjecture that the algorithm generated by the reference function $\\cosh-1$ outperforms the rest of the methods on our experiments because the preconditioner is better tailored to such high order polynomial functions.\n\nAnswer to **Question 3**:\n\nWe agree with the reviewer that our wording might cause confusion and we will change our text. What we show in Subsection 1.6 is that if one was to remove the gradient accumulation and momentum mechanisms from these methods, they would obtain the shown basic forward iterations. We are well aware that momentum plays a crucial role in the success of methods such as Adam and Adagrad. However, in this paper we mostly focused on laying the foundation for a new framework for analyzing various gradient descent type methods. Extensions such as adding momentum to recover schemes like Adam and Adagrad are possible and an exciting direction for future research. Moreover, through this connection, practical new algorithms can be derived by combining the momentum mechanisms with other reference functions $\\phi$.\n\n---\n\nReferences: \n\nChen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.\n\nGorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richtárik, P., Horváth, S., Takáč, M. Methods for convex $(L_0, L_1)$-smooth optimization: Clipping, acceleration, and adaptivity. arXiv preprint arXiv:2409.14989, 2024\n\nVankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. U. Optimizing $(L_0, L_1)$-smooth functions by gradient methods. arXiv preprint arXiv:2410.10800, 2024.\n\nLaude, E. and Patrinos, P. Anisotropic proximal gradient. arXiv preprint arXiv:2210.15531, 2022.\n\nMaddison, C. J., Paulin, D., Teh, Y. W., and Doucet, A. Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1):991–1016, 2021.", "claims_and_evidence": "Most of the claims are supported. One confusing part is in line 101: \"... we describe a common nonlinear gradient preconditioning scheme for the main iterates of popular algorithms including gradient clipping, Adam, Adagrad and ...\". However, as described in Section 1.6, a special case of these methods were recovered. These special cases have no gradient accumulation or momentum which are important building blocks for the successful performance of the mentioned algorithms.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes, the current experiments are sound. One  issue, is as follows:\nThe paper claims that their framework brings out novel insights for the class of ($L_0$-$L_1$)-smooth functions and it allows them to go beyond already established methods. While I appreciate such direction, the paper leaves me with no numerical insights toward understanding how this claim looks like in practice.", "relation_to_broader_scientific_literature": "One of the contributions relates to an extension of the anisotropic smoothness. The new definition allows for two different constants to play a complementary role. Accordingly, a second order sufficient condition was defined. Additionally, the analysis for nonconvex functions nonsmooth functions was extended to nonconvex smooth functions. The new result allowed for larger step sizes compared to the previous work. The authors claim that they strengthen the results from some previous works in Theorem 3.6, but it was not mentioned that in what sense did they strengthen the prior results?", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths: I like the idea of moving toward unified models to understand and gain insights about the existing concepts. This work endeavours to move toward this direction by relating to generalized and more realistic smoothness assumptions. They also explored the performance of algorithm (2) in terms of convergence rate under smooth nonconvex and convex assumptions. Unfortunately, this extension was not formulated numerically and experimentally, leaving the readers doubtful about the applicability of their $(L,\\bar{L})$-smoothness extension.", "other_comments_or_suggestions": "I believe the paper would benefit from a comprehensive revision specially in terms of presentation and delivering the message. In many instances, vague statements leave the reader helpless. Such statements damage the independentness of the paper. Examples are:\n\nline 255: \"... are Legndre through (Laude & Patrinos, 2022, Proposition 4.1)\"\n\nline 258: \"... when $\\phi$ is a regular optimal transport cost in light of (Villani,2008 Definition 12.27)\"\n\nline 269: \" Note that in this case (Gorbunov et al., 2024, Algorithm 1) can be viewed as (2) with a convservative ...\"\n\nline 272: \"In a similar manner, the stepsize introduced in [Vankov et al., 2024, Equation (3.5)] can be viewed as a less tight version of Corollary 2.7.\"\n\nline 379: \"wile also answering the question posed in (Maddison et al., 2021, p. 17).\"\n\nFigure 3 (right): I suggest a probability bound instead of 100 instances since it would be a more meaningful visualization.", "questions_for_authors": "First, I'd like to thank the authors for their research.\n\n1- I like the idealogy/motivation presented in lines 80-95. Why authors did not use this idealogy in practice and see how reference functions with appealing properties (like strong convexity) perform in training problems?\n\n2- lines 417-419: Is this why Fig3(right) acieves slighly better results?\n\n3- Why does the paper claims encompassing Adagrad, Adam, and Gradient Clipping methods, when they only recover a special case of  these methods? (On the side: the momentum plays a crucial role in the success of algorithms like Adam and should not be neglected.)", "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:

Meta-review: The paper presents a unified nonlinear gradient preconditioning framework that encompasses popular algorithms such as gradient clipping, Adam, Adagrad, and recent methods tailored for $(L_0, L_1)$-smooth functions. It also introduces anisotropic smoothness that is more general that L-smoothness, and showcases its application in the convergence analysis of the algorithm in the nonconvex regime.
 
Four reviewers evaluated the paper, and their overall assessment is positive. I agree with their evaluation and believe the paper makes a significant contribution with compelling results. In particular, I believe the most impressive result in this paper is the introduction of the anisotropic smoothness property, which is shown to be easily verifiable for a broad range of non-convex functions.
Decision: Accept (oral)