Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
Authors: Alexander Bodard
Panagiotis Patrinos
Venue: NeurIPS 2025 spotlight ()
Keywords: Nonconvex optimization
generalized smoothness
saddle point avoidance
Primary area: optimization

Abstract: We study generalized smoothness in nonconvex optimization, focusing on $(L_0, L_1)$-smoothness and anisotropic smoothness. The former was empirically derived from practical neural network training examples, while the latter arises naturally in the analysis of nonlinearly preconditioned gradient methods. We introduce a new sufficient condition that encompasses both notions, reveals their close connection, and holds in key applications such as phase retrieval and matrix factorization. Leveraging tools from dynamical systems theory, we then show that nonlinear preconditioning—including gradient clipping—preserves the saddle point avoidance property of classical gradient descent. Crucially, the assumptions required for this analysis are actually satisfied in these applications, unlike in classical results that rely on restrictive Lipschitz smoothness conditions. We further analyze a perturbed variant that efficiently attains second-order stationarity with only logarithmic dependence on dimension, matching similar guarantees of classical gradient methods.

Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
Alexander Bodard ESAT-STADIUS & Leuven.AI KU Leuven alexander boderddkkuleeeeee...b
Panagiotis Patrinos
ESAT-STADIUS & Leuven.Al KU Leuven
panos. www.ipssesnnnnttat......m kul luven. be
Abstract
We study generalized smoothness in nonconvex optimization, focusing on (Lo, L1)- smoothness and anisotropic smoothness. The former was empirically derived from practical neural network training examples, while the latter arises naturally in the analysis of nonlinearly preconditioned gradient methods. We introduce sufficient condition that encompasses both notions, reveals their close connection, and holds in key applications such phase retrieval and matrix factorization. Leveraging tools from dynamical systems theory, we then show that nonlinear preconditioning- including gradient clipping - preserves the saddle point avoid- ance property of classical gradient descent. Crucially, the assumptions required actually satisfied in these applications, unlike in classical
for this analysis results that rely on restrictive Lipschitz smoothness conditions. We further ana- lyze a perturbed variant that efficiently attains second-order stationarity with only logarithmic dependence on dimension, matching similar guarantees of classical gradient methods.
Introduction
We consider the unconstrained optimization problem
minimiie f()).
(I)
where f - F is twice continuously differentiable nonconvex function. This work studies the nonlinearly preconditioned gradient method, with iterates described by
x++1 T7,x(=") = x² (AV )x))),
(P-GD)
where RRU is referred to as the reference function, and ø², its convex conjugate, is called the dual reference function.
Nonlinear preconditioning provides a flexible framework for constructing and analyzing gradient-
based optimization algorithms [36] 21 31 For instance, when d(x:) = | the update (D-GD) reduces to classical gradient descent. More broadly, we focus on isotropic reference functions of the
form ((x) h( [|= for some scalar kernel function R + R, {oo). though our results extend
in part to more general settings, including separable reference functions o(x) = >i h((z)). Some
kernel functions of interest include:
h (x) cosh(ar) 1, h2(x)) exp((=)) - |a| 1, h₂(x) - In(1
|=]),
(2)
each which upper bounds the quadratic function =²/2, as visualized in Fig. These choices induce preconditioners that closely resemble common gradient clipping heuristics, shown in Fig. |
The effectiveness of gradient clipping has been justified using the concept (Lo, L, smoothness..
which is empirically motivated by practical neural network training scenarios 42 However, it
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

0:5
0.5
0.5
0.5
fx coch(2)
mini (maxfyy -1).1 Af (x) aresinhig)
[a]
(x)
-|=]
In(1
(g) [nf] (pp()))))))
Figure 1: Comparison of kernel functions and (h) their corresponding nonlinear preconditioners.
remains unclear under what precise conditions this smoothness assumption holds in real-world applications. On the other hand, the preconditioned gradient method naturally analyzed under anisotropic smoothness [36], another generalization of the classical Lipschitz smoothness condition. Rather than imposing global quadratic upper bound, anisotropic smoothness permits more flexible upper bounds defined in terms of the reference function é. This makes the preconditioned gradient method particularly attractive in settings where the standard Lipschitz condition is too restrictive. This leads us to our first central question:
Can we formally establish anisotropic smoothness and (Lo, Ly)-mmoothness of practical problems where traditional assumptions fail?
Our second line of inquiry focuses on the behavior of the preconditioned gradient method when applied to nonconvex objectives. Classical gradient descent is known to avoid strict saddle points under the assumption of (global) Lipschitz smoothness (24). phenomenon which helps explain its strong empirical performance in nonconvex settings. However, for many practical applications Lipschitz smoothness holds only locally or compact around minimizer, meaning that this assumption is not truly satisfied. This raises the following question:
Does nonlinear preconditioning preserve the saddle point avoidance properties of gradient descent under possibly less stringent smoothness assumption?
Our results reveal novel connections between different generalizations of smoothness and provide strong theoretical support for nonlinear preconditioning, particularly in nonconvex settings where the classical Lipschitz smoothness assumption may fail.
Contributions Our contributions be summarized follows.
We investigate the classes of problems for which (Lo, L.)-smoothhess and anisotropic smoothness two generalizations of the classical Lipschitz smoothness condition applicable. To this end, we propose a novel sufficient condition (Assumption 2.8) that guarantees both anisotropic and (Lg, L, smsoohotssssss, thereby revealing structural link between these two frameworks. We further demonstrate section [2.3] that this condition holds for several prominent nonconvex problems, including phase retrieval, low-rank matrix factorization, and Burer-Monteiro factorizations of MaxCut-type problems.
We establish that nonlinear preconditioning preserves the saddle point avoidance behavior of gradient descent, and moreover extends results from the classical Lipschitz smoothness framework to the broader setting anisotropic smoothness. Specifically, we prove asymp- totic avoidance of strict saddle points by leveraging the stable-center manifold theorem. By invoking a recent nonsmooth generalization of this theorem, this analysis is then further extended to accommodate hard gradient clipping. Finally, we present complexity analysis for perturbed variant the preconditioned gradient method, showing that converges to second-order stationary point with only logarithmic dependence the problem dimension.

---

Notation Let @ux" be the set of symmetric n X n matrices. We denote the standard Euclidean
inner product on R" by (..,), , and the corresponding norm by || ||. For X, E R= (X, Y) trace(XX Y) is the standard inner product on IK " and ||- denotes the spectral norm. The class of k times continuously differentiable functions
open set O _ I is denoted by C* (O). We write sgn(z) = -//lz=l for I E R" \ {0} and otherwise. A function f E C is L-Lipschitz smooth for all x. y E R" it holds that | fz) V
f(y)) S Li|æ yll. with L 2 and (Lo, L J-smoohh if
||V [x)) < Lo + L1 (x)) for all æ e R with Lo. L1 2 0. Otherwise, we follow (37]
1.1 Related work
Generalized smoothness Gradient descent is traditionally analyzed under the assumption of Lipschitz smoothness (34), although many applications violate this condition. Bregman relative smoothness is a popular extension which allows the Hessian to grow unbounded, see e.g. (30) which assumes a certain polynomial growth. More recently, the (Lo, L1 )smoothness condition was proposed by Zhang et al. [42], based empirical observations in LSTMs, and used to analyze clipped gradient descent and a momentum variant [41). The framework has since been applied to stochastic normalized gradient descent [43 and generalized SignSGD [12]. Notably, Crawshaw et al. (12) provided empirical evidence that (Lo, L1) -tmoohotssssss holds for Transformers [40]. albeit with layer-wise variation in constants. Further generalizations include a-symmetric smoothness [9] and é-smoothness (28), and the latter was used to analyze the convergence of Adam (29]. Despite empirical support for these conditions in key applications, theoretical guarantees remain limited.
Nonlinear preconditioning The preconditioned gradient method with updates given by P-GD
was introduced in the convex setting by Maddison et al. (31]. Then, Laude et al. [22] 21 studied
L-anisotropic smoothness and, under this condition, showed convergence of (P-GD) for nonconvex
problems. The method was later extended to measure spaces [4). Oikonomidis et al. (36) proposed
the (L, L)- aniisotropicc smoothness condition, connected it to (Lo, L1 (1)-smoothness and analyzed convergence of (P-GD) in both convex and nonconvex settings. We also highlight the works [26] 35
that study the concept of P-convexity, which is closely related to anisotropic smoothness.
Saddle point avoidance To explain the success of gradient descent on Ronconvex problems, much work has focused on its (strict) saddle point avoidance properties (25) 24 It was shown that gradient descent may take exponential time escape saddle points, even with random initialization [13). The works (27 33) showed that noise-injected normalized gradient descent escapes them more efficiently. Jin et al. [7 [8 demonstrated that perturbed gradient descent escapes saddle points in time polylog- arithmic in the problem dimension. Recently, Cao et al. [8] studied saddle point avoidance under a second-order self-bounding regularity condition rather than under classical Lipschitz smoothness.
2
Anisotropic smoothness
2.1 Definition and basic properties
This section introduces (I., aniinoootoo smoothness as proposed by (36). The following assump- tion, which guarantees in particular that o² E C² (IR") and Φ 2 0, is considered valid throughout.
Assumption 2.1. The function & R. - R is proper, Isc, strongly convex and even with ((0)=
We usually also assume the following condition, which ensures in particular that 6* E (RR). Assumption 2.2. int dom o + 0; & E (int dom d). and for for any sequence {a* kee that converges to some boundary point of int dom di it follows that V Vo (0((=)]] + 0o.
We follow the definition of anisotropic smoothness by (36], which reduces to [21 Def. 3.1] with
reference function Ló if dom & g" If C² this concept corresponds global version of anisotropic prox-regularit of f 200 2.13J. For a geometric intuition, we refer to [26 35 36
Definition 2.3 (LL, -a smoothness (36)). A function f
E
R is (L. L)
anisotropically smooth relative to reference function ó with constants L, L > 0 if
f(x) < f()) + T.I.- T 7)) - T.I. (( 5))
for all 3, E R", where Tr 1. --
3

---

The following proposition provides a sufficient condition for anisotropic smoothness. We consider the case 6* E C for simplicity of exposition, but note that a variant for Φ & C² can also be formulated. Proposition 2.4 (Second-order characterization of (L, -anisotrropie smoothness). Suppose that Assumption 2.2 holds, and let f E C² be such that for all x E R (L
Amax
S LL.
(3)
co. Moreover, assume that either dom & is bounded or that dom Φ = IR" and that for all E R we have f(x) S Lr <(r)) 3 for some E (0, b E R. Then, f is (ôL, L -anisotropically smooth relative to à for any 1.
and limils| 1 II
We say that f satisfies the second-order characterization of anisotropic smoothness if (3) holds. Note that the growth condition on is not restrictive when dom IR, and that the coercivity assumption on the iteration map Tr 1.L is very mild; we refer the reader to the arguments in [36] Finally, we connect anisotropic smoothness some popular smoothness notions.
Example 2.5 (Lipschitz smoothhnsssss (36] Proposition 2.3]). Suppose that f C² Ly-Lipcchitz
smooth. Denote by > 0 the parameler of strong convexity of reference function cb. Then S is
(Lr/u, 1) >aansotrropically smooth relative to Φ.
Example 2.6 (LL, L, -s)-oooohhnesss). Let f E be (Lo, Lmm-mmothh, let L= L,, La/ L., and let ó(x) -|,=|| In(1 - || Then f satisfies the second-order characterization of (L, L)-
anisotropic smoothness relative to 6 130 Proposition 2.6 & Corollary 2.7
2.2 A novel sufficient condition for generalized smoothness
Although it is not necessarily the case for multivariate polynomials, as illustrated by the following example.
that univariate polynomials are (Lo, L1 --moohhhh [42 Lemma 2], this is
Example 2.7. Consider the polynomial f y) = ta² + 1//²= -22²²² with gradient and Hessian
vf(2.y) = xx3 -xy
f(x ( -2xy
(3x²
y²
22ry 3y²
x²y
x2
Remark that V -z) = and V2 (x, x² (3 222). Clearly, f cannot be (Lo, L1) since f(x -1)l = =4|==|? grows unbounded, while [Vf((z -z)l for all x E IR
For multivariate polynomials there may exist path of || - ao along which the gradient norm grows slower than the Hessian norm, in which case (In, In) In)-mmothhness cannot hold. More examples are included in appendix [A.2 Based on this insight, we propose the following novel condition.
Assumption 2.8. There exists an R E N such that for all E R.
(x))]F PR([[=])), and [[](()]] (
Here PR(a) Ex= aja' and (a) = R+1 b,ad are polynomials of degree R and R 1, respectively, and in particular assume that bR+1 > 0.
Note that 330 constructs Bregman distance inducing kernel function under a similar polynomial
upper bound to the Hessian norm. Appendix A. verifies Assumption for univariate polynomials.
The following result states that Assumption 2.8
8 is sufficient condition for (Lo, Li Li)-smoothness) [
Theorem 2.9. Suppose that Assumption 2.8 holds for C?. Then, for any I, there exists
Lo > 0 such that f is (Lo, Lmmoohh
Under mild conditions on the kernel function h, which appendix A.5 shows hold for all examples in 2), Assumption 2.8 also implies the second-order characterization anisotropic smoothness. In fact, implies the stronger condition that ||V2 (V=2 VV==VV(())VV+ f(x)] is uniformly bounded.
Assumption 2.10. The reference function is isotropic, i.e. o(x) h([|=]]), and such that (i) h "wrly is a decreasing function on R4, (ii) lim yh = C2. for some C2 E R., and (iii)
he (sa(v)) = O, for any polynomial sa(a)
d
lim +0++00
Σ u,a of degree d. i=u
Theorem 2.11. Suppose that f satisfies Assumption 2.8 If o satisfies Assumption 2.2 and As- sumption 2.10 then for any L L> there exists an L >> such that f satisfies the recond-orded characterization of (I, L.) -aaaisootopiic smoothness relative to Φ.
In fact, Theorem 2.9 still holds if Assumption 2.8 is relaxed to [V]())] 2 qn(()=])).

---

2.3 Applications
We now establish for a number of key applications that Assumption 2.8 holds, thus proving that the objective is (Lo, L1 -smooth and satisfies the second-ordes characterization of (L, -nnisotrppii smoothness. Remark that for all of these, the classical Lipschitz smoothness assumption is violated.
2.3.1 Phase retrieval
Consider the real-valued phase retrieval problem with objective and gradient
f(x) = + D (1 (a, x))
1 m
m
VS(x)
-
(ue (a) xT) aza
Here, 0; Rn and y: E for Np.m. are the measurement vectors and the corresponding measurements, respectively. A relaxed smoothness condition for the phase retrieval problem has been explored
based on Bregman distances. The following theorem establishes that whenever the measurement vectors span R", the objective f also satisfies our Assumption 2.8 Note that the measurement vectors can only span IR if 2 n. Moreover, the assumption on spanning IR" is mild compared to well-studied conditions that guarantee signal recovery in the phase retrieval problem. These conditions either require randomly sampled measurement vectors with m on the order of log (7), or the so-called complement property (1. The former ensures the spanning property with high probability, while the latter guarantees it deterministically.
Theorem 2.12. Consider the phase retrieval problem with objective and suppose that the vectors {a h span R..
(1) For any
there exists Lo > 0 such that f is (Lo, I-moshooth.
(ii) If à satisfies Assumptions 2.2 2.10 then for any L there exists L > 0 such that
f satisfies the second-ored -oder characterization of (L, ...-)aaiioorrppt smoothness.
2.3.2 Symmetric matrix factorization
Consider the symmetric matrix factorization problem with objective and gradient
f(U) = ] - -I VS()) = (UUT - YYU.
(5)
Here, U Rexr is the optimization variable, and Y Sux= is given symmetric matrix. When r < n, minimizing f yields low-rank approximation of Y with rank at most r. Such low-rank matrix factorizations fundamental in variety of applications, most notably in principal component analysis (PCA) [19]. where one seeks to capture the most significant directions of variation in the data. More broadly, symmetric matrix factorization plays central role across various domains: in machine learning, it underlies techniques such as non-negative matrix factorization for parts- based representation learning [23]: in signal processing, it employed in matrix completion and compressed sensing to reconstruct structured signals from incomplete or noisy measurements [6]
Theorem 2.13. Consider the symmetric matrix factorization problem with objective following statements hold.
Then the
(i) For any L1 > there exists an Lo > 0 such that f is (Lo, -mooth.
(ii) If db satisfies Assumptions 2.2 and 2.10 then for any > O, there exists an T, > 0 such that f satisfies the second-order characterization of (T., -.)-J.ssorroopi smoothness.
2.3.3 Asymmetric matrix factorization
Consider the regularized asymmetric matrix factorization problem with objective
f(W, H) | - W + K IHI
(6)
where W R and H rx are the optimization variables, E Rmxx is given matrix, and 2 is regularization parameter. When and r min(m, n),, this reduces to the classical
5

---

low-rank matrix factorization problem. Additionally, such objectives have been used to model the training of two-layer linear networks, such as in the case two-layer autoencoders [T5]. We note that
the results below also hold for regularization terms of the form x|[WT W HH F described
in [TT], and highlight the work of (32), which designed a Bregman proximal- gradiennt method for
similar regularized matrix factorization problems.
Theorem 2.14. Consider the asymmetric mutrix factorization problem with objective (6 and let
0. Then the following statements hold.
(i) For any L1 there exists an Lo > 0 such that f is (Lo, L1)-smooth
(ii) If à satisfies Assumptions 2.2 2.10 then for any L. O, there exists L > 0 such that f satisfies the second-order characterization of aniisorroii smoothness.
Note that Theorem 2.14 requires > 0. To understand why, observe that the gradient of f is given by
fw H) = (W 11 H-YY + + and VHf = W (W (WH-Y)) + Let a denote the concatenation of the vectors vec(W) and vec( such that || = | In contrast to symmetric matrix factorization, if 0, the gradient norm of f can approach zero reequirs an asymptotic growth proportional to ||0/| To see this,
||>|| + 20, whereas Assumption 2.8 requires consider W* Rmxr, H R such that W* H Y. In this case, the gradient norm is zero, and rescaling W* and H with nonsingular matrix D grxr, i... W W D and H D" preserves the gradient norm. As a result, one can construct counterexamples where the gradient norm remains zero while || - oc, and consequently | oc.
Finally, we remark that the key step proving Theorem 2.14 entails lower bounding /V H)] in terms of the variable V == max(I] [I [[)] and expl oiting that |V - oc if and only if ||>||| > xc. appears that this strategy can generalized to the factorization of Y into more than two factors, which is relevant for training deep linear networks.
2.3.4 Burer-Monteiro factorizations of MaxCut-type semidefinite programs
Let us consider so-called MaxCut-type semidefinite programs (SDPs)
minimize Xes*xn
XC,
subject to
X > 0 diag(X) = 1n,
where C E S is the cost matrix. The relaxation (7) provides precise relaxation to the MaxCut
problem, a fundamental combinatorial problem arising in graph optimization [4] 14] In an effort to
exploit the typical low-rank structure of the solution, a Burer-Monteiro factorization 5 decomposes
X =VVV T for V E Rexr, This yields
minimize VeRaxr
- (C,VVT)
subject to diag(VVT)= 1,.
Choosing r much smaller than significantly decreases the number of variables from n² nr. However, the downside of this approach is that convexity is lost. Fortunately, under certain conditions every second-order stationary point of this nonconvex problem is global minimizer (14). Let us denote by æ; R² the i' I'th row of V. such that V = { [2,, .,, We also define the vectorized variable x = [<r _ ..... xIl E IRd where d = nr. Then we denote by f(x) the objective of the constraint of
terms of .r, and likewise by ((x)
terms of z.
As proposed in the seminal work [ this nonconvex constrained problem can be solved with an augmented Lagrangian method (ALM). Each iteration consists of minimizing with respect to the primal variable x the (unconstrained) augmented I Lagrangian with penalty parameter /3 > 0, i.e.,
Lø(x, v) = f(x) + (A(x). - (1(()))
followed by an update of the multipliers y E R", A similar strategy was also used in 38 for Burer-Monteiro factorizations of clustering SDPs. The following theorem establishes generalized
smoothness of the augmented Lagrangian with respect to the primal variable.

---

Theorem 2.15. Consider the Stree-MMontein factorization of the MaxCut-type SDP 7 and let Lg denote the augmented Lagrangian with penalty parameter 3 O of this factorized problem. Then, with respect to the primal variable x: E R and for some fixed multiplier y E th the following statements hold.
(i For any L1 there exists Lg > 0 such that Lo(-s v) is (Lo,LL)-smootte
(ii) If d satisfies Assumptions 2.2 and 2.10 then for any L O, there exists L > 0 such that La(',)) 3) satisfies the second-order characterization of (L, LL,L))ann L.)aassotroppic smoothness.
3 Saddle point avoidance of the preconditioned gradient method
The remarkable performance of simple gradient descent-like methods for minimizing nonconvex functions is often attributed to the fact that they avoid strict saddle points of Lipschitz smooth objectives. This section establishes that nonlinear preconditioning of the gradient preserves this desirable property, and in fact generalizes this result to anisotropically smooth functions.
3.1
Asymptotic results based the stable-center manifold theorem
Denote by X the set of strict saddle points of a function f E C.. i.c.
x {a*
Vf(==) 0, Amin (V2 < 03.
24 which are based the stable-center manifold theorem (39]. exploit the fact that the eigenvaluee lues of the Hessian f are uniformly bounded. In a similar way, for the preconditioned gradient descent method require that the second-order characterization of (I, -nnaasootoooiccc smoothness holds. By exploiting the fact that V² = I, we then obtain the following theorem, which generalizes 25 Theorem 4).
Classical results like
Theorem 3.1. Let f E C² and suppose that Assumption 2.2 holds. Consider the iterates (x men generated by the preconditioned gradient method, ie., x T., (x²*,, where the initial iterate x E R is chosen uniformly at random. If satisfies the second-ordes characterization of (L, L)- anisotropic smoothness, and if t, then
lim x E x xx=)== k0000
IP
(10)
Assumption 2.2 ensures 6- E C²2 which in turn guarantees that T.,L-1 E C², as needed for the stable-center manifold theorem 39 24). Unfortunately, this means that the reference function (xx) h([ with 2
1... which gives rise to a version of the gradient clipping method 36 Example 1.7], is not covered by Theorem 3.1 Indeed, in this case we have h²((y) = 1111 y max {min {y. 1 -1.. Note however that this projection is piecewise affine function, and therefore h² is continuously differentiable almost everywhere, i.e., except the points y +1.
Based on a recent variant of the stable-center manifold theorem [T0 we now establish that also the above clipped gradient variant with 6² & C2 avoids strict saddle points with probability one. In particular, [10, Proposition 2.5] only requires that the iteration map Tn,x, is continuously differentiable set of measure
which contains the set of strict saddle points X We thus have to show that (i) V (L- VV())) is differentiable almost everywhere; and that (ii) VØ" (-) is differentiable around the point L Vf fx** O, with x* X Remark that the former requires additional assumption for guaranteeing that f maps a set of measure one onto a set on which VΦ" is differentiable.
Theorem 3.2. Let f C²+ and Φ(z) h([]=]] with h -lll 112 + 8 Consider the iterates keM)) generated by the preconditioned gradient method, i.e., a++ T T- (w+)
*² 7 mim(m///V L- f(*)), where the initial iterate 2 R. chosen uniformly at random. Moreover, suppose that the set
U= (a E [1VVf()) +1]
is set of measure one. If ff satisfies the second-order sufficient condition for (L, annisotrroii smoothness, and if < 1 then
IP
lim k-
t E x²)
(11)
7

---

3.2 Efficiently avoiding strict saddle points through perturbations
Despite avoiding strict saddle points asymptotically for almost any initialization, gradient descent may actually be significantly slowed down around saddle points. In fact, gradient descent can take exponential time to escape strict saddle points [13). in the sense that the number of iterations depends exponentially on the dimension of the optimization variable. Yet, by adding small perturbations, this issue can be mitigated, and the complexity of obtaining second-order stationary point then depends only polylogarithmicalyy on the dimension result for a perturbed preconditioned gradient method.
(17 18 This section establishes similar
Existing works analyzing the complexity of gradient descent for converging to a second-order stationary point require not only Lipschitz continuity the gradients, but also the Hessian. This is quite restrictive, since for example any (non- degenerat)) polynomial of degree more than 2 violates this assumption. Instead, we require Lipschitz continuity of the mapping
Hx = x J(Vo' (AV & (xV)
To ensure well-definedness of Hx. Assumption 2.2 is assumed in the remainder of this section. Assumption 3.3. The mapping Hx)x) = v (AV is p-Lipxchitz-comtimouu, i.e.,
pp 0: [+)(=) - (x)x)) s p| -ll, Vr,y E R..
This new condition appears significantly less restrictive, as illustrated by the following example. Example 3.4. Let fxx 1 1,²²² and (xx) cosh(|==)) 1. Since arcsinh is odd function,
VΦ VØ' = arcsinh (12 (f (x)) = arcsinh(Aff( arcsinh(A( -x)).
Therefore, we obtain that Hx(z) X X ((
(3=2-1)
(1= One easily verifies that
da
H^ C¹ with bounded derivative, which implies the required Lipschitz-continnie of H In fact, this reasoning generalizes to any univariate polynomial, regardless of its degree.
Under anisotropic smoothness, it is natural to consider X X''o"Vo" (AV)(() first-order station- arity measure, and Amiu ( (x)) as second-order stationarity measure. Therefore, we say that point IR' an e-second-order stationary point an (L, annioottrrppl smooth function f and Amin ( 6* (AT 2 -Vpc.
- VV
S e
For é = Ill 2| we recover the classical notion of c-second-order stationarity, with p the constant of Lipschitz continuity of v
perturbed preconditioned gradient method that closely resembles perturbation schemes presented in [17 [8] In particular, whenever the first-order stationarity is sufficiently small, then perturbation added followed by [T] unperturbed iterations.
Algorithm 1 Perturbed preconditioned gradient descent
X > 0, perturbation radius > 0, time interval T > 0, tolerance G > 0 REQUIRE: x E R", 7
1: kipertuth
2: for k = 0. 1,..... do
3: if A Φ V (A f 8 and Is kpenuub T then
4:
L k e
ek Bo(r) uniformly, kpenub k
5:
k+l = =² V (AV
We analyze the complexity of algorithm T under the following assumption.
Assumption 3.5. Suppose that Assumption 2.2 holds, such that o² E C², and let 6(x) h([[=l) where in particular h E C Moreover, let h(T) x² x²/2, and h(x) = x² a2/2 o(x²) as I + 0.
This assumption holds for kernel functions from P Remark that there no real loss generality by fixing the scale of l around 0, since a rescaled version of be obtained by modifying L.

---

In our analysis, we specify the parameters of algorithm | in terms of L, L, and some x 2 1,
+/- A ==
200x3
T
voc Xi
G min { Jz
(12)
and introduce two additional constants that are used only in the analysis, i.e.,
- 2
(13)
50AX
We obtain the following complexity of algorithm I for converging second-order stationary point. Theorem 3.6 (Iteration complexity). Let f be (L. Lnaaioootropilllly relative to ø. Moreover, suppose that Assumptions 3.3 and 3.5 hold, and define constants D 2 f(x²) inf f and
some LAVTA, for some c > O. There exists a constant Cmax > 0 such that if S Cuaxo then
= -log2 for any >> O sufficiently small, and for any ò E (0, 1), Algorithm 7 with parameters as in (12) and 133. visits an e-second-orde stationary point least T/2 iterations with probability least 1-666 8. where
CappLe785
T = 8 max {
(d(a")-int JYT , ( ] = ) (LI(()))) 275
(
Lea
The Ô notation hides a factor X" which is polylogarithmic in the dimension n and the tolerance c.
Theorem 3.6 generalizes [18] Theorem 18], and relies on a similar high-level proof strategy, which goes as follows. If the current iterate is not e-second-order stationary point, then either o (AVf(x)) is large, or Amin ( (Hx) is sufficiently negative. In either case, we establish a significant decrease in function value after most [T] iterations of algorithm | Since f(z") - is bounded, the number of iterates which are not e-Second-order stationary can be bounded.
inf
Nevertheless, the generalization of [18 Theorem 18] to the setting of Algorithm is by means straightforward. The original proofs rely heavily on Lipschitz smoothness, in a way that often does not generalize directly to the anisotropically smooth setting. Here, highlight two such difficulties. First, consider a point æ E R" and the perturbed point T == x + 76 for some perturbation & E (r)).. Then, by anisotropic smoothness
upper bound
f(z) - f(x) S dtc + Vo' (AV)(z))).
While Lipschitz-smoothness with á = -12 readily provides an upper bound in terms of ||5]|2 s 22 and [>)](, the reference functions are not typically such that an upper bound terms of
Φ(E) <(Vo" fx))
can be obtained. Second, unlike in the L-Lipschitz-smooke case where || < L, the norm |Hll cannot be upper bounded uniformly, even under the second-order characterization of (L, L.-- anisotropic smoothness. The latter only guarantees that Amax(H, S LL, but it does not lower bound Amin (Hx). And even if the eigenvalues of H2 were bounded absolute value, this still would not guarantee boundedness of ||A]], since H, not a normal matrix in general.
4 Numerical validation
Lastly, we illustrate some merits of nonlinear preconditioning, and validate the complexity result of Theorem 3.6 numericllly. The source code is publicly available
Nonlinear preconditioning for symmetric matrix factorization For the symmetric matrix factor- ization problem (5) with n = 2 and r = 1, Fig. 2 presents a 2D visualization of the level curves of the objective, along with the iterates of both vanilla gradient descent (GD) and the preconditioned variant (P-GD) with Φ(z) = cosh( || - 1. Unless GD is initialized close to a stationary point, the stepsize must be chosen very small prevent the iterates from diverging expected, because the quartic objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for = 1)
sinh sinh-i(( ((v))()) Vf()))
xt
[V(()II
In this case, large gradients are damped recall the close resemblance to clipping methods, cf. Fig.
resulting in the convergence of PDD for stepsizes 7 that are often orders of magnitudes larger than the maximum stepsize of GD. In turn, this causes (P-GD) to often require significantly fewer iterations, and overall outperform GD for fixed stepsize.

---

Figure 2: Iterates of GD (red) and P-GD (blue) on symmetrie matrix factorization problem.
5
2
Objjet Volle
OBjectic Value
Objecton Value
-200
-20
-200
-400
-200
-200
-00
-200
212
416
1000
200
602
670
820
1762
407
907
277
465
800
3100
SpacTs
Epochs
Epuths
Spachs
10,
Ostestvv Volue
Diject ore Saluw
Oxjective
Oujodive
2000
1020
2000
2002
ED0ch5
Ebocha
Epodis
Esochs
Figure 3: Performance of vanilla GD (blue), perturbed vanilla GD rithm D (green) on the 'octopus' function 13
13 Alg 1] (orange), and Algo-
Fast avoidance of saddle points Fig validates the fast escape of saddle points by Algorithm| [
We consider the 'octopus' objective [3 which was constructed such that GD takes exponential time
to escape saddle points. We select all hyperparameters as in [13] $5J, and set the only additional hyperparameter L vary the constant L E 1.5, 2, 3} and dimension E {5, 10), thus creating counterparts to [11, Figs and 4]. We observe that algorithm| D performs similar to perturbed vanilla GD, and also scales in similar way with respect to and L. This validates the complexity result from Theorem 3.6
We compare against vanilla GD and perturbed vanilla GD 13 Alg 1], and
5 Conclusion
This work introduced a novel sufficient condition unifying Lz)-sooooootthn -mmothhnssssss and anisotropic smoothness. We showed that this condition holds in key applications such phase retrieval, matrix factorization, and Burer-Monteiro factorizations of MaxCut.
We further analyzed the nonlinearly preconditioned gradient method, which naturally aligns with anisotropic smoothness. Notably, we proved that preserves the saddle point avoidance properties of gradient descent and extends them to amisotropically smooth settings. This contrasts with prior analy- ses requiring either global Lipschitz smoothness, or local smoothness combined with compactness, both of which are often unmet in practice.
To knowledge, this is the first work to rigorously establish saddle point avoidance for problems like phase retrieval and matrix factorization under a smoothness condition that both practical and verifiable. These results strengthen the theoretical foundations of first-order methods for nonconvex optimization and in particular encourage further study of nonlinear gradient preconditioning.
Acknowledgments and Disclosure of Funding
The authors are supported by the Research Foundation Flanders (FWO) research projects G081222N, G033822N, GOA0920N and the Research Council KU Leuven C1 project with ID C14/24/103.
We thank Konstantinos Oikonomidis, Jan Quan and Emanuel Laude for the insightful discussions.
10

---

References
[1] A. S. Bandeira, Cahill, D. G. Mixon, and A. A. Nelson. "Saving phase: Injectivity and stability for phase retrieval", In: Applied and Computational Harmonic Analysis 37.1 (July 2014), pp. 106-125.
[2] D. P. Bertsekas, Nonlinear Programming. 2nd ed. Athena Scientific, 1999.
[3] J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd. "First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems". In: SIAM Journal on Optimization 28.3 (2018), pp. 2131-2151.
[4] C. Bonet, T. Uscidda, A. David, P.-C. Aubin-Frankowste and A. Korba. "Mirror and Pre- conditioned Gradient Descent in Wasserstein Space". In: Advances in Neural Information Processing Systems 37 (Dec. 2024), pp. 25311-25374.
[5] S. Burer and R. D. Monteiro. "A nonlinear programming algorithm for solving semidefi- nite programs via low-rank factorization". In: Mathematical Programming 95.2 (Feb. 2003), pp. 329-357.
[6] E. Candès and B. Recht. "Exact Matrix Completion via Convex Optimization", In: Founda- tions of Computational Mathematics 9.6 (Dec. 2009), pp. 717-772.
[7] E. Candès, T. Strohmer, and V. Voroninski. "PhaseLift; Exact and Stable Signal Recovery from Magnitude Mcasurements via Convex Programming", In: Communications on Pure and Applied Mathematics 66.8 (2013), pp. 1241-1274.
[8] Cao, A. Y. Chen, K. Sridharan, and Tang. Efficiently Escaping Saddle Points under Generalized Smoothness via Self- Bounding Regularity. Mar. 2025.
[9] Z. Chen, Y. Zhou, Y. Liang, and Z. Lu. "Generalized-S Nonconvex Optimization is
As Efficient As Smooth Nonconvex Optimization". In: International Conference on Machine Learning (June 2023). pp. 5396-5427.
[10] P. Cheridito, A. Jentzen, and F. Rossmannek. "Gradient Descent Provably Escapes Saddle Points in the Training of Shallow ReLU Networks". In: Journal of Optimization Theory and Applications (Sept. 2024).
[11] Y. Chi, Y. M. Lu, and Y. Chen. "Nonconvex Optimization Meets Low-Ram Matrix Fac- torization: An Overview". In: IEEE Transactions on Signal Processing 67.20 (Oet. 2019),
pp. 5239-5269.
[12] M. Crawshaw, M. Liu, F. Orabona, W. Zhang, and Z. Zhuang. "Robustness to Unbounded Smoothness of Generalized SignSGD". In: Advances in Neural Information Processing Systems 35 (Dec. 2022), pp. 9955-9968.
[13] S. S. Du, C. Jin, J. D. Lee, M. I. Jordan, A. Singh, and B. Poczos. "Gradient Descent Can Take Exponential Time to Escape Saddle Points". In: Advances in Neural Information Processing
Systems. Vol. 30. 2017.
[14] F. R. Endor and I. Waldspurger. Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs. arXiv:241 1.00310011111 [math]. Mar. 2025.
[15] I. Fatkhullin and N. He. "Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence". In: Proceedings of The 27th International Conference on Artificial Intelligence and Statistics. PMLR, Apr. 2024, pp. 3493-3501.
[16] M. X. Goemans and D. P. Williamson. "Improved approximation algorithms for maximum and satisfiability problems using semidefinite programming". In: J. ACM 42.6 (Nov. 1995), pp. 1115-1145.
[17] Jin, R. Ge, P. Netrapalli, S. M. Kakade, and I. Jordan. "How to Escape Saddle Points Efficiently". In: Proceedings of the 34th International Conference on Machine Learning. PMLR, July 2017, pp. 1724-1732.
[18] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. "On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points". In: J. ACM 68.2 (Feb. 2021),
11:1-11:29.
[19] I. T. Joliffe. Principal Component Analysis. Springer Series in Statistics. New York: Springer- Verlag, 2002.
[20] E. Laude. "Lower envelopes and lifting for structured nonconvex optimization". PhD thesis. Technische Universität München, 2021.

---

[21] E. Laude and P. Patrinos. "Anisotropic proximal gradient". In: Mathematical Programming (Apr. 2025).
[22] E. Laude, A. Themelis, and P. Patrinos. "Dualities for Non-Euclidess Euclidean Smoothness and Strong Convexity under the Light of Generalized Conjugacy". In: SIAM Journal on Optimization 33.4 (Dec. 2023), pp. 2721-2749.
[23] D. D. Lee and H. S. Seung. "Learning the parts of objects by non-negative matrix factorization".
In: Nature 401.6755 (Oct. 1999). pp. 788-791.
[24] J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. Jordan, and B. Recht. "First-order methods almost always avoid strict saddle points". In: Mathematical Programming 176.1 (July
2019), pp. 311-337.
[25] J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. "Gradient Descent Only Converges to Minimizers". In: Conference on Learning Theory. PMLR, June 2016, pp. 1246-1257.
[26] F. Léger and P.-C. Frbni-Frankowski.. Gradient descent with a general cost. arXiv:2305.0491 [math]. June 2023.
[27] K. Y. Levy. The Power of Normalization: Faster Evasion of Saddle Points. arXiv: 1...043)
[cs]. Nov. 2016.
[28] H. Li, J. Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie. "Convex and Non-convex Optimization Under Generalized Smoothness". In: Advances Neural Information Processing Systems 36 (Dec. 2023), pp. 40238-40271.
[29] H. Li, A. Rakhlin, and A. Jadbabaie. "Convergence of Adam Under Relaxed Assumptions". In: Advances in Neural Information Processing Systems 36 (Dee. 2023), pp. 52166-52196.
[30]
Lu, R. M. Freund, and Y. Nesterov. "Relatively Smooth Convex Optimization by First-Order Methods, and Applications". In: SIAM Journal on Optimization 28.1 (Jan. 2018), pp. 333-354. [31] C. J. Maddison, D. Paulin, Y. W. Teh, and A. Doucet. "Dual Space Preconditioning for Gradient Descent". In: SIAM Journal on Optimization 31.1 (Jan. 2021), pp. 991-1016.
[32] M. C. Mukkamala and P. Ochs. "Beyond Alternating Updates for Matrix Factorization with In- ertial Bregman Proximal Gradient Algorithms", In: Advances in Neural Information Processing Systems. Vol. 32. 2019.
[33] Murray, Swenson, and S. kar. "Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points". In: IEEE Transactions on Automatic Control 64.11 11 (Nov. 2019), pp. 4818- 4824.
[34] Y. Nesterov. Lectures on Convex Optimization. Vol. 137. Springer Optimization and Its
Applications. Springer International Publishing, 2018.
[35] K. Oikonomidis, E. Laude, and P. Patrinos. Forward-buckwart splitting under the light of generalized convexity. ar arXiv:2503. 18098 [math]. Mar. 2025.
[36] K. Oikonomidis. J. Quan, E. Laude, and P. Patrinos. Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness. arXiv:2502.0855: [math]. Feb. 2025.
[37] R. Т. Rockafellar and R. J. B. Wets. Variational Analysis. Ed. by M. Berger et al. Vol. 317. Grundlchren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 1998.
[38] M. Sahin, A. Eftekhari, A. Alacaoglu, Latorre, and Cevher. "An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints", In: Advances in Neural Information Processing Systems. Vol. 32. 2019.
[39] M. Shub. Global Stability of Dynamical Systems. Springer New York, 1987.
[40] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, E. u. Kaiser, and
I. Polosukhin. "Attention is All you Need". In: Advances Neural Information Processing Systems. Vol. 30. 2017.
[41] B. Zhang, J. Jin, C. Fang, and L. Wang. "Improved Analysis of Clipping Algorithms for Non-comen Non-convex Optimization". In: Advances Neural Information Processing Systems. Vol. 33. 2020, pp. 15511-15521
[42] J. Zhang, T. He. S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv:1905. 1881 [math]. Feb. 2020.
[43] S.- Zhao, Y.PP. Xie, and W.-J Li. "On the convergence and improvement of stochastic normalized gradient descent". In: Science China Information Sciences 64.3 (Feb. 2021),
p. 132103.
12

---

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 accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly define our assumptions and their limitations.
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 on 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]
13

---

Justification:
A detailed proof is provided for every theoretical result.
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: The paper discloses the information needed to reproduce the main experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to 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?
14

---

Answer: [Yes]
Justification: The paper provides open access to the code at https:/ com/ Alexaandebbdaarrdesssag.....g www.allsss.ihhpprrrroooooooooeee
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
http:///ddd//oeSuuunntn ssicnpolicy) for more details. hetpolliiigguddde/oooooo
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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all hyperparameters directly or indirectly (same as de- scribed in other papers).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, 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:
[NA]
Justification: The illustrative experiments in this paper do not involve statistical results.
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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).
15

---

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 enror rates).
If error bars reported in tables 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 com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The illustrative experiments this paper required negligible compute.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 study generalized smoothness and optimization algorithms from theoreti-
cal perspective. Any societal impact would be indirect and the result of further research.
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.
16

---

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: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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/datasets 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.
17

---

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
18

---

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 the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Additional results
A.1 Univariate polynomials satisty Assumption 2.8
Theorem A.1. Let f(x) = -E a,z' be univariate polynomial of degree d in x with coefficients E R. Then, f satisfies Assumption 2.8
Proof. Without loss of generality, assume that ad # since otherwise would be polynomial of lower degree. Then, by the triangle inequality we have
d-2
d-2
(x)( S
Σ 1i + 1)(i + 2)a
Σ (i 1)(i + 2)
1=0
i=0
which is polynomial of degree d 2 in |z]. In similar way, obtain from the triangle inequality
d-2
d-2
lf'(z) 2 |d d- 1 1-1 Σ
(i + 1),4112'12 Ida 11- - (d- (dd-1) 1)
a
||~²|
km0
-dlaallad (d 1) Σ |,41||='1
which is polynomial of degree d - 1 in [x]] where the leading coefficient d|aa is nonzero.
A.2
Multivariate polynomials for which (Lo, L1 -.mootthmmooonnsss faall
and This section extends example and provides some simple multivariate polynomials which are not (Lo, L1) )smoohh. particular, we illustrate that this may still happen if the gradient norm grows unbounded.
Consider the following functions
1 (o + 2²
fi
f2(2, f1 +
fs(r, f1(x,)) v) 2
4
By similar reasoning as in example 2.7 gradients
we remark that along a path y = -r these functions have
Vhi -x) = 00)
V S22 -x) -x)= =())
-22)
2.x
Vaa(., -x) =
and Hessians
f2, 122 xx) -x== x² (-2 -2 2 v'lalz -x) x²
2 -2
+2 0 9)
-2
2
Clearly, these functions cannot be (To, I1) >-soohh,, because for y the Hessian norms grow proportionally to |x|² whereas the gradient norms are zero (for f1), constant (for f2), or grow proportionally to [z] (for fa). This visualized in fig.
Remark that fa illustrates that unboundedness of the gradient norm not sufficient for (Lo, L1)- smoothness. Instead, the gradient norm needs to grow 'sufficiently fast'; sufficient condition is given by Assumption 2.8
A.3 Anisotropic smoothness is more general than (Lo, Im)-smoothness
Example 2.6 already established that if a function ff is (Lo- L1) -smoohh, then it also satisfies the second-order characterization of (I,,, Lo --anisotropic smoothness (Assumption 2.8) relative the reference function (xx) -||xr|| Ilnrl [|a]]). We now show that the function f(x) = exp(I|a]] is not (Lo, [n -moothh, but satisfies the second-order characterization (I. L) -anisotropic smoothness with L 2, L 1, thus confirming that anisotropic smoothness generalizes (Lo, L1 smmothhess..
Note that the function f=x exp([[=[1²) has gradient and Hessian
fz(x) 2 exp(r?)x,
f2)() 2 exp(r3) (1 + 2xx
20

---

fa(a.
50
fa(2,))
50
4-4
Figure 4: Surface plot of some multivariate polynomials which not (Lo, L1) smooth. The gradient norm is zero (left), constant (middle), or scales proportional to |æ|] (right) along the path -r (red), whereas the Hessian norm scales with |
where we defined = ||>||| for case of notation. Remark also that
[V[()]] exp(r>)[|==]1 2r exp(r"),
|V²] exp(()) 2r
where the norm of the Hessian follows from the observation that æx has eigenvalues and r².
The following theorem establishes that f(x) = cxp([1=113) not (Lo, -sm-ohh
Theorem A.2. There do not exist constants Lo, I. 2 for which the function f(x)) exp([|=||3) (Lo, In -moothh
Proof. Assume, by contradiction that there exist constants Lo, L1 2 0 which ||v2f(z)| s Lo L1 [(())l
for all R".
This means that
2 eep (x
s Lu 2r exp(r²), for all R"
or equivalently,
To
2r 2
+
exx)(r2) + Lir, for all R".
Clearly, this cannot hold, since the left hand side grows faster than the right hand side as r + co.
Theorem A.3. The function ((x) exp([|x||²) satisfies the second-order characterization of (L, L)-
anisotropic smoothness relative the functionn 6(x) -||>|| in(1 [[=]] for L 1 and
2
Proof. By 36 Lemma 2.5], the second-order characterization of anisotropic smoothness for L = 1 equivalent to
For our particular reference function, this condition becomes
L -- = (1 (V)))))) + Th ((x)V\((<>))
Let us define := 1+ [=)(())] 1 2r exp()=) and recall that Vf(x) 2 cx. Then remains to show that the matrix
exp(r2) L
Mz(x) T
(T 2nx
|
is positive semidefinite for L > 2, uniformly in x E R". Note that we can rewrite
2exp(r2)
4exp(12)
M2(x)= = a L
I+ [aVV
||,||
L
||0||1
==A
21

---

as the weighted sum of two symmetric positive semidefinite matrices. We now show that both weights and are nonnegative for L 2, for any 0, from which the claim follows.
The weight A equals
A(r) = 2cxp(r22 exp(12)
2
2r
L
and has derivative
(2 (2- T,
4r
(
A'(r) exp(12)
+ 4r" = exp(12)
2 1 +
T - 2r
For L 2 2 this yields
A'(r) 2 exp(12) (1
2r
> 0,
meaning that A(r) is strictly increasing. Since A(0) = 2 we conclude that A(r) is nonnegative for 2 0. As for the weight B, remark that
a a/|Vf(>)l (1 + 2r 2 2r exp(()) + 4r exp(2r²),
and
4 eexp(r2)
4r2 exp((2)
||||==
L
L
Therefore, the second coefficient becomes
1 -1
B(r) = 4r exp(1²)
(exp()2)
+ 2r exp((r?
which is nonnegative for L, 2 2 since exp(r²) 2 1
As a second example, we consider the function ((x) = exp(I1=]11)) - 2||x//| which has gradient and Hessian
Vf(=)= = (exp(r²) - 2) x,
f²f(x) = 2 eexp(r²) (T + 2xx )) 47
where we defined := ||x:| for ease of notation. Remark also that
[V(())] 2 |exp(r2) 2) | 2r lexp(r²) 2|,
[(>)(>))| exxp(r>)( +2r)) 4,
where the norm of the Hessian follows from the observation that æx. has eigenvalues and y2 The following theorem establishes that f is not (Lo, L1)-ssnsm -smoohh.
Theorem A.4. There do not exist constants Lo, Li 0 for which the function (xx exp([1=]|²) 2/|x|||2 is (Lo, Li -smooth.
Proof. Assume, by contradiction that there exist constants Lo, Li 2 0 for which
for all x E R". ||V fx))l < Lo + [V(v)l
This means that
To + 2r |exp(13)-0) 2/,
for all TR..
or equivalently,
Lu 44 + Lit (exp(r2) 2
1 2 <
for all x E R
2exp(r2)
exp(r2)
Clearly, this cannot hold, since the left hand side grows faster than the right hand side as + co.
Theorem A.5. The function [(x) ex) 2|| satisfies the second-orler characterization of (T., a))-nisotroppc smoothness relative the reference function x(x) -||=||| - In(1 || for L 1 and L = 10.
22

---

Proof. By [36] Lemma 2.5], the second-orde characterization of anisotropic smoothness for L = 1
equivalent
f(x) < v [Vo'(v
For our particular reference function, this condition becomes
L --v =3 (1+ [V> (लेा V[<+\\
Let us define := 1+ [ = =1+2r exp((>)) - 2 and recall that Vf(x) 2 (exp(r²)- - 2)
Then it remains show that the matrix
exp(("))
Mx(=)= = a T [
2.
(T 2rx )) +
|>||
L
is positive semidefinite for L = 10, uniformly in R., Note that we can rewrite
ML(x)= = (a 2exp(r²)
4 L L
+
a [lVf(())]
4exp(r2)
|
2.
L
|
Our proof strategy goes follows. First, we show that A(r) 0.8 for all 2 0. Since the eigenvalues of vo [oll are 0 and 1, and since adding a multiple of the identity matrix shifts the eigenvalues by that multiple, it then suffices to show that B(r) 2 -0.8 for r 2 0. This then implies positive
semidefiniteness of Mr and proves the claim.
We start by lower bounding
2 exx((22)
4
+ 2r (exp(r2) 2xx)(r²)
4
A(r) = a
T.
+ T.
T.
+
T.
We distinguish three cases. If exp(r²)
< 2, then (exp(12) - 2 = 2 - -exp(r?), and hence
A(r) = 1 + 2r (2 - exx((22)
22xp(r²)
+
L
=
+ 4r 2exp(r²)
(r+
1
+
L
r+ 1
4
> >1+4r
L
+ L L
=
+ =
L
On the other hand, if exp(r2) 2 2, then (exp(12) - -2| = exp(r>2 - 2, and hence
A(r) + (exp(r2) - 2) 2exp(r")
4
2xxp(r") 4
I
L.
When additionally exp(r?) S 3, then clearly A(r) 2 1 1 0.8. Thus, it remains verify the case exp(r²) > 3, i.e. r
> VIn(3). We compute the derivative
A'(r) = exp()²) 2
4r + 4r² -xx((x²)
2 (2-
1
+
[( -2r) ) - 4.
( 1 -2r) 2
2r
L
L
Since exp(12) 2 3 this yields
) 2)
2 - L +/
1
3 L
1
3 0
A'(r) > 3
4=
+
-
2r
2 2
100
meaning that A(r) is strictly increasing for 2 v /nn(3. Since A(
/ /3)(3)
1+2 1 - 0.8.
we conclude that A(r) 2 0.8 for r 2 Vln3). Putting everything together, we have shown that A(r) 2 0.8 for 0. As for the weight B, remark that
a al\Vf(=)] = (1 + 2r exp((>) - 2/)2r exp(r?) - 2/ 2 4r² (exp(r?) - 2)²
and
4 eexp(r2)
4r exp(r2)
||
10
23

---

Therefore, the second coefficient is lower bounded by
B(r) 2 4n (cexp(>>) - -2)² exp(r2) - 4r² (xx((r))² -4exp(r))) + exp(r2)
10
10
Let us define = = 2 and w = (x) 2 Then we can express this lower bound as
Q(w, 2) == (4w² 16.4w + +1).
The quadratic factor is negative only when 1.6 < w < 2.5, and is minimized at w" = 2.05 where attains the minimum value -0.81. remains lower bound Q(w, 2) for ln(1.6) < 2 < (n.2.5). We have
Qu 2) 0.81 -0.81 10.81 > -0.8.
We conclude that B(r) 2 0.8 for r 2 0, which completes the proof.
A.4
Connection to (p, Lo, L smoothness
This section establishes connection between anisotropic smoothness and (p. Lu, Lp) -mmoohhhnsssss which arguably describes the most important subset of (-smooth functions (28)
Definition A.6 ((28) Definition 3])- A twice continuously differentiable function f : R -, R is
(p, Lo, p -mmothh for constants Lo, L, 2 0 if f(x)) s Lo + ->]]V( for all E R2.
Note that the original definition is slightly more general, as it encompasses functions without full domain and only requires the Hessian upper bound almost everywhere.
Theorem A.7. Suppose that a univariate function f R + is (p. Lus Lp)-smooth for constants p. Lo, T.p 2 O, with p S 2. Then, satisfies the second-order characterization of [.), T.)-anisotropic smoothness relative to the reference function ((x) -||=|| In(1 ||>||) for L and Z 2 max Lo, Lp}.
Proof. By 36 Lemma 2.5], the second-order characterization of anisotropic smoothness for L = 1 equivalent to
-->v²f(x) =
For our particular reference function and because f is univariate, this condition becomes
f=) < (1 + If'(z))2 1 fz)))+ f())²
now prove that this upper bound holds. By (p. Lo, Lp) -mootthnsss we have for all x E R that
Lo L
< L 11)(())
We distinguish two cases. If (z)) S 1, then -- S 4. 4. and for L 2 2 Amax(Lo, Lp}
we obtain L f"(x) I 1, which establishes the required upper bound. If [f')))) > 1, then follows from p 2 and max (To, [.p] that
Lo Le -- (²) T. (15())
which implies the required upper bound.
Remark that most examples of univariate (p, Lo. -smoohh functions in (88 satisfy S 2. Besides polynomials, this includes exponential functions at with a > 1, and double exponentials ((b)) with
a, b >
A.5 Verification of assumptions on the reference functions
Throughout this work, we have made a number of assumptions which only relate to the reference
function 6, i.e., Assumptions 2.1 2.2 2. and 3.5 This section explicitly verifies these assumptions where the kernel function one the following:
for isotoopic reference functions @
h (x) = cosh(a)) - 1, h2(2r) exp(Iar) (Ir) |a:| 1, hz(x)) = -|x] l
In(1 - [æ])-
To this end, the following results from (36] Table will prove useful:
h (v) arcsinh
h (v) In(1 + (vl) sgn(v).
hy (v) --'Mi
h (v) /
h (v) 1+|=l*
h²" (v) = (1+1b))>

---

Assumptions
2.1 and 2.2
These assumptions were proven for h1 h2, hy in [36].
Assumption 2.10
To verify (i), i.e., whether ('(v) is decreasing on R4, check if for y
y
0,
8²
or equivalently, yh yh""(y) < 1/" (y). This holds for h1, h2. and h3. Part (ii) holds, since
lim yh 1 (v) = lim yhg #
" (v) =
lim yhg (v) = 0. g-000
80000
Also (iii) is satisfied, since hi and hy scale logarithmically and hg is bounded. In particular,
lim d'i(()) = (e((e()))
lim +00
y0+ y
lim
lim dln(u) +00
lim
(eu(())))
lim 1 = 0. +00
4-+00
Here we used the fact that arcsinh(y) = In(y + v + 1). Thus, Assumption 2.10 holds for h1, h2 and hg.
Assumption
3.5
The kernel functions have the following Taylor expansions:
h1
(2n)!
h2
|ar
|n|
12!
21
31
n=2
DC
hx(x)= =
Σ
1=1
7
We remark in particular that each summand is nonnegative, and that the term with the lowest degree equals =²/2 for all three kernel functions. This immediately implies hx(x) 2 =²22 and h,(x) = = + olx2) as 0, for (), and proves that the assumption holds for h1, h2 and h3.
A.6 Generalized smoothness of regularized neural networks with quadratic loss
The main goal of this section is to investigate the generalized smoothness of the quadratic loss of deep neural network, and in particular, whether Assumption 2.8 holds. turns out that, under sufficient regularization, this is indeed the case. To establish this result, we need to bound the gradient and Hessian norm of the loss by polynomial of an appropriate degree.
Consider a deep N-layer neural network with quadratic loss. Each layer- - of which we denote the index by Njo,N-1] - consists of weights W. E R xx,, bias term by R and componentwise activation function M, 12*++ + IR*++1, The final mapping N is assumed to be the identity mapping, common regression problems. For given data point _ and corresponding label E R"x, training this network entails minimizing the loss function
CW + b.)...)) b²) .1
(14)
Neural networks usually trained large of pairs { ." " JieNy in which case the total loss becomes a summation of the losses for each individual pair. To simplify the presentation, we proceed with / 1, i.e., with (14). but the results are easily extended the case I > 1.
Let us denote intermediate variables *++1 = fe(x',
EeWWa + b²) E R where we use the convention z H, and define the vectorized weights and bias at layer by wt
(oo(WW)TBTT) E R (1++))) Then the loss 14 can compactly written as -| vll
25

---

The minimization of the loss (4 can then be interpreted as an optimal control problem (OCP) of horizon N with states x² E T and inputs w' E IR 1 i.c.
minimize
Σ le w²) + (x(x*) subject
x+ fe(a', w N
where x. = 8. l fort No..N-1 and la (x(xx) || y l In the context of OCPs, the functions fi(e", w²) Ee(Wat b*) are called the dynamics, and have gradients
Ver w0) =W, (W) +b))TT
E R 1
ver Sele", (()(",,w')= = (sr 1me-1
(W + +b)) (x' @ Inm-1)
(15)
E (0n--mm4xmma
Let = (x2 ..... N )T and w w- "W."...,,N ....,"WIITT"" denote the vectors containing all states and inputs respectively. We aim to derive expressions for the gradient and Hessian of the loss function (14) with respect to w. To that end, we use a standard idea in optimal control and eliminate the dynamics. This approach is known as single shooting. Following Bertsekas (2) $1.91, we introduce mappings
(w) = (e(F)(w)), w) = x1t11 t= t= N - 1.
with F-1(w) = T. Let (w) = (w) ....,, TT) and note that 2 Eq. (1.246) and below]
V w
V wo fo V. fi Vo ... V 1fN-1
V x2 f2 ...
VAN fNN-
VF(w)=
(16)
JN-1
We highlight that the block columns correspond to the gradients of the individual mappings F,, i.e.,
F(ww) = (w) VF2(w)
Fx(w)).
Therefore, the OCP, and equivalently, the neural network training problem, compactly written as minimize J(w) == (x(NN(()) = 511 51
(17)
or
The gradient of J is then easily expressed by
V V. (w)((x( v). Obtaining an expression for the Hessian is more involved. We follow
(18)
(2 $1.91, which uses the
Lagrangian function of the OCP with multipliers X = (X AN..,,ATT T
T
E R EM ne+1, i.c.
N-1
L(x, w. A) = (N(x) + E ( - x I
The central idea is to express VJ(ww) in terms of V V.L(a, w. A) and V I. w. A). The computation of V J(w( is simplified by selecting an appropriate multiplier, which is recursively defined by
N FN A' = (V. f1
E R
ER"
1 1=
This yields for example A = VaiVV VAN IN-I((FN - -y) Bertsekas 12 Eq. (1.242)) establishes that
v²J(w)= - V VFW L(F(w) w. ()VF(w) 2VF(w) V2 L(F(), w. A) V2 L(F(w), w, A).
(19)
The following theorem establishes that, under sufficient regularization, the regularized loss function of neural network training satisfies Assumption 2.8 and consequently satisfies the generalized smoothness notions investigated in this work. We emphasize that the rather restrictive bound on power P of the regularizer can be relaxed significantly by exploiting the structure of V F(w) (cf. (66)
and further working out the Hessian (2 (cf. (19)) before upper bounding its norm. However, for simplicity, the proof below immediately uses submultiplcaatiityy of the matrix norm (cf. 21
26

---

Theorem A.8. Consider the regularized neural network training problem with objective
Jww) [ww + k||wal1
where J (w) is the quadratic loss of an N N-layer network defined in 17 Suppose that the mappings E, are bounded and have bounded first and second derivatives for E Ni..N- and that the mapping
EN-1 is the identity map. If P 2 3N + 2, then the following statements hold for any k. >> 0.
(i) For any L1 O there exists Lo > 0 such that J is (Lo, L1)- -m)oshhhth
ii If o satisfies Assumptions 2.2 a 2.10 then for any L O. there exists L > 0 such that
J satisfies the second-order characterization of (L, -anisorropii smoothness.
Proof. By boundedness of Σx, also the states x=+1 are bounded for / E Nio.N-2j. whereas we note that ||
Fx (w)l = [[] From the gradient expressions 15
D. we observe that
| fell = (1) and || zt fell
([]), and by (T6) we obtain || w [[[ ((-)) ).
Therefore, the gradient (w) as defined in (18) is upper bounded by polynomial of degree N in
||lml i.e., / [[=]l = 0[
|| )N Consequently.
Jww(ll 2 K x|||
P-1 [[J(w)]| xP][w|||- P-1 -
(20)
As for the Hessian norm, we have by
19p that
[V'(w)] = [1 22
L(F(w), x)
V L(F(w); w. w.A))
su [(F(())
V wa
aa I (F((),, w, X)
(21)
We compute the gradient of the Lagrangian with respect to r and w
V La, w, A) (V=' ".r,,w)) w())a="-
t= I.
V N [2,, w, A) = (x - -D) A V ai L(x, w. A) = fel' w 1
t= 0, N O=....,NN-1
Clearly, 2 [.(F(w), w, A) is block diagonal. The last block V2 forward to compute. For the other ones, we proceed by rewriting
NNAN aN Mx, W, Inn is straight-
In. (V w())) X V2 La, w, A) = vec((V felat, w²))))))))))))) )))))+++ X' (2++TT
Here we used the fact that vec(2) = for any vector, and vec(IBA) = (AT @ I) vec(B for any matrices A, and identity matrix of compatible dimensions. This yields
O Vvec((V... w())
V L(x, w. A) = (x+22 2 Ini)
Ox'
From the fact that || O(11w0| for 1. = 0 O.....N obtain
N - 1, and from boundedness of EY we
22 L(x, w. A)II O1] ([-
N
and follows that L(x, w, A [[ Similar arguments can be used show that also
the other Hessian blocks of the Lagrangian satisfy a similar upper bound. In conclusion, we obtain [|] )2 = [ (1 ). It follows immediately that [|V² is
that [w))l upper bounded by polynomial of degree 3.V in [|w]]. And since by (20) the gradient | [(w) is
lower bounded by polynomial of degree 3.V + 1 in ||l|| with strictly positive leading coefficient,
we conclude that Assumption 2.8 holds. The claims then follow by Theorems 2.9 and 2.11
B Auxiliary results
Lemma B.1 (Power Mean inequality). Letp > >
Then,
1/P
1/4
m
m
P
ag
m
m
i=1
27

---

Proof. Note that the function ((a) 0/ is concave for a > 0 since < By Jensen's 's inequality. this implies
%/-
m =
m = m7
04
aas ?
p(aass
m
m
Raising both sides to the power 1/9 establishes the claim.
Lemma B.2. Let F R 7 Rm be mapping satisfying, for all E R",
|F a||=1| b||ar|1
where 0 and b 0. Then, for all RR"
b
|F(2)) 2 vol|=||
|-||
Proof. In the proof we write r r= ||a=|| for simplicity. The given inequality becomes:
[[F())] 2 ar br (ar² 6).
We distinguish two cases:
Case 1: p2 &. In this case the given lower bound is nonnegative. Taking the square root yields
[F(x)]| 2 (rr(2r2 - -b) r² V ar - b.
We apply the inequality v1 2 for S 2 S by letting ar= E (0, 1]. Then = vary
b
(1
b
ar b V ar? 1
ar 2 var
= Var
ar?
ar?
ar
Multiplying both sides by r², we obtain
[F(() (Var
b Var
Var
Va
Case 2: y2 < b. The claim follows immediately by nonnegativity of the norm and from the fact that the desired lower bound negative in this case, i.e.,
[((x)] 2
(ar - = =vr Va" r.
Va
Lemma B.3. Suppose that Assumption 3.5 holds, and that point R" satisfies
X \ - G²
2
where G is defined in 12 Then,
Vo S Vgg.
Proof. The bound d(x)= 2 2 yields
Xg2
VVV(((())) <
2 S ((V5g).
The claim then follows by Φ h || ||. nonnegativity of g and strict monotonicity of h.
C Missing proofs of section
C.1 Proof theorem 2.4
Proof. This proposition is direct combination of 336
Propositions 2.6 & 2.9].
28

---

C.2 Proof of theorem 2.9
Proof. By Assumption
2.8 we have
V2 fx))lF
I lim sup PR[[=]]]
QR
sup
lim sup
[ |
|V [v)(
- QR+1 (I|=])
bR+1
||]|||
|V2 [V
By nonnegativity of
(=(] we conclude that lim|jz|]==oo
Thus, for any
L1 > 0 there exists 8 > 0 such that
|||||| > 8 + [<>il>) S L
Moreover, by continuity of V f. we know that [<>]() p is bounded on the compact set Q2 == {or ||>||| I 6}. We conclude that f (Lo. -smoohh with Lo max,en fx))(.)..
C.3 Proof of theorem 2.11
Proof. Fix an arbitrary L > 0 and, for ease of notation, define
Hx(x) == VZ
lim - [Hx())] 0, then for any > 0 there exists such that
||<||| > = | <.
Therefore, the continuous function x - x (a:) is bounded on the compact set Ω == |||||||||| o)
and for all IR 12 we know that (x)] S c. We conclude that if lim - | then x (z)]l is bounded R", and because Amax (H)))) s { this would prove the claim. By equivalence norms, it suffices to show boundedness of any norm; we proceed with the Frobenius norm (x)x ||. Because for isotropic reference functions
v² = - (Ilvll)
yy'
h² (Ilvll)
(I
yy
|vvl
||
it follows that
[H)))) 1 (I (v5(0))
(1- (1-11>)" (ONE!
|
(h (IL (" pR[[
[2- (v(()]
Taking the limes superior and using Assumption 2.10 yiclds
(I= + | [-'([I--V(000 pn(ll=l]))
lim sup [x(x))]
lim sup
hh" hh"
||--VV((=| 1
| +000
||00
C2
|1~' \V
sup
[V]'(( pR([
[-'Vf(>)
||||-->0
C2
+ h/" (L- ((=+)))
simsuu
T.- T. (1]ll=))))
T, (1-10++2((=01)
||||0>0
aRC2 + an/h" (R=1)))(((=1))) =0
lim sup
bR+1 |z]||
bR+1||/|
|
Here, the third step used the fact that "''(x// is decreasing on R4 in combination with
(L-'vf(>) 2 L 44+1 ([]=]]). Since || 2 O. we conclude ai [xx(r)] = 0.
C.4 Proof of theorem 2.12
Lemma C.1 (Gradient norm lower bound). Consider the phase retrieval problem with objective
(4) and suppose that that the vectors {as (mm) span R Then, there exists a constant > 0 which
depends the measurement vectors (o am (but not on x)) such that
|V > 3
1 |||=|||
29

---

Proof. Clearly, the gradient norm can be lower bounded by
IVf(2)] =
Σ (a a
Σ
1 |||
Let us further lower bound | (a, x) a in terms of ||=|||- For ease of notation, we denote
g(x:= |G(z)]] where ((z) := -i (ag x: )aa Observe that y is positively homogeneous of
degree 37 Definition 13.4], since for any
m
m
g(xx)=
Σ (Aa, )))aa))))
x
( 2) 01 g²))
For any E IR we have g(z) || 1 (1/ and hence it suffices lower bound g the unit sphere gn-1 := {a E R" |||||| = 13. Remark that achieves a minimum over @" because S
compact and g is continuous. Denote this minimum by C' min g(u), such that
(xx) 2 C||z/|².
If > 0, then the proof is done. For this reason, we show by contradiction that the case = 0 not possible. If C O, there exists u² gn-1 such that
G(u") Σ (aTut))0 u =0. i=1
follows that
m
n- G(u*) = Σ
aa 11 =
and since (a,Jur "² 2 we conclude that a. u² for 1,... m, ie.. is orthogonal to all measurement vectors. Therefore, u* (span {a1,... ... (m))T (RR") {0). This results in contradiction, since 2² = 0 & g"-1, We conclude that C > 0, which proves the claim.
Proof. The objective f a fourth-order polynomial in the variables æ. Hence, one easily verifies that
|a,111
|x||² +
Σ 2
where the upper bound is polynomial of degree 2 in | Moreover, by lemma C.1 the gradient norm fx)) can be lower bounded by a polynomial of degree 3 in | with strictly positive leading coefficient. Therefore, Assumption 2.80hlld holds. Theorem 2.12(1) now follows directly from Theorem 2.9 and Theorem 2. 1iii) from Theorem 2.11
C.5 Proof of theorem 2.13
Lemma C.2 (Gradient norm lower bound). Consider the matrix factoriaaaoo problem with objective 5 Then the gradient norm can be lower bounded by
|V 2 n
- -
Proof. We have that
| = trace trace(V VF(U) = trace (UUT QUUUT -
LTTTTTUTTTTTTT 2U YUUTU +UTYYU)
trace(UTTUTTuTTu 103-2tracs (trace(UTYUUTTU) + trace(U TYYU)
trace(U UuuTeuuTu ||
30

---

Remark that U is symmetric and positive semi-definice with eigenvalues A1. An 2 0. There- fore, trace U (U Σi= A; = | and
3
trace(U COTTUTT U) = trace((U ( -
Ag.
1=1
The power mean inequality (lemma B.1
with = 3 and yields
1/3
1
n
-
2
A
72
n
1=1
1=1
and hence
3
trace(U SUTTUUT UU U) = ())
Σ 2ラ
n
1 n
n² 11
Since f is a fourth-order polynomial in the variables U. the Hessian norm can be upper bounded by a second-order polynomial in ||U|]] By combining lemmas B.2 and C.2 we conclude that the gradient norm is lower bounded by a polynomial of degree 3 in [|U]] with strictly positive leading coefficient. Therefore, Assumption 2.8 holds. The claim then respectively.
Proof. We trace the steps from Theorem 2.12.
follows from Theorems 2.9 and 2.11
C.6 Proof of theorem 2.14
Lemma C.3 (Gradient norm lower bound). Consider the asymmetric matrix factorization problem with objective (6) Denote V = max( ([))) Then,
f H|ll 2 v² 4(1 + K) ||
Proof. We have that
/W H) 12 J(W, H) [W The first term can be lower bounded by
V fWW H
trace((H W - YT) + (IW
w()
traco( (H T Y (WH -YHH
+ 2k| 11 traco(W
(WH- -Y)H + W
[WHH I 2 trace
HY (HHH HY TY
+ 2k| W1| trace( W
(WH-Y)H)) ) +
2 | 1/ ||Y'TT +x [ TIAHH WHH
- (
2 | 2x| W trace H WH)
- -2<////1////11|||11),,++++ I
||X1|=/| [ WHI
-|<]|| | I
--|||X|| || - 11 |||||||/|| + 111
Here the second to last step used the cyelic property of the trace. In similar way, obtain
(W,
2 || || 2*| ||||>|W]]| + 1
Putting this all together, we have that
| (WW, 12 2 x² (lll 11 + || 2(1 + +||l||r (111)-1111) + || | 26 4(1 +
31

---

[)) ||>||| [ + v 1 [ + H | -||,=|| and we remark that ||]||| + co if and only V oC.
Proof. Let r be the concatenation of vec(W) and vee H). and let V := max ([We,, [H) Then
We now trace the steps from Theorem 2.12 Since is a fourth- -oddr polynomial in the variables
I, the Hessian norm can be upper bounded by second-order polynomial in || lr] By combining
lemmas B.2 and C.3 with || 2 V 2 -|| we conclude that the gradient norm is lower bounded by
a polynomıal of degree 3 in | with strictly positive leading coefficient. Therefore, Assumption 2.8
holds. The claim then follows from Theorems 2.9 and 2.11 respectively.
C.7 Proof of theorem 2.15
We first establish the following lemma.
Lemma C.4. Consider the Burer-Montein factorization denote the augmented Lagrangian with penalty parameter of this factorized problem. Then, there exist constants C₁ Co 2 0 such that
of the MaxCut-type SDP 7 and let Lg
28 2 |||||
V LoL,( (11l
C1
||=||||| Co
Proof. The gradient of the augmented Lagrangian with respect to is
v ( I(()))))
vaLe(E,))
and since f and A are quadratic in can lower bound its norm by
|V v) 2 B
1
|A(=)))))
- [Vf(2=)] - |
2
3 V 2
A(x))))))
C111=|1 - Co.
The constraint mapping A has the particular form
|| 112
A(z) = diVg(VVV)) - 1,, = diag
(
xn)
In =
||
and therefore the gradient of the augmenting term equals
||
2x1
V (1A(G))))= =
-xr
||
2xn
Since |// Σi= 1 ||| 1 P 1 Em
|
can apply the power mean inequality lemma B.
with and = 2. This yields
1/8
1/2
1/ |//
7/-
|0:116
|
2/2
Thus |/
2 1/ | or ||w/||
2
||00|| 3. Putting everything together, we obtain
VoL
2 8
V=
[1((2)))))
|
|
Ci Cillal Co
2 2. |ll
2/||2/| - || - Co
2/3
| 3 2,||
C |||||||| Co.
n
The claim follows by redefining the constant C₁.
32

---

We now present the proof of Theorem 2.15
Proof. We again trace the steps from Theorem 2.12 Since for fixed multipliers y, the augmented Lagrangian Ls is fourth-order polynomial in the variables it follows that the Hessian norm can be upper bounded by a second-order polynomial in ||>|]. Moreover, from lemma C.4 we know that the gradient norm is lower bounded by polynomial of degree 3 in || with strictly positive leading coefficient. Therefore, Assumption 2.8 holds. The claim then follows from Theorems 2.9 and 2.11 respectively.
D Missing proofs of section 3
D.1 Proof of theorem 3.1
Proof. First, under Assumption 2.2
the iteration map T, i mapping with Jacobian
Since Amax
s T.T. and < 1/2 it follows that
Amin (JT (JTz,L-((x)) 2 1 -
Hence, det JT ( (x) # 0 for all x E R". Second, denote the of unstable fixed points
A" x T,, xxx") = x", max (A, 1}
For any stationary point x², satisfying fz²*) O, we know that x²' = I
max maxTA (-- max - (z*). and therefore
max -1(1->2-1799(
Hence, if Amin (v²f(z*) < 0, then max, [A (J, 1.
We conclude that X At.
Thus, we have established conditions of 24 Corollary 1), from which the claim follows.
D.2 Proof of theorem 3.2
Proof. First, remark that U is an open set. For x E U we have by 36 Lemma 1.3] that
Vo' ( = ( (.-
min [1, L f(r)]
sign (
min ||-') 1 1) [-\v(()).
We partition T into two sets
U1: 12" | < <1}, U2 E
ER" | ||- > 1].
If oF U1, then V
Thus, T. is continuously differentiable with locally Lipschitz continuous Jacobian on U1. If E U2. then V (I- = V/(=)/ [()]]- Since the function + */||=|l is twice continuously differentiable on I2"" \ [0} and since f C²+ continuously differentiable with locally Lipschitz continuous Jacobian on Uz- Since U = U1 U U2 we conclude that JT 7, is locally Lipschitz continuous on U. By the same arguments as in the proof of Theorem 3.1
follows that T, T-
we conclude that
Amin (JT, --) 2 -1 0.
and that for any x² E X the Jacobian JT (x= is symmetric and has eigenvalue of absolute value strictly greater than 1. The claim now follows immediately by applying (10) Proposition 2.5].
33

---

D.3 Proof of theorem 3.6
Henceforth, we assume that f is (L, -)anisottoppillly smooth relative @, without further mention. We first describe the following descent lemma.
Lemma D.1 (Descent lemma). Suppose that Assumption 3.5 holds. Lery = 9/L, a E (0. and let (x)) keN denote a preconditioned gradient sequence, i..., x = (xx for k E N. Then,
f(x f(x*)( - ? (VV
22
Proof.
By 36 SC.1] we have
f( f(x=(((())
XL (AV
a
The claim then follows from ((x) 2 1|=11/22
We now establish the two key lemmas for our analysis. First, we establish that the objective does not decrease much, then the iterates will remain close the initial point.
Lemma D.2 (Improve or localize). Suppose that Assumption 3.5 holds. Let (kEN denote preconditioned gradient sequence, i.e., k+1 -T,21 ) for k E N. Then, for any 1 2
| - x01 ( - -(x))).
Proof. By consecutively applying the triangle inequality, Gauchy-Schwarp and lemma D.
we obtain
|1-" -
x
| 5
11
1
| x²¹ 112
1/2
Vot (AV
1)1
S 2xyt -
Second, we show that the region in which the iterates of algorithm reemain stuck for at least [T] iterations (if initialized there) is small. We do this by showing that there exists a point, not to far away, which does yield sufficient decrease.
Lemma D.3 (Coupling sequence). Suppose that Assumptions 3.3 and 3.5 holds. Let a point i e Rn satisfy Amin (H)( S -ypE where S L Moreover let (x )eEN (y kEN denote two p
preconditioned gradient sequences, i.e., k- = (x and yh+ -T,,' ) for l E N, which additionally satisfy
max 11|2 æ|1, 11y +1}} S yr,
and x yy =rrue,,
where E is the minimum eigenvector of H²) and ro > w = = 22- Then,
min
- (f(=)))) f(y)) f(19) s -F.
Proof. By contradiction, assume that min - f(20), f(20)} -F. Lemma D.2 states that for any < T
max {||=² - -11, I/v' - } s max { [|k² - x 11 / |1] + max 111000 - -Tll, 1115 - -
s / 2xxT max (f(2)) f(xx)((x))))))) f(y ff
f(y 7r
(22)
s 22xTTF + rr 52.
34

---

Here the last step follows from S 12' Denote by == x² - y² the difference between the two sequences. Then, it follows by the mean value theorem that
2 = = (Ax" - VØ (Ay')] = - -HH-))²²² - -7
(1 (1-77) 20
Σ (1-1H)² A
1=0
p(r+1)
s(t+1)
where H: (3) and 4, == So [Hx +((x' y/)) HH] d0. We show by induction that
||a(t)]1 - |lo(t)ll vt E 10, 77.
(23)
For the base case 0, the claim holds trivially, since [|]())] = S 2 [|](0)]]. For the induction step, we assume that the claim holds for t and show that it also holds for t + 1. Since 20 lies along the minimum eigenvector of H (T), we have for any 7 S
|| S |p(T)]l [q())]| = 211p(r)]l 2][(1 - HH) 2 2(1 + + voo where I' :=== -Amin (H2 (T)). By Lipschitz-continuity of H (cfr. Assumption
3.3 we have
=11, Ilv - x|l} pZ. ||r|l S / plyy - - 0(''(( I') pmax {||=*
Combined with 2yp2T= = 1/2, we obtain
lla(t + +1]1 s 7 7 (1 (1-77)) A122 S 1Tp2 Σ |1 (1 - 771" |||
1=0
1=0
< 2 Σ
+ >T)rrr S 2yp22T(1 (1)))))
1=0
=2yp2T1ppt + 1)ll - 2 llp(t + 1)ll-
This completes the proof of
In turn, we conclude that
max {11= - E11, 1ly =|}} > | [P(T)] 1
- (l(())]] 2 [P(())] - [P((T) (
2 2
|p(7)l (1+ (1+)1)]>r 2x yro > Z.
4
Here we used (1 + x))²= 2 2 for x E (0, 1]. This contradicts (2 and completes the proof.
By combining lemma D.2 and lemma D.3 we can show that the iterates of algorithm 1 will escape from a strict saddle point with high probability.
Lemma D.4 (Escaping strict saddle points). Suppose that a point T satisfies
g² and ( (AVT))))))))) S -Vpe
x (VV S
2
for é >> O small enough. Let x0 = I + 7E where & is sampled uniformly from a ball with radius and that ++1 2t Vo" (AV for E N. Then,
P (((T)) (((x7)- f(ā) S
F
Lvn
x 228-x
Vpe
Proof. We define Xunck as in 18 Lemma 20], i.e..
Xstuck : (2 || -l < or and f(x7) f(x") -F where k+1 Txx((=²) for K E N).
35

---

By the same arguments as in [88 Lemma 20] we conclude that
Lvn
IP (xx E Ktuck) -
Vpc X x228-3 x
We now proceed by showing that f(x") - f()) S - _ if x²d & Kauck By anisotropic smoothness, we have
f(x") - f(t) 0t + (VV A AAl + (AV
By monotonicity of h, the triangle inequality and lemma B.3 we have
f(x)) f(ā) = n(IlEll + (AV - hbr + vxg) - 2 h(2r).
Here, the last step uses the bound vAg I r, which follows from g min {1, 1 For sufficiently small which holds for sufficiently small we can further bound l((2r) S (2r)
vx
gr This yields, again using S L2 that f(*") f(ā) दे F/2. We conclude that if $ Ksucck then
F F 2
(t) f(x")) + -f(x")-f(a))
- f(i)] S -
2
Theorem 3.6 follows by combining lemmas D.I and D.4
Proof. Let the total number of iterations of algorithm D be
{ [ fT)
(
mm) 8I(((x0)) f*)
max {50x* 200 min [. x²]
T 8 max
F , 27
Lea
8L( f*)
max (50x², 200xx
LE
Using max (50x*, 220xx0000 s 25 -5xx $284242444 for all x > 1/2 and, we find
T LV Vp
x// x/ x22 x L'Vn (f(=)) f*) 211 28 228-x
Vpe
Le
and since for x > 1/ we have x22-x < 20 1:00x/2 it follows that
T T x225 1.2 1.2v/ (f(x0) 2302 x/4
Vpc
Vpc
Lea
Selecting Cmax 2-39 i.e. x 4log2
(209 L2 L'VTA,) VpLc"128
we obtain
T LLV/ Vpc
X 228-x 8.
Observe that G such that X - (XV < o implies X oVV 2
With probability at least - 6, algorithm aadds a perturbation at most T/4T times to a point, because by lemma D.4 we have
T T
f(x 5
47 SS.
Excluding the iterations which follow within T steps after adding a perturbation, have at most 87/4 iterations left. They either satisfy -Vo'VV" (**)(())) ))) z o or are e-second-order stationary points. Among these, at most T/4 are not second-order stationary points, because by lemma D.1 we have
g2
((=))
-
<
2x 2
Therefore, we conclude that least T/2 iterations of algorithm are c-second-order stationary points.
36


Reviews:
[{"review_id": "mdf9i4dx6K", "reviewer": "Reviewer_K1tP", "summary": "The paper studies nonconvex optimization under a generalized smoothness condition, called $(L,\\bar{L})$-anisotropic smoothness, introduced in [32]. This condition generalizes both the standard Lipschitz smoothness and the $(L_0,L_1)$-smoothness proposed in [38]. The latter has been empirically validated for LSTMs in [38], and later for the transformers in [36], where gradient clipping was shown to be effective.\n\nBuilding on this, the paper takes an important step forward by theoretically showing that several well-known standard nonconvex problems, such as phase retrieval and matrix factorization, satisfy both the $(L_0,L_1)$-smoothness and the $(L,\\bar{L})$-anisotropic smoothness conditions. This provides additional support for their practical relevance. Furthermore, the paper is the first to show that (perturbed) nonlinearly preconditioned gradient method, including gradient clipping, can (efficiently) escape saddle points, under these relaxed smoothness assumptions.", "questions": "Theorem 3.2: Can you provide an insight why a set $U$ needs to be measure one? I first need some explanation why $||\\nabla f(x)||$ and $\\bar{L}$ are related here.", "limitations": "The paper does not explicitly state its limitations, but I did not observe any major ones.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. The paper presents that several well-known nonconvex problems satisfy the $(L,\\bar{L})$-anisotropic smoothness condition, by first identifying a sufficient condition (Assumption 2.8), formulated in terms of polynomials, and then verifying that these examples satisfy this assumptioin. This offers a valuable theoretical justification for analyzing the problems under this relaxed condition, beyond the traditional Lipschitz smoothness, which was lacking in prior work. I would like to point out one relevant reference that appears to be missing, which also explores a relaxed smoothness condition for the phase retrieval problem:\n\n- Bolte, Sabach, Teboulle and Vaisbourd, First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems, SIAM Journal of Optimization, 2018.\n\n2. As the authors note, extending saddle point escape guarantees from the standard Lipschitz smoothness setting to the more general $(L,\\bar{L})$-anisotropic smoothness is nontrivial, which especially required using a recent extension of the stable-center manifold theorem [8]. This extension strengthens the theoretical foundation for the empirical success of gradient clipping fin modern neural network training, where such relaxed smoothness conditions may hold, and represents a meaningful contribution.\n\n* Although the authors provide careful explanations and examples of $(L,\\bar{L})$-anisotropic smoothness condition, the geometric intuition behind the definition and properties, particularly in Definition 2.3 and Proposition 2.4, remains difficult to grasp due to their complexity. While I understand this may be hard to elaborate further within the page limit, I recommend that the authors guide interested readers to [32] for more geometric intuition, and consider adding a brief pointer in the revised version.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe thank you for your encouraging feedback.\n\n---\n\n**Suggestion:** Another relevant reference.\n\n**Response:** Thank you for bringing this relevant reference to our attention. We include it accordingly.\n\n---\n\n**Suggestion:** Guide readers to [32] for a geometric intuition behind $(L, \\bar L)$-anisotropic smoothness.\n\n**Response:** Thank you for this suggestion. We will add an explicit pointer to [32, p2], which links anisotropic smoothness to the related concept of $\\Phi$-convexity and provides a visualization of the latter. For a deeper geometric intuition, we believe it is also worth pointing the interested reader to the related works [23, 31] on $\\Phi$-convexity. \n\n---\n\n**Question:** Theorem 3.2: Why does $U$ need to be measure one, and why are $\\Vert \\nabla f(x) \\Vert$ and $\\bar L$ related?\n\n**Response:** The recent extension of the stable-center manifold theorem to nonsmooth iteration maps [8, Prop. 2.5] requires the iteration map $T_{\\gamma, \\lambda}$ to be continuously differentiable on *a set of measure one*.\nThis is the case if $\\nabla \\phi^*(\\bar L^{-1}\\nabla f(\\cdot))$ is continuously differentiable almost everywhere.\n\nFor $\\phi = h(\\Vert \\cdot \\Vert)$ with $h = \\frac{1}{2} \\Vert \\cdot \\Vert^2 + \\delta_{[-1, 1]}$ we have that\n\n$$\n    \\nabla \\phi^*(\\bar L^{-1} \\nabla f(x)) = \\min \\left( \\frac{1}{\\Vert \\bar L^{-1} \\nabla f(x) \\Vert}, 1 \\right) \\bar L^{-1} \\nabla f(x),\n$$\n\nwhich is potentially non-differentiable at points $x$ for which $\\Vert \\bar L^{-1} \\nabla f(x) \\Vert = 1$.\nIf $U$ has measure one, then $\\nabla \\phi^*(\\bar L^{-1}\\nabla f(\\cdot))$ is continuously differentiable almost everywhere, as required by [8, Prop. 2.5].\nWe also refer to Question 3 of Reviewer M3Bk for more details on when this assumption holds.\n\n---\n\nWe thank you again for your suggestions and hope this response adequately addresses your question."}, {"review_id": "BX6cU5TbgW", "reviewer": "Reviewer_ZsPD", "summary": "The authors proposes a novel sufficient condition (Assumption 2.8) bridging ($L_0,L_1$)-smoothness and anisotropic smoothness, enabling saddle-point avoidance and convergence guarantees for nonlinear preconditioned GD (e.g., gradient clipping) beyond Lipschitz assumptions. The key innovations of this article lie in two aspects:1. Proposing a novel sufficient condition for generalized smoothness. 2.Establishing a theoretical guarantees for saddle-point avoidance to nonlinear preconditioning.", "questions": "1.Would requiring gradient growth ($r +1$) to strictly exceed Hesse growth ($r$) limit application scenarios?  \n2.What relationship exists between the polynomial degree r and the function f in the algorithm 1? Is there any theoretical or empirical analysis on how to select the appropriate $r$ for different function $f$?  \n3.Assumption 3.3 plays a central role in the complexity analysis of the perturbed preconditioned gradient method. However, it is not entirely clear under what practical conditions this assumption is guaranteed to hold. Are there natural or verifiable sufficient conditions on the function $f$ and the reference function $\\Phi$ that ensure Assumption 3.3 holds?", "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.Proposes ​Assumption 2.8​ as a novel sufficient condition bridging two distinct smoothness frameworks;  \n2.Extends saddle-point avoidance properties to non-Lipschitz settings;  \n3.Demonstrates applicability in key nonconvex problems where Lipschitz smoothness fails;  \n4.The structure of this paper is clear, and the language is well-articulated, which greatly aids readers in understanding this manuscript.\n\n**Weaknesses:**  \n1.Lack of numerical experiments validation;  \n2.Lack of analysis for parameter $r$ in Assumption 2.8.", "was_revised": true, "final_justification": "After carefully considering the feedback and further discussion, I maintain my original rating.", "rebuttal": "Dear Reviewer,\n\nWe thank you for your time and effort in reviewing our work.\n\n---\n\n**Comment:** Lack of numerical experiments.\n\n**Response:** To address this comment, we have conducted two experiments: \n\n(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\\phi(x) = \\cosh(\\Vert x \\Vert) - 1$. As suggested by Reviewer M3Bk, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\\bar L = 1$)\n$$\nx^+ = x - \\gamma \\frac{\\sinh^{-1}(\\Vert \\nabla f(x) \\Vert)}{\\Vert \\nabla f(x) \\Vert} \\nabla f(x).\n$$\nIn this case, *large gradients are damped* -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\\gamma$ that are often *orders of magnitudes* larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to often require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.\n\n(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\\bar L = 1$. We compare against classical GD, and vary the constant $L \\in \\\\{1, 1.5, 2, 3\\\\}$ and dimension $n \\in \\\\{5, 10\\\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD.\nThe resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\\bar L^{-1}$.\n\nWe believe these experiments significantly improve our manuscript and therefore plan to include them. \n\n---\n\n**Comment:** Lack of analysis for parameter $r$ in Assumption 2.8.\n\n**Response:** The meaning of this comment is not entirely clear to us, so please let us know if it is not properly addressed by the statements below.\n\nIn case you are wondering how to obtain $r$ in Assumption 2.8 for specific applications, the degree of the polynomial bound to the Hessian norm is typically quite clear, especially for polynomial objectives. Given this polynomial upper bound of degree $r$ the main difficulty in showing that Assumption 2.8 holds, is establishing the polynomial lower bound to the gradient norm.\n\nIn case this comment relates to us using the same symbol $r$ for the polynomial degree in Assumption 2.8 and the perturbation radius $r$ in Algorithm 1 (which are unrelated, see also Question 2), we apologize. We will update the notation.\n\n---\n\n**Question:** Does requiring gradient growth $r+1$ to strictly exceed Hessian growth $r$ limit application scenarios?\n\n**Response:** We are not aware of practical applications in which this is the limiting factor, although toy examples can of course be constructed. \n\nNevertheless, we highlight that in cases where the gradient norm is lower bounded by a polynomial of degree $r$ rather than $r+1$, Theorem 2.9 still holds, as noted in the footnote on page 4. Likewise, the proof of Theorem 2.11 still holds for reference functions $\\phi(x) = h(\\Vert x \\Vert)$ for which ${h^*}'(y)$ is uniformly lower and upper bounded.\nThis is the case, e.g., for $h(x)= - \\vert x \\vert - \\ln(1 - \\vert x \\vert)$, but not, e.g., for $h(x) = \\cosh(x) - 1$.\n\nFor simplicity of exposition, and because we believe this entails no significant limitation, we formulated Assumption 2.8 with the gradient growth strictly exceeding the Hessian growth.\n\n---\n\n**Question:** What relationship exists between the polynomial degree $r$ and the function $f$ in Algorithm 1? Is there any theoretical or empirical analysis on how to select the appropriate $r$ for different function $f$?\n\n**Response:** The polynomial degree $r$ in Assumption 2.8 is unrelated to the perturbation radius $r$ in Algorithm 1: the former bounds the gradient and Hessian growth of $f$, whereas the latter is a hyperparameter in Algorithm 1, which we fix (cf. (13)) in the analysis of Theorem 3.6. \n\nWe acknowledge that using the same symbol for both is confusing, and will update the notation to have separate symbols for both; our apologies for any confusion caused because of this.\n\n---\n\n**Question:** It is not entirely clear under what practical conditions Assumption 3.3 is guaranteed to hold. Are there natural or verifiable sufficient conditions on the function $f$ and the reference function $\\phi$ that ensure Assumption 3.3 holds?\n\n**Response:** Thank you for raising this interesting question. First, we would like to point out that the reasoning in Example 3.4 with $\\phi = \\cosh(\\vert \\cdot \\vert) - 1$ actually holds for *any* univariate polynomial, regardless of its degree. We will also explicitly mention this in the manuscript. This result provides a strong indication that Assumption 3.3 is relatively mild, although verifable sufficient conditions on $f$ and $\\phi$ remain difficult to obtain. \n\nNevertheless, it appears that polynomial bounds can also be used as a sufficient condition in this case. We further explored this idea under the conditions of Theorem 2.11 and the additional assumption that $h^* \\in \\mathcal{C}^3$, which we mention only holds for $h = \\cosh(\\cdot) - 1$, but not for the other kernel functions in (2).\n\nLipschitz continuity of $H_\\lambda(x)$ can be established through boundedness of $\\Vert \\nabla H_\\lambda(x) \\Vert$, which in turn can be bounded by an expression of the form \n\n$$\n\\Vert \\nabla H_\\lambda(x) \\Vert \\leq \\Vert \\nabla^3 \\phi^\\*(\\nabla f(x)) \\Vert \\Vert \\nabla^2 f(x) \\Vert^2 + \\Vert \\nabla^2 \\phi^\\*(\\nabla f(x)) \\Vert \\Vert \\nabla^3 f(x) \\Vert.\n$$\n\nAfter careful examination of the structure of $\\Vert \\nabla^3 \\phi^*(\\nabla f(x)) \\Vert$, a similar reasoning as in the proof of Theorem 2.11 indicates that the following two conditions on $f$ and $h$ would be sufficient:\n\n(i) $\\Vert \\nabla^3 f(x) \\Vert$ is upper bounded by a polynomial of degree $r$ in the variable $\\Vert x \\Vert$ (similar to the Hessian bound in Assumption 2.8).\n\n(ii) $\\vert {h^*}'''(y) \\vert$ decreases fast enough as $y \\to \\infty$, i.e.,\n\n$$\n    \\lim_{y \\to +\\infty} \\vert y^2 {h^*}'''(y) \\vert < \\infty.\n$$\nWe note that this condition holds for $h = \\cosh(\\cdot) - 1$.\n\nIt would be interesting to further investigate the approach outlined above. In particular, we believe that the assumption $h^* \\in \\mathcal{C}^3$ can be relaxed to accomodate for both $h(x) = \\exp(\\vert x \\vert) - \\vert x \\vert - 1$ and $h(x) = - \\vert x \\vert - \\ln(1 - \\vert x \\vert)$, in which case the corresponding ${h^*}''(y)$ is differentiable everywhere except at $0$.\n\n---\n\nWe hope that we have accurately addressed any concerns that you may have had."}, {"review_id": "VLr5YRrc5E", "reviewer": "Reviewer_M3Bk", "summary": "This paper presents a significant theoretical contribution to the field of nonconvex optimization. It tackles the analysis of first-order methods under generalized smoothness conditions that are more realistic for many machine learning problems than the standard Lipschitz smoothness of the gradient. The authors focus on two such conditions: $(L_0, L_1)$-smoothness and anisotropic smoothness.\n\nThe core contributions are:\n\n1. The paper introduces a novel sufficient condition (Assumption 2.8) that elegantly unifies $(L_0, L_1)$-smoothness and anisotropic smoothness, revealing a deep structural connection between these two frameworks.\n\n2. It rigorously proves that this new condition holds for several key, non-Lipschitz-smooth problems in machine learning, including phase retrieval, symmetric and asymmetric matrix factorization, and Burer-Monteiro factorizations for SDPs. This provides the first formal verification of these generalized smoothness properties for such problems.\n\n3. Saddle-Point Avoidance: The paper extends the classical saddle-point avoidance results for gradient descent to the nonlinearly preconditioned gradient method (P-GD). It shows that under anisotropic smoothness, P-GD asymptotically avoids strict saddle points. The analysis is also extended to handle non-smooth preconditioners like hard gradient clipping.\n\n4. Efficient Complexity Guarantees: For a perturbed version of P-GD, the authors provide a complexity analysis, showing that the algorithm finds an approximate second-order stationary point in time that depends only polylogarithmically on the dimension, matching the state-of-the-art results for standard gradient descent under Lipschitz smoothness.\n\nThis is a purely theoretical paper with no experimental results.", "questions": "1. Regarding Assumption 3.3 ($H_\\lambda(x)$ is $\\rho$-Lipschitz): Could you provide more intuition on this condition? How does the choice of the reference function $\\varphi$ affect whether this assumption holds? Are there natural choices of $\\varphi$ for which it fails, and what would be the consequences?\n2. In Theorem 3.6, how do the constants $L$, $\\bar{L}$, and especially $\\rho$ scale with the dimension $n$ and other problem parameters for the key applications (e.g., matrix factorization)? Is the overall complexity still truly polylogarithmic in $n$ once these constants are accounted for?\n3. The analysis for hard clipping in Theorem 3.2 requires the set $U \\coloneqq \\{x | \\|\\nabla f(x)\\| \\neq L\\}$ to have measure one. This is used to ensure differentiability of the iteration map almost everywhere. Can you provide a justification or an example where this assumption holds for the problems of interest? It seems plausible but is not immediately obvious.\n4. Could you elaborate on the significance of the regularization term $(\\kappa > 0)$ in the asymmetric matrix factorization case (Theorem 2.14)? The explanation provided is clear, but does this imply that the unregularized problem $(\\kappa = 0)$ does not satisfy $(L_0, L_1)$-smoothness, and if so, does this have implications for the analysis of unregularized matrix factorization?", "limitations": "Please refer to the section on Weaknesses.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The primary strength of this work is its success in building a unified theoretical bridge between $(L_0, L_1)$-smoothness (which is often empirically motivated) and anisotropic smoothness (which arises naturally from preconditioning). Assumption 2.8, which connects polynomial bounds on the Hessian and gradient norms, is novel and powerful. This provides a much-needed foundational understanding of the geometry of loss landscapes that do not satisfy standard assumptions.\n2. A major achievement of this paper is demonstrating that its theoretical framework is not vacuous. By proving that problems like phase retrieval and matrix factorization satisfy Assumption 2.8 (and thus both generalized smoothness conditions), the authors make their abstract theory immediately relevant. This is a crucial step that many theoretical papers fail to take; it validates the entire enterprise by showing the assumptions are met in important, practical settings where classical theory fails.\n3. The paper successfully generalizes the seminal saddle-point avoidance results of Lee et al. (asymptotic) and Jin et al. (efficient) to the broader setting of anisotropic smoothness. This is a non-trivial technical feat. The authors correctly identify the key challenges, such as the difficulty of bounding the function value after a perturbation step without the convenience of quadratic bounds from Lipschitz smoothness, and the fact that the mapped Hessian $H_\\lambda(x)$ is not necessarily normal. Overcoming these challenges is impressive and extends our understanding of why first-order methods work so well in practice.\n4. The paper is well-written and organized. The motivation is laid out clearly with two central research questions. The contributions are explicitly listed. The mathematical development flows logically from definitions to applications and finally to the main analysis of saddle-point dynamics.\n\nWeaknesses:\n\n1. The paper is entirely theoretical. While this is acceptable for a strong theoretical contribution, the work would have been enhanced by even simple numerical experiments. For instance, a 2D visualization of the P-GD dynamics on a function satisfying the assumptions (e.g., the polynomial from Example 2.7) could provide valuable intuition. Similarly, illustrating the convergence of the perturbed algorithm and comparing it to standard GD could help ground the complex theoretical bounds.\n2. The complexity analysis in Section 3.2 relies on Assumption 3.3, the Lipschitz continuity of the mapped Hessian $H_\\lambda(x)$. While the paper provides an example where this holds, the assumption itself is quite technical. It is not immediately clear how restrictive this assumption is or how one would verify it for a general problem and preconditioner. A more detailed discussion on the scope and interpretation of this assumption would be beneficial. For instance, how does the Lipschitz constant $\\rho$ scale with problem parameters for the applications discussed?\nThe final complexity bound in Theorem 3.6 is given in Big-O notation, $\\tilde{O}(\\dots)$, which hides polylogarithmic factors in $n$ and $\\epsilon$. The text also notes it hides a factor $\\chi^4$, where $\\chi$ is polylogarithmic. However, the bound also depends on problem-specific constants like $L$, $\\bar{L}$, and the new Lipschitz constant $\\rho$. It would be valuable for the authors to discuss how these constants might scale for the applications in Section 2.3. If $\\rho$ or other constants hide a polynomial dependency on $n$, the overall efficiency of the algorithm could be misleading.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I will stick to my original score.", "rebuttal": "Dear Reviewer,\n\nWe thank you for your thorough and encouraging feedback.\n\n---\n\n**Comment:** A visualization of the P-GD dynamics and an illustration of the convergence of Algorithm 1 in comparison to standard GD could provide valuable intuition.\n\n**Response:** Thank you for this suggestion! We have conducted the following two experiments:\n\n(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\\phi(x) = \\cosh(\\Vert x \\Vert) - 1$. As you suggested, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\\bar L = 1$)\n$$\nx^+ = x - \\gamma \\frac{\\sinh^{-1}(\\Vert \\nabla f(x) \\Vert)}{\\Vert \\nabla f(x) \\Vert} \\nabla f(x).\n$$\nIn this case, *large gradients are damped* -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\\gamma$ that are often *orders of magnitudes* larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.\n\n(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\\bar L = 1$. We compare against classical GD, and vary the constant $L \\in \\\\{1, 1.5, 2, 3\\\\}$ and dimension $n \\in \\\\{5, 10\\\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD.\nThe resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\\bar L^{-1}$.\n\nWe believe these experiments significantly improve our manuscript and therefore plan to include them.\n\n---\n\n**Question:** Provide more intuition regarding Assumption 3.3. How does the choice of $\\phi$ affect whether this assumption holds?\nAre there natural choices of $\\phi$ for which the assumption fails, and what would be the consequences?\n\n**Response:** Thank you for raising this interesting question. \n\nWe believe Assumption 3.3 constitutes a meaningful generalization of the Hessian Lipschitz continuity assumption that is often used in complexity analyses. In an attempt to provide some more intuition, we highlight that under the conditions in Assumption 2.10 $\\Vert \\nabla^2 \\phi^\\*(y) \\Vert \\to 0$ as $\\Vert y \\Vert \\to \\infty$. The rough idea is that this counteracts the growth of $\\nabla^2 f(x)$ as $\\Vert x \\Vert \\to \\infty$ in a way that ensures Lipschitz continuity of $H_\\lambda(x) = \\nabla^2 \\phi^\\*(\\lambda \\nabla f(x)) \\nabla^2 f(x)$.\n\nWe stress that even if Assumption 3.3 is violated, then the asymptotic result of Theorem 3.1 still holds. Only regarding the required number of iterations, we can no longer give a formal guarantee.\n\nFinally, we refer to our answer to Question 3 of Reviewer ZsPD for a discussion about sufficient conditions on $f$ and $\\phi$ for Assumption 3.3 to hold.\n\n---\n\n**Question:** In Theorem 3.6, how do $L, \\bar L$ and $\\rho$ scale with the dimension $n$ and other problem parameters for key applications? Is the overall complexity truly polylogarithmic?\n\n**Response:** This is an interesting question. From a theoretical point of view, we mention that the proofs in Section 2.3 do not explicitly construct the constants $L, \\bar L$, so that we cannot formally rule out a dependence on the dimension. However, we strongly believe this is not the case, and this for the following reasons: \n\n(i) By Example 2.6, $(L_0, L_1)$-smoothness implies anisotropic smoothness with $L = L_1$ and $\\bar L = L_0 / L_1$. Thus, if $L_0, L_1$ are independent of $n$, then so are $L, \\bar L$. Judging from the experiments in [38], the empirical estimates for $L_0, L_1$ remain very moderate, even for high-dimensional neural networks.\n\n(ii) This is in line with with our own experiments on e.g. matrix factorization, in which the method converges for large step sizes, also when the dimension is increased.\n\n(iii) Likewise, we mention that for $L_H$-Lipschitz continuous Hessians $\\nabla^2 f$, the constant $\\rho$ reduces to $L_H$ when $\\phi = \\frac{1}{2}\\Vert \\cdot \\Vert^2$. To further rule out hidden dependencies on $n$, we carefully investigated the scaling of the number of iterations of Algorithm 1 with the dimension $n$ (cf. Comment 1: Experiment (ii)).\nWe found the scaling to closely match the one reported in [11, Figs 3 and 4], thus further validating the complexity of Theorem 3.6.\n\n---\n\n**Question:** The analysis for hard clipping in Theorem 3.2 requires the set $U := \\{x \\mid \\Vert \\nabla f(x) \\Vert \\neq \\bar L\\}$ to have measure one. Can you provide a justification or an example where this assumption holds for the problems of interest?\n\n**Response:** Let us define the function $F(x) := \\Vert \\nabla f(x) \\Vert^2$, which is $\\mathcal{C}^1$ whenever $f \\in \\mathcal{C}^2$. \n\nIf $\\bar L^2$ is a regular value of $F$, i.e., if there exists no $x \\in \\mathbb{R}^n$ for which $F(x) = \\bar L^2$ with $\\nabla F(x) = 0$, then by the preimage theorem the level set $F^{-1}(\\bar L^2) \\equiv \\\\{x \\mid F(x) = \\bar L^2 \\\\} \\equiv \\mathbb{R}^n \\setminus U$ is a smooth manifold of dimension $n - 1$, and therefore has measure zero in $\\mathbb{R}^n$.\n\nOn the other hand, the set of critical values ($\\bar L^2$ is a critical value of $F$ if it is not a regular value of $F$) is small for generic functions. To be more precise, by Sard's theorem the set of *critical values* has measure $0$ if $F$ is $k$ times continuously differentiable for some $k$ large enough ($k$ depends on $n$).\n\nIn conclusion, if $f$ is $k$ times continuously differentiable for some $k$ large enough, then *for almost every $\\bar L$* the set $U$ has measure one.\n\n---\n\n**Question:** Could you elaborate on the significance of the regularization term ($\\kappa > 0$) in the asymmetric matrix factorization case (Theorem 2.14)? Does this imply that the unregularized problem ($\\kappa = 0$) does not satisfy $(L_0, L_1)$-smoothness, and if so, does this have implications for the analysis of unregularized matrix factorization?\n\n**Response:** Indeed, if $\\kappa = 0$, then asymmetric matrix factorization does *not* satisfy $(L_0, L_1)$-smoothness. Let $m = n = r = 1$ such that $f(w, h) = \\frac{1}{2} (w h - y)^2$ is minimized w.r.t. $w, h \\in \\mathbb{R}$ for some given $y \\in \\mathbb{R}$. Clearly, any $w, h$ on the curve $h(w) = \\frac{y}{w}$ are (global) minimizers. The Hessian for global minimizers reduces to \n$$\n\\nabla^2 f(w, h(w)) = \\begin{pmatrix} \\frac{y^2}{w^2} & y\\\\\\ y & w^2 \\end{pmatrix}.\n$$\nThis matrix has eigenvalues $0$ and $\\frac{y^2}{w^2} + w^2$, and hence $\\Vert \\nabla^2 f(w, h(w)) \\Vert = \\frac{y^2}{w^2} + w^2$. Clearly, as $w \\to \\infty$, this Hessian norm grows unbounded, whereas the gradient norm $\\Vert \\nabla f(w, h(w)) \\Vert = 0$ remains zero. This clearly violates $(L_0, L_1)$-smoothness.\n\nConsequently, also Assumption 2.8 is violated. However, it remains unclear whether anisotropic smoothness may nevertheless hold for some reference function $\\phi$; this is a question we are further exploring.\nIn this regard, we also highlight that anisotropic smoothness generalizes $(L_0, L_1)$-smoothness, since the equivalent matrix inequality [32, Lemma 2.5] only imposes an upper bound to the eigenvalues of $\\nabla^2 f(x)$. We refer to our answer of Reviewer F5tt's first comment for more details.\n\nA possible implication for unregularized matrix factorization is that regularization actually helps satisfy (generalized) smoothness assumptions, which in turn may make the optimizer more efficient.\nWe believe that this hypothesis deserves further investigation.\n\n---\n\nWe thank you for your valuable suggestions, and hope that we have accurately addressed your questions."}, {"review_id": "BW8zKEPSOb", "reviewer": "Reviewer_F5tt", "summary": "This paper focuses on generalized smoothness conditions in non convex optimization. It first introduces a common sufficient condition for (L0, L1)-smoothness and anisotropic smoothness, and shows that it is satisfied in a few key applications. Secondly, it studies the saddle-point avoiding property of a few algorithms under relaxed smoothness conditions.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: The paper is well-written. It has a good summary of the literature and clear statements of the main results.\n\nWeakness: \n1. The paper introduces a new common sufficient condition for the two generalized smoothness conditions in the literature, but didn't discuss how 'tight' this sufficient condition could be. Without such a discussion, it is hard to judge if it is indeed an insightful sufficient condition, or just a convenient intermediate step to include a few applications. \n\n2. The paper shows that a few classical ML non convex optimization problem satisfies the generalized smoothness condition. Those applications in Section 2.3 have specialized algorithm that are quite efficient. It is not clear whether nonlinear preconditioned gradient method is a good choice for those problems. \n\n3. There are no numerical experiments that support the findings in the paper.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns about the tightness of conditions and the lack of numerical examples. I am happy to increase my score to 4 in the final justification.", "rebuttal": "Dear Reviewer,\n\nThank you for your review.\n\n---\n\n**Comment:** A discussion regarding the `tightness' of the sufficient condition (Assumption 2.8) is missing. \n\n**Response:** Assumption 2.8 is a sufficient condition that is significantly easier to verify than the second-order characterization of anisotropic smoothness (3), which in turn is equivalent to a matrix inequality involving $\\nabla^2 f$ [32, Lemma 2.5]. The merits of this condition are two-fold: On the one hand, it is practical and was used it to establish generalized smoothness of the examples in section 2.3. On the other hand, it reveals the close connection between anisotropic smoothness and $(L_0, L_1)$-smoothness.\n\nFor $(L_0, L_1)$-smoothness, some tightness is lost by requiring global polynomial upper and lower bounds to the Hessian and gradient norms, respectively. In principle, a bounded ratio of these two quantities suffices, in which case the definition of $(L_0, L_1)$-smoothness can be used directly.\n\nFor anisotropic smoothness, more tightness is lost: the matrix inequality [32, Lemma 2.5] \n$$\n\\forall x \\in \\mathbb{R}^n: \\nabla^2 f(x) \\prec L \\bar L[\\nabla^2 \\phi^*(\\bar L^{-1}\\nabla f(x))]^{-1}\n$$\nonly imposes an *upper bound* to the Hessian's eigenvalues, whereas a bound on $\\Vert\\nabla^2 f(x)\\Vert$ -- as in Assumption 2.8 or in $(L_0, L_1)$-smoothness -- imposes *both a lower and an upper bound* to the Hessian's eigenvalues.\nThis makes anisotropic smoothness (at least for certain reference functions $\\phi$) more general than $(L_0, L_1)$-smoothness (see also Example 2.6), but significantly harder to verify.\n\nAs we have illustrated through the applications in section 2.3, the Assumption 2.8 entails a practically verifiable sufficient condition, whereas, e.g., the matrix inequality [32, Lemma 2.5] would be far more difficult to establish for specific applications.\n\nWe thank the reviewer for posing this question, and agree that a discussion regarding the tightness of Assumption 2.8 would be valuable. We will include it after introducing Assumption 2.8. \n\n---\n\n**Comment:** The applications in section 2.3 have specialized algorithms that are efficient. It is not clear why a nonlinearly preconditioned gradient method is a good choice for those problems.\n\n**Response:** Section 2.3 does not claim that nonlinearly preconditioned gradient methods are *efficient* methods for the applications in section 2.3 -- although [32, Fig 3] indicates that they perform very well for phase retrieval, and this also agrees with our personal experience. Rather, we wanted to illustrate that this theoretical framework for generalized smoothness is truly relevant by showing that it applies to certain key applications where classical Lipschitz smoothness fails. As acknowledged by one of the other reviewers, this is a crucial step which many theoretical papers fail to take.\n\n---\n\n**Comment:** There are no numerical experiments.\n\n**Response:** To address this comment, we have conducted two experiments: \n\n(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\\phi(x) = \\cosh(\\Vert x \\Vert) - 1$. As suggested by Reviewer M3Bk, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\\bar L = 1$)\n$$\nx^+ = x - \\gamma \\frac{\\sinh^{-1}(\\Vert \\nabla f(x) \\Vert)}{\\Vert \\nabla f(x) \\Vert} \\nabla f(x).\n$$\nIn this case, *large gradients are damped* -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\\gamma$ that are often *orders of magnitudes* larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.\n\n(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\\bar L = 1$. We compare against classical GD, and vary the constant $L \\in \\\\{1, 1.5, 2, 3\\\\}$ and dimension $n \\in \\\\{5, 10\\\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD.\nThe resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\\bar L^{-1}$.\n\nWe believe these experiments significantly improve our manuscript and therefore plan to include them.  \n\n---\n\nWe hope that we have adequately addressed any concerns that you may have had, and that you are willing to re-evaluate your rating of our work."}]

Author rebuttal:

Meta-review: The paper studies the nonlinear preconditioned gradient method, which generates its iterate updates by pushing the gradient through a nonlinear map, under an anisotropic smoothness conidtion. This framework encompasses both standard gradient descent and methods that use clipping or truncation, variants of which have been proposed for studying the training of transformers and other models, as well as for statistical problems with heavy-tailed costs. The paper studies the saddle-escaping property of this family of methods, under anisotropic smoothness. The former is important for guaranteeing high-quality solutions under structured nonconvexity (i.e., phase retrieval and matrix factorization), while the latter is important for nonlinear problems with high-order polynomial costs, where the global Lipschitz property breaks down. The paper proves (L,\bar{L})-anisotropic smoothness of a number of problems with structured nonconvexity, including matrix factorization, phase retrieval, and Burer-Monteiro factorization. It then proves that the nonlinear preconditioned gradient method has the saddle avoiding property, i.e., from random initialization it escapes strict saddles with probability one, and with random initialization, it efficiently escapes saddles. Reviewers positively evaluate the paper’s novelty and technical contributions, noting that relaxed Lipschitz conditions are necessary in problems with higher-order costs. The paper provides both a probability-one guarantee of saddle avoidance using the stable manifold theorem and complexity analysis for the perturbed version. The paper is very clearly organized and well-written. The only limitation noted by the reviewers is the lack of numerical experiments. This was partially addressed during the discussion period; in any case, the theoretical contributions of the paper are strong enough to merit acceptance.
Decision: Accept (spotlight)