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

By Sebastian U. Stich, Sai Praneeth Karimireddy. 2019

184 citations recorded by the source corpus.

Subfields: Efficiency & Compression, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “We note that several recent works allow biased estimators and would work nicely with Laplacian noise [371], however those would not give differential privacy, as they break independence between rounds.”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “In [28], and more recently in [29, 26, 16, 37], sharper and refined analyses of the same method (sometimes called local SGD) for identical functions.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[17] Sebastian U Stich and Sai Praneeth Karimireddy.”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, methodology): “Together with some form of error compensation, these methods have been shown to converge as fast as vanilla SGD in [26], [27], [37].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “In this work we do not consider gradient compression techniques (Alistarh et al., 2017; Stich et al., 2018; Tang et al., 2018a; 2019; Stich & Karimireddy, 2019)—but such orthogonal techniques could be added on top of our scheme—and instead only focus on local updates steps which are often efﬁcient…”
Is Local SGD Better than Minibatch SGD? (2020, background): “Reference Setting Best Convergence rate (i.e., E [ F ( x output ) − F ( x (cid:63) )] (cid:46) ) Stich and Karimireddy (2019 Non-SC”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “Stich (2018) and, more recently Stich and Karimireddy (2019) and Patel and Dieuleveut (2019), gave a sharper analysis of the same method, under the name of local SGD, also for identical functions.”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, background): “Karimireddy et al. (2019) and Stich & Karimireddy (2019) further develop and generalize the framework of error feedback with improved rates.”
Dynamic Model Pruning with Feedback (2020, methodology): “Here we follow Lacoste-Julien et al. (2012) for the general structure, combined with estimates from the error-feedback framework (Stich et al., 2018; Stich & Karimireddy, 2019) to control the pruning errors.”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, neutral): “We further provide a novel analysis in the convex case, which has not been previously explored in the literature, with the exception of (Stich and Karimireddy, 2019).”
Towards Understanding Biased Client Selection in Federated Learning (2022, methodology): “…on the convergence of local-update SGD is analyzed in recent works (Reddi et al., 2021; Haddadpour and Mahdavi, 2019; Khaled et al., 2020; Stich and Karimireddy, 2020; Woodworth et al., 2020; Koloskova et al., 2020; Huo et al., 2020; Zhang et al., 2020; Pathak and Wainwright, 2020;…”
Better Theory for SGD in the Nonconvex World (2020, methodology): “Then for all x ∈ R d we have This lemma shows up in several recent works and is often used in conjunction with other assumptions such as bounded variance (Li & Orabona, 2019) and convexity (Stich & Karimireddy, 2019).”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, methodology): “[5,34,45,50], a quantization operator is applied before transmitting the gradient to server.”
Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning (2021, background): “Wang & Joshi (2018) and Stich & Karimireddy (2019) further proposed improved FedAvg algorithms to achieve a O ( + √ mKT ) rate without bounded gradient assumption.”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “[12] Sebastian U Stich and Sai Praneeth Karimireddy.”
Federated Learning under Arbitrary Communication Patterns (2021, methodology): “Notice that even though related, our model, which is the asynchronous communication version of local SGD as also discussed in (Stich, 2018; Basu et al., 2019; Stich & Karimireddy, 2019), is different in that we assume all the clients perform local updates in each round.”