On the boundedness of the sequence generated by minibatch stochastic gradient descent

Heinz H. Bauschke; Tran Thanh Tung

REVIEW 3 major objections 5 minor 11 references

On the boundedness of the sequence generated by minibatch stochastic gradient descent

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper proves that minibatch SGD iterates stay bounded for coercive convex objectives, not just strongly convex ones.

desk verdict A solid extension of the DecSPS boundedness result with a small repairable proof gap; worth reviewing after a patch. read the letter →

arxiv 2506.23303 v1 pith:BQ4SFMVO submitted 2025-06-29 math.OC math.FA

Heinz H. Bauschke , Tran Thanh Tung This is my paper

classification math.OCmath.FA MSC 90C1590C2565K0568T0768W2068W40

keywords minibatchstochasticgradientdescentPolyakstepsizedecreasingboundediteratescoerciveconvexfunctionoptimizationlevel-setcondition

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

Minibatch stochastic gradient descent with a decreasing Polyak stepsize (DecSPS) is shown to keep its iterates bounded for a broad class of convex objectives, not only strongly convex ones. The central theorem applies to any stepsize satisfying the inequality $\gamma_k \|\nabla f_{B_k}(x_k)\|^2 \le m (f_{B_k}(x_k) - \mu_{B_k})$ with $m<2$ and $\gamma_k$ bounded, provided every batch function has a minimizer and its lower level sets outside the argmin are bounded. This class includes coercive convex functions, so the earlier convergence result for DecSPS, which assumed bounded iterates, now holds without that extra assumption when $\lambda_0<2$. The paper also constructs a case where a batch without a minimizer leads to divergence, and a boundary case where boundedness can go either way.

What carries the argument

The load-bearing object is the recursion of Proposition 3.7, $\|x_{k+1}\|^2 \le \|x_k\|^2 - (2-m)\gamma_k (f_{B_k}(x_k)-\mu_{B_k}) + 2\gamma_k (f_{B_k}(0)-\mu_{B_k})$, obtained by expanding the SGD update and using convexity together with the stepsize condition (1). Condition (C2) supplies the threshold mechanism: far from the batch minimizers, $f_{B_k}(x_k)$ is forced to exceed $\mu_{B_k}+2D/(2-m)$, making the negative term strictly dominate the positive constant, so the squared norm decreases whenever the iterate is large. The proof threads these two facts with a sharpened triangle inequality involving the batch minimizer $x^*_{B_k}$, which controls how far the iterate can be from the minimizer in terms of the next iterate and the Lipschitz constant $L_{\max}$.

What would settle it

To falsify Theorem 3.8, exhibit a finite family of convex, smooth, bounded-below functions whose batch functions satisfy (C2), a stepsize rule satisfying (1) with $m<2$ and $0<\gamma_k\le\gamma$, and an explicit sampling sequence respecting the resampling rule, for which the iterates leave every ball of finite radius. A concrete test: run DecSPS with $\lambda_0=1.5$ on a coercive but non-strongly-convex finite sum (e.g., a convex function that is flat near its minimizer and quadratic at infinity) and check whether the iterates diverge; any unbounded trajectory would contradict Corollary 3.10.

Watch

Extended reading notes

Core claim

The paper's central discovery is Theorem 3.8: if every batch function has a minimizer and its lower-level sets, with the minimizers removed, are bounded (condition (C2)), then any SGD sequence whose stepsizes satisfy (1) with $m<2$ and $0<\gamma_k\le \gamma$ is bounded. The proof is an induction on a squared-norm bound: when an iterate is large, smoothness and the level-set condition force $f_{B_k}(x_k)-\mu_{B_k}$ to exceed a fixed threshold, and then the negative term in the recursion dominates the constant term, so the norm cannot escape the bound. Applied to DecSPS, whose stepsizes obey (1) with $m=\lambda_0$, this gives boundedness for all $\lambda_0<2$. The paper thereby replaces the strong-convexity assumption used in previous boundedness proofs with the much weaker geometric condition (C2), which holds, for instance, when enough components of the finite sum are coercive.

Load-bearing premise

The proof depends on the unproven premise that at every iteration the current point is not a minimizer of the sampled batch; the paper's response is to resample when the gradient is zero, but it does not prove such a resampling sequence can always be chosen.

Editorial extensions

If this is right

