{"id":"arxiv/2610.00295","url":"https://arxiv.org/abs/2610.00295","tags":["math.OC","cs.IT"],"score":0,"title":"Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations","domain":"math.OC","source":"arxiv","authors":["Yekini Shehu"],"reviews":0,"subject":"math.OC","summary":"We study stochastic fixed-point iterations $x_{n+1}=θ_nx_0+(1-θ_n)\\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $θ_n=c_n/(n+2)$ whose density $c_n\\in(0,1]$ does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities $θ_n=c/(n+2)$ the tradeoff is exact, with $\\norm{x_n}\\asympΓ(c+1)(n\\varphi)^{-c}$ on rotations by angle $\\varphi$ ($\\varphi\\to0$, $n\\varphi\\to\\infty$) and, for the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}