Неасимптотический анализ алгоритмов стохастической аппроксимации и приложения

Доклад посвящен алгоритмам стохастической аппроксимации, которые широко используются для поиска приближенного решения уравнения $f(x*) = 0$ в случае, когда функция $f$ неизвестна, но может быть оценена через несмещённые наблюдения $F(x, Z_n), n>=1$. Будет рассмотрен случай, когда $Z_n, n>=1$, образуют последовательность независимых одинаково распределенных случайных величин, а также более общий случай эргодической цепи Маркова. Мы дадим неасимптотические оценки для процедуры усреднения Поляка–Рупперта и рассмотрим примеры приложения доказанных теорем к задачам теории оценивания, оптимизации и теории обучения с подкреплением. В завершение доклада обсудим вопрос построения доверительных интервалов для неизвестного решения.

Список литературы

1. A. Durmus, E. Moulines, A. Naumov, S. Samsonov, “Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation”, Mathematics of Operations Research, 2024, 1–30  
2. S. Samsonov, D. Tiapkin, A. Naumov, E. Moulines, “Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability”, Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research, 247, 2024, 4511–4547 https://proceedings.mlr.press/v247/samsonov24a.html
3. S. Samsonov, E. Moulines, Qi-Man Shao, Zhuo-Song Zhang, A. Naumov, Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning, NeurIPS, 2023