On the Role of Batch Size in Stochastic Conditional Gradient Methods

• URL: http://arxiv.org/abs/2603.21191v1
• Date: Sun, 22 Mar 2026 12:23:41 GMT
• Title: On the Role of Batch Size in Stochastic Conditional Gradient Methods
• Abstract summary: We study the role of batch size in conditional gradient methods under a $$-Kurdyka-ojasiewicz ($$-KL) condition.<n>Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy but, beyond a critical threshold, the benefits and saturate can degrade performance under a fixed token budget.
• Score: 51.97510367368799
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study the role of batch size in stochastic conditional gradient methods under a $μ$-Kurdyka-Łojasiewicz ($μ$-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.

Related papers

• Deriving Hyperparameter Scaling Laws via Modern Optimization Theory [55.63126290312615]
  We study modern first-order boundss for methods based on the Linear Minimization Oracle (LMO)<n>Treating bounds in recent literature as a proxy and minimizing them across different tuning regimes yields closed-form power-law schedules for learning rate, momentum, and batch size.<n>Our results draw particular attention to the interaction between momentum and batch-size scaling, suggesting that optimal performance may be achieved with several scaling strategies.
  arXiv  Detail & Related papers  (2026-03-16T22:21:27Z)
• Optimal Growth Schedules for Batch Size and Learning Rate in SGD that Reduce SFO Complexity [0.6906005491572401]
  Batch-size and learning-rate scheduling in computational gradient methods can degrade efficiency and compromise convergence.<n>We theoretically derived optimal growth schedules for the batch size and learning rate that reduce SFO complexity.<n>Our results offer both theoretical insights and practical guidelines for scalable and efficient large-batch training in deep learning.
  arXiv  Detail & Related papers  (2025-08-07T11:52:25Z)
• Beyond First-Order: Training LLMs with Stochastic Conjugate Subgradients and AdamW [2.028622227373579]
  gradient-based descent (SGD) have long been central to training large language models (LLMs)<n>This paper proposes a conjugate subgradient method together with adaptive sampling specifically for training LLMs.
  arXiv  Detail & Related papers  (2025-07-01T23:30:15Z)
• AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods [17.043034606088234]
  We introduce AdAdaGrad's scalar variant AdAdaGradNorm, which increase sizes during training. We also perform image classification experiments, highlighting the merits of our proposed strategies.
  arXiv  Detail & Related papers  (2024-02-17T07:49:50Z)
• Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization [0.6906005491572401]
  We show that noise in batch descent (SGD) has the effect of smoothing objective function.<n>We show that there is an interesting relationship between the degree of smoothing by SGDs noise, and the well-studied sharpness' indicator.
  arXiv  Detail & Related papers  (2023-11-15T07:27:40Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  Gradient Descent (SGD) and its variants have become the dominant methods in the large-scale optimization machine learning (ML) problems. We provide formal guarantees of a few convex optimization methods and proposing improved algorithms.
  arXiv  Detail & Related papers  (2022-07-31T19:41:22Z)
• Sample Efficient Reinforcement Learning with REINFORCE [10.884278019498588]
  We consider classical policy gradient methods and the widely-used REINFORCE estimation procedure. By controlling number of "bad" episodes, we establish an anytime sub-linear high regret bound as well as almost sure global convergence of the average regret with anally sub-linear rate. These provide the first set of global convergence and sample efficiency results for the well-known REINFORCE algorithm and contribute to a better understanding of its performance in practice.
  arXiv  Detail & Related papers  (2020-10-22T01:02:55Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
  We show that a host of variations can be covered in a unified framework that we propose. We prove the convergence of this novel scheme and rigorously evaluate its empirical performance on ResNet, LSTM, and Transformer.
  arXiv  Detail & Related papers  (2020-06-10T08:22:41Z)
• Adaptive Learning of the Optimal Batch Size of SGD [52.50880550357175]
  We propose a method capable of learning the optimal batch size adaptively throughout its iterations for strongly convex and smooth functions. Our method does this provably, and in our experiments with synthetic and real data robustly exhibits nearly optimal behaviour. We generalize our method to several new batch strategies not considered in the literature before, including a sampling suitable for distributed implementations.
  arXiv  Detail & Related papers  (2020-05-03T14:28:32Z)
• Large Batch Training Does Not Need Warmup [111.07680619360528]
  Training deep neural networks using a large batch size has shown promising results and benefits many real-world applications. In this paper, we propose a novel Complete Layer-wise Adaptive Rate Scaling (CLARS) algorithm for large-batch training. Based on our analysis, we bridge the gap and illustrate the theoretical insights for three popular large-batch training techniques.
  arXiv  Detail & Related papers  (2020-02-04T23:03:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.