Any stepsize rule satisfying (1) with $m<2$ and bounded above by $\gamma$ automatically produces bounded iterates for objectives satisfying (C2), so the boundedness guarantee is not tied to DecSPS itself.
DecSPS with $\lambda_0<2$ generates bounded iterates whenever the finite-sum objective satisfies (C2), which in particular covers coercive convex objectives; this removes the boundedness assumption from the earlier convergence theorem.
If some batch function has no minimizer, there exists a batch-sampling sequence for which DecSPS iterates diverge to infinity, so condition (C2) is sharp in ruling out divergence from this mechanism.
In the intermediate case (C3), where batch minimizers exist but level sets outside them can be unbounded, boundedness is delicate: for relaxed random projections onto unbounded polyhedral sets a boundedness condition holds, while dropping polyhedrality allows divergent examples.

Reading between the lines

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

The most fragile point is the resampling premise that each $x_k$ is not a minimizer of its sampled batch; if that premise cannot be guaranteed by the stochastic model, the induction in Theorem 3.8 fails at the step where it excludes the argmin case. A natural next step is to prove that zero-gradient batch draws have small probability, or to modify the stepsize when the gradient is near zero.
Because (C2) is implied by having at least $N-b+1$ coercive components in the finite sum, the theorem gives a checkable, pre-run condition for boundedness of DecSPS on practical objectives.
The same squared-norm induction may transfer to other adaptive or line-search stepsizes that satisfy an inequality of the form (1) with $m<2$, suggesting the bound is a general stability principle rather than a DecSPS-specific calculation.
The (C3) examples connect the boundedness question to the geometry of relaxed random projections; one could numerically probe where the boundary between boundedness and blow-up lies for non-polyhedral constraint sets.

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

The short version: this is a real extension of the DecSPS boundedness result, and the main theorem is correct, but the proof has a small gap that needs a patch. The paper deserves review, and after that patch it should be publishable.

What's new: [10] proved boundedness of the iterates for DecSPS only under strong convexity. Bauschke and Tung replace that with condition (C2)—every batch has a minimizer and its lower level sets away from the minimizer are bounded—which covers coercive finite sums. Corollary 3.10 gives boundedness for DecSPS with λ0<2 under (C2). They also give a clean divergence example when some batch has no minimizer (Theorem 3.4). The C1–C3 classification is helpful and the exposition is clear.

The main proof uses a standard potential inequality (Proposition 3.7) and an induction. The weakness is in Theorem 3.8: after deriving that x_k is outside the lower-level set minus argmin for every batch, the proof says f_Bk(x_k) either equals µ_Bk or exceeds the threshold, and then discards the equality case by invoking the standing assumption after Remark 3.6 that x_k is never a minimizer of the sampled batch. That assumption is not in the theorem statement, and the paper doesn't prove that a sampling sequence satisfying it exists under the stochastic model. If you hit the equality case, the induction as written collapses. The stress-test note is right about this. But the fix is straightforward: if ∇f_Bk(x_k)=0, then x_{k+1}=x_k, so the induction bound carries over; otherwise you're in the nonzero-gradient case and the strict inequality (8) follows. So the theorem is correct as stated, after a one-line patch.

There's also a minor edge case: M is the max over batches I, which can be empty when D=0. Setting M=0 or treating D=0 separately fixes it. One more small thing: the C3 section relies on the companion preprint [2] for the key boundedness and divergence results. That's fine if the companion is real, but worth a referee checking whether those claims are solid.

For whom: this is theory for the stochastic optimization community, especially people working on Polyak stepsizes. It doesn't change practice, but it cleans up a known restriction. I'd take it seriously and send it to a referee. After a minor revision, I'd be happy to see it published.

Referee Report

3 major / 5 minor

Summary. The paper studies boundedness of iterates generated by minibatch SGD with decreasing Polyak-type stepsizes for finite-sum convex smooth objectives. It partitions batch functions into three cases: (C1) some batch has no minimizer, (C2) every batch has a minimizer and its lower level sets with the minimizer removed are bounded, and (C3) the remaining case. The main results are Theorem 3.4, constructing in case (C1) a batch sampling sequence for which the iterates escape to infinity; Theorem 3.8, proving boundedness in case (C2) under a stepsize inequality (1) with m < 2 and bounded stepsizes; and Corollaries 3.9 and 3.10, which specialize to constant stepsizes and to DecSPS with lambda_0 < 2. Section 3.3 discusses case (C3) via relaxed random projections, partly relying on a companion preprint.

