When training machine learning models, we face a fundamental tension between two optimization paradigms: stochastic gradient methods and full-batch deterministic methods.
Stochastic methods (like Stochastic Gradient Descent) use small, randomly sampled mini-batches. They are incredibly fast out of the gate because every single data point provides a rough estimate of the descent direction, allowing the model to make rapid early progress. However, as the model approaches the optimum, this randomness introduces variance, causing the parameters to bounce around the minimum rather than settling into it.
Full-batch methods, by contrast, compute gradients over the entire dataset. They are steady, precise, and exhibit fast linear convergence near the optimum, but they are painfully slow and computationally prohibitive in early training stages when the model is far from the solution.
As Michael P. Friedlander et al. observe in their work on hybrid deterministic-stochastic methods, we do not have to choose a single static batch size. Instead, we can dynamically scale the batch size as training progresses—starting small to exploit the rapid initial progress of stochastic updates, and growing large to achieve the high-precision convergence of full-batch methods.
The Intuition: Signal-to-Noise Ratio
To understand why adaptive batch sizing works, imagine navigating a foggy valley. When you are high up on the mountain slopes, the general direction of "down" is obvious. You do not need a precise topographic map to take a step forward; a quick glance at your immediate surroundings is enough. In optimization terms, the true gradient is large, and even a small mini-batch provides a noisy estimate that points in roughly the right direction.
However, as you approach the valley floor, the terrain flattens out. The true gradient shrinks, and the local bumps and ridges in the landscape (stochastic noise) begin to dominate. If you continue using a small batch size, the noise drowns out the signal, and you will wander aimlessly around the valley floor.
Traditionally, practitioners combat this by decaying the learning rate. Decaying the learning rate squashes the stochastic noise, but it also shrinks the step size, forcing the algorithm to crawl. Adaptive batch sizing offers an alternative: by increasing the batch size, we suppress the noise without shrinking the step size.
Levi Boyles et al. formalized this intuition in Statistical Tests for Optimization Efficiency by tracking the signal-to-noise ratio (SNR) of the gradients. Early on, the SNR is high, so small subsets are sufficient. As the model converges and the SNR drops, the algorithm automatically recruits larger batches to provide the exact precision required for final convergence. This ensures that computational resources are allocated proportionally to the precision needed at each stage of the optimization trajectory.
Early Training (High Gradient Signal)
[Data Sample] ---> Clear Direction ---> Large Step
Late Training (Low Gradient Signal, High Noise)
[Small Sample] ---> Noise Dominates ---> Wandering
[Large Sample] ---> Noise Suppressed ---> Precise Convergence
Growth Schedules: Fixed vs. Adaptive
How exactly should the batch size grow? The literature broadly splits into two camps: predefined schedules and data-driven adaptive schedules.
Predefined Exponential Growth
The foundational theoretical groundwork for batch scaling was laid by Genevieve B. Orr in Removing Noise in On-Line Search using Adaptive Batch Sizes. Orr demonstrated that increasing the batch size exponentially with the number of iterations is an optimal strategy for maximizing error reduction per data point.
This exponential scaling mechanism allows algorithms to transition seamlessly from rapid stochastic estimation to high-precision convergence. For instance, Pan Zhou et al. utilized exponentially increasing mini-batches in Efficient Stochastic Gradient Hard Thresholding to achieve full-gradient accuracy without the prohibitive cost of evaluating the entire dataset at every iteration. Similarly, Anthony Man-Cho So et al. showed that gradually increasing the sample size allows inexact gradient methods to maintain a geometric convergence rate while keeping per-iteration costs low.
In second-order optimization, this growth is critical for maintaining mathematical guarantees. Qiujiang Jin et al. developed an adaptive sample size approach for Quasi-Newton methods (AdaQN), demonstrating that geometrically increasing the training sample size ensures the solution from a smaller dataset provides a sufficiently accurate warm start for the next, larger subproblem. This keeps the optimizer within its "superlinear" convergence region throughout the entire run.
Data-Driven and Online Adaptation
While exponential schedules work well in theory, finding the right growth rate manually can be challenging. To solve this, researchers have designed automated, online mechanisms that listen to the model's feedback.
In Batch-Expansion Training, Michal Derezinski et al. proposed an automated scheduling mechanism that runs two parallel optimization tracks on different batch sizes. When the loss on the larger batch drops below the loss on the smaller batch, it signals that the model has extracted all available information from the current subset and requires more data, triggering a dataset expansion.
For large language models, William Merrill et al. investigated the Critical Batch Size (CBS)—the threshold beyond which increasing the batch size yields diminishing returns in training efficiency. In Critical Batch Size Revisited, the authors showed that CBS grows rapidly during early training before plateauing. By implementing a dynamic batch size warmup that tracks this capacity, they reduced the total number of gradient steps by 43% without sacrificing final model quality.
Broad Applications Across Machine Learning
The utility of dynamic sample allocation extends far beyond standard deep learning optimization. The same principle—balancing update frequency with variance reduction—applies across diverse domains:
- Data Management & Graph Neural Networks: GNN training is often bottlenecked by data movement rather than raw computation. Hao Yuan et al. demonstrated in a comprehensive evaluation of GNN systems that starting with small batches accelerates initial convergence, while transitioning to larger batches stabilizes the final optimization phase by balancing gradient update frequency with variance reduction.
- Computer Vision & Non-linear Least Squares: In computer vision tasks like bundle adjustment or image alignment, calculating Jacobians for millions of pixels at every step is a massive bottleneck. Huu Le et al. introduced Progressive Batching, which adaptively grows the sample size only when the noise of the stochastic approximation begins to hinder the solver's progress.
- Active Learning: Active learning algorithms query data samples for human annotation. Silvio Giancola et al. designed an adaptive scheduling mechanism in Towards Active Learning for Action Spotting in Association Football Videos that increases the number of samples queried in later training stages. This balances the need for frequent model updates early on with computational efficiency as the model matures.
- Multi-Armed Bandits: In parallelized bandit optimization, actions are committed in groups. Hossein Esfandiari et al. showed in Batched Multi-Armed Bandits with Optimal Regret that dynamically adjusting the size of subsequent experiment batches based on previous outcomes allows learning algorithms to eliminate suboptimal options far more efficiently.
Ultimately, adaptive batch sizing works because it aligns the computational effort with the difficulty of the optimization task. By treating batch size as a dynamic trajectory rather than a static hyperparameter, algorithms can learn from data in a way that is both computationally efficient and statistically precise.
Key Foundational Work
Learning from Infinite Data in Finite Time (2001) — contributed 1 concept elements to this direction.
Removing Noise in On-Line Search using Adaptive Batch Sizes (1996) — contributed 1 concept elements to this direction.