Importance Sampling for Minibatches

By Dominik Csiba, Peter Richtárik. 2016

134 citations recorded by the source corpus.

Minibatching is a very well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling -- a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is no existing work combining the power of importance sampling with the strength of minibatching. In this paper we propose the first {\em importance sampling for minibatches} and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular datasets, and show that the improvement can reach an order of magnitude.

Subfields: Artificial Intelligence, 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

In Statistics and Probability

Citations in the corpus

Online Continual Learning on Class Incremental Blurry Task Configuration with Anytime Inference (2021, methodology): “Inspired by works on sample importance (Kloek & Van Dijk, 1978; LeCun et al., 1990; Chang et al., 2017; Katharopoulos & Fleuret, 2018; Csiba & Richt´arik, 2018), we propose a novel sampling strategy speciﬁc for CL that removes samples from the memory based on sample-wise importance as following…”
Distributed optimization with arbitrary local solvers (2015, background): “However, mini-batch versions of both SGD and coordinate descent (CD) [14, 15, 37, 46, 48, 50, 51, 57, 66, 70] suﬀer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “More generally, our work ﬁts into a recent effort to auto-mate or simplify the tuning of parameters in stochastic optimization algorithms, most notably the learning rate [23, 17].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “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.”
99% of Parallel Optimization is Inevitably a Waste of Time (2019, methodology): “Standard coordinate descent exploits a smoothness structure of objective (either via coordinate-wise smoothness constants or more generally using a smoothness matrix) in order to sample coordinates non-uniformly (Qu & Richtárik, 2016b; Csiba & Richtárik, 2018; Hanzely & Richtárik, 2018).”
Automated Inference with Adaptive Batches (2017, background): “Another conceptually related approach is importance sampling, i.e., choosing training points such that the variance in the gradient estimates is reduced (Bouchard et al., 2015; Csiba and Richtárik, 2016; Needell et al., 2014).”
FairBatch: Batch Selection for Model Fairness (2020, background): “More recently, importance sampling techniques have been proposed for faster convergence (Loshchilov and Hutter, 2016; Alain et al., 2016; Stich et al., 2017; Csiba and Richt ´ arik, 2018; Katharopoulos and Fleuret, 2018; Johnson and Guestrin, 2018).”
Advances in Variational Inference (2017, background): “Several authors suggested variants of importance sampling in the context of mini-batch selection [32], [55], [148], [226].”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, background): “Indeed, while the results in (Richtárik and Takáč, 2016a; Csiba and Richtárik, 2018; Hanzely and Richtárik, 2019) and other works on this topic construct importance sampling for minibatches, these are not shown nor believed to be optimal.”
Balanced Mini-batch Sampling for SGD Using Determinantal Point Processes (2017, background): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 33, 39, 48, 49].”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, methodology): “Alternatively, the partition may exploit some inherent substructure of the objective function such as block separability [51], the ability to efficiently solve the corresponding sub-problem (2) with respect to the blocks [81], or based on the Lipschitz constants of the resulting blocks [90, 14].”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, methodology): “[6] Dominik Csiba and Peter Richtárik.”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, background): “The recent paper [28] also considered the combination of importance sampling and mini-batching for a stochastic dual coordinate ascent algorithm in the general setting of empirical risk minimization, wherein the function to minimize is smooth and convex.”
Efficient Distributed SGD with Variance Reduction (2015, background): “, choosing training points such that the variance in the gradient estimates is reduced [7, 9, 24].”
Safe Adaptive Importance Sampling (2017, background): “Instead, randomized selection has become ubiquitous, most prominently uniform sampling [27, 29, 7, 8, 28] but also non-uniform sampling based on a ﬁxed distribution, commonly referred to as importance sampling [18, 19, 2, 33, 16, 6, 25, 24].”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, background): “Another conceptually related approach is importance sampling, i.e., choosing training points such that the variance in the gradient estimates is reduced (Bouchard et al., 2015; Csiba and Richt´arik, 2016; Needell et al., 2014).”
Stochastic Learning on Imbalanced Data: Determinantal Point Processes for Mini-batch Diversification (2017, background): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 32, 38, 47, 48].”
Coordinate Descent Face-Off: Primal or Dual? (2016, background): “The situation is much more complicated with non-serial samplings where first importance sampling results have only been derived recently [1].”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, unknown): “4 For some prior results on importance sampling for minibatches, in the context of QUARTZ, see [5].”