Loss Landscape Characterization of Neural Networks without  Over-Parametrization
Authors: Rustem Islamov
Niccolò Ajroldi
Antonio Orvieto
Aurelien Lucchi
Venue: NeurIPS 2024 poster (2024)
Keywords: optimization
deep learning
neural networks
convergence
Primary area: optimization_for_deep_networks

Abstract: Modern machine learning heavily depends on the effectiveness of optimization techniques. While deep learning models have achieved remarkable empirical results in training, their theoretical underpinnings remain somewhat elusive. Ensuring the convergence of optimization methods requires imposing specific structures on the objective function which often do not hold in practice. One prominent example is the widely recognized Polyak-Lojasiewicz (PL) inequality, which has garnered considerable attention in recent years. However, validating such assumptions for deep neural networks entails substantial and often impractical levels of over-parametrization. In order to address this limitation, we propose a novel class of functions that can characterize the loss landscape of modern deep models without requiring extensive over-parametrization and can also include saddle points. Crucially, we prove that gradient-based optimizers possess theoretical guarantees of convergence under this assumption. Finally, we validate the soundness of our assumption through both theoretical analysis and empirical experimentation across a diverse range of deep learning models.

Loss landscape Characterization of Neural Networks without Over-Parametrization
Rustem Islamov
Niccoló Ajroldi²
Antonio Orvieto2.3.4
Aurelien Lucchi*
University Basel Max Planck Institute for Intelligent Systems ELLIS Institute Tübingen
*Tübingen Al Center
Abstract
Optimization methods play crucial role in modern machine learning, powering the remarkable empirical achievements of deep learning models. These successes are even more remarkable given the complex non non-convex nature of the loss landscape of these models. Yet, ensuring the convergence of optimization methods requires specific structural conditions on the objective function that are rarely satisfied in practice. One prominent example the widely recognized Polyak-t.ojasiewicz (PL) inequality, which has gained considerable attention in recent years. However, validating such assumptions for deep neural networks entails substantial and often impractical levels of pereaaaatttiinionnnn In order to address this limitation, we propose novel class of functions that can characterize the loss landscape modern deep models without requiring extensive over- pararaettttiziionnnn and also include saddle points. Crucially, we prove that gradient- based optimizers possess theoretical guarantees of convergence under this assumption. Finally, we validate the soundness of our new function class through both theoretical analysis and empirical experimentation across diverse range of deep learning models.
Introduction
The strides in empirical progress achieved by deep neural networks over the past decade have been truly remarkable. Central to the triumph of these techniques lies the effectiveness of optimization methods, which is particularly noteworthy given the non-convex nature of the objective functions under consideration. Worst-case theoretical results point to a pessimistic view since even a degree four polynomial can be NP-hard to optimize [30] and the loss landscape of some neural networks are known include saddle points bad local minima [6, 70, 88).
Yet, empirical evidence has shown that gradient-based based optimizers - including SGD, AdaGrad [21] and Adam [39] among many others models. While some have pointed to the ability of gradient- based optimizers to deal with potentially complex landscapes, e.g. escaping saddle points [36, 17], another potential explanation is that the loss landscape itself is less complex than previously assumed [27, 51].
effectively optimize the loss of modern deep-learning- based
Some key factors in this success include the choice of architecture [5, 48. 40. 18], well as the werrparaaettrization [73, 12, 50, 51]. the well-known infinite-width limit [86, 35, 32], neural networks are known to exhibit simple landscapes [49]. However, practical networks operate in finite range, which still leaves a lot of uncertainty regarding the nature of the loss landscape. This is especially important given that the convergence guarantees of gradient-bast based optimizers are derived by assuming some specific structure on the objective function [37, 79, 71]. Consequently, an essential theoretical endeavor involves examining the class of functions that neural networks represent.
In this work, we present new class of functions that satisfy newly proposed a-3-condition (see Eq. (2)). We theoretically and empirically demonstrate that these functions effectively characterize
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table I: Summary of existing assumptions the problem (1) and their limitations. Here S denotes the set of minimizers of f and f == argmin, fx()). Unlike earlier conditions, the a---coondition is specifically designed to capture local minima and saddle points. NN Neural Network.
Condition
Definition
Comments
QCvx [28]
(x)., - ((f(a) R(*))
exclluds saddle points and local minima
for some fixed CS
excludes saddle points and local minima
Aiming [5]]
(V)(), Proj(s,) 0f(a))
thoorctically holds for NN in the presence of
impractical puraneletization [51]
does always hold prictice [Fig. n-h)
minima thooretccally holds for NN in the presence of
exclludes saddle points
(L [66]
2
impractical over paramelenizatio [50]
does not always hold in practice (Fig. I c-d]
a-B-condition [This wurk]
( Proj(z. 8) a(fit)) (.Pro) 8))
might have saddles [Ex. 2] and local minima (Ex. 3]
-3 -3(1(()) -1)
practice does not require
over. pee-paraamterriatiin [Fx. 5]
the loss landscape of neural networks. Furthermore, we derive theoretical convergence guarantees for commonly used gradient- based optimizers under the a-8-condition.
In summary, we make the following contributions:
1. We introduce the a-33-condition and theoretically demonstrate its applicability to wide range of complex functions, notably those that include local saddle points and local minima.
2. We empirically validate that the a-9-condiiion is meaningful assumption that captures a wide range of practical functions, including matrix factorization and neural networks (ResNet, LSTM, GNN, Transformer, and other architectures).
3. We analyze the theoretical convergence of several optimizers under a- a-8-condition, including vanilla SGD (Stochastic Gradient Descent), SPS (Stochastic Polyak Stepsize) [53]. and NGN [63] (Non-negative Gauss-Newton).
4. We provide empirical and theoretical counter-examples where the weakest assumptions, such as the Pl. and Aiming conditions, do not hold, but the a-B-condition does.
2 Related work
2.1 Function classes in optimization
Studying the convergence properties of gradient-based optimizers has a long history in the field of optimization and machine learning. Notably, one of the fundamental observations is the linear and sub-linear convergence exhibited by GD for strongly convex (SCvx) and general convex (Cvx) functions [61]. However, most modern Machine Learning models have non-convex loss landscapes. for which the existing convex theory is not applicable. Without assumptions on the loss functions (other than smoothness), one can only obtain weak convergence guarantees to a first-order critical point. This situation has led to the derivation of assumptions that are weaker than convexity but that are sufficient to guarantee convergence of GD-based optimizers. The list includes error bounds (EB) [54], essential strong convexity (ESC) [52], weak strong convexity (WSC) [60], the restricted secant inequality (RSI) [87], and the quadratic growth (QG) condition
[1]. In the neighborhood of the minimizer set S, EB, PL, and QG are equivalent if the objective is twice differentiable [68]. All of them, except QG, are sufficient to guarantee a global linear convergence of GD. However, among these less stringent conditions, the Polyak- Lojasiewiiiiiiiizz (PI.) condition stands out as particularly renowned. Initially demonstrated by Polyak [66] to ensure lincar convergence, it has recently experienced a resurgence of interest, in part because it accurately characterizes the loss landscape of heavilly over- paraptrrmeteieed neural networks [50]. It was also shown to be one of the weakest assumptions among the other known conditions outlined so far [37]. A generalized form of the PL condition for non-smooth optimization is the much larger class of functions [14, 77] than PL. The KL inequality has been employed to analyze the convergence of the classic proximal-pont algorithm [3, 11, 47] and other optimization methods [4, 45).
(KL) condition [43, 10] which is satisfied for a
More recently, some new convex-like conditions have appeared in the literature such as star-convex (StarCvx) [62], quasar-convex (QCvx) [28], and Aiming [51]. These conditions are relaxations of
2

---

