Summary
Finding points that do not change when a certain operation is applied is important in many fields. The authors give a new algorithm that can quickly find such points for high-dimensional problems measured in a specific way called the infinity norm. Their method uses a boosting technique to focus the search faster than before. This also means some game problems that were hard to solve can now be done in less time.
What this means in practice
- •For game developers: Solve simple stochastic games more efficiently to improve automated game analysis.
- •For optimization engineers: Find approximate fixed points faster in high-dimensional optimization problems using the provided algorithm.
A theory result. No direct application yet.
Authors
Ashkan Soleymani, Gabriele Farina
Abstract
We give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.