Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models

Yunfei Teng, Wenbo Gao, François Chalus, Anna Choromanska, Donald Goldfarb, Adrian Weller

Abstract

We consider distributed optimization under communication constraints for training deep learning models. We propose a new algorithm, Leader Stochastic Gradient Descent (LSGD), whose parameter updates rely on two forces: a regular gradient step and a corrective direction dictated by the currently best-performing worker (the leader). Unlike parameter-averaging schemes like EASGD, LSGD preserves the original problem's stationary points, avoids convergence deceleration caused by averaging workers in different local minima, and breaks the "curse of symmetry." Our approach is more communication-efficient as it broadcasts only the leader's parameters. We provide theoretical analysis and demonstrate that LSGD compares favorably to state-of-the-art baselines for training convolutional neural networks.

Introduction

Training massive deep learning models requires distributing workloads across multiple GPUs or nodes. However, synchronization remains a major bottleneck. Standard approaches like DataParallel require frequent, high-bandwidth communication. Elastic Averaging SGD (EASGD) mitigates this by allowing workers to drift and periodically pulling them toward a central average. Yet, EASGD faces critical flaws: it can be trapped in poor regions due to the "curse of symmetry," shifts the optimization objective, and requires significant communication overhead to compute averages.

The LSGD Approach

LSGD shifts the paradigm from "consensus by averaging" to "following the best." Each worker's update consists of a standard gradient step plus a corrective direction toward the leader—the worker with the lowest training loss.

Symmetry Breaking and Efficiency

In complex, non-convex landscapes, averaging parameters from workers heading toward different minima can trap the model in high-loss saddle points. By following a specific successful individual, LSGD forces the group to "pick a side," effectively escaping these traps. This is illustrated in matrix completion tasks where standard averaging methods plateau prematurely.

Matrix completion performance comparing LGD and EAGD.

Key Insights

  • Newton-like Directions: Theoretical analysis suggests that pulling toward a leader makes the search direction behave similarly to a second-order Newton method, allowing for more efficient paths through the loss landscape.
  • Multi-Leader Hierarchy: To align with hardware architectures, LSGD can be implemented hierarchically. Workers within a node follow a local leader, while local leaders follow a global leader, optimizing communication across different network tiers.
  • Preserving the Objective: LSGD does not change the stationary points of the original loss function, ensuring that the distributed system optimizes the intended problem.

Empirical Results

Evaluations on CIFAR-10 and ImageNet demonstrate LSGD's superior performance. On a CNN7 architecture with 12 workers, LSGD converged approximately 1.5x faster than EASGD and achieved lower final test errors than DataParallel and LARS.

CIFAR-10 training results for CNN7 across different worker counts.

Limitations

While effective, LSGD introduces hyperparameters such as the "pull strength" ($\lambda$) and communication intervals ($\tau$) that require tuning. Additionally, in asynchronous settings, workers might be pulled toward a "stale" leader if communication is too infrequent. Future work aims to provide more formal non-convex convergence proofs to complement the current empirical and convex theoretical foundations.

The authors have released a PyTorch-based library for LSGD at: https://github.com/yunfei-teng/LSGD.

Summary updated

Abstract

We consider distributed optimization under communication constraints for training deep learning models. We propose a new algorithm, whose parameter updates rely on two forces: a regular gradient step, and a corrective direction dictated by the currently best-performing worker (leader). Our method differs from the parameter-averaging scheme EASGD in a number of ways: (i) our objective formulation does not change the location of stationary points compared to the original optimization problem; (ii) we avoid convergence decelerations caused by pulling local workers descending to different local minima to each other (i.e. to the average of their parameters); (iii) our update by design breaks the curse of symmetry (the phenomenon of being trapped in poorly generalizing sub-optimal solutions in symmetric non-convex landscapes); and (iv) our approach is more communication efficient since it broadcasts only parameters of the leader rather than all workers. We provide theoretical analysis of the batch version of the proposed algorithm, which we call Leader Gradient Descent (LGD), and its stochastic variant (LSGD). Finally, we implement an asynchronous version of our algorithm and extend it to the multi-leader setting, where we form groups of workers, each represented by its own local leader (the best performer in a group), and update each worker with a corrective direction comprised of two attractive forces: one to the local, and one to the global leader (the best performer among all workers). The multi-leader setting is well-aligned with current hardware architecture, where local workers forming a group lie within a single computational node and different groups correspond to different nodes. For training convolutional neural networks, we empirically demonstrate that our approach compares favorably to state-of-the-art baselines. This work is a gentle extension of [2].
BibTeX
@inproceedings{teng2019leader,
  author = {Yunfei Teng and Wenbo Gao and François Chalus and Anna Choromanska and Donald Goldfarb and Adrian Weller},
  title = {{Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=1m_b_hTqxm},
}
Figure