Adding vs. Averaging in Distributed Primal-Dual Optimization

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

178 citations recorded by the source corpus.

Distributed optimization methods for large-scale machine learning suffer from a communication bottleneck. It is difficult to reduce this bottleneck while still efficiently and accurately aggregating partial work from different machines. In this paper, we present a novel generalization of the recent communication-efficient primal-dual framework (COCOA) for distributed optimization. Our framework, COCOA+, allows for additive combination of local updates to the global parameters at each iteration, whereas previous schemes with convergence guarantees only allow conservative averaging. We give stronger (primal-dual) convergence rate guarantees for both COCOA as well as our new variants, and generalize the theory for both methods to cover non-smooth convex loss functions. We provide an extensive experimental comparison that shows the markedly improved performance of COCOA+ on several real-world distributed datasets, especially when scaling up the number of machines.

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): “Recent works show that a careful choice of the server-side learning rate can lead to faster convergence [12, 11, 9].”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “The observed slowdown is both consistent across data sets (roughly 20x) and with other papers that use Scala code (e.g. Mania et al. 2017, Ma et al. 2015, Fig.”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “…a multi-task learning framework for federated learning and its related optimization algorithm, which extends early works SDCA (Shalev-Shwartz and Zhang, 2013; Yang, 2013; Yang et al., 2013) and CO-COA (Jaggi et al., 2014; Ma et al., 2015; Smith et al., 2016) to the federated learning setting.”
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.”
COLA: Decentralized Linear Learning (2018, methodology): “In the distributed setting with a central server, algorithms of the C O C O A family [Yang, 2013, Jaggi et al., 2014, Ma et al., 2015, Dünner et al., 2018]—see [Smith et al., 2018] for a recent overview— are targeted for problems of the forms (A) and (B).”
Federated Multi-Task Learning (2017, methodology): “Though we prove our results for a general γ , we simplify the method and results here by setting γ := 1 , which has been shown to have the best performance, both theoretically and empirically [30].”
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].”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “For convex objectives, distributed local-updating primal-dual methods have emerged as a popular way to tackle such a problem [54, 62, 72, 107, 128].”
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): “These methods are D ANE [20], D ISCO [23] and C OCOA + [11, 5, 12, 21].”
Bayesian Nonparametric Federated Learning of Neural Networks (2019, background): “Yet others explore distributed optimization with a speciﬁc emphasis on communication ef-ﬁciency (Zhang et al., 2013; Shamir et al., 2014; Yang, 2013; Ma et al., 2015; Zhang & Lin, 2015).”
Scheduling Policies for Federated Learning in Wireless Networks (2019, background): “Nevertheless, the value of such quantity affects the ultimate rate of convergence [35].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “First analysis was introduced in [42], with further improvements in [58], and a more general version in [57].”
Distributed optimization with arbitrary local solvers (2015, background): “The framework therefore completely decouples the local solvers from the distributed communication.”
ASAGA: Asynchronous Parallel SAGA (2016, background): “Our second dataset was first introduced in Ma et al. (2009). Its associated task is a binary malicious url detection.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “…cost, such as increased mini-batch 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…”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Two classes of methods address this issue – randomized coordinate descent methods [4], [5], [6] , [7], [8], [9], [10], [11], [12], [13] and stochastic gradien t methods [14], [15], [16], [17], [18].”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “However, in comparison, GIANT has some major advantages over the prior works DANE, AIDE, CoCoA (Smith et al., 2016), and DiSCO (Zhang and Lin, 2015).”