Pith. sign in

REVIEW 1 major objections 2 minor 1 cited by

Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis

T0 review · 1 major / 2 minor · reviewed 2026-05-23 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read Two-time-scale stochastic approximation with non-expansive slower mappings has last-iterate mean square residual error decaying at O(1/k^{1/4-ε}).

desk verdict Extends finite-time SA analysis to non-expansive slow mappings via stochastic inexact KM iteration but the fast-scale error conditions needed for the O(1/k^{1/4-ε}) rate are the unverified link. read the letter →

arxiv 2501.10806 v4 submitted 2025-01-18 math.OC cs.LGcs.SYeess.SYstat.ML

Siddharth Chandak This is my paper
classification math.OCcs.LGcs.SYeess.SYstat.ML
keywords two-time-scalestochasticapproximationnon-expansivemappingsfinite-timeanalysisKrasnoselskii-Manniterationlast-iterateconvergencealmostsureminimaxoptimization
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

This paper broadens finite-time analysis of two-time-scale stochastic approximation algorithms beyond contractive mappings to include non-expansive ones on the slower time-scale. It shows that the last-iterate mean square residual error decays at a rate of O(1/k^{1/4-ε}) for any small positive ε, and that the iterates converge almost surely to the fixed point set. The slower iteration is analyzed by recasting it as a stochastic inexact Krasnoselskii-Mann process with appropriate error bounds from the faster scale. This extension covers variants with projection steps and applies directly to minimax optimization, linear stochastic approximation, and Lagrangian optimization.

What carries the argument

Stochastic inexact Krasnoselskii-Mann iteration, which incorporates the errors from the faster time-scale while allowing the slower mapping to be non-expansive.

What would settle it

A simulation or theoretical construction of a two-time-scale algorithm with non-expansive slower mapping where the mean square residual error does not decay at least as fast as 1/k to a power strictly less than 1/4 would falsify the rate claim.

Watch

Extended reading notes

Core claim

We show that the last-iterate mean square residual error for such algorithms decays at a rate O(1/k^{1/4-ε}), where ε>0 is arbitrarily small. We further establish almost sure convergence of iterates to the set of fixed points. The slower time-scale can be viewed as a stochastic inexact Krasnoselskii-Mann iteration, and the framework applies to minimax optimization, linear stochastic approximation, and Lagrangian optimization.

Load-bearing premise

The slower time-scale mapping is non-expansive and the overall process satisfies the technical conditions needed to apply the rate proof for the stochastic inexact Krasnoselskii-Mann iteration.

Editorial extensions

If this is right

  • The analysis provides finite-time guarantees without requiring contractivity on the slower time-scale.
  • Almost sure convergence to the fixed points holds under the given conditions.
  • The results apply to a variant with projection steps on the faster time-scale.
  • The framework directly yields bounds for minimax optimization and Lagrangian optimization problems.

Reading between the lines

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

  • If the non-expansive assumption holds in practice for a given application, the derived rate gives a concrete performance guarantee.
  • Similar recasting techniques might apply to other multi-time-scale algorithms with non-expansive components.
  • The almost sure convergence result complements the finite-time rate analysis.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 2 minor

Summary. The manuscript analyzes two-time-scale stochastic approximation where the slow-scale mapping is non-expansive (or rendered non-expansive via projection). It recasts the slow recursion as a stochastic inexact Krasnosel'skii-Mann iteration and proves that the last-iterate mean-square residual error decays as O(1/k^{1/4-ε}) for arbitrary ε>0, together with almost-sure convergence of the iterates to the fixed-point set. The framework is applied to minimax optimization, linear stochastic approximation, and Lagrangian optimization.

Significance. If the error-term conditions are verified, the result meaningfully extends finite-time analysis of two-time-scale SA beyond the contractive regime that has dominated prior work. The O(1/k^{1/4-ε}) rate, while slower than typical contractive bounds, remains sublinear and is accompanied by a.s. convergence; both are relevant for saddle-point and constrained problems where non-expansive operators arise naturally.

