Communication-Efficient Distributed Dual Coordinate Ascent

By Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, Michael I. Jordan. 2014

363 citations recorded by the source corpus.

Communication remains the most significant bottleneck in the performance of distributed optimization algorithms for large-scale machine learning. In this paper, we propose a communication-efficient framework, CoCoA, that uses local computation in a primal-dual setting to dramatically reduce the amount of necessary communication. We provide a strong convergence rate analysis for this class of algorithms, as well as experiments on real-world distributed datasets with implementations in Spark. In our experiments, we find that as compared to state-of-the-art mini-batch versions of SGD and SDCA algorithms, CoCoA converges to the same .001-accurate solution quality on average 25x as quickly.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

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 Learning: Collaborative Machine Learning without Centralized Training Data (2022, neutral): “The CoCoA framework [12] is designed for this setting.”
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.”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “These works reduce communication overhead by proposing algorithm-speciﬁc approaches, such as solving a dual problem (Shalev-Shwartz & Zhang, 2013; Takác et al., 2013; Jaggi et al., 2014) or employing a different optimization algorithm (Rakhlin et al., 2012; Zhang & Lin, 2015).”
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).”
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).”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “Related Work The large-scale nature of modern machine learning has spurred a great deal of novel research on distributed and parallel training algorithms and systems (Recht et al., 2011; Dean et al., 2012; Alistarh et al., 2017; Jaggi et al., 2014; Liu et al., 2014; Mania et al., 2015; Chen et al., ”
Federated Multi-Task Learning (2017, methodology): “4, our method and theory generalize the results in [22, 31].”
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): “To illustrate the role of f as a smooth loss function and g as a strongly convex regularizer in objective (A), contrasting with their traditional roles in prior work (Yang, 2013; Jaggi et al., 2014; Ma et al., 2015b,a), we consider the following examples.”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “These methods are DANE [20], DISCO [23] and COCOA+ [11, 5, 12, 21].”
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].”
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, ”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “; Liu & Wright, 2014; Fer-coq & Richt ´ arik, 2013; Fercoq et al., 2014; Jaggi et al., 2014; Shamir & Srebro, 2014; Shamir et al., 2014a; Zhang & Xiao, 2015; Qu & Richt ´ arik, 2014) and the references therein.”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “Work in parallel and distributed optimization has shown that these systems can obtain massive speed up gains in both convex and non-convex settings [9, 18, 19, 26, 34, 41].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “As datasets continue to increase in size, and parallel computing platforms becoming more and more common (from multiple cores on a single CPU to large-scale and geographically distributed computing grids), distributed learning and optimization methods have been the focus of much research in recent y”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “Recent advances in parallel and distributed computing technologies have generated renewed interest in the theoretical understanding and practical implementation of parallel stochastic algorithms [15–20].”
Distributed optimization with arbitrary local solvers (2015, methodology): “The presented work here builds on the promising approach of [26, 70] in this direction.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “In the case of non-smooth optimization, fast communication schemes were developed in [14, 15], although precise optimal convergence rates were not obtained.”
Coordinate descent algorithms (2015, methodology): “[20] perform a synchronized CD method on the dual ERM model (7) for the case of g(w) = g∗(w) = (1/2)‖w‖2, partitioning components of the dual variable x between cores and sharing a copy of the vector Ax across cores, updating this vector at each synchronization point.”