Loss Landscape Characterization of Neural Networks without  Over-Parametrization

Authors: rustem  islamov
niccoló  ajroldi
antonio  orvieto
aurelien  lucchi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-01 11:49:18

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.

Main paper: 
 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 to include saddle points or bad local minima [6, 70, 88 ].Yet, empirical evidence has shown that gradient-based optimizers -including SGD, AdaGrad [21] and Adam [39] among many others -can effectively optimize the loss of modern deep-learning-based 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] .Some key factors in this success include the choice of architecture [5, 48, 40, 18] , as well as the over-parametrization [73, 12, 50, 51] . In the well-known infinite-width limit [86, 35, 32] , neural networks are known to exhibit simple landscapes [49] . However, practical networks operate in a 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-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 can represent.In this work, we present a new class of functions that satisfy a newly proposed α-β-condition (see Eq. ( 2)). We theoretically and empirically demonstrate that these functions effectively characterize Table 1 : Summary of existing assumptions on the problem (1) and their limitations. Here S denotes the set of minimizers of f and f * i := argmin x f i (x). Unlike earlier conditions, the α-β-condition is specifically designed to capture local minima and saddle points. NN = Neural Network.QCvx [28] ⟨∇f (x), x -x * ⟩ ≥ θ(f (x) -f (x * )) for some fixed x * ∈ S -excludes saddle points and local minima Aiming [51] ⟨∇f (x), x -Proj(x, S)⟩ ≥ θf (x)-excludes saddle points and local minima -theoretically holds for NN in the presence of impractical over-parameterization [51] -does not always hold in practice [Fig. 1 a-b ] PL (a) [66] ∥∇f (x)∥ 2 ≥ 2µ(f (x) -f * )-excludes saddle points and local minima -theoretically holds for NN in the presence of impractical over-parameterization [50] -does not always hold in practice [Fig. 1 c-d ]α-β-condition [This work] ⟨∇f i (x), x -Proj(x, S)⟩ ≥ α(f i (x) -f i (Proj(x, S))) -β(f i (x) -f * i )-might have saddles [Ex. 2] and local minima [Ex. 3] -in practice does not require over-parameterization [Ex. 5] the loss landscape of neural networks. Furthermore, we derive theoretical convergence guarantees for commonly used gradient-based optimizers under the α-β-condition.In summary, we make the following contributions:1. We introduce the α-β-condition and theoretically demonstrate its applicability to a wide range of complex functions, notably those that include local saddle points and local minima. 2. We empirically validate that the α-β-condition is a 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 α-β-condition, including vanilla SGD (Stochastic Gradient Descent), SPS max (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 α-β-condition does.2 Related work 
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-Łojasiewicz (PL) condition stands out as particularly renowned.Initially demonstrated by Polyak [66] to ensure linear convergence, it has recently experienced a resurgence of interest, in part because it accurately characterizes the loss landscape of heavilly over-parametrized 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 Kurdyka-Łojasiewicz (KL) condition [43, 10] which is satisfied for a much larger class of functions [14, 77] than PL. The KL inequality has been employed to analyze the convergence of the classic proximal-point algorithm [3, 11, 47] and other optimization methods [4, 45] .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 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 to StarCvx, QCvx or the Aiming condition.We present a summary of some of these conditions in Table 1 . There is no general implication between already existing assumptions such as QCvx, Aiming, PL, and the α-β-condition. However, as we will later see, the α-β-condition can more generally characterize the landscape of neural networks without requiring unpractical amounts of over-parametrization. Notably, the α-β-condition is a condition that applies globally to the loss. However, we will demonstrate that convergence guarantees can still be established for commonly-used gradient-based optimizers, although these guarantees are weaker than those derived under the PL condition, which relies on much stronger assumptions.Next, we discuss the limitations of previous conditions to characterize the loss landscape of complex objective functions such as the ones encountered when training deep neural networks.Necessity of Over-parameterization. When considering deep models, the theoretical justification of conditions such as Aiming [51] and PL [50] require a significant amount of over-parameterization. This implies that the neural network must be considerably large, often with the minimum layer's width scaling with the size of the dataset n. However, various studies suggest that this setup may not always accurately model real-world training dynamics [13, 2] . To the best of our knowledge, the weakest requirements on the width of a network are sub-quadratic Ω(n 3/2 ) [20, 74] , where n is the size of a dataset. This implies that, even for a small dataset such as MNIST, a network should have billions of parameters which is not a realistic setting in practice. In contrast, the α-β-condition condition does not require such an over-parametrization condition to hold (e.g., see Example 5) . In Section 5 we provide empirical results showing how our 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 is zero must be deemed a global minimizer. However, such conditions are not consistent with the loss landscapes observed in practical neural networks. For example, finite-size MLPs can have spurious local points or 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 1 where we observe that (i) the angle between the full gradient and direction to the minimizer ∠(∇f (x k ), x k -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 ∥∇f (x k )∥2 ≥ 2µ(f (x k ) -f * ) is not true for any positive µ). These observations suggest that the Aiming and PL conditions do not characterize well a landscape in the absence of invexity property. In contrast, we demonstrate in Example 2 and Figure 9 that our proposed assumption is preferable in this scenario.Lack of Theory. 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 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-examples to these conditions proved in prior work. We train LSTM-based model 2 with standard initialization on Wikitext-2 [57] and Penn Treebank (PTB) [58] datasets. In Figure 1 (a-b ), we show that the angle between the full gradient and direction to the minimizer ∠(∇f (x k ), x k -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-parameterization or the initialization does not lie in the locality region where Aiming holds). Moreover, for the same setting in Figure 1 3to measure the empirical value of PL constant log(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 a more detailed discussion. In contrast, we demonstrate in Figure 7-(g-h ) that the proposed α-β-condition can be verified in this setting.(c-d) we plot 2 log(∥∇f (x k )∥) -2 /δ log(f (x k ) -f (x K ))Constant stepsize parameter. In this section, we present the proof of convergence of SGD with Polyak stepsize (with constant stepsize parameters) under α-β-condition for completeness of the presentation.Lemma 1 (Lemma from [53] ). The SPS max stepsize satisfyEQUATION)Lemma 2 (Lemma from [53] ). Assume each f i is L-smooth, then SPS max stepsize satisfyEQUATIONNow we present the proof of Theorem 2 with constant stepsize parameters.Theorem 2. Assume that Assumptions 1-2 hold. Then the iterates of SPS max (Alg. 2) with a stepsize hyperparameter c >EQUATIONwhere γ min := min{ 1 /2cL, γ b } and c 1 := c γmin(2(α-β)c-1) .Proof. Let x k p ∈ Proj(x k , S) that satisfies Definition 1, then we haveE k dist(x k+1 , S) 2 ≤ E k ∥x k+1 -x k p ∥ 2 = ∥x k -x k p ∥ 2 -2E k γ k ∇f i k (x k ), x k -x k p + E k γ 2 k ∥∇f i k (x k )∥ 2 (i) ≤ dist(x k , S) 2 -2αE k γ k (f i k (x k ) -f i k (x k p )) + 2βE k γ k (f i k (x k ) -f * i k ) + 1 c E k γ k (f i k (x k ) -f * i k ) = dist(x k , S) 2 -2αE k γ k ([f i k (x k ) -f * i k ] -[f i k (x k p ) -f * i k ]) + 2βE k γ k (f i k (x k ) -f * i k ) + 1 c E k γ k (f i k (x k ) -f * i k ) = dist(x k , S) 2 -E k γ k 2α -2β - 1 c (f i k (x k ) -f * i k ) + 2αE k γ k (f i k (x k p ) -f * i k ) ,where (i) follows from Lemma 1 and α-β-condition . Now, since c > 1 2(α-β) , we get that 2α -2β -1 /c > 0. Therefore, using Lemma 2 and the fact thatf * i k ≤ f i k (x k p ) and f * i k ≤ f i k (x k ) we get E k dist(x k+1 , S) 2 ≤ dist(x k , S) 2 -γ min 2α -2β - 1 c E k f i k (x k ) -f * i k + 2αγ b E k (f i k (x k p ) -f * i k ) = dist(x k , S) 2 -γ min 2α -2β - 1 c E k f i k (x k ) -f i k (x k p ) -γ min 2α -2β - 1 c E k f i k (x k p ) -f * i k + 2αγ b E k (f i k (x k p ) -f * i k ) ≤ dist(x k , S) 2 -γ min 2α -2β - 1 c E k f i k (x k ) -f i k (x k p ) + 2αγ b E k (f i k (x k p ) -f * i k ) . Therefore, noticing that E k f i k (x k p ) = f * since x k p is independent of i k , we have γ min 2α -2β - 1 c E k f (x k ) -f * ≤ dist(x k , S) 2 -E k dist(x k+1 , S) 2 + 2αγ b σ 2 int .Dividing both sides by γ min (2α -2β -1 /c) and taking full expectation, we getE f (x k ) -f * ≤ c γ min (2(α -β)c -1) E dist(x k , S) 2 -E dist(x k+1 , S) 2 + 2αcγ b γ min (2(α -β)c -1) σ 2 int .Averaging for k ∈ {0, . . . , K -1} we getmin 0≤k<K E f (x k ) -f * ≤ c γ min (2(α -β)c -1)K E dist(x 0 , S) 2 + 2αcγ b γ min (2(α -β)c -1) σ 2 int ,that finalizes the proof.Decreasing stepsize parameter. Now we switch to the analysis of SPS max with decreasing stepsize parameters. We consider the stepsize DecSPS introduced in [64 ]γ k = 1 c k min f i k (x k ) -f * i k ∥∇f i k (x k )∥ 2 , c k-1 γ k-1 with c -1 = c 0 and γ -1 = γ b > 0 to get γ 0 = 1 c 0 min f i0 (x 0 ) -f * i0 ∥∇f i0 (x 0 )∥ 2 , c 0 γ b .Lemma 3 (Lemma 1 from [64] ). Let Assumption 1 holds. Let {c k } k≥0 be any non-decreasing positive sequence of real numbers. Then we haveEQUATION)Theorem 5. Assume that Assumptions 1-2 hold. Let {c k } k≥0 be any positive non-decreasing sequence such that c k ≥ 1 α-β . Let Then iterates of DecSPS satisfyEQUATION)whereD 2 := max 0≤k≤K dist(x k , S) 2 , L := max L, 1 2c0γ b .Proof. From the definition of the stepsize we haveγ k ≤ 1 c k f i k (x k ) -f * i k ∥∇f i k (x k )∥ 2 .Therefore, we haveγ 2 k ∥∇f i k (x k )∥ 2 ≤ γ k c k (f i k (x k ) -f * i k ).Let x k p = Proj(x k , S) which satisfies Definition 1. Now we havedist(x k+1 , S) 2 ≤ ∥x k+1 -x k p ∥ 2 ≤ dist(x k , S) 2 -2γ k ∇f i k (x k ), x k -x k p + γ k c k (f i k (x k ) -f * i k ).Using α-β-condition we getdist(x k+1 , S) 2 ≤ ∥x k+1 -x k p ∥ 2 ≤ dist(x k , S) 2 -2αγ k (f i k (x k ) -f i k (x k p )) + 2βγ k (f i k (x k ) -f * i k ) + γ k c k (f i k (x k ) -f * i k ) = dist(x k , S) 2 -γ k (2α -2β -1 /c k ) (f i k (x k ) -f i k (x k p )) + γ k (2β + 1 /c k )(f i k (x k p ) -f * i k ).Let us divide both sides byγ k > 0 dist(x k+1 , S) 2 γ k ≤ dist(x k , S) 2 γ k -(2α -2β -1 /c k ) (f i k (x k ) -f i k (x k p )) + (2β + 1 /c k )(f i k (x k p ) -f * i k ).Since by hypothesis c k ≥ 1 α-β , we get 2α -2β -1 /c k ≥ α -β. Therefore, we getf i k (x k ) -f i k (x k p ) ≤ dist(x k , S) 2 (α -β)γ k - dist(x k+1 , S) 2 (α -β)γ k + (2β + 1 /c k ) α -β (f i k (x k p ) -f * i k ).Summing from k = 0 to K -1 we getK-1 k=0 f i k (x k ) -f i k (x k p ) ≤ K-1 k=0 dist(x k , S) 2 (α -β)γ k - K-1 k=0 dist(x k+1 , S) 2 (α -β)γ k + K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ) ≤ dist(x 0 , S) 2 (α -β)γ 0 + K-1 k=1 dist(x k , S) 2 (α -β)γ k - K-2 k=0 dist(x k+1 , S) 2 (α -β)γ k - dist(x K , S) 2 (α -β)γ K-2 + K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ).Here we use the fact that γ k is a non-increasing sequence with k. We continue as followsK-1 k=0 f i k (x k ) -f i k (x k p ) ≤ dist(x 0 , S) 2 (α -β)γ 0 + K-2 k=0 1 γ k+1 - 1 γ k dist(x k+1 , S) 2 α -β + K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ) ≤ D 2 α -β 1 γ 0 + K-2 k=0 1 γ k+1 - 1 γ k + K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ) ≤ D 2 (α -β)γ K-1 + K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ).Here we use the fact that 1 /γ k+1 -1 /γ k ≥ 0. From Lemma 3 we have1 γ k ≤ c k max 2L, 1 c 0 γ b := L .Therefore, we continue as follows1 K K-1 k=0 f i k (x k ) -f i k (x k p ) ≤ 2 LD 2 c K-1 K(α -β) + 1 K K-1 k=0 2β α -β (f i k (x k p ) -f * i k ) + 1 K K-1 k=0 1 (α -β)c k (f i k (x k p ) -f * i k ).Taking expectation we getEQUATION)Proof. The proof directly follows from Theorem 4 using the choice c k = √ k + 1 and the fact thatK-1 k=0 k -1/2 ≤ 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.Algorithm 3 NGN: Non-negative Gauss Newton 1: Input: Stepsize parameter γ 2: for k = 0, 1, 2, . . . , K -1 do3: Sample i k ∼ Unif[n] and compute ∇f i k (x k ) 4:Compute NGN stepsizeγ k := γ 1 + γ 2fi k (x k ) ∥∇f i k (x k )∥ 2 5:Update modelx k+1 = x k -γ k ∇f i k (x k ) 6: end for C.2. 
the proposed α-β-condition: 
 Setting. We consider the following Empirical Risk Minimization (ERM) problem that typically appears when training machine learning models:EQUATIONHere x ∈ R d denotes the parameters of a model we aim to train, d is the number of parameters, and n is the number of samples in the training dataset. Each f i (x) 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 * i := min x f i (x), 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 f i and the set of minimizers of the global loss function f . Definition 1 (α-β-condition ). Let X ⊆ R d be a set and consider a function f : X → R as defined in (1) . Then f satisfies the α-β-condition with positive parameters α and β such that α > β if for any x ∈ X there exists x p ∈ Proj(x, S) such that for all i,EQUATIONThe α-β-condition recovers several existing assumptions as special cases. For example, the proposed assumption reduces to QCvx around x * if α > 0, β = 0, and S is a singleton {x * }. Importantly, the α-β-condition is also applicable when the set S contains multiple elements.One can easily check that the pair of parameters (α, β) in (2) can not be unique. Indeed, if the assumption is satisfied for some α and β, then due to inequality f i (x p ) ≥ f * i it will be also satisfied for (α + δ, β + δ) for any δ ≥ 0.To demonstrate the significance of Definition 1 as a meaningful condition for describing structural non-convex functions, we provide several examples below that satisfy (2) . We do not aim to provide the tightest possible choice of α and β such that Definition 1 holds. Instead, this section aims to offer a variety of examples that demonstrate specific desired characteristics when α-β-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 1.EQUATIONthen Definition 1 holds with α ∈ [ 5 /2, +∞) and β ∈ [ 4α /5, α).Next, we provide an example where f satisfies Definition 1 even in the presence of saddle points.EQUATIONthen Definition 1 holds for some α and β = α -8. Remark 1. Examples 1 and 2 can be generalized for any number of functions n and dimension d as followsEQUATIONfor some properly chosen {a i } andEQUATIONthen Definition 1 holds for some α and β = α -1.The three examples above demonstrate that functions satisfying Definition 1 can potentially be nonconvex with an unbounded set of minimizers S (Example 1) and can have saddle points (Example 2) and local minima (Example 3). In contrast, the PL and Aiming conditions are not met in cases where a problem exhibits saddle points. For illustration purposes, we plot the loss landscapes of f in Figure 3 .So far, we have presented simple examples to verify Definition 1. Next, we 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 can be shown to be PL after a sufficiently large number of iterations of alternating gradient descent and under a specific random initialization [81] .Example 4. Let f i , f ij be such that f (W, S) = 1 2nm ∥X -W ⊤ S∥ 2 F = 1 2nm i,j (X ij -w ⊤ i s j ) 2 , f ij (W, S) = 1 2 (X ij -w ⊤ i s j ) 2 , (7) where X ∈ R n×m , W = (w i ) n i=1 ∈ R k×n , S = (s j ) m j=1 ∈ R k×m ,and rank(X) = r ≥ k. We assume that X is generated using matrices W * and S * with non-zero additive noise that minimize empirical loss, namely, X = (W * ) ⊤ S * +(ε ij ) i∈[n],j∈ [m] where W * , S * = argmin W,S f (W, S). Let X be any bounded set that contains S. Then Definition 1 is satisfied with α = β + 1 and some β > 0. EQUATION)for a classification problem where ϕ(t):= log(1 + exp(-t)), W ∈ R k×d , v ∈ R k , σ is a ReLU function applied coordinate-wise, y i ∈ {-1,+1} is a label and x i ∈ R d is a feature vector. Let X be any bounded set that contains S. Then the α-β-condition holds in X for some α ≥ 1 andβ = α -1. 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 f i does not have minimizers inS, i.e. ∄(W * , v * ) ∈ S such that f i (W * , v * ) = f * i for some i ∈ [n].We highlight that Example 5 is applicable for a bounded set X of an arbitrary size. Moreover, in practice, we typically add ℓ 1 or ℓ 2 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 S requiring initialization to be close enough to the solution set [51, 50] . The proofs for all examples are given in Appendix C.1.Constant stepsize parameter. In this section we present the proof of convergence of NGN with constant stepsize parameter γ under α-β-condition for completeness of the presentation. Lemma 4 (Lemma from [63] ). Let f i be L-smooth for all i, then the stepsize of NGN satisfiesEQUATIONLemma 5 (Lemma from [63] ). Let f i be L-smooth for all i, then the iterates of NGN satisfyEQUATIONTheorem 3. Assume that Assumptions 1 with α ≥ β + 1 and 1-2 hold. Assume that each function f i is positive and σ 2 pos < ∞. Then the iterates of NGN (Alg. 3) with a stepsize parameter γ > 0 satisfyEQUATIONwhere c 2 := 2γL(α -β -1) + α -β.Proof. Let x k p ∈ Proj(x k , S) satisfying Definition 1. Then we haveEQUATION)From Lemma 5EQUATIONPlugging (35) in (34) we getE k dist(x k+1 , S) 2 ≤ dist(x k , S) 2 -2αE k γ k (f i k (x k ) -f i k (x k p )) + 2βE k γ k (f i k (x k ) -f * i k ) 4γL 1 + 2γL + E k γ k (f i k (x k ) -f * i k ) + 2γ 2 L 1 + γL max 2γL -1 2γL + 1 , 0 E k f * i k .We havef i k (x k ) -f i k (x k p ) = (f i k (x k ) -f * i k ) -(f i k (x k p ) -f * i k ). Now we write γ k = ρ + ϵ k where ρ is a constant independent of i k . Therefore, we haveEQUATIONWe need to find ρ such thatαϵ k -β + 2γL 1 + 2γL γ k ≥ 0 α(γ k -ρ) -β + 2γL 1 + 2γL γ k ≥ 0 γ k α -β - 2γL 1 + 2γL ≥ αρ.Note that since γ k ≥ γ 1+γL from Lemma 4, then it is enough if ρ satisfiesγ 1 + γL α -β - 2γL 1 + 2γL ≥ αρ γ(2γL(α -β -1) + α -β) α(1 + γL)(1 + 2γL) ≥ ρ.Let us take this bound as a value of ρ. Note that since α ≥ β + 1, then ρ ≥ 0. Therefore, the bound for ϵ k is the followingϵ k = γ k -ρ ≤ γ - γ(2γL(α -β -1) + α -β) α(1 + γL)(1 + 2γL) = γ α(1 + γL)(1 + 2γL) -2γL(α -β -1) -(α -β) α(1 + γL)(1 + 2γL) = Lγ 2 α + 2αγL + 2(β + 1) α(1 + γL)(1 + 2γL) + γ β α(1 + γL)(1 + 2γL) ≤ 3Lγ 2 1 + 2γL := 1 2 T2(γ 2 ) + βγ α(1 + γL)(1 + 2γL) := 1 2 βT1(γ).Therefore, we get the following descent inequalityEQUATIONHere we use the fact that x k p is a minimizer of f and independent of i k . Unrolling the recursion, we getEQUATIONwhereEQUATIONTherefore, we getEQUATIONThis finished the proof.Remark 5. If all f i are convex, i.e. we can take α = 1, β = 0 in α-β-condition, then we getmin 0≤k≤K-1 E f (x k ) -f * ≤ E dist(x 0 , S) 2 2γK (1 + 2γL) 2 + 3Lγ(1 + γL)σ 2 int+ γL max {2γL -1, 0} σ 2 pos , that coincides with the results in [63] .Decreasing stepsize parameter. Now we present the results with decreasing stepsize parameter. Theorem 6. Assume that Assumptions 1 with α ≥ β + 1 and 1-2 hold. Assume that each function f i is positive and σ 2 pos < ∞. Then the iterates of NGN with decreasing stepsize of the formEQUATIONwhere C 1 , C 2 , C 3 , and C 4 are defined in (43) .Proof. Similarly to the proof with constant stepsize parameter we can obtain (similar to ( 37))E k dist(x k+1 , S) 2 ≤ dist(x k , S) 2 -T 0 ( γ k )(f (x k ) -f * ) + T 2 ( γ 2 k )ασ 2 int + βT 1 ( γ k )ασ 2 int + T 3 ( γ 2 k )σ 2 pos .Note that we haveT 0 ( γ k ) = 2 γ k (2 γ k L(α -β -1) + α -β) (1 + γ k L)(1 + 2 γ k L) ≥ 2 γ k (α -β) (1 + γ 0 L)(1 + 2 γ 0 L) = : T 0 ( γ k ), T 1 ( γ k ) = 2 γ k α(1 + γ k L)(1 + 2 γ k L) ≤ 2 γ k α = : T 1 ( γ k ), T 2 ( γ 2 k ) = 6L γ 2 k 1 + 2 γ k L ≤ 6L γ 2 k = : T 2 ( γ 2 k ), T 3 ( γ 2 k ) = 2 γ 2 k L 1 + γ k L max 2 γ k L -1 2 γ k L + 1 , 0 ≤ 2 γ 2 k L max{2γL -1, 0} = : T 3 ( γ 2 k ).Therefore, we can continue as followsE dist(x k+1 , S) 2 ≤ E dist(x k , S) 2 -T 0 ( γ k )E f (x k ) -f * + T 2 ( γ 2 k )ασ 2 int + β T 1 ( γ k )ασ 2 int + T 3 ( γ 2 k )σ 2 pos .This leads toK-1 k=0 T 0 ( γ k )E f (x k ) -f * ≤ E dist(x 0 , S) 2 + K-1 k=0 T 2 ( γ 2 k )ασ 2 int + K-1 k=0 β T 1 ( γ k )ασ 2 int + K-1 k=0 T 3 ( γ 2 k )σ 2 pos .Therefore, we havemin 0≤k<K E f (x k ) -f * ≤ 1 K-1 k=0 T 0 ( γ k ) E dist(x 0 , S) 2 + K-1 k=0 T 2 ( γ 2 k ) K-1 k=0 T 0 ( γ k ) ασ 2 int + β K-1 k=0 T 1 ( γ k ) K-1 k=0 T 0 ( γ k ) ασ 2 int + K-1 k=0 T 3 ( γ 2 k ) K-1 k=0 T 0 ( γ k ) σ 2 pos .Following the results of [64] and [24] we getK-1 k=0 T 0 ( γ k ) = K-1 k=0 2 γ k (1 + γL)(1 + 2γL) ≥ 8γ √ K 5(1 + γL)(1 + 2γL) , K-1 k=0 T 2 ( γ 2 k ) = K-1 k=0 6L γ 2 k ≤ 12Lγ 2 log(K + 1), K-1 k=0 T 3 ( γ 2 k ) = K-1 k=0 2 γ 2 k L max{2γL -1, 0} ≤ 4γ 2 L max{2γL -1, 0} log(K + 1), K-1 k=0 T 1 ( γ k ) K-1 k=0 T 0 ( γ k ) = K-1 k=0 2 γ k α K-1 k=0 2 γ k (α-β) (1+γL)(1+2γL) = (1 + γL)(1 + 2γL) α(α -β) .Thus, the final result can be written as followsmin 0≤k<K E f (x k ) -f * ≤ 5(1 + γL)(1 + 2γL) 8γ √ K E dist(x 0 , S) 2 + 12Lγ 2 log(K + 1) 8γ √ K 5(1+γL)(1+2γL) ασ 2 int + K-1 k=0 T 1 ( γ k ) K-1 k=0 T 0 ( γ k ) ασ 2 int + K-1 k=0 T 3 ( γ 2 k ) K-1 k=0 T 0 ( γ k ) σ 2 pos = 5(1 + γL)(1 + 2γL) 8γ √ K E dist(x 0 , S) 2 + 15Lγ(1 + γL)(1 + 2γL) log(K + 1) 2 √ K ασ 2 int + (1 + γL)(1 + 2γL) (α -β) βσ 2 int + 5(1 + γL)(1 + 2γL)γL max{2γL -1, 0} log(K + 1) 2 √ K σ 2 pos .Now it is left to use the definitions of constants C 1 , C 2 , and C 3 Compute AdaGrad-norm-max stepsizeEQUATIONEQUATIONc 2 k := max c 2 k-1 , ∥∇f i k (x k )∥ 2 b 2 k := b 2 k-1 + c 2 k , γ k = γ b k 5:Update modelx k+1 = x k -γ k ∇f i k (x k )6: end for iterates of AdaGrad-norm-max (Alg. 4) satisfyEQUATIONWe 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 x k p = Proj(x k , S) satysfying Definition 1. Then we haveEQUATIONNote that we choose b -1 ≥ 2Lγ α-β . Since b k is inreasing sequence, then we have for any k that b k ≥ 2Lγ α-β . Therefore,Lγ k = L γ b k ≤ L γ b -1 ≤ L γ 2Lγ /α-β = α -β 2 .This means that-2γ k (α -β -Lγ k ) ≤ -2γ k (α -β -α-β /2) = -γ k (α -β).Thus, we can continue (45) as followsdist(x k+1 , S) 2 ≤ dist(x k , S) 2 - γ b k (α -β)(f i k (x k ) -f * i k ) + 2α γ b k (f i k (x k p ) -f * i k ).We know that b k is increasing sequence that satisfyb 2 -1 + D 2 (k + 1) ≤ b k ≤ b K-1 ≤ b 2 -1 + G 2 K.This leads together with the fact that bothf i k (x k ) -f * i k and f i k (x k p ) -f * i k are non-negative to dist(x k+1 , S) 2 ≤ dist(x k , S) 2 - γ b 2 -1 + G 2 K (α -β)(f i k (x k ) -f * i k ) + 2α γ b 2 -1 + D 2 (k + 1) (f i k (x k p ) -f * i k ) = dist(x k , S) 2 - γ(α -β) b 2 -1 + G 2 K (f i k (x k ) -f i k (x k p )) + 2αγ b 2 -1 + D 2 (k + 1) (f i k (x k p ) -f * i k ).Taking the conditional expectation we getE k f (x k ) -f * b 2 -1 + G 2 K ≤ dist(x k , S) 2 γ(α -β) - E k dist(x k+1 , S) 2 γ(α -β) + 2α b 2 -1 + D 2 (k + 1)(α -β) σ 2 int ,which leads to the following boundE k f (x k ) -f * ≤ dist(x k , S) 2 γ(α -β) - E k dist(x k+1 , S) 2 γ(α -β) b 2 -1 + G 2 K + 2α b 2 -1 + D 2 (k + 1)(α -β) σ 2 int b 2 -1 + G 2 K.Averaging over K iterations we getmin 0≤k<K E f (x k ) -f * ≤ 1 K K-1 k=0 E f (x k ) -f * ≤ dist(x k , S) 2 γK(α -β) b 2 -1 + G 2 K + 2α (α -β)K σ 2 int b 2 -1 + G 2 K K-1 k=0 1 b 2 -1 + D 2 (k + 1) ≤ dist(x k , S) 2 γK(α -β) b 2 -1 + G 2 K + 2α (α -β)KD 2 σ 2 int b 2 -1 + G 2 K b 2 -1 + D 2 (K + 1) = O 1 √ K + ασ 2 int .For all the experiments, we make use of PyTorch [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 4xA100-SXM4 GPUs, with a 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. Here T (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) -f i k (x K )) -βf i k (x k ) assuming that f * i = 0.(x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) - f i k (x K )) -βf i k (x k ) assuming that f * i = 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 α ≥ β + 0.1.We observe that the magnitude of the smallest possible values of α and β increase till up to the second layer size 512, but then it starts decreasing as the model becomes more over-parameterized. This leads to smaller values of neighborhood O(βσ 2 int ) as we expect in this setting.We use CNN model with 2 convolution layers followed by a fully connected one. After each convolution layer, we use max-pooling and ReLU activation functions. We train the model with a cosine annealing learning rate scheduler with a maximum value 0.01 and batch size 64. We train the model on CIFAR10 dataset [41] for 1500 epochs. We run the experiments for 4 different random seeds. In Figure 13 we plot possible values of α and β satisfying α ≥ β + 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-parameterization: values of stochastic losses decrease. We observe the same phenomenon as in Appendix D.3: minimum possible values of α and β increase up to 128 number of convolutions, but then it decreases for a larger number of convolutions. This happens because the model becomes more over-parameterized. Moreover, the possible difference between α and β tends to increase with number of convolutions starting from 128 convolutions. (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) - f i k (x K )) -βf i k (x k ) assuming that f * i = 0.We use the implementation from Kumar [42] . We train the model on CIFAR100 dataset [41] for 1000 epochs. We use one-cycle scheduler with a maximum learning rate 0.01. To compute dense stochastic gradients, we switch off dropout during evaluations of stochastic gradients and losses for α-β-condition. We run the experiments for 4 different random seeds and plot the mean along with maximum and minimum fluctuations.In Figure 15 we observe that the minimum value of stochastic loss increases with batch size which means that the model becomes further from over-parameterization.Now we turn to another interesting question: how does the choice of an optimizer affect the practical verification of the α-β-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 α and β for SGD (from Figure 6 ), SGDM, and Adam, we observe that the loss landscape explored by the Adam optimizer achieves smaller values of α and β. Moreover, the values of α and β found by SGDM are typically smaller than those found by SGD. This result may shed light on why momentum (from a 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 a loss landscape from the α-β-condition point of view. 17 suggest that the values of α and β tend to decrease with the depth of a model. These observations align with those from Section 5.1 and Section 5.2 as the constants α and β decrease as the depth of the model increases.For each of 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 we provide the parameters of optimizers we use for each task. The loss curves are presented in Figure 18 . For each workload, we run 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 7 .We employ a cosine annealing learning rate schedule that reduces the learning to 1e -10, with an 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. (x k ) = ⟨∇f i k (x k ), x k -x K ⟩-α(f i k (x k )-f i k (x K ))-βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for a given pair of (α, β). We plot values of α,β in α-β-condition for SGDM (first row) and Adam (second row). (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) -f i k (x K )) -βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for a given pair of (α, β).For each of all aforementioned tasks, we repeat the training with 3 random seeds to create more stable results. We train Pythia 70M and Pythia 160M [8] on publicly available Slim-Pajama-627B dataset [72] . Both models are trained on sequences of length 2048, and makes use of a batch size of 0.5M tokens, which amounts to a batch size of 256 samples. We use AdamW optimizer and a cosine annealing with linear warmup, with hyperparameters specified in Table 3 . The stochastic loss and training perplexity are reported in Figure 19 .• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.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 a new class of functions we propose in the paper as well as other assumptions on the smoothness and noise of ERM problem. We explicitly state all convergence guarantees 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 be properly referenced. 
