Query-Efficient Fixpoints of ${\ell }_p$-Contractions

Abstract

We prove that an $\hat{I}\mu$-approximate fixpoint of a map $f:[0,1{]}^d\to [0,1{]}^d$ can be found with $\mathcal{O}(d^2(\log \frac{1}{\hat{I}}\mu +\log \frac{1}{1-\hat{I}»}))$ queries to $f$ if $f$ is $\hat{I}»$-contracting with respect to an ${\ell }_p$-metric for some $p\in [1,\infty )\cup \{\infty \}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC'24] from the ${\ell }_{\infty }$-case to all ${\ell }_p$-metrics. Previously, all query upper bounds for $p\in [1,\infty )\setminus \{2\}$ were either exponential in $d$, $\log \frac{1}{\hat{I}}\mu$, or $\log \frac{1}{1-\hat{I}»}$. Chen, Li, and Yannakakis also show how to ensure that all queries to $f$ lie on a discrete grid of limited granularity in the ${\ell }_{\infty }$-case. We provide such a rounding for the ${\ell }_1$-case, placing an appropriately defined version of the ${\ell }_1$-case in ${\text{FP}}^{dt}$. To prove our results, we introduce the notion of ${\ell }_p$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p\in [1,\infty )\cup \{\infty \}$ and any mass distribution (or point set), we prove that there exists a centerpoint $c$ such that every ${\ell }_p$-halfspace defined by $c$ and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).

33 pages, 4 figures