Active Regression via Linear-Sample Sparsification

Abstract

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 }^{\ast }$ minimizing $\Vert X\beta -y{\Vert }_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β - y\|_2^2] \leq 2 \mathbb{E}[\|X β^* - y\|_2^2]. \] This improves on the best previous result of $O(d\log d)$ from leverage score sampling. We also present results for the \emph{inductive} setting, showing when $\tilde{\beta }$ will generalize to fresh samples; these apply to continuous settings such as polynomial regression. Finally, we show how the techniques yield improved results for the non-linear sparse Fourier transform setting.

References in corpus (3)

• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Unbiased estimates for linear regression via volume sampling

Cited by in corpus (9)

• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Unbiased estimators for random design regression
• Online A-Optimal Design and Active Linear Regression
• Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Differentiable Learning Under Triage
• Classification Under Human Assistance
• Robust Model Selection and Nearly-Proper Learning for GMMs
• Regression Under Human Assistance