Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

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

819 citations recorded by the source corpus.

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-accurate solution with probability at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-\rho $$\end{document} in at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((n/\varepsilon ) \log (1/\rho ))$$\end{document} iterations, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341–362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document} from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document}-regularized least squares problems with a billion variables.

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

Citations in the corpus

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “We ﬁrst show that our algorithm can be seen as an instance of proximal coordinate descent (PCD) (Tseng and Yun, 2009; Richt´arik and Tak´ac, 2014) on a slightly modiﬁed objective function.”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “These approaches can be combined, and theory was developed for methods that update a random subset of blocks of coordinates at a time (Richt´arik & Tak´aˇc, 2012a; Fercoq & Richt´arik, 2013).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “Numerous follow-up works extended the concept to proximal setting [79], single processor parallelism [15, 80] and develop efficiently implementable acceleration [51].”
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, methodology): “Inexact Block Coordinate Descent.”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “But importance sampling has also been considered in stochastic coordinate-descent methods [33, 40].”
Mini-Batch Primal and Dual Methods for SVMs (2013, background): “…by considering the dual problem (2) as an ℓ1-regularized, box-constrained quadratic problem, it is possible to obtain guarantees on the dual suboptimality, D(α∗) − D(α(t)), after a finite number of SDCA iterations (Shalev-Shwartz & Tewari, 2011; Nesterov, 2012; Richtárik & Takáč, 2013).”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “Such weighted sampling schemes have also been proposed for the Prox-SDCA method [35], as well as for coordinate descent methods [24, 26, 18].”
A Universal Catalyst for First-Order Optimization (2015, methodology): “We first show how to accelerate full gradient and randomized c oordinate descent algorithms [21].”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “Complexity results for stochastic coordinate descent methods are also typically analyzed in the high probability regime [3].”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, neutral): “The related randomized coordinate descent method has been investigated by some other authors [8, 10, 17].”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, neutral): “A different line of methods is that of (primal) coordinate descent methods, and their parallel and distributed variants [13, 14, 18, 21, 22].”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, neutral): “One can also apply the analysis of stochastic coordinate descent methods given in Richtárik and Takáˇc [19] on the dual problem.”