Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity

By Jason D. Lee, Qihang Lin, Tengyu Ma, Tianbao Yang. 2015

53 citations recorded by the source corpus.

Subfields: Optimization & Training, Federated & Distributed Learning

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

In Federated & Distributed Learning

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “This phenomena has been discussed (and sometimes been adressed by modifing the SGD updates) for example in (Shi et al., 2015; Lee et al., 2015; Nedić et al., 2016) and been rediscovered frequently in the context of stochastic optimization (Zhao et al.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of the works for instance are Reddi et al. (2015); Zhao and Li (2016); De and Goldstein (2015); Lee et al. (2015).”
Byzantine Stochastic Gradient Descent (2018, background): “There is an extremely rich literature studying the scalability and communication requirements of distributed SGD, e.g. [1, 9, 23, 24, 31, 32, 35, 40], in settings where all the workers are correct.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “More sophisticated algorithms have been proposed in order to achieve better accuracy than the one-round approach while maintaining lower communication costs; examples include DANE (Shamir et al., 2014), Disco (Zhang and Lin, 2015), distributed SVRG (Lee et al., 2015) and their variants (Reddi et al.”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “, 2016), DSVRG (Lee et al., 2015), and MP-DANE (proposed and analyzed in Appendix D).”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Examples of such methods include distributed variants of stochastic gradient descent (SGD) [17, 27, 47], accelerated SGD [35], variance reduction SGD [10, 28], stochastic coordinate descent methods [5, 13, 20, 31] and dual coordinate ascent algorithms [30, 43, 46].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “Byzantine-robust distributed learning Solving large scale learning problems in distributed systems has received much attention in recent years, where communication efficiency and Byzantine robustness are two important topics (Shamir et al., 2014; Lee et al., 2015; Yin et al., 2018b; Blanchard et al.”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, background): “(Recht et al., 2011), Distributed SDCA (Takáč et al., 2015), Distributed SVRG (Lee et al., 2015; Zhao & Li, 2016), ASAGA (Leblond et al., 2017), ProxASAGA (Pedregosa et al., 2017)).”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, background): “Other distributed optimization algorithms have also been proposed under different distributed computation frameworks: some algorithms use a one-shot model averaging [31, 51, 50], and a few other algorithms consider the cases where the workers locally store fractions of the dataset that they do not s”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, methodology): “Special cases of the proposed framework were published earlier as conference and work-shop papers (Lee and Roth 2015; Lee et al. 2015).”
A Distributed Second-Order Algorithm You Can Trust (2018, methodology): “Alter-natives include variance-reduced methods such as (Lee et al., 2015) and coordinate descent methods such as (Richtárik & Takáˇc, 2016), however, they suffer similar communication bottlenecks.”
Communication-Efficient Distributed Statistical Inference (2016, methodology): “Lee et al. (2015a) extended this idea to high-dimensional sparse linear regression by combining local debi-ased Lasso estimates (van de Geer et al. 2014).”
Faster On-Device Training Using New Federated Momentum Algorithm (2020, methodology): “Another line of communication-efficient distributed methods [17, 23, 40] performed model averaging after solving local subproblems and are guaranteed to converge.”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, background): “primal-dual structure of the problem and [10, 13, 22] which work in the primal alone.”
Efficient Distributed Learning with Sparsity (2016, methodology): “Concurrent work of (Jordan et al., 2016) (personal communication) also improved computational efficiency of Lee et al. (2015b) using ideas of Shamir et al. (2014).”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “In a similar spirit, distributed variance reduction techniques have been proposed for the ﬁnite-sum case (Lee et al., 2015; Koneˇcn`y et al., 2016a; Cen et al., 2019).”
Gradient Diversity Empowers Distributed Learning (2017, methodology): “…also been proposed under diﬀerent distributed computation frameworks: some algorithms use a one-shot model averaging [31, 51, 50], and a few other algorithms consider the cases where the workers locally store fractions of the dataset that they do not share it with other workers [27, 39, 49, 20].”