Fixed Point Computation: Beating Brute Force with Smoothed Analysis

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.