EUVIMEDEUVIMED entdecken
Crossref

Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation

Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov

Mathematics of Operations Research · 2025-05 · 50 (2) · 935-964

DOI: 10.1287/moor.2022.0179 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2025-05. Verfasst von Alain Durmus und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 30 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 [Formula: see text] for which [Formula: see text] can only be estimated by (asymptotically) unbiased observations [Formula: see text]. We consider here the case where [Formula: see text] is an a sequence of independent and identically distributed random variables sequence or a uniformly geometrically ergodic Markov chain. We derive pth moment and high-probability deviation bounds for the iterates defined by LSA and its Polyak–Ruppert-averaged version. Our finite-time instance-dependent bounds for the averaged LSA iterates are sharp in the sense that the leading term we obtain coincides with the local asymptotic minimax limit. Moreover, the remainder terms of our bounds admit a tight dependence on the mixing time [Formula: see text] of the underlying chain and the norm of the noise variables. We emphasize that our result requires the LSA step size to scale only with logarithm of the problem dimension d. Funding: The work of A. Durmus and E. Moulines was partly supported by [Grant ANR-19-CHIA-0002]. This project received funding from the European Research Council [ERC-SyG OCEAN Grant 101071601]. The research of A. Naumov and S. Samsonov was prepared within the framework of the HSE University Basic Research Program.

Zitieren

APA

Durmus, A., Moulines, E., Naumov, A., & Samsonov, S. (2025). Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation. Mathematics of Operations Research, 50(2), 935-964. https://doi.org/10.1287/moor.2022.0179

Vancouver

Durmus A, Moulines E, Naumov A, Samsonov S. Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation. Mathematics of Operations Research. 2025;50(2):935-964. doi:10.1287/moor.2022.0179

BibTeX
@article{Durmus2025,
  author = {Durmus, Alain and Moulines, Eric and Naumov, Alexey and Samsonov, Sergey},
  title = {Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation},
  journal = {Mathematics of Operations Research},
  year = {2025},
  volume = {50},
  number = {2},
  pages = {935--964},
  doi = {10.1287/moor.2022.0179}
}
Kostenlos starten →