A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

Ashkan Soleymani; Gabriele Farina

cs.GTOct 21, 2026

A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

Authors: Ashkan Soleymani, Gabriele Farina

Organizations: MIT

Abstract

We give an algorithm for computing an $\eps$ -approximate fixed point of any $d$ -dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$ . At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.

Figures & tables

Panel of Figure 1 — Figure 1: Polynomial-time reduction hierarchy connecting approximate $\ell_{\infty}$ fixed-point computation to stochastic games and related decision problems. The dashed box groups turn-based, perfect-information stochastic games that are polynomial-time Turing equivalent [ AM09a ] . The upper reductions arise from the fixed-point formulation of discounted stochastic games, where sufficiently accurate approximations also yield exact solutions to SSGs [ Sha53 , BFG+25 ] . The lower reductions connect parity games, modal $\mu$ -calculus model checking, and decision problems equivalent to deterministic mean-payoff games [ Jur98 , EJS01 , BCD+11 , AGG12 , AGQS23 , AM09b ] . The red boxes highlight our main result and its application to SSGs, the gray boxes indicate intermediate problems, and the white boxes show further consequences.

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioOracle Complexity Stochastic Approximation
Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain
Solving Stochastic Fixed-Point Equations with High Probability
Jul 10, 2026Jelena DiakonikolasStochastic Approximation Stochastic Optimization Convergence
Department of Computer Sciences University of Wisconsin-Madison
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
May 24, 2026Samuel B. Hopkins, Stefan TiegelRobust Regression Robust Mean Estimation
MIT

Sep 8, 2026J/K move · Enter open · S save

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio

Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain

Oracle Complexity Stochastic Approximation Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

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

Explore similar work

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

Solving Stochastic Fixed-Point Equations with High Probability

Algorithms with Polynomially-Improved Approximation Factors for the 2→q2 \rightarrow q2→q Norm, and Applications

Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications