Convergence of projected stochastic approximation algorithm

B{\l}a\.zej Miasojedow; Micha{\l} Borowski

REVIEW 2 major objections 5 minor 29 references

Convergence of projected stochastic approximation algorithm

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that the projected Robbins-Monro algorithm converges on hyperrectangles, filling a missing step in the standard convergence proof.

desk verdict 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. read the letter →

arxiv 2501.08256 v1 pith:5GMP2QSG submitted 2025-01-14 math.OC

Micha{l} Borowski , B{l}ażej Miasojedow This is my paper · ORCID

classification math.OC MSC 62L2034D0546B50

keywords stochasticapproximationRobbins-MonroalgorithmODEmethodprojectionhyperrectangleequicontinuityproximalgradientconvergence

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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.

Credit 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.

Soft 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.

Proportion: 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[§3, proof of Theorem 3.1, Eqs. (3.7)–(3.9)] 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.
[§3, Lipschitz part of Theorem 3.1] 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.

minor comments (5)

[§3, Proposition 3.2, after Eq. (3.24)] Equation (3.25) states ˙x(t) = h(˙x(t)) - z(t); this should read ˙x(t) = h(X(t)) - z(t).
[§3, Proposition 3.2, Eq. (3.21)] 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.
[§3 and §4, theorem numbering] 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.
[§4, Theorem 4.1] 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.
[References] Reference [17] lacks a publication year and reference [26] lacks publisher information; please complete the bibliographic data.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the central equicontinuity theorem is proved from stated assumptions and standard analytic tools.

full rationale

The paper's central claim, Theorem 3.1, is not circular: it assumes (Con-γ), (Con-e-r), boundedness of h on the hyperrectangle K, and the recursion (SA), then proves equicontinuity of (X_n), (Z_n) and the Lipschitz property of limit points directly via Lemma 3.1 and estimates on sums of projections. None of these assumptions contains the conclusion, and no parameter is fitted to the target quantity. The proof's restriction to a hyperrectangle is explicitly stated as an assumption rather than smuggled in as a conclusion. The only self-citation appears in the applications section: Theorem 4.2 combines Theorem 3.1 with [22, Theorem 5.4], and Theorem 4.1's proof is said to follow the lines of [22, Theorem 3.5]; [22] has one overlapping author. This is a minor, non-load-bearing self-citation for the main equicontinuity result, and the application section is not used as independent confirmation of Theorem 3.1. Potential mathematical issues in the proof, such as the index-shift concern in the projection estimate, are correctness concerns rather than circularity; they do not constitute a definitional reduction of the theorem to its inputs. Therefore no circular step is identified, and the low score reflects only the minor self-citation in the applications portion.

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

No free parameters were fitted and no new entities were introduced. The contribution is a proof, not a model with tunable constants; the central claim rests entirely on standard SA assumptions, the hyperrectangle structure, and known functional-analytic tools.

assumptions (7)

domain assumption (Con-γ): ∑ γ_n = ∞, γ_n → 0.
Standard stochastic approximation step-size condition; used throughout the proof, for example in Lemma 3.1 and estimates (3.4)-(3.6).
domain assumption (Con-e-r): |r_n| → 0 almost surely and ∑ γ_n e_n converges almost surely.
Models vanishing residual noise and conditionally convergent weighted stochastic noise; invoked in (3.5), (3.15), and Proposition 3.2.
domain assumption h is bounded on K.
Used to bound ∑ γ_k h(x_k) by H ∑ γ_k, which is essential to (3.4), (3.10), and (3.14).
domain assumption K is a hyperrectangle ∏[a_i,b_i].
Coordinate-wise projection enables the key implication (3.8); the authors state this assumption cannot be easily skipped.
standard math Arzelà-Ascoli theorem in the extended sense (Theorem 2.1, Corollary IV.8 of Dunford-Schwartz).
Used to extract uniformly convergent subsequences of (X_n) and (Z_n) in the proof of Theorem 3.1 and Proposition 3.2.
standard math Upper semicontinuity of the normal cone, [26, Proposition 6.5].
Used in Proposition 3.2 to pass from convex hulls of normal cones to z(t) ∈ N_K(X(t)).
domain assumption Existence of a Lyapunov function V with S = {x : ⟨∇V(x), Π_{T_K}h(x)⟩ = 0} having empty interior.
Assumed in Theorem 4.1; needed to conclude dist(x_n,S) → 0 from ODE stability. The proof is delegated to [22, Theorem 3.5].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Convergence of projected stochastic approximation algorithm." pith.science (2026). https://pith.science/paper/5GMP2QSG

