{"id":"16e94d84-dc47-4c44-899b-356ca8a950a4","arxiv_id":"2506.23303","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Minibatch SGD with decreasing stochastic Polyak stepsizes keeps iterates bounded under a sublevel-set condition that includes coercive convex objectives, and specific unbounded cases are constructed.","lead":"Minibatch SGD with decreasing Polyak step sizes is proved to keep its iterates bounded for coercive convex objectives, not only strongly convex ones. The paper also constructs sampling patterns that make the iterates escape to infinity, so it maps where this adaptive step size is safe and where it is not.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.8's induction relies on the unstated assumption that x_k is never a minimizer of the sampled batch; the zero-gradient case is patchable, but the written proof is conditional.","rationale":"The reader's weakest_assumption and my stress-test point to the same place: Theorem 3.8's proof needs x_k not in argmin f_Bk to derive the strict decrease from (7), yet this is not a stated hypothesis and is not established for the randomized batch process. I checked the surrounding argument: the definitions of D, c, M, the use of Proposition 3.7, and the triangle inequality with gamma Lmax are otherwise consistent, and no independent counterexample to the boundedness claim emerged. The zero-gradient equality case is actually harmless for the truth of the theorem because the SGD update leaves the iterate fixed, so a one-line case split repairs the proof. The edge case where I is empty (often D=0) is also harmless but is not handled by the written definition of M. Because the paper's proof is incomplete as written but the central claim appears correct with a small repair, the existing CONDITIONAL verdict is appropriate and unchanged.","tokens_in":8307,"tokens_out":20822,"duration_ms":230663,"concrete_test":"Rewrite the induction step of Theorem 3.8 after (7) with a case split: (a) if grad f_Bk(x_k)=0, use x_{k+1}=x_k and the induction hypothesis to conclude ||x_{k+1}||^2 <= max{4c^2(1+gamma Lmax)^2, ||x0||^2}; (b) if grad f_Bk(x_k)!=0, then x_k is not in argmin f_Bk, so f_Bk(x_k)-mu_Bk > 2D/(2-m) and Proposition 3.7 gives the strict decrease. Verify the remaining inequalities hold with no other use of the blanket resampling assumption. Also re-check the case I=empty/D=0 with M defined as 0. If both checks pass, the central boundedness result is valid as stated and only the exposition needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 3.8. After deriving (7), the proof states that for the sampled batch either f_Bk(x_k)=mu_Bk or f_Bk(x_k)>mu_Bk+2D/(2-m), and then discards the equality case using the blanket assumption after Remark 3.6 that x_k is never a minimizer of the sampled batch. That assumption is not a hypothesis of Theorem 3.8, and the paper gives no proof that the stochastic batch process satisfies it. If the equality case occurs, Proposition 3.7 only yields ||x_{k+1}||^2 <= ||x_k||^2 + 2 gamma_k (f_Bk(0)-mu_Bk), which need not be smaller than the induction bound, so the written induction collapses. The gap is repairable: if grad f_Bk(x_k)=0, then (SGD) gives x_{k+1}=x_k, so the induction bound carries over; if the gradient is nonzero, x_k is not in argmin f_Bk and (8) follows. A second, minor edge case is that M := max_{B in I} M_B is undefined when I is empty (e.g., D=0); setting M=0 or treating D=0 separately fixes it. The theorem appears true, but as written its proof depends on an unproved resampling premise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8669,"tokens_out":8018,"duration_ms":84775,"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":[{"comment":"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":"Section 3.2, Theorem 3.8 proof, after Eq. (8)"},{"comment":"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":"Section 3.2, Theorem 3.8 proof, definition of M"},{"comment":"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.","section":"Section 3.3, case (C3)"}],"minor_comments":[{"comment":"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.","section":"After Remark 3.6"},{"comment":"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":"Theorem 3.4 proof"},{"comment":"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.","section":"Section 3.3, displayed derivation"},{"comment":"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.","section":"Notation, Section 2 and Eq. (1)"},{"comment":"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.","section":"Miscellaneous"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is sound in spirit and the proof gap described in the first major comment is straightforwardly patched by handling the zero-gradient step. The editor may wish to check whether the companion preprint [2] is publicly available, since Section 3.3 relies on it for two nontrivial claims. With those revisions the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nThere'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.\n\nFor 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.","headline":"A solid extension of the DecSPS boundedness result with a small repairable proof gap; worth reviewing after a patch.","tokens_in":9098,"tokens_out":3612,"would_cite":true,"duration_ms":34609,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C25","65K05","68T07","68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that minibatch SGD iterates stay bounded for coercive convex objectives, not just strongly convex ones.","keywords":["minibatch stochastic gradient descent","Polyak stepsize","decreasing stepsize","bounded iterates","coercive convex function","convex optimization","level-set condition"],"falsifier":"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.","tokens_in":8141,"feed_emoji":"📉","tokens_out":9874,"duration_ms":92343,"temperature":0.7,"pith_summary":"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.","feed_headline":"Minibatch SGD iterates stay bounded for coercive convex objectives","feed_subtitle":"The decreasing Polyak stepsize now provably bounds iterates for coercive convex objectives.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines DecSPS, supplies the two-sided stepsize bound used in Corollary 3.10, and is the previous strong-convexity boundedness result this paper relaxes.","marker":"[10]"},{"why":"Lemma 2.28, the gradient lower bound for smooth convex functions, is used in Remark 3.5 to show any bounded stepsize satisfies condition (1) with $m=2L_{\\max}\\gamma$.","marker":"[5]"},{"why":"Fact 2.11, the convergence of the deterministic gradient method with diminishing stepsizes, is used in Theorem 3.4 to build the divergent example for case (C1).","marker":"[4]"},{"why":"The coercivity and level-set equivalences characterize condition (C2) and the sufficient condition that at least $N-b+1$ components be coercive.","marker":"[1]"},{"why":"Supplies the polyhedral projection boundedness result and the blow-up example that delimit case (C3).","marker":"[2]"}],"fun_headline_variants":["Boundedness proof for minibatch SGD drops strong convexity","Coercive objectives guarantee bounded minibatch SGD iterates","Broadening boundedness of minibatch SGD iterates","SGD with Polyak stepsize: bounded iterates for coercive losses","Minibatch SGD stays bounded without strong convexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Boundedness proof for minibatch SGD drops strong convexity","Coercive objectives guarantee bounded minibatch SGD iterates","Broadening boundedness of minibatch SGD iterates","SGD with Polyak stepsize: bounded iterates for coercive losses","Minibatch SGD stays bounded without strong convexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00018,"raw_usage":{"total_tokens":1254,"prompt_tokens":844,"completion_tokens":410,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":460,"completion_tokens_details":{"reasoning_tokens":323}},"tokens_in":460,"tokens_out":410,"duration_ms":4365,"temperature":1.0,"reasoning_tokens":323,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:47:59.879133+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Orvieto, S","cited_arxiv_id":null,"evidence_quote":"Defines DecSPS, supplies the two-sided stepsize bound used in Corollary 3.10, and is the previous strong-convexity boundedness result this paper relaxes."},{"cited_title":"Bertsekas: Nonlinear Programming, 3rd edition, Athena Scientific, 2016","cited_arxiv_id":null,"evidence_quote":"Fact 2.11, the convergence of the deterministic gradient method with diminishing stepsizes, is used in Theorem 3.4 to build the divergent example for case (C1)."},{"cited_title":"Bauschke and P .L","cited_arxiv_id":null,"evidence_quote":"The coercivity and level-set equivalences characterize condition (C2) and the sufficient condition that at least $N-b+1$ components be coercive."},{"cited_title":"Bauschke and T.T","cited_arxiv_id":null,"evidence_quote":"Supplies the polyhedral projection boundedness result and the blow-up example that delimit case (C3)."}],"review_version":1}