Distributed optimization with arbitrary local solvers

By Chenxin Ma, Jakub Konecný, Martin Jaggi, Virginia Smith, Michael I. Jordan, Peter Richtárik, Martin Takác. 2015

206 citations recorded by the source corpus.

With the growth of data and necessity for distributed optimization methods, solvers that work well on a single machine must be re-designed to leverage distributed computation. Recent work in this area has been limited by focusing heavily on developing highly specific methods for the distributed environment. These special-purpose methods are often unable to fully leverage the competitive performance of their well-tuned and customized single machine counterparts. Further, they are unable to easily integrate improvements that continue to be made to single machine methods. To this end, we present a framework for distributed optimization that both allows the flexibility of arbitrary solvers to be used on each (single) machine locally and yet maintains competitive performance against other state-of-the-art special-purpose distributed methods. We give strong primal–dual convergence rate guarantees for our framework that hold for arbitrary local solvers. We demonstrate the impact of local solver selection both theoretically and in an extensive experimental comparison. Finally, we provide thorough implementation details for our framework, highlighting areas for practical performance gains.

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

In Management Science and Operations Research

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.”
Robust Aggregation for Federated Learning (2019, background): “Recent work includes primal-dual frameworks [62, 80] and variants suited to decentralized [37], and asynchronous [52] settings.”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “Consensus optimization underlies most of the primal methods, while dual decomposition and ADMM are the most popular among the primal-dual algorithms (Glowinski and Marroco, 1975; Gabay and Mercier, 1975; Boyd et al., 2011; Jaggi et al., 2014; Ma et al., 2017; Deng et al., 2017).”
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.”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “The main focus of [34]–[36] 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): “(Ma et al., 2015b, Remark 7) If the data points x i are normalized such that x i (cid:107) ≤ 1 , ∀ i ∈ [ n ] , then σ k ≤”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “[11] Chenxin Ma, Jakub Konečný, Martin Jaggi, Virginia Smith, Michael I Jordan, Peter Richtárik, and Martin Takáč.”
Scheduling Policies for Federated Learning in Wireless Networks (2019, methodology): “…FL. Recognizing the potential inefﬁciency of the conventional FL training approach [16], we leverage methods from distributed coordinate descent [20] and propose an algorithm that decouples the global averaging at the AP and local computing at each UE, whereas the partial solutions from UEs…”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The general upper bound on number of iterations of the CoCoA framework is I( ,Θ) = O(log(1/ )) 1−Θ [42, 58, 57] for strongly convex objectives.”
fPINNs: Fractional Physics-Informed Neural Networks (2018, methodology): “On the other hand, we will investigate other available optimization algorithms such as in references [67, 68] in order to expedite finding better local minima.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “For this class of problems, the recently proposed C O C O A approach (Yang, 2013; Jaggi et al., 2014; Kone ˇ cn ´ y et al., 2014) has formulated a communication efﬁcient primal-dual coordinate ascent scheme which targets the communication bottleneck, by allowing more computation to be performed on…”
LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning (2018, methodology): “Roughly speaking, algorithms in (Smith et al., 2017; Jaggi et al., 2014; Ma et al., 2017; Shamir et al., 2014; Zhang and Lin, 2015) reduce communication by increasing local computation (relative to GD), while our method does not increase local computation.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “…sizes (Goyal et al., 2017), deﬁning local problems for each worker (Shamir et al., 2014; Jaggi et al., 2014; Ma et al., 2015; Reddi et al., 2016; Ma et al., 2017), reducing the communication frequency (McDonald et al., 2009; Zinkevich et al., 2010; You et al., 2017; Stich, 2018) or…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Here we only remark that the popular algorithm CoCoA+ [104] arises if Step 5 in Algorithm 15 is done inexactly.”
When Edge Meets Learning: Adaptive Control for Resource-Constrained Distributed Machine Learning (2018, background): “The results were then extended to general classes of distributed learning approaches in [16].”
Federated Learning over Wireless Networks: Optimization Model Design and Analysis (2019, methodology): “As in [2], [6], the computation phase is synchronous such that all UEs have to finish solving their local problems before entering the communication phase to transmit their updates to the BS by using a wireless medium sharing scheme (e.”
Primal-Dual Rates and Certificates (2016, background): “The proof is partially motivated by proofs in (Ma et al., 2015a; Shalev-Shwartz & Zhang, 2013) but come with some crucial unique steps and tricks.”
A Crowdsourcing Framework for On-Device Federated Learning (2019, background): “Furthermore, authors in [18] extended the theoretical training convergence analysis results of [15] to general classes of distributed learning approaches with communication and computation cost.”