@misc{pith2026250108256,
  author       = {Pith},
  title        = {Pith review of: Convergence of projected stochastic approximation algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5GMP2QSG}},
  note         = {Machine review of arXiv:2501.08256}
}

read the original abstract

We study the Robbins-Monro stochastic approximation algorithm with projections on a hyperrectangle and prove its convergence. This work fills a gap in the convergence proof of the classic book by Kushner and Yin. Using the ODE method, we show that the algorithm converges to stationary points of a related projected ODE. Our results provide a better theoretical foundation for stochastic optimization techniques, including stochastic gradient descent and its proximal version. These results extend the algorithm's applicability and relax some assumptions of previous research.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 28 canonical work pages

[22]

Majewski, B

S. Majewski, B. Miasojedow, and E. Moulines. Analysis of nonsmo oth stochastic approximation: the diﬀerential inclusion approach, 2018. arXiv:1805.01916

arXiv 2018
[1]

Andrieu and E

C. Andrieu and E. Moulines. On the ergodicity properties of some a daptive mcmc algorithms. Annals of Applied Probability, 16:1462–1505, 2006

work page 2006
[2]

Beck and M

A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. , 31(3):167–175, May 2003

work page 2003
[3]

Bianchi and J

P. Bianchi and J. Jakubowicz. Convergence of a multi-agent pro jected stochastic gradient algorithm for non- convex optimization. IEEE Trans. Automat. Control , 58(2):391–405, 2013

work page 2013
[4]

Bolte, S

J. Bolte, S. Sabach, and M. Teboulle. Proximal alternating lineariz ed minimization for nonconvex and nonsmooth problems. Math. Program., 146(1):459–494, Aug. 2014

work page 2014
[5]

V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization , 38(2):447–469, 2000

work page 2000
[6]

V. S. Borkar. Stochastic approximation: a dynamical systems viewpoint . Cambridge University Press, Cambridge; Hindustan Book Agency, New Delhi, 2008, pages x+164

work page 2008
[7]

L. Bottou. Large-scale machine learning with stochastic gradien t descent. In Y. Lechevallier and G. Saporta, editors, Proceedings of COMPSTAT’2010, pages 177–186, Heidelberg. Physica-Verlag HD, 2010

work page 2010

Show all 29 references

[8]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods fo r large-scale machine learning. SIAM Review, 60(2):223–311, 2018

2018
[9]

Cao and Q

Y. Cao and Q. Gu. Generalization bounds of stochastic gradient d escent for wide and deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alch´ e-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 32. Curran Ass...

2019
[10]

F. H. Clarke. Optimization and nonsmooth analysis , volume 5 of Classics in Applied Mathematics . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, secon d edition, 1990, pages xii+308

1990
[11]

Delyon, M

B. Delyon, M. Lavielle, and E. Moulines. Convergence of a stocha stic approximation version of the em algorithm. Annals of statistics :94–128, 1999

1999
[12]

Duchi, S

J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Eﬃcie nt projections onto the l1-ball for learning in high dimensions. In ACM Other conferences , pages 272–279. Association for Computing Machinery, New York, NY, USA, July 2008

2008
[13]

Dunford and J

N. Dunford and J. T. Schwartz. Linear Operators I. General Theory , volume Vol. 7. Interscience Publishers, Inc., New York; Interscience Publishers Ltd. London, 1958, pages xiv+ 858. With the assistance of W. G. Bade and R. G. Bartle

1958
[14]

Fan and R

J. Fan and R. Li. Variable selection via nonconcave penalized likeliho od and its oracle properties. J. Amer. Statist. Assoc., 96(456):1348–1360, 2001

2001
[15]

