L1 Regression with Lewis Weights Subsampling

Aditya Parulekar, Advait Parulekar, Eric Price

We consider the problem of finding an approximate solution to ${\ell }_1$ regression while only observing a small number of labels. Given an $n\times d$ unlabeled data matrix $X$, we…