L1 Regression with Lewis Weights Subsampling

Abstract

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 n rows to observe the labels of, then output an estimate whose error on the original problem is within a 1 + 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(1^2 d d ). 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 (d^2 + (d + 1^2) 1).

Tasks

Reproductions