2025/01/18 by Idan Attias, Attias, Idan, Yuval Dagan +7 · 1 citation
Computer Science · #Music Technology and Sound Studies
paper · pdf · doi:10.48550/arxiv.2501.10884
We propose a new algorithm that finds an ε-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)/ε, under the smoothed-analysis framework. This is the first known algorithm in such a generality whose runtime is faster than (1/ε)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/√(n))-approximate fixed points.