Acceleration Meets Inverse Maintenance: Faster ${\ell }_{\infty }$-Regression

Deeksha Adil, Shunhua Jiang, Rasmus Kyng

We propose a randomized multiplicative weight update (MWU) algorithm for ${\ell }_{\infty }$ regression that runs in $\tilde{O}\left(n^{2+1/22.5}\text{poly}(1/\epsilon )\right)$ time when…