SDCA without Duality
This work addresses a limitation in optimization methods for machine learning practitioners by extending SDCA to non-convex settings, though it is incremental as it modifies an existing algorithm.
The paper tackles the problem of applying Stochastic Dual Coordinate Ascent (SDCA) to non-convex losses by introducing a variant that works under the condition that the expected loss is convex, and proves a linear convergence rate for this method.
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.