Paper recorded by Signals 4 on 2026-10-21 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-10-21 on arXiv · recorded by Signals 4 on 2026-10-22
Category: cs.LG · 机器学习 · first seen 2026-10-22
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.