Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations
En palabras de los autores
We study stochastic fixed-point iterations for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule whose density does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities the tradeoff is exact, with on rotations by angle (, ) and, for the classical schedule, . 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 , , and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is on affine maps, and within the anchored class 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 in every -uniformly smooth Banach space and the Hilbert rate by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 55 pages, 5 figures