Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

• URL: http://arxiv.org/abs/2508.07928v1
• Date: Mon, 11 Aug 2025 12:41:14 GMT
• Title: Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
• Authors: Bogdan Butyrin, Artemy Rubtsov, Alexey Naumov, Vladimir Ulyanov, Sergey Samsonov,
• Abstract summary: 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.
• Score: 4.4491311274892436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak-Ruppert averaging regimes, we derive bounds for normal approximation in terms of the convex distance between probability distributions. Our analysis reveals a non-trivial interaction between the fast and slow timescales: the normal approximation rate for the last iterate improves as the timescale separation increases, while it decreases in the Polyak-Ruppert averaged setting. We also provide the high-order moment bounds for the error of linear TTSA algorithm, which may be of independent interest.

Related papers

• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation [28.34847294888529]
  We consider the normal approximation by the Gaussian distribution with covariance matrix predicted by the Polyak-Juditsky central limit theorem.<n>We prove a non-asymptotic validity of the multiplier bootstrap procedure for approximating the distribution of the rescaled error of the averaged LSA estimator.
  arXiv  Detail & Related papers  (2025-10-14T10:50:10Z)
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning [55.197497603087065]
  We analyze the performance of the Temporal Difference (TD) learning algorithm with linear function approximations.<n>We establish novel and general high-dimensional concentration inequalities and Berry-Esseen bounds for vector-valued martingales induced by Markov chains.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• 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)
• Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning [15.041074872715752]
  We prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstraps.<n>We illustrate our findings in the setting of temporal difference learning with linear function approximation.
  arXiv  Detail & Related papers  (2024-05-26T17:43:30Z)
• Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization [6.012173616364571]
  We combine a variational approximation of the posterior with a similar and efficient SIC-restricted Kullback-Leibler-optimal approximation of the prior. For this setting, our variational approximation can be computed via gradient descent in polylogarithmic time per iteration. We provide numerical comparisons showing that the proposed double-Kullback-Leibler-optimal Gaussian-process approximation (DKLGP) can sometimes be vastly more accurate for stationary kernels than alternative approaches.
  arXiv  Detail & Related papers  (2023-01-30T21:50:08Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• 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)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.