Skip to content
Preprint

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations

Sep 2026 · 0 citations
Mathematics Computer Science

Abstract

We study stochastic fixed-point iterations $x_{n+1}=\theta_nx_0+(1-\theta_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 $\theta_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 $\theta_n=c/(n+2)$ the tradeoff is exact, with $\norm{x_n}\asymp\Gamma(c+1)(n\varphi)^{-c}$ on rotations by angle $\varphi$ ($\varphi\to0$, $n\varphi\to\infty$) and, for the classical schedule, $\norm{x_n}=\frac{2|\sin(n\varphi/2)|}{n\varphi}+O(\frac1n)$. The dichotomy fails exactly under lacunary anchor concentration: an explicit $\gamma$-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent $1/\alpha_0$, $\alpha_0=\log_2(3/2)$, and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is $\Theta(\sigma^2\eps^{-2}(1-\gamma)^{-2})$ on affine maps, and within the anchored class $\Theta(\sigma^2\eps^{-2}(1-\gamma)^{-2}+(1-\gamma)^{-1}\ln(D/\eps))$ for known modulus via geometric batching; without a certified modulus bound no sound distance certificate exists, and a certified ceiling is the exact boundary. For nonexpansive maps we prove $O(K\sigma^2D^2\eps^{-4})$ in every $2$-uniformly smooth Banach space and the Hilbert rate $\tilde\Theta(\sigma^2\eps^{-2}+D\eps^{-1})$ by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.