Not All Samples Are Created Equal: Deep Learning with Importance Sampling

By Angelos Katharopoulos, Franccois Fleuret. 2018

663 citations recorded by the source corpus.

Deep neural network training spends most of the computation on examples that are properly handled, and could be ignored. We propose to mitigate this phenomenon with a principled importance sampling scheme that focuses computation on "informative" examples, and reduces the variance of the stochastic gradients during training. Our contribution is twofold: first, we derive a tractable upper bound to the per-sample gradient norm, and second we derive an estimator of the variance reduction achieved with importance sampling, which enables us to switch it on when it will result in an actual speedup. The resulting scheme can be used by changing a few lines of code in a standard SGD procedure, and we demonstrate experimentally, on image classification, CNN fine-tuning, and RNN training, that for a fixed wall-clock time budget, it provides a reduction of the train losses of up to an order of magnitude and a relative improvement of test errors between 5% and 17%.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

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 Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Natural Compression for Distributed Deep Learning (2019, background): “[25] Angelos Katharopoulos and François Fleuret.”
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…”
Online Coreset Selection for Rehearsal-based Continual Learning (2021, positive): “Importance sampling [13, 14, 38] strengthens the loss/gradients of important samples based on influence functions.”
An Empirical Study of Example Forgetting during Deep Neural Network Learning (2018, background): “Zhao & Zhang (2015); Katharopoulos & Fleuret (2018) relate sample importance to the norm of its loss gradient with respect to the parameters of the network.”
Meta Learning on a Sequence of Imbalanced Domains with Difficulty Awareness (2021, neutral): “Following [30, 1], it can be expressed as: Theorem 2 illustrates the optimal task sampling distribution for reducing the gradient variance is proportional to the per-task gradient norm.”
Regret Minimization Experience Replay in Off-Policy Reinforcement Learning (2021, background): “Previous work [8] points out that emphasizing on important samples in the replay buffer can benefit off-policy RL algorithms.”
Dice Loss for Data-imbalanced NLP Tasks (2019, background): “Oversampling (Chen et al., 2010; Chawla et al., 2002) (Chang et al., 2017; Katharopoulos and Fleuret, 2018) adjusted the weights of different training examples based on training loss.”
Data Selection for Language Models via Importance Resampling (2023, positive): “Following RoBERTa [48],”
Learning Data Manipulation for Augmentation and Weighting (2019, methodology): “Data weighting has been used in various algorithms, such as AdaBoost [10], self-paced learning [27], hard-example mining [43], and others [4, 22].”
Learning to Reweight with Deep Interactions (2021, methodology): “The idea of adjusting weights for the data is also essential in another line of research about combing optimizers with different sampling techniques (Katharopoulos and Fleuret 2018; Liu, Wu, and Mozafari 2020; Namkoong et al. 2017).”
Towards Understanding Biased Client Selection in Federated Learning (2022, background): “Another relevant line of work (Jiang et al., 2019; Katharopoulos and Fleuret, 2018; Shah et al., 2020; Salehi et al., 2018) employs importance sampling of data to speed-up convergence of centralized SGD.”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “Another relevant line of work [28–31] employs biased selection or importance sampling of data to speed-up convergence of classic centralized SGD – they propose preferentially selecting samples with highest loss or highest gradient norm to perform the next SGD iteration.”
GPU accelerated t-distributed stochastic neighbor embedding (2019, methodology): “In order to validate this, we computed the importance scores for each point using the algorithm given by Katharopoulos and Fleuret [57].”
Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics (2022, background): “Meanwhile, loss-based prioritization [28, 31] techniques essentially do the opposite – these techniques upweight high loss examples, assuming these examples are challenging yet learnable.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “Importance sampling [1, 12, 30], uses only a subset of the dataset in each epoch to save on computation.”
Training Deep Models Faster with Robust, Approximate Importance Sampling (2018, methodology): “[5] approximates importance values using additional forward passes.”
BackPACK: Packing more into backprop (2019, background): “…the batch has been found to be theoretically and practically useful for adapting hyperparameters like learning rates (Mahsereci & Hennig, 2017) and batch sizes (Balles et al., 2017), or regularize ﬁrst-order optimization (Le Roux et al., 2007; Balles & Hennig, 2018; Katharopoulos & Fleuret, 2018).”