Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Abstract

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 $\epsilon$-accurate solution with probability at least $1-\rho$ in at most $O(\frac{n}{\epsilon }\log \frac{1}{\rho })$ iterations, where $n$ is the number of blocks. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper #2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\epsilon$ 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 true iteration complexity bounds. 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 ${\ell }_1$-regularized least squares and support vector machine problems with a billion variables.

33 pages, 7 figures, 10 tables

References in corpus (3)

• A note on the group lasso and a sparse group lasso
• On the Finite Time Convergence of Cyclic Coordinate Descent Methods
• A proximal method for composite minimization

Cited by in corpus (14)

• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Parallel Coordinate Descent Methods for Big Data Optimization
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Inexact Coordinate Descent: Complexity and Preconditioning
• A Second-Order Method for Strongly Convex L1-Regularization Problems
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Structure-Aware Dynamic Scheduler for Parallel Machine Learning