# Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

arXiv: https://arxiv.org/abs/2609.09524 · HTML: https://mlsanity.com/paper/2609.09524/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 18 of 18)

- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Optimal error bounds for nonexpansive fixed-point iterations in normed spaces](https://mlsanity.com/paper/2108.10969/) (2021)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependence](https://mlsanity.com/paper/2411.11271/) (2024)
- [Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion](https://mlsanity.com/paper/2506.17698/) (2025)
- [Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance](https://mlsanity.com/paper/2604.22581/) (2026)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)

## Abstract (arXiv)

We study the oracle complexity of computing a point with small fixed-point residual |T(x)-x| ≤ ε, for a general norm |·| 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 |·| 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 ℓp-spaces for p ∈ [2, ∞], our algorithm attains stochastic oracle complexity tilde O(σ2 ε-3 + ε-1). We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such ℓ∞-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 ℓp norm is of the same order, ruling out the possibility of improving oracle complexity as a function of varepsilon by measuring variance in a non-matching ℓp norm.