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

Abstract

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%.

arXiv commentAccepted at ICML 2018 (short oral)

References in corpus (10)

• Adam: A Method for Stochastic Optimization
• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Prioritized Experience Replay
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Simple Way to Initialize Recurrent Networks of Rectified Linear Units
• Online Batch Selection for Faster Training of Neural Networks
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Variance Reduction in SGD by Distributed Importance Sampling
• Learning What Data to Learn
• On Optimal Probabilities in Stochastic Coordinate Descent Methods

Cited by in corpus (36)

• Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval
• Optimal Client Sampling for Federated Learning
• SelectNet: Self-paced Learning for High-dimensional Partial Differential Equations
• Natural Compression for Distributed Deep Learning
• ResKD: Residual-Guided Knowledge Distillation
• Learning nonlocal constitutive models with neural networks
• Faster Neural Network Training with Data Echoing
• Dice Loss for Data-imbalanced NLP Tasks
• Federated Few-Shot Learning for Mobile NLP
• Semantic Redundancies in Image-Classification Datasets: The 10% You Don't Need
• Using Small Proxy Datasets to Accelerate Hyperparameter Search
• Choosing the Sample with Lowest Loss makes SGD Robust
• Angular Visual Hardness
• In Defense of the Triplet Loss Again: Learning Robust Person Re-Identification with Fast Approximated Triplet Loss and Label Distillation
• Empirical study towards understanding line search approximations for training neural networks
• Computation-Efficient Knowledge Distillation via Uncertainty-Aware Mixup
• AutoAssist: A Framework to Accelerate Training of Deep Neural Networks
• Adaptive Task Sampling for Meta-Learning
• Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
• Modern Subsampling Methods for Large-Scale Least Squares Regression
• Revisiting Prioritized Experience Replay: A Value Perspective
• Weighting Is Worth the Wait: Bayesian Optimization with Importance Sampling
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• A Simple Non-i.i.d. Sampling Approach for Efficient Training and Better Generalization
• Selective sampling for accelerating training of deep neural networks
• Margin-Based Regularization and Selective Sampling in Deep Neural Networks
• When does loss-based prioritization fail?
• Adam with Bandit Sampling for Deep Learning
• Investigating the Compositional Structure Of Deep Neural Networks
• ALLWAS: Active Learning on Language models in WASserstein space
• Submodular Batch Selection for Training Deep Neural Networks
• Uniform Sampling over Episode Difficulty
• Learning to Reweight with Deep Interactions
• Stochastic Doubly Robust Gradient
• Large Batch Experience Replay
• Scheduling and Power Control for Wireless Multicast Systems via Deep Reinforcement Learning