PaperlayerView exact revision on arXiv

Source-linked AI summary

Coupling Adaptive Batch Sizes with Learning Rates

Lukas Balles, Javier Romero, Philipp Hennig

arXiv:1612.05086v2cs.LGcs.CVstat.ML

TL;DR

Fixed batch sizes are often chosen ad hoc despite the trade-off between gradient variance and computational cost. CABS adapts batch size using gradient-variance estimates coupled to learning rate and objective value; it outperformed alternatives on three of four benchmarks.

  • Problem

    Batch size is often fixed by ad hoc choice, despite its variance–cost trade-off and interaction with learning rate and objective structure.

    Source: §1.1 · p. 2

  • Method

    CABS adapts batch size using gradient-variance estimates, coupling it to learning rate and optimization progress represented by function value.

    Source: §6 · p. 9

  • Results

    0.4 percentage points on CIFAR-10 and 1.4 points on CIFAR-100 separated CABS's best test accuracy from the second-best; overall, it outperformed alternatives on three of four benchmarks.

    Source: §5.2 · p. 8

  • Takeaways & Limitations

    CABS reduced performance dependence on learning rate compared with both constant-batch and competing adaptive methods in the reported SVHN and MNIST experiments.

    Source: §5.2 · p. 9

    The mathematical motivation assumes a scalar Hessian, a substantial simplification that is only partly generalized under μ-strong convexity.

    Source: §3.3 · p. 5

Abstract

from arXiv · show

Mini-batch stochastic gradient descent and variants thereof have become standard for large-scale empirical risk minimization like the training of neural networks. These methods are usually used with a constant batch size chosen by simple empirical inspection. The batch size significantly influences the behavior of the stochastic optimization algorithm, though, since it determines the variance of the gradient estimates. This variance also changes over the optimization process; when using a constant batch size, stability and convergence is thus often enforced by means of a (manually tuned) decreasing learning rate schedule. We propose a practical method for dynamic batch size adaptation. It estimates the variance of the stochastic gradients and adapts the batch size to decrease the variance proportionally to the value of the objective function, removing the need for the aforementioned learning rate decrease. In contrast to recent related work, our algorithm couples the batch size to the learning rate, directly reflecting the known relationship between the two. On popular image classification benchmarks, our batch size adaptation yields faster optimization convergence, while simultaneously simplifying learning rate tuning. A TensorFlow implementation is available.

1 INTRODUCTION

Large-scale empirical risk minimization often uses mini-batch gradients because computing exact gradients can be inefficient or impossible. The paper motivates runtime batch-size adaptation by the variance–cost trade-off and describes estimating gradient variance from mini-batches.

1.1 THE EFFECT OF THE BATCH SIZE

  • Batch size trades off linearly decreasing gradient variance against linearly increasing per-step cost, while optimizer performance also depends on objective structure and learning rate.The paper notes that parallel hardware use can be supported by enforcing a suitable minimum batch size.Source: §1.1 · p. 2
  • CABS adapts batch size using gradient-variance estimates observed at runtime; the estimate uses mini-batch sample variance and only the covariance diagonal.The exact variance over the full data set is prohibitively costly to compute.Source: §1.1 · p. 2

1.2 NOTATION

  • For single-step batch-size analysis, the paper fixes the parameter vector w and suppresses it from the notation for the function and gradient.Source: §1.2 · p. 2

2 RELATED WORK

Prior work studies increasing or variance-adaptive batch sizes, while this paper emphasizes accounting for the learning-rate-scaled step. Related approaches also include variance reduction and broader parameter-tuning efforts.

2 RELATED WORK

  • Friedlander & Schmidt (2012) derive decreasing gradient-variance bounds for fast convergence with a constant learning rate, but implement them with a pre-specified batch-growth factor.Their schedule does not adapt to an estimate of gradient variance.Source: §2 · p. 2
  • Byrd et al. (2012) and De et al. (2017) adapt batch size using variance estimates and a descent-direction criterion, which does not account for the actual step set by learning rate α.The paper also notes that the criterion adds a free parameter θ.Source: §2 · pp. 2–3
  • SVRG and SAGA combined with increasing sample sizes use pre-specified schedules rather than runtime adaptation.Source: §2 · p. 3
  • Non-uniform sampling methods target batch composition rather than batch size, making that line of work orthogonal to this paper.The cited examples include Needell et al. (2014), Zhao & Zhang (2015), Schmidt et al. (2015), and Csiba & Richtárik (2016).Source: §2 · p. 3
  • The paper places its approach within efforts to automate or simplify stochastic-optimization parameter tuning, especially learning-rate tuning.Source: §2 · p. 3

3 COUPLED ADAPTIVE BATCH SIZE

The section derives batch-size adaptation from a bound on expected SGD gain per computational cost and proposes CABS, which explicitly couples batch size to learning rate. Its rationale links the rule to gradient variance and objective value, with a mathematical motivation that relies on simplifying assumptions.

3.1 MAXIMIZING A BOUND ON THE EXPECTED GAIN

  • Expected gain per computational cost motivates choosing batch size by balancing the gain from larger batches against their linearly increasing cost.The derivation assumes Lipschitz-continuous gradients to obtain a lower bound on the gain.Source: §3 · p. 3, §3.1 · p. 3
  • The expected-gain bound subtracts a gradient-variance penalty that decreases with batch size, and expected descent requires the gain to remain positive.The deterministic gain term depends on the learning rate and true gradient; the variance term makes the required batch size depend on the learning rate.Source: §3.1 · p. 3

