← Back to papers
2016 ICML ICML 2016

SDCA without Duality, Regularization, and Individual Convexity

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.

🧭 Keyword Pioneer — loss minimization
🐣 Hot Topic Early Bird — non-convex optimization
🐝 Cross-Pollinator — Artificial Intelligence, Computer Vision, Deep Learning, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Reinforcement Learning

Authors

Shai Shalev-shwartz

Topics

Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Optimization Machine Learning > Core Methods > Optimization

Keywords

non-convex optimization convex optimization strong convexity stochastic dual coordinate ascent linear convergence regularized loss minimization loss minimization
Download PDF

Related papers

Associative Long Short-Term Memory 2016
Recycling Randomness with Structure for Sublinear time Kernel Expansions 2016
Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues 2016
Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization 2016
Hawkes Processes with Stochastic Excitations 2016