Source-linked AI summary
A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
Ashkan Soleymani, Gabriele Farina
TL;DR
The open question is whether an ε-approximate fixed point can be computed in time polynomial in d, log(1/ε), and log(1/γ), despite Picard iteration taking O(γ^-1 log(1/ε)) evaluations. The algorithm boosts thin labelings by querying several and using majority voting to construct final labels. Solve(f, ε) returns an ε-near fixed point for a (1−γ)-contraction; for d≥2 and 0<ε≤1/2, ℓ∞-nonexpansive maps admit deterministic ε-approximate fixed-point computation with complexity log(1/ε)^{C log² d}.
Problem
The open question is whether an ε-approximate fixed point can be computed in time polynomial in d, log(1/ε), and log(1/γ), despite Picard iteration taking O(γ^-1 log(1/ε)) evaluations.
Source: §1 · p. 1Method
The algorithm boosts thin labelings by querying several and using majority voting to construct final labels.
Source: §4.2 · p. 8Results
Solve(f, ε) returns an ε-near fixed point for a (1−γ)-contraction; for d≥2 and 0<ε≤1/2, ℓ∞-nonexpansive maps admit deterministic ε-approximate fixed-point computation with complexity log(1/ε)^{C log² d}.
Source: §1 · p. 2Takeaways & Limitations
The reductions yield exact quasipolynomial-time solutions for simple stochastic games and extend the bound to several turn-based stochastic games.
Source: §1 · p. 2The algorithm may use search boxes outside [0,1]^d, so the analysis extends f by clipping inputs to the domain.
Source: §3 · p. 5
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction presents a quasipolynomial-time approach to fixed-point computation and its applications to stochastic games. Its key advance is a dimension dependence of O(log^2 d), with reductions extending the approach to several game and decision problems.
Motivation
- The motivating open question asks whether approximate fixed points can be computed in time polynomial in d, log(1/ε), and log(1/γ).Picard iteration takes O(γ^-1 log(1/ε)) evaluations, which can be exponential in input size when the contraction gap is exponentially small.Source: §1 · p. 1
Result and consequences
- The paper gives a first quasipolynomial-time algorithm for finding near fixed points of ℓ∞-contractions.Its main theorem concerns contractions on [0,1]^d, and the introduction also derives a deterministic algorithm for approximate fixed points of ℓ∞-nonexpansive maps.Source: §1 · p. 2
- Scaling a nonexpansion f by 1 − ε/2 gives a contraction whose (ε/4)-near fixed points are ε-approximate fixed points of f.This reduction yields the stated nonexpansion bound for d ≥ 2 and 0 < ε ≤ 1/2.Source: §1 · p. 2
- O(log^2 d) replaces the prior O(d log d) exponent, changing the total running-time bound from subexponential to quasipolynomial.When log(1/ε) = d^O(1), the bounds improve from exp(O(d log^2 d)) to exp(O(log^3 d)).Source: §1 · p. 2
Applications
- The algorithm yields exact quasipolynomial-time solutions for simple stochastic games and value-vector approximations for Shapley’s general discounted stochastic games.Polynomial-bit parameters and efficiently evaluable operators support the SSG reduction; Turing equivalences extend the bound to several turn-based stochastic games.Source: §1 · p. 2
- Reductions extend the consequences to deterministic mean-payoff games, parity games, and modal µ-calculus model checking.Figure 1 places approximate fixed-point computation and SSGs among intermediate problems and further consequences.Source: §1 · p. 2, Figure 1 · p. 3
2 Further Related Work
The related-work discussion distinguishes approaches by norm, map structure, and computational guarantees. It places the paper alongside algorithms for nonexpansive maps, monotone maps, and game-specific problems.
Games and other norms
- Other adjacent work includes smoothed polynomial-time algorithms for deterministic games and fixed-dimensional algorithms for ℓ1-contractions.A reduction also connects generalized Arrival to approximate fixed-point computation for ℓ1-contractions.Source: §2 · pp. 4–5
ℓ∞-nonexpansive maps
- For ℓ∞-nonexpansive maps, earlier fixed-dimension running times remain exponential in dimension, while query-efficient methods incurred exponential computation to select queries.Feodorov and Haslebacher later bounded both query complexity and total running time subexponentially.Source: §2 · p. 4
Monotone maps
- Monotone ℓ∞-contractions admit dimension-dependent query and total-running-time bounds; monotone finite-grid maps have separate query bounds and lower bounds.Without contraction, Tarski fixed points connect to simple stochastic games, Shapley-game values, and supermodular-game equilibria.Source: §2 · p. 4
Norms and map classes
- For ℓp maps, prior work gives polynomial query bounds for contractions, while a poly(d, p, log(1/ε))-time result applies to ℓp-nonexpansive maps for even p.For ℓ2, an ellipsoid-based method uses O(d log(1/ε)) function evaluations.Source: §2 · p. 5
3 Preliminaries and Notation
The preliminaries extend the function beyond its original domain by clipping inputs, and establish bounds relating residual error to distance from the unique fixed point.
Preliminaries and notation
- The algorithm extends f outside [0,1]^d by applying it to the clipped input, preserving the contraction gap and unique fixed point.The notation x_N and x_-N denotes subvectors on a coordinate set and its complement; f_N restricts the output to coordinates in N.Source: §3 · p. 5
- The stated lemma is used to convert guarantees between approximate and near fixed points.The residual-distance inequalities provide the conversion bounds.Source: §3 · p. 5
- For every x, the residual norm lies between γ times and (2 − γ) times the distance to the unique fixed point.The bounds follow from the contraction property and the triangle inequality.Source: §3 · p. 5
4 Algorithm Overview
The algorithm repeatedly shrinks a box containing the fixed point, using coordinate labels to choose safe inward moves. It formalizes accurate labelings and constructs them by boosting recursively built thin labelings.
4 Algorithm Overview
- Each iteration moves one face inward by D/8 per coordinate while preserving the fixed point in the box, shrinking side lengths by a factor of 7/8.After O(log(1/ε)) iterations, the box has size ε and its midpoint is an ε-approximate fixed point.Source: §4 · p. 5
- The labeling routine identifies when each fixed-point coordinate is near a box extremum, enabling safe inward face updates; it can instead return an ε-near fixed point.At least one face per coordinate is safe to move inward by D/8.Source: §4 · pp. 5–6, §4.1 · p. 6
4.1 Labelings
- A τ-accurate labeling assigns lo or hi to box faces according to whether their slacks are near the minimum or maximum slack.If no valid labeling exists, the box center is already a τ-near fixed point.Source: §4.1 · pp. 6–7
4.2 Overview of Labeling Construction
- The construction first builds thin labelings by splitting coordinates at median side length and recursively solving lower-dimensional contractions, then boosts accuracy by majority voting.The thin labels have accuracy O(γ); the resulting labeler runs in time log(τ/(γε))^O(log^2 d).Source: §4.2 · pp. 7–8
5 Constructing Thin Labelings
ThinLabel divides coordinates by side length, recursively solves contractions on the two coordinate groups, and uses the resulting point to produce either an approximate fixed point or a thin labeling.
5 Constructing Thin Labelings
- The algorithm splits coordinates into narrow and wide groups at the median side length, then recursively solves restricted contractions of dimension at most d/2.Each restriction fixes the coordinates in the other group to the box center.Source: §5 · p. 8
- ThinLabel returns either an η-approximate fixed point or a γη/8-accurate labeling for the box.The returned approximate fixed point may lie outside the box.Source: §5 · p. 8
- When the candidate point is not an η-approximate fixed point, estimates of fixed-point distances to box faces support assignments satisfying the thin-labeling contract.The estimates use f(x) as an approximation to the fixed point; contractivity bounds the error relative to separated face slacks.Source: §5 · pp. 8–9
- The candidate point combines approximate fixed points from the two restricted problems, with narrow coordinates clipped to a median-width interval.The proof uses these recursive solutions to establish sufficient separation between extreme slacks and the median half-side.Source: §5 · pp. 9–10
6 Amplifying Thin Labelings
This section develops an amplification procedure for turning labels initially correct near extrema into constant-accuracy labels, framing the task as an extremal amplification game and connecting it to thin labeling. It establishes Amplify’s coordinate-labeling correctness and recursive-cost bound, then states a complexity bound for Solve on contractions using lower-dimensional recursive calls.
6 Amplifying Thin Labelings
- For n ≥ 2 and κ ≥ 4ρ > 0, Amplify either obtains the Oracle’s defeat or returns a κ-accurate labeling, with quasipolynomially many Oracle calls in log(κ/ρ) and O(nQ) additional arithmetic operations.The call-count expression is omitted from the supplied theorem passage, so this point reports only its stated dependence and arithmetic bound.Source: §6 · p. 12
6.1 Vanilla Boosting
- AdaBoost’s potential argument reduces the potential when incorrect predictions carry at most one quarter of its known upper bound; here, potential bounds replace unavailable true labels.The section presents a direct potential proof, avoiding the deeper minimax-theorem connection.Source: §6.1 · pp. 12–13
6.2 Algorithm
- Amplify runs separate boosting processes for coordinates near the maximum and minimum, using recursive half-accuracy Oracle calls when extremal weights are high to secure the required mistake-weight bound.Its relaxed termination condition is that the product of the two potential bounds is below 1.Source: §6.2 · pp. 13–15
6.3 Correctness
- Theorem 3 establishes termination with either Oracle defeat or labels satisfying the contract; with n = 2d and ThinLabel precision η = γε, the construction yields an ε-near fixed point or a τ-accurate labeling.The initialization Amplify(0, 2κ, 0, n, n) solves the extremal amplification game.Source: §6.3 · p. 16
- Amplify’s correctness follows from preserving required labels through its steps and using a weak oracle when labels remain unset; boosting then resolves any remaining labels correctly.The guarantee applies when the potential bound holds at the start of a boosting iteration, and a symmetric argument handles the negative labels.Source: §6.3 · p. 19
6.5 Complexity of Solve
- Theorem 1 bounds Solve’s arithmetic operations and exact evaluations of f for returning an ε-near fixed point of a (1 − γ)-contraction; ThinLabel recurses on at most two problems of half the dimension.The supplied theorem passage omits the explicit upper-bound expression; the recursive calls use tolerance γ²ε/2.Source: §6.5 · p. 21