Negative eigenvalues of the Hessian in deep neural networks

Guillaume Alain, Nicolas Le Roux, Pierre-Antoine Manzagol

TL;DR

This paper investigates the role of negative eigenvalues of the Hessian matrix in deep neural networks, revealing that the quadratic approximation of the loss function is highly inaccurate in these directions. The authors propose that better handling of these negative curvature directions could unlock significant improvements in optimization.

What Problem Does This Paper Address?

Optimizing deep neural networks is notoriously challenging due to their non-convex loss landscapes. While much research has focused on navigating saddle points, the precise nature of non-convexity, particularly the influence of negative eigenvalues of the Hessian, remains less understood. The Hessian, a second-order derivative matrix, provides information about the local curvature of the loss function. In convex optimization, positive eigenvalues indicate a "bowl-like" shape, guiding towards a minimum. However, in deep networks, the Hessian often has negative eigenvalues, signifying directions where the loss decreases as you move away from a point. This paper aims to understand the significance of these negative curvature directions and how they impact optimization.

Methods

The authors employ a combination of theoretical analysis and empirical investigation. They analyze the eigendecomposition of the Hessian matrix at various stages of training. A key technique is the "Jacobian Vector Product" (JVP) trick, which allows them to compute the largest and smallest eigenpairs of the Hessian without explicitly forming the massive Hessian matrix itself. This is crucial given the high dimensionality of deep learning models. They then study the behavior of the loss function along these eigenvector directions, comparing the true loss with a quadratic approximation.

Datasets

  • MNIST: Used for experiments involving a LeNet architecture.
  • CIFAR-10: Also used for experiments, as shown in Figure 1.

Key Insights and Ideas

  • Quadratic Approximation Fails in Negative Curvature: The most striking finding is that while the quadratic approximation of the loss function is accurate in directions of positive curvature, it is wildly inaccurate in directions of negative curvature, especially for larger step sizes. This suggests that standard second-order methods that rely on this approximation might be fundamentally flawed in these regions.
  • Negative Curvature Directions Hold Potential: The paper demonstrates that directions associated with negative eigenvalues offer significant potential for loss reduction. The improvement in loss along these directions remains stable throughout training, unlike directions of positive curvature where improvements diminish.
  • "Temporal Spread" of the Hessian Matters: While the Hessian's spectrum might stabilize, the eigenvectors can change, leading to a "temporal spread" that can hinder the efficiency of second-order methods that slowly update their Hessian approximations.
  • Subspace Stability Differs: The subspace spanned by the largest positive eigenvectors of the Hessian appears relatively stable during optimization, but the subspace spanned by the smallest eigenvectors (associated with negative curvature) is much less stable.

Key Results

  • Empirical studies on MNIST and CIFAR-10 show that the optimal step size in directions of positive curvature is approximately $1/\lambda_i$ (where $\lambda_i$ is the eigenvalue), aligning with theoretical predictions for quadratic functions.
  • However, for negative eigenvalues, this relationship breaks down, and the optimal step size is largely decorrelated from the eigenvalue.
  • The paper quantifies the loss improvement achievable by moving along eigenvector directions, showing that negative curvature directions offer substantial, stable loss reduction potential.

Limitations and Future Work

  • Limited Scope: The authors acknowledge that their study is based on a single architecture (LeNet), optimizer (RMSProp), and dataset (MNIST). They caution that these findings might not generalize to all deep learning scenarios.
  • Focus on Training Loss: The study primarily analyzes the training loss, and the relationship between training and generalization loss is not deeply explored.
  • Computational Cost: Computing the full eigenspectrum of the Hessian is computationally prohibitive for large networks. The paper uses a subset of the training data for eigendecomposition to manage costs.
  • Future Work: The authors suggest developing optimizers that explicitly handle negative eigenvalues, perhaps by maintaining a running approximation of the smallest eigenvector and incorporating updates in that direction. They also propose exploring the use of third-order information to better model the loss landscape in negative curvature regions.

Summary updated

Abstract

The loss function of deep networks is known to be non-convex but the precise nature of this nonconvexity is still an active area of research. In this work, we study the loss landscape of deep networks through the eigendecompositions of their Hessian matrix. In particular, we examine how important the negative eigenvalues are and the benefits one can observe in handling them appropriately.
BibTeX
@inproceedings{alain2018negative,
  author = {Guillaume Alain and Nicolas Le Roux and Pierre-Antoine Manzagol},
  title = {{Negative eigenvalues of the Hessian in deep neural networks}},
  booktitle = {Workshops @ ICLR},
  year = {2018},
  url = {https://openreview.net/forum?id=KO12VhHoJW},
}
Figure