SDCA without Duality
arXiv:1502.06177
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.
References in corpus (1)
Cited by in corpus (23)
- Stochastic Variance Reduction for Nonconvex Optimization
- Variance Reduction for Faster Non-Convex Optimization
- Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
- Fast and Simple PCA via Convex Optimization
- Faster Eigenvector Computation via Shift-and-Invert Preconditioning
- Stochastic, Distributed and Federated Optimization for Machine Learning
- SDCA without Duality, Regularization, and Individual Convexity
- Fast Incremental Method for Nonconvex Optimization
- Importance Sampling for Minibatches
- On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
- Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
- Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
- Primal-Dual Rates and Certificates
- Riemannian stochastic variance reduced gradient on Grassmann manifold
- Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
- Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
- A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
- MISO is Making a Comeback With Better Proofs and Rates
- Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
- Structured and Localized Image Restoration
- Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
- Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
- Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization