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