Computing a Fixed Point of Contraction Maps in Polynomial Queries

Abstract

We give an algorithm for finding an $\hat{I}\mu$-fixed point of a contraction map $f:[0,1{]}^k\mapsto [0,1{]}^k$ under the ${\ell }_{\infty }$-norm with query complexity $O(k\log (1/\hat{I}\mu ))$.

Journal version with improved bounds