Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
arXiv:1511.07294
Abstract
We consider convex-concave saddle point problems with a separable structure and non-strongly convex functions. We propose an efficient stochastic block coordinate descent method using adaptive primal-dual updates, which enables flexible parallel optimization for large-scale problems. Our method shares the efficiency and flexibility of block coordinate descent methods with the simplicity of primal-dual methods and utilizing the structure of the separable convex-concave saddle point problem. It is capable of solving a wide range of machine learning applications, including robust principal component analysis, Lasso, and feature selection by group Lasso, etc. Theoretically and empirically, we demonstrate significantly better performance than state-of-the-art methods in all these applications.
Accepted by AAAI 2016
References in corpus (5)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- On the Linear Convergence of the Alternating Direction Method of Multipliers
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
- Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems
- OSGA: A fast subgradient algorithm with optimal complexity