Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning

Tehila Dahan Technion Haifa, Israel Bassel Hamoud Technion Haifa, Israel Roie Reshef Technion Haifa, Israel Martin Jaggi EPFL Lausanne, Switzerland Kfir Y. Levy Technion Haifa, Israel · 2026

Read Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning by Tehila Dahan Technion Haifa, Israel Bassel Hamoud Technion Haifa, Israel Roie Reshef Technion Haifa, Israel Martin Jaggi EPFL Lausanne, Switzerland Kfir Y. Levy Technion Haifa, Israel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01128.txt.

Introduction

Dahan and co-authors break a scaling law in distributed learning in this 2026 paper. Training across many workers saves time, but communication rounds pile up. Known methods, from local SGD to minibatch variants, need rounds that grow with the total sample count. That tie binds big datasets to heavy network traffic.

Their framework, Local MixVR, mixes local updates with variance reduction to tame local noise. It is the first method whose communication cost drops the sample count out, they prove. The cost scales only with the number of workers. Where workers are few against the data size, it beats the top minibatch accelerated baseline. The regime they name is wide in practice: clusters rarely grow as fast as datasets. The result closes a long standing gap in distributed optimization theory. It also gives a new template: local steps for speed, variance control for calm, and rounds priced by workers alone.

Catalog record

