Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations
Abstract
We study stochastic fixed-point iterations xn+1=θnx0+(1−θn)T̂(xn) for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule θn=cn/(n+2) whose density cn∈(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 normxnasympΓ(c+1)(nφ)−c on rotations by angle φ (φ→0, nφ→∞) and, for the classical schedule, normxn=2|sin(nφ/2)|/nφ+O(1/n). The dichotomy fails exactly under lacunary anchor concentration: an explicit γ-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent 1/α0, α0=log2(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 Θ(σ2eps−2(1−γ)−2) on affine maps, and within the anchored class Θ(σ2eps−2(1−γ)−2+(1−γ)−1ln(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σ2D2eps−4) in every $2$-uniformly smooth Banach space and the Hilbert rate Θ̃(σ2eps−2+Deps−1) by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.
Related
- Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
- Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers
- Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
- Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
- Exact oracle complexity for function-value suboptimality under weighted initial conditions
BibTeX
@misc{shehu2026adaptivity,
title = {{Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations}},
author = {Yekini Shehu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00295},
eprint = {2610.00295},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00295},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations
AU - Yekini Shehu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00295
UR - https://arxiv.org/abs/2610.00295
AB - We study stochastic fixed-point iterations x_n+1=θ_nx_0+(1−θ_n)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∈(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 normx_nasympΓ(c+1)(nφ)^−c on rotations by angle φ (φ→0, nφ→∞) and, for the classical schedule, normx_n=2|sin(nφ/2)|/nφ+O(1/n). The dichotomy fails exactly under lacunary anchor concentration: an explicit γ-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent 1/α_0, α_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 Θ(σ^2eps^−2(1−γ)^−2) on affine maps, and within the anchored class Θ(σ^2eps^−2(1−γ)^−2+(1−γ)^−1ln(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σ^2D^2eps^−4) in every $2$-uniformly smooth Banach space and the Hilbert rate Θ̃(σ^2eps^−2+Deps^−1) by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.
ER -