Polynomial-time computation of ${\ell }_p$-contraction fixed points for even $p$

Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang

We give a $\text{poly}(d,p,\log (1/\hat{I}\mu ))$-time algorithm that computes an $\hat{I}\mu$-approximate fixed point of any ${\ell }_p$-nonexpansive map $f:\mathcal{X}\to \mathcal{X}$, where $\m…