On the Batch Size Selection in Stochastic Gradient Methods Using No-Replacement Sampling

Alberto De Santis; Marco Boresta; Stefano Lucidi

REVIEW 3 major objections 4 minor 13 references

On the Batch Size Selection in Stochastic Gradient Methods Using No-Replacement Sampling

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Under no-replacement sampling, a batch-size rule keeps the stochastic gradient batch size bounded by the dataset size while preserving global convergence, instead of growing without bound as the variance tolerance shrinks.

desk verdict A clean, correct derivation of a bounded batch-size rule for no-replacement SGD, but the convergence guarantee is borrowed and unverified, and there is no empirical validation. read the letter →

arxiv 2506.08758 v1 pith:5UOF64JW submitted 2025-06-10 math.OC

Marco Boresta , Alberto De Santis , Stefano Lucidi This is my paper

classification math.OC MSC 90C1565K0590C26

keywords stochasticgradientdescentbatchsizeselectionsamplingwithoutreplacementvariancereductionfinite-populationcorrectionglobalconvergencevariance-controlledSGDmachinelearningoptimization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stochastic gradient methods that converge globally do so by keeping the variance of the batch gradient estimate under control, and the standard way to do that is to grow the batch as the optimization proceeds. The variance formula used in the literature assumes sampling with replacement, and it makes the required batch size grow without bound as the tolerance shrinks. This paper replaces that formula with the exact finite-population variance for sampling without replacement, $\mathrm{Var}[\nabla_{S_n}F] = (\mathrm{Var}[\nabla f_i]/N_S)\cdot(N-N_S)/(N-1)$, and enforces the same variance-control condition on it. The resulting batch-size rule stays below the dataset size $N$ and rises smoothly toward $N$ instead of going to infinity. If the paper is right, the same global convergence guarantee is preserved while the batch-size schedule becomes bounded, smoother, and more realistic to implement in practice.

What carries the argument

The central object is the finite-population variance identity for the no-replacement batch gradient: $\mathrm{Var}[\nabla_{S_n}F] = \frac{\mathrm{Var}[\nabla f_i]}{N_S}\frac{N-N_S}{N-1}$. It is proved by counting that each component appears in ${N-1\choose N_S-1}$ of the ${N\choose N_S}$ equally likely batches and by reading off the average within-batch covariance from the special case $N_S=N$. Substituting this identity into the variance-control condition (Assumption 1, equation (3)) produces the bounded batch-size rule of equation (14), which is the mechanism that carries the global convergence and smoothness conclusions of the paper.

What would settle it

Compute, for a small finite sum such as $N=4$, $N_S=2$, the exact variance of the no-replacement batch gradient over all batches and compare it with $\mathrm{Var}[\nabla f_i](N-N_S)/(N_S(N-1))$; a mismatch would break the batch-size rule (14). A second check is to run iteration (2) with this rule on a smooth finite-sum problem with a summable tolerance sequence: if the iterates do not approach a stationary point while the variance condition holds, the inherited convergence guarantee has failed.

Watch

Extended reading notes

Core claim

The paper claims that a batch-size rule designed for no-replacement sampling satisfies the variance-control assumption that underpins global convergence of stochastic gradient methods, with a strictly more practicable bound. For a uniformly drawn batch of size $N_S$ from $N$ components, the variance of the gradient estimate is not $\mathrm{Var}[\nabla f_i]/N_S$ but $\mathrm{Var}[\nabla f_i]\cdot(N-N_S)/(N_S(N-1))$, the usual finite-population correction. Imposing the variance-control condition on this quantity yields the update rule $N_S \ge N\,\mathrm{Var}[\nabla f_i]/((N-1)\varepsilon_k + \mathrm{Var}[\nabla f_i])$, whose right-hand side is always strictly below $N$. Hence the batch size never needs to diverge as $\varepsilon_k$ tends to zero, and its trajectory is smoother than that of the replacement-based rule. The derivation is a direct combinatorial accounting of the uniform distribution over all ${N\choose N_S}$ batches, including an evaluation of the average within-batch covariance, which turns out to be negative and equal to $-\mathrm{Var}[\nabla f_i]/(N-1)$.

