Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
By Dominik Csiba, Peter Richtárik. 2015
23 citations recorded by the source corpus.
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 dening 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.
Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Peter Richtárik
- Jakub Konecný
- Samuel Horváth
- Dmitry Kovalev
- Dominik Csiba
- Nicolas Loizou
- Filip Hanzely
- Martin Takác
In Computational Mechanics
- Peter Richtárik
- Jakub Konecný
- Dominik Csiba
- Samuel Horváth
- Dmitry Kovalev
- Nicolas Loizou
- Martin Takác
- Zheng Qu
In Statistics and Probability
- Jakub Konecný
- Samuel Horváth
- Peter Richtárik
- Dmitry Kovalev
- Dominik Csiba
- Filip Hanzely
- Nicolas Loizou
- Martin Takác
Citations in the corpus
- SGD: General Analysis and Improved Rates (2019, neutral): “…(Hanzely & Richt´arik, 2018), coordinate and accelerated descent for convex functions (Qu & Richt´arik, 2016), primal-dual methods (Qu et al., 2015; Chambolle et al., 2018), variance-reduced methods with convex (Csiba & Richt´arik, 2015) and nonconvex (Horv´ath & Richt´arik, 2018) objectives.”
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, neutral): “…et al., 2012; Johnson & Zhang, 2013; Shalev-Shwartz & Zhang, 2013; Defazio et al., 2014; Qu et al., 2015; Shalev-Shwartz, 2016; Qu et al., 2016; Csiba & Richtárik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zhou, 2018) admit linear convergence on empirical risk…”
- Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) [151, 149, 164, 111, 188, 176, 150, 140, 141, 143, 38, 40] suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
- Importance Sampling for Minibatches (2016, methodology): “This method is a primal variant of SDCA, first analyzed by Shalev-Shwartz [30], and extended by Csiba and Richt´arik [2] to the arbitrary sampling setting.”
- Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “An exception to this is dfSDCA [5]; however, this method applies to an explicitly regularized version of (1), and while the individual functions are allowed to be non-convex, the average f is assumed to be convex.”
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017)…”