Reducing Communication Overhead in Distributed Machine Learning

42 concepts42 papers1 proposal

When training large-scale machine learning models, data and parameters must be distributed across multiple computing nodes. However, a severe bottleneck emerges: the time required to synchronize high-dimensional gradient vectors or model parameters across the network frequently dwarfs the time spent on local computation (Mousavi Kalan et al.).

In standard parallel stochastic gradient descent (SGD), workers must exchange data after every single local step. As the number of devices scales or network bandwidth becomes constrained, this high-frequency synchronization forces processors to spend more time "talking" than "thinking" (Shao et al.; Shen et al.). To overcome this distributed communication bottleneck, researchers have developed several distinct strategies to minimize network traffic while preserving convergence guarantees.

Local Updates: Decreasing Synchronization Frequency

The most intuitive way to reduce communication is simply to communicate less often. Instead of synchronizing after every gradient step, workers train independently on their local data for multiple steps before performing a global synchronization round. This approach is known as Local SGD.

Stich demonstrated that Local SGD achieves the same "linear speedup" as standard mini-batch SGD while requiring up to a factor of $\sqrt{T}$ fewer communication rounds (Local SGD Converges Fast and Communicates Little). To optimize this further, Shen et al. proposed a stagewise communication period (STL-SGD) that gradually increases the time between synchronizations as the learning rate decays. Similarly, Dieuleveut et al. showed that using large, decaying step sizes allows for a significant reduction in communication frequency without sacrificing accuracy.

Why does this work mathematically? For modern over-parameterized models that can perfectly fit the data via interpolation, Qin et al. proved that performing multiple local steps accelerates convergence even under high data heterogeneity. Furthermore, this local step paradigm can be extended beyond basic SGD. For instance, Chezhegov et al. integrated local steps with adaptive optimizers like Adam in their SAVIC framework, while Cheng et al. provided theoretical convergence proofs for Local SGDM and Local Adam using a novel contraction analysis technique. To bypass restrictive data similarity assumptions entirely, Mishchenko et al. introduced ProxSkip, a randomized algorithm that skips expensive proximal operators to achieve optimal communication complexity.

Gradient Compression and Quantization: Smarter Messages

If reducing the frequency of communication is one side of the coin, reducing the size of each message is the other. When models scale to billions of parameters, transmitting full 32-bit gradient vectors creates an immense bottleneck (Beznosikov et al.; He et al.).

Communication compression slashes the data volume sent over the wire through quantization and sparsification. For example, Kamilov et al. developed signProx, which compresses stochastic gradient updates down to a single bit (just the sign) while maintaining robust convergence. Taking a probabilistic approach, Mordido et al. introduced Monte Carlo Gradient Quantization (MCGQ), which uses importance sampling to simultaneously quantize and sparsify gradients based on their magnitudes, achieving massive compression ratios.

Recent methods also recognize that neural network layers are heterogeneous. Nguyen et al. proposed QODA, which applies layer-wise adaptive quantization combined with optimistic dual averaging to accelerate training. To minimize the bits transmitted even further, He et al. introduced CORE, a technique that leverages shared randomness to project high-dimensional gradients into low-dimensional spaces, provably reducing communication complexity from $O(d)$ bits to $O(1)$ when the effective dimension is small.

Curvature-Aware Optimization: Higher-Quality Steps

First-order gradient methods often require thousands of synchronization rounds because gradients only provide local directional information. By contrast, leveraging second-order curvature information allows algorithms to take much smarter, more effective steps, drastically reducing the total number of communication rounds required to converge.

Srebro et al. demonstrated this with DANE (Distributed Approximate NEwton), which uses local intelligence to solve subproblems and reduce synchronization frequency. Similarly, Bullins et al. introduced FEDSN (Federated Stochastic Newton), which treats general convex problems as a sequence of quadratic subproblems solved via one-shot averaging, outperforming first-order methods when communication is infrequent.

This principle applies to non-convex and constrained settings as well. Liu et al. developed DINPS for non-convex sparse learning, utilizing an inexact Newton-type pursuit to minimize communication rounds. Furthermore, Beznosikov et al. showed that second-order curvature (Hessian similarity) can be successfully synergized with communication compression and Nesterov-style acceleration in their OLGA and EF-OLGA frameworks to achieve record-breaking communication complexity.

Dynamic Batching and Asynchronous Execution

Beyond modifying the steps or compressing the vectors, the structural scheduling of training can be altered to mitigate the bottleneck.

One approach is to dynamically scale the workload per communication round. Yu et al. proved that by growing batch sizes exponentially during training, Parallel SGD can maintain its linear speedup while slashing the total number of communication rounds to a logarithmic scale.

Another approach is to abandon rigid synchronization entirely. In synchronous systems, the entire cluster must wait for the slowest machine (the straggler). As shown in Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD, allowing asynchronous updates with "stale" (outdated) gradients can significantly optimize total wall-clock time by avoiding straggler effects, shifting the optimization focus from error-per-iteration to error-per-second.

Key Foundational Work

Asymptotically Exact, Embarrassingly Parallel MCMC (2013) — contributed 1 concept elements to this direction.
Distributed Training Strategies for the Structured Perceptron (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_distributed_communication_bottleneck_gra_6f0cd40a,
  title = {distributed communication bottleneck (gradient synchronization overhead)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-communication-bottleneck-gradient-synchronization-overhead/rdr_6f0cd40ab78049cc9e5f54b87f9cc2ea},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_distributed_communication_bottleneck_gra_6f0cd40a_v1,
  title = {distributed communication bottleneck (gradient synchronization overhead)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-communication-bottleneck-gradient-synchronization-overhead/rdr_6f0cd40ab78049cc9e5f54b87f9cc2ea/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake