Online Batch Selection for Faster Training of Neural Networks

Ilya Loshchilov; Frank Hutter

Source-linked AI summary

Online Batch Selection for Faster Training of Neural Networks

Ilya Loshchilov, Frank Hutter

arXiv:1511.06343v4Nov 19, 2015cs.LGcs.NEmath.OC

TL;DR

The paper addresses the limited use and understanding of online batch selection in stochastic DNN training. It evaluates rank-based, loss-dependent sampling with AdaDelta and Adam, finding about a fivefold convergence speedup on MNIST. The evaluation remains limited in breadth, and the method depends on relatively stable loss rankings over time.

Problem
The benefits of online batch selection for stochastic DNN optimization are poorly understood despite the computational cost of mini-batch training.
Method
The paper ranks datapoints by their latest known loss and samples them with probabilities that decay exponentially with rank, evaluating the strategy with AdaDelta and Adam.
Results
Online batch selection speeds convergence of AdaDelta and Adam by a factor of about 5 on the MNIST experiments.
Takeaways & Limitations
Simple online batch selection mechanisms can substantially improve performance and may help focus training on datapoints contributing most to the objective.
Takeaways & Limitations
The empirical evaluation is narrow, and the method is expected to work well only when datapoint loss rankings remain relatively stable over time.

Abstract

from arXiv · show

Deep neural networks are commonly trained using stochastic non-convex optimization procedures, which are driven by gradient information estimated on fractions (batches) of the dataset. While it is commonly accepted that batch size is an important parameter for offline tuning, the benefits of online selection of batches remain poorly understood. We investigate online batch selection strategies for two state-of-the-art methods of stochastic gradient-based optimization, AdaDelta and Adam. As the loss function to be minimized for the whole dataset is an aggregation of loss functions of individual datapoints, intuitively, datapoints with the greatest loss should be considered (selected in a batch) more frequently. However, the limitations of this intuition and the proper control of the selection pressure over time are open questions. We propose a simple strategy where all datapoints are ranked w.r.t. their latest known loss value and the probability to be selected decays exponentially as a function of rank. Our experimental results on the MNIST dataset suggest that selecting batches speeds up both AdaDelta and Adam by a factor of about 5.

1 INTRODUCTION

DNN training commonly uses fixed-size mini-batches with stochastic gradient descent, making training a major computational bottleneck. The paper proposes online batch selection to focus SGD on more relevant datapoints and speed progress.

Training DNNs with fixed-size mini-batches and SGD is computationally expensive, especially on large datasets.Training can require several days even on high-performance GPUs.
Online batch selection remains uncommon despite the computational burden of DNN training.
The proposed methods sample each batch from a non-uniform distribution based on each datapoint’s previously computed loss.
The study evaluates online batch selection with AdaDelta and Adam to determine whether it can substantially speed optimization.

2 STOCHASTIC GRADIENT DESCENT (SGD)

SGD minimizes an expected dataset loss by updating parameters with gradients estimated from relatively small batches. This stochastic approximation reduces computation but introduces noisy gradient information and motivates careful batch-based optimization.

DNN training can be formulated as minimizing an expected loss function f over a distribution of datapoint-specific loss functions.
SGD updates the parameter vector using gradient information computed from a relatively small batch of datapoints.
Second-order methods are difficult to use for large neural networks because storing and computing the Hessian is intractable.
The paper treats batch selection itself, rather than only the parameter update, as an important part of stochastic optimization.

3 ADADELTA AND ADAM

The paper builds on AdaDelta and Adam, using them as baseline stochastic optimizers. Both adapt updates through gradient-history information, while Adam additionally uses bias-corrected momentum estimates.

AdaDelta and Adam are used as the baseline optimizers for evaluating online batch selection.
AdaDelta decays stored gradient-amplitude information to reduce the influence of outdated information.
AdaDelta normalizes updates using gradient-amplitude and parameter-change information to adjust learning rates.
Adam maintains first- and second-momentum vectors and uses bias-corrected estimates to update parameters and set learning rates.
The experiments select AdaDelta and Adam partly because their claimed robustness may reduce hyperparameter-tuning difficulty.

4 ONLINE BATCH SELECTION

