Active Regression via Linear-Sample Sparsification

Understand

We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and continuous sparse Fourier transforms.

• In the active linear regression problem, one would like to estimate the least squares solution $\beta^*$ minimizing $\|X\beta - y\|_2$ given the entire unlabeled dataset $X \in \mathbb{R}^{n \times d}$ but only observing a small number of labels $y_i$.
• We show that $O(d)$ labels suffice to find a constant factor approximation $\tilde{\beta}$: \[ \mathbb{E}[\|X\tilde{\beta} - y\|_2^2] \leq 2 \mathbb{E}[\|X \beta^* - y\|_2^2].
• \] This improves on the best previous result of $O(d \log d)$ from leverage score sampling.