On the Role of Batch Size in Stochastic Conditional Gradient Methods

We study the role of batch size in stochastic conditional gradient methods under a $\mu$-Kurdyka–Łojasiewicz ($\mu$-KL) condition. Focusing on momentum-based stochastic Frank–Wolfe–type conditional gradient algorithms (e.g., Scion), we derive a new analysis that explicitly captures the interaction between stepsize, batch size, and stochastic noise. Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy, but beyond a critical threshold, the benefits saturate and can eventually degrade performance under a fixed token budget. Notably, the theory predicts the magnitude of the optimal stepsize and aligns well with empirical practices observed in large-scale training. Leveraging these insights, we derive principled guidelines for selecting the batch size and stepsize, and propose an adaptive strategy that increases batch size and sequence length during training while preserving convergence guarantees. Preliminary experiments are consistent with the theoretical predictions and illustrate the emergence of the predicted scaling regimes. Overall, our results provide a theoretical framework for understanding batch-size scaling in stochastic conditional gradient methods and offer guidance for designing efficient training schedules in large-scale optimization.

When training large machine learning models, practitioners must decide how much data to process at each training step. This choice, known as the batch size, can strongly affect both training speed and final performance. In this work, we study how batch size should be chosen for a class of optimization methods that are useful in large-scale training. Our analysis shows that larger batches are helpful only up to a point. At first, increasing the batch size improves training, but after a critical threshold, the benefits become small and may even hurt performance when the total training budget is fixed. We also show how the best learning-rate-like parameter changes with batch size and training budget, and our predictions match empirical trends seen in large-scale experiments. These insights lead to practical rules for choosing batch size and step size. We also propose a training strategy that gradually increases the batch size and sequence length during training while maintaining theoretical guarantees. Preliminary experiments support the theory and show the predicted scaling patterns. Overall, this work helps explain when larger batches are useful and guides the design of more efficient training schedules for large machine learning models.