L1 Regression with Lewis Weights Subsampling

Abstract

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 must choose a small set of $m\ll n$ rows to observe the labels of, then output an estimate ${\hat{\hat{I}}}^2$ whose error on the original problem is within a $1+\epsilon$ factor of optimal. We show that sampling from $X$ according to its Lewis weights and outputting the empirical minimizer succeeds with probability $1-\hat{I}´$ for $m>O(\frac{1}{{\epsilon }^2}d\log \frac{d}{\epsilon \hat{I}´})$. This is analogous to the performance of sampling according to leverage scores for ${\ell }_2$ regression, but with exponentially better dependence on $\hat{I}´$. We also give a corresponding lower bound of $\hat{I}\text{c◯}(\frac{d}{{\epsilon }^2}+(d+\frac{1}{{\epsilon }^2})\log \frac{1}{\hat{I}}´)$.