Load-bearing premise

The argument rests on accepting that driving the batch-gradient variance below a shrinking tolerance sequence is enough to force global convergence; this implication is taken from a cited theorem, and the paper does not verify that its step sizes or objective functions satisfy that theorem's hypotheses.

Editorial extensions

If this is right

With the no-replacement rule, every batch size stays at or below $N$, so variance control no longer forces batch sizes to diverge as the tolerance tends to zero.
The iteration (2) using this rule inherits the global convergence guarantee carried by the variance-control condition, provided the hypotheses of the underlying cited theorem are satisfied.
At the same variance tolerance, the no-replacement rule demands a smaller batch size than the replacement-based rule, because of the factor $(N-1)$ in the denominator.
The smoother batch-size trajectory can reduce the computational overhead of repeatedly sampling the same examples and may make training dynamics more stable on large-scale problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's claims, the same finite-population correction could be inserted into other variance-controlled stochastic gradient algorithms, giving them bounded batch-size rules without re-deriving their convergence arguments.
The paper leaves the tolerance sequence $\varepsilon_k$ unspecified; a practical extension is to estimate $\mathrm{Var}[\nabla f_i]$ online from sampled gradients, and the rule (14) is well suited to that because it saturates at $N$ instead of overshooting.
A direct test the authors do not run: on a large logistic-regression or neural-network task, drive replacement-based and no-replacement schedules with the same $\varepsilon_k$ sequence and compare training progress per unit of compute; the no-replacement rule should use fewer samples and never need truncation.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This is a short, honest note. The genuinely new object is the batch-size rule (14), which follows from plugging the no-replacement variance formula (9) into the variance-control condition (3). The rule stays bounded by N and grows more gradually than the replacement-based rule (7), which is a real practical advantage. The derivation of Proposition 2.2 is algebraically correct and matches the classical finite-population correction, though the authors do not cite the sampling-theory origin, which is a small oversight. The paper is also transparent that its convergence claim is inherited from Franchini et al. (2023b, Thm 2.2); it does not try to pass off the variance bound as a full convergence proof.

The soft spots are real but moderate. The main one is that the paper never states the hypotheses of the cited theorem—step-size selection, line-search conditions, or regularity of F. Without those, Assumption 1 alone (summable epsilon_k) is not sufficient for global convergence of iteration (2); an arbitrary learning rate can still diverge. So the guarantee is inherited, not established for this scheme. The authors should either quote the theorem's conditions or at least state explicitly that the scheme is intended to be embedded in the algorithm of Franchini et al., with the same step-size rule. This is fixable with a paragraph.

Second, there are no experiments. Figure 1 is just a plot of the two formulas, not a numerical study. The authors acknowledge this in the conclusion, but a single practical test would strengthen the claim that the smoother batch-size update actually helps. Third, implementing (14) requires knowing Var[∇f_i(x)] at each iterate, which is not available in practice; the paper mentions an upper bound C but does not discuss how to estimate it during training. That is a practical gap worth addressing.

None of these are load-bearing flaws. The math is correct, the motivation is clear, and the contribution, while thin, is a small but useful alternative to the replacement-based rule. It is the kind of result that belongs in a workshop paper or a short note, not a major journal. I would send it to peer review: a knowledgeable referee can quickly verify the variance formula and check whether the cited theorem's conditions are satisfied. A revision that states those conditions, cites the sampling literature, and adds one empirical experiment would make this an acceptable publication. The paper is not ground-breaking, but it is a fair, serious piece of work.

Referee Report

3 major / 4 minor

Summary. The paper studies batch-size selection for stochastic gradient methods when mini-batches are drawn without replacement. It derives the variance of the no-replacement batch gradient estimate in Proposition 2.2, obtains the classical finite-population correction factor (N-N_S)/(N-1), and proposes the batch-size rule (14) that enforces the variance-control condition of Assumption 1. The paper argues that this rule is preferable to the replacement-based rule (7) because the required batch size remains bounded by N and grows more smoothly. The main theoretical claim is that the proposed rule 'ensures global convergence' of the SGD iteration (2), but this claim is inherited from an unstated theorem in earlier work rather than established in the manuscript.

Significance. If the convergence claim were fully established, the paper would provide a useful theoretical justification for a bounded and smoother batch-size schedule compared with the replacement-based approach. The variance derivation in Proposition 2.2 is algebraically sound and matches the well-known finite-population correction, and the comparison between the two sampling schemes is clear and instructive. The paper is, however, very short: the central convergence guarantee is borrowed, the implementation of the rule is not specified, and the promised numerical experiments are absent. The contribution is therefore a conditional one: a correct variance computation and a plausible batch-size update, whose practical and theoretical benefits are not yet substantiated within the manuscript itself.

major comments (3)

[Section 2, Assumption 1 and Eq. (3); Section 3] The claim that the proposed batch-size rule (14) 'ensures global convergence' is not established in this paper: it is inherited from Theorem 2.2 of Franchini et al. (2023b), whose hypotheses on the objective F, the step sizes alpha_k, and the line-search procedure are neither stated nor verified for iteration (2). A bounded variance condition with summable epsilon_k is not by itself sufficient for convergence of the recursion (2); an arbitrary sequence alpha_k can fail to converge even when Var_k <= epsilon_k and sum epsilon_k < infinity. The authors must either state the full theorem and check its assumptions, or prove convergence directly for their scheme.
[Section 2.2, Eq. (14)] The batch-size rule (14) depends on Var[grad f_i(x^(k))] = (1/N) sum_i ||grad f_i(x^(k)) - grad F(x^(k))||^2, which requires the full gradient and all component gradients at every iteration. The paper does not describe how this quantity is estimated or upper-bounded in the algorithm, other than mentioning an upper bound C in the discussion of Figure 1. Without an estimation procedure, the proposed update rule is not implementable, and the comparison in Figure 1 uses an arbitrary C = 10 rather than a quantity actually available to the optimizer.
[Section 4] The paper promises numerical experiments ('Section 4 describes the numerical experiments performed to validate our approach') and the abstract and conclusion claim that the method is 'more efficient' and leads to 'more stable training dynamics', but the manuscript contains no experimental section beyond the illustrative Figure 1: there are no datasets, baselines, optimization runs, or convergence curves. The practical benefits asserted in the introduction and conclusion are therefore unsubstantiated.

minor comments (4)

[Assumption 1 and Proposition 2.2] The relationship between E_k and E should be clarified: as written, E_k is a random variable (conditional on x^(0),...,x^(k)), while E[...] is defined as the expectation over the batch with x^(k) fixed, so the equality E_k[...] = E[...] needs a conditioning argument or a definitional clarification.
[Proof of Proposition 2.2] In the variance proof, the line '0 = Var[...] from which (12) Cov[...]' has a numbering error: the displayed equation labeled (12) actually defines the average covariance, and Eq. (13) gives its value. Also, in the unbiasedness proof, 'grad F(X)' should be 'grad F(x^(k))'.
[Section 2.2, Eq. (14)] The statement that the right-hand side of (14) is 'always less than N' should be made precise: it is less than N for epsilon_k > 0, and it approaches N only in the limit as epsilon_k goes to 0.
[Figure 1] Figure 1 is referenced in the text, but the full text contains only the caption; the actual plot is missing, and the axes and units are not described.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the batch-size rule is a direct algebraic consequence of the finite-population variance formula and the externally stated variance-control condition.

full rationale

The paper's derivation chain is self-contained. Assumption 1 (Eq. 3) is taken, with attribution, from Theorem 2.2 of Franchini et al. (2023b), which is an external published convergence result and not authored by the present authors. The replacement-based variance formula (Eq. 6) and no-replacement variance formula (Eq. 9) are derived by standard sampling algebra with no hidden use of the batch-size rule. The proposed rule (Eq. 14) is obtained by simply solving Var[f_i(x)](N-N_S)/(N-1) <= epsilon_k for N_S; it is the exact minimal batch size satisfying Assumption 1 under the no-replacement formula, so no fitted parameter is renamed as a prediction and no quantity is defined in terms of the rule itself. The global-convergence claim is inherited from the cited theorem, and the paper does not restate that theorem's step-size, line-search, or objective-function hypotheses; this is a completeness/correctness gap, not a circular one, because the cited theorem is independent external support. There are no self-citations that are load-bearing and no ansatz smuggled in via citation. The practical issue that Var[f_i(x)] must be bounded or estimated when implementing (14) is an implementation detail, not circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central derivation uses no fitted constants; the only hand-set inputs are C and the epsilon_k schedule. No new physical or mathematical entities are introduced.

free parameters (2)

C (upper bound on component-gradient variance) = C = 10 in Figure 1
Batch-size formulas (7) and (14) require a bound or estimate of Var[f_i(x)]; C=10 is chosen by hand for the illustration, and the paper gives no procedure for setting it in practice.
epsilon_k (variance tolerance schedule)
Assumption 1 requires a summable positive sequence epsilon_k, but the paper does not specify how to generate it; the resulting batch-size trajectory depends on this choice.

assumptions (3)

domain assumption Variance-control condition (Assumption 1) is sufficient for global convergence of the stochastic gradient iteration.
Invoked in Section 2, Eq. (3); credited to Franchini et al. (2023b), but the paper does not state the step-size and objective conditions required by that theorem.
domain assumption Uniform simple random sampling without replacement over all (N choose N_S) batches.
Used in Proposition 2.2 to compute expectation and variance over the discrete uniform measure on batches; real implementations may use shuffling or other schemes that are related but not identical to i.i.d. uniform random batches.
standard math Differentiability of each f_i and finiteness of component-gradient variance.
Problem (1) and the variance expressions require finite gradients and finite second moments of the component gradients.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Batch Size Selection in Stochastic Gradient Methods Using No-Replacement Sampling." pith.science (2026). https://pith.science/paper/5UOF64JW

@misc{pith2026250608758,
  author       = {Pith},
  title        = {Pith review of: On the Batch Size Selection in Stochastic Gradient Methods Using No-Replacement Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5UOF64JW}},
  note         = {Machine review of arXiv:2506.08758}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2506.08758 by the authors.

**Figure 1.** Batch Size Growth Comparison. Red: Sampling Without Replacement. Blue: Sampling With Replacement (truncated at N) References Beneventano, P., 2024. On the trajectories of sgd without replacement. URL: https://arxiv.org/abs/2312.16143, arXiv:2312.16143. Franchini, G., Porta, F., Ruggiero, V., Trombini, I., 2023a. A line search based proximal stochastic gradient algorithm with dynamical variance reduction. Journal of … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 5 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...
[2]

, year 2024

author Beneventano, P. , year 2024 . title On the trajectories of sgd without replacement . https://arxiv.org/abs/2312.16143, arXiv:2312.16143 http://arxiv.org/abs/2312.16143

arXiv 2024
[3]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , year 2023 a. title A line search based proximal stochastic gradient algorithm with dynamical variance reduction . journal Journal of Scientific Computing volume 94 , pages 23

work page 2023
[4]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , author Zanni, L. , year 2023 b. title Learning rate selection in stochastic gradient methods based on line search strategies . journal Applied Mathematics in Science and Engineering volume 31 , pages 2164000

work page 2023
[5]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , author Zanni, L. , year 2024 . title A stochastic gradient method with variance control and variable learning rate for deep learning . journal Journal of Computational and Applied Mathematics , pages 116083

work page 2024
[6]

, author Gower, R

