L1 Regression with Lewis Weights Subsampling

Aditya Parulekar, Advait Parulekar, Eric Price

TL;DR

When labels are expensive but features are cheap, how many labels do you need to observe to solve $\ell_1$ linear regression? This paper proves that non-adaptively subsampling data points according to their $\ell_1$ Lewis weights requires only $O\left(\frac{d}{\varepsilon^2} \log \frac{d}{\varepsilon\delta}\right)$ queries to achieve a $(1 + \varepsilon)$-approximation with probability $1 - \delta$. The authors also establish a near-matching lower bound of $\Omega\left(\frac{d}{\varepsilon^2} + \left(d + \frac{1}{\varepsilon^2}\right)\log\frac{1}{\delta}\right)$.

What Problem Does This Paper Address?

In many practical machine learning settings, unlabeled feature vectors $X \in \mathbb{R}^{n \times d}$ are abundant and cheap, but obtaining ground-truth labels $y \in \mathbb{R}^n$ is costly (requiring human annotators, wet-lab assays, or expensive simulations). Active regression seeks to select a small subset of $m \ll n$ rows to query such that the empirical risk minimizer $\hat{\beta}$ achieves:

$$\|X\hat{\beta} - y\|_p \le (1 + \varepsilon) \min_{\beta} \|X\beta - y\|_p$$

While active $\ell_2$ regression (least squares) is well-understood—solved using leverage score sampling—least absolute deviation ($\ell_1$ regression) is often preferred in practice due to its robustness against heavy-tailed noise and outliers. However, existing active regression guarantees for $\ell_1$ were far less mature, lacking tight sample complexities with high-probability guarantees.

Methods

The paper analyzes a non-adaptive sampling-and-reweighting approach:

  1. Lewis Weight Sampling: Compute the $\ell_1$ Lewis weights $\{w_i\}_{i=1}^n$ of the matrix $X$ (the $\ell_1$ analogue to $\ell_2$ leverage scores, representing the intrinsic importance of each row to the column space).
  2. Subsampling Sketch ($S$): Sample $m$ rows independently with probabilities $p_i \propto w_i$, reweighting queried entries by $1/p_i$ so the estimator is unbiased.
  3. Empirical Risk Minimization: Query only the labels corresponding to the sampled rows, $Sy$, and solve the sketched regression problem: $$\hat{\beta} = \arg\min_{\beta} \|SX\beta - Sy\|_1$$

Proof Innovation

In $\ell_2$ active regression, analyzing subsampling relies heavily on the closed-form normal equations and the fact that the residual vector $X\beta^* - y$ is orthogonal to the column space of $X$. In $\ell_1$ regression, neither property holds, and multiple distinct minimizers can exist.

To overcome this, the authors show that while the sketch $S$ does not preserve the absolute error $\|X\beta - y\|_1$ (because unseen label outliers can blow up the total loss), it does preserve the relative excess risk: $$\big(\|SX\beta^* - Sy\|_1 - \|SX\beta - Sy\|_1\big) \approx \big(\|X\beta^* - y\|_1 - \|X\beta - y\|_1\big)$$ By combining Rademacher symmetrization and a contraction principle (Ledoux–Talagrand), the unknown label vector $y$ cancels out completely, reducing the problem to bounding deviations over the subspace $X(\beta^* - \beta)$.

Datasets

Not discussed in the paper. The work is purely theoretical; experimental evaluations on real or synthetic datasets were not conducted. Lower bounds are established using information-theoretic constructions over Bernoulli hard instances.

Key Insights and Ideas

  • Outlier Cancellation via Differences: Sampling cannot estimate the total $\ell_1$ loss without seeing all entries (a single massive outlier in an unqueried row breaks the estimate). However, because that outlier affects $\|X\beta - y\|_1$ and $\|X\beta^* - y\|_1$ almost identically, the difference concentrates around its expectation just as well as an $\ell_1$ subspace embedding.
  • Exponentially Better Confidence than $\ell_2$ ERM: In $\ell_2$ active regression, standard empirical risk minimizers typically only succeed in expectation, whereas this $\ell_1$ Lewis weight guarantee scales logarithmically with $1/\delta$, providing exponential tail bounds.
  • Tight Information-Theoretic Lower Bounds: By decomposing the difficulty of the problem into three distinct regimes—learning coordinate signs ($\Omega(d/\varepsilon^2)$), distinguishing biased coins ($\Omega(\varepsilon^{-2} \log(1/\delta))$), and searching for a hidden non-zero index ($\Omega(d \log(1/\delta))$)—the authors construct instances showing that no algorithm (even adaptive ones) can beat the sum of these costs.

Key Results

  • Upper Bound: Sampling $m = O\left(\frac{d}{\varepsilon^2} \log \frac{d}{\varepsilon\delta}\right)$ rows according to $\ell_1$ Lewis weights guarantees a $(1 + \varepsilon)$-approximate solution with probability at least $1 - \delta$. For constant error probability $\delta = \Theta(1)$, $m = O\left(\frac{1}{\varepsilon^2} d \log d\right)$ suffices.
  • Constant-Factor Baseline: The authors show that a simple constant-factor approximation (e.g., a 41-approximation with probability $0.81$) requires only $O(d \log d)$ queries.
  • Lower Bound: Any active algorithm achieving a $(1+\varepsilon)$-approximation with failure probability $\delta$ must query at least: $$\Omega\left(d \log \frac{1}{\delta} + \frac{d}{\varepsilon^2} + \frac{1}{\varepsilon^2} \log \frac{1}{\delta}\right) \text{ rows.}$$

Limitations and Future Work

  • The Logarithmic Gap: A multiplicative gap remains between the upper bound (which multiplies $d/\varepsilon^2$ by $\log(d/\varepsilon\delta)$) and the lower bound (which has these terms additively). Determining whether the multiplicative $\log d$ factor is strictly necessary remains an open question.
  • Adaptivity: The proposed algorithm is completely non-adaptive (all queries are chosen up front). While the lower bound shows adaptivity cannot circumvent the core sample complexity, it is unknown whether adaptive query schemes could shave off lower-order logarithmic terms.

Summary updated

Abstract

We consider the problem of finding an approximate solution to 𝓁₁ 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/(ε²) d log d/(ε δ)). This is analogous to the performance of sampling according to leverage scores for 𝓁₂ regression, but with exponentially better dependence on δ. We also give a corresponding lower bound of Ω(d/(ε²) + (d + 1/(ε²)) log 1/(δ)).
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},
}

Loading related content...

Figure