major comments (1)
  1. [Main finite-time result and its proof (likely §4–5)] The O(1/k^{1/4-ε}) rate is obtained by treating the slow-scale recursion as a stochastic inexact Krasnosel'skii-Mann iteration whose inexactness sequence {e_k} must obey precise moment and summability conditions. The manuscript must explicitly derive or verify that the fast-scale error process satisfies these conditions under the chosen step-size schedules; non-expansiveness alone does not guarantee the required decay of E[||e_k||^2] without further restrictions on the relative step-size ratio (see the modeling step that recasts the two-time-scale system and the subsequent rate theorem).
minor comments (2)
  1. [Abstract] The abstract states the rate but supplies no indication of the step-size conditions or the precise moment requirements on the inexactness sequence; adding one sentence would improve readability.
  2. [Notation and problem formulation] Notation for the residual error (mean-square distance to the fixed-point set versus distance to the solution set) should be introduced once and used consistently in the rate statements.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the single major comment below and agree that an explicit verification step will improve the manuscript.

read point-by-point responses

  1. Referee: [Main finite-time result and its proof (likely §4–5)] The O(1/k^{1/4-ε}) rate is obtained by treating the slow-scale recursion as a stochastic inexact Krasnosel'skii-Mann iteration whose inexactness sequence {e_k} must obey precise moment and summability conditions. The manuscript must explicitly derive or verify that the fast-scale error process satisfies these conditions under the chosen step-size schedules; non-expansiveness alone does not guarantee the required decay of E[||e_k||^2] without further restrictions on the relative step-size ratio (see the modeling step that recasts the two-time-scale system and the subsequent rate theorem).

    Authors: We agree that the verification of the moment and summability conditions on the fast-scale error {e_k} should be derived explicitly rather than left implicit after the modeling step. In the revised manuscript we will insert a dedicated lemma immediately after the recasting argument (new Lemma 4.2 in §4) that, under the paper’s step-size schedules (α_k ∼ k^{-a}, β_k ∼ k^{-b} with a < b and β_k/α_k → 0), establishes E[||e_k||²] = O(α_k) together with the required summability ∑ α_k E[||e_k||²] < ∞ and the higher-moment bounds needed by the stochastic inexact Krasnosel’skii-Mann theorem. The proof of the lemma uses only the Lipschitz continuity of the fast mapping, the boundedness of the iterates (already shown in §3), and standard martingale arguments; no additional restrictions beyond the existing step-size assumptions are introduced. This change makes the passage from the two-time-scale system to the rate theorem fully rigorous while leaving the O(1/k^{1/4-ε}) bound and almost-sure convergence statements unchanged. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity in finite-time rate derivation

full rationale

The paper recasts the slow time-scale recursion as a stochastic inexact Krasnoselskii-Mann iteration and derives the O(1/k^{1/4-ε}) last-iterate rate from standard properties of non-expansive mappings and summability conditions on the inexactness sequence. This is a direct mathematical analysis with no reduction of the claimed result to a fitted parameter, self-definition, or self-citation chain. The derivation is self-contained against external benchmarks for KM iterations and does not exhibit any of the enumerated circularity patterns.

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

The analysis rests on standard properties of non-expansive operators and typical stochastic approximation noise assumptions; no new free parameters or invented entities are introduced in the abstract.

assumptions (2)
  • standard math Non-expansive mappings satisfy ||Tx - Ty|| ≤ ||x - y|| in the underlying normed space
    Invoked to model the slow time-scale iteration.
  • domain assumption Stochastic approximation noise has bounded variance and appropriate step-size summability
    Standard background assumption for SA convergence proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis." pith.science (2026). https://pith.science/paper/2501.10806

@misc{pith2026250110806,
  author       = {Pith},
  title        = {Pith review of: Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2501.10806}},
  note         = {Machine review of arXiv:2501.10806}
}
abstract

