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:
- 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).
- 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.
- 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