Communication-Efficient Distributed Optimization using an Approximate Newton-type Method

By Ohad Shamir, Nati Srebro, Tong Zhang. 2013

601 citations recorded by the source corpus.

We present a novel Newton-type method for distributed optimization, which is particularly well suited for stochastic optimization and learning problems. For quadratic objectives, the method enjoys a linear rate of convergence which provably \emph{improves} with the data size, requiring an essentially constant number of iterations under reasonable assumptions. We provide theoretical and empirical evidence of the advantages of our method compared to other approaches, such as one-shot parameter averaging and ADMM.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Federated Learning: Strategies for Improving Communication Efficiency (2016, background): “The above framework differs from conventional distributed machine learning [17, 11, 19, 22, 5, 4] due to the the large number of clients, highly unbalanced and non-i.”
Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, methodology): “Two other communication efficient algorithms, DANE [10] and DiSCO[14], diverge in this setting, and so are not included in the figure.”
Federated Optimization in Heterogeneous Networks (2018, methodology): “In addition, DANE (Shamir et al., 2014) and AIDE (Reddi et al., 2016), distributed methods designed for the data center setting, propose a similar proximal term in the local objective function, but also augment this with an additional gradient correction term.”
Federated Learning: Collaborative Machine Learning without Centralized Training Data (2022, neutral): “Further distributed optimization methods are DANE [25], its accelerated variant AIDE [21], and DiSCO [27].”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, methodology): “SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “However, these analyses do not easily extend to multiple rounds, and the R = 1 constraint can provably harm performance (see Shamir et al., 2014).”
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].”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “DANE by Shamir et al. (2014) obtain a closely related primal only algorithm, which was later accelerated by Reddi et al. (2016).”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “…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 & Zhang, 2013)).”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “Similar to the centralized parallel optimization (Jakovetic, 2013; Li et al., 2014a;b; Shamir et al., 2014; Zhang and Lin, 2015; Meng et al., 2016; Reddi et al., 2016; Richtárik and Takác, 2016; Smith et al., 2016; Zheng et al., 2016; Shusen Wang et al., 2018), FL lets the user devices (aka worker n”
Fair Resource Allocation in Federated Learning (2019, background): “We provide additional details on the framework below; for further background on αfairness and fairness in resource allocation more generally, we defer the reader to Shi et al. (2014); Mo & Walrand (2000).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of them are Boyd et al. (2011) (ADMM), Shamir et al. (2014) (DANE), Zhang and Xiao (2015) (DiSCO), Reddi et al. (2016) (AIDE), Ma et al. (2017); Smith et al. (2016); Ma et al. (2015) (COCOA) and some of the references therein.”
Wireless Network Intelligence at the Edge (2018, methodology): “Besides, similar to ESGD, FSVRG keeps track of the global MSI and updates it based on the distributed approximate Newton (DANE) [178] that also ensures a constant learning rate.”
Byzantine Stochastic Gradient Descent (2018, background): “[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.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
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].”
FedDANE: A Federated Newton-Type Method (2019, methodology): “In this work, we take a similar approach to FedProx, and draw inspiration from DANE and variants [9, 10], which are popular methods developed for the distributed data center setting.”