theoretical convergence of algorithms: 
 We conduct our analysis under the following smoothness assumption that is standard in the optimization literature. Assumption 1. We assume that each f i is L-smooth, i.e. for all x, y ∈ R d it holds ∥∇f i (x) -∇f i (y)∥ ≤ L∥x -y∥.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σ 2 int := E i [f * -f * i ] is finite, where the expectation is taken concerning the randomness of indices i for a certain algorithm.Now we demonstrate that the α-β-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 -γ k ∇f i k (x k )). 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 of 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 γ ≤ α-β 2L satisfyEQUATIONTable 2 : Summary of how the non-vanishing term βσ 2 int (as appearing e.g. in Eq. ( 9)) increases (↗) or decreases (↘) as a function of specific quantities of interest.Model's width ↗ Model's depth ↗ Batch-size ↗ Change in βσ 2 int ↘ ↘ ↘Theorem 1 shows that under the α-β-condition , SGD converges with a rate O(K -1/2 ) (the same rate obtained by SGD for convex functions [24] ) up to a ball of size O(βσ 2 int ). We argue that the non-vanishing term O(βσ 2 int ) must appear in the convergence rate for non-convex optimization for several reasons: (i) This term arises directly from the use of the α-β condition in the analysis, without resorting to additional upper bounds or approximations. It reflects the potential existence of local minima that the α-β condition is designed to model. In the worst-case scenario, if SGD is initialized near local minima and uses a sufficiently small step size, it may fail to converge to the exact minimizer and can become trapped in suboptimal minima. This sub-optimality is modeled in the upper bound by the stepsize-independent quantity O(βσ 2 int ) 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-parameterized (which is consistent with prior works such as [50] that require large amounts of over-parametrization); 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 over-parameterized such that the interpolation condition f * i = f * holds, then the non-vanishing term is not present in the bound. (iii) The presence of a non-vanishing error term in the rate with the α-β 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 a 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-vanishing term in the convergence rate (see Theorem 3.2 in [71] ).Convergence of SPS max . Next, we consider the SPS max algorithm. SPS max stepsize is given by γ k := min fi k (x k )-f * i k c∥∇fi k (x k )∥ 2 ,EQUATIONwhere γ min := min{ 1 /2cL, γ b } and c 1 := c γmin(2(α-β)c-1) .In the convex case, i.e. α-β-condition holds with α = 1, β = 0, we recover the rate of Loizou et al. [53] .Convergence of NGN. Finally, we turn to the analysis of NGN. This algorithm is proposed for minimizing positive functions f i which is typically the case for many practical choices. Its stepsizeγ k := γ 1+ γ 2f i k (x k ) ∥∇fi k (x k )∥ 2where γ is the stepsize hyperparameter. NGN stepsize differs from that of SPS max by replacing min operator by softer harmonic averaging of SPS stepsize and a constant γ. In addition to the already mentioned assumptions, we make a mild assumption that the positivity error σ 2 pos := E [f * i ] is finite. Theorem 3. Assume that Assumptions 1 with α ≥ β + 1 and 1-2 hold. Assume that each function f i is positive and σ 2 pos < ∞. Then the iterates of NGN (Alg. 3) with a stepsize parameter γ > 0 satisfyEQUATION)where c 2 := 2γL(α -β -1) + α -β. (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) -f i k (x K )) -βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for given pair of (α, β).One of the main properties of NGN is its robustness to the choice of stepsize γ. Theorem 3 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 α-β-condition.Comparing the results of Theorems 2 and 3 we highlight several important differences. (i) There is no restriction on the stepsize parameter γ for NGN. Conversely, SPS max requires c to be lower bounded. (ii) Both algorithms converge to a neighborhood of the solution with a fixed stepsize hyperparameter. However, the neighborhood size of SPS max is not controllable by the stepsize hyperparameter and remains constant even in the convex setting when β = 0. In contrast, NGN converges to a ball whose size can be made smaller by choosing a small stepsize parameter, and the "non-vanishing" term disappears in the convex setting β = 0.We note that our goal was not to achieve the tightest convergence guarantees for each algorithm, but rather to underscore the versatility of the α-β-condition in deriving convergence guarantees for SGD-type algorithms, both for constant or adaptive stepsizes. In addition to the results of this section, we demonstrate the convergence guarantees for SGD, SPS max , and NGN with decreasing with k stepsizes in Appendix C.2. Besides, in Appendix C.2.4 we present a convergence of a slightly modified version of Adagrad-norm method [82] under α-β-condition.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: For most of the experiments we use existing open source Github repositories making small changes in the code to 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.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe 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 to have some path to reproducing or verifying the results. 
