On the Role of Batch Size in Stochastic Conditional Gradient Methods

Rustem Islamov 1,4, † \dagger , Roman Machacek 2 , Aurelien Lucchi 1 , Antonio Silveti-Falls 3 Eduard Gorbunov 4, ⋆ \star , Volkan Cevher 5, ⋆ \star · 2026

Read On the Role of Batch Size in Stochastic Conditional Gradient Methods by Rustem Islamov 1,4, † \dagger , Roman Machacek 2 , Aurelien Lucchi 1 , Antonio Silveti-Falls 3 Eduard Gorbunov 4, ⋆ \star , Volkan Cevher 5, ⋆ \star (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21191.txt.

Introduction

Islamov and co-authors study batch size in stochastic conditional gradient methods. They work under a Kurdyka-Łojasiewicz condition and focus on momentum based methods such as Scion. Their analysis ties stepsize, batch size, and noise together. Larger batches first improve accuracy, then the gains saturate. The theory predicts the best stepsize and matches large scale training practice. They propose a schedule that grows batch size during training while keeping convergence guarantees. NanoGPT tests fit the predictions.

Catalog record

CREATORRustem Islamov 1,4, † \dagger , Roman Machacek 2 , Aurelien Lucchi 1 , Antonio Silveti-Falls 3 Eduard Gorbunov 4, ⋆ \star , Volkan Cevher 5, ⋆ \star
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92024
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21191

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Role of Batch Size in Stochastic Conditional Gradient Methods Rustem Islamov 1,4, † \dagger , Roman Machacek 2 , Aurelien Lucchi 1 , Antonio Silveti-Falls 3 Eduard Gorbunov 4, ⋆ \star , Volkan Cevher 5, ⋆ \star 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. $\dagger$ $\dagger$ footnotetext: Most of this work was done when Rustem Islamov was a visiting student in the group of Prof. Eduard Gorbunov at MBZUAI, UAE. $\star$ $\star$ footnotetext: The last two authors share senior authorship. 1 Introduction Large-scale language model training is constrained by a token budget T rather than by a fixed number of optimization steps. In this regime, we face a familiar batch size tradeoff: increasing the batch size B improves hardware utilization, yet beyond a certain scale it can degrade optimization efficiency and hurt generalization ( 13 ; 23 ; 42 ; 41 ) . A token budget-aware viewpoint makes this tradeoff explicit. With batch size B and sequence length S , the number of parameter updates is K\coloneqq\frac{T}{BS}, and hence (B,S) and the stepsize jointly determine how effectively the token budget is converted into optimization progress. This coupling raises a central question in model training: how should (B,S) and the stepsize be chosen, and adapted, to optimize performance under a fixed token budget T ? Recent empirical studies have further refined this picture. In particular, critical batch sizes – the point at which scaling B stops being beneficial – appear to scale primarily with the effective data size and only weakly with model size under a fixed token budget ( 53 ; 2 ) . Additionally, the critical batch threshold is often stage-dependent, motivating warmup and stage-wise training schedules ( 31 ) . Taken together, these findings suggest that the batch size should be treated as a dynamic optimization variable rather than a fixed hyperparameter. However, these insights remain largely empirical: they do not provide explicit optimization error laws as functions of (B,S,T) , nor do they characterize when increasing batch size becomes provably detrimental under a fixed token budget. In parallel, hyperparameter transfer frameworks such as \mu P have shown that, with appropriate parameterization and initialization, gradient magnitudes can be kept \Theta(1) across model scales, enabling stable training without retuning learning rates ( 49 ; 47 ; 48 ) . However, these results are inherently local: they ensure that individual updates neither explode nor vanish, but do not address how batch size, sequence length, and stepsize should scale globally with the token budget. Our work bridges this gap by showing that hyperparameters that are locally optimal for a given (B,S,T) can become provably suboptimal as the token budget increases, even under \mu P-style initialization. To obtain such global scaling laws, we derive an analysis for stochastic conditional gradient (SCG) methods ( 34 ) , a projection-free framework that underlies several modern norm-constrained training algorithms. This class of algorithms is closely aligned with modern optimizers such as Muon ( 20 ) . Our analysis is carried out for stochastic optimization ( 1 ) under smoothness ( A1 ) in a general norm, norm equivalence ( A2 ), and a \mu -Kurdyka–Łojasiewicz ( \mu -KL) error bound ( A3 ) ( 22 ; 4 ) . The \mu -KL condition is particularly well matched to SCG geometry, as it relates first-order stationarity to suboptimality measured in the dual norm induced by the linear minimization oracle (LMO). Specializing our convergence bounds to the fixed-token setting T=KBS yields an explicit, non-monotone dependence of the achievable optimization error on the effective batch–sequence scale BS . Three regimes emerge: (i) a noise-dominated regime where increasing BS improves performance, (ii) an intermediate regime where the best achievable error is essentially independent of BS , and (iii) a large-batch regime where performance deteriorates as BS grows under a fixed token budget. Balancing the dominant terms yields a critical effective batch–sequence–token (BST) scale rule BS\asymp T^{2/3} up to problem-dependent factors that we derive in this work, revealing how curvature, noise, geometry, and error-bound strength shift the optimal operating point. Importantly, our analysis shows that large batch sizes do not inherently degrade performance: when batch size, sequence length, and learning rate are chosen according to our BST scaling rule, large-batch training remains effective and token-efficient. In contrast to \mu P, our perspective disentangles local stability, as controlled by parameterization and initialization, from global efficiency, as governed by token-budget–aware optimization. Our contributions are as follows: • Convergence guarantees for momentum SCG under \mu -KL. We establish convergence guarantees for Algorithm 1 under the \mu -KL condition ( A3 ) in a general normed geometry, explicitly tracking the effects of momentum, smoothness, and stochastic gradient noise. Our bounds hold in expectation under bounded-variance and L -smoothness assumptions. • A token-budget view of batch, sequence length, and stepsize scaling. By translating iteration complexity into token complexity via T=KBS , we obtain explicit (B,S,T) -dependent error laws and identify the critical effective batch size BS that separates beneficial from harmful scaling. • Actionable adaptive scheduling rules. We turn the theory into concrete recipes for choosing and updating (\beta,B,S) during training under a fixed token budget, yielding the scaling relations ( 7 )–( 8 ) and a two-stage (and more generally multi-stage) protocol validated empirically on NanoGPT ( cf. , Figure 2 ). Our results complement classical large-batch heuristics such as linear learning rate scaling with warmup ( 13 ) and adaptive batch size schedules ( 42 ) , while offering a projection-free viewpoint rooted in conditional gradient geometry. They are also consistent with empirical observations that there exists a largest useful batch size depending on training stage and problem statistics ( 30 ; 41 ) , and provide an explicit optimization-side mechanism for the “too-large batch hurts” regime under a fixed token budget. 2 Related Works Assumptions in SCG methods: smoothness. Convergence analyses for stochastic conditional gradient (SCG) (aka Frank–Wolfe) methods and, more broadly, LMO-based methods, have been conducted under various assumptions. Most analyses, including our analysis, assume standard L -smoothness. However, recent works consider relaxed notions, such as (L_{0},L_{1}) -smoothness ( 54 ) and other extensions beyond global smoothness ( 35 ; 38 ) . Extending our analysis to

Read the complete text