SDCA without Duality, Regularization, and Individual Convexity

2016/02/04 by Shai Shalev‐Shwartz, Shalev-Shwartz, Shai · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1602.01582

openalex publication_date 2016/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex.

Citations

• A Universal Catalyst for First-Order Optimization
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• A Lower Bound for the Optimization of Finite Sums
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Cited by

• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning

Related

• SDCA without Duality
• Linear convergence of SDCA in statistical estimation
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Analysis of Distributed Stochastic Dual Coordinate Ascent