Title: Linear convergence of SDCA in statistical estimation,
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 $\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.