Significance. If Theorem 3.8 is correct, it is a useful extension of the DecSPS analysis of Orvieto, Lacoste-Julien, and Loizou: it replaces strong convexity with the geometric condition (C2), which is satisfied by coercive convex batch functions, and it removes the a-priori boundedness assumption on the iterates. The paper is mostly self-contained and uses standard convex analysis; Theorem 3.4 provides a nice counterexample for the missing-argmin case. At the same time, the central proof of Theorem 3.8 currently depends on an unstated resampling premise and contains a small edge-case gap, both of which are repairable without changing the theorem statement.

major comments (3)

[Section 3.2, Theorem 3.8 proof, after Eq. (8)] The induction step invokes the phrase 'Since we assumed xk notin argmin fBk' to discard the equality case fBk(xk) = µBk. This resampling assumption appears only in the informal paragraph after Remark 3.6 and is not a hypothesis of Theorem 3.8; the paper does not prove that the stochastic batch process satisfies it. In the equality case, Proposition 3.7 only gives ||xk+1||^2 <= ||xk||^2 + 2γk(fBk(0) - µBk), which need not be below the induction bound, so the written induction collapses. The gap is repairable: if ∇fBk(xk)=0, then xk+1 = xk and the induction bound carries over; if the gradient is nonzero, then xk cannot be an argmin of the convex differentiable batch function, so (8) follows. The theorem appears true, but as written its proof is conditional on an unproved premise.
[Section 3.2, Theorem 3.8 proof, definition of M] The proof defines M := max_{B in I} M_B, but M is undefined when I is empty, which can happen for instance when D=0. Since the subsequent argument uses c >= M, the proof needs to define M = 0 in that case or treat the case I = ∅ separately. This is a small edge case, but it appears inside the proof of the main theorem and should be fixed.
[Section 3.3, case (C3)] The boundedness and blow-up statements for the relaxed random projection algorithm are quoted from the companion preprint [2] (Theorem 2.5 and Example 4.1) without restating their proofs. If [2] is not yet publicly available or accepted, the claims in Section 3.3 cannot be verified from the manuscript alone; at minimum the dependence should be marked as conditional or the relevant arguments should be included in an appendix.

minor comments (5)

[After Remark 3.6] The informal resampling convention should either be listed as an explicit hypothesis in Theorem 3.8 and Corollaries 3.9 and 3.10, or replaced by the zero-gradient/skip-step argument described in the major comment, so that the theorem statement is self-contained.
[Theorem 3.4 proof] The sentence 'if we were to sample the same batch B at every step' is informal; the proof should state explicitly that the constructed sequence of batches is the deterministic sequence with Bk = B for all k, which is a valid realization of the sampling model.
[Section 3.3, displayed derivation] The derivation around equation (9) uses the same symbol λk for the DecSPS parameter and could be simplified; the current display with nested min-expressions is hard to read.
[Notation, Section 2 and Eq. (1)] The paper uses µ for infimum in the introduction and also µB for arbitrary lower bounds in (1). Using distinct symbols, for example µB^* for the infimum and m_B for a lower bound, would avoid ambiguity about whether equality fB(x) = µB implies that x is a minimizer.
[Miscellaneous] There are minor typographical issues, including '1 −smooth' in Section 3.3, which should read '1-smooth', and unnumbered intermediate display equations that could be numbered for readability.

Circularity Check

1 steps flagged · score 2.0 of 10

Peripheral self-citation carries the (C3) boundedness/unboundedness claims; the main Theorem 3.8 is self-contained.

self citation load bearing [Section 3.3, Case (C3), after equation (9)]
"By [2, Theorem 2.5], if min {λ0, 2γ−1} < 4, then the sequence (xk)k∈N generated by (9) is bounded. If we drop polyhedrality and let λk = γ−1 = 2 for all k ∈ N, then one can construct two sets C1, C2 such that (C3) is satisfied and there exists a sampling of sets such that the sequence (xk)k∈N generated by (9) blow up to infinity (see [2, Example 4.1])."

The paper's case-(C3) conclusion that boundedness may or may not hold is not proved here; it is imported from the authors' own companion preprint [2], both for the boundedness theorem ([2, Theorem 2.5]) and for the blow-up example ([2, Example 4.1]). The text then uses these imported results to assert 'Even in this special case, we've seen that the sequence of iterates ... can either be bounded or unbounded.' Since [2] is an unverified same-author preprint and no independent derivation is supplied, this secondary claim reduces to a self-citation. It is peripheral because the main boundedness result (Theorem 3.8) and its corollaries do not depend on [2].

full rationale