The proposed online batch selection ranks datapoints by their latest known losses and samples them with exponentially rank-decayed probabilities. Selection pressure and batch size can change over time, but stale loss estimates and exploitation–exploration trade-offs remain central concerns.

Online batch selection aims to maximize optimization progress relative to a resource budget such as evaluated datapoints or time.
Loss rankings create an exploitation–exploration dilemma because focusing on the current highest-loss datapoint can make other candidates important after its loss falls.
The method ranks training datapoints by their latest computed losses and assigns selection probabilities according to rank.
Selection probabilities decrease exponentially with rank, so higher-loss datapoints are sampled more frequently.
The selection-pressure parameter likely reduces the effective number of unique datapoints selected as its value increases.
The method periodically recomputes losses for the datapoints currently ranked highest to improve ranking quality.

5 TIME COMPLEXITY

The batch-selection procedure adds selection and optional loss-recomputation costs, while keeping measured overhead relatively small on MNIST.

Selection overhead: O(log(N)) selection complexity per datapoint uses bisection-based search over cumulative selection probabilities.Sorting costs O(N log(N)) and occurs periodically every Ts evaluated datapoints.
Selection overhead: 5% overhead is measured on a GPU for MNIST when selection excludes loss recomputation and plotting costs.This overhead reflects the selection procedure alone.
Loss recomputation: 20% overhead is expected when loss is recomputed every two epochs for the whole dataset using rfreq = 0.5 and rratio = 1.0.This corresponds to a factor of 1.2 higher cost than the default algorithms.

6 EXPERIMENTAL RESULTS

Experiments on MNIST evaluate online batch selection with AdaDelta and Adam across batch sizes, convergence settings, and time budgets. The results indicate faster training and validation improvement, including after hyperparameter optimization.

Experimental settings: The MNIST experiments use 50,000 training, 10,000 validation, and 10,000 test datapoints without data augmentation or preprocessing.The experiments combine AdaDelta and Adam with the proposed batch-selection variants.
Experimental settings: Batch size b = 64 is emphasized because it demonstrates better generalization errors over time than the other tested settings.Results for b = 16 and b = 256 are provided in supplementary figures.
Convergence speed: 5-fold speedup is achieved for both AdaDelta and Adam during the first 10 epochs without recomputation and throughout the run with recomputation.The top-row experiment motivates adding loss recomputation.
Selection pressure: s = 10^8 → 1 combines fast convergence during the first 10 epochs with steady improvement later.A decreasing selection pressure avoids the sustained-strong-selection behavior seen with fixed high s.
Loss recomputation: Recomputing losses for 1.0N datapoints 0.5 times per epoch drastically improves s = 10^8 → 10^8 results by making rankings more consistent.The same recomputation changes s = 10^2 → 10^2 and s = 10^2 → 1 much less.
Time-budget performance: 5-fold speedup after 5 epochs compensates for the relatively negligible batch-selection overhead for both AdaDelta and Adam.This comparison evaluates performance over elapsed time rather than only epochs.
Validation performance: Up to 5-fold faster achievement of better validation errors is observed for accelerated AdaDelta and Adam.Validation performance is reported to assess whether faster convergence corresponds to overfitting.
Hyperparameter optimization: A factor-of-3 speedup of peak performance remains after CMA-ES hyperparameter optimization for the original and batch-selection methods.CMA-ES used 1000 function evaluations to optimize the hyperparameters.

7 RELATED WORK

The paper situates online batch selection within non-uniform sampling, importance sampling, and curriculum learning, while distinguishing its loss-ranking approach from gradient reweighting and Lipschitz-based methods.

Non-uniform sampling: Non-uniform sampling addresses high variance caused by substantially different individual stochastic estimates across examples.Related strategies include importance sampling and selection based on gradient Lipschitz constants.
Distinction from prior methods: The proposed approach does not re-weight gradients or estimate Lipschitz constants, making selection invariant to rank-preserving loss transformations.It showed competitive performance against SAG-NUS* in a strongly-convex conditional-random-field problem.
Deep-learning context: Non-uniform training-batch selection was described as virtually absent in deep learning, with closely related parallel work prioritizing relevant replay experiences.Another parallel approach used importance sampling for variance reduction and unbiased gradient estimation.
Trade-offs: Importance sampling can be optimal for local-gradient variance reduction without necessarily improving generalization, and one cited approach is limited to fully connected networks.The paper states that its approach directly works for any kind of network.
Curriculum learning: Curriculum learning is framed as batch selection with s < 1, whereas this paper explores s > 1.The distinction concerns whether examples are organized toward gradually more complex concepts or toward higher-loss datapoints.

