AIDE: Fast and Communication Efficient Distributed Optimization

By Sashank J. Reddi, Jakub Konecný, Peter Richtárik, Barnab'as P'oczos, Alex Smola. 2016

153 citations recorded by the source corpus.

In this paper, we present two new communication-efficient methods for distributed minimization of an average of functions. The first algorithm is an inexact variant of the DANE algorithm that allows any local algorithm to return an approximate solution to a local subproblem. We show that such a strategy does not affect the theoretical guarantees of DANE significantly. In fact, our approach can be viewed as a robustification strategy since the method is substantially better behaved than DANE on data partition arising in practice. It is well known that DANE algorithm does not match the communication complexity lower bounds. To bridge this gap, we propose an accelerated variant of the first method, called AIDE, that not only matches the communication lower bounds but can also be implemented using a purely first-order oracle. Our empirical results show that AIDE is superior to other communication efficient algorithms in settings that naturally arise in machine learning applications.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Federated & Distributed Learning, Mathematical Optimization

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 Theory and Mathematics

In Federated & Distributed Learning

In Mathematical Optimization

Citations in the corpus

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 ”
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].”
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).”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “If the data are iid distributed, distributed optimization can be efficiently solved by the second-order algorithms [15, 19, 23, 25, 36] and the one-shot methods [12, 13, 32, 37, 38].”
Natural Compression for Distributed Deep Learning (2019, neutral): “For example, one may use mini-batching to construct more powerful gradient estimators [15], define local problems for each worker to be solved by a more advanced local solver [42, 37, 36], or reduce communication frequency (e.”
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.”
Expanding the Reach of Federated Learning by Reducing Client Resource Requirements (2018, background): “Communication-efﬁcient distributed learning Distributed learning is known to suffer from communication over-heads associated with the frequent gradient updates exchanged among nodes [Wang et al., 2018, Dean et al., 2012, Smith et al., 2018, Reddi et al., 2016].”
COLA: Decentralized Linear Learning (2018, methodology): “Other centralized algorithm representatives are parallel SGD variants such as [Agarwal and Duchi, 2011, Zinkevich et al., 2010] and more recent distributed second-order methods [Zhang and Lin, 2015, Reddi et al., 2016, Gargiani, 2017, Lee and Chang, 2017, Dünner et al., 2018, Lee et al., 2018].”
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): “…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., 2016, Wang et al., 2017).”
Randomized Distributed Mean Estimation: Accuracy vs. Communication (2016, background): “In these applications, the averaging operations need to be done repeatedly throughout the iterations of a master learning/optimization algorithm, and the vectors { X i } correspond to updates to a global model/variable.”
FedDANE: A Federated Newton-Type Method (2019, methodology): “Inexact DANE allows the ﬂexibility of solving (2) inexactly [9].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Several distributed local-updating primal methods have also been proposed, which have the added benefit of being applicable to non-convex objectives [93, 136].”
Overcoming Forgetting in Federated Learning on Non-IID Data (2019, background): “AIDE [13] improves the ability of DANE to deal with non i.i.d. data.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The communication eﬃcient algorithms provide us with much more ﬂexible tools for designing overall optimization procedure, which can make the algorithms inherently adaptive to diﬀerences in computing resources and architectures.”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “The existing works on distributed machine learning mainly focus on two directions: 1) how to design communication efficient algorithms to reduce the round of communications among workers [43, 31, 13, 27, 42], and 2) about how to use large mini-batches without compromising the convergence speed [21, ”
Distributed optimization with arbitrary local solvers (2015, methodology): “Since the first version of this work, Accelerated Inexact Dane (AIDE) [50]—a method based on related set of ideas but applied to the primal problem—was developed.”