Local Minima Are Rare in Higher Dimensions

• categories: Data Science, Observation

Why Local Minima Are Rare in Higher Dimensions
In high-dimensional optimization landscapes, local minima become increasingly rare compared to saddle points. This phenomenon is particularly relevant in the context of training deep neural networks, where the parameter space is vast.

---

Key Reasons

1. Saddle Points Dominate in High Dimensions:

   • In a $d$-dimensional space, a critical point (where the gradient is zero) can be classified based on the Hessian matrix (the matrix of second derivatives).
   • The Hessian can have eigenvalues that are positive (indicating a local minimum), negative (indicating a local maximum), or zero/indeterminate (indicating a saddle point).
   • As $d$ increases, the probability of all eigenvalues being positive (necessary for a local minimum) decreases exponentially. Most critical points in high dimensions are saddle points with mixed signs of eigenvalues.

2. Random Functions and High-Dimensional Spaces:

   • For random functions in high-dimensional spaces, critical points are overwhelmingly likely to be saddle points due to the combinatorial nature of eigenvalue arrangements.
   • Example: In a 10-dimensional space, a critical point with 5 positive and 5 negative eigenvalues is far more likely than one with all 10 positive eigenvalues.

3. The Curse of Dimensionality:

   • In high dimensions, the volume of parameter space grows exponentially. Regions that correspond to local minima occupy a vanishingly small fraction of this space compared to saddle points.

4. Energy Landscape in Deep Neural Networks:

   • Research in deep learning shows that the loss surfaces of neural networks tend to have many saddle points and plateaus rather than sharp local minima.
   • Local minima, when they occur, are often close in performance to the global minimum due to the over-parameterized nature of modern networks.

---

Implications for Optimization

1. Gradient Descent and Saddle Points:

   • Saddle points slow down optimization because gradients near these points are small or zero in some directions.
   • However, modern optimization methods (e.g., momentum, Adam) help escape saddle points by introducing directional bias or adaptive learning rates.

2. Local Minima Are Often “Good Enough”:

   • In high-dimensional problems, even if a local minimum is found, it often has a loss value close to the global minimum due to the smoothing effect of averaging over many dimensions.

3. Regularization in Neural Networks:

   • Over-parameterization in neural networks reduces the chance of encountering sharp local minima. This is one reason why deep networks generalize well despite their complexity.

---

Theoretical Insights

1. Critical Point Classification (Hessian Analysis):
   For a $d$-dimensional optimization problem:

   • Saddle points dominate because the probability of all $d$ eigenvalues being positive is proportional to $2^{-d}$.
   • The fraction of critical points that are true local minima shrinks as $d$ increases.

2. Loss Landscapes of Neural Networks:

   • Empirical studies and theoretical models of neural networks suggest that sharp local minima (with high curvature) are rare and typically correspond to poor generalization.
   • Flat minima (where the Hessian eigenvalues are small) are more common and tend to generalize better.

---

Practical Observations

1. Optimization in Deep Learning:

   • Gradient descent rarely “gets stuck” in poor local minima due to the scarcity of such points in high-dimensional spaces.
   • Networks often converge to wide basins of attraction corresponding to flat minima.

2. Modern Optimizers:

   • Techniques like SGD with momentum or adaptive learning rates help navigate high-dimensional landscapes efficiently.
   • These methods can escape saddle points faster than plain gradient descent.