?
On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning
P. 1711–1752.
Publication based on the results of:
In book
Vol. 134: Conference on Learning Theory. , PMLR, 2021.
Levin I., Shuklin M., Moulines E. et al., , in: Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337, 17-21 August 2026, KIT, Amsterdam, the NetherlandsVol. 337.: Proceedings of Machine Learning Research , 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
Соболев В. Н., Фролов А. А., Чебышевский сборник 2025 Т. 26 № 5 С. 203–220
In the article, on the class K 0 of infinite binary sequences without the runs of ones, a
consistent probability distribution P is constructed which is induced by a time-homogeneous
Markov chain with a one-step transition matrix P𝜑 , and is completely determined by the
golden ratio 𝜑. Using a Markov chain to construct a probability measure P ...
Added: February 11, 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
Skorobogatov A., Economics of Transition and Institutional Change 2026 Vol. 34 No. 2 P. 387–409
This paper analyzes the dynamics of the public attitude towards religion using longitudinal data from Russian respondents. Applying Markov chains and regression analysis, we determine the relative success of religious groups in retaining and attracting members. Based on this information, we estimate and explain the projected religious composition of Russia. According to our results, the ...
Added: November 3, 2025
Sheshukova M., Belomestny D., Durmus A. et al., , in: Proceedings of the 13th International Conference on Learning Representations (ICLR 2025).: ICLR, 2025.
Added: August 15, 2025
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
Sheshukova M., Belomestny D., Durmus A. et al., / Series arXiv "math". 2024.
We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation technique to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We ...
Added: October 13, 2024
Samsonov S., Tiapkin D., Naumov A. et al., , in: Proceedings of Machine Learning Research. Volume 247: The Thirty Seventh Annual Conference on Learning Theory, 30-3 July 2023, Edmonton, Canada.: PMLR, 2024. Ch. 247 P. 4511–4547.
Added: October 13, 2024
Durmus A., Moulines E., Naumov A. et al., / Series arXiv "math". 2023.
In this paper, we establish novel deviation bounds for additive functionals of geometrically ergodic Markov chains similar to Rosenthal and Bernstein-type inequalities for sums of independent random variables. We pay special attention to the dependence of our bounds on the mixing time of the corresponding chain. Our proof technique is, as far as we know, ...
Added: June 18, 2023
Konakov V., Mammen E., / Series arXiv "math". 2023. No. 2304.10673.
The Robbins-Monro algorithm is a recursive, simulation-based stochastic procedure to approximate the zeros of a function that can be written as an expectation. It is known that under some technical assumptions, Gaussian limit distributions approximate the stochastic performance of the algorithm. Here, we are interested in strong approximations for Robbins-Monro procedures. The main tool for ...
Added: April 24, 2023
Samsonov S., Lagutin E., Gabrie M. et al., , in: Thirty-Sixth Conference on Neural Information Processing Systems : NeurIPS 2022.: Curran Associates, Inc., 2022. P. 5178–5193.
Added: February 1, 2023
Cardoso G., Samsonov S., Thin A. et al., , in: Thirty-Sixth Conference on Neural Information Processing Systems : NeurIPS 2022.: Curran Associates, Inc., 2022. P. 716–729.
Added: February 1, 2023
Runev E. V., Springer Nature Switzerland 2022 Vol. 402 No. 1 P. 343–351
The book presents latest developments in the field of high-speed railway, Hyperloop transportation technologies and Maglev system. In recent years, railway transport has received a powerful impetus in its development. With the advent of the 4th Industrial revolution, the transport sector is moving towards full digitalization. TransSiberia is a platform where both the rail industry ...
Added: November 1, 2022
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
Veretennikov A., Veretennikova M., Известия РАН. Серия математическая 2022 Т. 86 № 1 С. 98–133
We continue the work of improving the rate of convergence of ergodic homogeneous Markov chains. The setting is more general than in previous papers: we are able to get rid of the assumption about a common dominating measure and consider the case of inhomogeneous Markov chains as well as more general state spaces. We give examples ...
Added: March 14, 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., Journal of Theoretical Probability 2024 Vol. 37 P. 2184–2233
In this paper, we establish moment and Bernstein-type inequalities for additive functionals of geometrically ergodic Markov chains. These inequalities extend the corresponding inequalities for independent random variables. Our conditions cover Markov chains converging geometrically to the stationary distribution either in V-norms or in weighted Wasserstein distances. Our inequalities apply to unbounded functions and depend explicitly on ...
Added: September 7, 2021
Olshanski G., Selecta Mathematica, New Series 2021 Vol. 27 Article 41
Using Okounkov’s q-integral representation of Macdonald polynomials we construct an infinite sequence Ω1,Ω2,Ω3,… of countable sets linked by transition probabilities from Ω𝑁 to Ω𝑁−1 for each 𝑁=2,3,…. The elements of the sets Ω𝑁 are the vertices of the extended Gelfand–Tsetlin graph, and the transition probabilities depend on the two Macdonald parameters, q and t. These ...
Added: June 4, 2021