Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence

• URL: http://arxiv.org/abs/2509.11039v1
• Date: Sun, 14 Sep 2025 02:06:15 GMT
• Title: Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence
• Abstract summary: We show that the Lyapunov function exhibits convergence rates in both cases.<n>If the state noise parameters fully approach their limiting value, the Lyapunov function achieves an exponential convergence rate.
• Score: 6.160559095588513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The nonlinear two-time-scale stochastic approximation is widely studied under conditions of bounded variances in noise. Motivated by recent advances that allow for variability linked to the current state or time, we consider state- and time-dependent noises. We show that the Lyapunov function exhibits polynomial convergence rates in both cases, with the rate of polynomial delay depending on the parameters of state- or time-dependent noises. Notably, if the state noise parameters fully approach their limiting value, the Lyapunov function achieves an exponential convergence rate. We provide two numerical examples to illustrate our theoretical findings in the context of stochastic gradient descent with Polyak-Ruppert averaging and stochastic bilevel optimization.

Related papers

• Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation [9.227034835080307]
  We study the finite-time convergence of projected linear two-time-scale approximation with constant step sizes and Polyak-Ruppert averaging.<n>We establish an explicit mean-square error bound, decomposing it into two interpretable components, an approximation error determined by the constrained subspace and a statistical error decaying at a sublinear rate.
  arXiv  Detail & Related papers  (2026-03-31T19:30:36Z)
• Upper Approximation Bounds for Neural Oscillators [8.075776288865907]
  Theory of quantifying the capacities of neural network architectures remains a significant challenge.<n>This study considers the neural oscillator consisting of a second-order ODE followed by a multilayer perceptron.<n>Results provide a robust theoretical foundation for the effective application of the neural oscillator in science and engineering.
  arXiv  Detail & Related papers  (2025-11-30T18:20:40Z)
• Gaussian Approximation for Two-Timescale Linear Stochastic Approximation [4.4491311274892436]
  We establish algorithms driven by martingale difference or Markov noise.<n>We derive bounds for normal approximation in terms of the convex distance between probability.<n>We also provide the high-order moment bounds for the error of linear TTSA algorithm.
  arXiv  Detail & Related papers  (2025-08-11T12:41:14Z)
• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation [12.69327994479157]
  We consider linear two-time-scale approximation algorithms driven by martingale noise.<n>We derive the first non-asymptotic central limit theorem with respect to the Wasserstein-1 distance for two-time-scale approximation with PolyakRuppert averaging.
  arXiv  Detail & Related papers  (2025-02-14T03:20:30Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  We investigate the statistical properties of Temporal Difference learning with Polyak-Ruppert averaging.<n>We make three theoretical contributions that improve upon the current state-of-the-art results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Real-time dynamics of false vacuum decay [49.1574468325115]
  We investigate false vacuum decay of a relativistic scalar field in the metastable minimum of an asymmetric double-well potential. We employ the non-perturbative framework of the two-particle irreducible (2PI) quantum effective action at next-to-leading order in a large-N expansion.
  arXiv  Detail & Related papers  (2023-10-06T12:44:48Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms [8.669461942767098]
  We study momentum-based first-order optimization algorithms in which the iterations are subject to an additive white noise. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification. We introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time.
  arXiv  Detail & Related papers  (2022-09-24T04:26:30Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance [1.52292571922932]
  We study the convergence and finite-time analysis of the nonlinear two-time-scale approximation. In particular, we show that the method achieves a convergence in expectation at a rate $mathcalO (1/k2/3)$, where $k$ is the number of iterations.
  arXiv  Detail & Related papers  (2020-11-03T17:43:39Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  We present for the first time an convergence analysis of two time-scale approximation driven by "controlled" Markov noise. We analyze the behavior of our framework by relating it to limiting differential inclusions in both time scales. We obtain the first informative error bounds on function approximation for the policy evaluation algorithm.
  arXiv  Detail & Related papers  (2020-04-08T03:59:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  We address the problem of policy evaluation in discounted decision processes, and provide Markov-dependent guarantees on the $ell_infty$error under a generative model. We establish both and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms.
  arXiv  Detail & Related papers  (2020-03-16T17:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.