Distributed Hessian-Free Optimization for Deep Neural Network

Xi He, Dheevatsa Mudigere, Mikhail Smelyanskiy, Martin TakácWorkshops @ AAAI 2017 · OpenReview

TL;DR

This paper introduces a distributed Hessian-Free (HF) optimization algorithm for deep neural networks that significantly improves training speed and scalability compared to traditional Stochastic Gradient Descent (SGD). By leveraging negative curvature detection and efficient distributed computation, their method achieves better performance and faster convergence, especially on large datasets and with large batch sizes.

What Problem Does This Paper Address?

Training deep neural networks (DNNs) is notoriously challenging due to the high dimensionality and non-convexity of the optimization landscape. While Stochastic Gradient Descent (SGD) is widely used, it suffers from slow convergence and limited scalability, especially with large datasets, as it's inherently sequential. Second-order optimization methods, like Hessian-Free (HF), offer more substantial weight updates and can potentially leverage larger batch sizes for better parallelism. However, traditional HF methods can be computationally expensive and struggle with the non-convexity of DNNs, often encountering saddle points that slow down training. This paper aims to bridge this gap by developing a distributed HF algorithm that is both efficient and robust, capable of exploiting modern parallel computing resources.

Methods

The core of this paper is the development of a distributed Hessian-Free (HF) optimization algorithm. Building upon the established Hessian-Free optimization framework (Algorithm 1), the authors propose a distributed variant (Algorithm 2) that utilizes data parallelism. This means the data is split across multiple computing nodes, while each node holds a copy of the model weights.

Key novelties and improvements include:

  • Negative Curvature Direction Detection: Unlike some HF methods that ignore negative curvature (which can lead to saddle points), this work explicitly incorporates a mechanism to detect and utilize it. They propose using Bi-Conjugate Gradient Stabilized (Bi-CG-STAB), a Krylov subspace method capable of solving indefinite systems, to find descent directions that can escape saddle points. This is a departure from methods that rely on approximations like Gauss-Newton, which can lose crucial curvature information.
  • Distributed Implementation: The algorithm is designed for distributed environments, allowing for efficient scaling across multiple nodes. They leverage data parallelism, where gradients and Hessian-vector products are computed locally on each node and then reduced to a central node.
  • Hybrid Approach: For dealing with negative curvature, they propose a hybrid strategy. When a negative curvature direction is detected, they switch to using it. Otherwise, they proceed with a more standard Newton-like step. This is intended to balance the benefits of exact Hessian information with the need for a valid descent direction.

Datasets

The paper evaluates their proposed methods on two standard datasets:

  • MNIST: A widely used dataset for handwritten digit recognition.
  • TIMIT: A dataset for speech recognition.

The authors emphasize that they do not use any data distortions or pre-training, focusing purely on the scaling and stability of the optimization algorithms themselves.

Key Insights and Ideas

  • Negative Curvature is Crucial for DNNs: The paper strongly advocates for the importance of explicitly handling negative curvature in non-convex optimization for DNNs. Ignoring it can lead to significant slowdowns around saddle points, a common issue in deep learning.
  • Bi-CG-STAB for Indefinite Systems: Using Bi-CG-STAB is a clever way to handle the potentially indefinite Hessian matrices encountered in DNN optimization, allowing for more accurate curvature information compared to approximations.
  • Distributed HF Scales Better than SGD: The core message is that distributed HF methods, by their nature, can exploit parallelism more effectively than sequential SGD, especially with large batch sizes. This leads to better scaling with the number of computing nodes.
  • Large Batch Sizes Benefit Second-Order Methods: While large batch sizes can sometimes hurt SGD by reducing the number of updates, they significantly improve the accuracy of the stochastic Hessian approximation for second-order methods, leading to faster convergence.

Key Results

  • Improved Training Performance: The proposed distributed HF algorithm, particularly the variant using Bi-CG-STAB and negative curvature detection, consistently outperforms standard SGD and other Hessian-free variants in terms of convergence speed and final error on both MNIST and TIMIT datasets.
  • Scalability: The distributed HF method demonstrates near-linear speed-up on up to 32 CPU nodes for a simple 4-layer network, showcasing its ability to effectively utilize larger computing resources.
  • Robustness with Large Batches: The method shows stable and improved performance with significantly larger batch sizes, a key advantage over SGD which can degrade.
  • Faster Convergence: Experiments show that the HF variants, especially their proposed method, achieve better and more stable scaling performance in terms of both the number of nodes and the size of the mini-batch.

Limitations and Future Work

  • Communication Bottleneck: While the paper highlights the scaling benefits of distributed HF, it also acknowledges that communication can become a bottleneck, particularly for the gradient computation and line search components. The time for CG iterations also increases with more nodes due to communication overhead.
  • Characterizing Compute vs. Communication: The authors state that a next step is to perform a more comprehensive characterization of the compute and bottleneck analysis for both single and multi-node performance.
  • Further Optimization of HF-CG: The paper mentions that HF-CG can be unstable and suggests further investigation into techniques to improve its stability and convergence.
  • Exploiting NUMA Architectures: While experiments are conducted on multi-socket nodes, the paper hints at further opportunities to exploit non-uniform memory architectures (NUMA) more effectively.

Summary updated

BibTeX
@inproceedings{he2017distributed,
  author = {Xi He and Dheevatsa Mudigere and Mikhail Smelyanskiy and Martin Takác},
  title = {{Distributed Hessian-Free Optimization for Deep Neural Network}},
  booktitle = {Workshops @ AAAI},
  year = {2017},
  url = {https://openreview.net/forum?id=BdMDCJbgEJp},
}
Figure