Linear convergence of SDCA in statistical estimation
arXiv:1701.07808
Abstract
In this paper, we consider stochastic dual coordinate (SDCA) {\em without} strongly convex assumption or convex assumption. We show that SDCA converges linearly under mild conditions termed restricted strong convexity. This covers a wide array of popular statistical models including Lasso, group Lasso, and logistic regression with regularization, corrected Lasso and linear regression with SCAD regularizer. This significantly improves previous convergence results on SDCA for problems that are not strongly convex. As a by product, we derive a dual free form of SDCA that can handle general regularization term, which is of interest by itself.
References in corpus (12)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- On the conditions used to prove oracle results for the Lasso
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
- Communication-Efficient Distributed Dual Coordinate Ascent
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
- Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
- Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
- Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
- A distributed block coordinate descent method for training regularized linear classifiers
- SAGA and Restricted Strong Convexity