{"id":"arxiv/2609.09524","url":"https://arxiv.org/abs/2609.09524","tags":["math.OC","cs.DS","cs.LG","stat.ML"],"score":0,"title":"Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps","domain":"math.OC","source":"arxiv","authors":["Jelena Diakonikolas","Cristóbal Guzmán","David Martínez-Rubio"],"reviews":0,"subject":"math.OC","summary":"We study the oracle complexity of computing a point with small fixed-point residual $\\|T(x)-x\\| \\leq ε$, for a general norm $\\|\\cdot\\|$ and a self-map $T$ of a compact convex set. We study this problem in the setting where $T$ is nonexpansive with respect to the same norm $\\|\\cdot\\|$ and accessed via an unbiased stochastic oracle with bounded variance $σ^2$. We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability. The algorithm is based on a recursive anchoring technique. For type-$2$ spaces, such as $\\ell_p$-spaces for $p…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}