Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

Abstract

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 σ². 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 Õ(σ² ε⁻³ + ε⁻¹). 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 ε by measuring variance in a non-matching ℓ_p norm.

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations
Yekini Shehu
arXiv1 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
Weiming Ou, Xiao Wang
arXiv26 Sep 2026PreprintCC BY 4.0Full textProbability StatisticsarXiv
An unbounded convex set with the fixed point property for nonexpansive mappings
M. Japón, Javier Laguna-Ricart
arXiv10 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
Wei Bian, Zekai Li
arXiv24 Sep 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Fixed point results for mappings of asymptotically Hölder nonexpansive type
Cleon S. Barroso, Carlos Sérgio R. da Silva
arXiv15 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{diakonikolas2026oracle,
  title = {{Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps}},
  author = {Jelena Diakonikolas and Cristóbal Guzmán and David Martínez-Rubio},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.09524},
  eprint = {2609.09524},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.09524},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
AU  - Jelena Diakonikolas
AU  - Cristóbal Guzmán
AU  - David Martínez-Rubio
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.09524
UR  - https://arxiv.org/abs/2609.09524
AB  - 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 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 ε by measuring variance in a non-matching ℓ_p norm.
ER  -

Abstract

Related

Cite