Abstract
We focus on solving constrained convex optimization problems using mini-batch stochastic gradient descent. Dynamic sample size rules are presented which ensure a descent direction with high probability. Empirical results from two applications show superior convergence compared to fixed sample implementations.
Introduction
Stochastic Gradient Descent (SGD) is the foundational algorithm for large-scale optimization. However, its performance is heavily dependent on the choice of mini-batch size, which governs a critical trade-off between computational efficiency and gradient accuracy. Small mini-batches are computationally inexpensive but produce noisy estimates that may lead the algorithm away from the optimal solution. Conversely, large mini-batches provide high-fidelity gradients but incur significant computational costs per iteration, often slowing down the wall-clock time to convergence.
Most practitioners rely on fixed batch sizes (e.g., 32, 128, or 512) determined through trial and error. This paper introduces a principled framework to dynamically adjust the mini-batch size, ensuring that every step taken is a "descent direction" with a high degree of statistical confidence.
Methodology
The core of the proposed approach is to treat the descent direction as a statistical constraint. By leveraging the Central Limit Theorem (CLT), the algorithm models the gradient estimate as a normal distribution. Using the sample covariance of gradients calculated during the current iteration, the method predicts the required number of samples ($N^{i+1}$) for the subsequent iteration to maintain a desired confidence level ($1-\alpha$).
Two primary rules for dynamic sample size selection are proposed:
- Per Dimension Update (PD): This rule evaluates each component of the gradient vector individually. It calculates the specific sample size needed for each dimension to ensure the sign of the estimated gradient matches the sign of the true gradient. To ensure robustness against outliers in high-dimensional space, the algorithm utilizes the median of these calculated sample sizes across all dimensions.
- Single Update (1D): This is a more aggregate approach that ensures the inner product of the estimated gradient and the true gradient remains positive. This condition guarantees that the step moves the function value downward with high probability.
An important practical finding is that assuming independence between gradient terms (using only the diagonal of the covariance matrix) often improves performance by reducing the computational overhead associated with estimating a full covariance matrix.
Experimental Evaluation
The dynamic sampling methods were evaluated on two complex, constrained convex optimization problems:
- Multi-product Newsvendor Problem: An operations research challenge involving 50 products with correlated demands and a risk-averse utility function.
- Options Portfolio Problem: A financial engineering task focused on finding the optimal growth portfolio for 50 stocks using European call and put options, where stock returns follow geometric Brownian motion.
These applications are characterized by non-linear objective functions where gradient noise is particularly disruptive to convergence.
Key Results and Insights
The dynamic rules were benchmarked against fixed batch sizes of 32, 256, and 512 using both standard SGD and the Adam optimizer.
- Superior Convergence: In both test cases, the dynamic rules—particularly the Per Dimension (PD) rule—reached higher utility values significantly faster than any fixed-batch implementation.
- Adaptive Efficiency: The algorithm automatically reduces sample sizes when the gradient signal is clear and increases them when the optimization landscape becomes "murky" or noisy. This allows for rapid progress in early stages and high precision in later stages.
- The Median Advantage: The "median trick" proved essential for stability. By taking the median of sample size requirements across dimensions, the algorithm avoids being swayed by extreme variance in a single dimension, leading to a more stable and effective batch size.
Conclusion and Future Work
This research demonstrates that dynamic batch sizing is a versatile, "plug-and-play" enhancement for SGD variants. By transforming batch size from a static hyperparameter into a dynamic statistical tool, the algorithm achieves better stability and faster convergence.
However, limitations remain. The reliance on the CLT assumes that the initial batch size is large enough for the normal approximation to hold. Additionally, the method assumes the variance of the gradient does not change drastically between iterations. Future work may explore the application of these rules in highly non-convex landscapes, such as deep neural networks, where the gradient variance may be more volatile.
Summary updated