[2603.21191] On the Role of Batch Size in Stochastic Conditional Gradient Methods

Abstract: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 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. Experiments on NanoGPT 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.

[2603.21191] On the Role of Batch Size in Stochastic Conditional Gradient Methods Skip to main content arXiv is now an independent nonprofit! Learn more × Search arXiv Press Enter to search · Advanced search --> Computer Science > Machine Learning arXiv:2603.21191 (cs) [Submitted on 22 Mar 2026] Title: On the Role of Batch Size in Stochastic Conditional Gradient Methods Authors: Rustem Islamov , Roman Machacek , Aurelien Lucchi , Antonio Silveti-Falls , Eduard Gorbunov , Volkan Cevher View a PDF of the paper titled On the Role of Batch Size in Stochastic Conditional Gradient Metho

related reading

• Jane Street Blog - Does batch size matter?blog.janestreet.com
• [2101.12176] On the Origin of Implicit Regularization in Stochastic Gradient Descentarxiv.org
• Stochastic gradient descent - Wikipediaen.m.wikipedia.org
• Why Momentum Really Worksdistill.pub
• [1512.04202] Preconditioned Stochastic Gradient Descentarxiv.org
• [2601.05034] How to Set the Batch Size for Large-Scale Pre-training?arxiv.org
• IsoCompute Playbook: Optimally Scaling Sampling Compute for RL Training of LLMscompute-optimal-rl-llm-scaling.github.io
• The Practitioner's Guide to the Maximal Update Parameterization | EleutherAI Blogblog.eleuther.ai
• The Practitioner’s Guide to the Maximal Update Parameterization - Cerebrascerebras.ai
• [2605.15522] Stochastic Non-Smooth Convex Optimization with Unbounded Gradientsarxiv.org
• Reiner Pope – The math behind how LLMs are trained and serveddwarkesh.com
• Notes on the Origin of Implicit Regularization in SGDinference.vc