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

Abstract

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 $\mathcal{X}\subset {\mathbb{R}}^d$ is a convex compact set and $p$ is an even integer. This is the first algorithm with $\text{poly}(d,\log (1/\hat{I}\mu ))$ runtime for any fixed $p\ne 2$. Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.