G. Fort, E. Moulines, and P. Priouret. Convergence of adaptiv e and interacting markov chain monte carlo algo- rithms. Annals of Statistics , 39:3262–3289, 2011

2011
[16]

Gupta, K

H. Gupta, K. H. Jin, H. Q. Nguyen, M. T. McCann, and M. Unser. Cnn-based projected gradient descent for consistent ct image reconstruction. IEEE Transactions on Medical Imaging , 37(6):1440–1453, 2018

2018
[17]

H. J. Kushner and D. S. Clark. Stochastic Approximation Methods for Constrained and Unco nstrained Systems. Springer, New York, NY, USA
[18]

H. J. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and App lications. Springer, New York, NY, USA, 2003

2003
[19]

Larson, M

J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimiza tion methods. Acta Numer., 28:287–404, 2019

2019
[20]

S. E. Li. Deep Reinforcement Learning. In Reinforcement Learning for Sequential Decision and Optima l Control, pages 365–402. Springer, Singapore, Apr. 2023

2023
[21]

L. Ljung. Analysis of recursive stochastic algorithms. IEEE Transactions on Automatic Control , 22(4):551–575, 1977

1977
[23]

Miasojedow, E

B. Miasojedow, E. Moulines, and M. Vihola. An adaptive parallel te mpering algorithm. Journal of Computational and Graphical Statistics , 22(3):649–664, 2013

2013
[24]

Parikh and S

N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends ® in Optimization , 1(3):127–239, 2014. 13

2014
[25]

Pereyra, P

M. Pereyra, P. Schniter, ´E. Chouzenoux, J.-C. Pesquet, J.-Y. Tourneret, A. O. Hero, andS. McLaughlin. A survey of stochastic simulation and optimization methods in signal processing. IEEE Journal of Selected Topics in Signal Processing, 10(2):224–241, 2016

2016
[26]

R. T. Rockafellar and R. J. B. Wets. Variational Analysis. Springer, Berlin, Germany
[27]

Tibshirani

R. Tibshirani. Regression shrinkage and selection via the lasso: a retrospective. J. R. Stat. Soc. Ser. B Stat. Methodol., 73(3):273–282, 2011

2011
[28]

C.-H. Zhang. Nearly unbiased variable selection under minimax con cave penalty. Ann. Statist. , 38(2):894–942, 2010

2010
[29]

Zinkevich, M

M. Zinkevich, M. Weimer, L. Li, and A. Smola. Parallelized stochast ic gradient descent. In J. Laﬀerty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems , vol- ume 23. Curran Associates, Inc., 2010. 14

2010

Pith tools

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

[1] [22]

Majewski, B

S. Majewski, B. Miasojedow, and E. Moulines. Analysis of nonsmo oth stochastic approximation: the diﬀerential inclusion approach, 2018. arXiv:1805.01916

arXiv 2018

[2] [1]

Andrieu and E

C. Andrieu and E. Moulines. On the ergodicity properties of some a daptive mcmc algorithms. Annals of Applied Probability, 16:1462–1505, 2006

work page 2006

[3] [2]

Beck and M

A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. , 31(3):167–175, May 2003

work page 2003

[4] [3]

Bianchi and J

P. Bianchi and J. Jakubowicz. Convergence of a multi-agent pro jected stochastic gradient algorithm for non- convex optimization. IEEE Trans. Automat. Control , 58(2):391–405, 2013

work page 2013

[5] [4]

Bolte, S

J. Bolte, S. Sabach, and M. Teboulle. Proximal alternating lineariz ed minimization for nonconvex and nonsmooth problems. Math. Program., 146(1):459–494, Aug. 2014

work page 2014

[6] [5]

V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization , 38(2):447–469, 2000

work page 2000

[7] [6]

V. S. Borkar. Stochastic approximation: a dynamical systems viewpoint . Cambridge University Press, Cambridge; Hindustan Book Agency, New Delhi, 2008, pages x+164

work page 2008

[8] [7]

L. Bottou. Large-scale machine learning with stochastic gradien t descent. In Y. Lechevallier and G. Saporta, editors, Proceedings of COMPSTAT’2010, pages 177–186, Heidelberg. Physica-Verlag HD, 2010

work page 2010