Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks

Mahdi Soltanolkotabi, Adel Javanmard, Jason D. LeeIEEE Trans. Information Theory 2017 · DOI · OpenReview

Abstract: In this paper we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the number of observations are fewer than the number of parameters in the model. We show that with quadratic activations the optimization landscape of training such shallow neural networks has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.

Introduction

Training neural networks is theoretically NP-hard because the loss functions are high-dimensional and non-convex, meaning they could be riddled with "bad" local minima where optimization gets stuck. Yet, in practice, simple local search heuristics like gradient descent (GD) and stochastic gradient descent (SGD) consistently find globally optimal solutions.

This paper addresses this mystery by focusing on the over-parameterized regime, where the number of model parameters exceeds the number of training samples. The authors aim to characterize the geometry of the optimization landscape to understand why local search works so well in this specific, yet practically common, setting.

Methods and Theoretical Framework

The paper focuses on shallow (one-hidden-layer) fully connected networks using two main analytical strategies:

  1. Global Landscape Analysis: For networks with quadratic activation functions ($\phi(z) = z^2$), the authors analyze the entire loss surface. They use tools from linear algebra and matrix analysis to characterize the properties of critical points, such as minima and saddle points.
  2. Local Convergence Analysis: For general differentiable activations (like Sigmoid, Softplus, or Erf), they analyze the trajectory of gradient descent. They prove that if the network is initialized sufficiently close to a "planted" solution, the gradient remains well-behaved, leading to guaranteed convergence.
Common activation functions analyzed in the study, including ReLU, Softplus, Sigmoid, and Erf.

The proofs rely heavily on random matrix theory and concentration of measure to show that these favorable landscape properties hold with high probability when inputs are drawn from Gaussian distributions. The study uses synthetic data models, including Gaussian inputs and "planted" models where labels are generated by a teacher network.

Key Insights: The Power of Width

The core finding is that as the number of hidden neurons ($k$) increases relative to the input dimension ($d$) and sample size ($n$), the complex non-convex landscape "flattens out" in a way that eliminates traps.

  • No Spurious Minima: For quadratic activations, every local minimum is a global minimum. There are no "bad" valleys to get stuck in.
  • Strict Saddles are Escapable: All saddle points are "strict," meaning they have at least one direction of strictly negative curvature. This ensures that gradient descent will always find a way down rather than getting stuck on a plateau.
  • Linear Convergence: Unlike the slow convergence often seen in non-convex problems, over-parameterization allows gradient descent to converge at a linear rate (exponentially fast) to the global optimum, provided the initialization is reasonable.

Key Results and Numerical Confirmation

The theoretical analysis yields several concrete results:

  • Quadratic Case: If the number of hidden units $k \ge 2d$, the training loss has no spurious local minima for any arbitrary dataset. Furthermore, if $d \le n \le cd^2$, the global minimum is exactly zero, meaning the network fits the data perfectly.
  • General Case: For differentiable activations, gradient descent converges to a globally optimal model at a linear rate, given a planted model and Gaussian inputs.
Probability of successful convergence to a global optimum as a function of network width (k) and input dimension (d).

Numerical experiments confirm these findings. As shown in the figures above, the probability of having no spurious local minimizers jumps from 0 to 1 as the number of parameters ($kd$) exceeds the number of samples ($n$). Interestingly, this holds even for random labels, echoing the empirical finding that deep nets can "memorize" random data.

Limitations and Future Work

While providing significant theoretical progress, the study notes several areas for future research:

  • Shallow Architecture: The results are limited to networks with a single hidden layer. Extending these "benign landscape" proofs to deep architectures remains a major challenge.
  • Activation Functions: While the global landscape results are powerful, they rely on quadratic activations. Common activations like ReLU are non-differentiable at zero, requiring different analytical techniques.
  • Gaussian Assumption: Much of the convergence analysis assumes Gaussian input data. Understanding how real-world data structures affect the landscape is a key next step.

Summary updated

Abstract

In this paper, we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the numbers of observations are fewer than the number of parameters in the model. We show that with the quadratic activations, the optimization landscape of training, such shallow neural networks, has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions, we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.
BibTeX
@article{soltanolkotabi2017theoretical,
  author = {Mahdi Soltanolkotabi and Adel Javanmard and Jason D. Lee},
  title = {{Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  doi = {10.1109/tit.2018.2854560},
}
Figure