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

Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1

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$ i…