Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

2026-03-31 · Yitao Bai, Thinh T. Doan, Justin Romberg arxiv

We study the finite-time convergence of projected linear two-time-scale stochastic approximation with constant step sizes and Polyak--Ruppert averaging. 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, with constants expressed through restricted stability margins and a coupling invertibility condition. These constants cleanly separate the effect of subspace choice (approximation errors) from the effect of the averaging horizon (statistical errors). We illustrate our theoretical results through a number of numerical experiments on both synthetic and reinforcement learning problems.

📄 PDF Abstract BibTeX arXiv:2604.00179

Code (0)

등록된 구현이 없습니다.

Tasks

Reinforcement Learning

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning

2017-03-15 · Gal Dalal, Balazs Szorenyi, Gugan Thoppe, Shie Mannor

Two-timescale Stochastic Approximation (SA) algorithms are widely used in Reinforcement Learning (RL). Their iterates have two parts that are updated using distinct stepsizes. In this work, we develop a novel recipe for …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Finite-Time Analysis of Projected Langevin Monte Carlo

2015-12-01 · NeurIPS 2015 12 · Sebastien Bubeck, Ronen Eldan, Joseph Lehec

We analyze the projected Langevin Monte Carlo (LMC) algorithm, a close cousin of projected Stochastic Gradient Descent (SGD). We show that LMC allows to sample in polynomial time from a posterior distribution restricted …

Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation

2022-10-12 · Gandharv Patil, Prashanth L. A., Dheeraj Nagaraj, Doina Precup

We study the finite-time behaviour of the popular temporal difference (TD) learning algorithm when combined with tail-averaging. We derive finite time bounds on the parameter error of the tail-averaged TD iterate under a…

Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems

2021-12-29 · Chris Junchi Li, Michael I. Jordan

Motivated by the problem of online canonical correlation analysis, we propose the \emph{Stochastic Scaled-Gradient Descent} (SSGD) algorithm for minimizing the expectation of a stochastic function over a generic Riemanni…

Finite-Time Analysis of Gradient Descent for Shallow Transformers

2026-01-23 · Enes Arda, Semih Cayci, Atilla Eryilmaz arxiv

Understanding why Transformers perform so well remains challenging due to their non-convex optimization landscape. In this work, we analyze a shallow Transformer with $m$ independent heads trained by projected gradient d…