Research map / Learning theory and algorithms / Prediction and decision losses
Understanding the Training Speedup from Sampling with Approximate Losses
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes greedy SGD that picks the largest approximate-loss sample among R candidates, proving faster early convergence than SGD, and proposes SIFT, which uses early-exit intermediate-layer losses to select half of each batch for BERT pretraining and ResNet-50 training.
Problem
Sample selection by high loss speeds up training, but exact loss computation is too costly; the paper asks when approximate losses still yield speedups over random sampling and whether early-exit losses can cheaply enable this in practice.
Approach
Greedy selection of the largest approximate loss (from an intermediate layer via early exiting) among R i.i.d. samples, with convergence analysis for smooth convex losses showing GSGD reaches a constant factor of F* in fewer iterations than SGD, plus a practical SIFT method that backpropagates on the top 50% of a batch ranked by early-exit loss or entropy.
Key results
- To reach 64% validation accuracy on BERT base pretraining, loss-based SIFT with first-layer exit takes about 43 hours versus about 57 hours for vanilla training.
- On BERT pretraining at 800K steps, entropy-based SIFT with first-layer exit reaches 0.6641 validation accuracy versus 0.6466 for baseline.
- On CIFAR-100 with equal training time, SIFT with early exit reaches 73.45% test accuracy versus 69.04% for baseline at max_lr 1e-2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use loss-based SIFT with exit at layer 1 instead of no sample filtering | BERT base pretraining · BERT validation set, last step | validation accuracy: 0.6466 -> 0.6599 | Helped |
| Use entropy-based SIFT instead of loss-based SIFT at exit layer 1 | BERT base pretraining · BERT validation set, last step | validation accuracy: 0.6599 -> 0.6641 | Helped |
| Use exit layer 12 instead of layer 1 for loss-based SIFT (ablation) | BERT base pretraining · BERT validation set, last step | validation accuracy: 0.6599 -> 0.6640 | Helped |
| Use exit layer 6 instead of layer 1 for entropy-based SIFT (ablation) | BERT base pretraining · BERT validation set, last step | validation accuracy: 0.6641 -> 0.6680 | Helped |
| Use SIFT with early-exit loss selection instead of the baseline | Modified ResNet-50 · CIFAR-100, same training time | test accuracy: 69.04 -> 73.45 | Helped |
| Use SIFT with early-exit loss selection instead of the baseline | Modified ResNet-50 · CIFAR-100, same backpropagation sample complexity | test accuracy: 69.04 -> 75.41 | Helped |
| Use last-layer predictions instead of early-exit predictions for SIFT (ablation) | Modified ResNet-50 · CIFAR-100, same backpropagation sample complexity | test accuracy: 75.41 -> 76.93 | Helped |
| Use SIFT with early-exit loss selection instead of the baseline | Modified ResNet-50 · Food-101, same training time | test accuracy: 59.52 -> 64.03 | Helped |
| Use last-layer predictions instead of early-exit predictions for SIFT (ablation) | Modified ResNet-50 · Food-101, same training time | test accuracy: 64.03 -> 66.47 | Helped |
| Use SIFT with early-exit loss selection instead of the baseline | Modified ResNet-50 · Food-101, same backpropagation sample complexity | test accuracy: 59.52 -> 64.04 | Helped |
| Use last-layer predictions instead of early-exit predictions for SIFT (ablation) | Modified ResNet-50 · Food-101, same backpropagation sample complexity | test accuracy: 64.04 -> 66.64 | Helped |
| Use loss-based or entropy-based SIFT with exit at layer 1 instead of vanilla training | BERT base pretraining · BERT validation accuracy target 64% | training time: ~ 57 hours -> ~ 43 hours (loss-based); ~ 57 hours -> ~ 40 hours (entropy-based) | Helped |
Surprising findings
- Under equal backpropagation budget, SIFT with last-layer exit beats SIFT with early exit on Food-101 at some learning rates, while early exit wins under equal wall-clock time.
- The SIFT baseline comparison on ResNet-50 diverges at the largest learning rate, with SIFT failing to converge on Food-101 at max_lr 5e-2.
Limitations
- The forward pass used for sample selection is implemented naively and not pipelined with the update, so the reported speedups are conservative.
- Experiments only cover BERT base (110M) and a modified ResNet-50; not tested on much larger transformers.
- The convergence theory covers only smooth convex losses; the non-convex case is left open.
Experimental setup
Datasets: BookCorpus English Wikipedia CIFAR-100 Food-101
Benchmarks: BERT MLM validation accuracy CIFAR-100 Food-101
Metrics: validation accuracy test accuracy wall-clock hours backpropagation sample complexity
Baselines: vanilla SGD / baseline BERT pretraining entropy-based SIFT SIFT with last layer exit
Builds on: ordered SGD online hard example mining importance sampling early exiting
Closest papers by meaning
- Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning (ICLR 2024 · similarity 0.85)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.85)
- Mixed-Sample SGD: an End-to-end Analysis of Supervised Transfer Learning (NeurIPS 2025 · similarity 0.84)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.84)
- Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapes (NeurIPS 2025 · similarity 0.84)
- Efficient Backpropagation with Variance Controlled Adaptive Sampling (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.