Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis
Authors: Konstantinos Oikonomidis
Jan Quan
Panagiotis Patrinos
Venue: NeurIPS 2025 poster ()
Keywords: nonconvex optimization
generalized smoothness
first-order methods
Primary area: optimization

Abstract: We study nonlinearly preconditioned gradient methods for smooth nonconvex optimization problems, focusing on sigmoid preconditioners that inherently perform a form of gradient clipping akin to the widely used gradient clipping technique. Building upon this idea, we introduce a novel heavy ball-type algorithm and provide convergence guarantees under a generalized smoothness condition that is less restrictive than traditional Lipschitz smoothness, thus covering a broader class of functions. Additionally, we develop a stochastic variant of the base method and study its convergence properties under different noise assumptions. We compare the proposed algorithms with baseline methods on diverse tasks from machine learning including neural network training.

Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis
Konstantinos Oikonomidis" ESAT-STADIUS & Leuven.AI KU Leuven
Jan Quan" ESAT-STADIUS & Leuven.Al KU Leuven
konstantinos. hatrrammiioso.okkooommmsisssuuee be
j jan wwr.quun@kuleeven..o be
Panagiotis Patrinos
ESAT-STADIUS & Leuven.AI
KU Leuven
panos. panos.patrinoskkulleeeeee patrinos@kuleuveen.
Abstract
We study nonlinearly preconditioned gradient methods for smooth nonconvex opti- mization problems, focusing sigmoid preconditioners that inherently perform a form of gradient clipping akin to the widely used gradient clipping technique. Building upon this idea, we introduce novel heavy ball-type algorithm and pro- vide convergence guarantees under a generalized smoothness condition that is less restrictive than traditional Lipschitz smoothness, thus covering broader class of functions. Additionally, we develop a stochastic variant of the base method and study its convergence properties under different noise assumptions. We compare the proposed algorithms with baseline methods on diverse tasks from machine learning including neural network training.
Introduction and preliminaries
In this paper we consider general minimization problems of the form:
min f(x, RE
(P)
where f R= of the gradient, gradient descent (GD) and its stochastic counterpart, stochastic gradient descent (SGD) are the standard methods to efficiently tackle such problems. Gradient descent-type methods are the backbone of training machine learning models, especially considering the ever-growing size of datasets and architectures. Nevertheless, most modern-day applications involve cost functions that do not fit into the traditional Lipschitz gradient assumption [48]. Although GD and SGD, being versatile solvers, can handle such problems as well, they require careful tuning or expensive linescarch strategies to converge. In recent years, there has thus been considerable effort to introduce and analyze methods that can better adapt to more general smoothness conditions.
smooth and possibly nonconvex function. Under (global) Lipschitz continuity
Gradient clipping [48, 20] is standard practice in tasks such as language models and has been widely used to stabilize the training of neural networks. Recently, the method has received lot of theoretical attention, especially since it was shown to be effective for problems under a less restrictive notion of smoothness, called (Lo, L1)-ssssss smoothness [48]. In [36], it was shown that in fact whole family of clipping methods, including the soft clipping algorithm [47] can be viewed as simple gradient
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Examples of reference functions along with generated algorithms. The subseript denotes the coordinate- tiine update. We call the method generated by cosh - Hyperbolic Gradient Descent (HGD), while indicates that the method is generated by an isotropic reference function and by separable one (see also Subsection 1.4).
((x)
Update
Algorithm
<(-||=]| In(1 - ||x)))
xx x²
[a V vf(x*)
NGD [48, Equation (6)
Σi=1 (- |1:|| In(1 - (x)
2 x
++ ++ I (w*t)) V=r(tx))
sNGD
cosh(||<<]])
x x
7 A ((*)))
arsinh V (1]) ff(ha)
iHGD
Ei=1 cosh(2;) -
x 10+1
x y arsinh (+f((=)))
sHGD
descent with nonlinear preconditioning: given x:0
E R and a stepsize y > 0, update x² as
= x - (Vf(z)))
(I)
In this scheme, Ø R - R is a convex function that plays the role of a reference function, while its convex conjugate, 6* is called the dual reference function and generates the preconditioner Vø*.
The fact that this method is connected to the gradient clipping framework can be seen by choosing strongly convex reference function 6 that has bounded domain. Then, the mapping Vλ maps I²" to
the unit n-ball and such, naturally clips the gradient. In fact, for (xx) <(=||==|| - In(1 [|=+I)) with e > O, (1) takes the form of the popular normalized gradient descent method (NGD). as displayed in the first line of Table 1. It is moreover important to stress the versatility of the framework, in that it also involves algorithms that normalize the gradient per component, akin to the methods that are used
in practice. Such an example presented in the second line of Table 1.
In fact, the method in (1) is naturally generated from a majorization pntoriizationmmmmmizattioo perspective, where in each iteration the following nonlinear upper bound is minimized w.r.t. x:
f(x) S f(x*) + [o(((z x²))
(2)
This inequality is called the anisotropic descent inequality [24] and natural extension of Lipschitz smoothness that is tightly connected to the notion of $- convexity [1] and to optimal transport theory [45]. We present more details on the concept of Φ-convexity in Appendix A.
where y² - = Vo
Intuitively, in order to generate less restrictive descent inequalities, one would consider reference functions & that grow rapidly, thus making the r.h.s. of (2) as large as possible. This procedure leads to algorithms similar to the one in the first line of Table 1. Nevertheless, one can follow a different procedure and generate descent inequality that is tighter model of the cost function, thus obtaining an algorithm with faster convergence. Consider for example ((x) = cosh( [|<]|) - 1. This function grows faster than any polynomial in ||a||| and is strongly convex, implying that the algorithm presented in the third line of Table 1 can handle problems beyond Lipschitz smoothness (from [36, Proposition 2.3]). However, in contrast to gradient clipping, the generated method does not clip the gradient to a predefined value, but rather rescales it adaptively, leading to an implicit adaptive stepsize rule. In fact, for reference functions that grow faster than ||,z]] the descent inequality is less restrictive than the standard Euclidean descent, and the preconditioner naturally takes a sigmoid shape. For example, p(z)= = cosh(]| [I) leads to V (y) = arsinh (1///l) y
Nevertheless, although considerable effort has been dedicated to analyzing the gradient clipping method, general methods of the form (1) are much less explored. In this paper we aim at bridging this gap, by introducing a heavy ball-type algorithm based on (1) and performing an initial analysis of stochastic extension of (1).
1.1 Our contribution
We summarize the contributions of the paper in the following.
We extend the anisotropic gradient descent method [32, 24, 36] by incorporating heavy-ball momentum in the base iterate and study the convergence guarantees of the proposed method

---

in the general nonconvex setting. To the best of our knowledge, such a scheme has not been analyzed before in the full generality of the setting considered in this paper. We remark that our analysis is based on the anisotropic descent inequality, condition that is less restrictive than (To, L1 >-smoothness and is applicable to whole family of algorithms. Moreover, we prove that our scheme enjoys linear rate of convergence under generalized PL. condition.
We propose a stochastic extension of the base method and analyze it under different noise assumptions. We first prove its approximate convergence under condition that we show is less restrictive than bounded variance and then provide a convergence rate for interesting reference functions assuming bounded variance and unbiasedness of the stochastic oracle. We moreover study the method under a generalized PI. inequality that leads to a linear rate up a constant.
In numerical simulations we show that the proposed methods perform well on variety of machine learning problems, including neural network training and matrix factorization.
1.2 Related work
Dual space preconditioning anisotropic gradient descent. The general scheme presented in (1) was originally introduced in [32] for convex, essentially smooth problems, where it was studied under a generalization of cocoercivity called dual relative smoothness. The anisotropic descent inequality, which lies at the center of our analysis was introduced in [26] and was further studied in [24], where also a proximal extension of the base method (1) was introduced in order tackle nonconvex, composite nonsmooth minimization problems. Further results were then provided under generalized convexity point of view in [28, 35), while generalization of the method in measure spaces was presented in [4]. Moreover, a nonlinear proximal point method for monotone operators was analyzed in [25]. while the regularity properties of the anisotropic proximal mapping where a general nonlinear strictly convex prox function is used, were studied in [27, 23]. Recently in [36], the method was shown to encompass a variety of popular algorithms including but not limited the clipped and normalized gradient method. Finally in [18] an accelerated extension of (1) for Lipschitz smooth functions was introduced and studied.
Gradient clipping and generalized smoothness. Departing from the anisotropic gradient descent framework, the algorithms that we study are mostly connected to clipped and normalized gradient methods. Although the literature in this field is vast and ever-expanding we refer to some of the major works in the following. In [48] the notion of (Lo, -1ssmmootsssss was introduced and the first theoretical analysis of gradient clipping under this new condition was presented. This approach was later extended in [47], where a general clipping framework with momentum under (Lo, L1)- smoothness was analyzed in the deterministic and the stochastic setting. [8] studied an algorithm that used both clipping and normalization to tackle more general noise assumptions, further deepening the theoretical understanding of the method. A large body of work has since been devoted to studying such methods under relaxed noise and smoothness assumptions [17, 20, 7, 30, 15, 16, 29, 46). Moreover, for convex problems, in [11], stochastic clipping method where the clipping is performed using an independent sample was analyzed.
The notion of (Lo. L1 >-mmoohhness has also received widespread attention beyond the gradient clipping literature. In [44] new interesting methods for (Lg. -moohh problems that take the form of rescaled gradient descent were introduced and studied, and an accelerated variant for convex problems was proposed. An analysis for convex problems was performed in [12] where also a stochastic variant of the proposed method under interpolation was studied.
1.3 Notation
We denote by ((-)) the standard Euclidean inner product on R² and by ||-|] the standard Euclidean norm on Th. as well as the spectral norm for matrices. We denote by (*(Y) the class of functions which are & times continuously differentiable on an open set Y C TR.. For a proper function R: + R with TV = R U [+oo] } and À 2 0 we define the episcaling (A fz) = >f(>-12) x) for >> and (A+ * fz) = o (I) otherwise. For an f E (RR)) we say that it (Lu, L2) smoothh
for some La, In > if it holds that [[x]]( < To + [n]] for all E T. adopt the notation from [42].
Otherwise we
3

---

1.4 The anisotropic descent inequality
Our analysis is centered around the anisotropic descent inequality from [24], that was recently shown to be connected to other notions of generalized smoothness in [36] and is itself a globalization of anisotropic prox-regularity [23, Definition 2.13].
Definition 1.1 (anisotropic descent inequality). Let f' CECCC(R) such that the following constraint
qualification holds true
rge Vf C rge VΦ.
(3)
Then we say that f satisfies the anisotropic descent property (is anisotropically smooth) relative to if for all x, B E I
f(x) S f()) + t d(a 5) + <( -9),
where y = (V)(t))
Although in [36] a different form of anisotropic smoothness that contains two constants L, L was presented, w.l.o.g. we present the simpler version displayed above since the constant L can be absorbed into o by considering Ø Ló.
In this paper, we focus mostly on strongly convex reference functions that grow faster than the quadratic, in order to analyze the method under less restrictive conditions than Lipschitz smoothness via [36, Proposition 2.3]. Keeping in line with the related literature, for some kernel function h: IR I. we refer to functions o h || or separable. The kernel function h = cosh -1 has some interesting properties that we focus on throughout the paper: is strongly convex, grows faster than any polynomial and has full domain, thus leading to a preconditioner that does not fully clip the gradient, but rather rescales it adaptively. We call the method generated by cosh - the hyperbolic gradient descent (HGD) method.
isotropic and (xx)) Σi= l1g anisotropic
We next formulate our assumptions on ø. which we consider valid throughout the rest of the paper.
Assumption 1.2. The reference function o R" + E is strongly convex and even with (00) 0. int dom o # 0; & E (iin dom 6) for any sequence {a* JREN, that converges to some boundary point of int dom @) [| )I - +00
Note that under Assumption 1.2 6* (R*) from [41, p. 42], while VΦ" is globally Lipschitz continuous and we can omit the constraint qualification in the definition of anisotropic smoothness. Moreover, from [2, Proposition 11.7], arg min á = {0} and thus é 2 Having formulated our assumption on the reference function, we now move on to the assumptions on the cost function.
Assumption 1.3. The cost function f R - RR is anisotropically smooth with constant L >> 0 and f. inf f -0.
It is important to note that under generally mild conditions anisotropic smoothness follows from a second-order characterization [36, Lemma 2.5]:
V f(x < L 8* (Vf(=)))- Va E R
(5)
which leads to connection with the popular (Lo, In)-smoothness condition [48]:
Remark 1.4 (connection between (Lo, L1)- and anisotropic smoothness). In light of [36, Corollary 2.11], any f E C2 (R") that (1 -smoohh, is also anisotropically smooth relative to d(x) Le (- - In [|=]))) with any constant L < L1. important to stress that this result is due to simplification of the matrix inequality displayed above and as such, anisotropic smoothness actually holds with tighter constants in many interesting cases, In fact, as shown in [3, Section A.3], anisotropic smoothness for this specific reference function is less restrictive than (Lo, L1)- smoothness, since there exist continuously differentiable functions that are not (Lo. L1)- -mooth but are anisotropically smooth.
We stress that our stationarity measure throughout the paper is (Vf((()))))) which is the natural measure for this algorithmic family. When specifying Φ, one can in many cases also translate the results to the standard measure [=) For example, for á cosh || 1, we have that and thus the analysis follows similarly to [36, Corollary
di (V (Vf()))) V [V](2)] 3.3].

