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

Angelos Katharopoulos; François Fleuret

Source-linked AI summary

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

Angelos Katharopoulos, François Fleuret

arXiv:1803.00942v3Mar 2, 2018cs.LG

TL;DR

Deep neural network training wastes computation on samples that become properly handled, creating a need for more selective computation. The paper introduces importance sampling based on a tractable gradient-norm upper bound and variance estimates, and reports improved training efficiency and quality across multiple tasks.

Problem
Deep neural network training is computationally costly, while many samples become properly handled and could be ignored after a few epochs.
Method
The paper derives a per-sample gradient-norm upper bound computable in one forward pass and estimates variance reduction to decide when to activate importance sampling.
Results
The method consistently reduces training loss and test error at equalized wall-clock time across image classification, fine-tuning, and recurrent sequence classification.
Takeaways & Limitations
Importance sampling can exploit unequal sample importance to obtain speedup, better-quality gradients, or both during deep network training.
Takeaways & Limitations
Computing importance scores still requires a forward pass, can waste resources early in training, and remains unsuitable for online learning when the whole dataset must be scored.

Abstract

from arXiv · show

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

1. Introduction

Deep neural network training is computationally expensive because many samples become uninformative, motivating importance sampling that prioritizes examples likely to change parameters. The proposed scheme uses a tractable gradient-norm upper bound, estimates variance reduction, and improves training under equal wall-clock time.

Deep network training has become computationally costly as model optimization grows more complex.
Many samples are properly handled after a few epochs and can often be ignored without affecting the final model.
The proposed importance sampling scheme focuses computation on samples expected to cause the largest parameter changes, reducing gradient-estimate variance.
The method derives a per-sample gradient-norm upper bound computable in one forward pass and uses variance estimates to determine when sampling is useful.It also provides theoretical speedup guarantees when variance reduction exceeds a threshold.
The generic implementation can be added to a standard Keras model with a single line of code.
Across image classification, fine-tuning, and recurrent sequence classification, the method achieves lower training loss and test error at equalized wall-clock time.

2. Related Work

Prior importance-sampling work spans convex optimization and deep learning, but deep networks lack simple importance measures and direct gradient-based sampling can be expensive. This paper positions its gradient-norm upper-bound scheme as easier to tune, theoretically grounded, and broadly applicable.

2.1. Importance Sampling for Convex Problems: Importance sampling for convex optimization has been extensively studied through methods such as LASVM and generalized coordinate descent.
2.1. Importance Sampling for Convex Problems: For convex stochastic optimization, the optimal sampling distribution is proportional to per-sample gradient norms, while simpler methods use input norms in linear classification.
2.2. Importance Sampling for Deep Learning: Deep learning lacks equally simple importance measures, and directly applying gradient-based sampling can require clusters of GPU workers to compute the distribution.
2.2. Importance Sampling for Deep Learning: Deep-learning sampling methods have used manually designed curricula, hard examples, or loss-based distributions built from histories of previously seen samples.
2.2. Importance Sampling for Deep Learning: History-based sampling requires many hyperparameters because model updates make stale importance scores poor reflections of current sample importance.
2.2. Importance Sampling for Deep Learning: The proposed upper-bound scheme is presented as theoretically grounded, easy to tune, guaranteed to speed up under stated conditions, and applicable across networks and loss functions.

3. Variance Reduction for Deep Neural Networks

Importance sampling reduces stochastic-gradient variance by sampling according to tractable per-sample importance estimates, while a variance-based criterion determines when the extra computation is worthwhile. The resulting pre-sample-and-resample procedure integrates into SGD and targets speedups under fixed computational cost.

Importance sampling focuses computation on samples that induce larger parameter changes, reducing gradient-estimate variance for a fixed computational cost.
The optimal sampling distribution is proportional to per-sample gradient norms, but computing those norms directly is computationally prohibitive.
A tractable upper bound to each per-sample gradient norm can be computed from the final-layer pre-activation output and used to construct importance scores.The bound is only marginally harder to compute than the loss, but it changes with the training step as model parameters change.
The algorithm pre-samples B datapoints, computes their importance scores, and resamples a batch of b points with replacement using importance weights.Importance sampling begins after the estimated equivalent batch-size increment exceeds τth; before then, the procedure uses uniform SGD sampling.
The pre-sampling procedure has a maximum variance reduction of 1/B and a maximum speedup of (B+3b)/(3B) when the backward pass takes twice the forward-pass time.These bounds apply to a large batch of B samples followed by a smaller batch of b samples.
Variance reduction is measured through the distance between the importance distribution and the uniform distribution, then expressed as an equivalent batch-size increase.This provides a criterion for activating importance sampling only when its variance reduction justifies the computational cost.

4. Experiments

Experiments compare the proposed upper-bound importance sampling with uniform and loss-based sampling across gradient variance, image classification, fine-tuning, and recurrent sequence classification. The method generally improves wall-clock convergence and test performance, while loss-based sampling can increase variance or hurt convergence.

Gradient variance: The upper-bound and true-gradient-norm samplers achieve very similar variance reduction, indicating that the upper bound is relatively tight.Their sampling probabilities are highly correlated, whereas sampling high-loss examples increases variance, especially early in training.
Image classification: On CIFAR10, the proposed method achieves more than an order of magnitude lower training loss and 8% lower test error, from 0.087 to 0.079, than uniform sampling.All methods provide some speedup on this relatively easy dataset, but the proposed method is the only one with a significant early test-error improvement.
Image classification: Using fresh loss values with a warmup stage outperforms the other loss-based batch-selection baselines on CIFAR10.The warmup prevents importance sampling from starting too early.
Pixel by Pixel MNIST: On pixel-by-pixel MNIST with an LSTM, the proposed algorithm achieves 20% lower training loss and 7% lower test error, while loss-proportional sampling hurts convergence.Importance sampling begins around 2,000 seconds under the reported threshold and presampling settings.

