{"ID":2883722,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.07928","arxiv_id":"2508.07928","title":"Gaussian Approximation for Two-Timescale Linear Stochastic Approximation","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.","short_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...","url_abs":"https://arxiv.org/abs/2508.07928","url_pdf":"https://arxiv.org/pdf/2508.07928v2","authors":"[\"Bogdan Butyrin\",\"Artemy Rubtsov\",\"Alexey Naumov\",\"Vladimir Ulyanov\",\"Sergey Samsonov\"]","published":"2025-08-11T12:41:14Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.OC\",\"math.PR\",\"math.ST\"]","methods":"[]","has_code":false}