Fixed Point Computation: Beating Brute Force with Smoothed Analysis

Idan Attias, Yuval Dagan, Constantinos Daskalakis +2

We propose a new algorithm that finds an $\epsilon$-approximate fixed point of a smooth function from the $n$-dimensional ${\ell }_2$ unit ball to itself. We use the general framew…