3.2 THE CABS CRITERION

  • CABS replaces the difficult-to-use criterion with a simpler rule that directly couples batch size to learning rate and uses objective value as a progress measure.The preceding criterion depends on an unknown Lipschitz constant and a true-gradient norm that is difficult to estimate without bias.Source: §3.2 · p. 4
  • CABS realizes a gradient-variance bound that decreases with distance to optimality, similar to a bound shown to guarantee convergence with a constant, non-decreasing learning rate.The paper says this coupling makes finding a well-performing learning rate easier in experiments.Source: §3.2 · p. 4

3.3 MATHEMATICAL MOTIVATION FOR CABS

  • The mathematical motivation approximates the Hessian as scalar and assumes a well-chosen learning rate; dropping the optimum value relies on non-negative loss.When the optimum is not close to zero, objective value adds a positive offset to the distance-to-optimality proxy; the authors suggest using unregularized loss when regularization is additive.Source: §3.3 · pp. 4–5

4 PRACTICAL IMPLEMENTATION

The implementation estimates objective value and gradient variance from mini-batches, smooths these estimates, and uses them to set the next batch size. It estimates variance without storing per-example gradients, at a reported additional computational cost of roughly 25%.

4 PRACTICAL IMPLEMENTATION

  • The practical rule estimates objective value and gradient variance from each mini-batch, using the estimates to choose the next batch size.The implementation smooths both quantities across optimization steps with exponential moving averages because the estimates, especially variance at small batch sizes, can be noisy.Source: §4 · p. 5, §4.1 · p. 5

4.1 MECHANICAL DETAILS

  • Batch size is rounded and clipped to avoid tiny-batch underutilization and respect GPU memory limits; the implementation's maximum was never reached in the experiments.The paper distinguishes algorithmic batch size from computational batch size and notes that future implementations could split an algorithmic batch into feasible computational batches.Source: §4.1 · pp. 5–6

4.2 VARIANCE ESTIMATE

  • Backpropagation aggregates per-example gradients implicitly, so the method computes their second moment through batch matrix operations rather than storing individual gradients, at roughly 25% extra cost.The paper notes that special matrix operations could reduce this cost.Source: §4.2 · p. 6

5 EXPERIMENTS

Across four image-classification benchmarks, CABS outperforms alternative batch-size schemes on three, with gains increasing with problem complexity. It also reduces learning-rate sensitivity, though it is outperformed by small-batch methods on MNIST.

5.1 EXPERIMENT DESIGN

  • The experiments train CNNs on MNIST, SVHN, CIFAR-10, and CIFAR-100, comparing CABS with fixed batch sizes and a variance-based competitor using tuned learning rates.The benchmarks were selected to keep evaluation manageable, requiring approximately 60 training runs per benchmark.Source: §5 · p. 6, §5.1 · pp. 6–7

5.2 RESULTS AND DISCUSSION

  • CABS reduces training loss faster and achieves the best test accuracy on SVHN, CIFAR-10, and CIFAR-100; its accuracy margins are 0.4 percentage points on CIFAR-10 and 1.4 on CIFAR-100.Source: Figure 1 · p. 7, Figure 2 · p. 7, Figure 3 · p. 8
  • On MNIST, batch size 32 and the competitor outperform CABS, which beats larger fixed batches in speed; test accuracy is virtually equal across methods.The authors conjecture that homogeneous data lead CABS to overestimate gradient variance and choose unnecessarily large batches later, whose per-iteration cost is not offset by its higher learning rate.Source: Figure 4 · p. 8, §5.2 · p. 8
  • On three of four benchmarks, CABS uses the minimum batch size of 16 for much of training, then increases it approximately linearly; MNIST is the exception.Source: Figure 1 · p. 7, Figure 2 · p. 7, §5.2 · p. 8
  • On SVHN and MNIST, CABS significantly reduces training-loss sensitivity to learning rate versus both constant-batch and competing adaptive methods, potentially simplifying learning-rate tuning.Source: Figure 5 · p. 9, Figure 6 · p. 9, §5.2 · p. 9

6 CONCLUSION

The conclusion presents CABS as a practical dynamic batch-size rule based on gradient-variance estimates, learning rate, and optimization progress. In experiments, it sped up SGD training in neural networks and simplified learning-rate tuning without adding free parameters.

6 CONCLUSION

  • CABS adapts batch size using gradient-variance estimates, the chosen learning rate, and the objective function value.The rule is presented as a practical method for dynamic batch-size adaptation.Source: §6 · p. 9
  • In experiments, CABS sped up SGD training in neural networks and simplified learning-rate tuning without adding free parameters.Source: §6 · p. 9
  • A TensorFlow implementation of SGD with CABS is available.Source: §6 · p. 9

A MATHEMATICAL DETAILS

The mathematical details include a sufficient condition for the inner product in Equation (11) to be positive, a maximization derivation yielding Equation (21), and a strong-convexity derivation of Equation (30).

A MATHEMATICAL DETAILS

  • Equation (11)'s inner product is positive when the gradient-estimation error norm is smaller than the norm of g.The proof applies the Cauchy-Schwarz inequality to obtain this sufficient condition.Source: A MATHEMATICAL DETAILS · p. 9
  • Setting the derivative to zero in the maximization problem and rearranging yields Equation (21).Source: A MATHEMATICAL DETAILS · p. 9
  • Under strong convexity with µ > 0, minimizing the inequality's right-hand side gives the minimizer used to derive Equation (30).The derivation sets its gradient with respect to u to zero and substitutes the resulting minimizer back into the inequality.Source: A MATHEMATICAL DETAILS · p. 9

Supplementary Material

The supplementary material provides additional results for SVHN, CIFAR-10, CIFAR-100, and MNIST, including comparisons with constant batch sizes omitted from the main text.

Supplementary Material

Related papers

Loading 1612.05086v2…