5. Conclusions

The paper presents an efficient importance-sampling algorithm that uses gradient-norm bounds and variance analysis to accelerate deep-network training. Experiments show reduced training time across image and sequence tasks, while future work includes adapting learning rates and batch sizes using gradient variance.

5. Conclusions: A single-forward-pass upper bound to the gradient norm supports efficient importance sampling for deep neural networks.The method also relates variance reduction to increasing batch size, enabling speedup estimation and a decision about when to stop uniform sampling.
5. Conclusions: Importance sampling reduces training time across several tasks involving image and sequence data.The experiments exploit unequal sample importance to obtain faster training, better-quality gradients, or both.
5. Conclusions: Future work includes automatically tuning learning rates from gradient variance and investigating smaller batch sizes.The analysis suggests that increasing the learning rate or reducing backward-pass computations could accelerate convergence while maintaining gradient-variance stability.

A. Differences of variances

This section quantifies the variance reduction from importance sampling using per-sample gradient norms and a uniform-sampling probability.

A. Differences of variances: The analysis defines sample importance as proportional to the squared per-sample gradient norm.The gradient norm is expressed through the loss gradient with respect to the network output.
A. Differences of variances: Uniform sampling is represented by probability 1/B in the variance comparison.This provides the baseline against which importance-sampling variance is evaluated.
A. Differences of variances: Completing the squares and using the uniform-probability identity yields the variance analysis for comparing sampling schemes.The supplied derivation fragment identifies these algebraic steps as part of the comparison.

B. An upper bound to the gradient norm

The paper derives an upper bound on each sample’s gradient norm for fully connected networks, using forward-pass quantities and the final-layer loss gradient.

B. An upper bound to the gradient norm: The derivation analyzes a fully connected neural network without bias to obtain a closed-form parameter-gradient expression.The network uses layer weight matrices and Lipschitz-continuous activation functions.
B. An upper bound to the gradient norm: The gradient with respect to network parameters is constructed by propagating the loss gradient backward from the final layer through each layer.The derivation separately defines gradients at the network output, layer outputs, activation functions, and parameters.
B. An upper bound to the gradient norm: The analysis assumes that weight initialization and activation normalization reduce activation variation across samples.Under this premise, intermediate quantities are treated as insufficient to capture the important per-sample gradient-norm variation.
B. An upper bound to the gradient norm: The derivation obtains per-layer bounds and combines them into a final upper bound for the per-sample gradient norm.The bound is motivated by experimentally observed gradient-norm behavior in the referenced analysis.
B. An upper bound to the gradient norm: The final-layer pre-activation loss gradient serves as an upper bound for the per-sample gradient norm.The paper argues that gradient-norm variations are mostly captured by the final classification layer, allowing this quantity to be computed in one forward pass.

C. Comparison with SVRG methods

The paper compares its importance-sampling approach with stochastic variance-reduced gradient methods on augmented CIFAR-10 and CIFAR-100. With tuned hyperparameters, SGD with momentum performs significantly better than the evaluated SVRG-based methods.

C. Comparison with SVRG methods: The comparison evaluates SVRG, Katyusha, and SCSG alongside SGD with momentum on augmented CIFAR-10 and CIFAR-100.Learning rates and update-related hyperparameters are tuned for all methods, with additional batch parameters tuned for SCSG.
C. Comparison with SVRG methods: SGD with momentum performs significantly better than all evaluated SVRG methods.Full-batch SVRG and Katyusha make few parameter updates and fail to optimize the networks in the reported experiments.

D. Ablation study on B

The presampling size B controls both potential variance reduction and the wall-clock cost of importance-sampling iterations. Larger B lowers training loss, while B = kb with 2 < k < 6 is recommended for speedup when paired with the analysis-based threshold.

Role of B: B controls both maximum variance reduction and the wall-clock time required for each importance-sampling iteration.Thus, increasing B trades additional computation per iteration for greater potential variance reduction.
Effect of B: Larger presampling sizes produce lower training loss because small B limits maximum variance reduction.The experiment found that B = 384 reached 0.6 training loss first.
Effect of B: B = 384 reaches 0.6 training loss first in the CIFAR10 ablation.The same threshold τth was used for all methods.
Practical choice: Choosing B = kb with 2 < k < 6 is reported as a good strategy for achieving speedup.Pairing B with the analysis-designated threshold τth restricts importance sampling to cases where variance can be greatly reduced.

E. Importance Sampling with the Loss

The paper examines whether loss can guide importance sampling as a proxy for per-sample gradient norms. Small losses imply small gradients, but large losses are poorly correlated with gradient norms, limiting loss-based variance reduction when most samples remain difficult.

Analysis: The analysis investigates using loss as an approximation or upper bound for the per-sample gradient norm.It considers negative log-likelihood and squared-error losses.
Gradient relationship: Small loss values imply small per-sample gradients for the losses considered.As L(ψ, y) approaches zero, the per-sample gradient norm also approaches zero.
Practical implication: Sampling proportionally to loss is conjectured to reduce variance mainly when most samples have losses close to zero.Experiments found that loss-based sampling struggles to achieve speedup early in training, when most losses remain relatively large.