Accelerated, Parallel, and Proximal Coordinate Descent

By Olivier Fercoq, Peter Richtárik. 2013

390 citations recorded by the source corpus.

We propose a new randomized coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel, and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate $2\bar{\omega}\bar{L} R^2/(k+1)^2 $, where $k$ is the iteration counter, $\bar{\omega}$ is a data-weighted average degree of separability of the loss function, $\bar{L}$ is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and $R$ is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of accelerated coordinate descent. The fact that the method depends on the average degree of separability, and not on the maximum degree...

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

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “Mini-batch CD (for lasso) and SDCA (for SVM) aim to improve mini-batch SGD by employing coordinate descent, which has theoretical and practical justiﬁcations (Shalev-Shwartz and Tewari, 2011; Takáč et al., 2015; Fercoq and Richtárik, 2015; Tappenden et al., 2015; Takáč et al., 2013).”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “Methods of this type, in various settings, were studied by several authors, including Hsieh et al. (2008); Shalev-Shwartz and Tewari (2009); Nesterov (2012); Richtárik and Takáč (2014); Necoara et al.”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “The asynchronous parallel optimization recently received many successes and broad attention in machine learning and optimization [Niu et al., 2011, Li et al., 2013, 2014b, Yun et al., 2013, Fercoq and Richtárik, 2013, Zhang and Kwok, 2014, Marecek et al., 2014, Tappenden et al., 2015, Hong, 2014].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “All of these three properties were connected in a single algorithm in [35], to which we refer the reader for a review of the early developments in the area of RCD, particularly to overview in Table 1 therein.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “…& Tak´aˇc, 2014; 2013b; 2012; Tappenden et al., 2015; Mareˇcek et al., 2014; Fercoq & Richt´arik, 2013; Lu & Xiao, 2013; Fercoq et al., 2014; Qu & Richt´arik, 2014; Qu et al., 2014) (Efﬁcient accelerated variants were considered in (Fercoq & Richt´arik, 2013; Shalev-Shwartz & Zhang, 2013a)).”
Distributed optimization with arbitrary local solvers (2015, methodology): “e online at: https://github.com/optml/CoCoA. Table 3. Local solvers used in numerical experiments. RCDM Randomized Coordinate Descent [44] APPROX Accelerated, Parallel and Proximal Coordinate Descent [17] GD Gradient Descent with Backtracking Line Search [39] CG Conjugate Gradient Method [21] L-BFGS”
Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, positive): “They have also analyzed asynchronous versions of other stochastic algorithms, such as stochastic coordinate descent (SGD) [14, 15] and accelerated parallel proximal coordinate descent (APPROX) [6], producing rate results that are similar to those of HOGWILD!”
Coordinate descent algorithms (2015, methodology): “Another variant of this implementation technique appears in [16, Section 5].”
Fast distributed coordinate descent for non-strongly convex losses (2014, methodology): “The same idea has been extended to the analysis of many variants of PCDM, including the Accelerated Coordinate Descent algorithm [4] (APPROX) and the Distributed Coordinate Descent method [3] (Hydra).”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, neutral): “ that designing accelerated methods for coordinate descent is signicantly easier than designing that for stochastic gradient descent, and this has indeed been done in many previous results including [7, 12, 18, 20, 21, 26]. 4 The state-of-the-art accelerated coordinate descent method is NUACDM [7] L”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, methodology): “If R2 = O(1) then the runtime of our method is better than that of [22] and [11].”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “For more information about modern dual and primal methods we refer the reader to the literature on randomized coordinate descent methods [8], [9], [10], [11], [12], [5], [13], [14], [15], [16], [17], [18] and stochastic gradient methods [4], [19], [20], [21], [22], [23], [17], [24], respectively.”
Semi-stochastic coordinate descent (2014, neutral): “Note that the standard SGD method does not have this property: indeed, there is no reason for E i (cid:6)∇ f i ( x ) 2 to be small even if x = x ∗ .”
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions (2014, methodology): “Distributed coordinate descent methods were developed and studied recently by Richtárik and Takáč [23] (algorithm: Hydra) and Fercoq et al. [4] (Algorithms: Hydra2).”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, background): “This approach leads to state of the art algorithms for several problems [11, 18, 19, 24, 29, 30].”