L1 Regression with Lewis Weights Subsampling

Aditya Parulekar, Advait Parulekar, Eric Price

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{eta}$ 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-\delta$ for $m > O(\frac{1}{\varepsilon^2} d \log \frac{d}{\varepsilon \delta})$. This is analogous to the performance of sampling according to leverage scores for $\ell_2$ regression, but with exponentially better dependence on $\delta$. We also give a corresponding lower bound of $\Omega(\frac{d}{\varepsilon^2} + (d + \frac{1}{\varepsilon^2}) \log\frac{1}{\delta})$.

Introduction

In many modern machine learning applications, unlabeled data is abundant, but obtaining labels is a costly process involving expert annotation or expensive physical experiments. Active learning addresses this by identifying the most informative data points to label. While standard $\ell_2$ regression (least squares) is a common choice for modeling, $\ell_1$ regression (Least Absolute Deviation) is often preferred in practice due to its inherent robustness against outliers and heavy-tailed noise. This paper provides a near-optimal algorithm for active $\ell_1$ regression, demonstrating that a highly accurate model can be trained using only a tiny, carefully selected fraction of the dataset.

The Lewis Weight Sampling Strategy

The proposed method utilizes a "sampling-and-reweighting" strategy based on $\ell_1$ Lewis weights. Lewis weights serve as a generalization of the leverage scores used in $\ell_2$ regression, providing a measure of the "influence" or importance of each row in a matrix relative to the $\ell_1$ norm.

The algorithm follows a three-step process:

  1. Weight Calculation: Calculate the $\ell_1$ Lewis weights for the unlabeled data matrix $X$.
  2. Subsampling: Sample $m$ rows with probability proportional to these weights.
  3. Empirical Risk Minimization (ERM): Query the labels for the selected $m$ rows and find the vector $\hat{\beta}$ that minimizes the weighted $\ell_1$ error on this small sample.

Theoretical Insights

A primary challenge in active $\ell_1$ regression is the presence of label outliers. Since the algorithm must choose which rows to label before seeing the labels themselves, it risks missing significant outliers. However, the authors identify an "outlier cancellation" effect: while sampling might miss a massive outlier in the labels, that outlier typically affects the error of all candidate models $\beta$ in a similar fashion. Consequently, the relative ranking of different models remains stable, allowing the algorithm to identify a near-optimal $\beta$ even without exhaustive label information.

Furthermore, this work improves upon previous active learning research by providing high-probability guarantees ($1-\delta$). While previous $\ell_2$ methods often required a linear dependence on $1/\delta$ to achieve high-probability success with a single ERM, this approach demonstrates an exponentially better logarithmic dependence on the failure probability.

Key Results and Complexity

The paper establishes tight bounds for the sample complexity of $\ell_1$ regression:

  • Upper Bound: The authors prove that $m = O\left(\frac{d}{\epsilon^2} \log \frac{d}{\epsilon\delta}\right)$ samples are sufficient to find a solution $\hat{\beta}$ within a $(1+\epsilon)$ factor of the true optimal error.
  • Lower Bound: They provide a matching lower bound of $\Omega\left(\frac{d}{\epsilon^2} + (d + \frac{1}{\epsilon^2}) \log \frac{1}{\delta}\right)$, confirming the near-optimality of the Lewis weight sampling approach.

Notably, the algorithm is non-adaptive—it selects all rows to be labeled simultaneously before observing any label values—yet it performs as well as the best possible adaptive algorithms.

Conclusion and Future Work

This research provides a robust theoretical foundation for active $\ell_1$ regression using Lewis weights. While the sample complexity is nearly optimal, the computational cost of calculating Lewis weights for extremely large matrices $X$ remains a practical consideration. Future research may focus on developing faster approximation heuristics for these weights and extending these high-probability guarantees to the broader range of $p$-norms.

Summary updated

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$ factor of optimal. We show that sampling from $X$ according to its Lewis weights and outputting the empirical minimizer succeeds with probability $1-\delta$ for $m > O(\frac{1}{\varepsilon^2} d \log \frac{d}{\varepsilon \delta})$. This is analogous to the performance of sampling according to leverage scores for $\ell_2$ regression, but with exponentially better dependence on $\delta$. We also give a corresponding lower bound of $\Omega(\frac{d}{\varepsilon^2} + (d + \frac{1}{\varepsilon^2}) \log\frac{1}{\delta})$.
BibTeX
@inproceedings{parulekar2021l,
  author = {Aditya Parulekar and Advait Parulekar and Eric Price},
  title = {{L1 Regression with Lewis Weights Subsampling}},
  booktitle = {APPROX-RANDOM},
  year = {2021},
  url = {https://openreview.net/forum?id=YYtnBWTFYu},
}
Figure