Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1

Majid Jahani, MohammadReza Nazari, Sergey Rusakov, Albert S. Berahas, Martin TakácLOD 2020 · OpenReview

TL;DR

This paper introduces DS-LSR1, a communication-efficient distributed algorithm for training large-scale machine learning models using quasi-Newton methods. By significantly reducing communication overhead and improving workload balancing, DS-LSR1 achieves near-linear speedups in distributed settings, making it a more practical choice for modern deep learning tasks.

What Problem Does This Paper Address?

Training large-scale machine learning models, especially deep neural networks, often involves massive datasets and high-dimensional parameter spaces. While distributed computing offers a solution, traditional optimization methods like Stochastic Gradient Descent (SGD) can become communication-bound in distributed settings. This is because they often use small mini-batches, leading to frequent communication of gradients between nodes, which can outweigh the computational gains. Quasi-Newton methods, which leverage curvature information, can potentially mitigate this by using larger batches and performing more computation per iteration. However, implementing these methods in a distributed fashion efficiently has been a challenge. Specifically, the Symmetric Rank-1 (SR1) method, a type of quasi-Newton method, has shown promise due to its ability to handle negative curvature and escape saddle points, but its naive distributed implementation suffers from excessive communication. This paper aims to bridge this gap by developing a communication-efficient distributed SR1 variant.

Methods

The core contribution of this paper is the DS-LSR1 (Distributed Sampled Limited-memory Symmetric Rank-1) algorithm. It's built upon the Sampled Limited-memory SR1 (S-LSR1) method but addresses its inefficiencies in a distributed setting. Key methodological aspects include:

  • Master-Worker Framework: The algorithm operates in a standard master-worker setup, where worker nodes perform local computations and the master node orchestrates the process.
  • Communication Efficiency: DS-LSR1 drastically reduces the amount of data communicated. Instead of sending full curvature pairs (which are vectors of dimension $d$), it communicates inner products of these pairs (e.g., $S^T Y$, $S^T S$, $Y^T Y$). This reduces communication from $O(md)$ to $O(m^2)$, where $m$ is the memory parameter of the SR1 method.
  • Matrix-Free and Inverse-Free: The method avoids explicitly forming or inverting Hessian approximation matrices. It leverages the compact representation of SR1 updates and uses sketching techniques to approximate necessary quantities without explicit matrix operations.
  • Workload Balancing: The heavy computations are offloaded to the worker nodes, while the master node primarily handles simple aggregations. This ensures a more balanced workload across all nodes, crucial for scalability.
  • Sketching for Approximations: To further reduce communication and computation, especially for checking the SR1 curvature pair condition, the paper employs sketching techniques. This allows for approximations of quantities like $Y^T Y$ without additional communication.

Datasets

The paper uses standard datasets for evaluation:

  • MNIST: Used for shallow and deep network experiments in weak scaling.
  • CIFAR10: Used for strong scaling experiments and performance evaluation on a neural network training task.

Key Insights and Ideas

  • Communication is the Bottleneck: The paper strongly emphasizes that for many distributed optimization algorithms in machine learning, communication overhead, not computation, is the primary bottleneck. This insight drives the design of DS-LSR1.
  • Inner Products as Communication Primitives: Realizing that inner products of curvature pairs are sufficient for many SR1 update steps and conditions is a key insight that enables significant communication reduction.
  • Sketching for Efficiency: The use of sketching techniques to approximate matrix quantities like $Y^T Y$ is a clever way to avoid expensive computations and communications, especially when exact values are not strictly necessary (e.g., for the SR1 condition check).
  • Workload Balancing is Crucial for Speedup: The paper demonstrates that by distributing computation more evenly, DS-LSR1 achieves better scaling than a naive distributed approach where the master node becomes a bottleneck.

Key Results

  • Near-Linear Speedup: DS-LSR1 achieves near-linear speedup as the number of nodes increases in strong scaling experiments. This is significantly better than the naive approach, which is limited by Amdahl's Law due to unbalanced workload.
  • Reduced Communication: DS-LSR1 reduces communication from $O(md)$ to $O(m^2)$ per iteration compared to a naive distributed implementation. For a VGG11 network with $d=9.2M$ and $m=256$, DS-LSR1 communicates 0.0688 GB per iteration, while the naive approach communicates 8.8081 GB.
  • Comparable Accuracy: The paper shows that DS-LSR1 achieves comparable training and testing accuracy to the naive approach, indicating that the communication reduction does not come at the cost of model performance.
  • Efficient Components: Figure 6 and Figure 13 show that DS-LSR1's components (reduce time, CG time, S-Y sampling time) scale favorably with memory size, often outperforming the naive approach.

Limitations and Future Work

  • Approximation in SR1 Condition: While sketching is used for efficiency, it's noted that this approximation is applied when checking the SR1 condition (2.4), which is stated to be less sensitive to approximation errors. However, the paper doesn't deeply explore the theoretical implications of this approximation on convergence guarantees.
  • Hyperparameter Tuning: Like many optimization algorithms, DS-LSR1 likely still requires careful tuning of hyperparameters (e.g., trust region parameters, memory size $m$).
  • Extension to Other Quasi-Newton Methods: The techniques developed for DS-LSR1 could potentially be extended to other quasi-Newton methods, which could be a fruitful area for future research.
  • Further Communication Reduction: While significant, the paper hints at further potential reductions in communication, suggesting ongoing research in this area.

Summary updated

BibTeX
@inproceedings{jahani2020scaling,
  author = {Majid Jahani and MohammadReza Nazari and Sergey Rusakov and Albert S. Berahas and Martin Takác},
  title = {{Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1}},
  booktitle = {LOD},
  year = {2020},
  url = {https://openreview.net/forum?id=6dQY0mwQLhz},
}
Figure