Parallel coordinate descent methods for big data optimization

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

500 citations recorded by the source corpus.

In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 h on a large memory node with 24 cores.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, ML Systems & Hardware, 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 Mechanics

In Computational Theory and Mathematics

In ML Systems & Hardware

In Mathematical Optimization

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “We consider two frameworks for distributed optimization: (i) data-parallelism architecture, where data points are distributed across diﬀerent worker nodes, and in each iteration, they all par-allelly compute gradients on their local data and master aggregates them to update the parameter vector usin”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “In particular, the first case follows from Eq (32) and the second from Eq (37) in Richtárik and Takáč (2015). It only remains to substitute pij into (12) and transform the result into the desired form.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Numerous follow-up works extended the concept to proximal setting [79], single processor parallelism [15, 80] and develop efficiently implementable acceleration [51].”
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].”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “It remains open to obtain improved convergence rates for more aggressive updates corresponding to βK > 1, which might be suitable for using the ‘safe’ updates techniques of [4] and the related expected separable over-approximations of [18, 19], here applied to K instead of n blocks.”
Distributed optimization with arbitrary local solvers (2015, background): “However, mini-batch versions of both SGD and coordinate descent (CD) [14, 15, 37, 46, 48, 50, 51, 57, 66, 70] suﬀer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
An asynchronous parallel stochastic coordinate descent algorithm (2013, background): “Each step of AsySCD chooses an index i ∈ { 1 , 2 , . . . , n and subtracts a short, constant, positive multiple of the partial gradient ∂f/∂x i from component i of x .”
Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, background): “have been proposed [5, 11, 12, 21, 22, 23]; only a fraction of these algorithms have been analyzed in the asynchronous case.”
Mini-Batch Primal and Dual Methods for SVMs (2013, methodology): “Our safe SDCA mini-batching approach is similar to the parallel coordinate descent methods of Bradley et al. (2011) and Richt´arik & Tak´aˇc (2012), but we provide an analysis in terms of the primal SVM objective, which is the more relevant object of interest.”
Coordinate descent algorithms (2015, methodology): “Richtarik and Takac [47] describe a method for the separably regularized formulation (2), (3) in which a subset of indices S k ⊂ { 1 , 2 , . . . , n } is updated according to the formula in Algorithm 2.”
SGD: General Analysis and Improved Rates (2019, methodology): “These subsets will be selected using a random set valued map S , in the literature referred to by the name sampling (Richt´arik & Tak´aˇc, 2016; Qu & Richt´arik, 2016).”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “, [11]–[16] and references therein).”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “RCD methods were first analyzed by Lewis and Leventhal in the context of linear systems and least-squares problems [45], and later extended by several authors to more general settings, including smooth convex optimization [61], composite convex optimization [76], and parallel/subspace descent varian”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “Several recent papers, e.g., Richtárik & Takáč [9], Le Roux, Schmidt & Bach [12, 13], ShalevShwartz & Zhang [14] and Johnson & Zhang [3] proposed methods which achieve such a variancereduction effect, directly or indirectly.”
Fast distributed coordinate descent for non-strongly convex losses (2014, methodology): “It has been first introduced by Richtárik and Takáč [2] for proposing a generic approach in the convergence analysis of the Parallel Coordinate Descent Methods (PCDM).”