Exact Stochastic Second Order Deep Learning

Fares B. Mehouachi, Chaouki KasmiarXiv 2021 · OpenReview

Abstract

Optimization in Deep Learning is mainly dominated by first-order methods which are built around the central concept of backpropagation. Second-order optimization methods, which take into account the second-order derivatives are far less used despite superior theoretical properties. This inadequacy of second-order methods stems from its exorbitant computational cost, poor performance, and the ineluctable non-convex nature of Deep Learning. Several attempts were made to resolve the inadequacy of second-order optimization without reaching a cost-effective solution, much less an exact solution. In this work, we show that this long-standing problem in Deep Learning could be solved in the stochastic case, given a suitable regularization of the neural network. Interestingly, we provide an expression of the stochastic Hessian and its exact eigenvalues. We provide a closed-form formula for the exact stochastic second-order Newton direction, we solve the non-convexity issue and adjust our exact solution to favor flat minima through regularization and spectral adjustment. We test our exact stochastic second-order method on popular datasets and reveal its adequacy for Deep Learning.

Introduction

Deep learning has long been a "first-order" world, relying almost exclusively on backpropagation and gradient descent variants like Adam or SGD. While second-order methods—which utilize curvature information via the Hessian matrix—promise faster convergence and superior theoretical properties, they have historically been dismissed due to significant practical hurdles.

The Three Hurdles of Second-Order Optimization

Traditionally, second-order methods face three massive obstacles in the context of deep neural networks: computational cost, non-convexity, and capacity/generalization issues. Calculating and inverting a Hessian matrix for millions of parameters is traditionally $O(N^3)$, which is computationally ruinous. Furthermore, in non-convex landscapes, standard Newton methods can be attracted to saddle points. Finally, ensuring that second-order steps lead to "flat minima" for better generalization remains a challenge.

The three fundamental challenges of second-order optimization: Cost, Convexity, and Capacity.

The Sifrian Framework and MK Solution

A new approach by researchers at the Technology Innovation Institute (TII) introduces an exact closed-form solution for stochastic second-order optimization. The core innovation is the Sifrian (named after the Arabic word Sifr, meaning zero), a novel second-order Lagrangian framework that provides an exact formula for the Newton direction.

Key Technical Components

  • Exact Stochastic Solution: In the stochastic case (batch size = 1), the complex system of equations generated by the Sifrian simplifies significantly, particularly when using piecewise linear activations like Leaky ReLU. This allows for a closed-form expression for the Newton direction.
  • The MK Solution: To address non-convexity, the authors adjust the Newton direction to ensure it is always a descent direction, effectively "flipping" the signs of directions that would lead toward saddle points.
  • Spectral Adjustment: By deriving the exact eigenvalues of the stochastic Hessian, the authors can analytically tune regularization parameters to minimize the "Hessian radius," mathematically pushing the model toward flatter minima.
A standard Feed-Forward Network (FNN) architecture with various activation functions, representing the testbed for the Sifrian framework.

Experimental Results

The authors validated their approach using MNIST and Fashion-MNIST benchmarks on a Feed-Forward Network (FNN) with three hidden layers.

Key Insights

  • Efficiency: Because the solution is closed-form, it avoids the "Hessian-free" trap of requiring dozens of extra forward/backward passes to estimate curvature. It utilizes the Sherman-Morrison identity for numerical stability without heavy matrix inversions.
  • Convergence: In both MNIST and Fashion-MNIST tests, the MK (second-order) method converged significantly faster than standard Stochastic Gradient Descent (SGD) in terms of the number of epochs.
  • Stability: The damped version of their solution maintained high accuracy and validation scores without the need for extensive hyperparameter fine-tuning.

Conclusion and Future Work

This work represents a major theoretical step by providing an exact solution for the stochastic case. While currently limited to a batch size of one and Feed-Forward architectures, the authors suggest that extending this to multi-pattern batches and more complex architectures like CNNs or RNNs is the immediate next step. The Sifrian framework may even pave the way for "Halley Deep Learning," extending optimization to third-order and beyond.

Summary updated

Abstract

Optimization in Deep Learning is mainly dominated by first-order methods which are built around the central concept of backpropagation. Second-order optimization methods, which take into account the second-order derivatives are far less used despite superior theoretical properties. This inadequacy of second-order methods stems from its exorbitant computational cost, poor performance, and the ineluctable non-convex nature of Deep Learning. Several attempts were made to resolve the inadequacy of second-order optimization without reaching a cost-effective solution, much less an exact solution. In this work, we show that this long-standing problem in Deep Learning could be solved in the stochastic case, given a suitable regularization of the neural network. Interestingly, we provide an expression of the stochastic Hessian and its exact eigenvalues. We provide a closed-form formula for the exact stochastic second-order Newton direction, we solve the non-convexity issue and adjust our exact solution to favor flat minima through regularization and spectral adjustment. We test our exact stochastic second-order method on popular datasets and reveal its adequacy for Deep Learning.
BibTeX
@misc{mehouachi2021exact,
  author = {Fares B. Mehouachi and Chaouki Kasmi},
  title = {{Exact Stochastic Second Order Deep Learning}},
  year = {2021},
  eprint = {2104.03804},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2104.03804},
}
Figure