TL;DR考虑了只观察到少量标签时，寻找 l1 回归的近似解的问题。我们表明，根据其 Lewis 权重对 X 进行采样并输出经验最小化器可在概率 1-δ 下成功地进行，其中 m>O（1/ε²dlog (d/εδ)）。我们还给出了相应的下界。
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 $\widehat{\beta}$ whose error on
the original problem is within a $1 + \varepsilon$ fac