The core of the paper, Theorem 3.8 and Corollaries 3.9–3.10, is self-contained: it builds on standard convex analysis (Lemma 2.6, Fact 2.11), the stepsize condition (1), and the structural assumption (C2). Proposition 3.7 is a direct descent-type estimate, and the induction in Theorem 3.8 follows from that estimate without invoking any fitted quantity or renaming. The proof does rely on the extra assumption, imported from [10, Remark 1], that x_k is never a minimizer of the sampled batch; this is an unproved premise, but it is not a circularity—it is a gap in the written theorem statement and is repairable, since the zero-gradient case gives x_{k+1}=x_k. The only genuine self-citation issue is in the secondary Section 3.3, where the boundedness and blow-up claims for case (C3) are taken verbatim from the authors' companion preprint [2]. Because that section is peripheral to the main theorem, the overall circularity score is 2 rather than higher.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No fitted parameters appear; the stepsize constants lambda_0 and gamma_-1 are user-specified, not inferred from data. The central proof rests on the (C2) geometric hypothesis, the resampling convention, and standard convex-analysis facts. The only reliance on an unpublished companion work is in the peripheral (C3) discussion.

assumptions (6)

domain assumption Each f_i is convex, L_i-smooth, and bounded below; f = (1/N) sum f_i; minibatches are sampled independently and uniformly.
Used throughout; guarantees batch functions are convex and L_max-smooth (Remarks 2.2 and 2.4).
domain assumption Condition (C2): for every batch B of size b, argmin f_B is nonempty and lev<=xi f_B minus argmin f_B is bounded for all xi.
Main hypothesis of Theorem 3.8 and Corollaries 3.9-3.10; covers coercive functions.
ad hoc to paper Resampling assumption: x_k is not in argmin f_{B_k} for all k, so the gradient of the sampled batch is nonzero.
Stated after Remark 3.6; adopted from [10, Remark 1], needed for the induction step of Theorem 3.8.
domain assumption Step-size condition (1): there exists m < 2 with gamma_k times the squared gradient norm bounded by m times the batch function gap.
Hypothesis of Theorem 3.8; for DecSPS it holds with m = lambda_0 via Remark 3.6, requiring lambda_0 < 2.
standard math Standard convex-analysis facts: Lemma 2.6 gradient lower bound, Fact 2.5 descent lemma, Fact 2.11 asymptotic properties of gradient methods.
External textbook facts used in the proofs of Theorems 3.4 and 3.8.
ad hoc to paper Theorem 2.5 and Example 4.1 of the authors' companion preprint [2] are invoked without restating their proofs.
Peripheral discussion of case (C3); the boundedness and blow-up conclusions there depend on unpublished companion work by the same authors.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the boundedness of the sequence generated by minibatch stochastic gradient descent." pith.science (2026). https://pith.science/paper/BQ4SFMVO

@misc{pith2026250623303,
  author       = {Pith},
  title        = {Pith review of: On the boundedness of the sequence generated by minibatch stochastic gradient descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BQ4SFMVO}},
  note         = {Machine review of arXiv:2506.23303}
}

read the original abstract

Stochastic Gradient Descent (SGD) with Polyak's stepsize has recently gained renewed attention in stochastic optimization. Recently, Orvieto, Lacoste-Julien, and Loizou introduced a decreasing variant of Polyak's stepsize, where convergence relies on a boundedness assumption of the iterates. They established that this assumption holds under strong convexity. In this paper, we extend their result by proving that boundedness also holds for a broader class of objective functions, including coercive functions. We also present a case in which boundedness may or may not hold.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

[10]

Orvieto, S

A. Orvieto, S. Lacoste-Julien, and N. Loizou: Dynamics of SGD with Stochastic Polyak Stepsizes: Truly adaptive variants and convergence to exact solution, Advances in Neural Information Processing Systems 35 (2024), 26943–26954. https://papers.neurips.cc/paper_files/paper/2022/file/ ac662d74829e4407ce1d126477f4a03a-Paper-Conference.pdf

work page 2024
[2]

Bauschke and T.T

H.H. Bauschke and T.T. Tran: On a result by Meshulam, arXiv preprint (2025)

work page 2025
[1]

Bauschke and P .L

H.H. Bauschke and P .L. Combettes: Convex Analysis and Monotone Operator The- ory in Hilbert Spaces , 2nd edition, Springer, 2017. https://doi.org/10.1007/ 978-3-319-48311-5

work page 2017
[3]

