Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
arXiv:1506.02227
Abstract
In this work we develop a new algorithm for regularized empirical risk minimization. Our method extends recent techniques of Shalev-Shwartz [02/2015], which enable a dual-free analysis of SDCA, to arbitrary mini-batching schemes. Moreover, our method is able to better utilize the information in the data defining the ERM problem. For convex loss functions, our complexity results match those of QUARTZ, which is a primal-dual method also allowing for arbitrary mini-batching schemes. The advantage of a dual-free analysis comes from the fact that it guarantees convergence even for non-convex loss functions, as long as the average loss is convex. We illustrate through experiments the utility of being able to design arbitrary mini-batching schemes.
arXiv comment13 pages, 3 figures, 2 algorithms
References in corpus (10)
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- Proximal Stochastic Dual Coordinate Ascent
- Stochastic Optimization with Importance Sampling
- Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- SDCA without Duality
- Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- On Optimal Probabilities in Stochastic Coordinate Descent Methods
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
Cited by in corpus (12)
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- SGD: General Analysis and Improved Rates
- SDCA without Duality, Regularization, and Individual Convexity
- Stochastic, Distributed and Federated Optimization for Machine Learning
- Faster Eigenvector Computation via Shift-and-Invert Preconditioning
- Importance Sampling for Minibatches
- Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- SAGA with Arbitrary Sampling
- Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
- Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization