Pith. sign in

REVIEW 1 major objections 4 minor 37 references

This paper proves that the classical one-quarter residual exponent in non-expansive two-time-scale stochastic approximation is a sharp balance of a fixed-schedule KM lower bound and first-order fast-manifold leakage, and that a residual-pre

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

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)} (single-loop).

T0 review reviewed 2026-08-02 challenge →

load-bearing objection Genuinely explains the 1/4 barrier and shows how modified oracles can beat it; the faster rates are conditional on strong structured-oracle access, but the paper is honest about that and the lower bound is clean. the 1 major comments →

arxiv 2607.13414 v1 pith:HHZA2GZA submitted 2026-07-15 stat.ML cs.LG

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

Dhruv Sarkar , Vaneet Aggarwal This is my paper
classification stat.ML cs.LG MSC 62L2047H0965K10
keywords two-time-scale stochastic approximationnon-expansive mappingsKrasnoselskii-Mann iterationfixed-point residualTikhonov regularizationbias correctionpreconditioninglower bound
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 tries to establish that the observed k^{-1/4} last-iterate residual rate in non-expansive two-time-scale stochastic approximation is not an information-theoretic floor but the balance of two sharp effects: the classical Krasnoselskii-Mann residual scale for a fixed slow stepsize schedule, and the first-order leakage of fast tracking error into the slow oracle. It proves a finite-horizon lower bound showing the KM scale is worst-case sharp for any prescribed schedule. It then introduces a residual-preconditioned slow oracle that cancels the first-order fast error, making the slow bias quadratic. Counting every inner-loop sample, this lifts the nested total-sample rate from T^{-1/4+o(1)} to T^{-1/3+o(1)}; and, in a smoother derivative-oracle model, online tracking of both the fast equilibrium and the preconditioner removes the repeated inner-loop cost and yields T^{-1/2+o(1)} with O(1) primitive samples per iteration. A sympathetic reader would care because the conclusion is that the bottleneck is algorithmic structure, not an unchangeable limit, and sensitivity information is what buys the improvement.

Core claim

The load-bearing claim is Theorem 4.1: for any fixed slow stepsize schedule (beta_k), there is a deterministic two-time-scale instance (a planar rotation) whose exact Krasnoselskii-Mann residual satisfies ||h(Y_N)-Y_N||^2 >= 1/(4B_N), with B_N = sum_{i<N} beta_i(1-beta_i); hence the classical residual scale is finite-horizon sharp for the same unregularized update and schedule. Corollary 4.1 gives N^{-(1-b)} for beta_k ~ k^{-b}. The second main claim is Proposition 5.1: with A(y)=I-nabla_x f(x*(y),y), C(y)=nabla_x g(x*(y),y), and P*(y)=C(y)A(y)^{-1}, the corrected oracle H_corr(x,y)=g(x,y)+P*(y)(f(x,y)-x) has bias O(||x-x*(y)||^2), whereas the raw oracle has bias O(||x-x*(y)||). Instantiatin

What carries the argument

The central object is the residual-preconditioned slow oracle H_corr(x,y)=g(x,y)+P*(y)(f(x,y)-x), where P*(y)=nabla_x g(x*(y),y)(I-nabla_x f(x*(y),y))^{-1} is the implicit sensitivity of the fast equilibrium to slow perturbations. This is the mechanism that cancels first-order fast-manifold leakage and turns the slow bias from O(||e||) into O(||e||^2). The supporting machinery is the Krasnoselskii-Mann residual scale B_N^{-1} established by the fixed-schedule sharpness theorem, a Tikhonov-regularized outer recursion that adds a controllable contraction gap lambda, and, for the single-loop theorem, online stochastic-approximation trackers for both x*(Y_k) and P*(Y_k).

Load-bearing premise

The whole acceleration rests on availability of P*(y)=nabla_x g(x*(y),y)(I-nabla_x f(x*(y),y))^{-1} — exactly or through an estimator whose error is product-accurate with the fast residual and fast noise; without that, the first-order term does not cancel and the 1/3 and 1/2 rates fall back to the raw 1/4.

What would settle it

On the planar rotation instance from Theorem 4.1, with beta_k ~ (k+1)^{-b}, compute the exact KM residual: if any b in (0,1) yields ||h(Y_N)-Y_N||^2 below 1/(4B_N) up to constants, the sharpness claim fails. Separately, run the nested corrected algorithm on a problem with known P*(y) and count all primitive samples: if the slope of log E||h(Y_N)-Y_N||^2 versus log T is not better than -1/4 for epsilon-close parameter choices, the claimed T^{-1/3+o(1)} improvement fails. The simplest check is to verify the deterministic identity H_corr(x,y)-h(y)=O(||x-x*(y)||^2) at a point where the Taylor rema

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For any fixed slow schedule, the unregularized KM residual cannot be guaranteed below 1/(4B_N) in mean square; improving the raw TTSA exponent requires changing the schedule regime, adding anchoring or regularization, or enriching the oracle — sharper KM analysis alone cannot help.
  • Tikhonov anchoring alone does not remove the one-quarter total-sample rate: the uncorrected nested oracle still gives T^{-1/4+o(1)} after all inner-loop samples are counted.
  • With exact or product-accurate sensitivity access to P*(y), the corrected nested oracle changes the slow bias to second order and certifies a total primitive-sample rate of T^{-1/3+o(1)}.
  • In the derivative-oracle model, tracking both x*(Y_k) and P*(Y_k) online removes repeated inner solves and yields T^{-1/2+o(1)} with O(1) primitive samples per iteration.
  • The standard separation condition beta_k^2/alpha_k^3 <= constant is not a fundamental restriction: violating it merely shifts the bottleneck to first-order moving-target lag, which yields the same one-quarter exponent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The fixed-schedule lower bound applies only to unregularized KM with a prescribed schedule; the paper's own comparisons with anchored and Halpern-type methods suggest that alternative schedule families could beat 1/4 without sensitivity oracles — a direction the paper names but does not develop.
  • The correction is structurally an implicit-differentiation step used for bias rather than for gradients; the same P*(y) idea could reduce fast-manifold bias in stochastic bilevel and minimax algorithms that currently pay first-order inner-error penalties.
  • A testable prediction of the mechanism: in a linear-quadratic instance with known P*, the measured slow-oracle bias should scale as ||e||^2 for the corrected oracle versus ||e|| for the raw one, with the total-sample exponent shifting from 1/4 to 1/3 as the inner-loop length grows.
  • If the product-accuracy condition in Assumption 3.7 fails but only E||P_hat-P*||^2 is controlled, the paper's own analysis predicts the 1/3 gain disappears — so practical preconditioner estimators must be validated on the fast-residual product, not on the matrix distance alone.
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 / 4 minor

Summary. The paper analyzes two-time-scale stochastic approximation (TTSA) in the non-expansive regime: the fast map is contractive, the reduced slow map is only non-expansive, and the performance metric is the fixed-point residual. It makes three main contributions. First, Theorem 4.1 proves a finite-horizon lower bound showing that, for any fixed slow stepsize schedule, the classical KM residual scale (sum β_i(1−β_i))^{-1} is worst-case sharp for the unregularized exact KM recursion; combined with a scaling analysis of raw fast-tracking leakage, this is used to explain the previously observed k^{-1/4+o(1)} residual exponent. Second, a residual-preconditioned slow oracle is introduced and analyzed in a nested Tikhonov-KM scheme: the uncorrected nested method has total-sample rate T^{-1/4+o(1)}, while the corrected method achieves T^{-1/3+o(1)}. Third, in a smooth derivative-oracle model, a single-loop algorithm that tracks the fast equilibrium and the leakage preconditioner online achieves T^{-1/2+o(1)} with O(1) primitive samples per iteration. The asymptotic-rate claims are stated in the T^{-c+o(1)} sense. The paper is explicit that the improved rates are structured-oracle results, relying on Assumptions 3.7–3.9.

Significance. If correct, the paper gives a clean diagnostic separation between the intrinsic KM residual scale and the first-order fast-manifold leakage in non-expansive TTSA, and it demonstrates constructively that changing the oracle structure—rather than merely tuning stepsizes—can break the one-quarter exponent. The strengths of the paper are substantial: the finite-horizon rotation lower bound in Theorem 4.1 is explicit and self-contained; the sample accounting in Theorems 7.2 and 7.3 counts all inner-loop and outer-loop primitive calls, making the T^{-1/4} vs T^{-1/3} comparison a genuine total-oracle comparison; the stochastic Tikhonov outer analysis in Theorem 7.1 is clean; and the single-loop learned-preconditioner proof in Appendix H is coherent. The paper also deserves credit for being transparent about the strength of its oracle assumptions: Remark 3.1 and Theorem 7.3 state plainly that the nested T^{-1/3} certificate requires exact access to P^*(y) (or a product-accurate estimator), with the cost of that structured oracle excluded from the primitive count. This caveat is real but not hidden. The main limitation is that the 'one-quarter barrier' for the raw TTSA recursion itself is

major comments (1)
  1. [§4.2, Proposition 4.2 and Appendix B] Proposition 4.2 is stated as a formal proposition, but its proof in Appendix B explicitly calls the argument a 'scale diagnostic' and uses deterministic inexact-KM residual algebra without treating the stochastic noise, the projection, or the dependence between the fast tracking error and the slow oracle noise. As written, the proposition is therefore not a theorem derived from Assumptions 3.1–3.5; it is a heuristic exponent calculation. This matters because the paper's explanatory claim that the raw obstruction to beating 1/4 is 'first-order fast-manifold leakage' rests on this calculation. I recommend either (i) relabeling Proposition 4.2 as a scaling analysis, or (ii) giving a rigorous derivation, or (iii) explicitly moving it to a remark with the heuristic status stated. This does not affect the correctness of Theorem 4.1, Theorem 7.1, Theorem 7.2, Theorem 7.3, or Theorem 8.1, whose
minor comments (4)
  1. [Abstract and Theorem 4.1] The abstract says 'for any prescribed slow stepsize schedule' without noting the N-dependence of the lower-bound instance and the condition B_N ≥ 1/8 in Theorem 4.1. The theorem is perfectly precise, but a phrase such as 'for each sufficiently large horizon' in the abstract would avoid overstating the scope.
  2. [Remark 3.1 and Assumption 3.7] The paper is admirably transparent about the fact that Assumption 3.7 is a structured-oracle assumption and that an estimator with only a bound on E||P̂−P^*||² is insufficient. I would suggest strengthening this point in the main text by adding a sentence in Section 7.2 noting that the T^{-1/3+o(1)} exponent is therefore not a primitive-to-primitive comparison without the exact P^* oracle cost. This is already implicit in Theorem 7.3, but a one-sentence reminder at the point where the theorem is invoked would help readers.
  3. [Appendix H, Lemma H.1] In the post-burn-in bounds, the paper writes N^{-12} terms that come from an arbitrary choice of Cburn. This is fine, but a short note that the exponent 12 is arbitrary and could be replaced by any fixed negative polynomial would improve readability and avoid the appearance of a mysterious constant.
  4. [General notation] The notation T^{-c+o(1)} is defined at the end of Section 1 and used consistently. However, in Theorem 8.1 the statement gives N^{-1/2+6ε} and then 'equivalently T^{-1/2+6ε}'. Since T≍N only up to constants, the phrase 'equivalently' is slightly too strong; it would be more precise to say 'after absorbing constants, this also gives T^{-1/2+6ε}'.

Circularity Check

0 steps flagged

No significant circularity: rates follow from explicit lower-bound constructions and Taylor identities; oracle assumptions are transparent caveats, not fitted predictions.

full rationale

The derivation chain is self-contained against external benchmarks. Theorem 4.1's lower bound is an explicit rotation construction: with f=0 and h=R_θ, the exact KM residual is δ∏(1−δβ_k(1−β_k)), and choosing δ=1/(2B_N) gives ∥h(Y_N)−Y_N∥^2 ≥ 1/(4B_N). This is an independent worst-case instance, not an assumption. The 1/4 exponent calculation in Proposition 4.2 is arithmetic balancing of two independently derived scales, α_k + (β_k/α_k)^2 and the KM-weighted perturbation scale; it does not re-import the target rate. The bias correction is a Taylor identity (Proposition 5.1): H_corr − h = R_g + P*R_f with P*=C A^{−1}, so the first-order term vanishes algebraically; this is a cancellation, not a fitted quantity renamed as a prediction. The nested and single-loop rates follow from the generic Tikhonov bound (Theorem 7.1) with ϵ_H^2=O(n^{−1}) for the uncorrected oracle and O(n^{−2}) for the corrected oracle; the parameters are chosen by standard complexity balancing. Assumption 3.7's exact P* access is explicitly flagged in Remark 3.1 as a structured oracle whose cost is excluded; this caveat reduces the scope of the result but does not make the derivation circular. The online single-loop theorem learns P* from derivative observations instead of assuming it, and its proof (Lemmas H.1–H.3) is a self-contained tracking argument. Self-citations (e.g., [18]–[20], [36]) appear only in related-work positioning and are not used in any proof step; no load-bearing citation chain exists. The paper's own limitations, including the strength of Assumption 3.7, are stated transparently rather than hidden.

Axiom & Free-Parameter Ledger

0 free parameters · 10 axioms · 0 invented entities

All three headline rates rest on a structured-oracle model: differentiability in the fast variable (Assumption 3.6), exact or product-accurate preconditioner access (Assumption 3.7), and for the single-loop result, stochastic derivative observations plus pathwise boundedness (Assumptions 3.8-3.9). The KM lower bound (Theorem 4.1) is independent of these and uses only contractive fast map, non-expansive reduced slow map, and compact stabilization. No free parameters are fitted to data; step-size exponents are horizon-tuning choices over which the bounds are uniform.

axioms (10)
  • domain assumption x ↦ f(x,y) is a μ-contraction for each y (Assumption 3.1)
    Used everywhere to ensure a unique fast fixed point x*(y) and uniform contraction; standard in TTSA.
  • domain assumption Reduced slow map h(y)=g(x*(y),y) is non-expansive with nonempty Fix(h) (Assumption 3.2)
    Defines the non-expansive regime and the fixed-point residual as the metric; the paper's rates are for this regime.
  • domain assumption Compact stabilization sets X,Y with projections (Assumption 3.3)
    Provides uniform constants and permits projection; standard but required for every finite-time bound.
  • domain assumption Primitive oracles are conditionally unbiased with bounded 2nd/4th moments (Assumption 3.4)
    Needed for martingale noise control in inner-loop, outer Tikhonov, and single-loop tracking lemmas.
  • domain assumption g is Lipschitz in the fast coordinate (Assumption 3.5)
    Converts inner fast error into first-order slow bias for the uncorrected oracle (Prop 5.1, Thm 7.2).
  • domain assumption f,g twice differentiable in x with Lipschitz Jacobians; I−∇_x f uniformly invertible (Assumption 3.6)
    Needed for the Taylor cancellation in Prop 5.1 and the Newton-point lemma 5.1; defines the structured-oracle setting.
  • ad hoc to paper Exact access to P*(y)=∇_x g(x*(y),y)(I−∇_x f(x*(y),y))^{-1}, or a product-accurate estimator (Assumption 3.7)
    The bias-corrected nested theorem (Thm 7.3) requires exact or product-conditioned preconditioner access; its cost is not counted in the primitive sample budget. This is the enabling assumption behind the T^{-1/3} improvement.
  • domain assumption Stochastic derivative oracle for ∇_x f and ∇_x g with bounded moments; P* Lipschitz in y (Assumption 3.8)
    Required for the single-loop learned-preconditioner algorithm (Thm 8.1) to track P* online.
  • domain assumption x* is Lipschitz in y and the single-loop updates are pathwise bounded (Assumption 3.9)
    Controls moving-target lag in Lemma H.1 and makes the online tracking analysis tractable; can be relaxed to moment conditions per Remark.
  • standard math Baillon–Bruck and Cominetti–Soto–Vaisman asymptotic-regularity estimates for KM (cited [13])
    Used as the classical upper-bound counterpart to the new finite-horizon lower bound; the paper proves the matching lower bound.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration." pith.science (2026). https://pith.science/paper/HHZA2GZA

@misc{pith2026260713414,
  author       = {Pith},
  title        = {Pith review of: Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HHZA2GZA}},
  note         = {Machine review of arXiv:2607.13414}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium. We study this regime under a contractive fast map and a non-expansive reduced slow map. We first prove a finite-horizon lower bound showing that, for any prescribed slow stepsize schedule $(\beta_k)$, the classical KM residual scale $(\sum_{i<N}\beta_i(1-\beta_i))^{-1}$ is worst-case sharp for the corresponding unregularized KM update. Combined with the raw fast-tracking leakage scale, this explains the previously observed $k^{-1/4+o(1)}$ last-iterate mean-square residual exponent. We then introduce a residual-preconditioned slow oracle that cancels the first-order dependence on the fast tracking error. In a nested Tikhonov-KM algorithm, the uncorrected oracle yields total-sample rate $T^{-1/4+o(1)}$, while the corrected oracle yields $T^{-1/3+o(1)}$. This improvement comes from changing the slow-oracle bias from first order to second order in the fast error after all inner-loop samples are counted. Finally, we show that the repeated inner-loop cost of the nested method can be avoided in a smooth derivative-oracle model. A single-loop algorithm that tracks both the fast equilibrium and the leakage preconditioner online achieves $T^{-1/2+o(1)}$ with $O(1)$ primitive samples per iteration.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 2 linked inside Pith

  1. [1]

    Amortized implicit differentiation for stochastic bilevel optimization

    Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In International Conference on Learning Representations, 2022

    2022

  2. [2]

    Jean-Bernard Baillon and Ronald E. Bruck. The rate of asymptotic regularity is o(1/√n). In Athanass G. Kartsatos, editor,Theory and Applications of Nonlinear Operators of Accretive and Monotone Type, volume 178 ofLecture Notes in Pure and Applied Mathematics, pages 51–81. Marcel Dekker, New York, 1996

    1996

  3. [3]

    Bauschke and Patrick L

    Heinz H. Bauschke and Patrick L. Combettes.Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Cham, 2 edition, 2017

    2017

  4. [4]

    Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind

    Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: A survey.Journal of Machine Learning Research, 18(153):1–43, 2018

    2018

  5. [5]

    Springer, Berlin, 1990

    Albert Benveniste, Michel Métivier, and Pierre Priouret.Adaptive Algorithms and Stochastic Approximations. Springer, Berlin, 1990

    1990

  6. [6]

    Vivek S. Borkar. Stochastic approximation with two time scales.Systems & Control Letters, 29(5):291–294, 1997

    1997

  7. [7]

    Borkar.Stochastic Approximation: A Dynamical Systems Viewpoint

    Vivek S. Borkar.Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge, 2008

    2008

  8. [8]

    Stochastic approximation with two time scales: The general case.Stochastic Processes and their Applications, page 104759, 2025

    Vivek S Borkar. Stochastic approximation with two time scales: The general case.Stochastic Processes and their Applications, page 104759, 2025

    2025

  9. [9]

    Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds.SIAM Journal on Control and Optimization, 62(1):191–219, 2024

    Mario Bravo and Roberto Cominetti. Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds.SIAM Journal on Control and Optimization, 62(1):191–219, 2024

    2024

  10. [10]

    Stochastic halpern iteration in normed spaces and applications to reinforcement learning.Mathematical Programming, 2026

    Mario Bravo and Juan Pablo Contreras. Stochastic halpern iteration in normed spaces and applications to reinforcement learning.Mathematical Programming, 2026

    2026

  11. [11]

    Felix E. Browder. Convergence of approximants to fixed points of nonexpansive nonlinear mappings in banach spaces.Archive for Rational Mechanics and Analysis, 24:82–90, 1967

    1967

  12. [12]

    Non-expansive mappings in two-time-scale stochastic approximation: Finite-time analysis

    Siddharth Chandak. Non-expansive mappings in two-time-scale stochastic approximation: Finite-time analysis. SIAM Journal on Control and Optimization, 2026. To appear, available at arXiv:2501.10806

    Pith/arXiv arXiv 2026

  13. [13]

    Soto, and José Vaisman

    Roberto Cominetti, José A. Soto, and José Vaisman. On the rate of convergence of krasnosel’skii–mann iterations and their connection with sums of bernoullis.Israel Journal of Mathematics, 199(2):757–772, 2014

    2014

  14. [14]

    Stochastic krasnoselskii-mann iterations: Convergence without uniformly bounded variance.arXiv preprint arXiv:2604.22581, 2026

    Daniel Cortild and Coralia Cartis. Stochastic krasnoselskii-mann iterations: Convergence without uniformly bounded variance.arXiv preprint arXiv:2604.22581, 2026

    Pith/arXiv arXiv 2026

  15. [15]

    Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning

    Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. InProceedings of the 31st Conference on Learning Theory, volume 75 ofProceedings of Machine Learning Research, pages 1199–1233. PMLR, 2018. 16 APREPRINT- JULY16, 2026

    2018

  16. [16]

    Thinh T. Doan. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. InProceedings of the 3rd Conference on Learning for Dynamics and Control, volume 144 ofProceedings of Machine Learning Research, pages 47–47. PMLR, 2021

    2021

  17. [17]

    Springer, New York, 2003

    Francisco Facchinei and Jong-Shi Pang.Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York, 2003

    2003

  18. [18]

    Order-optimal global convergence for actor-critic with general policy and neural critic parametrization

    Swetha Ganesh, Jiayu Chen, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. InThe 41st Conference on Uncertainty in Artificial Intelligence, 2025

    2025

  19. [19]

    A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach

    Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach. InInternational Conference on Machine Learning, 2025

    2025

  20. [20]

    On the sample complexity bounds of bilevel reinforcement learning.Advances in Neural Information Processing Systems, 38:67538–67570, 2025

    Mudit Gaur, Utsav Singh, Amrit Singh Bedi, Raghu Pasupathy, and Vaneet Aggarwal. On the sample complexity bounds of bilevel reinforcement learning.Advances in Neural Information Processing Systems, 38:67538–67570, 2025

    2025

  21. [21]

    Fixed points of nonexpanding maps.Bulletin of the American Mathematical Society, 73(6):957–961, 1967

    Benjamin Halpern. Fixed points of nonexpanding maps.Bulletin of the American Mathematical Society, 73(6):957–961, 1967

    1967

  22. [22]

    A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.SIAM Journal on Optimization, 33(1):147–180, 2023

    Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.SIAM Journal on Optimization, 33(1):147–180, 2023

    2023

  23. [23]

    Bilevel optimization: Convergence analysis and enhanced design

    Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 4882–4892. PMLR, 2021

    2021

  24. [24]

    Finite time analysis of linear two-timescale stochastic approximation with markovian noise

    Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. InProceedings of the Thirty Third Conference on Learning Theory, volume 125 ofProceedings of Machine Learning Research, pages 2144–2203. PMLR, 2020

    2020

  25. [25]

    Kingma and Max Welling

    Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. InInternational Conference on Learning Representations, 2014

    2014

  26. [26]

    Konda and John N

    Vijay R. Konda and John N. Tsitsiklis. On actor-critic algorithms.SIAM Journal on Control and Optimization, 42(4):1143–1166, 2004

    2004

  27. [27]

    G. M. Korpelevich. The extragradient method for finding saddle points and other problems.Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976

    1976

  28. [28]

    M. A. Krasnoselskii. Two remarks on the method of successive approximations.Uspekhi Matematicheskikh Nauk, 10(1(63)):123–127, 1955. In Russian

    1955

  29. [29]

    Kushner and G

    Harold J. Kushner and G. George Yin.Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York, 2 edition, 2003

    2003

  30. [30]

    A fully first-order method for stochastic bilevel optimization

    Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. InInternational Conference on Machine Learning, 2023

    2023

  31. [31]

    A unified view of the IPA, SF, and LR gradient estimation techniques.Management Science, 36(11):1364–1383, 1990

    Pierre L’Ecuyer. A unified view of the IPA, SF, and LR gradient estimation techniques.Management Science, 36(11):1364–1383, 1990

    1990

  32. [32]

    Robert Mann

    W. Robert Mann. Mean value methods in iteration.Proceedings of the American Mathematical Society, 4(3):506– 510, 1953

    1953

  33. [33]

    Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems.SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  34. [34]

    A stochastic approximation method.The Annals of Mathematical Statistics, 22(3):400–407, 1951

    Herbert Robbins and Sutton Monro. A stochastic approximation method.The Annals of Mathematical Statistics, 22(3):400–407, 1951

    1951

  35. [35]

    Approximation of fixed points of nonexpansive mappings.Archiv der Mathematik, 58:486–491, 1992

    Rainer Wittmann. Approximation of fixed points of nonexpansive mappings.Archiv der Mathematik, 58:486–491, 1992

    1992

  36. [36]

    On the convergence of self-improving online llm alignment

    Xudong Wu, Pangpang Liu, Vaneet Aggarwal, and Jiayu Chen. On the convergence of self-improving online llm alignment. InProceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), 2026. 17 APREPRINT- JULY16, 2026 A Proofs of Theorem 4.1 and Corollary 4.1 This appendix contains the elementary rotation construction behind Theorem 4.1 ...

    2026

  37. [37]

    For the fourth moment, we use the following elementary perturbation estimate

    Increasing K to cover the finite initial value u0 closes the induction and yields E∥X t −x ∗(y)∥2 ≤ C t+t 0 . For the fourth moment, we use the following elementary perturbation estimate. If a is Ft-measurable, E[∆| Ft] = 0, andE[∥∆∥ 4 | Ft]<∞, then E[∥a+η∆∥ 4 | Ft]≤ ∥a∥4 +Cη 2 ∥a∥2 E[∥∆∥2 | Ft] +Cη 4E[∥∆∥4 | Ft].(32) To verify (32), write ∥a+η∆∥ 2 =∥a∥ 2...

    2026

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.