Beck: First-Order Methods in Optimization , SIAM, 2017

A. Beck: First-Order Methods in Optimization , SIAM, 2017. https://doi.org/10. 1137/1.9781611974997

work page 2017
[4]

Bertsekas: Nonlinear Programming, 3rd edition, Athena Scientific, 2016

D.P . Bertsekas: Nonlinear Programming, 3rd edition, Athena Scientific, 2016

work page 2016
[5]

Garrigos and R.M

G. Garrigos and R.M. Gower: Handbook of convergence theorems for (stochastic) gradient methods, arXiv preprint (2024). https://arxiv.org/pdf/2301.11235

arXiv 2024
[6]

Loss Landscape Characterization of Neural Networks without Over-Parametrization

R. Islamov, N. Ajroldi, A. Orvieto, and A. Lucchi: Loss Landscape Characterization of Neural Networks without Over-Parametrization, arXiv preprint (2024), https: //arxiv.org/pdf/2410.12455

work page Pith review arXiv 2024
[7]

Jiang and S.U

X. Jiang and S.U. Stich: Adaptive SGD with Polyak stepsize and Line-search: Ro- bust Convergence and Variance Reduction,Advances in Neural Information Processing Systems 36 (2023), 26396–26424. https://proceedings.neurips.cc/paper_files/ paper/2023/file/540eb9e0ee35d525231c3fd22d1dcbf2-Paper-Conference.pdf

work page 2023

Show all 11 references

[8]

Loizou, S

N. Loizou, S. Vaswani, I. Hadj Laradji, and S. Lacoste-Julien: Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics 130 (2021), 1306–1314. https://proceed...

2021
[9]

Oikonomou and N

D. Oikonomou and N. Loizou: Stochastic Polyak Step-sizes and Momentum: Con- vergence Guarantees and Practical Performance, arXiv preprint (2024). https:// arxiv.org/pdf/2406.04142

2024 arXiv
[11]

Rockafellar: Convex Analysis, Princeton University Press, 1970

R.T. Rockafellar: Convex Analysis, Princeton University Press, 1970. 11

1970

Pith tools

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

[1] [10]

Orvieto, S

A. Orvieto, S. Lacoste-Julien, and N. Loizou: Dynamics of SGD with Stochastic Polyak Stepsizes: Truly adaptive variants and convergence to exact solution, Advances in Neural Information Processing Systems 35 (2024), 26943–26954. https://papers.neurips.cc/paper_files/paper/2022/file/ ac662d74829e4407ce1d126477f4a03a-Paper-Conference.pdf

work page 2024

[2] [2]

Bauschke and T.T

H.H. Bauschke and T.T. Tran: On a result by Meshulam, arXiv preprint (2025)

work page 2025

[3] [1]

Bauschke and P .L

H.H. Bauschke and P .L. Combettes: Convex Analysis and Monotone Operator The- ory in Hilbert Spaces , 2nd edition, Springer, 2017. https://doi.org/10.1007/ 978-3-319-48311-5

work page 2017

[4] [3]

Beck: First-Order Methods in Optimization , SIAM, 2017

A. Beck: First-Order Methods in Optimization , SIAM, 2017. https://doi.org/10. 1137/1.9781611974997

work page 2017

[5] [4]

Bertsekas: Nonlinear Programming, 3rd edition, Athena Scientific, 2016

D.P . Bertsekas: Nonlinear Programming, 3rd edition, Athena Scientific, 2016

work page 2016

[6] [5]

Garrigos and R.M

G. Garrigos and R.M. Gower: Handbook of convergence theorems for (stochastic) gradient methods, arXiv preprint (2024). https://arxiv.org/pdf/2301.11235

arXiv 2024

[7] [6]

Loss Landscape Characterization of Neural Networks without Over-Parametrization

R. Islamov, N. Ajroldi, A. Orvieto, and A. Lucchi: Loss Landscape Characterization of Neural Networks without Over-Parametrization, arXiv preprint (2024), https: //arxiv.org/pdf/2410.12455

work page Pith review arXiv 2024

[8] [7]

Jiang and S.U

X. Jiang and S.U. Stich: Adaptive SGD with Polyak stepsize and Line-search: Ro- bust Convergence and Variance Reduction,Advances in Neural Information Processing Systems 36 (2023), 26396–26424. https://proceedings.neurips.cc/paper_files/ paper/2023/file/540eb9e0ee35d525231c3fd22d1dcbf2-Paper-Conference.pdf

work page 2023