← 研踪 PaperTrailarXiv:2611.13846 · v1
Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation
首次提交 2026-11-10 18:04
版本更新 2026-11-10 18:04
雷达观测 2026-11-11 11:04
摘要
We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.
作者备注：23 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 18:04 · 最新观测版本
Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation
We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.
查看此版本解读 →查看此版本原文 ↗