---

2 The nonlinearly preconditioned gradient method with momentum
In this section we propose and analyze a novel heavy ball-type method based on (1). The proof' can be found in Appendix C.
Algorithm 1 Nonlinearly preconditioned gradient method with momentum (m-NPGM)
Require: Choose _² E RR. 7, B 0 and set m-1 On- Repeat for = 0, until convergence
1: Compute
m (1- (1-
(1-
(6)
2: Compute
xt1 x ym.
(7)
Remark 2.1. Before moving to convergence results, we have to note that our proposed method Algorithm 1 is different from the methods in the related literature. Specifically, our momentum estimate consists of convex combinations of the preconditioned gradients, in contrast to the standard technique of aggregating the gradients and then preconditioning n in the update of =+1 [16, 39, 40, 43]. With simple algebraic manipulations, the algorithm be written equivalently
x 1+ = x² (1 V/ (V + B(x - -x" =²=1),
and thus takes the form of the standard heavy ball method but applied to the mapping V V.f. We believe that this is a more natural approach for the descent inequality we base our analysis on. This is made more apparent with the introduction of our Assumption 2.5.
The following theorem describes the convergence of Algorithm under anisotropic smoothness of f. To the best of our knowledge this is the first result regarding the convergence of the method with momentum.
Theorem 2.2. Let Assumption 1.3 hold and J be the sequence of iterates generated by Algorithm I with 3 E 0.5) and ? L. a I 1. Then, we have the following rate:
L(f(x))-1 f-)
(Vo < OSKER
min
(8)
a(K + +1(11-
233) 23)
The proof of Theorem 2.2 requires some additional effort compared to standard heavy ball momentum analysis under Lipschitz or (To, I4)-smoothness due the particular structure of the anisotropic descent inequality (4). For example, consider the special case where algorithm becomes standard gradient descent with fixed stepsize. Then, the anisotropic descent inequality is just the Euclidean one after completing the squares. By using the Pythagorean theorem, one can handle the terms on the r.h.s. of the inequality and then follow a similar technique to [34]. Nevertheless, such property is not present for the general reference functions that consider in this paper and thus a different approach is necessary.
1 || and the main
Another difficulty arising due to the generality of the setting we consider is that there do not exist
global upper bounds for [x) V f [.))], in contrast to Fuclidean [34] or ( (To, L -s)-smootsssss [47]. Finally, due to the general nature of the preconditioner VØ which can span the whole space, the
analysis becomes more complicated, in contrast to clipping or normalized gradient methods. To better motivate this, note that for normalized gradient type methods such [30, Algorithm 1], the
primal update takes the form x k+1 -² - Y [lm= and as such ||a x || = 7, thus bounding the distance between consecutive iterates and simplifying the analysis.
We are nonetheless able to prove the convergence of the method with novel proof technique that is solely based on the convexity of the reference function ø, thus also unifying and greatly simplifying the analysis. As caveat, we are not able to show the result for any 3 E [0. 1) is the case for Lipschitz smooth functions [34]. Whether or not this constraint can be lifted for the general setting consider, is interesting open question.
5

---

2.1 Convergence under generalized PL condition
In a majorization- intiatttionmmiimizattin procedure, upper bounds of the cost function are usually utilized to study the general convergence properties of the method, such as asymptotic convergence and sublinear rate for some optimality measure, while lower bounds are used prove faster rates of convergence, e.g., linear convergence rates for the suboptimality gap.
One of the major advantages of the dual space preconditioning anisotropic gradient descent method compared to other frameworks of generalized smoothness is that the aforementioned lower bounds are well-studied. In our setting of smooth nonconvex optimization they take the form of the anisotropic gradient dominance condition from [24, Definition 5.6]:
Definition 2.3. We say that satisfies the anisotropic gradient dominance condition relative to Φ with constant 0 for all E I2"
6(Vo 2 -(f(x)-
(9)
The fact that this condition is generalization of the classical PI. inequality becomes evident when
choosing ø ||1 1|2 where (9) becomes [x)]] 2 =(f(=) - f.). Definition 2.3 holds for example when f is anisotropically strongly convex [24, Proposition 5.11], in parallel to the standard Euclidean setting where strong convexity implies the PL inequality. Therefore, in light of [24, Proposition 5.11] it holds when f is smooth relative to o² with constant ı i.e., when μ -0 f convex. Examples of functions f that satisfy Definition 2.3 relative to some Φ can be found in [24] and in [32, Section 4].
For the base method, linear convergence under this generalized PL condition was shown in [24, Theorem 5.7] and this result was further refined in [35, Lemma 6.7]. In this paper we manage to extend the aforementioned results, showing that Algorithm also converges linearly when is 2-subhomogeneous function [36, Theorem 3.7], i.e., 6(fx) I (zx(x) for all 0 E [0, 1] and E dom é. We provide examples of important E-suhhomogeneous reference functions as well as further discussion on the generalized PL condition in Appendix E.
Let Assumption 1.3 hold and f satisfy the anisotropic gradient dominance condition relative with constant μ. > O, where o is 2-subhomogeneous. Let, moreover, {x") kEN, be the sequence of iterates generated by Algorithm I with B E (0,0.5) and S +. Then, we have the following rate:
Theorem 2.4.
f(x*) f. S a (f(2²) f.). where a = max - 10
(10)
2.
In contrast to the proof of Theorem 2.2, in the proof of Theorem 2.4 utilize Lyapunov function that is monotonically decreasing along the sequence of iterates, given by Vi: = = ( - +f**)) f.. We further utilize the convexity and 2-subhomogeneity of Φ along with the anisotropic gradient dominance condition to show that Vi2 converges linearly and thus obtain the claimed result.
2.2 Convergence under preconditioned Lipschitz continuity
As already mentioned, one of the main difficulties in proving the convergence of Algorithm 1 comes from the fact that anisotropic smoothness is not equivalent to an upper bound on [ V=()) for IF R Intuitively, this is because the second-order condition for anisotropic smoothness (5) does not involve the spectral norm of the Hessian of f. as is for example the case for standard Lipschitz smoothness where [(x]]
I. or (To, L smooshnotsssss where [ < To L [x)]] Nevertheless, it involves the Jacobian matrix of the preconditioned gradient operator V ff and under some generally mild conditions, we can then obtain a bound of the form [VV(V* ot o fz)]] < L, which then implies global L-Lipschitz continuity of V ff. We call this condition preconditioned Lipschitz continuity and formally define it in the following assumption.
Assumption 2.5. For any x, Z E R² the following inequality holds with L as in Assumption 1.3:
V V (Vf(z)) - V (Vf(E)) & L| - El|.
(11)
Assumption 2.5 states that the preconditioned gradient is a Lipschitzian operator, hence the name preconditioned Lipschitz continuity. We remark that although more restrictive than anisotropic smoothness itself, this assumption is in fact mild since it holds for example for Lipschitz smooth

---

functions. Moreover, we show in the following proposition, it also holds for f E (RR")) that are (Lo. L1 --mooth for a suitable choice of the reference function Φ.
Proposition 2.6. Let C² (R") be (Lo, L1) smooth.. Then, f satisfies Assumption 2.5 for the reference function ((x)) tu (- -arl In(1 [(=l))) More precisely, the following inequality holds for all I, I :
V
$ - E|I.
(12)
Lo + [(|| Lo + 4 /(
To the best of our knowledge Proposition 2.6 also provides new characterization for (Lo, L))- smooth functions. Therefore, Assumption 2.5 is natural assumption that is at least as general as (Lo, L1 -smoooottsssss In fact, using arguments similar to those in Remark 1.4, we can show that is less restrictive than (Lo, L1) smooothness. We now turn to our main result regarding the convergence of Algorithm 1, where we allow 3 E (0,1)
Theorem 2.7. Let Assumptions 1.3 and 2.5 hold for Φ = h o Il Il Let, moreover, {ar (ke8o be the sequence of iterates generated by Algorithm I with /3 E (0. and 7 (1-3)² Then, we have the following rate:
f(x0)= - f. By 1- ol [VVoo
VV < K IERCK
min
(13)
Note that the proofs of Theorems 2.2, 2.4 and 2.7 are based mainly on the convexity of Φ and further utilize that e is even. We can obtain even better convergence guarantees by exploiting the strong convexity of Φ as well as the 2-subhomogeneity of important reference functions, but we decide to keep the analysis general enough and easier to follow.
3 The stochastic nonlinearly preconditioned gradient method
In this section we study a stochastic version of the base iterate (1). More precisely, we assume that we have access to stochastic first-order oracle which returns stochastic gradient g(x), similarly to [22. p. 114 Assumption 2]. The algorithm then takes the following form:
k+1 x (o(((((a)))
(14)
Throughout this section we assume that dom Φ = R.. The proofs are deferred to Appendix D.
Our first result describes the behavior of the method under noise condition that, demonstrate later on, is less restrictive than bounded variance of the stochastic gradients for many interesting reference functions é. Note that for now we do not assume that is unbiased estimator of V..
Theorem 3.1. Let Assumption 1.3 hold and E[o(V (VF()) - V (g(x))) I o². Let moreover
(o* JKEN be the sequence of iterates generated by (14) with stepsize & $ t. Then, the following holds:
K-1 Σ
(f(x9) - fa) +
E
((Vo'(
(15)
K
K
The assumption on the stochastic gradients in Theorem 3.1 might seem unintuitive upon first inspec- tion. Nevertheless, it follows naturally from the anisotropic smoothness condition, similarly to how the bounded variance assumption tailored Lipschitz smoothness. Moreover, we show in the next proposition, it is at least as general as the well-established bounded variance assumption for interesting reference functions é.
Proposition 3.2. Let be either Σn cosh(x;)) - or cosh([|=|])- 1. Then, the following inequality holds for all y. 7 E :
o(Vo"()) (v) V (π) 2 lly 0l
(16)
Therefore, if B(] - - x² we have that
B(((v((V(()) (o0()()))) [ < g²
(17)
7

---

1070
13.10
UP
Thiite
107d
Thilit Ice
10.
10/1
Roodi
Booeb
Roodb
17
Tol A4C2000
85
SGD
SGDn
1BCDs
3000
00
Epocas
Eporaa
Figure 1: Results for training an MLP on MNIST and ResNet-18 on Cifar10. Top row is the training loss and bottom row the test accuracy. (left) MNIST MLP (middle) Cifarl0 ResNet18 without momentum (right) C ResNet18 with momentum.
In the proof of Proposition 3.2 we show that there exist even tighter bounds between the two quantities. We next provide a simple example demonstrating that fact the noise assumption of Theorem 3.1 less restrictive than bounded variance.
2)²] with æ R. In this case have (z) 2(x 1), fz(x) 4(x + 2) and it is straightforward that |a| too also [[)f((x)) [+] becomes unbounded above. Nevertheless, choosing 6 = cosh -1 we have that 6(Ø" (f(()) o² (f((z))) is upper bounded for every sample i. It is also clear that the example considered here does satisfy the p-th bounded moment assumption (also known as heavy-tailed noise in the related literature) [15, Assumption 3J. Nevertheless, we are not aware if it is actually less restrictive assumption, since there does not seem to exist simple inequality that connects the two quantities.
Example 3.3. Consider the function f(x) -) +)2
-
Although the noise assumption in Theorem 3.1 follows naturally from the analysis of the algorithm, not clear whether we can prove the convergence of the method under it. Moreover, due to the nonlinear preconditioning of the proposed method in (14), the difference * - z² is not true estimator of Vø" f even when [xg())] = ff()), i.e. (VVo'(g(x)) & (Vf(()
similarly to the gradient clipping method [6, 20]. One way to reduce the potential bias introduced by the preconditioning when g a true estimator of f. is to increase the batch size. Utilizing thus Proposition 3.2, we obtain the following result.
Theorem 3.4. Let Assumption 1.3 hold for some o such that (16) holds and assume moreover that [x) (=)) < K for all x E R If we run (14 r K iteratioon with 7 S } we have
the following rate.
K- Σ k=0
1 (f((x)- ff) <
o²1 K 7 +
E
[VVo
{
(18)
K
2
The noise assumption in Theorem 3.4 corresponds to the case where the stochastic oracle is unbi- ased, has bounded variance and we run minibatch version of (14) with batch size K. Therefore, Theorem 3.4 describes convergence guarantees for the method under standard assumptions on the stochastic gradients and a generalized smoothness assumption that goes beyond Lipschitz smoothness for the cost function itself. Moreover, covers both isotropic reference functions (xx) h{[[==]] and separable ones > h((r;)) We emphasize the importance of this fact because for separable reference functions (14) takes the form of SGD with coordinate-wis stepsize that depends on the iterates, effectively complicating the analysis but also leading more interesting algorithms.

---

101
11P
337
10
10
OThe
AdDDaaad
IHCDs
6223 Strder Disalicss
20.0
500
1900
1206
2000
Nurder Stcrllies
Namtle Recalions
Figure 2: Results for the matrix factorization problem. The figure on the left corresponds to 10, the one in the middle to r 20 and the one on the right to r 30. be seen that our method, iHGDm, significantly outperforms the rest of the methods.
The following result describes the linear convergence of the method up to a constant under the generalized PL condition described in Definition 2.3.
Theorem 3.5. Let Assumption 1.3 hold, E[ ( o' (V
Vo*(g(=))) S o² and f satisfy the anisotropic gradient dominance condition relative to 6 with constant μ. Let moreover {a IKEN, be the sequence of iterates generated by (14) with stepsize Y S +. Then, the following holds:
0²
- -A) (1-))((
(19)
We remark that we have not provided a stochastic extension of the proposed method with momentum Algorithm 1. We believe that this would require specializing to reference functions with more favor- able properties and extending results from our stochastic analysis. We leave detailed investigation of this future research.
4 Experiments
In our experiments, we compare the proposed algorithms with baseline and state-of-the-art methods: stochastic gradient descent (SGD), SGD with momentum (SGDm), Adam [19], gradient descent (GD), gradient descent with momentum (GDm) and the heuristic accelerated variant of the adaptive gradient method from [33] (AdGD-accel) Our methods are versions of Algorithm I and (14) that are generated by cosh 1. The code for reproducing the experiments is publicly available?.
4.1 Neural networks
We first consider some neural network experiments. Here, implemented (14) and the stochastic version of Algorithm 1, while we used the standard PyTTrrch [38] implementations for SGD and Adam. Moreover, for Adam we used the standard momentum parameters. For all the methods used fixed stepsizes.
Image classification the MNIST dataset [9]. For first experiment we compare base method (14) with SGD and Adam on the standard classification problem on the MNIST dataset with the cross-entropy loss. We two-layer fully connected neural network with layer dimensions [28 28, 512, 256] and the ReLUU activation function and a batch size of 256. We tuned the stepsizes by performing adaptive gridsearch varied greatly across different seeds. The confidence intervals are obtained from five random seeds. The results are presented in the left column of Figure 1. It be seen that iHGD reaches small training losses fast and performs better than the rest of the methods.
seed and then decreasing the stepsize if the results
Image classification the Cifar10 dataset [21]. In this experiment [14] architecture and train it to classify images with the cross-entropy loss. We use batch size 128 for all methods.
the standard ResNet-18
We first compare the methods without momentum with SGD over five random seeds. The stepsizes are tuned using the same procedure as in the MNIST experiment. The results are presented in
Phttps://giie www///////ooon/aaiieaeooo
httppp///gtthhhb.ooomm////o//aa/ wwwpelliin--reeeeeee stoch

---

the middle column of Figure 1. We then compare the proposed methods with momentum with SGDm and Adam. We choose 3 0.9 for all methods which also the standard value for training residual networks with SGDm. We set the learning rate by performing parameter sweep over 0.1, {5. 1, 0.1, 0.05, 0.01, 0.005). The results of this experiment are presented in the right column of Figure 1. The confidence intervals for this experiment are obtained from three random seeds. It can be seen that our proposed methods perform similarly to SGD and SGDm which are known to be state-of-the-art for this problem.
4.2 Matrix factorization
We consider the matrix factorization problem as presented in [33]: Given matrix R=*" and r < min(m, n) we solve the following minimization problem.
min [U,]]= x
[(X) V) = = All
(20)
where E Rmxr and V E Rax and ||= denotes the Frobenius norm. important to note that this problem is not convex and also not (globally) Lipschitz smooth, since it is a multivariate polynomial of degree We use the Movielens 100K dataset [13] and values of r {10, 20,30). For r 10 and 20 we average the results over 10 random initializations, while for r = 30 over 3.
In this experiment we compare iHGDm with GD, GDm and AdGD-accel, which although is designed to tackle convex problems, performs very well on settings beyond convexity as remarked in [33]. For GD we use the same tuning as in [33], which guarantees convergence although the problem is not globally smooth as it involves quartic polynomials. For our method we use 8 = 0.9 and stepsize
y 2, but consider the method generated by x(x) X(cosh( (||= 1) with X 100, thus allowing for two stepsizes, similarly to [36]. It seems that the relation between these two stepsizes plays an important role for the fast convergence of the method. For GDm we use momentum parameter B = 0.9 and 7 1/300. This stepsize can be considered optimal since by doubling the stepsize can seen that iHGDm significantly outperforms the other methods, while it is more stable across the random initializations.
the method did not converge. The results are presented Figure
We provide more details about the implementation along with further experimental results in Ap- pendix F.
5 Conclusion and future work
In this paper we have analyzed extensions of the dual space preconditioning anisotropic gradient de- scent method. We introduced a preconditioned heavy ball-type algorithm and studied its convergence guarantees the general nonconvex setting and under a generalized PL condition. We moreover presented stochastic extension of the base method that we analyzed under both new and standard noise assumptions in the nonconvex setting. Finally, we tested the proposed methods and showed their good performance on various tasks from machine learning and optimization.
Interesting future work includes a unified analysis of the momentum algorithm Algorithm under relaxed assumptions on the reference function Φ as well as for any 3 E [0, 1). Moreover, extending the full proximal gradient-type algorithm from [24] to incorporate momentum is an important task with many potential applications, especially for constrained problems. For the stochastic algorithm, we believe that the analysis should focus on removing the dependence on the batch size and including momentum in the base method. We believe that such an endeavor would require building upon tools from martingale theory, such as obtaining generalizations of the standard concentration inequalities.
Acknowledgements
This work was supported by the Research Foundation Flanders (FWO) PhD grant 11A8T26N and research projects G081 18822, G033822N, GOA0920N; Research Council KUL grant C14/24/103.
The authors thank Emanuel Laude for the inspiration and helpful conversations.
10

---

References
[1] E. Balder. "An extension of suality-stability relations to nonconvex optimization problems".
In: SIAM Journal on Control and Optimization 15.2 (1977), pp. 329-343.
[2] H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2017.
[3] A. Bodard and P. Patrinos. Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning 2025, arXiv: 2509. 15817 [math. OC]. URL: https::/ pattps://ariv..
org/ aba/ 2509.. 15817.
[4] C. Bonet, T. Uscidda, A. David, P.-C. Aubin-Frankowski, and A. Korba. "Mirror and precondi- tioned gradient descent Wasserstein space". In: Advances in Neural Information Processing Systems 37 (2024), pp.
[5] H. Brézis. Functional analysis, Sobolev spaces and partial differential equations. Vol. 2. 3. Springer, 2011.
[6] X. Chen, S. Z. Wu, and M. Hong. "Understanding gradient clipping in private SGD: A geometric perspective". In: Advances in Neural Information Processing Systems 33 (2020), Pp. 13773-13782.
[7] Z. Chen, Y. Zhou, Y. Liang, and Lu. "Generalized-smoode nonconvex optimization is as efficient as smooth nonconvex optimization". In: International Conference on Machine Learning. PMLR. 2023, pp. 5396-5427.
[8] Cutkosky and H. Mehta. "High-probability bounds for non-convex stochastic optimization with heavy tails". In: Advances in Neural Information Processing Systems 34 (2021), pp. 4883- 4895.
[9] L. Deng. "The MNIST database of handwritten digit images for machine learning research [best of the web]". In: IEEE Signal Processing Magazine 29.6 (2012), pp. 141-142.
[10] S. Dolecki and Kurcyusz. "On (--coneextty extremal problems". In: SIAM Journal on Control and Optimization 16.2 (1 (1978), pp. 277-300.
[11] O. Gaash, K. Y. Levy, and Y. Carmon. Convergence clipped SGD convex (Lo, L smooth functions. 2025. arviv: 2502. 16492 [math. OC]. URL: https: /ttpxaaxvvv/////////////////aaaa org/ abs 2502. 16492.
[12] E. Gorbunov, N. Tupitsa, Choudhury, A. Aliev, Richtárik, S. Horváth, and Takáč. Methods for convex (Lp, Lm)-shooth optimization: Clipping, acceleration, and adaptivity. 2024. arXiv: 2409. 14989 [math. [C]. URL: https: / //ta///axxv org/ aa////////4// 14989.
[13] F. M. Harper and A. Konstan. "The MovieLens datasets: History and context". In: ACM Transactions Interactive Intelligent Systems (TiiS) 5.4 (2015), pp. 1-19.
[14] K. He, X. Zhang, S. Ren, and J. Sun. "Deep residual learning for image recognition". In: Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition. 2016,
pp. 770-778.
[15] F. Hübler, Fatkhullin, and N. He. "From gradient clipping to normalization for heavy tailed SGD". In: Proceedings of The 28th International Conference on Artificial Intelligence and Statistics. PMLR, 2025, pp. 2413-2421. URL: https: httpp:://ppoceette h/pp://edinoo/eeoeeeoo/oe///// mlr. press/v258/ hubler25a.Ne html.
[16] F. Hübler, Yang, X. Li, and N. He. "Parameter-agnoste optimization under relaxed smooth- ness". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2024, pp. 4861-4869.
[17] J. JJin, B. Zhang, H. Wang, and L. Wang. "Non-convex distributionally robust optimization: Non-asymptotic analysis". In: Advances in Neural Information Processing Systems 34 (2021), pp. 2771-2782.
[18] J. Kim, C. Park, A. Ozdaglar, Diakonikolas, and E. K. Ryu. Mirror duality in convex optimization. 2024. arXiv: 2311. 17296 [math. OC]. URL: https: //arxaavvvvv/////// org/ abs/
17296.
[19]
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. 2014. arXiv: 1412.6980
[cs LG]. URL: https: pttpps:/aaxxin //tpx/aivvv.////////////a///aarv wttpiii.rrrabbb////eeeae 6980.
[20] A. Koloskova, H. Hendrikx, and S. Stich. "Revisiting gradient clipping: Stochastic bias and tight convergence guarantees". In: International Conference Machine Learning. PMLR.
2023, pp. 17343-17363.

---

[21] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[22] G. Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
[23] E. Laude. "Lower envelopes and lifting for structured nonconvex optimization". PhD thesis. Technical University of Munich, 2021.
[24] E. Laude and P. Patrinos. "Anisotropic proximal gradient". In: Mathematical Programming
(2025), pp. 1-45.
[25] E. Laude and P. Patrinos. Anisotropic proximal point algorithm. 2024, arXiv: 2312, 09834 [math. OC]. URL: https: / atraarxivv..oo org/ /2122 09834. [26] E. Laude, A. Themelis, and Patrinos. "Dualities for non-Euclidean smoothness and strong convexity under the light of generalized conjugacy". In: SIAM Journal on Optimization 33.4
(2023), pp. 2721-2749.
[27] E. Laude, T. Wu, and D. Cremers. "Optimization of inf-convolution regularized nonconvex composite problems". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 547-556.
[28] F. Léger and P.-C. Frani-Frannowski. Gradient descent with a general cost. 2023. arXiv: 2305. 04917 [math. OC]. URL.: attps://aarsie .rgg wwt//bs///////eoooooooooo/e abs/2305. 00917.
[29] L. Liu, Y. Wang, and L. Zhang. Hrigh-probability bound for non-smooth non-convex stochastic optimization with heavy tails", In: International Conference on Machine Learning. PMLR.
2024, pp. 32122-32138.
[30] Z. Liu and Z. Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. 2025. arXiv: 2412. 19529 [math. [0]]. URL: https:
//arxiv.co www. htgg/ab//44/ 19529.
[31] H. Lu, R. M. Freund, and Y. Nesterov. "Relatively smooth convex optimization by first-order methods, and applications". In: SIAM Journal on Optimization 28.1 (2018). pp. 333-354. [32] C. J. Maddison, D. Paulin, Y. W. Teh, and A. Doucet. "Dual space preconditioning for gradient descent". In: SIAM Journal Optimization 31.1 (2021), pp. 991-1016.
[33] Y. Malitsky and K. Mishchenko. " "Adaptive gradient descent without descent". In: International Conference on Machine Learning. PMLR, 2020, pp. 6702-6712.
[34] P. Ochs, Y. Chen, T. Brox, and T. Pock. "iPiano: Inertial proximal algorithm for nonconvex optimization". In: SIAM Journal on Imaging Sciences 7.2 (2014), pp. 1388-1419.
splitting under the light of [35] K. Oikonomidis, E. Laude, and P. Patrinos. [math. [cth URL: https:///artt //axiv org/
generalized convexity. 2025. arXiv: 2503.18098 abs/2503 18098.
[36] K. Oikonomidis, J. Quan, E. Laude, and P. Patrinos. Nonlinearly preconditioned gradient methods under generalized smoothness. 2025. arXiv: 2502. 08532 [math. OC]. URL: https:
// //axxiv.oor wwrxxiiorr///ooo abs 2502.. 08532.
[37] D. E. Pallaschke and S. Rolewicz. Foundations of mathematical optinization: convex analysis without linearity. Vol. 388. Springer Science& & Business Media, 2013.
[38] A. Paszke et al. Automatic differentiation in PyTorch. 2017.
[39] T. Pethick, W. Xie, K. Antonakopooloss, 7.. 7hu, A. Silveti-Falls, and V. Cevher. Training deep learning models with norm-coonstrained LMOs. 2025. arXiv: 2502. 07529 [Cs. URL.: https: //apii////xvv...//// org/ hlgg/ab//2502.002
[40] T. Pethick, W. Xie, M. Erdogan, K. Antonakopoulos, T. Silveti-Falls, and V. Cevher. General- ized gradient norm clipping & non-Euclidean (Lo. L smmoohhness. 2025. arXiv: 2506.01913
URL: https: / atwpaaaivvvv...... www./ogg///////eeee/eoooeeee///e 01913.
[41] R. T. Rockafellar. "Higher derivatives of conjugate convex functions". In: Int. J. Applied
Analysis (1977), pp. 41-43.
[42] R. T. Rockafellar and R. J. Wets. Variational Analysis. New York: Springer, 1998.
[43] M.-E. Sfyraki and J.-K. Wang. Lions and muons: Optimization via stochastic Frank- Wolfe.
04192. [44] D. Vankov, A. Rodomanov, A. Nedich, L. Sankar, and S. U. Stich. Optimizing (To, I.)- smooth functions by gradient methods. 2025. arXiv: 2410. 10800 [math. OC]. URL: https:
2025. arXiv: 2506 04192 [math. .C]]. URL: https: / //t///xxivvvv//////////////aal//
// aaxiiv org/ abs/ (os//2 22400.2 10800.
[45] C. Villani. Optimal Transport: Old and New. Springer, 2008.
12

---

[46] Y. Yang, E. Tripp. Y. Sun, S. Zou, and Y. Zhou. Adaptive gradient normalization and indepen- dent sampling for (stochastic) generalized smooth optimization. 2025, arXiv: 2410. 14054 [math. OC]. URT: btttps//aarxte
org/abs/ aba/24b////10 14054.
[47] B. Zhang, J. Jin, C. Fang, and L. Wang. "Improved analysis of clipping algorithms for non- convex optimization". In: Advances in Neural Information Processing Systems 33 (2020),
Pp. 15511-15521
[48] J. Zhang, T. He. S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. 2020. aiv: 1905. 11881 [math. mmath.OC]. URL: https: // //axivv. org/ abs/ 1905 11881.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction reflect the paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss the related assumptions and limitations after stating our theoretical results.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide proofs for all of our theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the information needed to reproduce the main experimental results of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We provide the code needed for the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /Codeeuomiisseeeeeeee
/nips. wwtpccccpppcccaeccccccccccccccat / ssisssolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We provide details on the experiments we performed, including the problem formulations, datasets and the algorithms compared.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We present figures with error bars for our main experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide details on the computer resources required to perform our experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://rrs..cccppccieeeeeeeeeeee httpae///ehiscieeeeeeeeeeeeeee
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification; We introduce and study optimization algorithms that although could potentially have societal impact, we believe it does not have to be highlighted in the current paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We provide the credits for the assets use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA].
Justification: Our research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https http:/rips.ce/oooeeeeeeeeeeeeeee for what should or should be described.
cc/ cctc//o/mmerrrccee22////1//
20

---

A Φ-convexity and anisotropic smoothness
In this section describe the concept of @--conexity and discuss its connection anisotropic smoothness [24, Appendix A].
@-convexity basics. For the purpose of this paper, @-convexity can be considered as extension of the envelope representation of convex functions [42, Theorem 8.13] which states that a proper, Ise and convex function is the pointwise supremum of its affine supports. By replacing the affine supports with nonlinear ones, we obtain the definition of O -cconvexity for functions:
Definition A.1 (#-convex functions). Let X and Y be nonempty sets and X - coupling. Let f:X + R. We say that is Φ-convex on X if there is an index set I and paramelers (y,, (,) E Y x I for E I such that
f(z) = sup D( vi) - B,
(21)
iEI
For definition of d-convex sets, the interested reader can check [37, Section 1.4]. From (21) is clear that if Φ (), then f(z) suptez (z. vi) - 3g and we recover the class of proper, Isc and convex functions from [42, Theorem 8.13]. An important notion in the P-convexity framework is
that of ccconjuaacy, which generalizes standard convex conjugacy:
Definition A.2 (Ø-conjugate functions). Let X and Y be nonempty sets and + X + R coupling. Let f X + F. Then we define
f (v)
sup ((x,)) f(x), xe
(22)
as the d-conjugate of f on Y and
fb sup ((x,0) - (y).
(23)
NEY
as the ft-biconjugate back on X.
Once again it is clear that by choosing + = ( we retrieve the definition of convex conjugates [42, Equation 11]. Note that the @--biconjugate is defined back on X, similarly to how the convex
biconjugate is defined on E instead of F [5, p- 13]. Choosing $fr, y) 27 || - yll we get
sup xER
2イ || v/1 fxx = inf =E
f(x) + 2
yl
i... the P-conjugate is the negative Moreau envelope f. very important quantity in optimization theory [42, Definition 1.22]. Finally, we present the definition of the 4-subgradient which generalizes the notion of the standard convex subgradient:
Definition A.3 (f-subgradients). Let X and Y be nonempty sets and t X Y - R coupling.
Let f X R. Then we say that y is d-subgradient of f at ā if
f(x) 2 f()) 4((z, v) (
(24)
for all E X. We denote by Oz (ā) the of all subgrraddsstss of f at point T E X, which call the &- s-suuddiferential of f. When the @-subdiiferential is nonempty at some point T, we say that f is D-suabliferemtiaable at it and when it is everywhere nonempty, we say that f b-ssabiiffernntiable
From the definition above it is clear that a function has s-subbgrdiien at a point I. then also d-convex at this point. The opposite does not hold in general, as there exist dcconvex functions that have everywhere empty @-subdiifferentials [10].
Anisotropic smoothness. By choosing ( y) - + ((x y), the connection between anisotropic smoothness and de-onvexity can be made evident: the anisotropic descent incquality for f (4) is equivalent to the --subgradient inequality for - f. (24). From this equivalence it is also straightfor- ward that at any point x E R2,, ( (=) = {r (VF((((())) and thus the main iterate (1)
boils down to taking a d-subbradieet of ff at =
This connection to fb-convxxity actually leads to an interesting envelope representation of anisotropic smoothness. As discussed above, since- -f is d-suubdifferentiable, it is also &-convex, i.e.,
-f(x) sup te + * 6(x yi) - Bi,
21

---

meaning that
f(z) = inf iEI
o(x v/) + Bi.
Therefore, f is the pointwise infimum over a family of nonlinear functions, in parallel to standard Euclidean smoothness where is the infimum over convex quadratics, a fact that immediately follows from the Euclidean descent inequality. In that sense, anisotropic smoothness is natural generalization Euclidean smoothness, that as discussed in the main text, also less restrictive than (Lo, L1 -smoothness.. Moreover, the d d-convexity of -f implies that
o(x - u) (- - inf 1 * b(r - v) (-f) -f(x) = (-)) (x) = sup - +(x yER"
yER"
i.., that f can be written as the infimal-comvolution epi-addition [42, Equation 1(12)] between two functions.
The aforementioned envelope representation leads to important relations that, to the best of our knowledge, are absent other forms of generalized smoothness. To begin with, when f convex, in light of [24, Proposition 4. 1, anisotropic smoothness relative to é with constant L is equivalent to the convexity of f I
Φ²" I_-i with the latter being known in the literature as strong convexity of f" relative to o [31]. In this setting therefore, anisotropic smoothness and relative (Bregman) strong convexity form a conjugate duality, in parallel to the standard one between Lipschitz smoothness and strong convexity. Except for further highlighting the fact that anisotropic smoothness is natural generalization Lipschitz smoothness, this conjugate duality is very useful in obtaining convergence guarantees in the convex setting [36]. while the envelope representation is useful in providing calculus results for anisotropic smoothness [24, Section 4.2].
B Helper Lemmas and auxiliary results
Lemma B.I. Let (dg]KeN, be nonnegative sequence of reals that satisfies
8e+1 S (1 -a0) + 0
(25)
where 0 > 0 and a E (0, 2). Then,
8x S [1 a1* 80 1- 11 al
(26)
Proof. By using the fact that (1 - 0x) S 1 al5r and unrolling (25) we have that
k-1
& S - aa 6u +
Σ
alf S a1/660 + 1 - - 0K
i=0
where the second inequality follows by the fact that Σx= |1 - axl < Eie - -al' 1111-a]
since [1 al 1.
In our analysis we will also need the following standard result. We remind that 2-subhomogeneity means that (0xx) < (z)( for all 0 [0, and & E dom c.
Proposition B.2. Let & : R2n + R be convex and (00) = 0. Then, for constants X; 2 0 and (x:)d= E dom é, the following inequality holds long as X = Σd di S 1:
d
d
A:O(I;).
(27)
1=1
If. moreover, is 2-subhomogenesuus, then
d
AsT;
S
Arb(Tz).
(28)
1=1
22

---

Proof. The proof of the first statement follows immediately by the convexity inequality along with the fact that (0)) 0:
d
d
A53z
- (1- 1-0 + Σ Aet's
1 (1 (1--))((0)
+
Aeb(T:)) = Σ )x)(
Regarding the second statement, we have:
d =
d
Apti Σ
I
22
de Σ
X
oi
S
(x((1))
The first inequality follows by the definition of 2-subhomogeneiity since Di Xx; dom e and the second one by the convexity inequality.
We will also need an extension of the monotonicity property of anisotropic smoothness under episcaling [24, Proposition 4.8] to our setting where e is possibly of full domain.
Proposition B.3. Let f E C. (R"), L > I > 0 and x, E IR.", and suppose that
f(x) < f()) + 1 Ln f0
- Σ -
- 2, V
Then, it holds that
f(x) S [()+ x (
- * (V]
Therefore, if f has the anisotropic descent property relative to é with constant L1 > 0, then f has the anisotropic descent property relative to o for any L2 > Lt.
(+)) for ease of presentation. Note that if dom á R". then the statement follows from [24, Proposition 4.8).
Proof. We define the shorthand ū
Now fix any x, R" If L2(x= Σ) + & dom d, the statement holds vacuously. We first show that if L2(r 2) + dom Φ, then L1 (I z) + E dom Φ as well:
Consider E [o, 1]. Then, by convexity, t [[22 (x x) + ū) + (1 - t)ū E dom ø where we also used
that i E dom é by convex conjugacy. Choose t = L1 < and then we have
Lı T) + L1 ū + (1
L ju E dom Lg
L T) + ū E dom Φ.
Therefore, (z x) + ū & dom & the statement holds vacuously as well. Moreover, we have the following:
[L 2) + 11 -)) In 4))
( < Tue (z) La * - + La (0))
()((a)
where the incquality follows by convexity and the second equality by the definition of episcaling. The claimed result now follows by substituting the inequality above into the anisotropic descent inequality with constant L1.
C Proofs of Section 2
We define the shorthand * = Vó" Vo' (Vf(z*)) for ease of presentation.
23

---

C.1 Proof of Theorem 2.2
Proof. To set up our proof let us first unroll the recursion for m²:
m U (1 3)u²
m' 3(1 B) (1-B)au -B)u'
m² = (1 3)x² + B(1 - B)u² + (1 - 3)
m = (1 3)
3k kK
k'=0
Note that since 7 S 1 1
7 2 and we can use Proposition B.3 with constant 7
f(x - f(x²)
x²)) ) + u²) 70("") = f(x²) + rolu* m²) - 70(21 (2*)
where in the equality we have substituted the update rule for k Substituting the results of the recursion for m² we thus have:
[a s(x)) + ga Bu -1 (snt-(1 -33
gk wk vo(""))
k=11
Note now that the constants in front of wt and -uk inside the @ in the first line of the above display are 3 and (1 3* for 1. Moreover, we have that
k
B ++3
Σ (1- 33- = B - 82 + 1=1
3o +.. 8h - gh+ = -23 -23- -ght2 < 1,
since 8 < 0.5. Thus, we can apply (27) in the inequality above and obtain for k 2 1
f(a S f(x*) (0-(")" +1 3)
gk
o(un-k()
k=1
where we have also used the fact that á is even. Now let unroll this inequality in order make our logic clear, noting that for = we immediately obtain the result from the convexity inequality since the argument of á is just 3uc:
( - 1 3)0(u")
f(>3) f(()))())))))))
+((1 +((1))+-1--))))
3)3(((²)) - 7(1 -0(1-))o(u)
3)3((u))) f(x²) < f(2)) +1 (((1 ((1)))))() - 3))(2² -B)))))
up until iterate > Summing up the inequalities for k 0, .,.... K we thus have:
K
f( ((2 < f(x2)) - 7(1 (1- - -
Σ (1 3)(1 - B))(a²).
0=
where B = KK B¹. Now note that 8
1 -
I-B and thus 1 1 1-32 1 Using the fact
1-3
that & 2 0, we further obtain:
K
f( )(akt)) -7(1 - 1 -23) Σ )lut).
(29)
By rearranging and using f (x 2 Sa and 7 = 3. we have:
min ((u²) < L(J(x")
USkcK
a(K 1) 229)
which is exactly (8).
24

---

C.2 Proof of Theorem 2.4
To begin with, we define the Lyapunov function:
V = fo(m (1mmm-11) + f(x²)- f..
(30)
By convexity of Φ, the momentum update of Algorithm and the fact that u dom o m e dom ø (as convex combination of elements of dom Φ). we have that
vo(m") S 736(m= + 3))(1").
(31)
Now consider the anisotropic descent inequality between points æ² and x but with constant 2 L, from Proposition B.3:
[x s s(**) + 70(u² m²) 70(u²)
=s(a²) + 70(B(( m m) 700
where we have moreover used the update of m Utilizing (28) with A = 2B < and the fact that even we can further bound
f(**+1) S f(x²) + 2:32 ro("") 2,3 2mm -6o(m"))
(32)
Denoting Ps f(x²1) - f+ and summing (31) and (32) we have:
Pa+1 + (0(m") ) S Pk- + 7(3 + (m 1) - -B )o()))
Note that + and 3-233 2,3 by our choice of 0 < 3 < 0.5. From the anisotropic gradient dominance condition, we have that ø ) 2 μP= and thus
Pa+1 + vo(m") (1 (B 2,3 )m)) Pa (8 2 nm(m))))=)))
Since and PA 0 we further bound the r.h.s. by
V4+1 max{1 (3 - 228 ym 8 + 2
Iterating now this inequality we obtain the claimed result.
C.3 Proof of Proposition 2.6
To begin with, we prove the following more general result that we utilize later on:
Proposition C.1. Ler (V < L hold for all e R". Then, for all x, 2 E R":
Vo
L|x-
(33)
Proof. By the fundamental theorem of caleulus, for any x. E R
V' oa f() ((x- (2)))))0))))) z)dt
VΦ -
and as such
2 ( 1(x z))(z 3)d1
[ V + +1(r f(x (() t(x d))| #I
0
< -||=
where the second inequality follows by the assumption of the statement.
Now, regarding the proof of Proposition 2.6, note that since the spectral norm is submultiplicative, V (
(V
25

---

We have that 6(x) = Ln p(z) where p(x) == (|]=)|lIn(110))) and by standard convex conjugacy,
VΦ* (v/ h Since Vy*(y) = -I+|IT we thus have:
y
y
I1
Le + |M
Lo
La L2llll
Li
By simple calculations we then have
La
yy T 11v/|2
(2)
=
Lo ||y1|
I+
(llvll Le 2
L1
T1
La
|1lll]
||y/1
yy
Lo +
||9/1
[T,
+
+11y11)2
|1
Li
1
|8ll
3/3 T
La |M
|
The term multiplying
in the display above is therefore negative and as such Xmax (m²x(()) S La+bi Iill Clearly, & is positive semidefinite as the Hessian of a convex function and thus 2| (VI(()) S I++Zilva= By (Lo, -m)-mooohh we moreover have [>>]( S
yy Tly z
Li
Lo + f and thus
V (V L1.
Using now Proposition C.I completes our proof.
C.4 Proof of Theorem 2.7
We denote a == (1 - 3)² and start from the anisotropic descent inequality between points x² and k++ with constant + L. Proposition B.3:
1(a < s(x²) + ( x²t) + w² -00(1²)
= =(aa)) + rd(BBt Bm=-1) ((((1t)
(34)
Now, we work out the recursion for ek:
8 = :.n00
1 = Bu' 3(1 - Byu = B(u u0) + 3du
e² Bu Bm B(u² w + 2 u + 33
k-1
*k = 1
3k' - -1
Therefore, from the triangle inequality have that
| < gh+ |
8 k- -k-
< 1/
gh +1 T b x- -
+
= =
Σ
3 +1 aalaammmm --K- ||.
(35)
k--0
where we have used Assumption 2.5, the update of the algorithm and the fact that 7 L.
26

---

From convexity of á we moreover have
r0(m²) I 3ry0(m + (1 - 3))((2)))
Summing up (34) and the inequality above we obtain:
1( + v0(m²) f(x²) (y0(m==)) + (0(Ex) - 3y0(u*).
(36)
Now, since h o || we have x5**) II] and thus for all A: 2 we get from (35) and the fact that increasing that:
0(5*) S |
Σ
ge +
k'=0
S ( + a g +0 ((
dom h. Moreover, by definition, for any & E N, m² E dom ø as convex combination of elements of dom ø. Since, & h || || this implies that [|m'|] E dom h as well and thus all the points the r.h.s. of the first inequality belong in dom h. Furthermore, by our choice a, gh+1 + a Σi= 3 +1 < 1 and thus the second inequality follows from (27).
Regarding the second inequality, note that from [36, Lemma 1.3), || |h (II
Plugging this result back into (36) we obtain:
f( + >0(mm) $ f(a²) + 3yø(m - ;rØ(u²)
k-
tn gktl +
Σ #=
gk' gl' k(
We thus have:
[(x*) + x S [(x") = [(x") + (0)(0) - f(x") ) + B)d(m-1)
f(z²) + s (rdm))))(m)) + r + a3yø(m²) )yØ(u²)
{(=2) x S s(x²) + 330(mmm) + r + (37m(mm) rbbmm - 3y
up until K > O. Summing up these inequalities for k: = =0,.... O,..., K we obtain
k1) + Emmm) < f(x") + 3r
Σ 6(m 6(m 8y Σ s(a²)
k=
k=1
K
K k-1
+ vo(uO)
Σ
gh+l + ar
B +1 b(m
k=
and by rearranging
K
k-1
f(*k+1)+ Σ
( (1-Br))(m*)) ay Σ gh _ookmm)m
kmo
km
$1(0)) Bx + )Φ((1) Σ gk+1 ,34 o(w
further implying
K
(1) + ? Σ ((m
1 3 (x Σ
k=0
k¹
K < f(x0) 3) + 7
Σ
gk+1 - -37
Σ ((rt).
Rm
k
27

---

I-3 2 - 1-23--1-- + B 2 0 and thus the terms on Note that 1 3 - a K-k gk - -1 (1-))
83 and thus rearranging and using the hhs.s. are positive, since Φ 2 0. Moreover, Ex=1 gh+ 1 I-B f(**+1)= 2 f. we obtain:
1 (1(4))
- o(m*)
1 3
min ISKSK
((
K
By
and by dropping the negative term on the r.h.s. is the claimed result.
D Proofs of Section 3
D.1 Proof of Theorem 3.1
Proof. We start from the anisotropic descent inequality between points x² and x*+1, and note that,
since 7 S F, the inequality also holds with constant in light of Proposition B.3:
1(* - f(x*))++++)))))))) 7 o(x V" -
= f(x") (V (V ()((()))))) - (VV((V"((V(("")
(37)
where the equality follows by substituting the update (14). Taking conditional expectation obtain:
[[f(x*+1) x - f(x*) + 70 "V[Vo"
Taking total expectation and summing up the inequality above for k 0,...; 1, obtain
......K K
K-1
- - [Vo(Vo"( & / -f(=)))(((a** Bif(* o2 7 (f(=9)-f-)+
2=0
which then implies that
(V
< f(x9) - fx
E
7K + 0².
K
D.2 Proof of Proposition 3.2
Throughout the proof we will use the following facts about hyperbolic functions:
cosh(arsinh(a)) = v1 + a²
(38)
and
cosh(a aa b) cosh(a) cosh(b) - sinh(a) sin)())
(39)
Proof.
Case 1: ((x) Σi= cosh(x;)) Let y. y R" and note that (v) - (z)
Σ cosh(arsinh(ss) - arsinh();)) -
and thus we work with each individual summand. Therefore, will prove that for any a, b R, 1)2
cosh(arsinh(a)) arsinh(b)) - 1 < (a b)2. From (38) and (39) we have that
(ashiarsinh(o) arsinh(b)) / a² 1 ab.
Therefore, we need to show that
+ 02
ab 1 15 (a-
*V 1+ 22 < 3/2 + 2 +1
0² 2 o2b < tat + 4bt +1+ fa² + a² 1
- < 1a2-1199 183
28

---

which holds trivially. We thus have
1
1 11 g1 2
(Vo'ly) - (F6((7) -
y 2 i=1
8.2²
Case 2: d(z) = cosh | - 1. Note that (v) = arsinh ((ggss()))))) is a bijection from I" to IR" with inverse Vo(r) = sinh(||= )s)gn((())))) and the result holds true if the following equivalent inequality holds true:
((x σ) - / VQ(x)) Vo(T)l
V R".
In fact, we will show the tighter inequality
o(z Σ) + (6(z) -(())) - 1 1 v
(40)
2
Substituting the definition of Φ and V we equivalently have:
cosh(]|> - =1) - 1 + cosh([|=]1)² -
+ c)sh(1|=]])2
(x. .) ||
sinb([|=|]) -
2 sinh(]|=|))?
[
Using the hyperbolic identity cosh(a)² sinh(a)² = 1 we arrive at cosh(11æ - x [)) I cosh cosh sinh([|=|]) sinh (|=l)
(x, x) ||00||
|>|||
(z. [
Now we can parametrize the expression above by defining 0 ||
and
((0) = || - 2|| = / | + | - 2 =
To this end, we define the function [-1, TR by g(0) == cosh( ( | 1 | |||==|||=
cosh [| cosh [|=|]) sinh [==]]) sinh([|=)]] l)
for which we have that g( 1) g1) 0 by (39). By taking the second derivative we get
g0) || | 1 cosh(((O)
| | sinh(((O))
1(0)2
1(0)3
which is nonnegative by virtue of the inequality = cosh(2) - siinh()) 2 0 for all = E R.,. Therefore g(0) is convex, implying that g()) < for all E 1], which in turn implies the claimed result.
D.3 Proof of Theorem 3.4
Proof. Recall from (37) that since 2 L, it follows from Proposition B.3 that 1(a S f(x*) + (V(VVV (VI((())())) V - [V[[V
From (16) we have that
(V((V) Vo"( S // -
o²
2K
and the rest of the proof follows similarly to the proof of Theorem 3.1.
D.4 Proof of Theorem 3.5
Proof. Recall from (37) that since > L,, it follows from Proposition B.3 that
11x S f(x*) + ~ (Vf(=²)) V (g(x))) - (VVVo"VV(2"")
Using Definition 2.3, taking conditional expectation and utilizing the assumption on the noise of the stochastic gradient we obtain
E[[(**+1) .x* f(*)) 70² -)((((²)))) fx).
Rearranging and taking total expectations we thus arrive at
E[f(=*+1) - f.l < (1 7P) fa] +702
The claimed result now follows from Lemma 1 for 6n (xf f.] and 2
29

---

E The anisotropic gradient dominance condition and 2-subhomogeneity
In this section we provide a discussion on the anisotropic gradient dominance condition Definition 2.3 and provide examples of 2-subhomogeneous reference functions. To begin with, the relation of Definition 2.3 with the classical PL condition varies with the properties of the reference function Φ. This is captured in the following proposition.
Proposition E.1. Let Φ
R be as in Assumption 1.2 and let pa be the strong convexity R
parameter of Φ.
1. Then (VV' (v)) S
2pg 1lyl for all y E IR..
2. If. moreover, 6 is Lg -apiisschitz smooth, then (VVo 2 1 |1ll for all y E R 2Lg
Proof. To begin with, note that since & is μé Ha-strongly convex, o² -Lipschitz smooth. Moreover, since min @ 0, from [42, Theorem 11.8), 6* (0) = O. By the definition of the convex conjugate have o² (v) = (V (v): y) - (V)(()) and as such
o (v) (V o (v), (v) S 200 1lvl.
where the inequality follows from the descent lemma for o² between the points and y, and s (0) = O.
Now, regarding the second item, note that d= is stronglyy convex. From the strong convexity inequality we thus have
(0) のz (v) + V (v), -) ZLL llyl
for all y E R", The result now follows from the same arguments as the proof of the first item.
Therefore, for functions & that grow faster than ! ||==/1 the generalized PL inequality of Definition 2.3 is in fact stricter than the standard PL inequality. Nevertheless, when considering a local regime, one can translate bounds from one inequality to the other presented in the following example.
Example E.2. Let c(x) cosh(x) Then, for all (y, 3) E R" x 14_ such that ||y|| S 3 we have that
VI VI+ g2
v(Vo')y)) 2
1
g
V1+87 (2 for > straightforward that 8² I(B) = ((0) and that 3, are the only solutions of ((t) 0 in [0, 8]. Therefore, if we show that for some f (0, 3). ((t) we are done, since is continuous function. Choose 3/2 and note that
Proof. Consider the function ((1) 1
32-1
((3/2) =
Then, for the function 7(8) = V 1+
14,07
B 2 0, we have that i(0) = 0 and
i(3) = 3
> 0,
4 +1
V 82 +
implying that ((8) > 0 and thus that ((3/2) > 0. This finishes the proof.
We next move on to providing some examples of 2-subhomogeneous functions. To begin with, in light of [36, Lemma 3.8), cosh -1 is 2-subhomogeneous function. We moreover have the following new results:
Proposition F.3. The functions (a) -|ar In(1 (ool) and h2(x)) 1 /I x2 are subhomogeneous.
30

---

10
ClySGD
10
HIGD
sIGD
10
10
10a
10
10
3000
10000
15000
20000
Number of iteratioos
Figure 3: Results for the stochastic implementation of the phase retrieval problem (42),
Proof. For E [1,2] we want to show the following inequality:
(0x) S (x))
(41)
for all 0 E [0, and a E dom h4. The inequality holds with equality for A = 0 and 0 = 1, so we
study 0 E (0, 1). Now fix 0 (0, and consider the function (z) = h (f.z)) 6 (z)). We will show that h 0.
For h we have dom h1 = (-1,1) and since even we consider x E [0, 1). Clearly, in (0) - and thus if we show that h1 (z) S we are done. For x E [0, 1) and 0 E (0, 1). we have
(² - 1)x²
(xx = (x 1)( - 1)
Using 0 E (0, 1) yields (x) S for all x E [0, 1) implying that h a decreasing function and thus (x:) < h1 (0) = 0.
For h2(x) VI x² with similar reasoning as above we have
0r
[x(x)
x2 V1- (0x)²).
02
Clearly, since E (0.1), (x) < 0 and the proof follows similarly to the proof for h1
F Further experimental details
Experimental details
We provide further details on the experiments presented in Section 4. All neural networks experiments were carried out on an NVIDIA P100 GPU in an internal cluster. The experiment on the MNIST dataset requires less than 2 hours for each algorithm. For the ResNet-18 in the Cifar10 experiments, each run of each algorithm requires approximately hours. The matrix factorization experiments Intel Core 17-11700 @ 2.50GHz CPU and the total time required was less than hours.
The stepsizes used in the experiments of Subsection 4.1 are presented in Table 2.
Table 2: Stepsizes of the NN experiments in Section 4.
iHGD
sHGD
SGD
Adam
MNIST
1.0
0.40
0.56
0.001
Ci
0.2
0.35
0.10
Cifar 10 momentum
0.5
0.10
0.05
0.001
31

---

SGDa
75.0
Adian
72.5
1BGDm
Test arcutacy
Traiiin loss
#HGDm
70.0
10-1
07.5
SGDm
65.0
02.5
HHDDm
10
sHGDu
60.0
200
Epochs
Egoçaa
Figure 4: Results for training ResNet-34 on the Cifar100.
F.2
Additional experiments
F2.1
Nonconvex phase retrieval
In this experiment consider the phase retrieval problem
min f(x) = 2m Σ (v: (a. x;))
(42)
where ys and a; E R We consider an overparametrized problem, with r = 1000 m 300 and a, ~ (O, 0.5). zo ~ ~5(5 0.5) are generated element-wise with denoting the ground truth. The measurements are generated as y: = (a. 2)² with n. NN.0444) 42).
We compare the stochastic algorithm (14) generated by (a:) 1000 1000(cosh [|=|]) 1) and d2(2) 1000 > Et=1 (cosh(z;) - 1) with the stochastic clipped gradient method, as presented in [47] with O. We choose batch size of 50 and carefully tune the methods such that they perform well on 10 random problems. For iHGD we choose 7 1/45, for sHGD 7 1/44 and for the clipped gradient method 17 0.000023 and y 1 (in the notation of [47]). The results are presented in Figure 3. It can be seen that sHGD performs similarly to the clipped gradient method, while iHGD takes more iterations in the beginning but behaves similarly to the other methods towards the end.
F.2.2 Image classification on the Cifar100 dataset
In this experiment we use the ResNet-34 architecture and train it to classify images with the cross- entropy loss. We batch size 128 for all methods. We used stepsizes 0.1, 0.01, 0.001 respectively for iHGDm, sHGDm, SGDm and Adam. The results are presented in Figure 4. The confidence intervals for this experiment are obtained from three random seeds, while for each algorithm one run takes approximately 5 hours.
32


Reviews:
[{"review_id": "Ug6WAU4Xwm", "reviewer": "Reviewer_A43W", "summary": "The paper proposes nonlinearly pre-conditioned gradient methods (NPGMs) that combine the dual-space/anisotropic-descent framework with heavy-ball momentum and with a stochastic variant. It establishes global convergence bounds for the momentum version under anisotropic smoothness and shows a linear rate when a generalized PL condition holds. For the stochastic setting, the authors derive non-asymptotic rates under a novel noise assumption that subsumes bounded variance and prove linear convergence under generalized PL. Finally, they include experiments on MNIST/CIFAR-10 classification and matrix-factorization tasks.", "questions": "See weaknesses", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The paper is well structured and has a nice flow.\n2. They provide rigorous proofs for all stated theorems, and the assumptions are clearly presented. In particular, they both deterministic and stochastic analyses, including mini-batch dependence.\n3. The authors give the first convergence proof for heavy-ball momentum inside anisotropic preconditioning setting.\n\n**Weaknesses**\n1.  In the statement of Theorem 2.1 the authors make the restriction $\\beta<0.5$, limiting practical momentum choices (usually $\\beta=0.9$), however, they note this as an open question. \n2. The stochastic results (Section 3) cover only the base (no-momentum) method. Following the work from Section 2, one would expect results for the momentum-based method. After all, this is what practitioners usually deploy. \n3. Empirical accuracy gains over tuned SGD/Adam are modest on CIFAR-10; error bars overlap after 200 epochs.", "was_revised": true, "final_justification": "The authors have made an adequate job addressing my concerns. Therefore I maintain my initial rating of 4.", "rebuttal": "We thank the reviewer for their positive evaluation of our paper.\n\nIn the following we address the **Weaknesses** stated by the reviewer.\n\n> 1\\. In the statement of Theorem 2.1 the authors make the restriction $\\beta \\in [0, 0.5)$, limiting practical momentum choices (usually $\\beta = 0.9$), however, they note this as an open question.\n\nIndeed, Theorem 2.1 covers momentum parameters $\\beta \\in [0,0.5)$, a limitation that we acknowledge in our manuscript. Nevertheless, in Theorem 2.6 we provide convergence guarantees of the method for $\\beta \\in [0,1)$ under a condition that we show is more general than standard Lipschitz smoothness and is at least as general as $(L_0, L_1)$-smoothness. This condition can also be less restrictive than $(L_0, L_1)$-smoothness, when the Jacobian of $\\nabla \\phi^* \\circ \\nabla f$ is symmetric, following the discussion in lines 204-212. In that sense our result Theorem 2.6 is state-of-the-art, especially considering that it covers the whole family of algorithms described in Algorithm 1 and it does not require considering specific instances (e.g. normalized gradient) as is standard in the literature. Therefore, Theorem 2.1 describes an even broader result, since it holds under an even less restrictive condition, with the caveat that $\\beta \\in [0, 0.5)$.\n\n> 2\\. The stochastic results (Section 3) cover only the base (no-momentum) method. Following the work from Section 2, one would expect results for the momentum-based method. After all, this is what practitioners usually deploy.\n\nIn this paper we have indeed not studied the proposed algorithm with momentum in the stochastic setting. We believe that this is an important research direction that deserves separate work, especially when considering that our paper is the first that studies the momentum extension and the stochastic version of the base method in the general nonlinearly preconditioned gradient framework.\n\n> 3\\. Empirical accuracy gains over tuned SGD/Adam are modest on CIFAR-10; error bars overlap after 200 epochs.\n\nIn our experiments we have focused on the algorithms generated by $\\phi(x) = \\cosh(\\|x\\|)-1$ and $\\phi(x)=\\sum_{i=1}^n \\cosh(x_i)-1$ (called HGD) which we find interesting because they behave in a way that is between standard GD and gradient clipping. This intermediate behavior is especially clear in one dimension, where it can be illustrated by plotting the preconditioner $\\sinh^{-1}(y)$. In that sense, the aim of our experimental section is to show that it keeps the best of both worlds in that it performs similarly to or even better than state-of-the-art methods in a variety of problems including NN training, while at the same time having stronger theoretical guarantees than GD. Therefore, HGD is a robust solver that can tackle a variety of problems, supported by theoretical guarantees that extend beyond the usual Lipschitz smoothness assumptions."}, {"review_id": "2FBgIFEVwL", "reviewer": "Reviewer_VEKm", "summary": "This paper proposes a nonlinearly preconditioned heavy-ball-type algorithm and provides its convergence guarantees in the general nonconvex setting and under a generalized PL condition. It also presents a stochastic variant and analyzes its convergence behavior under both new and standard noise assumptions. Finally, it tests the proposed methods and shows their good performance on various tasks, including neural network training and matrix factorization.", "questions": "1. It is better to explain sigmoid preconditioners in the main text.\n2. Is there any relationship between the so-called Hyperbolic Gradient Descent with the gradient descent in hyperbolic space [1]?\n3. Is it better to use $\\cosh(\\cdot)-1$ instead of $\\cosh-1$?\n4. To obtain the next iterate, Equation (2) is minimized over what?\n5. Define $\\delta_{\\{0\\}}(x)$ in Line 103\n6. Define $\\text{rge}$ in Equation (3)\n7. It is better to give the formulation of the stochastic optimization problem at the beginning of Section 3.\n8. What about the numerical performances of algorithms induced by other reference functions?\n9. Is it possible to include numerical experiments on PL-type functions?\n---\n[1] Wilson, B., & Leimeister, M. (2018). Gradient descent in hyperbolic space. arXiv preprint arXiv:1805.08207.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. This paper extends the nonlinearly preconditioned gradient descent method by incorporating a momentum term and studies the convergence behavior under different conditions.\n\n2. This paper also proposes a stochastic variant of the base method and analyzes it under different noise assumptions.\n\n3. The numerical experiments consider two different applications and show the good performance of the proposed methods.\n\n**Weaknesses**\n1. Some concepts are used without any explanations, such as $\\Phi$-convexity. It may be better to give a brief introduction in the appendix.\n\n2. It is better to compare the standard convergence analysis of gradient clipping under the $(L_0, L_1)$-smooth condition and the one under this anisotropic smoothness. For example, does the paper obtain a stronger result in the stochastic setting? Does the analysis become simpler? Are the assumptions weaker? I think the current manuscript lacks a discussion on this aspect.", "was_revised": true, "final_justification": "I believe the authors have addressed all my concerns. They are also committed to incorporating several discussions into the revised manuscript.", "rebuttal": "We appreciate the reviewer’s time and effort in providing feedback and their acknowledgement of our papers' novelty, quality and clarity.\n\nIn the following we address the **Weaknesses** stated by the reviewer.\n> 1\\. Some concepts are used without any explanations, such as $\\Phi$-convexity. It may be better to give a brief introduction in the appendix.\n\nWe would like to thank the reviewer for their suggestion. Indeed, we will provide additional details on the important concept of $\\Phi$-convexity in a revised version of the manuscript. \n\n> 2\\. It is better to compare the standard convergence analysis of gradient clipping under the $(L_0, L_1)$-smooth condition and the one under this anisotropic smoothness. For example, does the paper obtain a stronger result in the stochastic setting? Does the analysis become simpler? Are the assumptions weaker? I think the current manuscript lacks a discussion on this aspect.\n\nWe would like to stress that although there exist connections between the two notions of smoothness, they are not equivalent and thus directly comparing the analysis of the methods is not straightforward.\n\n> Are the assumptions weaker?\n\nFrom [1, Proposition 2.9] we know that anisotropic smoothness encompasses a class of functions that is wider than that of $(L_0, L_1)$-smooth functions. In other words, anisotropic smoothness is a **weaker assumption** than $(L_0, L_1)$-smoothness. To better see this, note that for $\\phi(x)= -L_0/L_1 (-\\\\|x\\\\|-\\ln(1-\\\\|x\\\\|))$, the second-order sufficient condition for anisotropic smoothness from [1, Definition 2.4] takes the following form:\n$$\n\\nabla^2 f(x) \\prec ( L_0 +  L_1\\\\|\\nabla f(x)\\\\|)I + \\left( L_1 + \\frac{ L_1^2}{L_0} \\\\|\\nabla f(x)\\\\|\\right) \\frac{\\nabla f(x)\\nabla f(x)^\\top}{\\\\|\\nabla f(x)\\\\|},\n$$\nwhile for $(L_0, L_1)$-smoothness it is $\\\\|\\nabla^2 f(x)\\\\|\\leq L_0 + L_1\\\\|\\nabla f(x)\\\\|$.\nTherefore, we can see that this second-order sufficient condition 1) does not require lower bounds on the eigenvalues of $\\nabla^2 f(x)$ and 2) can be less restrictive than the one for $(L_0, L_1)$-smoothness stated above. Some simple examples of functions that are anisotropically smooth but not $(L_0, L_1)$ include $1-\\sqrt{1-x^2}$, $\\exp(x^2)$, $-|x|-\\ln(1-|x|)$ (by choosing as $\\phi$ the function itself). It is also important to note that our preconditioned Lipschitz continuity Assumption 2.4 is at least as general as $(L_0, L_1)$-smoothness and can be even less restrictive when the Jacobian of $\\nabla \\phi^* \\circ \\nabla f$ is symmetric, following the discussion on lines 204-212 of the manuscript. \n\nWe remark that another advantage of the anisotropic smoothness framework is that it can better describe the functions that are between Lipschitz smoothness and $(L_0, L_1)$-smoothness in that it generates tighter upper bounds. For further details please see our reply to reviewer tUyH.\n\n> Does the analysis become simpler?\n\nOur analysis covers a whole family of algorithms (parameterized by the reference function $\\phi$) under a very general condition and can thus be considered simpler, since it does not require further effort for every specific instance of the algorithm and the corresponding descent inequality, as is standard in the related literature. Moreover, it is illuminating in that it links the choice of the preconditioner (and thus algorithm) with the function class of the cost function.\n\n> Does the paper obtain a stronger result in the stochastic setting?\n\nIn the stochastic setting we obtain standard convergence guarantees for this type of methods (without some variance reduction technique) [3, Section 4.1], but under a different condition.\n\nWe aim to add a discussion on this subject in a revised version of the manuscript.\n\nIn what follows we answer the **Questions** asked by the reviewer.\t\n\n1. We thank the reviewer for their suggestion, we will include some discussion on the sigmoid shape of the preconditioners in the main text.\n2. We are not aware of any relationship between HGD and gradient descent in hyperbolic space. However, the general update described in (1) is connected to works from the geometry of optimal transport literature [4, 5]. \n3. Thank you for the suggestion, we will replace $\\cosh-1$ with $\\cosh(\\cdot)-1$.\n4. The main iterate is generated by minimizing the r.h.s. of the inequality (2) over $x$. We will specify this in the manuscript.\n5. We will include the suggested changes in a revision.\n6. We will include the suggested changes in a revision.\n7. We will include the suggested changes in a revision.\n8. In our paper we focus mostly on the algorithms generated by $h(x) =\\cosh(x)-1$, since their behavior is between that of plain GD and gradient clipping (see also the response to reviewer A43W). We did not provide experiments with reference functions that have bounded domains, since they perform some form of gradient clipping for which there already exists a rich literature.\n9. We believe that in order for such experiments to be meaningful, the algorithms should be applied with the correct stepsize obtained by the theory. For that reason we have left such a project for future work. Nevertheless a toy experiment is presented in our reply to reviewer tUyH, where the function satisfies the generalized PL inequality along the sequence of iterates.\n\nWe believe that we have addressed all the reviewer's concerns and weaknesses, and we kindly ask the reviewer to reevaluate their rating.\n\n---\n**References:**\n\n[1] Oikonomidis, Konstantinos, et al. \"Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness.\" ICML (2025).\n\n[2] Laude, Emanuel, and Panagiotis Patrinos. \"Anisotropic proximal gradient.\" Mathematical Programming (2025): 1-45.\n\n[3] Lu, Haihao, Robert M. Freund, and Yurii Nesterov. \"Relatively smooth convex optimization by first-order methods, and applications.\" SIAM Journal on Optimization 28.1 (2018): 333-354.\n\n[4] Gangbo, Wilfrid, and Robert J. McCann. \"The geometry of optimal transportation.\" (1996): 113-161.\n\n[5] Figalli, Alessio, Young-Heon Kim, and Robert J. McCann. \"When is multidimensional screening a convex program?.\" Journal of Economic Theory 146.2 (2011): 454-478."}, {"review_id": "sq4WJiiZCp", "reviewer": "Reviewer_28hb", "summary": "This paper presents a theoretically rigorous and practically motivated study of nonlinearly preconditioned gradient methods (NPGMs), specifically extending them with momentum (m-NPGM) and developing a stochastic variant. The paper analyzes convergence under anisotropic smoothness, a generalization of Lipschitz smoothness, and establishes novel results under generalized PL conditions and (L0, L1)-smoothness. It also provides empirical comparisons on deep learning and matrix factorization tasks.", "questions": "see above", "limitations": "see above", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: 1) Theory: This work introduces a novel heavy-ball extension of nonlinear preconditioning methods with provable convergence guarantees in the general nonconvex setting under a generalized PL condition. This is the first result regarding the convergence of the method with momentum under anisotropic smoothness conditions.\n2) Assumption and setting: the analysis is established under anisotropic smoothness and preconditioned Lipschitz conditions, which cover many applications. In particular, the analysis is a non-trivial extension of the previous work due to the particular structure of the anisotropic descent inequality and the lack of global upper bounds for the gradient difference term. Therefore, the techniques developed here have the potential to be applied to develop and analyze other algorithms in this setting.  \n\nWeakness: The presentation of the content lacks details. All the main results are presented right after the assumptions/conditions, without any elaboration on the proof sketch and technical novelty. The paper discusses a variety of settings, but could focus on one or two of them to further elaborate the technical details. The experimental section could be strengthened with ablation on choice of reference function and effect of momentum coefficient on convergence, etc.", "was_revised": true, "final_justification": "I want to thank the authors for providing the response. I am satisfied with the response and have raised the rating to 4.", "rebuttal": "We appreciate the reviewer’s time and effort in providing feedback.\n\nIn the following we address the **Weaknesses** stated by the reviewer.\n\n> The presentation of the content lacks details. All the main results are presented right after the assumptions/conditions, without any elaboration on the proof sketch and technical novelty. The paper discusses a variety of settings, but could focus on one or two of them to further elaborate the technical details. \n\nWe appreciate any feedback on the presentation of our work. However, in this case the comment feels unjustified, as we motivate below.\n\nOne of our main theorems is Theorem 2.1 and the three paragraphs that follow it are dedicated to discussing both the difficulties of the setting that we study and its limitations. Then, we present the generalized PL condition and briefly explain it in one paragraph, but we provide additional details on it and further study its relation to the classical PL condition in Appendix D. We do not discuss the difficulty of the setting after Theorem 2.3, since this is similar to Theorem 2.1.\n\nWe then move on to establishing the preconditioned Lipschitz continuity assumption, which we state after an introductory paragraph. Following the statement of the assumption we show that it holds for Lipschitz smooth functions and even for $(L_0,L_1)$-smooth ones, thus showcasing its generality and applicablity. Then, we state our convergence theorem under this new assumption. We do not provide a discussion after this statement due to spacing constraints, but our proofs are presented in full detail in the appendix.\n\nRegarding Section 3, we present it in a way such that the main convergence result Theorem 3.4 follows naturally. The logic of the presentation is as follows: we first show in Theorem 3.1 the convergence of the method up to $\\sigma^2$ under a new noise assumption. Then, in Proposition 3.2 we show that this noise assumption is actually implied by the standard bounded variance assumption and in Example 3.3 we provide an example where the bounded variance assumption fails and our noise assumption holds. Following that we provide the convergence result Theorem 3.4 where we assume bounded variance and that we have access to a minibatch oracle. Finally, we discuss the limitations and advantages of our approach.\n\nIn general, we agree that in some places of the manuscript we could provide more details and the page limit constraint is the main reason we have not done so. Nevertheless, we do not believe that this is a valid reason to reject the paper.\n\n> The experimental section could be strengthened with ablation on choice of reference function and effect of momentum coefficient on convergence, etc.\n\nRegarding the choice of preconditioner in our experiments, please see our comment on weakness 3 stated by reviewer A43W. As for the ablation study on the momentum parameter, we consider this an interesting research direction, as the current paper primarily focuses on theoretical analysis.\n\nWe believe that we have addressed all the reviewer's concerns and weaknesses in our paper, and we kindly ask the reviewer to reevaluate their rating."}, {"review_id": "eqjWHE4zGg", "reviewer": "Reviewer_QeMc", "summary": "This paper investigates smooth noncovnex optimization problem using anisotropic gradient descent (GD) method & its extensions. They combine the notion of momentum with nonlinear preconditioned GD & propose a Heavy-Ball (HB)-type method with a convergence rate of $\\mathcal{O}(L/K)$ for a strongly convex reference function $\\phi$ & $f$ being anisotropically smooth relative to $\\phi$ (a notion that was proposed by previous works). Later, they extend their convergence result to the scenario when $f$ satisfies a generalized PL inequality and $\\phi$ is 2-subhomogenous. Additionally, they study their method for functions that satisfy a preconditioned-smoothness assumption which contains $(L_0-L_1)$-smoothness as a special case. A convergence analysis of the stochastic preconditioned GD method under a more general noise assumptions revealed that the convergence is not guaranteed without variance reduction techniques (like increasing batch sizes). Numerical experiments revealed competetive behaviour of the proposed method.", "questions": "First, thank you for your efforts.\n\n1- In line 117 it is mentioned that this work mainly focuses on strongly convex reference functions. Then they propose some examples. What are other examples of strongly convex reference functions?\n\n2- Did you ensure that all the methods in your simulations are compaired fairly in terms of the choice of the step-sizes? I'm mainly referring to the neural network simulations where the step-size was chosen through sweeping on $\\{1,0.1,0.01\\}$.\n\n3- Why ADAM was not compared in the training on CIFAR10 ResNet18 experiment with momentum?\n\n4- Do you think it would be possible to extend these results to the constrained optimization?\n\nThanks!", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1- The problem is well-motivated. Although, the gradient clipping method is more explored and studied in the literature, its general form (1) is less attended. This is the general motivation in this work. (Lines 42-54)\n\n2- The contribution is good. To further study the general form of nonlinear preconditioned GD, they propose an HB-type method with its convergence analysis under the assumptions of anisotropic smooth relative to $\\phi$ (lines 155-156 theorem 2.1), a generalized PL inequality where $\\phi$ is 2-subhomogenous (lines 197-201 theorem 2.3), and a preconditioned Lipschitz continuity (lines 225-228 theorem 2.6) . A stochastic extension is also studied (for the first time as the authors claim) under a slightly more general noise assumption (lines 241-243 theorem 3.1). Additionally, they show that if the mini-batch size increase (classical approach to reduce the variance estimation error), the true convergence is possible in theorem 3.4.\n\n\n**Weaknesses**\n\n1- The writing could improve, sometimes the reader might feel lost or diconnected. Adding a bit more coherency might help with this (this point exists throughout the whole paper. Examples are Paragraph on line 22 is incoherent with the previous paragraph, paragraph on line 203 hard to read sentence on line 207).\n\n2- ADAM is a momentum-based algorithm, however it was not compared in the Numerical simulations (Figure 1, right).", "was_revised": true, "final_justification": "After reading all the comments, I decide to raise my score to 5 as I see clear positive responses from other reviewers who responsed. The authors have clearly addressed my concerns regarding their simulation results. Due to comparative novelty aspects existing in NeurIPS, I do not raise my score to 6 as this work is developing on the same line of prior works like reference [30]. However, still they bring valuable results as mentioned in the \"Strengths\" section of my initial comment.", "rebuttal": "We thank the reviewer for their positive evaluation of our paper, and we appreciate their recognition of the significance of our work.\n\nIn the following we address the **Weaknesses** stated by the reviewer.\n\n> 1\\. The writing could improve, sometimes the reader might feel lost or diconnected. Adding a bit more coherency might help with this (this point exists throughout the whole paper. Examples are Paragraph on line 22 is incoherent with the previous paragraph, paragraph on line 203 hard to read sentence on line 207).\n\nWe acknowledge that our writing could improve at places in the manuscript. We will refine the writing by simplifying the language and providing additional details.\n\n> 2\\. ADAM is a momentum-based algorithm, however it was not compared in the Numerical simulations (Figure 1, right).\n\nWe did not include Adam in Figure 1 (right) because this experiment is the same (Resnet18 on the Cifar10 dataset) as the one shown in Figure 1 (center), where Adam is already included. We aimed to avoid overcrowding the image on the right.\n\nIn what follows we answer the **Questions** asked by the reviewer.\n\n> 1\\. In line 117 it is mentioned that this work mainly focuses on strongly convex reference functions. Then they propose some examples. What are other examples of strongly convex reference functions?\n\nThere are many interesting strongly convex reference functions. In order to avoid repetition we only present the 1d kernel functions $h$ that generate $\\phi$, along with the corresponding preconditioner ${h^*}'$, in the following table:\n| $h(x)$                                              | ${h^*}'(y)$                        |\n|-----------------------------------------------------|------------------------------------|\n| $\\exp(\\|x\\|)-\\|x\\|-1$                               | $\\ln(1+\\|y\\|)\\text{sgn}(y)$        |\n| $1-\\sqrt{1-x^2}$                                    | $\\frac{y}{\\sqrt{1+y^2}}$           |\n| $\\frac{1}{2}x^2 + \\delta_{[-1,1]}(x)$               | $\\text{min}(1, \\text{max}(-1, y))$ |\n| $x \\text{arctanh(x)}-\\ln(\\cosh(\\text{arctanh(x)}))$ | $\\tanh(y)$                         |\n| $-\\frac{2}{\\pi}\\log(\\cos(\\frac{\\pi x}{2}))$                 | $\\frac{2}{\\pi}\\text{arctan(y)}$    |\n\nWe remark that the second and third reference functions lead to a simplified version of Adagrad and the gradient clipping algorithm respectively through [1, Examples 1.5 & 1.7].\n\n> 2\\. Did you ensure that all the methods in your simulations are compaired fairly in terms of the choice of the step-sizes? I'm mainly referring to the neural network simulations where the step-size was chosen through sweeping on $1, 0.1, 0.01$.\n\nIn order to clear possible confusion we remark that except for the experiment with momentum, in all the other ΝΝ experiments we tuned the methods via an adaptive gridsearch. We did not use the same gridsearch for the experiment with momentum to lower the computational cost, since SGDm achieves state-of-the-art performance with these parameters.\n\n> 3\\. Why ADAM was not compared in the training on CIFAR10 ResNet18 experiment with momentum?\n\nPlease see our comment on the second weakness.\n\n> 4\\. Do you think it would be possible to extend these results to the constrained optimization?\n\nIndeed, we believe that an extension to the constrained case is certainly possible and is interesting future work. We remark that another advantage of the anisotropic smoothness framework that we study is that it has a natural proximal extension for additive nonsmooth problems [2].\n\n---\n**References:**\n\n[1] Oikonomidis, Konstantinos, et al. \"Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness.\" ICML (2025).\n\n[2] Laude, Emanuel, and Panagiotis Patrinos. \"Anisotropic proximal gradient.\" Mathematical Programming (2025): 1-45."}, {"review_id": "TwXhQo8aaH", "reviewer": "Reviewer_tUyH", "summary": "This paper considers preconditioned gradient methods for nonconvex optimization problems under the generalized smoothness condition. It first introduces preconditioned gradient descent with momentum when the full gradient is available. In addition, the authors propose a stochastic variant of the preconditioned gradient descent method and study its convergence guarantee.", "questions": "1. With an appropriate choice of the reference function $\\phi$, anisotropic smoothness is equivalent to $(L_0, L_1)$-smoothness. The $(L_0, L_1)$-smoothness framework already encompasses a wide range of machine learning applications. Therefore, a key concern is the significance of further generalizing from $(L_0, L_1)$-smoothness to anisotropic smoothness in the context of machine learning. Specifically, I would like to know which machine learning applications fall within the class of anisotropically smooth functions but not within the class of $(L_0, L_1)$-smooth functions.", "limitations": "The theoretical guarantees for the stochastic variants of preconditioned gradient descent appear to be limited, as highlighted in Weaknesses (2) and (3).", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n* Extension of the preconditioned gradient descent to the stochastic setting is an interesting topic to explore.\n* The authors provide a rigorous theoretical analysis of the proposed methods. \n* This paper presents empirical evidence to demonstrate the effectiveness of the proposed methods.\n\nWeakness:\n\n* The authors do not provide a comparison of the convergence rates of the proposed methods with existing approaches under the generalized smoothness setting. The theoretical advantages of the proposed methods over existing approaches are not clearly articulated.\n\n* In Theorem 3.1, the R.H.S. of (15) has a non-vanishing term of $\\sigma^2$, which implies that the proposed stochastic preconditioned gradient descent cannot have exact convergence to the stationary point.\n\n* In Theorem 3.4, the choice of batch size is too large. To obtain $\\epsilon$-stationary point, one needs to choose a batch size $K = 1/ \\epsilon$, which is impractical for large-scale machine learning applications.", "was_revised": true, "final_justification": "The author addressed my concerns. I am satisfied with their response.", "rebuttal": "We appreciate the reviewer’s time and effort in providing feedback.\n\nIn the following we address the **Weaknesses** stated by the reviewer.\n\n> The authors do not provide a comparison of the convergence rates of the proposed methods with existing approaches under the generalized smoothness setting. The theoretical advantages of the proposed methods over existing approaches are not clearly articulated.\n\nWe would like to stress that the notion of smoothness that we work with in this paper is different from that of other papers in the generalized smoothness framework. Therefore it is not straightforward to compare the obtained convergence rates except for specific cost functions. Nevertheless, a major advantage of our work is that it provides a unified analysis for a family of algorithms, thus eliminating the need to produce new results for every different setting.\n\n> In Theorem 3.1, the R.H.S. of (15) has a non-vanishing term of $\\sigma^2$, which implies that the proposed stochastic preconditioned gradient descent cannot have exact convergence to the stationary point.\n\nIndeed, in Theorem 3.1 we show convergence up to $\\sigma^2$ under a new noise assumption that is less restrictive than bounded variance and when the stochastic estimator is potentially biased. We believe that this is an interesting standalone result (such as [3, Section 4.1]), but it also helps provide some insight on our main result, Theorem 3.4 (see also our reply to reviewer 28hb).\n\n> In Theorem 3.4, the choice of batch size is too large. To obtain $\\epsilon$-stationary point, one needs to choose a batch size $K=1/\\epsilon$, which is impractical for large-scale machine learning applications.\n\nTheorem 3.4 requires large batch sizes to obtain convergence up to $\\epsilon$, which to the best of our knowledge is standard for all clipping-type methods under (generalized) smoothness that do not utilize some variance reduction technique or momentum (see [1, Section 3.1], [2, Section 2], [3, Section 4.1]). Using such a technique to remove the need for a large batch size, possibly under a weaker noise assumption, is an important research direction that we believe deserves separate work.\n\nIn what follows we answer the **Question** asked by the reviewer.\n\n> 1\\. With an appropriate choice of the reference function $\\phi$, anisotropic smoothness is equivalent to $(L_0, L_1)$-smoothness. The $(L_0, L_1)$-smoothness framework already encompasses a wide range of machine learning applications. Therefore, a key concern is the significance of further generalizing from $(L_0, L_1)$-smoothness to anisotropic smoothness in the context of machine learning. Specifically, I would like to know which machine learning applications fall within the class of anisotropically smooth functions but not within the class of $(L_0, L_1)$-smooth functions.\n\nWe would like to stress that although a $\\mathcal{C}^2$ function that is $(L_0, L_1)$-smooth is also anisotropically smooth relative to a suitably chosen reference function, the corresponding descent inequalities are in general not equivalent. In fact for this specific $\\phi$, anisotropic smoothness is **less restrictive** than $(L_0, L_1)$-smoothness, as we detail in our answer to reviewer VEKm. Moreover, to the best of our knowledge, although $(L_0, L_1)$-smoothness has been shown **empirically** to better describe some machine learning applications, proving these empirical findings remains an open question.\n\nRegarding the significance of anisotropic smoothness as a notion of generalized smoothness, we would like to stress that as we state in the introduction (lines 42-46) our goal is not only to obtain the most general descent inequality but also to fit the best one to the cost function at hand. From a majorization-minimization perspective we want to find a tight model of the cost function in order to obtain faster algorithms that do not require additional tuning. Therefore, similarly to how $L$-smooth functions also belong to the class of $(L_0, L_1)$-smooth functions (for $L_1 \\geq 0$), but the standard approach to minimizing them is standard GD with stepsize $1/L$, there exist functions that are both anisotropically smooth and $(L_0, L_1)$-smooth, but the anisotropic descent inequality describes a tighter model and thus the best approach is the nonlinearly preconditioned gradient method. We next provide some simple examples of 1d functions that are provably anisotropically and $(L_0, L_1)$-smooth, to better motivate this.\n* The function $f(x) = \\cosh(x-a)$ is both anisotropically and $(L_0, L_1)$-smooth, but the method described in Equation (1) of the paper for $\\phi(x) = \\cosh(x)-1$ converges in just one iteration.\n* The function $f(x) = \\tfrac{1}{4}x^4 - \\tfrac{1}{2}x^2$ is a simple 1d nonconvex function that is anisotropically smooth relative to $\\phi(x) = \\cosh(x)-1$ with $L = 3.032$ and thus we can use HGD to minimize it. It is also $(L_0, L_1)$-smooth with constants $L_0 = \\max |3x^2-1| - L_1|x^3-x|$, where we can freely set $L_1$. We can thus use the algorithm described in [4, Equation (3.2)] to minimize this function. We compare the two methods and present the results in the following table, where the number denotes the required iterations to achieve accuracy $10^{-06}$.\n\n| Initial point | HGD | [4, Equation (3.2)] $L_0=17.02$, $L_1=0.5$ | [4, Equation (3.2)] $L_0=5.08$, $L_1=1$ |\n|---------------|-----|-----------------------------------------|-----------------------------------------|\n| $x_0=10$      | 10  | 25                                      | 55                                      |\n| $x_0=50$      | 21  | 83                                      | 84                                      |\n| $x_0=100$     | 32  | 155                                     | 120                                     |\n\nThese simple examples showcase the existence of functions that are better described by the anisotropic descent inequality.\n\nWe believe that we have addressed all the reviewer's concerns and weaknesses, and we kindly ask the reviewer to reevaluate their rating.\n\n---\n**References:**\n\n[1] Hübler, Florian, Ilyas Fatkhullin, and Niao He. \"From gradient clipping to normalization for heavy tailed sgd.\" arXiv preprint arXiv:2410.13849 (2024).\n\n[2] Kornilov, Nikita, et al. \"Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1) $-Smoothness.\" arXiv preprint arXiv:2502.07923 (2025).\n\n[3] Yang, Junchi, et al. \"Two sides of one coin: the limits of untuned SGD and the power of adaptive methods.\" Advances in Neural Information Processing Systems 36 (2023): 74257-74288."}]

Author rebuttal:

Meta-review: This paper studies preconditioned gradient methods for smooth nonconvex optimization problems. This work is a follow up to the work of Oikonomidis, Quan, Laude, and Patrinos [30] who introduces the idea of preconditioned gradient methods which generalize gradient clipping techniques. Moreover, the assumptions which they prove convergence generalizes (L_0,L_1)-smooth functions. 

In this paper, they analyze (i) a heavy ball variant of the method (algorithm 1) and (ii) a stochastic version of the method (which as theorem 3.4 specifies requires very large minibatches such that the gradient noise is less than 1/K where K is the number of iterations). Their numerical results are okay with no meaningful gains training CIFAR10/MNIST (figure 1) but significant gains demonstrated on matrix factorization with the Movielens 100K dataset (figure 2). One weakness of these empirical results is that there is limited modern relevance of gains on this task.

Comments:

Please explain clearly how heavy tail distributions are captured by your assumption that E[\phi(\grad \phi*(\grad f(x)))] <= \sigma^2.

“We set the learning rate by performing a parameter sweep over {1, 0.1, 0.01}.” Use a finer grid.
Decision: Accept (poster)