Linear Convergence of the Randomized Feasible Descent Method Under the
  Weak Strong Convexity Assumption
  In this paper we generalize the framework of the feasible descent method
(FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent
method (RC-FDM) framework. We show that the famous SDCA algorithm for
optimizing the SVM dual problem, or the stochastic coordinate descent method
for the LASSO problem, fits into the framework of RC-FDM. We prove linear
convergence for both R-FDM and RC-FDM under the weak strong convexity
assumption. Moreover, we show that the duality gap converges linearly for
RC-FDM, which implies that the duality gap also converges linearly for SDCA
applied to the SVM dual problem.
