L1 Regression with Lewis Weights Subsampling

We consider the problem of finding an approximate solution to ℓ1 regression while only observing a small number of labels. Given an n × 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 widehatβ whose error on the original problem is within a 1 + varepsilon factor of optimal. We show that sampling from X according to its Lewis weights and outputting the empirical minimizer succeeds with probability 1-δ for m > O(frac1varepsilon2 d log fracdvarepsilon δ). This is analogous to the performance of sampling according to leverage scores for ℓ2 regression, but with exponentially better dependence on δ. We also give a corresponding lower bound of Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1δ).