{"id":"52258c51-1a43-42bd-8843-ca68db5cf7b1","arxiv_id":"2501.08256","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A rigorous proof shows that Robbins-Monro stochastic approximation with projections onto a hyperrectangle converges to stationary points of the associated projected ODE, filling a gap in Kushner and Yin's classic text.","lead":"This math paper supplies a missing step in the classic proof that projected stochastic approximation algorithms converge, for the case where the constraint set is a rectangle. The gap is filled by a new equicontinuity argument that also relaxes earlier bounded-noise assumptions for stochastic proximal gradient methods.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The key projection estimate (3.8)-(3.9) is not proved as written: it conflates pre- and post-projection states, so Theorem 3.1's equicontinuity and Lipschitz conclusions rest on an off-by-one that must be corrected.","rationale":"The reader's weakest_assumption correctly identifies the hyperrectangle structure as load-bearing, but my concern is sharper: even within that structure, the displayed proof of the key implication (3.8) is off by one because it treats x_{n_j} as the post-projection boundary state when it is actually the pre-projection state. The same off-by-one infects (3.7) and (3.9), and since those equations are the only mechanism controlling sums of projections, Theorem 3.1 is not fully proved as written. This is an internal consistency issue rather than a disagreement with consensus. The error appears very likely repairable by shifting indices and applying (3.6) to the post-projection interval, which is why a conditional rather than a rejection verdict remains appropriate. The applications in Section 4 inherit the problem because Theorem 4.2 explicitly relies on Theorem 3.1. I therefore keep the reader's CONDITIONAL verdict unchanged, while noting that the weakest point is not merely the extension from rectangles to general convex sets but the correctness of the projection bookkeeping inside the rectangle proof. No judgment about the authors is intended; these are ordinary index errors that a careful revision should resolve.","tokens_in":12975,"tokens_out":17271,"duration_ms":159535,"concrete_test":"Redo the projection bookkeeping in post-projection variables y_k := x_{k+1}. For consecutive nonzero-projection indices n_j and n_{j+1} in coordinate l, verify the correct identity P^l_{n_{j+1}} = y^l_{n_j} - y^l_{n_{j+1}} + sum_{k=n_j+1}^{n_{j+1}} γ_k(e^l_k + r^l_k + h^l(x_k)), and check whether (3.6) applied to the interval [n_j+1, n_{j+1}] proves y^l_{n_j} = y^l_{n_{j+1}} when sum_{k=n_j+1}^{n_{j+1}} γ_k < δ. Then re-derive (3.9) from this corrected identity. If the corrected identity is what was intended, Theorem 3.1 is salvageable; if it does not imply the same-boundary conclusion, the equicontinuity estimate for Z_n and the Lipschitz bound are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core of Theorem 3.1 is the estimate (3.12) for sums of projections, and that estimate depends entirely on implication (3.8) and identity (3.9). As written, the proof of (3.8) is invalid. In the paper's notation x_n is the state before the projection at step n; a nonzero P^l_n forces x^l_{n+1} to be a_l or b_l, not x^l_n. The sentence 'as in each point n_j, the projection is non-zero, we have that x^l_{n_j} is equal to a_l or b_l' is therefore false. Moreover, the quantity that must cross the opposite boundary at n_{j+1} is x^l_{n_{j+1}} + γ_{n_{j+1}}(...), which equals x^l_{n_j+1} + sum_{k=n_j+1}^{n_{j+1}} γ_k(...) (with no projection terms between), not x^l_{n_j} + sum_{k=n_j}^{n_{j+1}-1} γ_k(...) as used. The same off-by-one appears in (3.7), whose left side should be P^l_{n_j} (or the formula should be shifted to post-projection states), and it propagates into the telescoping identity (3.9). Because (3.9) is the only mechanism that makes projection sums small over short time intervals and is reused in the Lipschitz bound for Z, the central claim of Theorem 3.1 is not established as written. The issue is internal to the hyperrectangle case, so it is more basic than the acknowledged limitation to rectangles.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Robbins–Monro stochastic approximation recursion with Euclidean projection onto a hyperrectangle K, under standard decreasing step sizes and vanishing total error assumptions. It defines piecewise-constant interpolations X_n of the iterates and Z_n of cumulative projections, and claims (Theorem 3.1) that almost surely (X_n) and (Z_n) are equicontinuous in the extended sense and that every limit of Z_n is Lipschitz. Proposition 3.2 then identifies limits of (X_n, Z_n) with solutions of the projected ODE; Theorem 4.1 converts this into convergence to stationary points via a Lyapunov function, and Theorem 4.2 extends the result to stochastic proximal gradient algorithms. The paper positions itself as filling a gap in Kushner–Yin's proof by supplying the missing equicontinuity argument.","tokens_in":13228,"tokens_out":10106,"duration_ms":88770,"significance":"If the proof can be repaired, the result is a genuine and useful contribution: it isolates the mechanism of equicontinuity for projected SA on rectangles, avoids fitted parameters or circular assumptions, and gives an elementary ODE-method proof of a classical statement. The restriction to hyperrectangles is explicitly acknowledged and is natural for the coordinatewise projection argument, and the paper is honest about what remains open for general convex sets. However, the central estimate as written contains an indexing error that is load-bearing; until corrected, Theorem 3.1 is not established, so the claimed filling of the Kushner–Yin gap is conditional.","major_comments":[{"comment":"In the recurrence x_{k+1} = x_k + γ_k y_k - P_k with y_k = h(x_k) + e_k + r_k, the quantity x^l_{n_j} appearing in (3.7) is the pre-projection value, while a nonzero projection at n_j forces x^l_{n_j+1}, not x^l_{n_j}, to be a_l or b_l. The correct identity connecting consecutive nontrivial projection indices is P^l_{n_{j+1}} = x^l_{n_j+1} - x^l_{n_{j+1}+1} + ∑_{k=n_j+1}^{n_{j+1}-1} γ_k y^l_k, or equivalently in pre-projection terms P^l_{n_{j+1}} = x^l_{n_j} - x^l_{n_{j+1}+1} + ∑_{k=n_j}^{n_{j+1}} γ_k y^l_k - P^l_{n_j}. Equation (3.7) as printed drops the term P^l_{n_j} and uses the wrong boundary index. Consequently the sentence 'as in each point n_j, the projection is non-zero, we have that x^l_{n_j} is equal to a_l or b_l' is false, and implication (3.8) is not proved for the quantities used there. The same error propagates into the telescoping identity (3.9), which is the only mechanism in the proof for showing that the sum of projections over a short time interval is small.","section":"§3, proof of Theorem 3.1, Eqs. (3.7)–(3.9)"},{"comment":"The proof of the Lipschitz bound (3.13)–(3.14) invokes (3.9) directly. Since (3.9) is not established, the displayed bound for |Z^l_N(t) - Z^l_N(s)| is unsupported. This is not a cosmetic issue: the Lipschitz property is used in Proposition 3.2 to differentiate Z and to write the projected ODE. A corrected argument will need a separate estimate for the first nontrivial projection term P^l_{n_i} that survives after proper telescoping; the individual bound (3.10) is likely sufficient, but the proof must be rewritten before Theorem 3.1 can be accepted.","section":"§3, Lipschitz part of Theorem 3.1"}],"minor_comments":[{"comment":"Equation (3.25) states ˙x(t) = h(˙x(t)) - z(t); this should read ˙x(t) = h(X(t)) - z(t).","section":"§3, Proposition 3.2, after Eq. (3.24)"},{"comment":"The symbol f is used for the limit of X_{n_k} in the statement, but in Eq. (3.21) and surrounding text the limit function is written as X; please make the notation consistent.","section":"§3, Proposition 3.2, Eq. (3.21)"},{"comment":"The reference to the theorem in Kushner–Yin is given as Theorem 5.2.1 in the Introduction, Theorem V.2.1 in Section 2, and Theorem V.2.1 again in Section 3; please standardize the citation.","section":"§3 and §4, theorem numbering"},{"comment":"The proof of Theorem 4.1 is only described as following the lines of [22, Theorem 3.5]; since this is one of the paper's stated convergence results, please either provide the details or explicitly state it as a corollary of Theorem 3.1 and Proposition 3.2 with the hypotheses checked.","section":"§4, Theorem 4.1"},{"comment":"Reference [17] lacks a publication year and reference [26] lacks publisher information; please complete the bibliographic data.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The off-by-one error is real and sits in the main proof, but I recommend major revision rather than rejection because the coordinatewise projection idea is sound and the individual bound (3.10) appears capable of absorbing the missing first-projection term after a correct telescoping. The applications section leans substantially on [22], which is transparently acknowledged and not circular. The decision should hinge on whether the authors can supply a corrected version of Eqs. (3.7)–(3.9) and re-verify the Lipschitz bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the paper takes on a real problem—the missing equicontinuity step in Kushner and Yin's projected Robbins-Monro theorem—and the coordinate-wise rectangle strategy is a plausible way to do it. But the key projection estimate is wrong as written. The stress-test note is right. In (3.7) the left-hand index is off by one: the identity telescopes to P^l_{n_j}, not P^l_{n_{j+1}}, and the statement that a non-zero P^l_{n_j} forces x^l_{n_j} to the boundary should refer to x^l_{n_j+1}. The same slip propagates into (3.8)-(3.9) and into the Lipschitz part of Theorem 3.1. There is also a related index error in Proposition 3.2: P_n belongs to the normal cone at x_{n+1}, not at x_n. So the central theorem is not established as written.\n\nCredit where due: if the indexing is repaired, this would be a genuinely useful proof. The paper identifies a specific gap in a standard reference, gives a self-contained proof for the hyperrectangle case, and shows how the argument removes the bounded-noise assumption in the proximal SGD application. That last point is a real improvement over [22]. The paper is not circular: it proves what it can, and the applications honestly lean on [22]. No parameters are fitted, and no code or data are needed.\n\nSoft spots: besides the indexing bug, Proposition 3.2's displayed ODE contains a typo (h of x-dot instead of h of X). The applications are sketches; Theorem 4.2's proof is essentially the same argument as [22] plus Theorem 3.1. The claim that no complete proof exists elsewhere is plausible but not independently verified in the paper. The hyperrectangle restriction is acknowledged, so it is not a hidden flaw.\n\nProportion: this is not a desk-reject situation. The flaw is central but mechanical, and the overall approach looks sound enough that a careful referee could push the authors to a correct version. Audience: people who care about the foundations of projected stochastic approximation and anyone who cites Kushner-Yin 5.2.1 without checking it. My recommendation: send to peer review, with a referee asked to redo the projection-index bookkeeping.","headline":"A real gap in Kushner-Yin, a sensible coordinate-wise proof idea, and a genuine indexing bug in the key projection identity: worth refereeing, not citable as is.","tokens_in":13874,"tokens_out":8028,"would_cite":false,"duration_ms":70656,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","34D05","46B50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the projected Robbins-Monro algorithm converges on hyperrectangles, filling a missing step in the standard convergence proof.","keywords":["stochastic approximation","Robbins-Monro algorithm","ODE method","projection","hyperrectangle","equicontinuity","stochastic proximal gradient","convergence"],"falsifier":"To falsify the central claim, one would need to exhibit a hyperrectangle $K$, a bounded $h$, and step sizes and noise satisfying $(Con-\\gamma)$ and $(Con-e-r)$ for which the interpolated sequences are not equicontinuous; the paper's proof shows this cannot happen, so finding such an example would settle the question.","tokens_in":12666,"feed_emoji":"📦","tokens_out":11366,"duration_ms":102100,"temperature":0.7,"pith_summary":"The paper establishes a rigorous convergence proof for the projected stochastic approximation (Robbins-Monro) algorithm when the constraint set is a hyperrectangle. This fills a gap that remained open in the standard textbook treatment of projected stochastic approximation. Using the ODE method, the paper shows that the rescaled iterates and the cumulative projection terms are equicontinuous, and that any limit solves a projected ordinary differential equation. As a result, the iterates converge almost surely to the stationary points of that ODE whenever a natural Lyapunov condition holds. The proof also relaxes earlier assumptions in the analysis of stochastic proximal gradient methods by allowing unbounded noise.","feed_headline":"Projected stochastic approximation converges on hyperrectangles","feed_subtitle":"A complete ODE-method proof unlocks convergence for constrained stochastic optimization.","key_machinery":"The key machinery is the coordinate-wise decomposition of projections onto a hyperrectangle $K=\\prod_{i=1}^d[a_i,b_i]$, combined with the rescaled-time interpolation of the iteration. The critical estimate, inequality (3.8), states that if two consecutive nontrivial projections in coordinate $l$ occur within a total step size below a threshold, then the iterates must project to the same boundary point $a_l$ or $b_l$. This lets the sum of projection terms over any small step-size window be bounded by the corresponding sum of the drift terms $\\gamma_k(h(x_k)+e_k+r_k)$, which is already controlled by the step-size and noise assumptions. The interpolation and the Arzelà–Ascoli type compactness principle then turn this into equicontinuity of $(X_n)$ and $(Z_n)$, and the normal-cone calculus identifies the limit as a solution of the projected ODE.","core_discovery":"The central claim is that, with probability one, the sequences of rescaled iterates $(X_n)$ and cumulative projection terms $(Z_n)$ are equicontinuous in the extended sense, and every limit point $(X,Z)$ is a solution of the projected ODE $\\dot{x}=h(x)-z$ with $z\\in N_K(x)$. The proof isolates a structural property of projections onto a hyperrectangle: two consecutive nontrivial projections in the same coordinate, occurring within a sufficiently small total step size, must land on the same boundary value. This coordinate-wise control of projection sums is the missing piece that allows the equicontinuity argument to go through. The paper then derives convergence of the iterates to the stationary set of the projected ODE and extends the result to stochastic proximal gradient algorithms, proving convergence without requiring the noise sequence to be bounded.","pith_inferences":["The coordinate-wise argument suggests a possible template for other constraint sets whose faces are axis-aligned, such as orthants or boxes with slanted sides only in certain directions, although the paper itself does not claim this.","A natural opening for future work is to test whether the boundedness assumption on $h$ can be replaced by a growth condition combined with a stronger stability assumption; the paper explicitly keeps $h$ bounded.","The relaxation of bounded noise in the proximal gradient application hints that other stochastic approximation proofs that rely on bounded noise may admit the same relaxation when working with hyperrectangle constraints and the $(Con-e-r)$ conditions."],"forward_implications":["The projected Robbins-Monro algorithm converges almost surely to the set of stationary points of the projected ODE whenever a Lyapunov function with empty-interior stationary set exists, as stated in Theorem 4.1.","The stochastic proximal gradient algorithm, in both proximal-then-project and project-then-proximal forms, converges to the composite stationary set described by the Clarke gradient, under the same step-size and noise conditions, without requiring bounded noise (Theorem 4.2).","The bounded-noise assumption that appeared in earlier differential-inclusion treatments of nonsmooth stochastic approximation can be removed when the constraint set is a hyperrectangle.","The equicontinuity result supplies the missing step in the standard proof of convergence for projected stochastic approximation, so the classical ODE analysis is now complete for hyperrectangular constraints."],"supporting_citations":[{"why":"The classical convergence theorem for projected stochastic approximation whose proof is missing the equicontinuity step that this paper supplies.","marker":"[18]"},{"why":"Supplies the Arzelà–Ascoli type compactness theorem (Corollary IV.8) used to extract convergent subsequences of the interpolated functions.","marker":"[13]"},{"why":"Provides the differential-inclusion framework and the stochastic proximal gradient convergence theorems that are combined with the new equicontinuity result in Theorems 4.1 and 4.2.","marker":"[22]"},{"why":"Gives the upper semicontinuity properties of the normal cone used in Proposition 3.2 to pass to the limit in the projection term.","marker":"[26]"},{"why":"Defines the Clarke gradient used to state the composite stationary condition in Theorem 4.2.","marker":"[10]"}],"fun_headline_variants":["Projected Robbins-Monro: convergence proven on hyperrectangles","Hyperrectangle projections: stochastic approximation converges","ODE method completes the convergence proof for projected Robbins-Monro","Convergence proof for projected stochastic approximation on hyperrectangles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the constraint set being a hyperrectangle, because the proof decomposes projections coordinate by coordinate and uses the fact that two nearby nontrivial projections in one coordinate land on the same boundary point; this fails for more general convex sets, and the paper does not claim the result there.","fun_headline_variants_meta":{"raw":{"variants":["Projected Robbins-Monro: convergence proven on hyperrectangles","Hyperrectangle projections: stochastic approximation converges","ODE method completes the convergence proof for projected Robbins-Monro","Convergence proof for projected stochastic approximation on hyperrectangles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00143,"raw_usage":{"total_tokens":5680,"prompt_tokens":770,"completion_tokens":4910,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":386,"completion_tokens_details":{"reasoning_tokens":4843}},"tokens_in":386,"tokens_out":4910,"duration_ms":35874,"temperature":1.0,"reasoning_tokens":4843,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:30:32.428434+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To falsify the central claim, one would need to exhibit a hyperrectangle $K$, a bounded $h$, and step sizes and noise satisfying $(Con-\\gamma)$ and $(Con-e-r)$ for which the interpolated sequences are not equicontinuous; the paper's proof shows this cannot happen, so finding such an example would settle the question.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The classical convergence theorem for projected stochastic approximation whose proof is missing the equicontinuity step that this paper supplies."},{"cited_title":"Dunford and J","cited_arxiv_id":null,"evidence_quote":"Supplies the Arzelà–Ascoli type compactness theorem (Corollary IV.8) used to extract convergent subsequences of the interpolated functions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the upper semicontinuity properties of the normal cone used in Proposition 3.2 to pass to the limit in the projection term."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Clarke gradient used to state the composite stationary condition in Theorem 4.2."}],"review_version":1}