On the Batch Size Selection in Stochastic Gradient Methods Using No-Replacement Sampling Marco Boresta, Alberto De Santis, Stefano Lucidi Abstract Recent stochastic gradient methods that have appeared in the literature base their efficiency and global convergence properties on a suitable control of the variance of the gradient batch estimate. This control is typically achieved by dynamically increasing the batch size during the iterations of the algorithm. However, in the existing methods the statistical analysis often relies on sampling with replacement. This particular batch selection appears unrealistic in practice. In this paper, we consider a more realistic approach to batch size selection based on sampling without replacement. The consequent statistical analysis is compared to that of sampling with replacement. The new batch size selection method, while still ensuring global convergence, provides a more accurate representation of the variance reduction observed in practice, leading to a smoother and more efficient batch size update scheme. keywords Stochastic Gradient Descent ,Batch Size Selection † † corresponding: Corresponding author 1 Introduction Batch size selection in stochastic gradient methods is crucial for controlling the variance of gradient estimates, which directly impacts the convergence of optimization algorithms. This is particularly important in large-scale machine learning tasks, where evaluating the full gradient is computationally expensive. Recent works, such as Franchini et al. 2023a , and its extensions Franchini et al. 2023b ; Franchini et al. 2024 , have introduced efficient strategies to dynamically adjust the batch size. These strategies are grounded in theoretical analyses (see e.g. Theorem 2.2 of Franchini et al. 2023b ) which show that global convergence of the stochastic gradient algorithms can be achieved by controlling the variance of the gradient batch estimate. In these methods, variance reduction is typically achieved by increasing the batch size during iterations of the algorithm. The variance bounds in Franchini et al. 2023b and Franchini et al. 2024 refer to the form of the variance of the gradient batch estimate obtained by a statistical analysis that follows the hypothesis of performing a sampling scheme with replacement. This scheme allows multiple selections of the same items within a batch, and this can be computationally inefficient and unrealistic. In practice, multiple choice should be avoided and this can be obtained by sampling without replacement. The selection of each item is no longer independent of the others, leading to a different formula for the variance of the gradient estimate. While both schemes imply that the variance decreases as the batch size increases, the variance formula for the replacement-based approach implies that the batch size increases indefinitely, since the variance must go to zero to ensure global convergence. In contrast, the no-replacement scheme introduces a natural upper bound based on the dataset size and results in smoother batch size updates. The differences between these two approaches become more apparent at larger batch sizes. Other features of stochastic gradient methods with no replacement are studied in Beneventano 2024 , Gazagnadou et al. 2019 , Shamir 2016 . Our contribution is to propose a more realistic sampling scheme leading to a batch size selection procedure that can reduce computational overhead while maintaining theoretical convergence properties. The paper is organized as follows. In Section 2, we analyze batch selection strategies, comparing sampling with and without replacement. Section 3 presents the proposed method and theoretical results. Section 4 describes the numerical experiments performed to validate our approach. Finally, Section 5 concludes the paper and suggests directions for future research. 2 Batch selection analysis In this section, we propose a novel approach for selecting the batch size in stochastic gradient methods. Our scheme builds upon the convergence results studied in Franchini et al. 2023a ; Franchini et al. 2023b . Specifically, we aim to address limitations related to controlling the variance of stochastic gradient estimates during the optimization process. This paper addresses the optimization problem: \min_{x\in\mathbb{R}^{d}}F(x)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x), (1) where each function f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R} is differentiable. We focus on scenarios where the number of components N is significantly large. In such cases, computing the full function F(x) and the full gradient \nabla F(x)=\frac{1}{N}\sum_{i=1}^{N}\nabla f_{i}(x) is impractical. Therefore, we approximate F(x) and \nabla F(x) by using a smaller subset (batch) S , with size N_{S}