On the Quality of the Initial Basin in Overspecified Neural Networks

Itay Safran, Ohad Shamir

Abstract Deep learning has achieved remarkable success despite the theoretical challenge posed by the highly non-convex nature of neural network objective functions. Training such networks is known to be computationally hard in the worst case, yet standard optimization algorithms often converge to global minima with ease. This paper investigates the geometric structure of the objective function for ReLU networks, specifically focusing on the properties of the landscape at random initialization. We identify conditions under which overspecified networks—those with more neurons than strictly necessary—exhibit a favorable geometry characterized by a high probability of initializing in a "good" basin. These basins are defined by the existence of monotonically decreasing paths to a global minimum, suggesting that the "theory-practice gap" in deep learning is bridged by the high-dimensional advantages of overspecification.

1. Introduction: The Theory-Practice Paradox

In classical computer science theory, training even a small neural network is an NP-hard problem. The loss surfaces are theoretically riddled with local minima, saddle points, and plateaus that should trap gradient-based optimizers like Stochastic Gradient Descent (SGD). However, in practice, massive models are trained successfully every day. This paper addresses this mystery by analyzing the geometric structure of the loss function from a probabilistic perspective. The central question is: why does a random starting point so often lead to a successful optimization outcome?

2. Geometric Framework and Methodology

The authors employ a rigorous geometric analysis of the objective function for networks utilizing Rectified Linear Unit (ReLU) activations. Unlike studies that focus on the dynamics of specific algorithms, this work examines the static landscape of the parameter space.

Two key concepts are introduced:

  1. Basins: Defined as convex regions of the parameter space where the loss function is "well-behaved"—specifically, regions where every local minimum is also a global minimum for that specific region.
  2. Monotonic Paths: The authors investigate the existence of continuous paths from a random initialization point to a global minimum along which the objective value strictly decreases.

By calculating the probability that standard initialization schemes (e.g., Gaussian weight distribution) land within these favorable regions, the paper quantifies how network architecture affects trainability.

3. The Role of Overspecification

A recurring theme in the results is the "overspecification advantage." While intuition might suggest that more parameters make a problem more complex, the authors show that extra neurons actually simplify the optimization landscape. These additional dimensions provide more "directions of descent," effectively smoothing out the landscape and making it exponentially more likely that a random initialization lands in a high-quality basin.

This finding suggests that the hardness results of previous literature are "brittle." For instance, problems designed to be difficult for small networks become trivial when a few additional neurons are added, as the "bad" local minima either vanish or become statistically insignificant.

4. Theoretical Results Across Data Regimes

The paper evaluates the probability of optimization success across several mathematically defined data scenarios:

4.1 Singleton and Full-Rank Data

For "singleton" data (where each example is non-zero on only one coordinate), the authors prove in Theorem 2 that the probability of failing to find a good basin is at most $2d(3/4)^n$, where $n$ is the number of neurons. This failure rate decays exponentially as the network size increases.

In the case of Full-Rank Data (where the number of examples $m$ is less than or equal to the input dimension $d$), Theorem 4 demonstrates that a network size of only $O(\log m)$ neurons is sufficient to ensure initialization in a basin containing a global minimum with overwhelming probability.

4.2 Clustered and Low-Dimensional Data

For data points grouped into tight clusters, Theorem 5 shows that the network will likely initialize in a high-quality basin if the network size is $\Omega(\log d)$. However, the authors note a potential "curse of dimension" in the Low Intrinsic Dimension regime; here, the number of neurons required to guarantee success may still grow exponentially with the dimension of the data manifold, indicating a limit to the smoothing effects of overspecification without further structural assumptions.

5. Discussion and Limitations

While the paper provides a robust geometric explanation for the ease of training, it acknowledges certain boundaries:

  • Geometry vs. Dynamics: The existence of a downhill path does not guarantee that SGD will follow it. The actual trajectory of an optimizer is influenced by momentum, batch size, and learning rates, which are not the focus of this geometric study.
  • Architecture Scope: While some results (Theorem 1) apply to networks of any depth, the detailed probabilistic bounds for basins are primarily derived for two-layer networks. Extending these specific bounds to deep architectures remains an open area for research.

6. Conclusion

This work provides a theoretical foundation for the empirical success of large-scale neural networks. By proving that overspecification transforms the loss landscape into one where "good" basins are ubiquitous and "downhill" paths to global minima are nearly guaranteed, the authors offer a compelling resolution to the theory-practice gap in deep learning optimization.

Summary updated

Abstract

Deep learning, in the form of artificial neural networks, has achieved remarkable practical success in recent years, for a variety of difficult machine learning applications. However, a theoretical explanation for this remains a major open problem, since training neural networks involves optimizing a highly non-convex objective function, and is known to be computationally hard in the worst case. In this work, we study the \emph{geometric} structure of the associated non-convex objective function, in the context of ReLU networks and starting from a random initialization of the network parameters. We identify some conditions under which it becomes more favorable to optimization, in the sense of (i) High probability of initializing at a point from which there is a monotonically decreasing path to a global minimum; and (ii) High probability of initializing at a basin (suitably defined) with a small minimal objective value. A common theme in our results is that such properties are more likely to hold for larger ("overspecified") networks, which accords with some recent empirical and theoretical observations.
BibTeX
@inproceedings{safran2016quality,
  author = {Itay Safran and Ohad Shamir},
  title = {{On the Quality of the Initial Basin in Overspecified Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2016},
  url = {https://openreview.net/forum?id=Sk-F-oZd-H},
}
Figure