Large-scale randomized-coordinate descent methods with non-separable linear constraints
arXiv:1409.2617
Abstract
We develop randomized (block) coordinate descent (CD) methods for linearly constrained convex optimization. Unlike most CD methods, we do not assume the constraints to be separable, but let them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making the global iteration complexity have an exponential dependence on the number of constraints. We present algorithms and analysis for four key problem scenarios: (i) smooth; (ii) smooth + nonsmooth separable; (iii) asynchronous parallel; and (iv) stochastic. We illustrate empirical behavior of our algorithms by simulation experiments.
References in corpus (10)
- Pathwise coordinate optimization
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
- Parallel Coordinate Descent for L1-Regularized Loss Minimization
- Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
- Parallel Coordinate Descent Methods for Big Data Optimization
- Accelerated, Parallel and Proximal Coordinate Descent
- Iteration Complexity Analysis of Block Coordinate Descent Methods
- Inexact Coordinate Descent: Complexity and Preconditioning
- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods