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.

ICML 2016

References in corpus (9)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Lower Bound for the Optimization of Finite Sums
• SDCA without Duality
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• New Optimisation Methods for Machine Learning

Cited by in corpus (19)

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Supervised Learning Under Distributed Features
• SGD: General Analysis and Improved Rates
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction
• MISO is Making a Comeback With Better Proofs and Rates
• Non-convex Conditional Gradient Sliding
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
• Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
• The Lingering of Gradients: Theory and Applications
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning