Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

arXiv:2609.09524v1 Announce Type: cross Abstract: We study the oracle complexity of computing a point with small fixed-point residual |T(x)-x| leq epsilon, for a general norm |dot| 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 |dot| and accessed via an unbiased stochastic oracle with bounded variance sigma^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 in [2, infty], our algorithm attains stochastic oracle complexity ilde O(sigma^2 epsilon^{-3} + epsilon^{-1}). We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such ell_{infty}-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any ell_p norm is of the same order, ruling out the possibility of improving oracle complexity as a function of arepsilon by measuring variance in a non-matching ell_p norm.

Related

• A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
• Mean-square and sublinear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature
• Centre manifold theorem for maps along manifolds of fixed points

Source: arXiv cs.LG | 2026-09-10