Pith. sign in

REVIEW 4 cited by

The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1909.05350 v2 pith:QOT7MXFC submitted 2019-09-11 cs.LG cs.DCmath.OCstat.ML

Sebastian U. Stich , Sai Praneeth Karimireddy This is my paper
classification cs.LGcs.DCmath.OCstat.ML
keywords delayedcompresseddelaygradientsratesresultsstochasticcommunication
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher order deterministic term which is only linearly slowed down by the delay. Thus, in the presence of noise, the effects of the delay become negligible after a few iterations and the algorithm converges at the same optimal rate as standard SGD. This result extends a line of research that showed similar results in the asymptotic regime or for strongly-convex quadratic functions only. We further show similar results for SGD with more intricate form of delayed gradients -- compressed gradients under error compensation and for local~SGD where multiple workers perform local steps before communicating with each other. In all of these settings, we improve upon the best known rates. These results show that SGD is robust to compressed and/or delayed stochastic gradient updates. This is in particular important for distributed parallel implementations, where asynchronous and communication efficient methods are the key to achieve linear speedups for optimization with multiple devices.

Discussion (0). Sign in to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Overcoming the Communication-Performance Tradeoff in LLM Pretraining

    cs.LG 2025-08 conditional novelty 7.0 of 10

    SparseLoCo combines error feedback with Top-k sparsification and 2-bit quantization to send 1-3% of the pseudo-gradient during LLM pre-training while matching or beating DiLoCo's dense updates.

  2. From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guarantees

    math.OC 2025-09 conditional novelty 6.0 of 10

    PowerSGD can provably fail to converge; the proposed PowerSGD+ with periodic SVD subspace resets converges under standard assumptions at O(1/sqrt(NT)).

  3. Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold

    math.OC 2025-06 conditional novelty 6.0 of 10

    EF-Landing provably converges at O(1/sqrt(N K)) for distributed stochastic problems on the Stiefel manifold while using compressed communication and no retraction.

  4. FedWSQ: Efficient Federated Learning with Weight Standardization and Distribution-Aware Non-Uniform Quantization

    cs.LG 2025-06 conditional novelty 5.0 of 10

    FedWSQ applies weight standardization in federated learning and uses Gaussian-optimal non-uniform quantization with a shared global scaling vector, improving accuracy at very low bit rates.

Pith tools