Smooth minimization of nonsmooth functions with parallel coordinate descent methods
Preprint
Abstract
We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss ("AdaBoost problem"). We assume the input data defining the loss function is contained in a sparse $m\times n$ matrix $A$ with at most $\omega$ nonzeros in each row. Our methods need $O(n \beta/\tau)$ iterations to find an approximate solution with high probability, where $\tau$ is the number of processors and $\beta = 1 + (\omega-1)(\tau-1)/(n-1)$ for the fastest variant. The notation hides dependence on quantities such as the required accuracy and confidence levels and the distance of the starting iterate from an optimal point. Since $\beta/\tau$ is a decreasing function of $\tau$, the method needs fewer iterations when more processors are used. Certain variants of our algorithms perform on average only $O(\nnz(A)/n)$ arithmetic operations during a single iteration per processor and, because $\beta$ decreases when $\omega$ does, fewer iterations are needed for sparser problems.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Parallel coordinate descent methods for big data optimizationMathematical Programming, 2015
- On the complexity analysis of randomized block-coordinate descent methodsMathematical Programming, 2014
- Separable approximations and decomposition methods for the augmented LagrangianOptimization Methods and Software, 2014
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraintsComputational Optimization and Applications, 2013
- Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: Application to distributed MPCJournal of Process Control, 2013
- Parallel Boosting with MomentumLecture Notes in Computer Science, 2013
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionMathematical Programming, 2012
- Randomized Methods for Linear Constraints: Convergence Rates and ConditioningMathematics of Operations Research, 2010
- Logistic Regression, AdaBoost and Bregman DistancesMachine Learning, 2002
- On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex OptimizationMathematics of Operations Research, 1995