Loss Landscape Characterization of Neural Networks without Over-Parametrization

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.

Strengths

The paper is very clear and well-written. It tackles the crucial question of understanding which structure in the loss landscape of deep neural networks enables efficient optimization with first-order methods. The arguments in favour of the proposed condition are fairly compelling, with both theoretical results and experimental insights. I verified the proof of one of the main results (Theorem 1), which is correct.

Weaknesses

The convergence for SGD is shown up to a non-vanishing error term $O(\beta \sigma^2)$. While the authors give some explanation on this term, I would have liked more insights: is the error term appearing for SPS and NGN the same (this is not directly obvious from the formulas)? Do authors think this term is an artefact of the proof technique, or intimately connected to the $\alpha-\beta$ condition? The authors argue that overparameterization leads to vanishing of this term. As far as I understand, both $\beta$ and $\sigma^2$ are affected by overparameterization, and both terms should decay with overparameterization. Is this correct? Does this give an insight of the "best" level of overparameterization?

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.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

4

Limitations

The limitations are adequately addressed.

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.

Strengths

The paper has several major strengths that make it a clear accept in my view: 1. Showing the PL-condition and Aiming do not necessarily hold for networks of realistic size encountered in practice. To the best of my knowledge, such an extensive empirical investigation has not been done before. This is of prime importance in my view, as much of the recent DL optimization literature takes these conditions for granted despite lacking a strong empirical foundation. I've long harbored doubts about how relevant the analysis in the over-parametrized regime (where said conditions hold with high probability) is to practice. Especially considering analyses over the past couple years showing networks that are well-approximated by their first-order Taylor expansion do not perform as well as networks not in this regime. So, I think the extensive empirics done in this paper showing these conditions don't hold for networks commonly used in practice is a valuable contribution to the literature 2. Introduction of the $\alpha-\beta$ condition and convergence analysis. The authors have gone beyond just identifying failure modes of previous conditions. They introduce a new condition, the $\alpha-\beta$ condition, under which optimizers like SGD (and several variants) converge to a ball-of-noise (or the minimum in the interpolation setting). Moreover, the condition allows for more realistic loss landscapes, i.e., saddle-points can occur. 3. Empirical verification of $\alpha-\beta$ condition. This is one of the most significant contributions of the paper. The authors provide strong empirical evidence that $\alpha-\beta$ holds for networks of practical interest. 4. The paper is very well-written. I found the paper easily to follow and enjoyable to read.

Weaknesses

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

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.

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

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

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.

Strengths

1. The newly introduced $\alpha$-$\beta$ condition covers the case where the function has saddle points. 2. The paper tries to give examples for which the condition holds 3. The paper empiricallly indentified cases where the aiminig condition does not hold

Weaknesses

1. The proof for Example 4 (shallow neural network) is problematic. In particular, based on the definition and assumption of $S$, the paper derived $f_i^* = 0$, and that points in $S$ have bounded norm (which is necessary to obtain the equation below line 684). However, these two conditions are contradictory as the logistic loss only achieves zero training loss when the output of the neural networks has magnitude infinity. This breaks the proof of Example 4. 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

Is it possible to establish the convergence rate of the non-stochastic gradient descent based on the proposed condition and the smoothness condition?

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

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.

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.

Strengths

The paper is written very clearly. It provides a new theoretical tool for studying convergence in deep neural networks, and has the potential of high impact.

Weaknesses

Some of the highlighted differences with respect to previous work are unfair, in particular previous work in overparameterized models. 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

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?

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

NA

Thank you for your rebuttal.

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.

Thank you for your rebuttal

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.

Response to the Author's Rebuttal

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.