Research map / Optimization / Distributed and compressed

LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Compressed distributed optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LOSCAR-SGD, a Local SGD variant with sparse (Rand-K) model averaging, communication-computation overlap, and worker-specific local step counts, plus a delay-corrected merge rule; gives non-convex convergence and time-complexity theory and logical-time simulations on logistic regression and small vision tasks.

Problem

Communication is a bottleneck in distributed and federated learning; existing methods combine local training, compression, or overlap, but no theory covers all of them together in heterogeneous-speed, data-homogeneous settings.

Approach

Workers keep taking local SGD steps while a sparse (Rand-K) model average is in flight, and on arrival merge via a delay-corrected rule x = z + Proj_S(ybar - y) that keeps overlap progress instead of overwriting coordinates with the stale average.

Key results

• Overlap improves over blocking sparse averaging on a9a logistic regression, and the delay-corrected merge gives the best loss-vs-rounds curve (4 workers, step times (1,2,3,6)).
• For the delay-corrected method, smaller sparsity fraction p reduces logical communication cost by orders of magnitude with only mild optimization loss at the most aggressive levels.
• Under long communication delay, delay correction substantially outperforms naive overwrite.

Surprising findings

• Very large local computation budgets can be harmful outside the homogeneous-data regime covered by the theory (heterogeneous-data stress tests).

Limitations

• Theory restricted to data-homogeneous setting
• Does not establish optimal time complexity
• Experiments run in a logical-time simulator rather than real distributed hardware

Experimental setup

Datasets: a9a CIFAR-10 Tiny ImageNet

Benchmarks: a9a CIFAR-10 Tiny ImageNet

Metrics: training loss gradient norm accuracy logical time communicated bits

Baselines: Local Sparse (blocking) Overlap overwrite Minibatch SGD Local SGD FedAvg

Builds on: Local SGD FedAvg asynchronous SGD Overlap-Local-SGD CO2 LoCoDL

Closest papers by meaning

• On the Convergence of Communication-Efficient Local SGD for Federated Learning (AAAI 2021 · similarity 0.92)
• Communication trade-offs for Local-SGD with large step size (NeurIPS 2019 · similarity 0.92)
• Communication-efficient SGD: From Local SGD to One-Shot Averaging (NeurIPS 2021 · similarity 0.91)
• Local SGD Converges Fast and Communicates Little (ICLR 2019 · similarity 0.90)
• Communication-efficient Distributed SGD with Sketching (NeurIPS 2019 · similarity 0.90)
• Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.88)