Large Scale Distributed Hessian-Free Optimization for Deep Neural Network

Xi He, Dheevatsa Mudigere, Mikhail Smelyanskiy, Martin TakácarXiv 2016 · arXiv · OpenReview

TL;DR

This paper introduces a distributed Hessian-free optimization method for deep neural networks that significantly outperforms traditional Stochastic Gradient Descent (SGD) in terms of scalability and convergence speed, especially for large datasets and models. By effectively handling negative curvature and leveraging distributed computing, it achieves near-linear speedups and better solutions.

What Problem Does This Paper Address?

Training deep neural networks (DNNs) is notoriously challenging due to the high dimensionality and non-convex nature of the optimization problem. While Stochastic Gradient Descent (SGD) and its variants are widely used, they can slow down considerably near saddle points. Second-order optimization methods, which consider the curvature of the loss landscape, offer a way to escape these plateaus more effectively. However, applying these methods to large-scale DNNs is computationally expensive. This paper aims to bridge this gap by developing a distributed Hessian-free optimization approach that is both scalable and capable of exploiting curvature information to accelerate training and improve solution quality.

Methods

The core of this work is a distributed variant of the Hessian-free (HF) optimization method. Traditional HF methods, like those proposed by Martens (2010), use approximations of the Hessian (like Gauss-Newton) or ignore negative curvature information, which can hinder convergence. This paper introduces two key improvements:

  • Negative Curvature Detection with BI-CG-STAB: Instead of ignoring negative curvature, the authors propose using the stabilized bi-conjugate gradient (BI-CG-STAB) method. This allows them to work with potentially indefinite stochastic Hessian approximations and explicitly detect and utilize negative curvature directions. This is crucial for escaping saddle points more efficiently.
  • Distributed Data Parallelism: The HF method is adapted for distributed environments using data parallelism. This means the dataset is split across multiple computing nodes, and each node processes a subset of the data. Gradients and Hessian-vector products are computed locally and then aggregated. This approach is shown to scale much better than SGD, which is inherently sequential and struggles with large batch sizes.

The paper also discusses two strategies for parallelizing DNN training: model parallelism (splitting model weights) and data parallelism (splitting data). They opt for data parallelism for their distributed HF method.

Datasets

The proposed methods were evaluated on two standard datasets:

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

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

Key Insights and Ideas

  • Negative curvature is not just a nuisance; it's an opportunity: By actively detecting and using negative curvature directions, optimization algorithms can escape saddle points more effectively and potentially find better solutions, rather than just avoiding them.
  • Hessian-free methods are inherently more scalable than SGD for large batches: While SGD's sequential nature limits its benefit from large batch sizes, Hessian-free methods can naturally leverage parallelism, leading to better scaling and faster convergence on distributed systems.
  • Communication is the bottleneck, not just computation: For distributed training, the cost of communication between nodes can become a significant limiting factor. The paper highlights how their distributed HF method, with fewer synchronization points than SGD, can mitigate this.
  • BI-CG-STAB is a powerful tool for non-convex optimization: Its ability to handle indefinite systems makes it suitable for using more accurate (though potentially indefinite) Hessian approximations in practice.

Key Results

  • Superior Scaling: The distributed Hessian-free method demonstrated near-linear speed-up on up to 32 CPU nodes for a simple 4-layer network, significantly outperforming SGD in terms of scaling.
  • Faster Convergence: The method accelerated training for both MNIST and TIMIT datasets, achieving robust performance with much larger batch sizes compared to SGD.
  • Improved Solution Quality: While not quantified with specific accuracy numbers, the paper suggests that the ability to escape saddle points and use curvature information leads to better final solutions.
  • Efficiency with Large Batches: The proposed HF variants showed better performance as batch sizes increased, indicating their suitability for modern large-scale distributed training setups.

Limitations and Future Work

  • Large Batch SGD Limitations: The paper notes that while large batches can reduce communication for SGD, they also slow down convergence. Addressing this trade-off in large-batch SGD is an ongoing area of research.
  • Characterizing Compute vs. Communication Bottlenecks: The authors acknowledge the need for more comprehensive analysis of compute and communication bottlenecks in both single and multi-node performance.
  • Further Exploration of Hybrid Approaches: The paper mentions a "Hybrid-CG" method that alternates between Hessian-free and Gauss-Newton approximations, suggesting that exploring such hybrid strategies could be a fruitful direction.
  • More Comprehensive Analysis: The authors plan to conduct more detailed characterizations of compute and communication bottlenecks.

Summary updated

Abstract

Training deep neural network is a high dimensional and a highly non-convex optimization problem. Stochastic gradient descent (SGD) algorithm and it's variations are the current state-of-the-art solvers for this task. However, due to non-covexity nature of the problem, it was observed that SGD slows down near saddle point. Recent empirical work claim that by detecting and escaping saddle point efficiently, it's more likely to improve training performance. With this objective, we revisit Hessian-free optimization method for deep networks. We also develop its distributed variant and demonstrate superior scaling potential to SGD, which allows more efficiently utilizing larger computing resources thus enabling large models and faster time to obtain desired solution. Furthermore, unlike truncated Newton method (Marten's HF) that ignores negative curvature information by using na\"ive conjugate gradient method and Gauss-Newton Hessian approximation information - we propose a novel algorithm to explore negative curvature direction by solving the sub-problem with stabilized bi-conjugate method involving possible indefinite stochastic Hessian information. We show that these techniques accelerate the training process for both the standard MNIST dataset and also the TIMIT speech recognition problem, demonstrating robust performance with upto an order of magnitude larger batch sizes. This increased scaling potential is illustrated with near linear speed-up on upto 16 CPU nodes for a simple 4-layer network.
BibTeX
@misc{he2016large,
  author = {Xi He and Dheevatsa Mudigere and Mikhail Smelyanskiy and Martin Takác},
  title = {{Large Scale Distributed Hessian-Free Optimization for Deep Neural Network}},
  year = {2016},
  eprint = {1606.00511},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.00511},
}
Figure