Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models

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

Introduction

Training massive deep learning models requires distributed computing, but keeping multiple "workers" (GPUs/CPUs) in sync is difficult. Standard approaches like DOWNPOUR or Horovod require frequent communication, which creates a bottleneck.

A popular alternative, Elastic Averaging SGD (EASGD), allows workers to drift apart and periodically pulls them toward a central average. However, EASGD has a major flaw: the "curse of symmetry." In the complex, non-convex landscapes of neural networks, different workers might fall into different, equally good local minima. Pulling them toward their average can drag them into a high-error region between those minima, slowing down convergence or leading to poor generalization. Furthermore, EASGD changes the objective function's stationary points, meaning it might converge to a solution that isn't actually a minimum of the original problem.

To address these issues, this paper introduces Leader Stochastic Gradient Descent (LSGD), a distributed optimization algorithm that pulls workers toward the current best-performing "leader" rather than the global average of all workers.

Methods

Instead of pulling workers toward a mean, LSGD identifies the worker with the lowest loss—the Leader—and pulls all other workers toward that leader's parameters.

Key technical components include:

  • The Update Rule: A worker's update consists of a standard gradient step plus a "corrective force" (an elastic pull) toward the leader.
  • Multi-Leader Extension: To match modern hardware (where communication within a server node is faster than between nodes), the authors implement a hierarchy. Workers are attracted to a local leader (best in the node) and a global leader (best in the cluster).
  • Asynchronous Operation: Workers don't wait for each other. Communication happens based on a total iteration counter, making the system robust to "stragglers" (slow workers).
  • Communication Efficiency: LSGD only needs to broadcast the leader's parameters, whereas averaging schemes often require aggregating data from every single worker.

Key Insights

  • Breaking the Curse of Symmetry: By following a leader rather than an average, the algorithm "picks a winner." If two workers are in different valleys, LSGD moves everyone toward the better valley rather than getting stuck on the ridge between them.
  • Preserving Stationary Points: Unlike EASGD, the authors prove that LSGD does not shift the location of the original problem's stationary points. If the leader is at a true minimum, the corrective force vanishes.
  • Exploration of "Wide Valleys": Like other elastic methods, LSGD tends to find "flat" or "wide" minima. In deep learning folklore, these regions are associated with better generalization on unseen data.
  • Hardware Alignment: The multi-leader approach mirrors the physical reality of GPU clusters, minimizing expensive across-node traffic in favor of faster local-node communication.

Experimental Results

The authors evaluated LSGD across several benchmarks, including synthetic Matrix Completion, CIFAR-10 (CNN7, VGG16, ResNet20), and ImageNet (ResNet50).

  • Robustness in Non-Convex Landscapes: In matrix completion tasks, LSGD reached high precision ($10^{-7}$ error) while EAGD plateaued much earlier. This is because the "pull" of the average in EAGD drags workers away from the true solution.
Matrix Completion Performance
  • Faster Convergence: On CIFAR-10 with 16 workers, LSGD was roughly 1.5x to 2x faster than EASGD to reach the same error level.
  • Better Accuracy: LSGD consistently achieved lower final test errors than both EASGD and DOWNPOUR across the tested architectures.
Training Error vs Time for 4 and 16 Workers
  • Scalability: On ImageNet with ResNet50, LSGD behaved comparably to EASGD but significantly outperformed DOWNPOUR in terms of convergence speed.

Limitations and Future Work

  • Stale Leaders: In highly asynchronous environments, the "leader" might be identified based on old information. The authors mitigate this by only applying the leader-pull step immediately after a communication sync, but more sophisticated "staleness-aware" pulls could be explored.
  • Hyperparameter Sensitivity: The algorithm introduces new hyperparameters, such as the pull strength ($\lambda$) and communication periods ($\tau$). While the authors provide some theoretical bounds, practical tuning is still required.
  • Leader Selection Cost: Finding the leader requires comparing losses across workers. While this is cheaper than averaging parameters, it still adds a small overhead that could be optimized in massive-scale deployments.

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.
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