experimental validation of the α-β-condition: 
 In this section, we provide extensive numerical results supporting that the α-β-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(x k , S) as the last iterate x K in a 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 non-deterministic CUDA operations while training on a GPU. For each task, we demonstrate possible values of pairs of (α, β) that work across all runs (might differ from one experiment to another) with different random seeds and satisfy α ≥ β + 0.1.First, we test MLP neural networks with 3 fully connected layers on Fashion-MNIST [83] dataset. We fix the second layer of the network to be a square matrix and vary its dimension layer to investigate the effect of over-parameterization on α-β-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 (α, β) that work across all 4 runs. We observe that minimum possible values of α and β increase from small size to medium, and then tend to decrease again as the model becomes more over-parameterized. We defer more experimental results for MLP to Appendix D.3 to showcase this phenomenon. This observation leads to the fact that the neighborhood of convergence O(βσ 2 int ) of SGD eventually becomes smaller with the size of the model as we expect (since it becomes more over-parameterized).In our next experiment, we test convolutional neural networks with 2 convolution layers and 1 fully connected layer on CIFAR10 dataset [41] . We vary the number of convolutions in the second convolution layer to investigate the effect of over-parameterization on α-β-condition. We test it (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) -f i k (x K )) - βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for a given pair of (α, β). HereT (x k ) = ⟨∇f i k (x k ), x k -x K ⟩ -α(f i k (x k ) -f i k (x K )) -βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for a given pair of (α, β).for {32, 128, 512, 2048} number of convolutions in the second layer, and for each case, we run experiments for 4 different random seeds. In Figure 5 , we observe that the smallest possible values of (α, β) increase till 64 convolutions, and then decrease back. Second, the difference α -β for possible choice of α and β decreases from Figure 5 -a to Figure 5 -b, but then it increases again.Next, we 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 (α, β) that works across all runs. We observe that α-β-condition holds in all cases. Besides, there is a tendency for the minimum possible choice of α and β to decrease with batch size. Moreover, for larger batches, the difference between α and β also increases. From Theorem 1, this result suggests that we can use bigger stepsizes with larger batches.We are now interested in assessing the validity of α-β-condition on modern Deep Learning architectures. Thereby, we consider tasks from the AlgoPerf benchmarking suite [16] . We consider four workloads from the competition: (i) DLRMsmall model [59] on Criteo 1TB dataset [44] ; (ii) U-Net model [69] on FastMRI dataset [85] (iii) GNN model [7] on OGBG dataset [31] ; (iv) Transformer-big [78] on WMT dataset [9] . To train the models, we use NAdamW optimizer [19] 4 , which achieves state-of-the-art performances on the current version of the benchmark. The hyperparameters of the optimizer are chosen to reach the validation target threshold set by the original competition. Moreover, we consider the pretraining of a 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, we use the SlimPajama [72] dataset. Following the original Pythia recipes, we fix a sequence length of 2048 and train the language model to predict the next token in a self-supervised fashion. We refer to section Appendices D and D.8 for additional details.The results are presented in Figure 7 . We observe that α-β-condition holds for a wide range of values of α and β 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 in previous sections. (x k ) = ⟨∇f i k (x k ), x k -x K ⟩-α(f i k (x k )-f i k (x K ))- βf i k (x k ) assuming that f * i = 0.Minimum is taken across all runs and iterations for a given pair of (α, β).This difference is 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 of the optimizers depend on a term O(βσ 2 int ) which is stable across all experiments we provide.We defer the verification of α-β-condition by Adam and SGDM to Appendix D.6. The results in Figure 16 6 Conclusion, potential extensions, and limitations.In this work, we introduce a new class of functions that more accurately characterize loss landscapes of neural networks. In particular, we 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 α-β-condition holds along the optimization trajectories of various large deep learning models.It is 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 α-β-condition on neural networks.We are only able to 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, we do not provide the most precise theoretical values of α and β that satisfy Definition 1. Therefore, in future work, we aim to obtain stronger theoretical guarantees demonstrating that the α-β-condition holds for neural networks with more precise values of α and β. We also intend to explore how the α-β-condition varies when changing the architecture or the number of parameters (i.e., theoretical exploration of over-parameterization). (12) . We observe that possible values of µ are of order 10 -9 -10 -7 which implies slow theoretical convergence and contradicts practical observations.Let us consider the relaxation of PL condition for some δ ∈ [1, 2] and µ > 0 (Assumption 3 in [22] )EQUATIONTaking logarithms of both sides we continueEQUATIONTo satisfy PL condition for some δ, we need to find µ that satisfies (13) for all iterations. In Figure 8 we plot LHS of (13) . We observe that the values of µ that satisfy (13) for all iterations should be of order 10 -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).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] .EQUATION)then Definition 1 holds with α ≥ We highlight that we only show that α-β-condition holds for some α, β without giving all possible values of them.EQUATIONthen Definition 1 holds with α ∈ [ 5 /2, +∞) and β ∈ [ 4α /5, α).Proof. Let (z, t) = Proj((x, y), S). One can show that the set of minimizers of f in this example is S = {(x, y) : y = -x -1 /2}. Moreover, f * 1 = 0 for x = -y. We will show that α-β-condition holds for i = 1. For i = 2 it can be shown in similar way with change of variables. We have∂ x f 1 (x, y) = ∂ y f 1 (x, y) = 2(x + y) (1 + (x + y) 2 ) 2 .Therefore, we need to show that2(x + y) (1 + (x + y) 2 ) (x -z + y -t) ≥ (α -β) (x + y) 2 1 + (x + y) 2 -αf i (z, t). Note that f i (z, t) = (z+t) 2 1+(z+t) 2 = (-1 /2) 2 1+(-1 /2) 2 = 1 5. Moreover, we can compute the projection operator onto S. After simple derivations, the projection can be expressed asProj((x, y), S) = 1 2 x -y -1 /2 -x + y -1 /2 .Therefore, we need to satisfy2(x + y) (1 + (x + y) 2 ) 2 (x + y + 1 /2) ≥ (α -β) (x + y) 2 1 + (x + y) 2 - α 5 .This is equivalent toEQUATION)We should satisfy the above for all values of x + y. First, we need the coefficient next to (x + y) 4 in LHS to be larger or equal of the corresponding coefficient in RHS. This gives us α 5 ≥ α -β. This shows that β can not be zero. Using 2ab ≤ a 2 + b 2 , ( 15) is satisfied as long as we have2(x + y) 2 + α 5 (1 + 2(x + y) 2 + (x + y) 4 ) ≥ (α -β)((x + y) 2 + (x + y) 4 ) + 1 2 (x + y) 2 + 1 2 .Therefore, we should satisfy   coefficient next to (x + y) 4 : α 5 ≥ α -β coefficient next to (x + y) 2 : 2 + 2α 5 ≥ α -β + 1 2 coefficient next to 1 : α 5 ≥ 1 2Note that if the first inequality holds, then the second one is true as well. Therefore, from the first and third inequalities we get that the solution of the system of inequalities is α ≥ 5 2 and β ∈ [ 4α /5, α].EQUATIONthen Definition 1 holds for some α and β = α -8.Proof. Let (z, t) = Proj((x, y), S). Again, we show that α-β-condition holds for f 1 ; for f 2 it can be proved with the same arguments with change of variables. Note that f * i = 0 and f * > 0. We also observe that S contains two points in total, and both of them of the form (t, t) where for one t is close to 0 (it is around t ≈ 0.00067) and for second t is close to 2 (it is around t ≈ 1.99932). Besides, note that c := min i min (t,t)∈S f i (t, t) ∈ (0, 1) and c ≈ 9 • 10 -7 , which means that we are close to interpolation.We have in this case∂ x f 1 (x, y) = 2x exp(-x 2 -y 2 ), ∂ y f 1 (x, y) = 2y exp(-x 2 -y 2 ).Therefore, we need to satisfy exp(-EQUATIONNote that if β = 0 and x, y → +∞, then the inequality is obviously can not be satisfied for all x, y ∈ R. Indeed, assume β = 0, then since f 1 (z, t) < 1 and LHS goes to 0 while RHS to α -αf 1 (z, t) > 0.Rearranging terms in (16) , we should satisfy exp(-x 2 -y 2 )(2x 2 + 2y 2 + α -β) + αf 1 (z, t) ≥ exp(-x 2 -y 2 )(2xt + 2yt) + (α -β).Using 2ab ≤ a 2 + b 2 , the above is satisfied if the following inequality holds exp(-x 2 -y 2 )(2x 2 + 2y 2 + α -β) + αc ≥ exp(-x 2 -y 2 )(x 2 + y 2 + 2t 2 ) + (α -β) ⇔ exp(-x 2 -y 2 )(x 2 + y 2 + α -β) + αc ≥ exp(-x 2 -y 2 ) • 2t 2 + (α -β).Since t ∈ (0, 2) we can choose α -β = 8, so thatEQUATIONthen Definition 1 holds for some α and β = α -1.Proof. Let (z, t) = Proj((x, y), S). For this example, we have f * 1 = 1 4 (achieved at (0, 0)), f * 2 = 0 (achieved at (2.5, 2.5)), and f * ≈= 0.408 (achieved at (2.471, 2.471)). Besides, we have f (0, 0) = 0.587963 and f (2.5, 2.5) = 0.409091. Besides, c := min i min (z,t)∈S f i (z, t) = f 2 (2.471, 2.471) = 0.00167918. Let us show that α-β-condition holds for f 1 ; for f 2 it can be shown similarly. We have∂ x f 1 (x, y) = 6x (4 + x 2 + y 2 ) 2 , ∂ y f 1 (x, y) = 6y (4 + x 2 + y 2 ) 2 .Therefore, we need to satisfy for some α and β6 (4 + x 2 + y 2 ) 2 (x(x -z) + y(y -t)) ≥ (α -β) 1 + x 2 + y 2 4 + x 2 + y 2 -f 1 (z, t) ⇔ 6x 2 + 6y 2 -6xz -6yt ≥ (α -β)(1 + x 2 + y 2 )(4 + x 2 + y 2 ) -αf 1 (z, t)(4 + x 2 + y 2 ) 2 ⇔ 6(x 2 + y 2 ) + αf 1 (z, t)(16 + 8(x 2 + y 2 ) + (x 2 + y 2 ) 2 ) ≥ 6xz + 6yt +(α -β)(4 + 5(x 2 + y 2 ) + (x 2 + y 2 ) 2 ).The above is satisfied for all x, y ∈ R and α -β = 1 if we have 6(x 2 + y 2 ) + αf 1 (z, t)(16+ 8(x 2 + y 2 ) + (x 2 + y 2 ) 2 ) ≥ 3(x 2 + y 2 ) + 3z 2 + 3t 2 +(4 + 5(x 2 + y 2 ) + (x 2 + y 2 ) 2 ).To satisfy the above for all x, y ∈ R we should have   16αf 1 (z, t) ≥ 4 + 3(z 2 + t 2 ) 6 + 8αf 1 (z, t) ≥ 3 + 5 αf 1 (z, t) ≥ 1,where z = t = 2.471, and f 1 (z, t) = 0.0016718. We can satisfy α-β-condition with α ≳ 1512.4586.Example 6. Let f 1 , f 2 : R 2 → R be such thatEQUATIONthen Definition 1 holds with α ≥ 2 mini min (z,t)∈S fi(z,t) ≈ 41.369325 and β = α -1. Besides, Definition 1 does not hold with β = 0 not satisfy Definition 1 with β = 0.Proof. Let (z, t) = Proj((x, y), S). We show that α-β-condition holds for f 1 ; for f 2 the proof is similar with change of variables. In this case, f * i = 0, while f * > 0 (f * ≈ 0.316988 at points (0.159375, 0.159375) and (0.840625, 0.840625)). Besides, we have c := min i min (z,t)∈S f i (z, t) ≈ 0.048345 > 0. Moreover, We have∂ x f 1 (x, y) = 2x (1 + x 2 + y 2 ) 2 , ∂ y f 1 (x, y) = 2y (1 + x 2 + y 2 ) 2 .Therefore, we need to satisfy for some α and β1 (1 + x 2 + y 2 ) 2 (2x(x -z) + 2y(y -t)) ≥ (α -β) x 2 + y 2 1 + x 2 + y 2 -αf 1 (z, t) ⇔ 2x 2 + 2y 2 -2xz -2yt ≥ (α -β)(x 2 + y 2 )(1 + x 2 + y 2 ) -αf 1 (z, t)(1 + x 2 + y 2 ) 2 ⇔ 2x 2 + 2y 2 + αf 1 (z, t)(1 + 2(x 2 + y 2 ) + (x 2 + y 2 ) 2 ) ≥ 2xz + 2yt + (α -β)(x 2 + y 2 )(1 + x 2 + y 2 ).Note that if we take β = 0 and x, y → +∞, then LHS grows as αf 1 (z, t)(x 2 + y 2 ) 2 and RHS grows as α(x 2 + y 2 ) 2 , therefore in the limit the RHS is larger. This implies that β ̸ = 0. Using 2ab ≤ a 2 + b 2 the above is satisfied if we haveEQUATION)Let us take α -β = 1 and α ≥ 2 mini min (z,t)∈S fi(z,t) ≈ 41.369325. With this choice, we havez 2 + t 2 ≤ 2 ≤ αf 1 (z, t), 1 + α -β = 2 ≤ 2 + 2αf 1 (z, t), α -β = 1 < 2 ≤ αf 1 (z, t).Therefore, LHS is always larger than RHS in (17) .EQUATION)where X ∈ R n×m , W = (w i ) n i=1 ∈ R k×n , S = (s j ) m j=1 ∈ R k×m , and rank(X) = r ≥ k. We assume that X is generated using matrices W * and S * with non-zero additive noise that minimize empirical loss, namely,X = (W * ) ⊤ S * +(ε ij ) i∈[n],j∈[m]where W * , S * = argmin W,S f (W, S). Let X be any bounded set that contains S. Then Definition 1 is satisfied with α = β + 1 and some β > 0.Proof. Since k ≤ r, then the matrix factorization problem has a unique solution which can be found from SVD decomposition of X [76] .We have∇ wi f ij (W, S) = (w ⊤ i s j -X ij )s j , ∇ sj f ij (W, S) = (w ⊤ i s j -X ij )w i .Therefore, we need to show that(w ⊤ i s j -X ij )s j , w i -w * i + (w ⊤ i s j -X ij )w i , s j -s * j ≥ α -β 2 (X ij -w ⊤ i s j ) 2 - α 2 (X ij -(w * i ) ⊤ s * j ) 2 , since f * ij = 0. Since f ij is convex w.r.t. w i , the above holds if we have 1 2 (w ⊤ i s j -X ij ) 2 - 1 2 (s ⊤ j w * i -X ij ) 2 + 1 2 (w ⊤ i s j -X ij ) 2 - 1 2 (w ⊤ i s * j -X ij ) 2 ≥ α -β 2 (X ij -w ⊤ i s j ) 2 - α 2 (X ij -(w * i ) ⊤ s * j ) 2 .Let us take α = β + 1, then we can simplify the above as follows1 2 (w ⊤ i s j -X ij ) 2 + α 2 (X ij -(w * i ) ⊤ s * j ) 2 ≥ 1 2 (s ⊤ j w * i -X ij ) 2 + 1 2 (w ⊤ i s * j -X ij ) 2 (18)Since we consider X to be bounded, then there exist r ≥ 0 such that ∥s j ∥, ∥w i ∥ ≤ 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 ij (X ij -(w * i )⊤s * j ) 2 = min ij ε 2 ij > 0.Therefore, we can take α ≥ 2C c to verify (18) .C.1.6 Proof of example 5Example 5. Consider training a two-layer neural network with a logistic lossEQUATION)for a classification problem where ϕ(t):= log(1 + exp(-t)), W ∈ R k×d , v ∈ R k , σ is a ReLU function applied coordinate-wise, y i ∈ {-1,+1} is a label and x i ∈ R d is a feature vector. Let X be any bounded set that contains S. Then the α-β-condition holds in X for some α ≥ 1 and β = α -1.Proof. Let (Z, z) := Proj((W, v), S). We have the following derivations for gradientsR k×d ∋ ∇ W f i (W, v) = ϕ ′ (y i v ⊤ σ(W x i )) • y i (v • 1 W xi≥0 )x ⊤ i + 2λ 2 W, R k ∋ ∇ v f i (W, v) = ϕ ′ (y i v ⊤ σ(W x i )) • y i σ(W x i ) = ϕ ′ (y i v ⊤ σ(W x i )) • y i (W x i ) • 1 W xi≥0 +2λ 1 v = ϕ ′ (y i v ⊤ σ(W x i )) • y i (W x i ) • e w + 2λ 1 v,where we denote e w := 1 W xi≥0 ∈ R k . Besides, we denote e z := 1 Zxi≥0 ∈ R k . Note that the optimal value of f * i > 0 because of the L2 regularization. Note that we have the following relationsEQUATIONNote 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 f * i in X , and due to continuity there existsc := min i∈[n] min (Z,z)∈S f i (Z, z) > 0.We need to show that there exist some α and β such thatEQUATIONAlgorithm 1 SGD with constant stepsize 1: Input: Stepsize γ 2: for k = 0, 1, 2, . . . , K -1 do3: Sample i k ∼ Unif[n] and compute ∇f i k (x k ) 4:Update modelx k+1 = x k -γ∇f i k (x k ) 5:end for where we use (19) . Since ϕ is convex, then we have ϕ ′ (x)(x -y) ≥ ϕ(x) -ϕ(y). Therefore, using (19) again, we get that ( 20) is satisfied if we have2ϕ(y i (v • e w ) ⊤ W x i ) -ϕ(y i (v • e w ) ⊤ Zx i ) -ϕ(y i (z • e w ) ⊤ W x i ) + λ 1 ⟨v, v -z⟩ + λ 2 ⟨W, W -Z⟩ ≥ α ϕ(y i (v • e w ) ⊤ W x i ) + λ 1 ∥v∥ 2 + λ 2 ∥W ∥ 2 F -ϕ(y i (z • e z ) ⊤ Zx i ) -λ 1 ∥z∥ 2 -λ 2 ∥Z∥ 2 F -β ϕ(y i (v • e w ) ⊤ W x i ) + λ 1 ∥v∥ 2 + λ 2 ∥W ∥ 2 F -f *i . Now we take α = β + 1 and simplify the above as followsEQUATIONEQUATIONbecause we also have ϕ(y i (z • e z ) ⊤ Zx i ) ≥ c for all i and (Z, z) ∈ S. Since (W, v) ∈ X , there exist constants R, r ≥ 0 such that ∥v∥ ≤ r and ∥W ∥ ≤ R, and RHS in ( 22) is bounded by2 max i∈[n] log(1 + exp(Rr∥x i ∥)) ≥ ϕ(y i (v • e w ) ⊤ Zx i ) + ϕ(y i (z • e w ) ⊤ W x i ).Therefore, we can take α ≥2 max i∈[n] log(1+exp(Rr∥xi∥)) c-f * i , 1 and β = α -1.Remark 3. The result suggest that the choice β = 0 is possible only if constants r and R are small, i.e. locally around S only. In order to satisfy α-β-condition in larger set X , one needs to choose β > 0.Constant stepsize. In this section, we present the proof of convergence of SGD with constant stepsize under α-β-condition for completeness of the presentation. Theorem 1. Assume that Assumptions 1-2 hold. Then the iterates of SGD (Alg. 1) with stepsize γ ≤ α-β 2L satisfyEQUATIONProof. Let x k p ∈ Proj(x k , S) satisfies Definition 1. Using smoothness we haveE k dist(x k+1 , S) 2 ≤ E k ∥x k+1 -x k p ∥ 2 = dist(x k , S) 2 -2γE k ∇f i k (x k ), x k -x k p + γ 2 E k ∥∇f i k (x k )∥ 2 (i) ≤ dist(x k , S) 2 -2αγE k f i k (x k ) -f i k (x k p ) + 2βγE k f i k (x k ) -f * i k + 2Lγ 2 E k f i k (x k ) -f * i k = dist(x k , S) 2 -2αγE k f i k (x k ) -f i k (x k p ) + 2γ(β + Lγ)E k (f i k (x k ) -f i k (x k p )) + (f i k (x k p ) -f * i k ) ,where (i) holds because of the α-β-condition and smoothness. Now we need to choose a stepsizeγ ≤ α-β 2L to get E k dist(x k+1 , S) 2 ≤ dist(x k , S) 2 -γ(α -β)E k f i k (x k ) -f i k (x k p ) + 2γ(β + Lγ)E k f i k (x k p ) -f * i k .Taking full expectation, noting that x k p is independent of the randomness of i k , and performing simple derivations, we getEQUATIONDecreasing stepsize. Now we present the results with decreasing stepsize. Theorem 4. Assume that Assumptions 1-2 hold. Then the iterates of SGD with decreasing stepsizeEQUATIONProof. Similarly to the proof of constant stepsize SGD we can obtainE k dist(x k+1 , S) 2 ≤ dist(x k , S) 2 -γ k (α -β)E k f i k (x k ) -f i k (x k p ) + 2γ k (β + Lγ k )E k f i k (x k p ) -f * i k , since γ k ≤ γ 0 ≤ α-β2L for all k. Now we follow standard proof techniques [24] for decreasing stepsize. Taking full expectation and dividing both sides by α -β we getγ k E f (x k ) -f * ≤ E dist(x k , S) 2 -E dist(x k+1 , S) 2 α -β + 2β α -β γ k σ 2 int + 2L α -β γ 2 k σ 2 int .Summing the above from iteration 0 to K -1 leads toK-1 k=0 γ k E f (x k ) -f * ≤ E dist(x 0 , S) 2 α -β + 2β α -β σ 2 int K-1 k=0 γ k + 2L α -β σ 2 int K-1 k=0 γ 2 k .Therefore, we getmin 0≥k<K E f (x k ) -f * ≤ E dist(x 0 , S) 2 (α -β) K-1 k=0 γ k + 2β α -β σ 2 int + 2L α -β σ 2 int K-1 k=0 γ 2 k K1 k=0 γ k .Using the results of Theorem 5.7 [24] we getK-1 k=0 γ 2 k ≤ 2γ 2 0 log(K + 1), K-1 k=0 γ k ≥ 4γ 0 5 √ K.Therefore, the final rate we get is Compute Polyak stepsizemin 0≥k<K E f (x k ) -f * ≤ E dist(x 0 , S) 2 (α -β) 4 5 γ 0 √ K + 2β α -β σ 2 int + 2L α -β σ 2 int 2γ 2 0 log(K + 1) 4γ0 5 √ K = 5E dist(x 0 , S) 2 4(α -β)γ 0 √ K + 5γ 0 Lσ 2 int α -β log(K + 1) √ K + 2β α -β σ 2 int .γ k := min f i k (x k ) -f * i k c∥∇f i k (x k )∥ 2 , γ b 5:Update modelx k+1 = x k -γ k ∇f i k (x k ) 6: end for C.2.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 to 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/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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 a 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 to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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 as the institution conducting the review.Our implementation is based on the open source repository https://github.com/archana95in/ Escaping-saddles-using-Stochastic-Gradient-Descent from[17] with small changes to track necessary quantities.2 Our implementation is based on the open source repository https://github.com/fhueb/ parameter-agnostic-lzlo from[33] with small changes to track necessary quantities. The detailed experiment description is given in AppendixD.2.3 We use x K (for a large value of K) to approximate the minimizer x * .Our implementation is based on open source AlgoPerf code https://github.com/mlcommons/ algorithmic-efficiency with minimal changes to track necessary quantities.(Cited on page 5)We use the implementation from[17] that can be found https://github.com/archana95in/ Escaping-saddles-using-Stochastic-Gradient-Descent.The implementation can be found following the link https://github.com/fhueb/ parameter-agnostic-lzloThe quality of performance is measured differently from one task to another; we defer to the[16] for a more detailed description of the competition. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper proposes a novel class of functions and proves convergence of gradient descent (and some other optimizers).