8 LIMITATIONS

The study’s empirical scope is limited, and its selection-pressure hyperparameter may not transfer reliably beyond MNIST. The method is expected to work best when datapoint loss rankings remain relatively stable over time.

Sorting adds overhead, while the dominant recomputation overhead can be controlled by rfreq and rratio.
The reasonable range for s on MNIST is 10^2–10^8, but suitable values for other datasets remain unclear.
The empirical evaluation covers deep-network training on MNIST and conditional-random-field training for optimal character recognition.
The proposed method is expected to work well when datapoint rankings by loss remain relatively stable over time.
CIFAR-10 experiments showed benefits over random selection but not over shuffling.

9 CONCLUSION

The paper proposes controlling the batch itself by selecting higher-loss datapoints more often, using probabilities that decrease with loss rank. Online batch selection sped convergence for AdaDelta and Adam by about 5, while broader selection strategies remain open for study.

The method controls the source of gradient information—the batch—rather than only post-processing gradients.
Datapoints with greater contributions to the objective are selected more frequently, with probability decreasing by the rank of latest known loss.
The selection is invariant to rank-preserving transformations of the loss function.
About 5×: online batch selection sped convergence of AdaDelta and Adam.
Tighter coupling of learning rates and batch size may provide additional speedups, and increasing batch size over time may reduce gradient-estimation noise near the optimum.
More advanced strategies could incorporate gradient amplitudes, datapoint features or classes, similarity, and proxies for generalization.

10 SUPPLEMENTARY MATERIAL

The supplementary material examines rank-based batch selection, batch-size scheduling, importance sampling, SAG-NUS*, and hyperparameter optimization across several settings. It reports benefits in some experiments, while noting time-based and dataset-specific limitations.

10.1 WHEN Neff = N?: Increasing selection pressure usually reduces the effective number of unique datapoints selected, although repeated loss reduction can still produce Neff = N.The paper gives a scenario in which repeatedly selecting and improving the highest-loss datapoint eventually schedules a full sweep of the dataset.
10.2 ONLINE SELECTION OF THE BATCH SIZE: Small batches can provide speedups early, while increasing batch size over epochs is proposed to reduce gradient-estimation noise near the optimum.Both exponential and linear batch-size increases are considered, with the increase starting and ending at specified epochs.
10.2 ONLINE SELECTION OF THE BATCH SIZE: The batch-size procedure is not reported as an additional time-based speedup because small GPU batches cost more per datapoint, despite epoch-based acceleration.The procedure is nevertheless included during hyperparameter optimization.
10.3 IMPORTANCE SAMPLING: Importance sampling produced worse validation accuracy than the original batch-selection approach in all MNIST cases shown for Figure 3.Figure 3 compares solid original-approach curves with dotted curves using importance sampling for AdaDelta and Adam.
10.4 RANK-BASED SELECTION FOR NON-UNIFORM STOCHASTIC AVERAGE GRADIENT METHOD: Replacing Lipschitz-constant-based proportional selection with rank-based selection leaves the rest of SAG-NUS* unchanged.The rank-based variant depends on loss ranks rather than Lipschitz-constant estimates.
10.5 HYPERPARAMETER OPTIMIZATION: Batch selection remained beneficial during CMA-ES hyperparameter optimization for both Adadelta and Adam across the tested time budgets.The experiments used budgets of 5, 10, 15, and 30 minutes; the supplementary text states benefits with both random and optimized hyperparameters.
10.5 HYPERPARAMETER OPTIMIZATION: On CIFAR-10, preliminary batch selection was slightly better than random selection but not yet better than shuffling.After 60 minutes, CMA-ES improved the best validation error from 12% in the first generation to about 10% by the 34th generation.