Communication-efficient algorithms for statistical optimization

By Yuchen Zhang, John C. Duchi, Martin J. Wainwright. 2012

620 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “With the exception of CoCoA [4, 7], the existing work concerning communication efficient optimization [10, 14] and/or statistical estimation [13, 12] presupposes, and in fact requires, that the number of nodes is (much) smaller than the number of datapoints available to each node, and that each node”
Federated Optimization in Heterogeneous Networks (2018, methodology): “Large-scale machine learning, particularly in data center settings, has motivated the development of numerous distributed optimization methods in the past decade (see, e.g., Boyd et al., 2010; Dekel et al., 2012; Dean et al., 2012; Zhang et al., 2013; Li et al., 2014a; Shamir et al., 2014; Reddi et ”
Is Local SGD Better than Minibatch SGD? (2020, neutral): “(Zinkevich et al., 2010; Zhang et al., 2012; Li et al., 2014; Rosenblatt and Nadler, 2016; Godichon-Baggioni and Saadane, 2017; Jain et al., 2017).”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “[48, 31, 11, 16] represent statistical convergence analysis with only one-pass over the training data which usually is not enough for the training error to converge.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “An orthogonal one is to pay more local computation for less communication, e.g., one-shot aggregation [53, 54, 16, 21, 46], primal-dual algorithms [37, 38, 7] and distributed Newton methods [33, 52, 29, 35, 25].”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “…ML training algorithms to reduce the dependency on intensive parameter updates to enable more efﬁcient parallel training (e.g., (Jaggi et al., 2014; Zhang et al., 2013; Zinkevich et al., 2010; Takác et al., 2013; Neiswanger et al., 2014; Shamir et al., 2014; Zhang & Lin, 2015; Shalev-Shwartz &…”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “For a large scale network, the communication cost often becomes dominant compared to the computation time, calling for communication eﬃcient distributed optimization (Zhang et al., 2012; McMahan et al., 2017; Park et al., 2018; Jordan et al., 2018; Liu et al., 2019; Sriranga et al., 2019).”
On the Convergence of FedAvg on Non-IID Data (2019, background): “Assumptions 3 and 4 have been made by the works (Zhang et al., 2013; Stich, 2018; Stich et al., 2018; Yu et al., 2019).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Skipping communication rounds , whereby nodes average their models after locally updating their models for several steps [YYZ18,Cop15,ZDW13,Sti19,CH16,WJ18].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “Zhang et al. (2012) OSA Small learning rates cµt ; µ often unknown; Nonasymptotic bound on single worker convergence rate is used (Rakhlin et al. (2012)); Jain et. al.”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, background): “It is immediate that xt = xt−1 − γ 1 N N∑ i=1 Gti (5) Inspired by earlier works on distributed stochastic optimization (Zhang, Wainwright, and Duchi 2012) (Lian et al. 2017) (Mania et al. 2017) (Stich 2018) where convergence analysis is performed for an aggregated version of individual solutions,…”
Local SGD Converges Fast and Communicates Little (2018, background): “[49] show statistical convergence (see also [10, 13, 33]), but the analysis restricts the algorithm to at most one pass over the data, which is in general not enough for the training error to converge.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “Previous work has considered a standard one-round scheme where each local machine computes the empirical risk minimizer (ERM) using its local data and the master machine receives all workers’ ERMs and computes their average (Zhang et al., 2012).”
Distributed Statistical Machine Learning in Adversarial Settings (2017, methodology): “One-Shot Aggregation: On the other end of the spectrum, using a One-Short Aggregation method, each working machine computes an estimate of the model parameter using only its local data and reports it to the server, which then aggregates all the estimates reported to obtain a final estimate [33, 32].”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “no better than training a model on a single client [44, 3, 46].”
Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015, background): “A lot of recent work has been devoted to design communication-eﬃcient learning algorithms [DAW12, ZDW13, ZX15, KVW14, LBKW14, SSZ14, LSLT15].”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “The main focus of [30]–[32] is the trade-off between communication and optimality, where the complexity of solving the local problem (such as the number of local updates needed) is not studied.”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “If only one outer round of communication is performed, this is similar in spirit to one-shot communication schemes, which attempt to completely solve for and then combine locallycomputed models (see, e.g., Mann et al., 2009; Zhang et al., 2013; Heinze et al., 2016).”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, background): “[24] Yuchen Zhang, Martin J Wainwright, and John C Duchi.”