Contrary to some previous classes, in relation to deep neural networks, this new class does not require extreme overparameterization.
In addition to theoretical convergence results, experiments are provided showing that some example neural networks seem to belong to the function class.
strength_weakness: strength_weakness: Some of the highlighted differences with respect to previous work are unfair, in particular previous work in overparameterized models. 
For 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.  

Also, 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.
questions: 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. 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.
questions: 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: 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.
paper_summary: paper_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.

 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.
strength_weakness: strength_weakness: Overall, the paper has no major weaknesses, but it can improve on a few minor points.

1.) 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. 

2.) 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.  

3.) 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.
questions: 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: 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:

1) 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)]: 

     $\||H(x)\|| \leq L_0+L_1\||\nabla f(x)\||$. 

The 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. 

2) 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. 

References:
1.) 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.

2.) Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. "Convergence of adam under relaxed assumptions." In Advances in Neural Information Processing Systems 36 (2024).
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
questions: questions: Questions:

See Weaknesses for main questions.

Other questions:
- “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?
- 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?
- 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].
- 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.
- Line 84-85: there does exist works showing a PL inequality with only linear overparameterization in width, see [3].

Minor remarks:
- 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.
- $\gamma_b$ in Theorem 2 is not defined (in the main text).

[1] Nesterov, Lectures on Convex Optimization, Second Edition, 2018.

