Linear convergence of SDCA in statistical estimation
This provides a theoretical improvement for optimization in statistical estimation, addressing a known bottleneck in convergence analysis for non-strongly convex problems, but it is incremental as it builds on prior SDCA results.
The paper tackles the problem of proving linear convergence for Stochastic Dual Coordinate Ascent (SDCA) without requiring strong convexity, showing that it converges linearly under mild restricted strong convexity conditions, which applies to models like Lasso and logistic regression with ℓ1 regularization.
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 $\ell_1$ 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.