Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption

Abstract

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.

References in corpus (4)

• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• Distributed dual gradient methods and error bound conditions
• Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

Cited by in corpus (3)

• Stochastic Dual Ascent for Solving Linear Systems
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Primal-Dual Rates and Certificates