[2] Rebjock, Boumal, Fast convergence to non-isolated minima: four equivalent conditions for C2 functions, arXiv:2303.00096

[3] Marion, Wu, Sander, Biau, Implicit regularization of deep residual networks towards neural ODEs, ICLR 2024.
limitations: limitations: The limitations are adequately addressed.

Comments: title: Response
Response
Response to the Author's Rebuttal
Thank you for your rebuttal
Thank you for your rebuttal.
comment: Dear reviewer,

As the deadline is approaching, we would like to know if the above response answers your concern regarding the values of $\beta$. We highlight that Resnet architecture can be accurately trained using SGD with CycleOneLR learning rate schedule reaching small loss. Therefore the issue of finding a bad approximation of $x^*$ is not the same as for large models. Based on Resnet experiments the values of $\beta$ tend to decrease with the number of layers as we expect (i.e., increasing the complexity of the model). Hence, in our opinion, the proposed $\alpha$-$\beta$-condition captures all expected trends in the training (convergence to the non-vanishing neighborhood, neighborhood size vanishes as a model becomes more over-parameterized).
We would like to highlight that the value of $\beta$ itself is not involved in the convergence rate, but rather $\alpha-\beta$ and $\beta\sigma^2_{\mathrm{int}}$. While $\alpha-\beta$ is typically a constant of order $0.1$ in our experiments, we also observe that $\beta\sigma^2\_{\mathrm{int}}$ decreases with increasing over-parameterization (see figures in additional pdf). Moreover, we decided to conduct experiments on Resnet18 and Resnet34 on CIFAR100 to support our claims on larger models. Since the rules regarding posting external links are unclear, we provide approximate values of the smallest $\beta$ found in the experiments over 3 runs:
|model| batch size | $\beta$|
|-------|:-------------:|:----------:|
|Resnet18| 64 | 578|
|Resnet18| 128| 160|
|Resnet18| 256 | 49|
|Resnet34| 64| 797|
|Resnet34|128 | 494|
|Resnet34| 256| 70|

