Abstract
In large-scale machine learning, researchers often face a trade-off between the rapid initial progress of Stochastic Gradient Descent (SGD) and the stable, high-precision convergence of batch methods like L-BFGS. We introduce Batch-Expansion Training (BET), a meta-algorithm designed to bridge this gap. By starting with a small data subset and strategically expanding the batch size based on theoretical bounds from Permutational Rademacher Complexity (PRC), BET achieves the speed of stochastic methods while maintaining the robust convergence of batch optimization. We evaluate BET on diverse datasets, showing it consistently outperforms traditional approaches by adaptively managing computational resources.
The Optimization Trade-off
The central challenge in large-scale optimization is balancing speed and precision. Stochastic methods (SGD) are fast but noisy, making it difficult to converge to an exact minimum. Conversely, batch methods use the entire dataset to find precise directions but are computationally expensive, especially in early training stages where a small subset of data would suffice to determine a general descent direction.
Batch-Expansion Training (BET)
BET is a principled framework that grows the dataset size dynamically. Unlike simple heuristics, BET uses Permutational Rademacher Complexity (PRC) to determine when to expand the training set. PRC measures how well a function class can fit random noise, allowing the algorithm to bound the "approximation error"—the difference between the loss on the current subset and the true loss on the full dataset.
As a meta-algorithm, BET acts as a wrapper for existing high-performance solvers like L-BFGS. It ensures that computation is not wasted on redundant data early on, but provides the full dataset's precision when needed for final convergence. The authors provide a rigorous proof (Theorem 4.1) showing that BET achieves an optimal complexity bound, reaching a target error $\epsilon$ with logarithmic dependence on the initial error.
Experimental Evaluation
The authors evaluated BET on two distinct datasets representing opposite ends of the machine learning spectrum: HIGGS (10.5 million samples, 28 dimensions) and url (1.8 million samples, 3.2 million dimensions).
Key Results and Insights
- HIGGS Dataset: BET behaves similarly to SGD in this "low-dimensional, high-volume" setting, achieving peak accuracy rapidly and often converging before requiring the full dataset.
- url Dataset: In this "high-dimensional, sparse" space, BET quickly identifies the need for more data to handle the complex feature geometry, transitioning into a full-batch mode that outperforms the plateaus often seen with SGD.
- Efficiency: As shown in the results, BET reaches target accuracy and low function values significantly faster than standard batch methods while matching or exceeding the initial speed of ParSGD. It effectively removes the need for manual batch-size tuning, as expansion is dictated by the underlying geometry of the data.
Conclusion
Batch-Expansion Training offers a theoretically grounded and practically efficient solution to the stochastic-vs-batch dilemma. By leveraging PRC to guide batch expansion, it automates the tuning of batch-size schedules and provides robust performance across varying data scales and dimensionalities. While current proofs rely on strong convexity, future work may extend these bounds to non-convex landscapes like deep neural networks and explore more sophisticated importance sampling strategies.
Summary updated