CREATORTehila Dahan Technion Haifa, Israel Bassel Hamoud Technion Haifa, Israel Roie Reshef Technion Haifa, Israel Martin Jaggi EPFL Lausanne, Switzerland Kfir Y. Levy Technion Haifa, Israel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01128

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning Tehila Dahan Technion Haifa, Israel Bassel Hamoud Technion Haifa, Israel Roie Reshef Technion Haifa, Israel Martin Jaggi EPFL Lausanne, Switzerland Kfir Y. Levy Technion Haifa, Israel Abstract Communication overhead is a crucial bottleneck in scalable distributed learning. While existing methods aim to efficiently utilize data points, such as Local SGD, Minibatch SGD, and their accelerated variants, they still exhibit communication-round complexity that scales with the total number of samples N N . In this paper, we introduce Local MixVR, a distributed framework that integrates local updates with variance-reduction techniques to mitigate local noise. We show that Local MixVR is the first distributed method to eliminate the dependence of communication complexity on N N , achieving a complexity that scales only with the number of workers M M . In common regimes where M < 𝒪 ⁡ ( N 1 / 4 ) M<\mathcal{O}\left(N^{1/4}\right) , Local MixVR outperforms the state-of-the-art Minibatch Accelerated SGD baseline, bridging a long-standing gap in distributed optimization and establishing a new paradigm for communication-efficient training. 1 Introduction In the era of massive-scale machine learning ( 37 ; 42 ) , parallelizing training across multiple workers has become necessary. However, communication overhead remains a fundamental bottleneck: as the number of workers increases, the cost of synchronizing updates can dominate overall training time. This can be even more severe in poorly connected clusters, where limited bandwidth and high latency between nodes can significantly slow synchronization ( 10 ; 15 ) . As a result, a central goal in distributed learning is to minimize the number of communication rounds while maintaining fast convergence. A fundamental approach to parallel stochastic optimization is Minibatch SGD ( 8 ) , where M workers compute stochastic gradients on minibatches of size K and average them at each synchronization round to perform a global update. This is equivalent to using an effective batch size of MK , which reduces the stochastic variance by a factor of MK . Due to its simplicity and effectiveness, Minibatch SGD is widely used in distributed training ( 2 ) . However, increasing the effective batch size is beneficial only up to a point ( 16 ) . Once stochastic noise has been sufficiently reduced, further increases in batch size yield diminishing returns. In many modern training regimes, the total batch size MK enabled by many workers already exceeds the level needed for efficient learning. Consequently, adding more workers may not substantially reduce the number of iterations to convergence, while it still increases synchronization and communication costs. This can slow overall training despite the availability of additional compute. This motivates distributed methods to use the available gradient information more effectively, rather than simply increasing the minibatch size. Instead of using the extra gradients solely to reduce variance, one can also use them to make additional progress in optimization. This is the idea behind Local SGD ( 36 ; 26 ) : each worker performs K local steps, then the server averages the models and sends the averaged model back to all workers. This contrasts with Minibatch SGD, which performs only one global update per communication round. More specifically, over R rounds, Minibatch SGD performs R optimization steps, whereas Local SGD performs KR local updates per worker. Thus, for the same number of processed gradients, Local SGD leverages this information to reduce stochastic gradient noise and make more progress along the optimization path. Table 1 : Convergence rates and R_{\min} for \sigma=\mathcal{O}\left(1\right) , and N=MKR total samples. Method Rate [\mathcal{O}\left(\cdot\right)] \boldsymbol{R_{\min}}~[\Omega\left(\cdot\right)] MiniBatch SGD ( 8 ) \dfrac{1}{R}+\dfrac{\sigma}{\sqrt{MKR}} N^{1/2} MiniBatch Accelerated SGD ( 23 ; 8 ) \dfrac{1}{R^{2}}+\dfrac{\sigma}{\sqrt{MKR}} N^{1/4} Local SGD ( 20 ) \dfrac{1}{KR}+\dfrac{\sigma^{2/3}}{K^{1/3}R^{2/3}}+\dfrac{\sigma}{\sqrt{MKR}} MN^{1/2} SCAFFOLD ( 18 ) \dfrac{1}{R}+\dfrac{\sigma}{\sqrt{MKR}} N^{1/2} Local Momentum ( 6 ) \dfrac{1}{KR}+\dfrac{\sigma^{1/2}}{K^{1/4}R}+\dfrac{1}{K^{1/3}R^{4/3}}+\dfrac{1}{R^{2}}+\dfrac{\sigma}{\sqrt{MKR}} M^{1/3}N^{1/3} Accelerated Outer SGD ( 19 ) \dfrac{1}{KR^{2}}+\dfrac{\sigma^{2/3}}{M^{1/3}K^{1/3}R}+\dfrac{\sigma^{1/2}}{K^{1/4}R^{5/4}}+\dfrac{\sigma}{\sqrt{MKR}} M^{1/4}N^{1/4} Local SGD Lower bound: ( 11 ) \dfrac{1}{KR}+\dfrac{\sigma^{2/3}}{K^{1/3}R^{2/3}}+\dfrac{\sigma}{\sqrt{MKR}} MN^{1/2} Local MixVR (this paper) Theorem 3.2 \dfrac{1}{KR}+\dfrac{\sigma}{K^{\mathbf{1/2}}R}+\dfrac{\sigma}{\sqrt{MKR}} \mathbf{M} This approach, however, introduces a new challenge: worker drift . Because each worker performs multiple updates with different samples, local models can diverge between synchronization rounds, especially when many local steps are taken. Thus, although Local SGD seeks to extract more progress from each sample, its gains are limited by this accumulated drift. Indeed, lower bounds ( 11 ) show that Local SGD cannot require fewer communication rounds than Minibatch SGD to effectively utilize data points; see Table 1 . To assess the required number of communication rounds, one should ask, given a sample budget N , what is the minimum number of communication rounds such that additional optimization steps no longer improve the convergence rate? The key trade-off is between the optimization error and the statistical error . Since the statistical error is determined by the fixed sample budget N , there is a point beyond which further reducing the optimization error (by performing more optimization steps) does not improve the overall rate. For example, Minibatch SGD has a convergence rate of order \displaystyle\underbrace{\dfrac{1}{R}}_{\text{optimization error}}+\underbrace{\dfrac{\sigma}{\sqrt{N}}}_{\text{statistical error}} where N:=MKR and \sigma^{2} bounds the stochastic variance. Thus, the statistical error dominates as long as \displaystyle\frac{1}{R}\leq\mathcal{O}\left(\frac{1}{\sqrt{N}}\right) Consequently, once the number of communication rounds exceeds the critical threshold R_{\min}=\Omega\left(\sqrt{N}\right) , increasing R no longer improves convergence. Conversely, using fewer than R_{\min} rounds worsens the rate, since the optimization error remains larger than the statistical error, which is the lower bound for first-order methods using N samples ( 30 ; 1 ) . Thus, R_{\min} is precisely the minimum number of communication rounds needed to preserve the optimal convergence rate. While existing local methods attempt to improve this threshold ( Table 1 ), none currently outperform Minibatch Accelerated SGD (ASGD) ( 23 ) . Designing a method that provably surpasses Minibatch ASGD , therefore, remains a long-standing challenge. Furthermore, the communication complexity of existing approaches, including ASGD, scales with the sample size N . This dependence can be restrictive in common distributed-learning regimes, where datasets are often large, and communication is a primary bottleneck. To overcome these limitations, we introduce Local MixVR, a distributed framework that integrates three distinct variance-reduction techniques: • Local double-momentum: We adopt a recent double-momentum approach ( 7 ) to substantially reduce local stochastic variance to keep workers closely aligned. • Hybrid local-minibatching: Near the end of each communication round, we replace the remaining local steps with a single minibatch update of the same size to reduce worker divergence rather than amplify it by progressing locally. • Drift correction mechanism: We introduce a correction mechanism that mitigates bias arising from the transition from local to global parameters at synchronization steps. Each of these components can operate to suppress local divergence; when combined, they yield a unified, robust framework for distributed learning with local updates. Our Contributions: • Surpassing the Accelerated Baseline. We show that in the common regimes where M\leq\mathcal{O}\left(N^{1/4}\right) , Local MixVR is the first algorithm to improve upon the state-of-the-art Minibatch ASGD baseline ( Table 1 ). This regime arises naturally in practical training; for example, ImageNet-1K ( 9 ) has about 1.28\times 10^{6} training images and is often trained with M=8 workers ( 13 ) , giving {R^{\rm ASGD}_{\min}}/{R^{\rm MixVR}_{\min}}\approx N^{1/4}/M\approx 4.2 . Similarly, FineWeb ( 33 ) has roughly 15\times 10^{12} tokens and was trained

Read the complete text