SDCA without Duality

2015/02/22 by Shai Shalev-Shwartz, Shalev-Shwartz, Shai
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.LG

paper · pdf · doi:10.48550/arxiv.1502.06177

arxiv created 2015/02/22 · arxiv updated 2015/02/24

Abstract

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. In this paper we show how a variant of SDCA can be applied for non-convex losses. We prove linear convergence rate even if individual loss functions are non-convex as long as the expected loss is convex.

Related

• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Linear convergence of SDCA in statistical estimation
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Proximal Stochastic Dual Coordinate Ascent