Inexact Coordinate Descent: Complexity and Preconditioning
arXiv:1304.5530
Abstract
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In his work we relax this requirement, and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update as well as the use of preconditioning for further acceleration.
32 pages, 6 tables, 2 figures, 1 algorithm
References in corpus (3)
Cited by in corpus (15)
- Distributed Coordinate Descent Method for Learning with Big Data
- Parallel Coordinate Descent Methods for Big Data Optimization
- Stochastic Dual Ascent for Solving Linear Systems
- Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- Accelerated, Parallel and Proximal Coordinate Descent
- Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
- On Optimal Probabilities in Stochastic Coordinate Descent Methods
- An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
- A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
- Large-scale randomized-coordinate descent methods with non-separable linear constraints
- Robust Block Coordinate Descent
- Separable Approximations and Decomposition Methods for the Augmented Lagrangian