Source-linked AI summary
Accelerating Deep Learning by Focusing on the Biggest Losers
Angela H. Jiang, Daniel L. -K. Wong, Giulio Zhou, David G. Andersen, Jeffrey Dean, Gregory R. Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary C. Lipton, Padmanabhan Pillai
TL;DR
Training expends equal effort on examples that may already be learned, motivating a method that prioritizes high-loss examples. Selective-Backprop uses forward-pass losses to skip low-loss backward passes, and Stale-SB reuses recent losses to reduce selection overhead. Across datasets and models, the methods accelerate convergence to target errors versus standard SGD and a state-of-the-art importance-sampling approach.
Problem
Training typically apportions computational effort equally across examples even when some are already classified accurately and contribute little.
Method
Selective-Backprop uses forward-pass loss as a proxy for gradient value, probabilistically skipping low-loss backward passes; Stale-SB reuses recent losses for selection.
Results
Across CIFAR10, CIFAR100, and SVHN, Selective-Backprop reaches target errors up to 3.5x faster than standard SGD and 1.02–1.8x faster than state-of-the-art importance sampling.
Takeaways & Limitations
Selective-Backprop is lightweight, broadly applicable to DNN training, and can further reduce training time by 26% with stale loss information.
Takeaways & Limitations
With 20% label corruption, Selective-Backprop overfits incorrect labels and increases final test error, making it most effective on relatively clean, validated datasets.
Abstract
from arXiv · showhide
This paper introduces Selective-Backprop, a technique that accelerates the training of deep neural networks (DNNs) by prioritizing examples with high loss at each iteration. Selective-Backprop uses the output of a training example's forward pass to decide whether to use that example to compute gradients and update parameters, or to skip immediately to the next example. By reducing the number of computationally-expensive backpropagation steps performed, Selective-Backprop accelerates training. Evaluation on CIFAR10, CIFAR100, and SVHN, across a variety of modern image models, shows that Selective-Backprop converges to target error rates up to 3.5x faster than with standard SGD and between 1.02--1.8x faster than a state-of-the-art importance sampling approach. Further acceleration of 26% can be achieved by using stale forward pass results for selection, thus also skipping forward passes of low priority examples.
1 INTRODUCTION
Selective-Backprop reallocates training effort toward high-loss examples, skipping low-value backward passes to accelerate convergence. Stale-SB further reduces selection overhead by reusing recent loss information.
- Training examples are not equally useful: well-classified, redundant examples may contribute little, while misclassified examples may deserve more computation.
- Selective-Backprop uses forward-pass loss as a cheap proxy for gradient norm and probabilistically skips backward passes for low-loss examples.
- ≈70% fewer backpropagations cut overall training time in half in one experiment, while broader evaluations show speeds up to 3.5x to target errors.
- Stale-SB reuses recent forward-pass results for selection, avoiding approximately half of forward passes and reducing training time by 26% relative to Selective-Backprop for n=3.
- Both methods require minimal protocol changes and work with data augmentation, cutout, dropout, and batch normalization across varied configurations.
- Selective-Backprop and Stale-SB reduce target-error training times by up to 3.5x and 5x, respectively, versus traditional training.
2 RELATED WORK
Related work accelerates neural-network training by biasing example selection, including importance sampling and curriculum-learning strategies. The paper positions Selective-Backprop alongside fully online importance sampling while comparing against that approach empirically.
- Importance-sampling methods bias selection toward examples likely to produce larger updates, often sampling rare examples more frequently.
- Katharopoulos and Fleuret’s fully online approach uses extra forward passes and current network state, like Selective-Backprop, but predetermines the number of selected examples per
- Curriculum-learning approaches differ in whether they emphasize easy examples early, difficult examples, rare examples, or marginal examples.
3 LOSS-BASED SAMPLING WITH SELECTIVE-BACKPROP
Selective-Backprop accelerates SGD by using forward-pass losses to prioritize high-loss examples and reduce backward computation. It further reduces selection overhead by reusing stale losses, while preserving useful gradient information better than random subsampling.
- Selective-Backprop: Selective-Backprop selects examples with probability based on current forward-pass loss, forming non-uniform batches while traversing the training set.A forward pass produces each loss; examples are probabilistically included for gradient updates until a batch is formed.
- Selective-Backprop: Higher-loss examples are sampled more often, while low-loss examples are sampled less frequently to suppress updates that contribute little.The selection probability is a monotonically increasing function of an approximate recent-loss CDF.
- Gradient information: Over 80% of gradient-weight signs remain unchanged when only the highest-loss 10% of data are subsampled, and their gradients are more cosine-similar to full-batch gradients than random subsamples.These measurements support retaining informative gradient directions while reducing the number of processed examples.
- Reducing selection overhead: Selective-Backprop reduces backward-pass computation, while selection passes become the largest remaining training-time cost.The method targets the backward pass first, motivating additional techniques for reducing forward passes used only for selection.
- Reducing selection overhead: Stale-SB performs selection passes every nth epoch and reuses previous losses between them, typically reducing selection cost without impacting final accuracy.Only batch formation uses reused losses; selected examples still receive up-to-date forward passes for training.
- Reducing selection overhead: Predicted-loss approaches did not outperform the simpler Stale-SB method, while pipelined selection introduces synchronization overhead and a staleness trade-off.A separate selection model could mask delays, but it must periodically synchronize with the training model.
4 IMPLEMENTATION DETAILS
Selective-Backprop adds a lightweight filtering stage that selects examples before the original training code processes them. Its implementation minimizes changes to existing code, while some duplicated forward passes remain an optimization opportunity.
- Implementation: The prototypes were built for PyTorch 0.4.1 and Keras 2.2.4, with evaluation based on the PyTorch implementation.
- Filtering: Filtering computes each example’s loss during a forward pass, estimates its loss percentile, and probabilistically adds it to the training minibatch.The filtering mechanism uses a bounded queue to track losses and calculate selection probabilities.
- Training integration: Selection minibatches undergo forward passes, after which selected examples form training minibatches passed to the original training code.This separation keeps the training code agnostic to SB’s filtering mechanism.
- Implementation: The implementation performs two forward passes for each selected example, leaving activation caching as a potential optimization.Caching selection-pass activations could avoid the extra training forward pass.
5 EVALUATION
Evaluation across modern image-classification models and CIFAR10, CIFAR100, and SVHN shows that Selective-Backprop reduces iterations and wall-clock time to target error, with further gains from Stale-SB. The speedups depend on dataset difficulty, selectivity, and label quality, while SB generally preserves or improves performance on challenging examples.
- 5.2 Selective-Backprop speeds up training: SB reaches nearly every test-error value with significantly fewer training iterations than Traditional.Training iterations are measured as updates to the network, and savings vary with the selected target error.
- 5.2 Selective-Backprop speeds up training: 1.2–1.5x faster on CIFAR10 and 3.4–5x faster on SVHN, SB reaches reported target error rates sooner than Traditional.The SVHN targets are 1.8%, 2.1%, and 2.4% error; the CIFAR10 comparison uses targets within 10%, 20%, and 40% of Traditional’s final error rate.
- 5.2 Selective-Backprop speeds up training: 1.02–1.8x faster than Kath18, SB provides a speedup over the state-of-the-art importance-sampling baseline.Kath18 itself accelerates training over Traditional by 0.8–3.4x, but is least effective on CIFAR100 and can slightly slow some target-error rates.
- 5.2 Selective-Backprop speeds up training: 29% versus 3%, SB correctly classifies examples at the 20th percentile of target confidence more often than Traditional.SB improves confidence and accuracy among harder examples, although it reduces confidence on higher-percentile examples without sacrificing test accuracy.
- 5.3 Reducing selection times further speeds training: 26% faster than SB on average, Stale-SB with n = 3 reaches target error rates while reducing selection passes with little effect on final error.Stale-SB uses the most recent selection forward-pass results between periodic selection passes.
- 5.4 Selective-Backprop sensitivity analysis: 20% label corruption causes SB to overfit incorrect labels and increases final test error, although lower corruption levels retain comparable final accuracy.The experiments also report faster training across 1%, 10%, and 20% corruption settings.
- 5.4 Selective-Backprop sensitivity analysis: 20–65% selectivity accelerates training, but higher selectivity can increase final error and the best setting depends on target error and dataset.At 20% selectivity on CIFAR10, SB comes within 0.92% of Traditional’s final error; at 25% on CIFAR100, it comes within 2.54%.
- 5.5 Putting it all together: 72%, 47%, and 80% of Pareto-optimal choices on CIFAR10, CIFAR100, and SVHN, respectively, come from SB and Stale-SB.Traditional accounts for 10%, 43%, and 6% of Pareto points on those datasets, and performs better at very large training-time budgets.
6 CONCLUSION
Selective-Backprop accelerates DNN training by skipping low-value backward passes, while stale loss information can further reduce computation. Across datasets and networks, it offers faster convergence and a broad training-time/accuracy trade-off.
- Selective-Backprop converges to target error rates up to 3.5x faster than standard SGD and 1.02–1.8x faster than a state-of-the-art sampling approach.
- Using stale loss information for selection further accelerates training by 26%.
- SB reaches similar test error rates to Traditional with 1% and 10% shuffled labels.
- SB accelerates training across a range of selectivities, although higher selectivity can increase error.
- SB and Stale-SB provide the majority of Pareto-optimal choices for trading off training time and accuracy.
A.1 Selective-Backprop code
The authors provide open-source implementations of Selective-Backprop and the specific training setup used in the paper.
- The Selective-Backprop implementation and modified training setup are publicly available through linked repositories.
A.2 Variance of relative losses over time
Sampling increases the variability of examples’ selection probabilities, while a look-once approach keeps importance estimates tied to the current network state.
- Selection probability variance increases when sampling is introduced during training.
- Selective-Backprop’s look-once importance calculation uses the up-to-date network state during training.
- For five CIFAR10 examples, selection likelihood fluctuates more when sampling is introduced.
A.3 Sensitivity analyses
Sensitivity analyses examine Selective-Backprop across architectures and learning-rate schedules, finding accelerated training under an additional schedule.
- CIFAR10 experiments use ResNet18, DenseNet, and MobileNetV2 architectures.
- An accelerated learning-rate schedule preserves the same training trends across CIFAR10, CIFAR100, and SVHN.
- SB reduces wall-clock time to target error with an accelerated learning-rate schedule.
A.4 Asymmetry between cost of backward and forward pass
The backward pass is substantially more expensive than the forward pass during MobileNetV2 training. Across modern GPUs, it can take up to 2.5x as long as the forward pass.
- Up to 2.5x longer backward passes than forward passes are observed across a variety of modern GPUs.The comparison concerns processing time during training.
- The Section 5 experiments use K20 and TitanV GPUs with a batch size of 128.
- Figure 18 breaks down processing time per batch for MobileNetV2 trained with Traditional.