Computing a Fixed Point of Contraction Maps in Polynomial Queries

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $\epsilon$-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/\epsilon ))$.