Loss landscapes and optimization in over-parameterized non-linear systems and neural networks

Chaoyue Liu, Libin Zhu, Misha BelkinOpenReview 2022 · OpenReview

TL;DR

This paper proposes a new mathematical framework, the "PL* condition," to explain why gradient-based optimization works so well for modern, over-parameterized neural networks. They show that this condition, which is related to the "tangent kernel," holds for wide neural networks and guarantees efficient convergence to a global minimum, even though the loss landscape is "essentially non-convex."

What Problem Does This Paper Address?

Modern machine learning models, especially deep neural networks, have an enormous number of parameters – often far more than the number of data points or constraints. Despite this "over-parameterization" and the fact that their loss landscapes are generally non-convex, gradient-based optimization methods like SGD and Adam are remarkably effective at finding good solutions. The core problem this paper addresses is: Why are these optimization methods so successful in these highly non-convex, over-parameterized settings? Traditional optimization theory often relies on convexity, which doesn't hold here, leaving a gap in our understanding.

Methods

The authors introduce a generalized condition called the PL* condition (a variant of the Polyak-Łojasiewicz condition). This condition states that the gradient of the loss function is sufficiently large relative to the loss value itself, which guarantees convergence. They connect this PL condition to the tangent kernel, a matrix derived from the derivatives of the model's output with respect to its parameters. Specifically, they show that if the tangent kernel is "uniformly conditioned" (meaning its smallest eigenvalue is bounded away from zero), then the loss function satisfies the PL condition. They then develop techniques to prove this uniform conditioning for specific model classes, particularly wide neural networks. They also propose a relaxed version of the PL* condition for "almost" over-parameterized systems.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Essential Non-Convexity: Over-parameterized systems are not just non-convex; they are "essentially non-convex," meaning they lack local convexity even near global minima. This fundamentally differs from under-parameterized systems.
  • PL* Condition as a Unifying Framework: The PL* condition provides a powerful mathematical tool to analyze optimization in these non-convex settings, bridging the gap left by traditional convexity assumptions.
  • Tangent Kernel as the Key: The properties of the tangent kernel, particularly its condition number, are directly linked to whether the PL* condition holds. This offers a concrete way to analyze the optimization landscape.
  • Wide Networks are "Well-Behaved": The paper demonstrates that sufficiently wide neural networks satisfy the PL* condition. This is a crucial insight explaining their successful training.
  • Over-parameterization Improves Conditioning: Similar to linear systems, increasing over-parameterization in non-linear systems tends to improve the conditioning of the tangent kernel, making optimization easier.

Key Results

  • The paper formally defines the PL* condition and shows it implies the existence of solutions and exponential convergence for gradient descent (GD) and stochastic gradient descent (SGD).
  • They prove that wide neural networks satisfy the PL* condition, providing a theoretical explanation for their trainability.
  • The authors establish a connection between the PL condition and the spectrum of the tangent kernel, showing that uniform conditioning of the tangent kernel implies the PL condition.
  • They introduce a relaxed PL condition to handle "almost" over-parameterized systems, relevant for practical scenarios where exact convergence isn't reached.

Limitations and Future Work

  • The paper focuses on specific types of neural networks (feedforward, linear output layers) and assumes certain properties for activation functions. Extending the analysis to more complex architectures like CNNs and ResNets is addressed in appendices, but further work might be needed.
  • The analysis of "almost" over-parameterized systems is a conjecture, with approximate convergence discussed rather than exact.
  • The authors suggest that the conditioning properties discussed might extend to other optimization methods beyond GD/SGD, such as accelerated methods, which would be an interesting avenue for future research.
  • The paper touches upon the transition from over-parameterization to under-parameterization along the optimization path, suggesting this is a key area for future investigation.

Summary updated

Abstract

The success of deep learning is due, to a large extent, to the remarkable effectiveness of gradient-based optimization methods applied to large neural networks. The purpose of this work is to propose a modern view and a general mathematical framework for loss landscapes and efficient optimization in over-parameterized machine learning models and systems of non-linear equations, a setting that includes over-parameterized deep neural networks. Our starting observation is that optimization landscapes corresponding to such systems are generally not convex, even locally around a global minimum, a condition we call essential non-convexity. We argue that instead they satisfy PL⁎, a variant of the Polyak-Łojasiewicz condition [32], [25] on most (but not all) of the parameter space, which guarantees both the existence of solutions and efficient optimization by (stochastic) gradient descent (SGD/GD). The PL⁎ condition of these systems is closely related to the condition number of the tangent kernel associated to a non-linear system showing how a PL⁎-based non-linear theory parallels classical analyses of over-parameterized linear equations. We show that wide neural networks satisfy the PL⁎ condition, which explains the (S)GD convergence to a global minimum. Finally we propose a relaxation of the PL⁎ condition applicable to “almost” over-parameterized systems.
BibTeX
@misc{liu2022loss,
  author = {Chaoyue Liu and Libin Zhu and Misha Belkin},
  title = {{Loss landscapes and optimization in over-parameterized non-linear systems and neural networks}},
  year = {2022},
  url = {https://openreview.net/forum?id=Du06rWqW8za},
  howpublished = {OpenReview},
}
Figure