# Fixed Point Computation: Beating Brute Force with Smoothed Analysis

arXiv: https://arxiv.org/abs/2501.10884 · HTML: https://mlsanity.com/paper/2501.10884/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 18 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Smoothed Complexity of 2-player Nash Equilibria](https://mlsanity.com/paper/2007.10857/) (2020)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [A Converse to Banach's Fixed Point Theorem and its CLS Completeness](https://mlsanity.com/paper/1702.07339/) (2017)

## Built on by (most cited first, 1 of 1)

- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)

## Abstract (arXiv)

We propose a new algorithm that finds an varepsilon-approximate fixed point of a smooth function from the n-dimensional ℓ2 unit ball to itself. We use the general framework of finding approximate solutions to a variational inequality, a problem that subsumes fixed point computation and the computation of a Nash Equilibrium. The algorithm's runtime is bounded by eO(n)/varepsilon, under the smoothed-analysis framework. This is the first known algorithm in such a generality whose runtime is faster than (1/varepsilon)O(n), which is a time that suffices for an exhaustive search. We complement this result with a lower bound of eOmega(n) on the query complexity for finding an O(1)-approximate fixed point on the unit ball, which holds even in the smoothed-analysis model, yet without the assumption that the function is smooth. Existing lower bounds are only known for the hypercube, and adapting them to the ball does not give non-trivial results even for finding O(1/√n)-approximate fixed points.