We provide faster algorithms for approximately solving \(\ell_{\infty}\) regression, a fundamental problem prevalent in both combinatorial and continuous optimization. In particular, we provide accelerated coordinate descent methods capable of provably exploiting dynamic measures of coordinate smoothness, and apply them to \(\ell_\infty\) regressio...

Coordinate Methods for Accelerating \(\ell_\infty\) Regression and Faster Approximate Maximum Flow