We will include the plots of this set of experiments in the revised version of the paper. We observe that the value of $\beta$ tends to decrease when we increase the depth of the Resnet model (note that we have results for Resnet9 in the main paper). These results are consistent with all our previous comments, but in this case for larger models as well. 

Based on all the results, we do not agree with the reviewer that $\alpha$-$\beta$-condition might be too relaxed. The experimental and theoretical results show all expected practical trade-offs.
Thank you for the detailed response, my opinion is still that the paper should be accepted.
Thank you so much for providing the detailed explanation and the proof sketch.

For W1, I agree with the new proof sketch which turns the set $S$ bounded by adding the regularization term. For W3, I agree that verifying the condition theoretically on NN with more complicated architectures can be a significant next step.

For W2 however, my concern remains about the non-vanishing term. Based on the author's argument, I agree that the non-vanishing term is necessary. However, this does poses the question of whether the $\alpha$-$\beta$ is a condition powerful enough to guarantee a good convergence property. In short, I am concerned that this condition might be too relaxed, as one can choose super large $\beta$ and $\alpha$ while maintaining the difference between the two.

For W4, I understand the difficulty of verifying $\alpha$-$\beta$ condition, and I am truly aware of the fact that finding minimizers of NN training is basically not possible. However, my real concern is that the values of $\alpha$ and $\beta$ are large for simpler networks, but smaller for more complicated networks. I still suspect that the large values of $\alpha$ and $\beta$ will hold across all neural network training.

Combining W2 with W4, I still have concern that the $\alpha$-$\beta$ condition may not be a good condition for NN training.

I have raised the score based on the new proof sketch, but I believe that the paper still falls below the acceptance borderline given the above concern.
Dear reviewers,

could you have a look at the authors response and comment on them if you have done so, yet.

thanks in advance 


your area chair
I would like to sincerely thank the authors for their detailed reply. In particular, I appreciate the authors adding the experiments I've requested. I think they will enhance the quality of the submission. The response has addressed all my concerns. 
As I said in my initial review, I think this paper is interesting and provides a strong contribution. Therefore, I am happy to raise my score from 7 to 8.
I thank the authors for their detailed rebuttal. Regarding the "best" level of over-parameterization, the authors adequately answered my question (the term "best" referred to the fact that I thought that there was some sort of tradeoff). I keep my score.