author Gazagnadou, N. , author Gower, R. , author Salmon, J. , year 2019 . title Optimal mini-batch and step sizes for SAGA , in: editor Chaudhuri, K. , editor Salakhutdinov, R. (Eds.), booktitle Proceedings of the 36th International Conference on Machine Learning , publisher PMLR . pp. pages 2142--2150 . https://proceedings.mlr.press/v97/gazagnadou19a.html

work page 2019
[7]

, year 2016

author Shamir, O. , year 2016 . title Without-replacement sampling for stochastic gradient methods , in: editor Lee, D. , editor Sugiyama, M. , editor Luxburg, U. , editor Guyon, I. , editor Garnett, R. (Eds.), booktitle Advances in Neural Information Processing Systems , publisher Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2...

work page 2016
[8]

, " * write output.state after.block = add.period write newline

ENTRY address archive author booktitle chapter doi edition editor eid eprint howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all ...

Show all 13 references

[9]

write newline

" write newline "" before.all 'output.state := FUNCTION add.period duplicate empty 'skip "." * add.blank if FUNCTION if.digit duplicate "0" = swap duplicate "1" = swap duplicate "2" = swap duplicate "3" = swap duplicate "4" = swap duplicate "5" = swap duplicate "6" = swap dupl...
[10]

, " * write output.state after.block = add.period write newline

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...
[11]

write newline

" write newline "" before.all 'output.state := FUNCTION if.digit duplicate "0" = swap duplicate "1" = swap duplicate "2" = swap duplicate "3" = swap duplicate "4" = swap duplicate "5" = swap duplicate "6" = swap duplicate "7" = swap duplicate "8" = swap "9" = or or or or or or...
[12]

, " * write output.state after.block = add.period write newline

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...
[13]

write newline

" write newline "" before.all 'output.state := FUNCTION if.digit duplicate "0" = swap duplicate "1" = swap duplicate "2" = swap duplicate "3" = swap duplicate "4" = swap duplicate "5" = swap duplicate "6" = swap duplicate "7" = swap duplicate "8" = swap "9" = or or or or or or...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...

[2] [2]

, year 2024

author Beneventano, P. , year 2024 . title On the trajectories of sgd without replacement . https://arxiv.org/abs/2312.16143, arXiv:2312.16143 http://arxiv.org/abs/2312.16143

arXiv 2024

[3] [3]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , year 2023 a. title A line search based proximal stochastic gradient algorithm with dynamical variance reduction . journal Journal of Scientific Computing volume 94 , pages 23

work page 2023

[4] [4]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , author Zanni, L. , year 2023 b. title Learning rate selection in stochastic gradient methods based on line search strategies . journal Applied Mathematics in Science and Engineering volume 31 , pages 2164000

work page 2023

[5] [5]

, author Porta, F

author Franchini, G. , author Porta, F. , author Ruggiero, V. , author Trombini, I. , author Zanni, L. , year 2024 . title A stochastic gradient method with variance control and variable learning rate for deep learning . journal Journal of Computational and Applied Mathematics , pages 116083

work page 2024

[6] [6]

, author Gower, R

author Gazagnadou, N. , author Gower, R. , author Salmon, J. , year 2019 . title Optimal mini-batch and step sizes for SAGA , in: editor Chaudhuri, K. , editor Salakhutdinov, R. (Eds.), booktitle Proceedings of the 36th International Conference on Machine Learning , publisher PMLR . pp. pages 2142--2150 . https://proceedings.mlr.press/v97/gazagnadou19a.html

work page 2019

[7] [7]

, year 2016

author Shamir, O. , year 2016 . title Without-replacement sampling for stochastic gradient methods , in: editor Lee, D. , editor Sugiyama, M. , editor Luxburg, U. , editor Guyon, I. , editor Garnett, R. (Eds.), booktitle Advances in Neural Information Processing Systems , publisher Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2...

work page 2016

[8] [8]

, " * write output.state after.block = add.period write newline

ENTRY address archive author booktitle chapter doi edition editor eid eprint howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all ...