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

Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1

We prove that an $\epsilon$-approximate fixpoint of a map $f:[0,1{]}^d\to [0,1{]}^d$ can be found with $\mathcal{O}(d^2(\log \frac{1}{\epsilon }+\log \frac{1}{1-\lambda }))$ queries to $f$ if $f$ is $…