EUVIMEDEUVIMED entdecken
Crossref

Concentration of contractive stochastic approximation: Additive and multiplicative noise

Zaiwei Chen, Siva Theja Maguluri, Martin Zubeldia

The Annals of Applied Probability · 01.04.2025 · 35 (2) · 1298-1352

DOI: 10.1214/24-aap2143 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Annals of Applied Probability, erschienen am 01.04.2025. Verfasst von Zaiwei Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 83 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we establish maximal concentration bounds for the iterates generated by a stochastic approximation (SA) algorithm under a contractive operator with respect to some arbitrary norm (e.g., the ℓ∞-norm). We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise. Our maximal concentration inequalities state that the convergence error has a sub-Gaussian tail in the additive noise setting and a Weibull tail (which is faster than polynomial decay but could be slower than exponential decay) in the multiplicative noise setting. In addition, we provide an impossibility result showing that it is generally impossible to have sub-exponential tails under multiplicative noise. To establish the maximal concentration bounds, we develop a novel bootstrapping argument that involves bounding the moment-generating function of a modified version of the generalized Moreau envelope of the convergence error and constructing an exponential supermartingale to enable using Ville’s maximal inequality. We demonstrate the applicability of our theoretical results in the context of linear SA and reinforcement learning.

Zitieren

APA

Chen, Z., Maguluri, S. T., & Zubeldia, M. (2025). Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability, 35(2), 1298-1352. https://doi.org/10.1214/24-aap2143

Vancouver

Chen Z, Maguluri ST, Zubeldia M. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability. 2025;35(2):1298-1352. doi:10.1214/24-aap2143

BibTeX
@article{Chen2025,
  author = {Chen, Zaiwei and Maguluri, Siva Theja and Zubeldia, Martin},
  title = {Concentration of contractive stochastic approximation: Additive and multiplicative noise},
  journal = {The Annals of Applied Probability},
  year = {2025},
  volume = {35},
  number = {2},
  pages = {1298--1352},
  doi = {10.1214/24-aap2143}
}
Kostenlos starten →