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