Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
This provides theoretical justification for SDCA's effectiveness in large-scale supervised machine learning applications like SVM, though it is incremental as it builds on existing methods.
The paper tackles the lack of convergence analysis for Stochastic Dual Coordinate Ascent (SDCA) methods in regularized loss minimization, showing that SDCA achieves strong theoretical guarantees comparable or better than Stochastic Gradient Descent (SGD).
Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications.