Fixed Point Computation: Beating Brute Force with Smoothed Analysis
This work addresses a fundamental computational challenge in optimization and game theory, offering a significant speedup over brute-force methods for fixed point computation, though it is incremental in extending smoothed analysis to this domain.
The paper tackles the problem of finding an approximate fixed point for smooth functions on the unit ball, proposing an algorithm with runtime bounded by e^{O(n)}/ε, which is faster than the brute-force exhaustive search time of (1/ε)^{O(n)}. It also provides a lower bound of e^{Ω(n)} on query complexity for approximate fixed points on the unit ball, even in the smoothed-analysis model.
We propose a new algorithm that finds an $\varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $\ell_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 $e^{O(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 $e^{Ω(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/\sqrt{n})$-approximate fixed points.