A Nearly-Optimal Bound for Fast Regression with ${\ell }_{\infty }$ Guarantee

Zhao Song, Mingquan Ye, Junze Yin +1

Given a matrix $A\in {\mathbb{R}}^{n\times d}$ and a vector $b\in {\mathbb{R}}^n$, we consider the regression problem with ${\ell }_{\infty }$ guarantees: finding a vector $x'\in \mathbb{R}^…