{
  "abstract": "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 \\in [2, \\infty]$, 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 $\\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 $\\varepsilon$ by measuring variance in a non-matching $\\ell_p$ norm.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.09524",
  "author_total": 3,
  "authors": [
    {
      "name": "Jelena Diakonikolas"
    },
    {
      "name": "Cristóbal Guzmán"
    },
    {
      "name": "David Martínez-Rubio"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/8yk1gd0732z1b.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.09524",
  "fulltext_url": null,
  "id": "8yk1gd0732z1b",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.09524",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "openalex",
      "1702|Stochastic Gradient Optimization Techniques"
    ]
  ],
  "openalex": "W7212117869",
  "pdf_url": "https://arxiv.org/pdf/2609.09524",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-08",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/8yk1gd0732z1b.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:20:15Z",
      "native_id": "2609.09524",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.09524"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:stat.ML",
      "subfield": "statistics"
    }
  ],
  "title": "Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps",
  "title_text": "Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps",
  "type": "preprint",
  "updated_at": "2026-10-30T12:20:22Z",
  "url": "https://research.draconitic.com/paper/8yk1gd0732z1b",
  "venue": "arXiv",
  "versions": []
}