Angle wi8
PL consont
PL consant
S
Epoch
Epoch
Epoch
Epoch
PTB
(5) 2ikitext
PTB
(d) Wikitexe
Figure I: Training of layer LSTM model that shows Aiming condition does not always hold. The term "Angle" in the figures refers to the angle f -x and it should be positive if Aiming holds, while in a-b we observe that is negative during the first part of the training. Figures c-d demonstrate that possible constant μ in PL condition should be small which makes theoretical convergence slow.
0.70
Anqia:
69.01
0.5
11083
2303
1000
3000
01X1
13991
3002
(eeration
Figure 2: Training for half-space learning problem with SGD. The term "Angle" in the figures refers to the angle [x (x*), x xx).
convexity and include non-convex functions. Within the domain of reinforcement learning, several works [84, 23] have also considered relaxations of the gradient domination condition, although these analyses are conducted specifically within the context of policy gradient methods, and therefore less relatable StarCvx, QCvx or the Aiming condition.
We present summary of some of these conditions in Table 1. There is no general implication between already existing assumptions such QCvx, Aiming, PL, and the a-f-condition. However, as we will later see, the a--3-condition can more generally characterize the landscape of neural networks without requiring unpractical amounts over wver-parametrization. Notably, the a-F3-conition is condition that applies globally to the loss. However, we will demonstrate that convergence guarantees can still be established for commonly-used gradient- optimizers. although these guarantees are weaker than those derived under the PI. condition, which relies on much stronger assumptions.
2.2 Limitations of existing conditions
Next, we discuss the limitations of previous conditions to characterize the loss landscape complex objective functions such as the ones encountered when training deep neural networks.
Necessity of peee-paramtterzation. When considering deep models, the theoretical justification of conditions such as Aiming [51] and PL [50] require a significant amount of over- seee-paramterrzzation This implies that the neural network must be considerably large, often with the minimum layer's 's width scaling with the size of the dataset n. However, various studies suggest that this setup may not always accurately model real-worls world training dynamics [13, 2]. To the best of our knowledge, the weakest requirements the width of network are sub-quadratic (/23/2) [20, 74], where n is the size of dataset. This implies that, even for a small dataset such as MNIST, a network should have billions of parameters which is not realistic setting in practice. In contrast, the a-$-condition condition does not require such an over- over-voveaee peer-arametrization condition to hold (e.g., see Example 5). In Section 5 we provide empirical results showing how condition is affected by over-parameterization.
Necessity of Invexity. One limitation of prior assumptions is their inability to account for functions containing local minima or saddle points. Indeed, many of the weakest conditions, such as QCvx, PL, KL, and Aiming, require that any point where the gradient zero must be deemed global minimizer. However, such conditions are not consistent with the loss landscapes observed in practical neural networks. For example, finite-size MIPs can have spurious local points saddle points [88, 80). Another known example is the half-space learning problem which is known to have saddle points [17]. We refer the reader to Figure 2-a that illustrates this claim (it showcases the surface of the problem

---

fixing all parameters except first 2), and also demonstrates that the Aiming and PL conditions fail to hold in such a setting. We present the results in Figure 2' where we observe that (i) the angle between the full gradient and direction to the minimizer f(Vf(=)) -² x²) can be negative implying that the Aiming condition does not hold in this case (since the angle should remain positive); (ii) the gradient norm can become zero while we did not reach minimum (loss is still large) implying that the
PL condition does not hold as well (since the inequality || [[V 2 2p(f(=") - f*) is not true for any positive μ). These observations suggest that the Aiming and PL conditions do not characterize
well landscape in the absence of invexity property. In contrast, we demonstrate in Example 2 and
Figure that our proposed assumption is preferable in this scenario.
As previously mentioned, most theoretical works apply to some infinite limit or neural networks of impractical sizes. In contrast, several works [89, 27, 75] have studied the empirical properties of the loss landscape of neural networks during training. They have shown that gradient-based optimization methods do not encounter significant obstacles that impede their progress. However, these studies fall short of providing theoretical explanations for this observed phenomenon.
Lack of Theory.
Lack of Empirical Evidence. Several theoretical works [49, 51] prove results on the loss landscape of neural networks without supporting their claims using experimental validation on deep learning benchmarks. We demonstrate some practical counter-examplee to these conditions proved in prior work. We train LSTM- model with standard initialization on Wikitext-2 [57] and Penn Treebank (PTB) [58] datasets, In Figure I (a-b), we show that the angle between the full gradient and direction to the minimizer fx=((x)) x x²) can be negative in the first part of the training. This result implies that the Aiming condition does not hold in this setting (either we do not have enough over-parane preepparamtterization or the initialization does not lie in the locality region where Aiming holds).
Moreover, for the same setting in Figure (c-d) we plot 2 f
2/8 log( [f (x** fxx*))²
to measure the empirical value of PL constant log 1og(2 (see derivations in Appendix A). We observe that the value of μ that might satisfy PL condition should be of order 10-8 10-7 and leads to slow theoretical convergence [37]. These observations contradict with practical results. We defer to Appendix A for more detailed discussion. In contrast, we demonstrate in Figure 7-- that the proposed a-88-cnndiiion can be verified in this setting.
3 The proposed a----conition
Setting. We consider the following Empirical Risk Minimization (ERM) problem that typically appears when training machine learning models:
min ZERd
= 1 f((x))
Here E Rd denotes the parameters of model we aim to train, is the number of parameters, and n is the number of samples in the training dataset. Each f((z) is the loss associated with the i-th data point. We denote the minimum of the problem (1) by f* and the minimum of each individual function by f == min, fx)), which we assume to be finite. Besides, the set S denotes the set of all minimizers of f.
A new class of functions. Next, we present a new condition that characterizes the interplay between individual losses ft and the set of minimizers of the global loss function f.
Definition 1 (a-f-cooniiton)) ). Let X S Rd be a set and consider function f X + R as defined in (I). Then f satisfies the a-S-condition with positive parameters a and 3 such that a 3 if for any
'Our implementation is based the open source repository https://gite Escaping- saddles- uuiiges---uu------e www.-uuttiinnaaeeeeeeeeeeeeee Stochastic-----eee Grwdieett-eeeeeeeeeee from [17] with small changes to track neces- sary quantities.
cww/coo////eo. cwm/arccaaee chana95in//
"Our implementation is based the open source repository https://github com/ homm/fhub// parameter- agnostic-lal from [33] with small changes to track necessary quantities. The detailed experi- ment description given in Appendix D.2.
We use K (for a large value of K) approximate the minimizer x".

---

E A' there exists 2p E Proj(z, S) such that for all i,
((()), xp) 2 a(f((x) -
(2)
The e--3-cnditionn recovers several existing assumptions special cases. For example, the proposed assumption reduces to QCvx around x² if a > 0. 3 O. and S is a singleton {x*}. Importantly, the a-3-condition is also applicable when the set S contains multiple elements.
One can easily check that the pair of parameters (a, B) in (2) can not be unique. Indeed, if the assumption is satisfied for some a and 3, then due to inequality fi(zp) 2 f; it will be also satisfied for (a + 6, 3 + 5) for any 2
3.1 Theoretical verification of the a-B-condition
To demonstrate the significance of Definition as a meaningful condition for describing structural non-convex functions, provide several examples below that satisfy (2). We do not aim to provide the tightest possible choice of a and 3 such that Definition holds. Instead, this section aims to offer variety of examples that demonstrate specific desired characteristics when a-B-condition holds, encompassing a broad range of functions.
The initial example illustrates that S could potentially be infinite for the class of functions satisfying Definition
Example 1. Let f, f2: R² + R be such that
(xtv+1)² 1)2 f= (fi f2) with fi y) = [++v)++I+ f2
(x+y)²
(++g+1944))
then Definition holds with +oo) and B (4)/5,
Next, we provide an example where satisfies Definition I even in the presence of saddle points. Example 2. Let f1 R² + R be such that
f= + with fi v) = -
0- e-----
fe(x, = 1 - (x-2))
(4)
then Definition holds for some a and = a Remark 1. Examples and 2 can be generalized for any number of functions n and dimension d as follows
fx) (E "
f((x) 143 (ot- bb,)
(5)
(E)=
for properly chosen {a,) and (bggie [n], [d].
Example 3. Let f, f2: R² > R be such that
f= (
+ fe) with f1 1+2 4
fe(z.y)
[m- (y- 4+ +(5)
(6)
then Definition holds for some a and B =3=0 a.
The three examples above demonstrate that functions satisfying Definition I can potentially be non- convex with an unbounded set of minimizers (Example 1) and can have saddle points (Example 2) and local minima (Example 3). In contrast, the PI. and Aiming conditions are not met in cases where problem exhibits saddle points. For illustration purposes, we plot the loss landscapes of f in Figure 3.
So far, we have presented simple examples verify Detinition 1. Next, turn our attention to more practical examples in the field of machine learning. We start with the matrix factorization problem that is known to have saddle points [76] but be shown be PL after sufficiently large number of iterations of alternating gradient descent and under a specific random initialization [81].
Example 4. Let fs; Jij be such that
f(W,S) 1 X T $|| 2nm
- s))2 (W, -3 s, (7) 1 -x
20m
where X E R=xm W = (w:) E Rkxn_ S (s,)T² E Rexm and rank(X) - k. We assume that X generated using matrices W and 5* with non-zero additive noise that minimize empirical loss, namely, X = T (ei))EE(n)) Let X' be any bounded set that contains S. Then Definition satisfied with a B and some 3 0.
S"
where W* = argminw.s S(W,S)
5

---

0.9
1
0.7
0.99
0.8
0.8
0.5
0.7
0.3
0
2
1
4 -2
Example
Example 2
Example 3
Figure 3: Loss landscape of that satisfy Definition 1. The analytical form of fi is given in Section 3.1. These examples demonstrate that the problem (1) that satisfies a-B-condition might have an unbounded set of minimizers S (Example 1), saddle point (Example 2), and local minima (Example 3) in contrast the PL and Aiming conditions. The contour plots are presented in ??.
Example 5. Consider training two-layer neural network with logistic loss
(8) for a classification problem where (0t) == log(1 1 + exp( ())) W Rexdd , E RR a is ReLU function applied coordinate-wise, Y/ [-] is label and 2; Rd is feature vector. Let X be any bounded set that contains S. Then the a-B-condition holds in X' for some 2 1 and 8 = a 1.
/ fa. f.W, ó To (WW::) + A Ar|lu|12 12
Remark 2. The previous examples can be extended to any positive and convex function ø (e.g.. square loss) with the additional assumption that each individual loss fa does not have minimizers in S, i.c. ((W u*) E S such that fiWW', v*) = for some E [n]]
We highlight that Example is applicable for bounded set X' of an arbitrary size. Moreover, in practice, we typically add & or & regularization which can be equivalently written as a constrained optimization problem, and therefore, Example 5 holds in this scenario. In comparison, the results from previous works do not hold for an arbitrary bounded set around requiring initialization to be close enough to the solution set [51, 50). The proofs for all examples are given in Appendix C.I.
4 Theoretical convergence of algorithms
We conduct our analysis under the following smoothness assumption that standard in the optimiza- tion literature.
Assumption 1. We assume that each fi is L-smooth, i.e. for all a, E Rd it holds f/V) ff(())l s
The next assumption, which is sometimes called functional dissimilarity [56]. is standard in the analysis of SGD with adaptive stepsizes [53, 26, 24].
Assumption 2. We assume that the interpolation error o [ - f; is finite, where the expectation is taken concerning the randomness of indices i for certain algorithm.
4.1 Convergence under the a-3-condition
Now we demonstrate that the a- a--3-condition is sufficient for common optimizers to converge up to a neighbourhood of the set of minimizers S. We provide convergence guarantees for SGD-based algorithms with fixed and adaptive stepsize (i.e., the update direction is of the form -7% V ft, (x*)) In this section, we only present the main statements about convergence while the algorithms' description and the proofs are deferred to Appendix C.2.
Convergence SGD. We start with the results for vanilla SGD with constant stepsize.
Theorem 1. Assume that Assumptions 1-2 hold. Then the iterates of SGD (Alg. 1) with stepsize 7 a-d satisfy
E dist S)
2Lv
23
min E [f(xh) - - oskcK
7(a - 3) + a - int
+
σ int
(9)
K
a 3

---

Table 2: Summary of how the non non-vanishing term So (as appearing c.g. in Eq. (9)) increases (7) or decreases ()) as a function of specific quantities of interest.
Model's width
Model's depth
/ Batch-size /
Change in Bo
Theorem 1 shows that under the a-B-condition, SGD converges with rate (K-21/2 (the same rate obtained by SGD for convex functions (24]) up to a ball of size ((3o We argue that the non-vanishing term ( must appear in the convergence rate for non-convex optimization for several reasons: (a) This term arises directly from the use of the a-3 condition in the analysis, without resorting to additional upper bounds or approximations. It reflects the potential existence of local minima that the a-B condition is designed to model. In the worst-case scenario, if SGD is initialized near local minima and uses a sufficiently small step size, may fail converge the exact minimizer and can become trapped in suboptimal minima. This sub- sub-optimality is modeled in the upper bound by the gepsize-independent quantity (( since we provide convergence guarantees for the function value sub-optimality rather than the squared gradient norm, which is more typical in the non-convex setting. (ii) We also observe that the last term in (9) shrinks as a model becomes more over werr-aarameteiized (which is consistent with prior works such as [50] that require large amounts of over-parames parametriizaaio)) see Sections 5.1, 5.2, and D.7 for experimental validation of this claim. Further empirical observations are summarized in Table 2 and will be discussed in Section 5. Theoretically, if a model is sufficiently aver-parameterized such that the interpolation condition f = f* holds, then the non- mon-ahiishin term is not present in the bound. (tit) The presence of a non-vanishing error term in the rate with the a-3 condition is consistent with empirical observation as it is frequently observed when training neural networks (see Figure 8.1 in [25]). This is also observed during the training of language models where the loss is significantly larger than 0 (see Figure 19). This phenomenon suggests that reaching a critical point, which is global minimizer, is not commonly observed practically. (iv) Finally, we note a potential similarity with prior works that propose other conditions to describe the loss landscape of deep neural networks (e.g. gradient confusion [71]), and also obtain a non- non-vanishing term in the convergence rate (see Theorem 3.2 in [71]).
Convergence of SPSmax.
Next, we consider the SPS algorithm. SPS stepsize is given by fu, (z Tb where e and nb are the stepsize hyperparameters.
fn f=
7hk = min
Theorem 2. Assume that Assumptions 1-2 hold. Then the iterates of SPSmax (Alg. 2) with a stepsize hyperparameter 2(0-3) satisfy
min E [|s(x*) osk<K
C Eddis((<&, + poci
(10)
where Tmin == miin(/2et,, )8) and C1 Tinin (2(a B)c-13
In the convex case, i.c. a-B-condition holds with a = 1, B = O, we recover the rate of Loizou et al. [53].
Finally, we turn to the analysis of NGN. This algorithm is proposed for minimizing positive functions Si which is typically the case for many practical choices. Its stepsize where y is the stepsize hyperparameter. NGN stepsize differs from that (1*)
Convergence of NGN.
Tkk 1+ 2/1 (
of SPS by replacing min operator by softer harmonic averaging of SPS stepsize and a constant y. In addition to the already mentioned assumptions, we make mild assumption that the positivity error o2 pos := E [fr] is finite.
Theorem 3. Assume that Assumptions I with a 2 3 + 1 and 1-2 hold. Assume that each function fa is positive and pos < co. Then the iterates of NGN (Alg. 3) with stepsize parameter > 0 satisfy
F. [di [S (1 + 22 3L + 7L
min E[s(2*) -1 osk$k-1
<
2
C2
C2
7L
2000
+ max (2 12--,, 1,0) 02
(11)
C2
where 02 = 27 -B 1 3.
7

---

150-00
5.06
40003
Aah TT-s) ST10
3.0
HAS TEAS
125400
1366
17/00
121
1943
230
235
300
800
3.0
221400
108423
101430
59443
30463
50085
47360
47100
47030
(2) 2nd Layer
2nd size
128
(c) layer 2048
(d) 2d) layer size 4096
Figure 4: a-f3-conition in the training of layer MLP model on Fashion-MNIST dataset varying the size of the second layer. Here T(*)) (V (x*), x x zk) a(fi, (2**) fi, (x*)) ff (x²*)
assuming that / O. Minimum is taken across all runs and iterations for given pair of (ar, B3.
One of the main properties of NGN is robustness the choice of stepsize y. Theorem can be seen as an extension of this feature from the set of convex functions originally analyzed in [63] to the class of structured non-convex satisfying a--3-coddition.
Comparing the results of Theorems 2 and 3 we highlight several important differences. (i) There no restriction on the stepsize parameter for NGN. Conversely, SPS requires to be lower bounded. (2i) Both algorithms converge to neighborhood of the solution with fixed stepsize hyperparameter. However, the neighborhood size of SPS not controllable by the stepsize hyperparameter and remains constant even in the convex setting when 8 = O. In contrast, NGN converges a ball whose size can be made smaller by choosing small stepsize parameter, and the "non-vanishing" term disappears in the convex setting = 0.
We note that goal not achieve the tightest convergence guarantees for each algorithm, but rather to underscore the versatility of the a- a-3-condition in deriving convergence guarantees for SGD-type algorithms, both for constant or adaptive stepsizes. addition to the results of this section, we demonstrate the convergence guarantees for SGD, SPSmax and NGN with decreasing with stepsizes in Appendix C.2. Besides, in Appendix C.2.4 we present convergence of a slightly modified version of Adagrad-none norr method [82] under a- c----conition.
5 Experimental validation of the a-B-condition
In this section, we provide extensive numerical results supporting that the a-8-condition does hold in many practical applications for various tasks, model architectures, and datasets. The detailed experimental setting is described in Appendix D.
In all cases, we approximate Proj(æ* S) as the last iterate - in run. After finding such an approximation, we start a second training run with the same random seed to measure all necessary quantities. To guarantee that the second training trajectory follows the same path as the first run, we disable nondeeterministic CUDA operations while training on GPU. For each task, we demonstrate possible values of pairs of (a, B) that work across all runs (might differ from one experiment to another) with different random seeds and satisfy a 3 +
5.1 MLP architecture
First, we test MLP neural networks with 3 fully connected layers on Fashion-MNIST [83] dataset. We fix the second layer of the network be a square matrix and vary its dimension layer investigate the effect of over- over-paramen parameterization on a----condition. We test it for dimensions {32, 128, 2049, 4096). and for each case, we run experiments for 4 different random seeds. In Figure 4 we demonstrate possible values of pairs of (a,, 3) that work across all 4 runs. We observe that minimum possible values of a and /3 increase from small size to medium, and then tend decrease again as the model becomes more pardeeeereee....d. We defer more experimental results for MIP to Appendix D.3 to showease this phenomenon. This observation leads to the fact that the neighborhood of convergence (Bo7))) of SGD eventually becomes smaller with the size of the model as expect (since it becomes more peer-parametrrized).
5.2 CNN architecture
In our next experiment, we test convolutional neural networks with 2 convolution layers and 1 fully connected layer on CIFARIO dataset [41]. We vary the number of convolutions the second convolution layer to investigate the effect of over-paramettriizatonn a-8-condition. We test it

---

130
Tr-h x000
11.10
nis mi--114)
7100
Te-
(3) # Convolutions 32
(b) # Convelations 64
(<) # Cumvolutions 512
(d) # Comolutions 2048
Figure 5: Q----ondition in the training of CNN model on CIFARIO dataset varying the number of convolutions in the second layer. Here T(æ;) fV (z*), x²) a (f (=*) fi. (x*)
(x* assuming that f 0. Minimum is taken across all runs and iterations for given pair of (a, ().
3.2
139
23712
10
70
27
327
855
20724
53743
055
25
259
231
503
285
35
27
12
(a) Hatch size 64
(b) Botch size 128
(c) Hotch size 266
(4) Banch size 612
Figure o- a--3-condtiion in the training Resnet9 model on CIFAR 100 dataset varying the batch size. Here T(xx) = (v,, (x*), ) x²) asSs, (x=*) Sia (x*)) Bfc, (x*) assuming that J 0.
Minimum is taken across all runs and iterations for given pair of 3),
for {32, 128, 512, 2048} number of convolutions in the second layer, and for each case, we run experiments for different random seeds. In Figure 5, we observe that the smallest possible values of (a. B) increase till 64 convolutions, and then decrease back. Second, the difference possible choice of and B decreases from Figure 5-a to Figure 5-b, but then it increases again.
for
5.3 Resnet architecture
Next, switch to the Resnet architecture [29] with batch sizes in {64, 128, 256, 512) trained on CIFAR100 [41]. For each batch size, we run experiments for 4 different random seeds. In Figure 6, we plot the possible choice of pairs (a, 5) that works across all runs. We observe that a-8-condition holds in all cases. Besides, there is a tendency for the minimum possible choice of a and B to decrease with batch size. Moreover, larger batches, the difference between a and / also increases. From Theorem 1, this result suggests that we can use bigger stepsizes with larger batches.
5.4 Training of AlgoPerf workloads and transformers for language modeling
We are now interested in assessing the validity of a-8-condition on modern Deep Learning archi- tectures. Thereby, we consider tasks from the AlgoPerf benchmarking suite [16]. We consider four workloads from competition: (i) Mssmll model [59] on Criteo 1TB dataset [44]; (ii) U-Net model [69] on FastMRI dataset [85] (iii) GNN model [7] on OGBG dataset [3 ]]: (iv) Transformer-big [78] on WMT dataset [9]. To train the models, we use NAdamW optimizer [19]*, which achieves state-of-the-art performances the optimizer are chosen to reach the validation target threshold set by the original competition. Moreover, we consider the pretraining of decoder-only transformer architecture [78] for causal language modeling. We conduct our evaluation on two publicly available Pythia models [8], of sizes 70M and 160M, trained on 1.25B and 2.5B tokens respectively. For this study, SlimPajama [72] dataset. Following the original Pythia recipes, we fix sequence length of 2048 and train the language model to predict the next token in self- self-supervised fashion. We refer to section Appendices and D.8 for additional details.
the current version of the benchmark. The hyperparameters of
the
The results are presented in Figure 7. We observe that a-f-condition holds for wide range of values of a and 3 which demonstrates that our condition can be seen as a good characterization of the training of modern large models as well. One can notice that the possible values of and for AlgoPerf workloads are higher than those for smaller models discussed previous sections.
'Our implementation is based on open source AlgoPerf code https: siithuu.... cww/mooc///////mo commoocommons/ algorithmic efficiency with minimal changes track necessary quantities.

---

-.27
15
21
100
(2) Chitoo ITB DLRMsmall
(h) FooMRR
(c) OGRG GNN
(d) WMT
U U.Net
Transformet
200
30
1.00
(0
10
10
15
30
15
50
10
30
10
30
PTB LSTM
(10 Wikiusst-2
(c). Co1.Slim-Paaamm Pythia 70M
(1) D0.SSliiPPjinn Pajim--ajjjm Pythia 16UM
LSTM
Figure 7: a-8-condition in the training of some large models from AlgoPerf, 3-layer LSTM, and Transformers for language modeling. Here T(x)) fi. (a"), - ) a (-")
faz (zx)) f fxx((*)) assuming that f O. Minimum is taken across all runs and iterations for given pair of 3).
This difference attributable to smaller models interpolating the training data more effectively, resulting in significantly lower training losses compared to those observed in AlgoPerf experiments (see Appendix D for detailed results). However, we highlight that the convergence guarantees the optimizers depend term ((3ol)) which is stable across all experiments we provide.
5.5
Additional experiments
We defer the verification of a-99-coddiioon by Adam and SGDM to Appendix D.6. The results in Figure 16 suggest that Adam explores the part of the landscape with smaller values of a and / than those for SGDM. The same conclusions can be drawn when comparing SGDM and SGD. These observations might be training of DL models. The verification of the proposed condition varying the depth of Resnet model can found Appendix D.7. The results from Figure demonstrate that the values of a and decrease with the depth of Resnet model, i.c. the model becomes more over-parametrized.
reasons why diagonal preconditioning and momentum are helpful
Conclusion, potential extensions, and limitations.
In this work, we introduce new class of functions that more accurately characterize loss landscapes of neural networks. In particular, provide several examples that satisfy the proposed condition, including 2-layer ReLU-neural networks. Additionally, we prove that several optimization algorithms converge under our condition. Finally, we provide extensive empirical verification showing that the proposed a- a----condition holds along the optimization trajectories of various large deep learning models.
also possible to further expand convergence guarantees upon the ones presented in Section 4, for instance, by considering momentum [67] which is widely used in practice. However, we defer the exploration of other possible extensions to future research endeavors.
One of the limitations of this work is the empirical validation of the a-3-condition on neural networks. We only able verify this condition along the trajectories of specific optimizers. Even when performing checks with many random seeds, we cannot fully observe the entire loss landscape. Additionally, while our theoretical examples demonstrate that the proposed condition holds, do not provide the most precise theoretical values of and 3 that satisfy Definition 1. Therefore, in future work, we aim to obtain stronger theoretical guarantees demonstrating that the a-f-condition holds for neural networks with more precise values of and B. We also intend to explore how the o-8--cnditioon varies when changing the architecture the number of parameters (i.e., theoretical exploration of over parmmtterriziiinnn)
10

---

Acknowledgement
Rustem Islamov and Aurelien Lucchi acknowledge the financial support of the Swiss National Foundation, SNF grant No 207392. Antonio Orvieto acknowledges the financial support of the Hector Foundation. The authors thank the anonymous reviewers for their valuable comments and suggestions on improving the paper.
References
[1] Mihai Anitescu. Degenerate nonlinear programming with a quadratic growth condition. SIAM Journal on Optimization, 2000. (Cited on page 2)
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, 2019. (Cited on page 3)
[3] Hedy Attouch and Jérôme Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming. 116:5-16, 2009. (Cited on page 2)
[4] Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, howwardbbckwwrr splitting, and regularized gauss-seidel methods. Mathematical Programming, 2013. (Cited page 2)
[5] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint arXiv: 1607.000 1607,06450, 2016. (Cited page 1)
[6] Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 1989. (Cited on page 1)
[7] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Manchez-Gonzaler Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre. Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1806.01261, 2018. (Cited page 9)
[8] Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, 2023. (Cited on pages 9 and 41)
[9] Ondfej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Shujian Huang, Matthias Huck, Philipp Koehn, Qun Liu, Varvara Logacheva, et al. Findings the 2017 conference on machine translation (wmtl7). Association for Computational Linguistics, 2017. (Cited on page 9)
[10] Jérôme Bolte, Aris Danillidis, Olivier Ley, and Laurent Mazet. Characterizations of lojasiewicz inequalities and applications. arXiv preprint arXiv:0802.0820 0826, 2008. (Cited on page 2)
[11] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W. Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 2017. (Cited on page 2)
[12] Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Processing Systems, 2018 (Cited on page 1)
[13] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS 2019), 2019. (Cited on page 3)

---

[14] Michel Coste. An introduction to o-minimal geometry. Istituti editoriali poligrafici internazion- ali Pisa, 2000. (Cited on page 2)
[15] Ashok Cutkosky and Harsh Mchta. Momentum improves normalized SGD, In Proceedings of the 37th International Conference on Machine Learning, 2020. (Cited on page 37)
[16] George F. Dahl, Frank Schneider, Z.achary Nado, Naman Agarwal, Chandramouli Shama Sastry, Philipp Hennig. Sourabh Medapati, Runa Eschenhagen. Priya Kasimbeg, Daniel Suo, Juhan Bac, Justin Gilmer, Abel L. Peirson, Bilal Khan, Rohan Anil, Mike Rabbat, Shankar Krishnan, Daniel Snider, Ehsan Amid, Kongtao Chen, Chris Maddison, Rakshith Vasudev, Michal Badura, Ankush Garg, and Peter Mattson. Benchmarking neural network training algorithms. arXiv preprint arXiv: 2306.07179 2023. (Cited on pages 9 and 40)
[17] Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In Proceedings of the 35th International Conference on Machine Learning, 2018. (Cited on pages 1, 3. 4, and 37)
[18) Hadi Daneshmand, Amir Joudaki, and Francis Bach. Batch normalization orthogonalizes representations in deep random networks. In Advances in Neural Information Processing Systems, 2021. (Cited on page 1)
[19] Timothy Dozat. Incorporating nesterov momentum into adam. 2016. URL https:
/ //openreview hetpeereviee.eee/ddf/iieeeeeee jwtpp///iidd000001888111111-1
(Cited on page 9)
[20] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, 2019. (Cited on page 3)
[21] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011. (Cited page 1)
[22] Ilyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimization under global lojdyka-ljjaieewizz inequality. Advances in Neural Information Processing Systems, 2022. (Cited on page 19)
[23] Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for nohbeerrn--eeeeeratte policies. In International Conference Machine Learning, 2023, (Cited on page 3)
[24] Guillaume Garrigos and Robert Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv: 2301. 2024. (Cited on pages 6, 7, 25, and 34)
[25] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. (Cited on page 7)
[26] Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021. (Cited on page 6)
[27] Charles Guille-Escuret, Hiroki Naganuma, Kilian Fatras, and loannis Mitliagkas. No wrong turns: The simple geometry of neural networks optimization paths. arXiv preprint arXiv: 2306.11922. 2023. (Cited on pages and 4)
[28) Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 2018. (Cited page 2)
[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv preprint 1522v:1512.03385, 2015. (Cited on page 9)
[30] Christopher Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 2013. (Cited on page
[31] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 2020. (Cited page 9)
12

---

[32] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, Hy- oukJoong Lee. Jiquan Ngiam, Quoe V Le. Yonghui Wu, and zhifeng Chen. Gpipe: Efficient training of giant neural networks using pipeline parallelism. In Proceedings of Advances in Neural Information Processing Systems, 2019. (Cited on page 1)
[33] Florian Hübler, Junchi Yang. Xiang Li, and Niao He. Parameter-agnostic optimization un- der relaxed smoothness. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, 2024. (Cited on pages 4 and 37)
[34] Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous-SGii algorithms. In Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238, pages 649 657. PMLR, 2024. (Cited on page 19)
[35] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 2018 (Cited on page
[36] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan, How to escape saddle points efficiently. In International conference on machine learning, 2017. (Cited on page 1)
[37] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Discovery in Databases, 2016. (Cited on pages I, 2, 4, and 19)
condition. Machine Learning and Knowledge
[38] Sarit Khirirat, Eduard Gorbunov, Samuel Horváth, Rustem Islamov, Fakhri Karray, and Peter Richtárik. Clip21: Error feedback for gradient clipping. arXiv preprint: arXiv 2305.18929. 2023. (Cited on page 19)
[39] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv: 1412.6980, 2017. (Cited page
[40] Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length-directo decoupling in non-convex optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, 2019. (Cited on page 1)
[41] Alex Krizhevsky. Learning multiple layers of features from tiny images. Lecture Notes, 2009. (Cited on pages 8, 9, 38, and 39)
[42] Shailesh Kumar. Classifying c0far100 images using resnets, regularization and data augmenta- tion in pytorch. sttpps//jjveee wtt.evinnnnnna.eeeeeeemmeeeeeeee cwm/ hon/kumar--shan httpaaawhhaaalaaaea/saaaooooeeee 2023. (Cited on page 39)
[43] Krzysztof Kurdyka. On gradients of functions definable in o-minimal structures. In Annales de l'institut Fourier, volume 48, pages 769-783, 1998. (Cited page 2)
[44] Criteo A. Lab. Criteo Itb click logs dataset. 2014. URL https: //ai:a/aalaab/aa/aa www.oo.rttooooo.ooo com/ download- criteo- 1 click- logs- dataset/. (Cited on page 9)
[45] Christian Lageman. Convergence of gradient-like dynamical systems and optimization algo- rithms. PhD thesis, Universität Würzburg, 2007. (Cited page 2)
[46] Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2017. (Cited on page 35)
inequality and [47] Guoyin Li and Ting Kei Pong. Calculus of the exponent of foundations of computational its applications linear convergence of first-order methods. mathematics, 2018. (Cited on page 2)
[48] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances neural information processing systems, 31, 2018. (Cited on page
13

---

[49] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward a theory of optimization for over- parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint WwXiv:200300037,, 2020. (Cited on pages and 4)
[50] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022. (Cited on pages 1, 2, 3, 6, and 7)
[51] Chaoyue Liu, Dmitriy Drusvyatskiy, Misha Belkin, Damek Davis, and Yian Ma. Aiming towards the minimizers: fast convergence of SGD for overparametrized problems. In Proceedings of Advances in Neural Information Processing Systems, 2023. (Cited on pages 2, 3, 4, and 6)
[52] Ji Liu, Steve Wright, Christopher Re, Victor Bittorf, and Srikrishna Sridhar. An asynchronous parallel stochastic coordinate descent algorithm. In Proceedings of the 31st International Conference on Machine Learning, 2014. (Cited on page 2)
[53] Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien, Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021. (Cited on pages 2, 6,
7, and 26)
[54] Zhi-Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 1993. (Cited on page 2)
[55] Maksim Makarenko, Elnur Gasanov, Abdurakhmon Sadiev, Rustem Islamov, and Peter Richtárik. Adaptive compression for communication--ffiiieee distributed training. Trans- actions on Machine Learning Research, 2023. (Cited on page 19)
[56] Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sampling without replacement provably help in federated optimization. OPT2021: 13th Annual Workshop on Optimization for Machine Learning, 2022. (Cited on page 6)
[57] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Proceedings of 4th International Conference on Learning Representations (ICLR 2016), 2016. (Cited on page 4)
[58) Tomas Mikolov, Martin Karafíát, Lukas Burget, Jan Cernocky, and Sanjeev Khudanpur. Recur- rent neural network based language model. Proceedings of the I 1tth Annual Conference of the International Speech Communication Association, INTERSPEECH 2010, 2010. (Cited on page 4)
[59] Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G Azzolini, et al. Deep learning recommendation model for personalization and recommendation systems. arXiv preprini arXiv: 00090, 2019. (Cited page 9)
[60] I. Necoara, Yu. Nesterov, and F. Glineur. Linear convergence of first order methods for non- strongly convex optimization. Mathematical Programming, 2019. (Cited on page 2)
[61] Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2004. (Cited page 2)
[62] Yurii Nesterov and Boris T. Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 2006. (Cited on page 2)
[63] Antonio Orvieto and Lin Xiao. An adaptive stochastic gradient method with non-negative gauss-newton stepsizes. arXiv preprint arXiv:2407.04335, 2024. (Cited pages 2, 8, 30, and 32)
[64] Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. In Advances in Neural Information Processing Systems, 2022. (Cited on pages 27, 29, and 34)
14

---

[65] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetoto, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of Advances in Neural Information Processing Systems, 2019. (Cited on page 36)
[66] Boris Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 1963. (Cited on page 2)
[67] B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical, 1964. (Cited on page 10)
[68] Quentin Rebjock and Nicolas Boumal. Fast convergence to non non-isolated minima: four equivalent conditions for c2 functions. arXiv preprint arXiv:2303.0000 2023, (Cited on page 2)
[69] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional Networks for Biomedical Image Segmentation. In Medical Image Computing and Compuler-Assisted Inter- vention MICCAI 2015, Cham, 2015. (Cited on page 9)
[70] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In Proceedings of the 35th International Conference on Machine Learning, 2018. (Cited on page !)
[71] Karthik A. Sankararaman, Soham De, Zheng Xu, W. Ronny Huang, and Tom Goldstein. The impact of neural network overparameterivation on gradient confusion and stochastic gradient descent. In Proceedings of the 37st International Conference on Machine Learning, 2020. (Cited
on pages 1 and 7)
[72] Zhiqiang Shen, Tianhua Tao, Liqun Ma, Willie Neiswanger, Joel Hestness, Natalia Vassilieva, Daria Soboleva, and Eric Xing. Slimpajama-de: Understanding data combinations for Ilm training. arXiv preprint arXiv:2309. 10818, 2023. (Cited on pages 9 and 41)
[73] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2015. (Cited on page 1)
[74] Chaehwan Song, Ali Ramezani-Keban Kebrya, Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparamettrrization for shallow neural networks. In Advances in Neural Infor- mation Processing Systems, 2021. (Cited on page 3)
[75] Hoang Tran, Qinzi Zhang, and Ashok Cutkosky. Empirical tests of optimization assumptions in deep learning. arXiv preprint 1rXiv:2407.018255 2024. (Cited on page
[76] Hossein Valavi, Sulin Liu, and Peter Ramadge. Revisiting the landscape of matrix factorization. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2020. (Cited pages and 22)
[77] Lou Van den Dries and Chris Miller. Geometric categories and o-minimal structures. 1996. (Cited on page 2)
[78] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez. Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 2017. (Cited on page 9)
[79] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models (and an accelerated perceptron). In Proceedings of 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019). 2019. (Cited on page 1)
[80] Luca Venturi, Afonso S. Bandeira, and Joan Bruna. Spurious valleys in one-hidden-laye layer neural network optimization landscapes. Journal of Machine Learning Research, 2019. (Cited on page 3)
[81] Rachel Ward and Tamara Kolda. Convergence of alternating gradient descent for matrix factorization. Advances in Neural Information Processing Systems, 36:22369-2253 2023. (Cited on page 5)
15

---

[82] Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Proceedings of the 36th International Conference on Machine Learning, 2019. (Cited on page 8)
[83] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1708.07747, 2017. (Cited on pages and 37)
[84] Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, 2022. (Cited on page 3)
[85] Jure Zbontar, Florian Knoll, Anuroop Sriram, Matthew J. Muckley, Mary Bruno, Aaron Defazio, Mare Parente, Krzysztof J. Geras, Joe Katsnelson, Hersh Chandarana, Zizhao Zhang, Michal Drozdzal, Adriana Romero, Michael G. Rabbat, Pascal Vincent, James Pinkerton, Duo Wang. Nafissa Yakubova, Erich Owens, C. Lawrence Zitnick, Michael P. Recht, Daniel K. Sodickson, and Yvonne W. Lui. fastmri: An open dataset and benchmarks for accelerated MRI. arXiv preprint arXiv: 181 1.08839. (Cited page 9)
[86] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. Communications of the ACM, 2016. (Cited on page 1)
[87] Hui Zhang and Wotao Yin. Gradient methods for convex minimization: better rates under weaker conditions. arXiv preprint arXiv: 3303.4645, 2013. (Cited on page 2)
[88] Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and landscape properties. In Proceedings of International Conference on Learning Representations (ICLR 2018), 2018. (Cited on pages and 3)
[89] Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. SGD converges to global minimum in deep learning via star-convex path. In Proceedings of International Conference Learning Representations (ICLR 2019), 2019. (Cited page 4)
16

---

Contents
Introduction
2
Related work
2.1
Function classes in optimization
2.2
Limitations of existing conditions
3
The proposed a--3-condition
3.1
Theoretical verification of the a-33-conittion
Theoretical convergence of algorithms
4.1
Convergence under the a a-B-condition
5
Experimental validation of the a-33-conditonn
5.1
MLP architecture
5.2
CNN architecture
8
5.3
Resnet architecture
5.4
Training of AlgoPerf workloads and transformers for language modeling
5.5
Additional experiments
10
6
Conclusion, potential extensions, and limitations.
10
A Additional explanation on PL assumption
19
Additional examples
19
Missing proofs
C.1 Proofs of examples satisfying definition
19
C.I.1 Proof of example
20
C.1.2 Proof of example 2
20
C.1.3 Proof of Example
21
C.1.4 Proof of example 6
................................
22
C.1.5 Proof of example 4
22
C.1.6 Proof of example 5
23
C.2
Convergence of optimization algorithms under a- --noditio
................................
24
C.2.1
Convergence of SGD
24
C.2.2
Convergence of SGD with Polyak Stepsize
26
C.2.3
Convergence of NGN
30
C.2.4 Convergence of AdaGrad-norm-max
34
Additional experiments
36
D.1 Half space learning
37
17

---

D.2 Experiment setup from section 2.2
37
D.3 MI.P architecture
................................
37
D.4 CNN architecture
................................
38
D.5 Resnet architecture
39
D.6 Verification of a-33-oonition by different optimizers
39
D.7 Increasing the depth of Resnet architecture
40
D.8 AlgoPerf experiments
40
D.9 Pythia experiments
41
Checklist
42
18

---

PL constart
PL consent
PL consrant
PL consrntt
010
090
1000
300
1000
303
1000
Epoch
(a) PTD.
PTB.
1.25
(O) 1.5
PTB.
1.75
PL constart
3x PL. condona
PL Pononaantt
PL. Roconsaant
200
010
850
300
1020
333
831 030
600
1000
930
031
030
503
1000
130
533
050
1000
Wikitest-2,
(6) Wikitent-2,
(4) Wikitext-2,
Figure 8: Training of layer LSTM model that shows Aiming condition does not always hold. We plot possible values of PL constant for different powers in (12). We observe that possible values of are of order 10-9 - 10-7 which implies slow theoretical convergence and contradicts practical observations.
A Additional explanation on PL assumption
Let us consider the relaxation of PL condition for some ó E [1,2] and (Assumption 3 in [22])
[ (2n))/2((((>) 1*) for all a E Rd.
(12)
Taking logarithms of both sides we continue
2 log( [f(())I) log(f(z) f*) 2 12g(
(13)
To satisfy PL condition for some 6, we need to find μ that satisfies (13) for all iterations. Figure we plot LHS of (13). We observe that the values of μ that satisfy (13) for all iterations should be of order 10-9 9 10-7 that leads to slow theoretical convergence [37]. Therefore, we claim that PL
condition does not hold globally for neural networks. Nevertheless, it might hold locally around the
solution (the value of μ closer to the end of the training are large enough).
B Additional examples
In this section, we list additional examples that satisfy Definition 1 and might have non-optimal stationary points. The functions of this form are typically used to simulate non-convex optimization problems and test the performance of algorithms on small or synthetic datasets [34, 55, 38].
Example Let f2: IR? + IR be such that
x² + y² f( 1+ x² + y²
(r - 1) (y) 1)²
fa(2.
(14)
1+ (a - 1)2 + (y - 1)2
then Definition holds with min, mings.nee f:(z.t)
41.369325 and a 1. Besides,
Definition does not hold with 3 = not satisfy Definition with 3 = 0.
C Missing proofs
C.1 Proofs of examples satisfying definition
highlight that we only show that a-B-condition holds for some a, B without giving all possible values of them.
19

---

C.1.1 Proof of example 1
Example 1. Let f, f2: I2 - R be such that
- - f2) with (x,,y)
[+tt)++1> f2(2,
(
(a+y++)) 1)
(*tvt))
then Definition holds with 19/2, +00) and a).
Proof. Let (2, Proj((xr, y), S). One show that the set of minimizers of in this example is S = {(z, u): ; -I -0--1/4 1/23. Moreover, fi for = -y. We will show that a a-8-condition holds for = For i 2 can be shown similar way with change of variables. We have
2(x + + -.f((a))) (1 (2+ w)
Therefore, we need to show that
2(x + y)
(a 3) (x + y)² + y)² ffi
(1+ (x + 2) (x - 2
1/21 5 Moreover, we can compute the projection operator onto S. After simple derivations, the projection can be expressed as
Note that () [+(++t)
(2+2)²
I+(-1/37
1 x- 1/2 -x+ 1/22)
Proj((,, v),
2
Therefore, need satisfy
2(x + y)
(x + y)² 1 (x y)²
x + y 1/2) 2 (a- 3)
(1+ (x 2)2
This is equivalent to
2(x + v) y 2 (a- 3) ( 3) (x -)) - (1+ (x 2)
< 2(x + y)
555 (1 + 2(x +) 3) (x+ 2 (a 3)( + u)² ( (x + y)- (15)
(1
We should satisfy the above for all values of + First, we need the coefficient next to (æ + y) in LHS to be larger or equal of the corresponding coefficient in RHS. This gives us _ 2 a - 8. This shows that 3 can not be zero. Using 2ab S a² + 62, (15) is satisfied as long as we have
2(x + y) 5
a (1 1 2(x + u) + +)+) (a 3)((2 + v) + (xr + w) + / + y)
Therefore, we should satisfy
coefficient next to (ar + 4)² : 2 a 3
coefficient next to (x + y)² 2 2a 2a - 3+1
coefficient next to 1 g 2 1
Note that if the first inequality holds, then the second one true as well. Therefore, from the first and third inequalities we get that the solution of the system of inequalities is a 2 5 and B E [4a/s, a). Li 2
C.1.2 Proof of example 2
Example 2. Let f, f2; R2 R be such that
f = (fi + f2) with fi v) = 1 2- 1a(x,)) = 1 e
(x-2)) 2)- (x-2)²
(4)
then Definition holds for some and 8.
20

---

Proof. Let (2,t) Proj((2, S). Again, we show that a-3-condition holds for f1; for fu it can be proved with the same arguments with change of variables. Note that f 0 and f > O. We also observe that S contains two points in total, and both of them of the form (t, () where for one & is close to (it is around & R 0.00067) and for second t close to (it is around note that = min, min(s.)) (i( E (0, 1) and = 9. 10-2 which means that we are close to interpolation.
1.99932). Besides,
We have in this case
Qzfi(r,y) = 2x exp( - 1²),, 0yfi(z,y) = 2yeep((-t" y²)). -2)).
Therefore, we need to satisfy
exp(-x² x² - (2x(1 - t) + 2y(1 - t)) 2 (a - 3)(1 - exp( - 1²)) - tz) (16)
Note that if 3 2 E R. Indeed, assume B = O, then since fi < and LHS goes to 0 while RHS to a (z, () > O.
and x. y + -00 then the inequality obviously can not be satisfied for all
Rearranging terms in (16), we should satisfy exp(-x² - =²2) + +2y² a B) + aff(2,)) 2 exp(-x² - (2x + 2yt) + - (B)
Using 2ab 1 a² + b2, the above is satisfied if the following inequality holds
exp(-x² - y² (2x + 2n²² + 3) + ac 2 exp(-x² -1-====226-- -22 (z² + 12² + 2t-) + (a- - 3)
exp(-x² (2² + y² a ( -3)
+ ac 2 - 21 (a B).
Since t E (0.2) we can choose a
8, so that x² y² 21 +a 32 2² 8² 2 0. Finally,
we choose a 2 8 so that ac 2 a - β = 8. We can estimate that a 2 72 70"
C.1.3 Proof of Example
Example 3. Let f, f2: R² R be such that
f= ff fe) with f1 3) 1+22+y² +g
fe(z,)) (x-2.5) (y ++5
(6)
then Definition holds for some a and | a 1.
Proof. Let (z, = Proj S). For this example, we have fi = (achieved (0, fī =
(achieved at (2.5, 2.5)). and f x= 0.408 (achieved at (2.471, 2.471)). Besides, we have f(0 0.587963 and f22,5, 2.5) = 0. 0.409091. Besides, e == min; m., fa(z, t) = (2.4711 2.471) = 0.00167918. Let us show that a-83-codition holds for fi; for f2 it can be shown similarly. We have 6y
6x
(zf v) = x4+ 22)2
0gfi(z,0) = x4 +2)
x
Therefore, we need to satisfy for some a and B
(4 12 x2 + 22 (I(x - =) - 1)) (a 1+
7 [z(2,1)
+
6.²² + 6y² - 6 2y (a
-af((z,t) x² 92
6(2² + 3²) (1 +))) (x² + + 6æz + byl
+ 5(2² + 12 + (2² + 1999).
The above satisfied for all x, and a - we have
6(0² +2) + a (16 + 8(0² + ) (1² + 2 3(1 2 +1) 3/"
+(++ + (1
To satisfy the above for all x, y we should have
t2,
2 2 + +t)
6 (+8af((z,t)
23+5
(2,((2)t)
11,
where = =1=2 22471, and (2, = 0.0016718. We can satisfy a-9--coniiion with a 2 1512.4586.
O
21

---

C.1.4 Proof of example 6
Example 6. Let f1, f2: IR² + IR be such that
x²2 y²
(x - 1)2 (y 1)2
f( 1 x2 + y²
f2(2.1)=
(14)
1+ (x - 1)2 + (y/ - 1)22
then Definition holds with z min, m nes J.2,t) R 41.369325 and B 1. Besides,
2
Definition does not hold with 3 not satisfy Definition with 3
Proof. Let tz Proj((z, 8). We show that a-3-condition holds for fi; for fo the proof is similar with change of variables. In this case, f = O, while f > (f* s 0.316988 at points (0. (0.159375, 0. 1.953555 and (0.840625, 0.840625)). Besides, we have == min; mi,(s fi(z, () R 0.048345 > 0. Moreover, We have
2x 0zf((z,v)= (1 x² y2)
2y ag5i(z,0) (1 x² + 2
Therefore, we need satisfy for some a and $
x² y2 - (2,()
(1+ (1+ + y²)3 (2x(x - 2) + 2y(y 1)) 2 (a - 8]
1 4
2x + 23²² 2xz - 2yt 2 (a- + + - (1 + x² 2/2
2x² + 2y² + afl(2, (1 2(x² + + (x² + ))) 2 2xz + 2yt +
() + )² + x22 + y²).
Note that if we take 3 = 0 and x, y + +o0, then LHS grows as (2, t)²2 + )² and RHS grows as axx + +y²)² therefore in the limit the RHS is larger. This implies that # 0. Using 2ab S a +b² the above is satisfied if we have
(2 + (x, + x²) + af((z)t(( + +22 + af, 2 (1 a +
2 12 + (a - B) + + (17)
Let us take a B = and a 2 min, min Ji(zt) 2 41.369325. With this choice, we have
2
3+
1+a-3=2521 (2,
a- =
Therefore, LHS is always larger than RHS in (17).
C.1.5 Proof of example 4
Example 4. Let Ji; fij be such that
f(W,S) = 2ram X W W S
I. Ex, w. T;)?, (w = = - w! 8,)², (7)
2Am
where X E Raxm = (w:) E R S (s,)² E R and rank(X) r We assume that X is generated using matrices W and 5 with non-zero additive noise that minimize empirical loss, namely, X = (W*)TS T +EE))EE (n) where W*, = argming.s f(W, S). Let X be any bounded set that contains S. Then Definition is satisfied with B and some 0.
Proof. Since & < r, then the matrix factorization problem has unique solution which can be found from SVD decomposition of [76].
We have
V Vw: fW, (w)) 82 X1y)84 V (W, (w..s, s, -Xis k
22

---

Therefore, we need to show that
((w)) 8j Xi))sz, - wi) + ((w) 83 -x,)) 83 .5) 2 a
a --2
3
(Xij - w 8))
2
2 (X1, (w 88)2,
since fij = 0. Since fig is convex w.n.t. Ws, the above holds if we have
2 [w) 8j Xi))² 2 2 wt Xz))² (w, 85 X1y)²
1
2 2/(00 63 X:i)
1
a- 3 (X,) wn s,)² ? (Xas (w $7)²
2
Let us take a = 8 + 1, then we can simplify the above as follows
1
2 w T 8, - X,y)
2 (X,, (wf) T 87)² 2 [8] w - X1))² + (w) 87 - X1y)² (18)
2
Since we consider X' to be bounded, then there exist r 2 0 such that ||s, |l. || || S r for all i and j. Therefore, the RHS in (18) is bounded by some constant C. From the data generation, we have that
c= min - (wx T ,3)² = min.y o > 0. Therefore, we can take a 2 2C to verify (18).
C.1.6 Proof of example 5
Example 5. Consider training two-layer neural network with logistic loss
- Ei= Si, J:(W,)) v) = Φ(v= v (Wx:)) + A1ll + 22|lW]
(8)
for a classification problem where <(t) = log(1 + exp( ()), W E R v E R a is a ReIU function applied coordinate-wise, y: E {-1,++1} is label and x; E Rd is a feature vector. Let X be any bounded set that contains S, Then the a-B-condition holds in X' for some 2 1 and 3 = a 1. 1.
Proof. Let (Z, 2) = Proj((W, S). We have the following derivations for gradients Rexd V f(W, o' (y (Wax)) y 1 + 2X2W,
Rk 3 V.J((W,)) (o (Wo(. o' (yxv o(Wx)) yy:(Wx) (Wx;) o 1wx,20
+2yLV = o'(uv (o(x:)) (WW,,,) ew + 2A1
where we denote 6mp == 1 E R Besides, we denote e, == 1 1z,220 E RR,, Note that the optimal value of 5 > 0 because of the 1.2 regularization.
Note that we have the following relations
T To(Wa;) xr4) (v. (W:;)) 1wr,20) (w I Wx.) (u ew, Wa:).
(19)
Note that S is bounded because of the L2 regularization. Since we assume that the interpolation does not hold, then f is always strictly larger than fe in X, and due to continuity there exists c = minke(n) min (Z, O.
We need to show that there exist some a and 3 such that
(iW, v), W Z)p + (V, u) z)
2 w)) u) - f((2,2)) ((f, -fr) Wi:)y: + 8' ('('(Voew) TW:)) ((100 W - -2) + +(WWx)) o Ew, v 2/)
u-)) + 221 v - 2)
+ 2W, W - Z)
2 a (d((((oo))) Wx;) + X ||/1/112 A₂ || o(vi(20 ( Zxx;)= - 21112112 - Az [11)
- B - Wx:) + 1 | // - -
+ o (()((oee)) ())))) Wa - y ( )T.) Zxza] + [y:( (ap(0ee, en) Tw vi(3 a ew.) Twx:)) +22 v 2) 22x (W, W Z)
2 a (o(u((00))) (W + 111101122 + > - 6(1((0 e Zx,) - >1112112 x21
-B(olui(vo ) War) + > -
(20)
23

---

Algorithm SGD with constant stepsize
1: Input: Stepsize y
2: for k= 0. 1,,,...; K do
3: Sample ~ Unif(n] and compute Vis, (a**)
4: Update model
k+1 x²
V.n (x**)
5: end for
where we use (19). Since á is convex, then have ('(x) - v) 2 ((x) Q(v). Therefore, using (19) again, we get that (20) is satisfied if we have
20(y o )w) Wx,) - oly.(v o ew)) Zx;) - Quu Wxx) -) W - -
2 a [o(u(v e Wx;) + Aillell + X21l 0 T Zx;) -
-3 ( Wx,) + +2 f31
Now we take a B 1 and simplify the above as follows
( Ww,) + ad(vi(z o )w) Zx.,)) + X (2 12 - 2) - ||0|| 2 ||
+22(2 W - Z) - |W]li - -1 + (a - 1)(a111211 + 2211Z1
2 2lui(v )w) Zx,) + o(u((2 o ew)
Wwx) + )
(a-1)f,
(21)
The above is satisfied if we have
Φ(yi(u o ew) " Wa,) + ac + A1 - 21 X2| W -71 + (a 1)(1=1 + 1
2 g(yi(v kw) Zx;)) (())(2)))) Ww,) + (a (aa-1)] -1)fi
(22)
because we also have (z e.) Zx,)) 2 c for a and (Z.z) S. Since (W, v) E X, there exist constants R, r 2 O such that ||a|| I r and ||]] S R, and RHS in (22) is bounded by
max + exp Rr|| (>x)))) 2 ( ) Zx,) + dyy (a o ew) Wx;). sE|n]
2 maxieia log(1 +exp (1 and B = a 1.
Therefore, we can take a
c-
Remark 3. The result suggest that the choice 3 is possible only if constants r and are small, i.c. locally around S only. In order to satisfy a----conition in larger set X, one needs to choose 0.
C.2 Convergence of optimization algorithms under a-B-condition
C.2.1 Convergence of SGD
Constant stepsize. In this section, we present the proof of convergence of SGD with constant stepsize under a-B-condition for completeness of the presentation.
Theorem 1. Assume that Assumptions 1-2 hold. Then the iterates of SGD (Alg, with stepsize
a-8 satisfy 2L
E [dit(( SS) 1
2L7
23
min E [f((a)) f
+
ii +
(9)
oSkcK
K 7a-3) a - 33"
3
Proof. Let oh E Proj([* S) satisfies Definition 1. Using smoothness we have Ex [1 [ < Ea [| [
dist(a* ,S) - - [ (2 - + EE (x+))11
dist(a" ,S?? - 207 [. (x - ffu( + +, [frg( - fill
+ 2L, (xx) -
dist(a* ,S' - 20 ) (cc
=
+ 27 + Ly) (ffix(( S.. (x()) + (fie (f(())))-
24

---

where (7) holds because of the a-B-condition and smoothness. Now we need to choose stepsize
y a= to get
I dist(x", .)² - 7(a- B) Ex [ist(( k+1 [)]]]
- (c
+ (3 + In) [A, (2.)) [ū]
Taking full expectation, noting that s independent of the randomness of ig. and performing simple derivations, we get
F [istt(>) ,S)
1 2L7
23 a 3 int
E [f((t)) M oskck
min
o
(23)
7a - 3) a - 3
Decreasing stepsize. Now we present the results with decreasing stepsize.
Theorem 4. Assume that Assumptions 1-2 hold. Then the iterates of SGD with decreasing stepsize
7k
7o VK+I
where 7/0 S a-8
21
satisfy
5IE dist(z .S)
5% int log( + +
23
min [[((a)) - 1-] s oskcK
+
o
(24)
4(a 3)70 K
- B
VK
B
δ
Bo
(25)
VK
Proof.
Similarly to the proof of constant stepsize SGD we can obtain
Eg [dist(x*** ++1 {)
I dist(x* ,8) - -u< 3) [fi((= Six (x
+ 2B + LAN)EE
since 7h I 7/0 I 2-d for all k. Now we follow standard proof techniques [24] for decreasing stepsize. Taking full expectation and dividing both sides by a 3 we get
E [istt(* S E [dist(x**+1 |5
23
2L 2
E.E [S(=*) [*] <
B
y Int +
3 2
int
Summing the above from iteration 0 to K- 1 leads to
K
[ist(<"", S)
2,
K-1 1
2L
K 1
TAEE [f(x*) - p*] <
a Q-8 3
B
2
int
7k +
a
3
0
int
Tk-
K=
k=0
k=0
Therefore, we get
min E [f(x*))-1 < 02k<K
E. [dist((z.) _S)3]
23
2
2h
2
K
-k=0
Tke
(a 3) 2k=0 7
a
3
3
k=
7kk
Using the results of Theorem 5.7 [24] we get
K
K K-1
47o
2
< 270 log(K K +1),
Σ
2
VK.
5
K=
k=0
Therefore, the final rate we get is
E dist(x0 (z" S
23
2L
2 log( K + 1)
02k<K
min E [[(x** [+]
<
(a - 3) Yov
+
3
2
+
int
47 VK
5
5 dist ( SS
5
Lo iu log( K + 1)
23
2
4(x 8)
a
/ K
α
9
in
25

---

Algorithm 2 mPS Stochastic Polyak Stepsize
1: Input: Stepsize parameter and stepsize upper bound Tb
2: for k= 0. 1,2,.... K do
3: Sample ~ Unif(n) [m] and compute V Vi, (a**)
4: Compute Polyak stepsize
(a,t Sth fi. (x*))12²
7 = min
5:
Update model
x+1 x² 7/2 Vig (z**)
end for 6:
C.2.2
Convergence of SGD with Polyak Stepsize
Constant stepsize parameter. In this section, we present the proof of convergence of SGD with Polyak stepsize (with constant stepsize parameters) under a-8-condition for completeness of the presentation.
Lemma (Lemma from [53]). The SPS stepsize satisfy
V (x+)
7th (fi((=") fiz))
(26)
c
Lemma (Lemma from [53]). Assume each fü is L-smooth, then SPS stepsize satisfy
}
Mmin
min
2cL mo 7h S mb.
(27)
Now we present the proof of Theorem 2 with constant stepsize parameters.
Theorem Assume that Assumptions 1-2 hold. Then the iterates of SPSmax (Alg. 2) with a stepsize
hyperparameter e > ]a- satisfy
min E [f(xt) - - OSkeK
E [dist(>" SSy] + 2ac1 2ac
(10)
K
where Tmin = min(1/2ol, ) and = Tmann (3a--
Proof. Let a E Proj(r*, 8) that satisfies Definition 1, then we have
Es [dist(=**) ++1 [5)))
x Es [||0 - =
+x || 21/1 - 2E [Tee (V (I. xz = [x (
dist(r A ,S)² - 2culf & [Tx(Ji, (x+*) - -Sc (x(
2 [71 (Ji, si:] + FE [Tx (Se, (x**) - -
C
= dist(I*, SS) - 2atEx (Tx (a*) - - (f fi,
+ 23E (fi - -fi [ (ar) - f(,)]
= disu(I*, SS, - Es 7k 2a - 23 1 = (Jig - 156)
+ 2aEx [Ta (1+))
26

---

where (i) follows from Lemma and a-B-condition. Now, since e > 2(a-0)- B) we get that 2a - 22
1
1/c > O. Therefore, using Lemma 2 and the fact that fi, I fiz (2f)) and fú, I (x²) we get
1
Eg (dist(c=++,,55)
I dist(x* ,5)² -Yuin
2a 23
Es (x* - -fil
+ Ex
- [(i)]] (2))
1
dist(æ ,))² Vmin
2a - 23
-
El (x*) fu (x/)
1
Yuin 2a 2/3
Ex (x Süel + 2a [(Fin (2 -f:))
c
1 :)
< dist(x", ,8)² Ymin 2a 23-
Es [fsz fae (z
+ 2amblE [(fie (x/) (xfi)((()))
].
Therefore, noticing that FEx [/s, (x/)] = 1 since sy independent its we have
(2a-23-44 Ymmin (2a (2a- 23 - 23-
+) Ex [5(x)) - S "ist(a",s)) Ex [dist(z s)yl + 2ar
Dividing both sides by "nnin (2a 233 - 1/c) and taking full expectation, we get
[[((x²) - -r $ Mmin (2(a B3 -1c--)
c
(E ( ,S)²] - [dist(x*+1,S)) #+1_ S))
1)
200hh
Mmi 7min (2(a 3)c 1) int.
Averaging for k E K -1] we get
min USkCK
E [[(( x
[ [ditt (x., 8
Vinin (2 - 3)c 1)K
20cmb
Ymin (2(a -)c 1) ints
that finalizes the proof.
Decreasing stepsize parameter. Now we switch to the analysis of SPS with decreasing stepsize parameters. We consider the stepsize DecSPS introduced in [64]
1 min Ck
fiu (rr fig Vi, (x5)]12 Ck- 7k-1
Yk =
with c-1 cp and 7-1 7b >> 0 to get
1
(-)( V
20
min
( COM6
CO
Lemma 3 (Lemma I from [64]). Let Assumption holds. Let {ck1a2o be any non-decreasing positive sequence of real numbers. Then we have
cu%b
Co%
min
and 7k 7--1-
(28)
2cxL
Ck
Theorem 5. Assume that Assumptions 1-2 hold. Let {cx)a20 be any positive non-decreasing
sequence such that Cj 2 a-g. Let Then iterates of DecSPS satisfy
min oSkc [[((z)) -f sr] < 2ÎD'CK-1
28
K-1 1
+ a- 3 int + K(a -3)
Σ
(29)
K
(a
B)ck
k=0
where DD
max dist(x* (5),, = max { (1,2011)) 0SkSk
1
20075
27

---

Proof. From the definition of the stepsize we have
The 1 1 fún (x*) fiz.
V fig (x²)
Ck
Therefore, we have
R V fi (x
Th (f(((*))) - fin). S Ck
Let 2/ = Proj(** .) which satisfies Definition 1. Now we have
dist(x ,S)² x |1+h1 - 21112
dist(x*, ,S) ,))- -2yx (V xt - -x/) + Th (fi(
Using a- e-B-condition we get
k+1 (an(tt+ 1 | - 2²11
< dist(2" 8)) - -207 - fi (x5)) + 2,3r0(fi (x-)) -57)
Lk (x²))
f(i -
dist(a* 5)²² -Nt (2x- -23 1/an) (fic(x*)) - fea (xt)
+ (2 + (fr. (xt)) - -fa.).
(0+))
Let us divide both sides by 7 > 0
dist(a**1, 888
,
(2a 233 1/ox) (fi, (x+) - fiv (2/))) + (2 + (fi, (xt)) f(.).
Kk
7k
Since by hypothesis ct 2 a-3. we get 2a - 2/3 1/cc 2 a - BB. Therefore, we get
dist(u*, 8))2
dist(x
(a - 3377k + (23 + 1/oc)
(x - Five (ag)
(frz (f)) - -.
(a - 8)7kk
a --8 B
Summing from k: = 00 K 1 we get
K
K
dist(a (8²
K-1 dist(x*t1, ,S}
Σ
Ji (x*) fia (x/))
(a B)7k
k=D (a
K=
k=
K-1 2/
K-1
Σ
(fra (fia(x))
f1.)
1
(fre (1))) f
a - 3
(a - 3)cx
k=0
dist(r", S)²²
K-1
dist(x* SS²
K 2
111 SS2
+ Σ
<
(a 3)r0
(a - 877x
(a - B8yTK
k=1
k=0
dist(z S
K-1 23
+
Σ
(fr (x())/)) -fi))
(a 8)7K-2
a 8
km
K-1
(a)) -..).
(a - B)c₁
k=U
28

---

Here we use the fact that "/k is a non-increasing sequence with k. We continue as follows
K-1
dist(r",
K-2
1
dist * +)))
Σ k=
Sua (x*) - lie (x x
+
(a
3)70
7k+1
7k
a - B
k=0
K-1
2/3
K
+
Σ
(fiz (2
- - +
Σ
(fix (1()) fin.
B
(a B)cz
k=0
k=0
D
1
K-2
1 1
Σ
+
α 8
70
7k+11
7k
k=0
K-1
K-1
2B
+
Σ
(fi (x
- -fi,) +
(f((zz) - f(,))
a
3
(a 3)cu
k=0
k=0
D
K-1
23
s
+
Σ
(fi. (x - f(,))
la 3YK-1
B
k=0
K-1
(Ji (xx) st..
(ax
B)ck
k=U
Here we use the fact that 1/Tu12 - 1/7. 2 0. From Lemma 3 we have
1
1
S c max
2L,
K
co7o
7.
Therefore, we continue as follows
1 K-1
Σ fx
fia (at)
2LD2CK-1
+ Σ
1 K-1
a B (frz (2 -fi)
23
K k=0
K(a B)
K
k=0
K
1
(Ja - -
(a - -3cck
k=
Taking expectation we get
min oskcK [[((a)) S
2LD2cK-1
2B
1
int
+
+
K(a - -3)
a a-
3
K
(a
B)ck
k=0
Corollary 1. Let cx = Vk + 1 with co, then iterates of DecSPS satisfy
2ÎD² + 20
23
min E [[f(a*) -r z ugkc
a 3 of
(30)
v K((a- - (3)
δ 1
+ Bo
(31)
VK
Proof. The proof directly follows from Theorem 4 using the choice ck w/+1 and the fact that 2/K.
Remark 4. It turned out that removing the bounded iterates assumption for DecSPS is a challenging task. Nevertheless, we believe that this is rather the technicalities of Polyak stepsize, but not of our assumption. Moreover, we highlight that [64] removed bounded iterates assumption in restrictive strongly convex setting.
29

---

Algorithm 3 NGN: Non-negative Gauss Newton
1: Input: Stepsize parameter y
2: for k= 0. 1, .,,, K do 3: Sample ~ Unif(v) [n] and compute VSs, (a**
4: Compute NGN stepsize
?
7k
V Lic |ا
2fg (ark)
5: Update model
x xx
7/ Vii (x*
end for 6:
C.2.3
Convergence of NGN
Constant stepsize parameter. In this section we present the proof of convergence of NGN with constant stepsize parameter under a-B-condition for completeness of the presentation.
Lemma 4 (Lemma from [63]). Let fi be L-smooth for all i, then the stepsize of NGN satisfies
I+ ?
(32)
Lemma (Lemma from [63]). Let fe be T-smooth for all i, then the iterates of NGN satisfy
4
2
2 - 0 22 (2 fi.
V Vi S
1 2 Th (xt - fin) 1+ max
(33)
Theorem 3. Assume that Assumptions I with a 2 3 + 1 and 1-2 hold. Assume that each function fi positive and 2 pos < c0. Then the iterates of NGN (Alg. 3) with stepsize parameter Y > satisfy
E dist(x", SS) (1+22L)² 3Lya(1 + 7L)o
min E [[f(x*)- osksk-1
ff s
27
+ max (2yL - 1,03 o pas + 2B0 Int
L
(11)
where 02 22 - -3) a 3.
Proof. Let a Proj(x* .S satisfying Definition Then we have Eg [dist(æ k+1 [) s Ex [|læAt] +1 =111
1aat - 2/21 2 (V fay (x*), - + Es fi (ot)
dist(x* ,5)2 - 22cEx (f - (x,)1
+ 2,E [F )- -Rii] + Ex [x21 V Sic (13]
(34)
From Lemma
- V (x,)))) (12
1 2 7n (f(x(x*) -5t))
4
( + I+
2
12yL -
2 +1 Six
0
(35)
Plugging (35) in (34) we get
Eg (x k+1 (1))) < disl(x ,S)2 2etEA (J (/,, ) - (3+ii)
4
+ 23Ex (fee (xxt) - -f 1 2
+ En (xt - f(.)]
2
Ex [ft]]]]] max ( (2yL 0
+ 1 ++7/
12 +
30

---

We have for (x*) füe (x =
(fr (ar) (fi fig). Now we write > p where
p is constant independent ig. Therefore, we have
Fg [dist(x x dist(r", ())) 20ypFE [Jig (30) - Sin (5
20 [fx (x*) - - 2axEE Icr (f
(2 )- {ia)]
47L
23Ex (Tu(Fir (x*)) - -(ii1 +
L (r (z**) - f())
1 ++2
L 1 7T maax
[ -
27.. + T: :0 Ex [Si]]
dist(x ,8)
22xple [Ji. (5.)))))
Sin (x
a -8+ 3+
27l.
)
2
1 + 27L ) Yk (ft) sti)
+ 2aEE [ex(Fix (x/) - {i,)]
2 max
12 -
2 + 0) Fx [si]]
(36)
1 1 I
We need to find such that
27
aC
7/k 20
1 27L
P)) - -(3+ + 27L
a(7h
7tk 2 0
2yT.
L
7 a - 3 1 2
2 ap.
Note that since 7 2 1-76
from Lemma 4, then it is enough if p satisfies
1
+ 7 a 1 2
2 op
> (2 - 1) 3) p.
(11+)))1++2)))
Let us take this bound as value of p. Note that since 8 1, then p 2 0. Therefore, the bound for Ek is the following
ck
= 7k -
- (2
S 7
a(1 + +
7 (a(1+ + 27:L) - (/ 33-1) (a -
a(1+gL)(1 + 2
L220+ + 20yL + 2(3+1) 11)
3
+7
a(1 +1 22
(11+2))1++21L)
< 3
By
+ a(1 + 7L)(1 + 27
2TL
= -T2())
(1)
31

---

Therefore, we get the following descent inequality
Ex [dist(=**1, |S8]
I dist(x",
2ap Es [ii (2") - Sie (3/%)
=To(t)
2
22 1
+ 20lEx (eie -x))
-(t)) + 1 7 max
Es [ft.
2 +
=Ta(??)
< dist(u -)) [fe, Jig (x/))]
+2(n")aaEs [f (x si,] + +3Ii())aEx (fx finl
+ ' )Ex [
dist(a ,) - --)
- +2) - sil (.T [f fi]] +3(()))E, [ft
(37)
Here we use the fact that a a minimizer of f and independent of é Unrolling the recursion, we get
To(:)
(E [ist(( ,8)²] -E [dist("), (1),)))))))))) ,))
S
E [f(())) -
K
K
Ei (7) + E2(r?);
(38)
where
=2(72)===ate E - Mil +Ta(7 E
(39)
int
int
pon
Therefore, we get
E |ist((" ,S)
E1(r)
E2(79)
E [[((x')- -r <
min 0ckcK-1
KTo(?)
To(>) To(?)
E [dist(x". [)]]
(1 L2
2
2 - 3 - 1) + a a-
3
1) + a 8 (1 + 7L)o
27L(a
L
max (2 - 1,0) o70
2yI(a 3 - 1) +
30
+
(40)
27L(a 3 aa
This finished the proof.
Remark 5. If all f; are convex, i.e. we can take a 1,, 0 in a-B-condition, then we get
E [dist(=", (s))
min OsksK-1
E[f(a*) - s*] s
(1 + 22 + + LL
2
+ L max {2yL 1,03 open
that coincides with the results in [63].
Decreasing stepsize parameter. Now we present the results with decreasing stepsize parameter.
Theorem 6. Assume that Assumptions I with > 3 + 1 and 1-2 hold. Assume that each function fi is positive and 0² ozos < co. Then the iterates of NGN with decreasing stepsize of the form
7k
7kk
7A
+
f (x+)))²
Vk
1
25 (z
32

---

satisfy
G
Colog(A (K + +1)
-0 2 + C2
min E [[(xa)- - |
F [dist(a", +
a - 3 io
oskcK
VK
v K
C4 log( K + +)
(41)
K
pus
1
δ
(42)
VK
where C₁ C2 C2 and Cs are defined in (43).
Proof. Similarly to the proof with constant stepsize parameter we can obtain (similar to (37))
Ex (dist(a**),S))
++1 I
dist 8)² - - + (2 )
BT, (5x + (Ts(72)0 pos
Note that we have
- 1 3) (1+ (1+ T.) + 2))
To(%k)
25x(er - 3)
(1 + Lo + 27) =: To(T))
27th
(7%%
a(1 + 7/ () (1+ + L)
27x a
Ti (Fx);
617%
T:
1 2 I.
I 6L =: (T()))
2
22 L -
73(22)
= 1 + I
max
1 +1 0
27 L max - 1,0) =: T:
Therefore, we can continue as follows
E [dist(a*t1,S))
++1
< E [ddist(** ; ,8)² - -To(T [M(x*t] - 1"1 + ao
+ (Fk (ox) + TT5(23) 00 opos-
This leads to
K-1
To - -1" <
E [diist("",s5) ss)]
+ Σ T2
+ Σ
BT, (ox)
k=
R=
K
+
0 pos-
k=
Therefore, we have
min E [ff(x*)- -1
5
1
E [diit((2" S) +
Σ KKI T T2(72)
a0
0skck
0= T TT(5k)
Σ k=0
K-1 To(Fx))
3 Σ K-1
T (7k)
Σk k== Ts(
+
20? iut +
Σk To( pposs
ΣKE To(Tx)
33

---

Following the results of [64] and [24] we get
K-
K
2
To
(m)
=
(1 + (1+
k=
k=0
SyvK K
5(1 + 7L)(1 + 27
K
K
Σ (5
= Σ
66%%
k=
s 12L log K + 1),
Σ T5
Σ
27 I. max (2> 1,03
K=
S 47 L max
(0xx(22/)) (27L. - 1, log( K 1),
Σk=0 2
IKJT
Σ k= (1+7L)(1427L)
(a-88
> (1 + Ly
a(a - (3)
Thus, the final result can be written as follows
min -[(( 54 $ 5(1+>L)(1 + 2) OSkCK
[d" SS) + 12L,2 log(K +1)
0.. int
87VK
> K- Ti Tik
RK
2k=0 Ta(TT))
> 2k= To(?k))
k=
int
Rー (T(
ppss
5(1 + L1 + L)
E [ddis((=), ,
8yVK
15L + +1+
+ 27
log K +
2o int
2VK
(1 + (L) + 2.2
(a- 33) 30 int
5(1 ([1+>D)(1+ + L) m, 1 03 log K + +1)
+
2VK
pos'
Now is left to use the definitions of constants C1, C2 and C3
G = 5(1 + (1 + L.)
(43)
87
C₂ = 15L + LL) + 27
2
Cs = (1 + 7 7b) + 17T.),
C4 5(1+>L)(1 + 2 Ly max 1annxx2211) 1,0)
2
C.2.4 Convergence of AdaGrad-norm-mart
Theorem 7. Assume that Assumptions 1-2 hold. Assume that for all k 2 0 stochastic gradients
satisfy | fyg (=*)]] < G2 for some G > 0 and b 2 2Lr
a-3. 3. Let D2 max; f(("")]2 Then the
34

---

6: end for Algorithm 4 AdaGrad-norm-max
1: Input: Stepsize parameter 7y > c, = 0, b- 2 a-
2Lg
2: for k k= 0, 1, 2,.... K do
3: Sample i [ni and compute V /i (a+t)
4: Compute AdaGrad-norm-me stepsize
c = max { (ch V fig (a )133}
bx = by + c:: 7/k bk
5: Update model
Nt = x² 7/ V Sis (xtt)
iterates of AdaGrad-norm-max (Alg. 4) satisfy
dist(x* ,8)2
min oSkcK [[((x))
{( - B) 12 1
2a
+
(a K)D on G2K BE,
o
+ coo 2 int
(44)
We see that if K is large enough, then we recover the standard convex rate of Adagrad of order O(K-1/2) [46].
Proof. Let o = Proj(u*, .) satysfying Definition 1. Then we have
(1 ,S}
< ||a - x//1
11* - -x/112 - 27 (V li. ) - (+1)11 S dist( ,5) 22 (frr (I*) (a,z))) (f (at) -f%)
+ V [ \12
S dist(r k ,S)² - 2007 2007 (2²) - -1a((()) (Je, (x*) -(te)
- 23
+ Lfa (x+) -(t))
dist(x" ,5) - 2007/ (Si, (xtt) - -Si + + - S. (1(+1) + 2,3r (x*)) -(t)
+ 22 (x²1) - -Kr.)
dist(a* ,5)² - 22 B Lnn)(fa - f%y +20 (fi, (1/g) - -fie)
(45)
Note that we choose b-1 2
267 Since by is inreasing sequence, then we have for any that a a-3.
by 2 Therefore,
LTk = -
S 1-2 < L 7 a - B
7 bb
by
22///-0
2
This means that
27x - 8 Lyk) S 27/2(aa -3 8- a-82//2 -- - -B).
Thus, can continue (45) follows
++st < dist(a* (5)²
7 (a - (f) - + 2a
?
(frs (1/) -()))
by
b%
35

---

We know that by is increasing sequence that satisfy
V + D2(K + 1) S by S bx-1 S V + G2K.
This leads together with the fact that both fix firh))) fin and fin (xt) - fir are non-negative to
dist(x ,)2 s dist(a", ,)
7 -(a (e)3))(iz - -
v 62, +
+ 2a
(Jix (1/) - -Stt))
12 D2(K + 1)
7/ (3)
dist(z ,5)² (
(fi,(x²)) - -fu (2x))
V 12 + G2K
2ar
(Frr (x²) - -Fi).
6 + D2 11)
Taking the conditional expectation get
Es [f(x*)
dist(=",S)
Es dist((**11, (t,,) _5) 7(x - (3
20
0 int
v G2K
7(a B)
VR + D2 + 1) 3)
which leads to the following bound
[dist(z". .5)
Eg [diss(=**),,s) ,8)
En [f(=t) - s*] s
V 6 +
7(a= 3B)
7/ 3)
2a
+
int
2
62 G2K.
Vo_, + D2 1)(a - 3)
Averaging over K iterations we get
min E[f(z*) -1 < oskck
Σ [f(a") 1
K km0
dist (I* ,8)²
4K(a= - (3) 11 + GGK
K
2x
+ (a - (a-B)K
Iin V 12, G2K
12
D2 + 1)
K=
dist ,8)2
7K(a= - () 112 /121+G2KK
+ (a B)K an V 12, G GKK D2(K DR
2a
o
+ +ao? int
K
D Additional experiments
For all the experiments, we make use of Py Torch [65] package. LSTM, MLP, CNN and Resnet experiments are performed using one NVIDIA GeForce RTX 3090 GPU with a memory of 24 GB. For training Algoperf and Pythia language models, we resort instead to 4xA 1000SSXM4 GPUs, with memory of 40 GB each, and employ data parallelism for efficient distributed training. When necessary, we disable CUDA non-deterministic operations, to allow consistency between runs with the same random seed.
36

---

0.6
410
Angle
0.3
24.4
0.12
5520
0.50
03
32262
35399
3020
1080
2003
1000
1000
10001
(teration
3300
Figure Training for half-space learning problem with SGD. Here T(x)) = (V (2* -x
aff (x*) > Sie (xx)) ))- 3 fc, (a*) assuming that f = 0.000523853; angle denotes <(Vf f2=*x))
x²).
D.1 Half' space learning
Half Space Learning problem corresponds to the following optimization problem
A f(x) o a.) + 2 ||==11?
where {a,, bi 1.::::0; E Rd Ur E {0. given dataset, A 10- and is a sigmoid function. For the test, we create synthetic dataset that contains 20 samples for both classes. We sample data points from normal distribution where each class has its own mean and variance value of 2. We use SGD with learning rate ] and batch size for minimization task.'
We observe that the gradient norm becomes saddle point. This leads to possible negative angle between full gradient and direction to minimizer. Nevertheless, we demonstrate that even for such highly non-convex landscape with many saddle points our a-8--conition holds for large enough values of a and 3.
quite which means that SGD trajectory goes through
D.2 Experiment setup from section 2.2
We use 3 layer LSTM based model from Hübler et al. [33]". The model for PTB dataset has 35441600 parameters while for Wikitext-2 dataset the model has 44798534 parameters. To train the model, we choose NSGD with momentum [15] with decaying stepsize and momentum parameters according the experiment section from [33]. We train the model for 1000 epochs with initial stepsize values 158 and 900 for PTB and Wikitext-2 datasets respectively. We switch off dropout during measuring stochastic gradients and losses for a a-8-condition. We run the experiments for 7 different random seeds and plot the mean with maximum and minimum fluctuations.
In Figure 10, we plot empirical aiming coefficient (V((a")=="="") for full loss f: mean of stochastic J(z*)
losses across runs along with maximum and minimum fluctuations from the mean; pairs of (a,, ()) that satisfy a-3-condition across all 7 runs. We observe that for both datasets, there a plateau at the beginning of the training. This part of the training corresponds possible negative values of the empirical coefficient Aiming condition. After this, it becomes stable and positive.
Besides, we demonstrate that possible values of pairs of (a: 3) that satisfy a-3-condition are large. We believe, this happens because the full loss f has minimum value of around 3.5 while individual losses have f7, i.e. the model is far from the interpolation regime (when f" f())
D.3 MLP architecture
We use MLP model with fully connected layers. We the dimensions of the second layer to be equal, i.e. the parameter matrix of this layer is square. After the first and second fully connected layers we use ReLU activation function. We train the model in all cases with fixed learning rate 0.09 for 1500 epochs and batch size 64 on MaSHI [83] dataset. In Figure 12, we plot the
'We the implementation from [17] that be found https://github. htt.://....ooomaccaaaa5....a Escaping-sadee srriing-sdddlsss Sonddles-using-Steee Stochastic- Sraiii-rrrrieeteeeeeeeee 'The implementation can be found following the link https://github.com fhue// grramtter-agnostic--
37

---

Aimine constart
770
Tut
Epoch
Epoch
Epoch
Alning constant
13
12
50
2
Full
200
600
600
300
200
200
1000
203
435
600
500
1000
Epech
Figure 10: Training of layer LSTM model on PTB (first row) and Wikitext-2 (second row) datasets.
) Here Txxk)= = fi (xx)), x² - x²) a(ffx((*) fi (xxk)) (x)) assuming that f;" 0.
690
5
2-22%
800
120-110
580700
800
520
025
3.00
540
111100
130
135/00
55000
300001
30070M
(8) 20rd
layer size 322
(b) 2012 layer size 1288
(0) 2nd layer size 512
198330
(9858)
50830
(7500
1000
2302.0
19002
08345
19000
41000
679.00
47010
(4) 2nd layer size 1024
(c) 2nd layer size 2048
(1 2nd layer size 4096
Figure 11: Values of a and / during the training of 3 layer MLP model on Fashion-MNIST dataset varying the dimension of the second layer. Here T(xx) (V (a*), x - x²) -a(fi, (x*) fa (I*) Bf (x*) assuming that ft = 0.
mean stochastic loss across 4 runs along with maximum and minimum fluctuations, and in Figure 11 possible values of and that work over all random seeds and iterations satisfying a 2 3 + 0.1.
We observe that the magnitude of the smallest possible values of a and 3 increase till up to the second layer size 512, but then it starts decreasing the model becomes more wverpparameterized. This leads to smaller values of neighborhood (B3oi as we expect in this setting.
D.4 CNN architecture
use CNN model with 2 convolution layers followed by fully connected one. After each convolution layer, we use max- max-pooling and ReLU activation functions. We train the model with cosine annealing learning rate scheduler with maximum value 0.01 and batch size 64. We train the model CIFARIO dataset [41] for 1500 epochs. We run the experiments for different random seeds. In Figure 13 we plot possible values of a and satisfying a 2 3 + 0.1 that work across all runs and iterations.
We observe that increasing the dimension of the second layer of the model makes the model closer to over- prameteriziiiiin: values of stochastic losses decrease. We observe the same phenomenon as Appendix D.3: minimum possible values and 3 increase up to 128 number convolutions, but then it decreases for larger number of convolutions. This happens because the model becomes more wver-paaaeeterized Moreover, the possible difference between and B tends increase with number of convolutions starting from 128 convolutions.
38

---

Sesthalle Lnn file)
Sorthehee Lons 5147)
Stochuttc Loss
293
1200
1003
220
12:0
2000
200
2000
Epoch
(a) 2nd Jayer
layer size 128
2 layer size
Sortheeie luve
Sortherte
Epoch
Epoch
Epoch
(4) 2nd layer size 1024
(c) 2nd layer size 2048
( 20.2t layer size 4096
Figure 12: Values of stochastic loss during the training of layer MLP model on Fashion-MNIST dataset varying the dimension of the second layer.
1009
12
32
(2) # Cumvlutions 32
(b) # Convolutions
(c) # Convolations 128
2014
15
15
00
50
103
10
12
10
12
Convolutions
Convolutions
Cunvolations
Figure 13: Values of and 3 during the training of CNN model on CIFARIO dataset varying the number of convolutions in the second layer. Here T(xxx (V (x*), x²) alfi (x*) Sig (2 Brg (x*) assuming that f O.
D.5 Resnet architecture
We use the implementation from Kumar [42]. We train the model on CIFAR100 dataset [41] for 1000 epochs. We use one-cycle scheduler with maximum learning rate 0.01. To compute dense stochastic gradients, we switch off dropout during evaluations of stochastic gradients and losses for a-8-condition. We run the experiments for 4 different random seeds and plot the mean along with maximum and minimum fluctuations.
In Figure 15 observe that the minimum value of stochastic loss increases with batch size which means that the model becomes further from over-parameterization.
D.6 Verification a-S--onnition by different optimizers
Now we turn to another interesting question: how does the choice of an optimizer affect the practical verification of the a-$-condition? To explore this question, we train Resnet9 model with SGD, SGDM, and Adam. We report the results in Figure 16 varying the batch size used in the training. Comparing the values of a and for SGD (from Figure 6). SGDM, and Adam, we observe that the loss landscape explored by the Adam optimizer achieves smaller values of a and B. Moreover, values of a and /3 found by SGDM are typically smaller than those found by SGD. This result may shed light on why momentum (from comparison of SGDM against SGD) and adaptive stepsize (from a comparison of SGDM against Adam) are typically beneficial in practice: these more advanced algorithms explore better part of loss landscape from the a-3-condition point of view.
39

---

Strcheate Lns fil?)
Secheetcion Less Kiih)
or
Stathade
10
300
230
653
1000
200
P30
1000
-00
830
1000
#
# Convolutions
Convolutions
Stoetreee Loa
to
Stochwete
to
Stochwete
Epoch
Epoch
Epoch
(d) # Convolutions 256
(c) # Convolutions 512
(1 Convolutions 2048
Figure 14: Values of stochastic loss during the training of CNN model CIFARIO dataset varying the number of convolutions in the second layer.
Late
100
(4) Ratch size 64
(b) Ratch size 128
Barch size 256
(4) Botch size 612
Figure 15: Training of Resnet9 model on CIFAR100 dataset varying the batch size.
Table 3: Training details of large models from Appendix D.8 and Appendix D.9
Dataset
Model
Batch Size
LR
B1
8/
Weight Decay
Warmup
Criteo 1TB
DLRMsmall
262144
0.0017
0.93
0.995
0.08
0.02
Fastmri
U-Net
32
0.001
0.9
0.998
0.15
O8GB
GNN
512
0.0017
0.93
0.995
0.08
0.02
WMT
Transformer
128
0.001
0.97
0.999
0.15
0.1
Slim-Pajaman Slim-Pajama-627BB
Pythia-70M
256
0.01
0.9
0.95
0.1
0.1
Slim Hain-Pajama-6223 627B
Pythia-160M
256
0.006
0.9
0.95
0.1
0.1
D.7 Increasing the depth of Resnet architecture
In our next experiment, we aim to investigate how the a-8-condition behaves increasing the depth of model. To do so, in addition to training Resnet9 model,
Resnet18 and Resnet34 models on CIFAR 100 dataset. The results in Figure 17 suggest that the values of a and 33 tend to decrease with the depth of model. These observations align with those from Section 5.1 and Section 5.2 as the constants a and 3 decrease as the depth of the model increases.
D.8 AlgoPerf experiments
For each all aforementioned tasks, we repeat the training with 3 random seeds to create more stable results. The detailed model architectures are given in [16]. In Table 3 provide the parameters of optimizers we use for each task. The loss curves are presented in Figure 18. For each workload, we the experiments for 3 different random seeds to obtain more stable results. The hyperparameters of optimizer NadamW are chosen such that we can reach the validation threshold set by the organizers? We employ cosine annealing learning rate schedule that reduces the learning 1e 10, with initial linear warm-up. For each workload, we run the experiments sufficiently enough so that we reach the validation target threshold and the stochastic loss becomes sufficiently stable.
'The quality of performance is measured differently from one task to another; we defer to the [16] for more detailed description of the competition.
40

---

27447
TaT Ter
2707
21500
152
(2) batch size
(b) batch size 128
(c) batch size 256
(4) batch size 512
172
(EO 7-33-
270
(4) batch size
(b) hatch size 122
(c) batch size 256
(4) batch size 512
Figure 16: Training of ResNet9 model CIFARI00 dataset varying the batch size with SGDM (stepsize 0.01 and momentum 0.9 with OneCycle learning rate scheduler) and Adam (stepsize 0.0001 with default momentum parameters with OneCycle learning rate scheduler) optimizers. Here T(xx) = fi, (x*), -===>=> oiff, (x*) ) fi, (a ))- - -3,,, (x*) assuming that f 0. Minimum taken across all runs and iterations for given pair of (a, (8). We plot values of a, in a-8-condition
for SGDM (first row) and Adam (second row).
min 7(Puh 10-5
105
min Flnh
475
579
160
45
(s) batch
butch 128
(c) basch 256
80
603
115t
405-
20
min Toaa
155
min
705
750
5035
100
-044
408
70
72
74
70
75
(0) batch size 64
(b) batch size 128
(c) batch sise 256
Figure 17: Training of & 8 and Resnet34 model on CIFARI00 dataset varying the batch size SGD (stepsize 0.01 and momentum 0.9 with OneCycle learning rate scheduler). Here T(xx) fV (x*),
), r - x² a( (a*) fix (xx) - -f (I*) assuming that fi = 0. Minimum is taken
across all runs and iterations for given pair of (a, 3).
D.9 Pythia experiments
For each all aforementioned tasks, we repeat the training with random seeds to create more stable results. We train Pythia 70M and Pythia 160M [8] on publicly available Slim-Pajama-627BB dataset [72]. Both models are trained on sequences of length 2048, and makes use of batch size of 0.5M tokens, which amounts to batch size of 256 samples. We use Adam W optimizer and cosine annealing with linear warmup, with hyperparameters specified Table 3. The stochastic loss and training perplexity are reported in Figure 19.
41

---

Sgidhage Lag
Spergatt Lo06
Stoclettt LOGE
Seccastc
0.77
0.3
9230 1000
1066
1000
Boraton
(2) Cáiico ITB DL M.MMalall
(e) Facimri
(b) OCTO GNN
ec) WMT Transforme
U-Net
Figure 18: Training of large models from AlgoPerf benchmark.
120N22 LOGS
101
Pepiesiy
10
9900 Kiraaion
Earadon
Tokens, X12
Tokens,
(4) Slim Pajama 6278 Pythis-TMM
(b) Slim- Pajama 627B Pythas
(c) Slim Pajama 627B Pythis 60M
(d) Slim Pajama 627B Pythin- 66M
Figure 19: Training statistics for Pythia language models.
E
Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract, we shortly list all the main results of the paper. In the introduction and related works, we demonstrate the limitations of previous works and explicitly list the contributions of our work. We support theoretical claims by extensive experimental results various deep learning benchmarks.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long it 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 provide section in the end of the main body where we discuss several limitations of our work.
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 separate "Limitations" section in 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 well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
42

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We explicitly state class of functions propose in the paper well as other assumptions on the smoothness and noise of ERM problem. We explicitly state all convergence guarantces for 4 different optimization algorithms. The proofs are deferred to the appendix.
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 or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: For most of the experiments we use existing open source Github repositories making small changes in the code track necessary quantities during the training. We provide the links to all used repositories. Besides, we list all parameters of optimizers to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
43

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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) 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) the contribution is a new model (c.g., a large language model), then there should either be way 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 authors are welcome to 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.. to registered users), but it should be possible for other researchers have some path reproducing 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?
Answer: [Yes]
Justification: For each open source data and code we attach the link. All codes can be used almost immediately with small changes that are needed track necessary quantities for validation of the proposed condition.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ public/ cebllccggudes... SooodeSubmissiioni
cy) for more details.
While 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cttcccc http//ubllcccce htwpc//ggiie//eeeeeeee httpe//ggiiiee/oedeuiuiiiiieee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
44

---

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 understand the results?
Question:
Answer: [Yes)
Justification: provide all hyperparameters and training details in the corresponding section of the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary 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: [Yes]
Justification: For each instance the experiment section, we run tests for several random seeds (exact numbers are indicated in the experiment section of the appendix) to get more stable results. For each figure with training curves, we plot the mean and maximum and minimum fluctuations around it.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
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?
Answer: [Yes]
Justification: We provide information about GPU that we use for our experiments in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
45

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/ //tppr/////ur...../e catss.cc/p// cttppcccc//eeeeeeeeeeece htt.:///iehiisuueeellleoele ines?
Answer: [Yes]
Justification: We follow all the rules listed following the link above. In particular, anonymized the paper and attached the code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: we provide an impact statement in ??.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or 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.
The conference expects that many papers will be foundational research and tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 such risks.
Guidelines:
46

---

The answer NA means that the paper poses no 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 to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use open-source datasets and code. For all used codes we explicitly cite the corresponding paper Github repository.
Guidelines:
The answer NA means that the paper does not use 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 license (e. CC-BY 4.0) should 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 in the package should be provided. For popular datasets, paperswi thcode. 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 derived asset (if has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's '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 assets.
Researchers should communicate the details the dataset/code/moddll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
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)?
Question:
Answer: [NA]
47

---

Justification:
The paper does not involve crowdsoureing 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 in the main paper.
According to the NeurIPS Code of Ethics, workers involved 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 crowdsoureing 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 we expect authors to adhere to the NeurIPS 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.
48


Reviews:
[{"review_id": "udcaswLAIt", "reviewer": "Reviewer_mWKG", "summary": "This paper proposes a novel class of functions and proves convergence of gradient descent (and some other optimizers).\nContrary to some previous classes, in relation to deep neural networks, this new class does not require extreme overparameterization.\nIn addition to theoretical convergence results, experiments are provided showing that some example neural networks seem to belong to the function class.", "questions": "In my understanding, if the interpolation condition holds, then the new proposed class is equivalent to PL. Is that true and why is this not explained in the paper?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is written very clearly. It provides a new theoretical tool for studying convergence in deep neural networks, and has the potential of high impact.", "weaknesses": "Some of the highlighted differences with respect to previous work are unfair, in particular previous work in overparameterized models. \nFor example, figure 1c and 1d show very small values of the PL constant in practical problems, implying slow theoretical convergence. However, the same is true for the new proposed class of functions, where the PL constant is replaced by alpha-beta, which seems very small in most experiments (alpha and beta have very similar values) thus implying very slow convergence. It would be easy to plots alpha-beta values in experiments to verify how large it can get, and thus show how fast is the convergence predicted by theory.  \n\nAlso, all other function classes considered in previous work guarantee convergence to a global minimum, here instead convergence theorems have an extra term since different data points have different optima, and it's not clear how big are those terms. It may be that these terms are so large that the bounds become trivial, for example when those terms are much larger than the decaying 1/K terms. At least some discussion comparing the magnitude of such terms would make the work more valuable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough reviews, insightful comments, and valuable\nquestions regarding our paper.\n\n***W1.*** \"Some of the highlighted differences...\"\n\n***A to W1:*** This is a good comment and we will provide further detail on it in a revision. In Figures 1c-1d we observe that the empirical PL constant can be of order $10^{-7}.$ Besides, in each figure where we plot the empirical values of $\\alpha$ and $\\beta$, we include only those values that satisfy $\\alpha \\ge \\beta + 0.1$. Let's now compare the optimization terms decreasing with $K$ in the rates under both conditions: $\\frac{L}{K(\\alpha-\\beta)}$ under the $\\alpha$-$\\beta$-condition vs $(1-\\frac{\\mu}{L})^K$ under the PL condition (see Theorem 3.9 in [1] for the explicit rate in the deterministic setting. Note that the contraction factor in the rate in the stochastic setting is even worse; see Theorem 5.10). We refer the reviewer to Figure 3 in the separate pdf file where we provide plots for several values of $L$ and $\\mu=10^{-7}, \\alpha-\\beta=0.1$. We observe that the theoretical convergence under the $\\alpha$-$\\beta$-condition with empirical values of $\\alpha$ and $\\beta$ is always more favorable than that under the PL condition with empirical value of $\\mu.$ In addition, from a theoretical point of view (see Theorem 1) we can choose the stepsize of order $\\mathcal{O}(\\frac{\\alpha-\\beta}{L})$ which implies that the first term in the convergence bound is $\\mathcal{O}\\left(\\frac{L\\mathrm{dist}(x^0,\\mathcal{S})^2}{K}\\right),$ i.e. it is not affected by $\\alpha-\\beta$ at all which shows a clear advantage of $\\alpha$-$\\beta$-condition over PL condition.\n\n***W2:*** \"Also, all other function classes considered in previous work...\"\n\n***A to W2:*** We refer to the general rebuttal.\n\n***Q:*** \"\nIn my understanding, if the interpolation condition holds...\"\n\n***A to Q:*** Good question! In the interpolation regime, we have $f_i^* = f^*.$ This means that $\\sigma_{\\mathrm{int}}^2 = 0.$ Therefore, $\\alpha$-$\\beta$-condition reduces to \n$$\n\\left<\\nabla f_i(x), x-x_p\\right> \\ge \\alpha(f_i(x) - f_i(x_p)), \\quad x_p = \\mathrm{proj}_{\\mathcal{S}}(x).\n$$\nIf we replace $x_p$ by some fixed point $x^*\\in\\mathcal{S},$ then the functions satisfying the above are called quasi-convex. However, to the best of our knowledge, there is no known relation between quasi-convex and PL functions. Therefore, the interpolation regime does not imply that the $\\alpha$-$\\beta$-condition reduces to PL. We will add a comment on this in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nI0Ayry7AL", "reviewer": "Reviewer_W37Q", "summary": "This paper introduces a new regulatory condition named $\\alpha$-$\\beta$ condition. To motivate the necessity of such condition, it first show empirically that the aiming condition is not always satisfied in neural newtork training. The paper then support the $\\alpha$-$\\beta$ condition with $i).$ examples (including a shallow neural network) that satisfies such condition; $ii).$ convergence guarantee of SGD, SPS, and NGN under such condition combined with smoothness; and $iii).$ Empirical evidence that the $\\alpha$-$\\beta$ condition holds during neural network training.", "questions": "Is it possible to establish the convergence rate of the non-stochastic gradient descent based on the proposed condition and the smoothness condition?", "limitations": "The author mentioned some limitations of the paper. However, I believe that the biggest limitation is the missing theoretical connection between the proposed condition and neural network training, which is not mentioned in the paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The newly introduced $\\alpha$-$\\beta$ condition covers the case where the function has saddle points.\n2. The paper tries to give examples for which the condition holds\n3. The paper empiricallly indentified cases where the aiminig condition does not hold", "weaknesses": "1. The proof for Example 4 (shallow neural network) is problematic. In particular, based on the definition and assumption of $S$, the paper derived $f_i^* = 0$, and that points in $S$ have bounded norm (which is necessary to obtain the equation below line 684). However, these two conditions are contradictory as the logistic loss only achieves zero training loss when the output of the neural networks has magnitude infinity. This breaks the proof of Example 4.\n2. The theoretical implications of Theorem 1-3 are week. The minimum loss during training is upper bounded by $O(\\beta\\sigma_{\\text{int}}^2)$ which can be extremely large. First, in real world applications, it is very hard to control $\\sigma_{\\text{int}}^2$ as the model output can vary a lot based on different inputs (this is not a big issue, as many previous works assumes the boundedness of $\\sigma^2$). Moreover, $\\beta$ can be as large as $10^6$ in order for the condition to hold, as shown in Figure 4. Multiplying the two gives an error region that does not seems to be small enough.\n3. There is no strong theoretical evidence that the proposed condition holds for neural network training in general. In particular, a major significance of developping the regulatory condition for neural network training is to theoretically show the convergence of neural network training based on such conditions. The proposed conditions loses such significance because it misses the theoretical connection with neural network training.\n4. The empirical justification that neural network training satisfies the proposed condition is limited. Figure 4 only shows the condition holds for large $\\beta$ (weaker condition), which does not imply great applicability of the condition in showing the convergence property. Indeed, Figure 5-7 shows that the condition holds for smaller $\\beta$ for harder tasks, which is quite conter-intuitive since harder tasks should have less flavorable loss landscape. However, it should be noticed that the results is obtained by using $x^K$ to approximate $x^*$. Therefore, the seemingly flavorable result may come from the fact that in harder tasks $x^K$ is a worse estimator of $x^*$ than in simpler tasks, which implies that the results reported in Figure 5-7 may not be showing the actual $\\alpha$-$\\beta$ condition in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough reviews, insightful comments, and valuable\nquestions regarding our paper.\n\n**A to W1:** Thank you for pointing this out. To ensure boundedness of $\\mathcal{S}$, one can simply add L2 regularization. We provide a sketch of the proof and will change Example 4 in the revised version of the paper.\n\n**Example.** Consider training a two-layer neural network with a logistic loss $f = n^{-1}\\sum_{i=1}^nf_i$, $f_i(W,v)=\\phi(y_i\\cdot v^\\top\\sigma(Wx_i))+\\lambda_1||v||^2+\\lambda_2||W||^2_F$ for a classification problem where $\\phi(t):=\\log(1+\\exp(-t)),$ $W\\in\\mathbb{R}^{k\\times d}, v\\in\\mathbb{R}^{k},$ $\\sigma$ is a ReLU function applied coordinate-wise, $y_i\\in\\\\{-1,+1\\\\}$ is a label and $x_i\\in\\mathbb{R}^d$ is a feature vector. Assume that the interpolation does not hold, i.e. $\\min_{(z,Z)\\in\\mathcal{S}}f_i(z,Z)>f_i^*$. Let $\\mathcal{X}$ be any bounded set that contains $\\mathcal{S}$. Then the $\\alpha$-$\\beta$-condition holds in $\\mathcal{X}$ for some $\\alpha\\ge1$ and $\\beta=\\alpha-1.$\n\n**Proof sketch.** Due to space limit we only mention the main difference in comparison with the proof of Example 4 in the submission.\n\n- First, we have additional $\\lambda_1v$ and $\\lambda_2W$ in the calculations of the gradients $\\nabla_vf_i(v,W)$ and $\\nabla_Wf_i(v,W)$ correspondingly. \n- The optimal value of $f_i^*>0$ because of the L2 regularization.\n- Because of L2 regularization $\\mathcal{S}$ is bounded and from example statement it fully lies in $\\mathcal{X}.$ \n- From non-interpolation assumption we make, there exists $c:=\\min_{i\\in[n]}\\min\\_{(Z,z)\\in\\mathcal{S}}f_i(Z,z)>f_i^*.$\n- In the next derivations, we mainly follow the derivations of example 4. After using convexity of $\\phi$, $\\alpha$-$\\beta$-condition is verified if we have\\begin{align}&2\\phi(y\\_i(v\\circ e_w)^\\top Wx_i)+2\\lambda_1\\left<v,v-z\\right>+2\\lambda_2\\left<W,W-Z\\right>_F-\\phi(y_i(v\\circ e_w)^\\top Zx_i)-\\phi(y_i(z\\circ e_w)^\\top Wx_i)\\\\\\\\&\\quad\\ge\\alpha\\left[\\phi(y_i(v\\circ e_w)^\\top Wx_i)+\\lambda_1||v||^2+\\lambda_2||W||_F^2-\\phi(y_i (z\\circ e_z)^\\top Zx_i)-\\lambda_1||z||^2-\\lambda_2||Z||^2_F\\right]\\\\\\\\&\\quad-\\beta(\\phi(y_i(v\\circ e_w)^\\top Wx_i)+\\lambda_1||v||^2+\\lambda_2||W||^2_F-f_i^*).\\end{align} \n- Rearranging terms and choosing $\\alpha-\\beta=1$ we get\\begin{align}&\\phi(y_i(v\\circ e_w)^\\top Wx_i)+\\lambda_1||v-z||^2+ \\lambda_2||W-Z||^2_F+\\alpha\\phi(y_i(z\\circ e_z)^\\top Zx_i)+(\\alpha-1)\\left[\\lambda_1||z||^2+\\lambda_2||Z||^2_F\\right]\\\\\\\\&\\quad\\ge\\phi(y_i(v\\circ e_w)^\\top Zx_i)+\\phi(y_i(z\\circ e_w)^\\top Wx_i)+(\\alpha-1)f_i^*.\\end{align}\n- Since $(W,v),(z,Z)\\in\\mathcal{X}$, there exist constants $R,r\\ge0$ such that $||z||,||v||\\le r$ and $||Z||_F,||W||_F\\le R$,and RHS in the above is bounded by\\begin{align}2\\max_i\\log(1+\\exp(Rr||x_i||))+(\\alpha-1)f_i^*\\ge\\phi(y_i(v\\circ e_w)^\\top Zx_i)+\\phi(y_i(z\\circ e_w)^\\top Wx_i)+(\\alpha-1)f_i^*.\\end{align}\n- From the assumption we have $\\phi(y_i(z\\circ e_z)^\\top Zx_i)\\ge c$.\n- Then we can take $\\alpha\\ge\\max\\left\\\\{\\frac{2\\max_i\\log(1+\\exp(Rr||x_i||))}{c-f_i^*},1\\right\\\\}$ and $\\beta=\\alpha-1.$\nWe will modify Example 4 in the paper to the one with L2 regularization.\n\n**A to W2:** We refer to the general rebuttal.\n\n**A to W3:** We agree that a theoretical verification of the proposed condition for neural networks is an important question, albeit a difficult one. Most existing theoretical results rely on unpractical amounts of over-parameterization, whereas our aim was to relax this requirement. Notably, Example 4 demonstrates that the $\\alpha$-$\\beta$ condition holds for 2-layer NNs with L2 regularization, albeit under somewhat restrictive assumptions, underscoring the complexity of the problem. Empirically, we have conducted an extensive verification of the $\\alpha$-$\\beta$ condition across a wide range of architectures, indicating that this proposed condition is a promising direction for the analysis of neural networks.\n\n**A to W4:** We agree with the reviewer that for harder tasks $x^K$ might be a worse approximation of $x^*$ than for easier ones. We did mention in the limitations section that the empirical verification of the $\\alpha$-$\\beta$ condition is a difficult task. However, we use the best-known optimizer to get as close as possible to $x^*$ (we choose the optimizer and last iterate $x^K$ such that the performance of networks is close to state-of-the-art). We emphasize that this type of verification has not been conducted in previous studies to the best of our knowledge, making it a significant advancement in the literature. \nFurthermore, we have made a significant effort to provide empirical verification across a wide range of neural network architectures, including those that are widely used in practice, such as ResNet and Transformers.\n\n**A to Q:** Yes, it is possible to derive the convergence of GD under $\\alpha$-$\\beta$-condition. Note that averaging the $\\alpha$-$\\beta$-condition across all $i\\in[n]$ gives $$\\left<\\nabla f(x),x-x_p\\right>\\ge\\alpha(f(x)-f(x_p))-\\beta\\left(f(x)-n^{-1}\\sum_if_i^*\\right).$$\nUsing this inequality and following the standard proof of GD we get\n\\begin{align}\\mathrm{dist}(x^{k+1},\\mathcal{S})^2 &\\le\\mathrm{dist}(x^{k},\\mathcal{S})^2-2\\gamma\\left<\\nabla f(x^k),x^k-x_p^k\\right>+\\gamma^2||\\nabla f(x^k)||^2\\\\\\\\&\\le\\mathrm{dist}(x^{k},\\mathcal{S})^2-2\\alpha \\gamma(f(x^k)-f^*)+2\\beta\\gamma\\left(f(x^k)-n^{-1}\\sum_if_i^*\\right)+2L\\gamma^2(f(x^k)-f^*)\\\\\\\\&\\le\\mathrm{dist}(x^{k},\\mathcal{S})^2-2(\\alpha-\\beta-L\\gamma)\\gamma(f(x^k) - f^*)+2\\beta\\gamma\\left(f^*-n^{-1}\\sum_if_i^*\\right).\\end{align}\n\nChoosing $\\gamma\\le \\frac{\\alpha-\\beta}{2L}$ gives$$\\mathrm{dist}(x^{k+1},\\mathcal{S})^2\\le\\mathrm{dist}(x^{k},\\mathcal{S})^2-(\\alpha-\\beta)\\gamma(f(x^k)-f^*)+2\\beta\\gamma\\left(f^*-n^{-1}\\sum_if_i^*\\right).$$Finally, unrolling this recursion we derive the following rate$$\\min\\limits_{0\\le k<K}[f(x^k)-f^*]\\le\\frac{\\mathrm{dist}(x^0,\\mathcal{S})^2}{\\gamma(\\alpha-\\beta)K}+\\frac{2\\beta}{\\alpha-\\beta}\\sigma^2_{\\mathrm{int}}.$$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DvegNMqnTJ", "reviewer": "Reviewer_qMQA", "summary": "A major challenge in Deep Learning optimization has been identifying structural conditions on the loss objective that ensure convergence of SGD and variants. As in practice despite the non-convexity, stochastic gradient algorithms have been tremendously successful in training neural networks. Many conditions have been proposed that purport to explain this phenomena, including the PL-condition and Aiming. Unfortunately, such conditions may fail to hold unless the network is extremely over-parametrized, which does not align with practice. Moreover, no comprehensive empirical study has been performed verifying these conditions hold on networks of realistic sizes.\n\n In this paper, the authors address these issues by performing an extensive empirical analysis, showing, in general, that many prior conditions fail to hold for realistic networks. They also provide theoretical counter-examples where these conditions fail to hold. This shows convergence analyses of SGD-like algorithms performed under these assumptions may not hold in practice. To rectify this unfortunate situation, the authors introduce a new condition, which they refer to as the $\\alpha-\\beta$ condition. They show under this assumption that SGD and variants like SPS converge to a ball of noise under this condition. Perhaps most importantly, the paper provides extensive empirical evidence and several theoretical examples showing the $\\alpha-\\beta$ condition holds.", "questions": "My main suggestion/request is that the authors address the first point under the Weaknesses sections. If the authors promise to include additional experiments along this line, I'm willing to raise my score. The results themselves can appear in the supplement, but there should be a clear reference to them in the main paper. In my view, this would significantly increase the value of the paper, as it would show that $\\alpha-\\beta$ empirically holds for three of the most popular optimizers in DL: SGD, SGD+Polyak momentum, and Adam. Even if the condition doesn't hold for one of them, say, Adam, it's still valuable as it raises interesting questions for future research.", "limitations": "I think the authors have adequately addressed limitations of the work for the most part. But I think two more items should be added:\n\n1) The assumption of globally Lipschitz continuous gradients. It is known empirically that models like transformers do not satisfy this property, see Zhang et al. (2019). Thus, the analysis here may not hold in such settings. It is known empirically, however, that transformers satisfy a generalized smoothness condition of the form [Zhang et al. (2019)]: \n\n     $\\||H(x)\\|| \\leq L_0+L_1\\||\\nabla f(x)\\||$. \n\nThe authors should state their assumption as a limitation and point to extending the convergence analysis under the $\\alpha-\\beta$ condition to the generalized smoothness setting as an interesting direction for future work. \n\n2) The analysis does not cover methods like Adam, which is arguably the most popular optimization algorithm in deep learning. Moreover, much progress has been made in recent years on analysis of its performance; see, for instance Li et al. (2024). So, this should be stated as a limitation and an interesting direction for future work. \n\nReferences:\n1.) Zhang, Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaie. \"Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity.\" In International Conference on Learning Representations. 2019.\n\n2.) Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. \"Convergence of adam under relaxed assumptions.\" In Advances in Neural Information Processing Systems 36 (2024).", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper has several major strengths that make it a clear accept in my view:\n\n1. Showing the PL-condition and Aiming do not necessarily hold for networks of realistic size encountered in practice. \n\nTo the best of my knowledge, such an extensive empirical investigation has not been done before. This is of prime importance in my view, as much of the recent DL optimization literature takes these conditions for granted despite lacking a strong empirical foundation. I've long harbored doubts about how relevant the analysis in the over-parametrized regime (where said conditions hold with high probability) is to practice. Especially considering analyses over the past couple years showing networks that are well-approximated by their first-order Taylor expansion do not perform as well as networks not in this regime. So, I think the extensive empirics done in this paper showing these conditions don't hold for networks commonly used in practice is a valuable contribution to the literature \n\n2. Introduction of the $\\alpha-\\beta$ condition and convergence analysis. \n\nThe authors have gone beyond just identifying failure modes of previous conditions. They introduce a new condition, the $\\alpha-\\beta$ condition, under which optimizers like SGD (and several variants) converge to a ball-of-noise (or the minimum in the interpolation setting). Moreover, the condition allows for more realistic loss landscapes, i.e., saddle-points can occur. \n\n3. Empirical verification of $\\alpha-\\beta$ condition. \n\nThis is one of the most significant contributions of the paper. The authors provide strong empirical evidence that $\\alpha-\\beta$ holds for networks of practical interest.  \n\n4. The paper is very well-written. I found the paper easily to follow and enjoyable to read.", "weaknesses": "Overall, the paper has no major weaknesses, but it can improve on a few minor points.\n\n1.) For the MLP and ResNet experiments I would have liked to have seen experiments with SGD+momentum and Adam (or AdamW), as these tend to be the most popular optimizers employed in practice. Given that you observed $\\alpha-\\beta$ holds for NAdamW for language tasks, I'd be surprised if you found the condition doesn't hold in the MLP and ResNet settings for optimizers other than SGD. \n\n2.) Continuing off the preceding point, it would be insightful if, besides verifying $\\alpha-\\beta$ for several sets of optimizers, the authors also plotted the corresponding loss curves alongside and reported the estimated $\\alpha, \\beta$ values for each optimizer. This would give insight into how values of $\\alpha, \\beta$ differ across optimizers, and could help explain why an optimizer converges faster than another, as it may exhibit more favorable values of $\\alpha, \\beta$. Though admittedly, this requires some extrapolation as the current theory doesn't apply to a method like Adam, so it is unclear how the values of $\\alpha$ and $\\beta$ would affect its convergence. But it could lead to interesting questions that provide more avenues for future research.  \n\n3.) The authors provide no idealized setting, i.e. wide-networks, where $\\alpha-\\beta$ holds. It would be interesting to see if the level of overparametrization required to ensure $\\alpha-\\beta$ is weaker than what is needed to ensure the Aiming condition. Intuitively I'd expect the answer to be yes, given that it is a weaker condition than Aiming and the strong empirical evidence provided in the paper. Nevertheless, it seems non-trivial to verify and somewhat tangential to the goals of the paper, so its understandable the authors chose to leave this as a direction for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough reviews, insightful comments, and valuable\nquestions regarding our paper.\n\n**A to W1:** The main reason why we used SGD for MLP, CNN, and ResNet experiments is the fact that SGD is known to be able to train those models, i.e. the last iterate of $x^K$ is a good approximation of $x^*$ [1]. In contrast, for larger networks, especially for language modeling tasks, SGD is not able to train a model well, see e.g. [2]. Therefore, we use NAdamW to obtain a better last iterate $x^K$ as an approximation of $x^*.$ \n\n[1] Choi, Dami and Shallue, Christopher J and Nado, Zachary and Lee, Jaehoon and Maddison, Chris J and Dahl, George E, On empirical comparisons of optimizers for deep learning, arXiv preprint arXiv:1910.05446, 2019\n\n[2] Noci, Lorenzo, et al. \"Signal propagation in transformers: Theoretical perspectives and the role of rank collapse.\" Advances in Neural Information Processing Systems 35 (2022): 27198-27211.\n\n\n**A to W2:** Following the experimental setup that the reviewer suggested, we present the experiments on ResNet9 model on CIFAR100 dataset trained with three different optimizers in a separate pdf file. We use SGD (stepsize $0.01$ with OneCycle learning rate scheduler), SGDM (stepsize $0.01$, momentum $0.9$ with OneCycle learning rate scheduler), and Adam (stepsize $0.0001$, default momentum and epsilon parameters with OneCycle learning rate scheduler). For each optimizer, we run experiments with $3$ random seeds to obtain more stable results. We observe that Adam converges slower than SGD and SGDM. This is because the learning rate for Adam is chosen to be slightly smaller so that the convergence behaviour in the end of the training is stable (with learning rates $0.001$ or higher Adam converges faster than SGD and SGDM, but the fluctuations at the end of the training are too high. This most likely happens because, at the end of the training, the Adam stepsize involves a division by a small number as the gradient becomes close to zero. Therefore, we decided to choose a smaller stepsize which still gives the same stochastic loss at the end but with smaller fluctuations). First, we observe that momentum decreases the $\\alpha$, $\\beta$ constants in the proposed condition which suggests that the trajectory of SGD with momentum is better under the $\\alpha$-$\\beta$-condition. Next, we see that Adam optimizer achieves much better $\\alpha$ and $\\beta$ constants than both SGD and SGDM. The provided experimental results open new interesting questions as practically both stepsize adaptivity in Adam and momentum improve convergence under the $\\alpha$-$\\beta$-condition.\n\n**A to W3:** We agree with the reviewer that understanding how over-parametrization affects the $\\alpha$-$\\beta$-condition is an important direction to explore in follow-up works, although as you pointed out, it is a complex and non-trivial question. We will acknowledge this as a limitation of our work that requires further investigation. Thank you for highlighting this point.\n\n**A to Q:** We observe that the condition still holds using all three mentioned algorithms, which we agree is an interesting addition to the paper. We present the discussion in **A to Q2** together with the plots in a separate file.\n\n**A to L1:** We thank the reviewer for these comments. Relaxed smoothness is indeed an interesting approach for future work. We will add a discussion on this to the limitations at the end of the paper.\n\n**A to L2:** We agree with the reviewer that Adam is a widely used optimizer in practice, and including convergence guarantees for Adam would be a nice addition to the paper. However, we emphasize that deriving formal convergence guarantees for Adam requires an involved analysis, which seemed out of scope for the paper where we already derived convergence guarantees for three optimizers. Nonetheless, we concur with the reviewer that this topic should be noted for future research endeavors.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HcHg7fZc0y", "reviewer": "Reviewer_MYcC", "summary": "This paper proposes a new condition to describe the optimization landscape of deep neural networks. This condition alleviates restrictive consequences of alternative conditions such as PL, in particular the overparameterisation and absence of saddle points. A convergence for SGD (and other variants of first-order stochastic methods) is proven for the class of functions that satisfy this condition. The paper showcases examples, both in simple cases and in deep learning, where other conditions do not hold while theirs does. Numerical experiments show that the condition holds in practice.", "questions": "Questions:\n\nSee Weaknesses for main questions.\n\nOther questions:\n- “However, we highlight that the convergence guarantees of the optimizers depend on a term $O(\\beta \\sigma^2)$ which is stable across all experiments we provide.” What does ”stable” mean here?\n- Remark 3 line 687: what is the connection between r and R small, and the fact that X is situated locally around S? If S is far away from 0, then r and R would be large even around S?\n- Line 696: several nabla signs missing. I also believe there is a factor 2 missing from the use of the smoothness condition, see for instance equation 2.1.10 in [1].\n- Several existing function class (Polyak--Łojasiewicz inequality, Quadratic Growth and Error Bound) that are mentioned in the overview of Section 2.1 are actually equivalent, see [2]. This would benefit from being mentioned.\n- Line 84-85: there does exist works showing a PL inequality with only linear overparameterization in width, see [3].\n\nMinor remarks:\n- The acronyms SPS and NGN are not explained in the main text, and are not that well-known. Spelling out the acronyms once would be beneficial.\n- $\\gamma_b$ in Theorem 2 is not defined (in the main text).\n\n[1] Nesterov, Lectures on Convex Optimization, Second Edition, 2018.\n\n[2] Rebjock, Boumal, Fast convergence to non-isolated minima: four equivalent conditions for C2 functions, arXiv:2303.00096\n\n[3] Marion, Wu, Sander, Biau, Implicit regularization of deep residual networks towards neural ODEs, ICLR 2024.", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is very clear and well-written. It tackles the crucial question of understanding which structure in the loss landscape of deep neural networks enables efficient optimization with first-order methods. The arguments in favour of the proposed condition are fairly compelling, with both theoretical results and experimental insights. I verified the proof of one of the main results (Theorem 1), which is correct.", "weaknesses": "The convergence for SGD is shown up to a non-vanishing error term $O(\\beta \\sigma^2)$. While the authors give some explanation on this term, I would have liked more insights: is the error term appearing for SPS and NGN the same (this is not directly obvious from the formulas)? Do authors think this term is an artefact of the proof technique, or intimately connected to the $\\alpha-\\beta$ condition? The authors argue that overparameterization leads to vanishing of this term. As far as I understand, both $\\beta$ and $\\sigma^2$ are affected by overparameterization, and both terms should decay with overparameterization. Is this correct? Does this give an insight of the \"best\" level of overparameterization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**A to W (part 1):** For NGN the first three terms that appear in our Theorem 3 also appear in the convex setting; see Theorem 4.5 in [1]. The fourth (and last) term appears because of the $\\alpha$-$\\beta$-condition. We highlight that the first three terms shrink with a decreasing stepsize, but the last term persists, and it is proportional to $\\beta\\sigma^2_{\\mathrm{int}}$ similarly to SGD. However, if we consider a convex regime, i.e. $\\alpha=1, \\beta=0$ in the $\\alpha$-$\\beta$-condition, then the last term disappears. For SPS, the error term is different. First, it is proportional to $\\alpha\\sigma^2_{\\mathrm{int}}$, i.e. even in the convex regime it remains in the bound  (this result aligns with convergence guarantees in [2]). However, in the interpolation regime, for both NGN and SPS, the error terms disappear. In conclusion, the error terms for NGN and SPS are different in the general case ($\\alpha,\\beta >0$), but both disappear in the interpolation regime.\n\n[1] Orvieto, Antonio and Xiao, Lin, An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes, arXiv preprint arXiv:2407.04358, 2024.\n\n[2] Loizou, Nicolas and Vaswani, Sharan and Laradji, Issam Hadj and Lacoste-Julien, Simon, Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence, AISTATS 2021.\n\n**A to W (part 2):** We refer to the general answer. Regarding the \"best\" level of over-parameterization, could the reviewer please clarify his questions? From Theorem 1, the best rate of SGD is given when a model is over-parametrized, and then the second and third terms in the rate disappear; only the classic optimization term decaying as $\\mathcal{O}(1/K)$ remains in this setting.\n\n**A to Q1:** Thank you for this comment. We can very roughly estimate the value of $\\beta\\sigma^2_{\\mathrm{int}}$ based on experiments. The value of $\\sigma^2_{\\mathrm{int}}$ can be approximated as the value of the stochastic loss at the end of the training (since we use $x^K \\approx x_p$, then $f_i(x^K) \\approx f_i(x_p)$). Therefore, assuming that $f_i^*=0$ we get that $\\sigma^2_{\\mathrm{int}} \\approx f_i(x^K).$ Using such approximations, we compute the value $\\beta\\sigma^2_{\\mathrm{int}}$ and show following the experimental setup of the paper that $\\beta\\sigma^2_{\\mathrm{int}}$ remains stable and decreases as a model becomes closer to over-parameterization. See the table in the separate pdf file for concrete values.\n\n**A to Q2:** We need $\\mathcal{S}$ to be inside $\\mathcal{X}$, so that the projection operation $\\mathrm{proj}_{\\mathcal{S}}$ in the definition of $\\alpha$-$\\beta$-condition is correctly defined for any $(v,W)\\in\\mathcal{X}.$  Note that if $r$ and $R$ are small, then $\\mathcal{S}$ cannot be arbitrarily far away from $0$ as it lies fully inside $\\mathcal{X}$. If $R$ and $r$ are small enough, then the revised value of $\\alpha$ we take is\n$$\\max\\left\\\\{\\frac{2\\max\\_{i\\in[n]} \\log(1+\\exp(Rr\\\\|x_i\\\\|))}{c-f_i^*}, 1\\right\\\\} = 1.$$\nThis implies that $\\beta=\\alpha-1=0.$ We provide Remark 3 to show that in most of the cases, we might need $\\beta > 0,$ which implies that quasi-convexity (i.e., $\\beta=0$) does not hold in this case. However, we highlight that this is only our intuition, and a more careful study is needed in this case.\n\n**A to Q3:** We thank the reviewer for pointing to the typos. We added the missing nabla signs in the proof of the convergence of SGD. Regarding the missing factor 2, there was a typo in the first equality (it should be $\\gamma^2\\mathbb{E}_k[\\\\|\\nabla f\\_{i_k}(x^k)\\\\|^2]$ instead of  $2\\gamma^2\\mathbb{E}_k[\\\\|\\nabla f\\_{i_k}(x^k)\\\\|^2]$). Therefore, the final result does not change.\n\n**A to Q4:** We thank the reviewer for providing a reference [2]. This is indeed an interesting result that PL, EB, and QG are equivalent in the neighborhood of the $\\mathcal{S}$ if $f$ is sufficiently differentiable. We will add this reference to highlight that the discussion on the limitations of PL condition is also transferable to EB and QG. \n\n**A to Q5:** We thank the reviewer for providing a reference [3]. After checking the paper, we would like to highlight that their Definition 1 is stricter than the standard PL condition. They ask for the PL condition to hold in the bounded set around some fixed set of parameters. The radius of the bound is vanishing with the number of data points $n$ as $M = \\mathcal{O}(1/\\sqrt{n})$. We believe this could be one of the reasons to make over-parameterization to be linear in $n$ in their work. However, we will add a citation of [3] to the main body to highlight the possible improvement of necessary over-parameterization with additional restrictions (i.e., in a bounded set around some point).\n\n**A to Q6:** We thank the reviewer for this suggestion. We will spell out the acronyms in the list of contributions where we mention algorithms for the first time. \n\n**A to Q7:** $\\gamma_b$ is a stepsize upper bound of SPS${}\\_{\\max}$ algorithm $\\gamma_k = \\min\\left\\\\{\\frac{f\\_{i_k}(x^k) - f\\_{i_k}^*}{c\\\\|\\nabla f\\_{i_k}(x^k)\\\\|^2}, \\gamma\\_{\\rm b}\\right\\\\}$. We will add the definition in the statement of SPS convergence theorem.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their valuable comments and questions that allowed us to improve our paper. 

**Non-vanishing term in the convergence rate:**
Three of the reviewers raised the question on the convergence of optimizers under the $\alpha$-$\beta$-condition. The main comment is about the presence of the non-vanishing $\mathcal{O}(\beta\sigma^2_{\mathrm{int}})$ term in the rate. Below we provide a detailed discussion of this term which we believe can not be removed since $\alpha-\beta$ functions can have local minima.

1) This term directly appears because of the use of $\alpha$-$\beta$-condition in the analysis, without relying on additional upper bounds or approximations, and it captures the potential presence of local minima as explained below

2) We recall that one can find examples that satisfy the $\alpha$-$\beta$-condition and have local minima. For instance, let $$f_1(x,y)=\frac{1+x^2+y^2}{2+x^2+y^2},f_2(x,y)=\frac{(x-2)^2+(y-2)^2}{1+(x-2)^2+(y-2)^2},f=1/2(f_1+f_2).$$ For this problem, $f_1^*=\frac{1}{2}, w_1^*=(0,0),f_2^*=0,w_2^*=(2,2),f^*\approx 0.45,w^*=(1.97,1.97)$ (we will add the example in the revised version with a proof). We attach a surface plot in the separate pdf) that satisfies the condition with $\alpha\gtrsim1250,\beta=\alpha-1.$ Moreover, in example 4 we provide an example of a 2-layer neural network with ReLU activation that is known to have spurious local minima [4]. In contrast, previously proposed conditions such as PL and quasar-convexity do not allow to have local minima/saddle points. 

3) Note that on the losses that have local minima, SGD does not converge to $f^*$, regardless of the values of stepsize $\gamma$. Indeed, as the rates must hold for any initialization $x^0$, in the worst-case scenario (i.e. $x^0$ is close to spurious minima), annealing the stepsize does not recover convergence to the global minimizer. Near local minima, the gradient dynamics resemble those on a quadratic function (Hartman–Grobman theorem), and one can assume the noise strength is bounded (in norm) near the basin (which holds for ERM problem that we consider). So if we initialize close to a local minimizer and let the stepsize $\gamma$ converge to zero, we get the convergence to the spurious local minima. This suboptimality is modeled by the stepsize-independent quantity $\mathcal{O}(\beta\sigma\_{\mathrm{int}}^2)$ since we provide convergence guarantees for function suboptimality value and not for squared gradient norm as usual in the non-convex setting. Because of the previous considerations, the loss is not necessarily minimized making it necessary to include a worst-case correction term $\mathcal{O}(\beta\sigma\_{\mathrm{int}}^2)$. 


**Additional evidence from prior works:** Other prior works lead us to believe this term indeed correctly appears in the convergence bound:

- We emphasize that the stochastic term $\mathcal{O}(L\gamma\sigma^2_{\mathrm{int}})$ also appears in the standard rate of SGD with constant learning rate; see Theorem 5.5 in [1]. Although it can be annealed with a decreasing learning rate, this only guarantees convergence to a critical point for non-convex functions.
- A non-vanishing term is frequently observed when training neural networks. We for instance refer the reviewer to Figure 8.1 in the seminal reference [2]. This is also observed during the training of language models where the loss is significantly larger than $0$; see plots in Figures 16 and 17 corresponding to language modeling in the appendix. This phenomenon suggests that reaching a critical point that is a global minimizer is not always observed practically. Therefore, the presence of a non-vanishing error term in the rate with the $\alpha$-$\beta$ condition is consistent with empirical observation.
- Finally, prior works that propose other conditions to describe the loss landscape of deep neural networks (e.g. gradient confusion [3]) also obtain a non-vanishing term in the convergence rate (see Theorem 3.2 in [3]). Interestingly, the non-vanishing terms from both analyses capture some sort of discrepancy between datapoints, although they do not seem to be directly relatable.
- The value of $\beta\sigma^2_{\mathrm{int}}$ decreases with over-parametrization which is the expected trend; see rough estimations of $\beta\sigma^2_{\mathrm{int}}$ in the table in the separate pdf.

Nevertheless, we will investigate this aspect further in the next revision and provide an extended discussion regarding this limitation.

[1] Garrigos, Guillaume and Gower, Robert M, Handbook of convergence theorems for (stochastic) gradient methods, arXiv preprint arXiv:2301.11235, 2023.

[2] Ian Goodfellow, Yoshua Bengio, Aaron Courville, Deep Learning, MIT press, 2016.

[3] Sankararaman, Karthik Abinav and De, Soham and Xu, Zheng and Huang, W Ronny and Goldstein, Tom, The impact of neural network overparameterization on gradient confusion and stochastic gradient descent ICML 2020.

[4] Safran, Itay and Shamir, Ohad, Spurious local minima are common in two-layer relu neural networks, ICML 2018.

Meta-review: This paper proposed a new a novel class of functions (alpha-beta condition) and proves convergence of gradient descent. The authors showed that several non-convex landscape with saddle point e.g. matrix completion satisfies the alpha-beta condition. Authors also empirical veryfied the condition on several NN training landscape.  Contrary to some previous classes, in relation to deep neural networks, this new class does not require extreme overparameterization. Relationship between the alpha-beta condition with pl condition and quasi-convex should be included. The framework of the paper is nice, but the applicability of the alpha-beta condition to (modern, current) architectures needs/inspires further study.  Overall this is quite nice paper for optimization studying in the area of machine learning.
Decision: Accept (poster)