Towards Optimal Communication Complexity in Distributed Non-Convex Optimization

Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, Nathan SrebroNeurIPS 2022 · OpenReview

Introduction

In distributed machine learning paradigms like Federated Learning, moving data between a central server and thousands of edge devices is the primary bottleneck. To save time and bandwidth, researchers rely on "intermittent communication," where devices perform many local updates (e.g., $K$ steps) before syncing their models with the central server.

While intermittent communication saves bandwidth, it introduces a core challenge: heterogeneity. If every device holds vastly different data, local updates can lead the model astray—a phenomenon known as client drift. While many algorithms exist to correct this drift, it has remained unclear if they actually perform better than simple "centralized" mini-batch methods in non-convex settings (like training deep neural networks). This paper seeks to find the optimal balance: the absolute minimum number of communication rounds needed to reach a target accuracy, given the degree of difference between the clients' local functions.

Proposed Method: CE-LSGD

The authors propose CE-LSGD (Communication Efficient Local Stochastic Gradient Descent), an algorithm designed to achieve near-optimal communication complexity. Its key features include:

  • Lighter Variance Reduction: CE-LSGD uses a SARAH/STORM-style momentum approach to reduce the noise in gradient estimates. Unlike previous state-of-the-art methods (such as BVR-L-SGD), CE-LSGD requires fewer "heavy-batch" operations—computing gradients on very large chunks of data—making it significantly more computationally efficient for edge devices.
  • Two-Round Syncing: Each iteration involves two rounds of communication to carefully update the variance-reduction term using both current and previous model states.
  • Heterogeneity Modeling: The theoretical analysis explicitly accounts for "first-order" ($\zeta$) and "second-order" ($\tau$) heterogeneity, which measure how much the gradients and curvatures differ across machines.
  • New Lower Bounds: Beyond proposing an algorithm, the authors establish mathematical lower bounds, proving that for many scenarios, no algorithm can achieve significantly better communication complexity.

Theoretical and Empirical Results

Theoretical Dominance

The paper demonstrates that CE-LSGD matches or improves upon the convergence rates of all previous methods in both "full participation" (all devices active) and "partial participation" (only a subset of devices active) settings.

Comparison of convergence rates for various distributed optimization methods.

The authors identified that CE-LSGD is min-max optimal when using exact gradients. It achieves a communication complexity of roughly $O(\Delta \tau / \epsilon)$ in the deterministic case, which they prove is the best possible rate. In the stochastic (noisy) setting, it remains near-optimal, filling a significant gap in the theoretical understanding of non-convex distributed optimization.

Empirical Speedup

To validate their theoretical findings, the researchers evaluated CE-LSGD on the CIFAR-10 image classification dataset. To simulate real-world federated learning, they partitioned CIFAR-10 so that each client primarily held specific classes, allowing them to test varying levels of "non-IID" data.

Training loss versus communication rounds for CE-LSGD and BVR-LSGD.

In these experiments, CE-LSGD converged significantly faster than baselines like BVR-L-SGD, FedAvg, and SCAFFOLD. It consistently reached lower training losses in fewer communication rounds across various levels of data heterogeneity and local update steps ($K=64$ and $K=1024$). The results underscore that when heterogeneity is low, local-update methods like CE-LSGD provide a massive speedup in communication over centralized baselines.

Limitations and Future Directions

While CE-LSGD pushes the boundary of distributed optimization, a few open questions remain:

  • The Stochastic Gap: There is still a small gap (a factor of $1/\sqrt{K}$) between the algorithm's performance and the theoretical lower bound in the stochastic setting. The authors suggest this might be an artifact of the analysis rather than a fundamental flaw in the algorithm.
  • Partial Participation Bounds: The lower bounds for the partial participation setting are likely "loose." The true optimal rate likely involves a specific interaction between heterogeneity and the number of participating clients that hasn't been fully captured yet.
  • Hessian-Free Variant: The authors propose a variant using stochastic Hessian-vector products to save memory, but more extensive empirical testing on massive-scale models is needed to fully validate its practical utility.

Summary updated

Abstract

We study the problem of distributed stochastic non-convex optimization with intermittent communication. We consider the full participation setting where $M$ machines work in parallel over $R$ communication rounds and the partial participation setting where $M$ machines are sampled independently every round from some meta-distribution over machines. We propose and analyze a new algorithm that improves existing methods by requiring fewer and lighter variance reduction operations. We also present lower bounds, showing our algorithm is either $\textit{optimal}$ or $\textit{almost optimal}$ in most settings. Numerical experiments demonstrate the superior performance of our algorithm.
BibTeX
@inproceedings{patel2022towards,
  author = {Kumar Kshitij Patel and Lingxiao Wang and Blake Woodworth and Brian Bullins and Nathan Srebro},
  title = {{Towards Optimal Communication Complexity in Distributed Non-Convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=SNElc7QmMDe},
}
Figure