mlsanityData to 14 Oct 2026

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

arXiv 2609.09524 ↗First posted 8 Sep 2026math.OC cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

18 of 41 references.

References · 18

  1. 2019Deep Equilibrium Modelscited by 615
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  4. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  5. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  6. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  7. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  8. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  9. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  10. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  11. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 17
  12. 2021Optimal error bounds for nonexpansive fixed-point iterations in normed spacescited by 12
6 more
  1. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  2. 2024Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependencecited by 6
  3. 2025Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansioncited by 5
  4. 2026Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variancecited by 5
  5. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  6. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1

Built on by

Not cited yet.