?
Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
Ch. 247. P. 4511–4547.
Language:
English
Keywords: GTD learninglinear stochastic approximationстохастическая аппроксимацияRandom matrix products
Publication based on the results of:
Levin I., Shuklin M., Moulines E. et al., , in: Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337: Conference on Uncertainty in Artificial Intelligence, 17-21 August 2026, KIT, Amsterdam, the NetherlandsVol. 337.: MLResearchPress, 2026. Ch. 134 P. 3487–3545.
In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated {Gaussian} approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects of local step size, number of local updates, and heterogeneity on convergence rates. We present results for both (i) constant ...
Added: September 4, 2026
Levin I., Naumov A., Samsonov S., , in: Proceedings of the AAAI Conference on Artificial Intelligence. AAAI-26: AAAI Technical Track on Planning, Routing, and Scheduling; AAAI Technical Track on Reasoning under Uncertainty; AAAI Technical Track on Search and Optimization. Main Track, volume 40 no. 43.: American Association for Artificial Intelligence (AAAI) Press, 2026. P. 36696–36704.
In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the ...
Added: April 17, 2026
Samsonov S., Sheshukova M., Moulines E. et al., , in: 39th Conference on Neural Information Processing Systems (NeurIPS 2025).: NeurIPS, 2025. P. 174565–174626.
In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields O(n −1/4 ) convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the nonasymptotic validity of a multiplier block bootstrap procedure for constructing the ...
Added: January 26, 2026
Mangold P., Samsonov S., Labbi S. et al., , in: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).: [б.и.], 2024. Ch. 37 P. 13927–13981.
In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ϵ. To overcome this, we propose SCAFFLSA a new ...
Added: February 11, 2025
Durmus A., Moulines E., Naumov A. et al., Mathematics of Operations Research 2025 Vol. 50 No. 2 P. 935–964
This paper provides a finite-time analysis of linear stochastic approximation (LSA) algorithms with fixed step size, a core method in statistics and machine learning. LSA is used to compute approximate solutions of a $d$-dimensional linear system $\bar{\mathbf{A}} \theta = \bar{\mathbf{b}}$, for which $(\bar{\mathbf{A}}, \bar{\mathbf{b}})$ can only be estimated through (asymptotically) unbiased observations $\{(\mathbf{A}(Z_n),\mathbf{b}(Z_n))\}_{n \in \mathbb{N}}$. ...
Added: July 13, 2022
Durmus A., Moulines E., Naumov A. et al., , in: Advances in Neural Information Processing Systems 34 (NeurIPS 2021).: Curran Associates, Inc., 2021. P. 30063–30074.
This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and $\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf b}_n): ...
Added: February 17, 2022
Durmus A., Moulines E., Naumov A. et al., , in: Proceedings of Machine Learning ResearchVol. 134: Conference on Learning Theory.: PMLR, 2021. P. 1711–1752.
Added: August 6, 2021
Kaledin M., Moulines E., Naumov A. et al., , in: Proceedings of Machine Learning ResearchVol. 125: Proceedings of Thirty Third Conference on Learning Theory.: [б.и.], 2020. P. 2144–2203.
Added: July 30, 2020