Active Regression via Linear-Sample Sparsification

arXiv:1711.10051v4 Announce Type: replace 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 eta^* minimizing |Xeta - y|_2 given the entire unlabeled dataset X in R^{n imes d} but only observing a small number of labels y_i. We show that O(d) labels suffice to find a constant factor approximation ilde{eta}: [ E[|Xilde{eta} - y|_2^2] leq 2 E[|X eta^* - 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 inductive setting, showing when ilde{eta} 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.

Related

• Feature Weighting Improves Pool-Based Sequential Active Learning for Regression
• Bagging Robustly Learns VC Classes with Linear Sample Complexity
• The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

Source: arXiv cs.LG | 2026-08-17