Concentration of contractive stochastic approximation: Additive and multiplicative noise
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.
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}
}
EUVIMED