Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
This work provides incremental theoretical improvements for optimization algorithms in machine learning, specifically benefiting researchers and practitioners using methods like SDCA and stochastic coordinate descent.
The paper tackles the problem of generalizing feasible descent methods to randomized and coordinate-wise variants, proving linear convergence under weak strong convexity assumptions, with results including linear convergence of the duality gap for SDCA applied to SVM duals.
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.