2025/02/14 by Seo Taek Kong, Sihan Zeng, Kong, Seo Taek +5 · 2 citations
Economics, Econometrics and Finance · Mathematics · Computer Science · #Stochastic processes and financial applications #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2502.09884
We consider linear two-time-scale stochastic approximation algorithms driven by martingale noise. Recent applications in machine learning motivate the need to understand finite-time error rates, but conventional stochastic approximation analysis focus on either asymptotic convergence in distribution or finite-time bounds that are far from optimal. Prior work on asymptotic central limit theorems (CLTs) suggest that two-time-scale algorithms may be able to achieve 1/√(n) error in expectation, with a constant given by the expected norm of the limiting Gaussian vector. However, the best known finite-time rates are much slower. We derive the first nonasymptotic central limit theorem with respect to the Wasserstein-1 distance for two-time-scale stochastic approximation with Polyak-Ruppert averaging. As a corollary, we show that expected error achieved by Polyak-Ruppert averaging decays at rate 1/√(n), which significantly improves on the rates of convergence in prior works.