Distributed Coordinate Descent Method for Learning with Big Data

By Peter Richtárik, Martin Takác. 2013

262 citations recorded by the source corpus.

In this paper we develop and analyze Hydra: HYbriD cooRdinAte descent method for solving loss minimization problems with big data. We initially partition the coordinates (features) and assign each partition to a different node of a cluster. At every iteration, each node picks a random subset of the coordinates from those it owns, independently from the other computers, and in parallel computes and applies updates to the selected coordinates based on a simple closed-form formula. We give bounds on the number of iterations sufficient to approximately solve the problem with high probability, and show how it depends on the data and on the partitioning. We perform numerical experiments with a LASSO instance described by a 3TB matrix.

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

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “Works including [2, 8, 3, 9] have established basic theoretical results and developed distributed versions of existing methods, but as this is a relatively new area, many open questions remain.”
Federated Optimization in Heterogeneous Networks (2018, methodology): “…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 al., 2016; Zhang et al., 2015; Richtárik & Takáč, 2016; Smith et al., 2018).”
On the Convergence of FedAvg on Non-IID Data (2019, background): “Traditional distributed machine learning employs a centralized approach which ﬁrst aggregates the training data on a single machine or in a data center and then performs model updates [7, 23, 36, 19, 20, 26, 40, 25].”
Natural Compression for Distributed Deep Learning (2019, background): “Another possibility is to apply randomized sparsification masks to the gradients [45, 28, 4, 44], or to rely on coordinate/block descent updates-rules, which are sparse by design [37, 11, 32].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “ethods, which involve extending classical stochastic methods to process multiple data points at a time, have emerged as a popular paradigm for distributed machine learning in data center environments [28, 88, 96, 102, 103]. In practice, however, they have been shown to have limited ﬂexibility to ada”
LoAdaBoost: Loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data (2018, methodology): “[4] proposed a distributed coordinate descent method named HYbriD for solving loss minimization problems with big data.”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) (e.g., Takáč et al., 2013; Shalev-Shwartz and Zhang, 2013b; Qu et al., 2015; Richtárik and Takáč, 2016) suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increa”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The first distributed versions of Coordinate Descent algorithms were the Hydra and its accelerated variant, Hydra2, [81, 34], which has been demonstrated to be very efficient on large sparse problems implemented on a computing cluster.”
Learning Theory for Distribution Regression (2014, methodology): “Beyond its simple analytical formula, kernel ridge regression also allows efficient distributed (Zhang et al., 2015; Richtárik and Takác̆, 2016), sketch (Alaoui and Mahoney, 2015; Yang et al.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “See e.g. (Shalev-Shwartz & Zhang, 2013c) for several concrete applications.”
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”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, background): “For sparse data, the work of [20, 21] gives some data dependent choices of βb which are safe.”
Distributed optimization with arbitrary local solvers (2015, background): “…with the massive growth of available datasets, major roadblocks still persist in the distributed setting, where data no longer ﬁts in the memory of a single computer, and computation must be split across multiple machines in a network [3, 7, 12, 18, 22, 28, 32, 34, 37, 46, 50, 58, 60, 62, 76].”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “Several recent papers, e.g., Richt´arik & Tak´aˇc [9], Le Roux, Schmidt & Bach [12, 13], Shalev-Shwartz & Zhang [14] and Johnson & Zhang [3] proposed methods which achieve such a variance-reduction eﬀect, directly or indirectly.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “…(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 distributing along features (Richtárik & Takáč, 2016; Fercoq et al., 2014).”
Fast distributed coordinate descent for non-strongly convex losses (2014, methodology): “The core of the paper forms the development of new stepsizes, and new efficiently computable bounds on the stepsizes proposed for distributed CD methods in [3].”