Two-time-scale stochastic approximation algorithms are iterative methods used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of these algorithms has primarily focused on fixed point iterations where both time-scales have contractive mappings. In this work, we broaden the scope of such analyses by considering settings where the slower time-scale has a non-expansive mapping. For such algorithms, the slower time-scale can be viewed as a stochastic inexact Krasnoselskii-Mann iteration. We also study a variant where the faster time-scale has a projection step which leads to non-expansiveness in the slower time-scale. We show that the last-iterate mean square residual error for such algorithms decays at a rate $O(1/k^{1/4-\epsilon})$, where $\epsilon>0$ is arbitrarily small. We further establish almost sure convergence of iterates to the set of fixed points. We demonstrate the applicability of our framework by applying our results to minimax optimization, linear stochastic approximation, and Lagrangian optimization.

Figures

Figures reproduced from arXiv: 2501.10806 by the authors.

Figure 1
Figure 1. Linear Stochastic Approximation: effect of stepsize sequence on residual errors [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Minimax Optimization: residual errors for the two time-scales [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Constrained optimization: (a) effect of stepsize on residual error, and (b) [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

    stat.ML 2026-07 accept novelty 7.0 of 10

    A sharp lower bound for non-expansive KM residual, and a residual-preconditioned oracle that improves non-expansive two-time-scale stochastic approximation from T^{-1/4+o(1)} to T^{-1/3+o(1)} (nested) and T^{-1/2+o(1)...

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · cited by 1 Pith paper

  1. [1]

    H. H. Bauschke, P. L. Combettes, H. H. Bauschke, and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces , Springer, 2011

    work page 2011

  2. [2]

    Borkar , Stochastic Approximation: A Dynamical Systems Viewpoint: Second Edition , Texts and Readings in Mathematics, Hindustan Book Agency, 2022

    V. Borkar , Stochastic Approximation: A Dynamical Systems Viewpoint: Second Edition , Texts and Readings in Mathematics, Hindustan Book Agency, 2022

    work page 2022

  3. [3]

    Bravo and R

    M. Bravo and R. Cominetti , Stochastic fixed-point iterations for nonexpansive maps: Con- vergence and error bounds, SIAM Journal on Control and Optimization, 62 (2024), pp. 191– 219

    work page 2024

  4. [4]

    Bravo, R

    M. Bravo, R. Cominetti, and M. Pavez-Sign ´e, Rates of convergence for inexact krasnosel’skii–mann iterations in banach spaces, Mathematical Programming, 175 (2019), pp. 241–262

    work page 2019

  5. [5]

    Chandak, o(1/k) finite-time bound for non-linear two-time-scale stochastic approximation , 2025, https://arxiv.org/abs/2504.19375

    S. Chandak, o(1/k) finite-time bound for non-linear two-time-scale stochastic approximation , 2025, https://arxiv.org/abs/2504.19375

    work page arXiv 2025

  6. [6]

    Chandak, I

    S. Chandak, I. Bistritz, and N. Bambos , Learning to control unknown strongly monotone games, 2024, https://arxiv.org/abs/2407.00575

    work page arXiv 2024

  7. [7]

    Chandak, V

    S. Chandak, V. S. Borkar, and P. Dodhia , Concentration of contractive stochastic approx- imation and reinforcement learning, Stochastic Systems, 12 (2022), pp. 411–430

    work page 2022

  8. [8]

    Chandak, S

    S. Chandak, S. U. Haque, and N. Bambos , Finite-time bounds for two-time-scale stochastic approximation with arbitrary norm contractions and markovian noise, 2025, https://arxiv. org/abs/2503.18391

    work page arXiv 2025

Show all 30 references
  1. [9]

    Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam , Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes , Advances in Neural Information Processing Systems, 33 (2020), pp. 8223–8234

    2020

  2. [10]

    Z. Chen, S. T. Maguluri, and M. Zubeldia , Concentration of contractive stochastic approx- imation: Additive and multiplicative noise , 2024, https://arxiv.org/abs/2303.15740

    2024

  3. [11]

    Davis and W

    D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, Splitting methods in communication, imaging, science, and engineering, (2016), pp. 115–163

    2016

  4. [12]

    T. T. Doan, Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance, IEEE Transactions on Automatic Control, 68 (2023), pp. 4695–4705

    2023

  5. [13]

    Q.-L. Dong, Y. J. Cho, S. He, P. M. Pardalos, and T. M. Rassias, The Krasnoselskii-Mann Iterative Method: Recent Progress and Applications , Springer, 2022

    2022

  6. [14]

    Facchinei and C

    F. Facchinei and C. Kanzow , Generalized nash equilibrium problems , Annals of Operations Research, 175 (2010), pp. 177–211

    2010

  7. [15]

    Facchinei and J.-S

    F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems, Springer Science & Business Media, 2007

    2007

  8. [16]

    S. U. Haque, S. Khodadadian, and S. T. Maguluri , Tight finite time bounds of two-time- scale linear stochastic approximation with markovian noise , 2023, https://arxiv.org/abs/ 2401.00364

    2023

  9. [17]

    Kaledin, E

    M. Kaledin, E. Moulines, A. Naumov, V. Tadic, and H.-T. Wai , Finite time analysis of linear two-timescale stochastic approximation with markovian noise , in Proceedings of Thirty Third Conference on Learning Theory, J. Abernethy and S. Agarwal, eds., vol. 125 of Proceedings o...

    2020

  10. [18]

    V. R. Konda and J. N. Tsitsiklis , Convergence rate of linear two-time-scale stochastic ap- proximation, The Annals of Applied Probability, 14 (2004), pp. 796 – 819

    2004

  11. [19]

    Liang, J

    J. Liang, J. Fadili, and G. Peyr ´e, Convergence rates with inexact non-expansive operators , Mathematical Programming, 159 (2016), pp. 403–434

    2016

  12. [20]

    T. Lin, C. Jin, and M. I. Jordan , Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization , 2024, https://arxiv.org/abs/2408.11974

    2024

  13. [21]

    J. J. Maul ´en, I. Fierro, and J. Peypouquet , Inertial krasnoselskii-mann iterations , Set- Valued and Variational Analysis, 32 (2024), p. 10

    2024

  14. [22]

    Nagurney and D

    A. Nagurney and D. Zhang , Projected dynamical systems and variational inequalities with applications, vol. 2, Springer Science & Business Media, 2012. 30 S. CHANDAK

    2012

  15. [23]

    Nesterov et al., Lectures on convex optimization, vol

    Y. Nesterov et al., Lectures on convex optimization, vol. 137, Springer, 2018

    2018

  16. [24]

    Platt and A

    J. Platt and A. Barr, Constrained differential optimization, in Neural Information Processing Systems, 1987

    1987

  17. [25]

    Robbins and S

    H. Robbins and S. Monro, A Stochastic Approximation Method, The Annals of Mathematical Statistics, 22 (1951), pp. 400 – 407

    1951

  18. [26]

    Srikant and L

    R. Srikant and L. Ying , Finite-time error bounds for linear stochastic approximation andtd learning, in Proceedings of the Thirty-Second Conference on Learning Theory, vol. 99 of Proceedings of Machine Learning Research, PMLR, 25–28 Jun 2019, pp. 2803–2830

    2019

  19. [27]

    R. S. Sutton and A. G. Barto , Reinforcement learning: An introduction , The MIT Press, 2018

    2018

  20. [28]

    R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesv ´ari, and E. Wiewiora, Fast gradient-descent methods for temporal-difference learning with linear function approximation , in Proceedings of the 26th annual international conference on machine learning, 2...

    2009

  21. [29]

    Y. F. Wu, W. Zhang, P. Xu, and Q. Gu, A finite-time analysis of two time-scale actor-critic methods, Advances in Neural Information Processing Systems, 33 (2020), pp. 17617–17628

    2020

  22. [30]

    S. Zeng, T. T. Doan, and J. Romberg , A two-time-scale stochastic optimization framework with applications in control and reinforcement learning , SIAM Journal on Optimization, 34 (2024), pp. 946–976

    2024

Pith tools

Reviewed May 23, 2026 · model on record in the stance chip above.