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.
13 pages, 3 figures, 2 algorithms
References in corpus (6)
- Proximal 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
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
Cited by in corpus (5)
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- Stochastic, Distributed and Federated Optimization for Machine Learning
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- SAGA with Arbitrary Sampling