Parallel Restarted SGD for Non-Convex Optimization with Faster Convergence and Less Communication

By Hao Yu, Sen Yang, Shenghuo Zhu. 2018

66 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “While [370, 428, 399, 371] mainly focused on the IID case, the analysis technique can be extended to the non-IID case by adding an assumption on data dissimilarities, for example by constraining the difference between client gradients and the global gradient [266, 261, 265, 401] or the difference be”
On the Convergence of FedAvg on Non-IID Data (2019, background): “The prior work [3, 41, 28, 34, 30, 31] requires the full device participation in the aggregation step of FedAvg .”
Fair Resource Allocation in Federated Learning (2019, methodology): “These local updating methods enable flexible and efficient communication compared to traditional mini-batch methods, which would simply calculate a subset of the gradients (Stich, 2019; Wang & Joshi, 2018; Woodworth et al., 2018; Yu et al., 2019).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “[39] Hao Yu, Sen Yang, and Shenghuo Zhu.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Recently, Yu et al. (2018) have given convergence rates for the non-convex synchronous and a stale synchronous settings.”
Practical Distributed Learning: Secure Machine Learning with Communication-Efficient Local Updates (2019, background): “The limited existing work with convergence guarantees are based on the strong assumption of IID training data (Yu et al., 2018; Stich, 2018), which we have argued is inappropriate for the federated learning setting.”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “When considering overall computational cost, there seems no benefit in evaluating multiple stochastic gradients at the same time, such as done in mini-batch SGD.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms Federated Averaging, rigorous theoretical understanding of how its convergence depends on the number of local updates τ is quite limited (Zhou & Cong, 2017; Yu et al., 2018).”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, background): “…special case since Algorithm 1 calculates the model average to obtain y every I iterations and performs local SGDs at each worker 3After the preprint (Yu, Yang, and Zhu 2018) of this paper is posted on ArXiv in July 2018, another work (Wang and Joshi 2018) subsequently analyzes the convergence…”
Local SGD Converges Fast and Communicates Little (2018, background): “Indeed, very recent work [44, 51] analyzes local SGD for non-convex optimization problems and shows convergence of SGD to a stationary point, though the restrictions on H are stronger than here.”
FedDANE: A Federated Newton-Type Method (2019, methodology): “Other works analyze different methods with non-identically distributed data, but under different (possibly) limiting assumptions, such as using SGD as a specific local solver [6], full device participation [14, 15], convexity [3, 6, 14], or uniformly-bounded gradients [6, 15].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “, convexity [27] or uniformly bounded gradients [52].”
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD (2018, methodology): “While some recent theoretical works (Zhou & Cong, 2017; Yu et al., 2018; Wang & Joshi, 2018; Stich, 2018) study this dependence of the error-convergence with respect to the number of iterations as τ varies, achieving a provably-optimal speed-up in the true convergence with respect to wall-clock…”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “There are a few recent work such as [31,33,36] try to maximize E , while achieving linear speed up.”
Clustered Federated Learning: Model-Agnostic Distributed Multitask Optimization Under Privacy Constraints (2019, background): “Different authors have investigated the convergence properties of Federated Learning in congruent iid and non-iid scenarios: [12],[13],[14] and [15] perform an empirical investigation, [8], [16], [17] and [9] prove convergence guarantees.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “Analyses have been developed for strongly convex (Patel and Dieuleveut, 2019; Stich, 2019b) and non-convex (Yu et al., 2018; Wang and Joshi, 2018) functions.”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “Instead, the nodes locally perform a few iterations of training using local-update stochastic gradient descent (SGD) [5–8], and only send model updates periodically to the aggregating cloud server.”
SLSGD: Secure and Efficient Distributed On-device Machine Learning (2019, methodology): “Our algorithm is based on local SGD introduced in [29,26].”