Active Regression via Linear-Sample Sparsification
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. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningregressionSimilar Papers 제목 키워드 기반
Joint Model and Data Sparsification via the Marginal Likelihood
Sparse recovery in linear systems underpins applications from signal processing to high-dimensional regression. Sparse Bayesian Learning, grounded in the principle of automatic relevance determination (ARD), offers a pra…
Nearly Linear Row Sampling Algorithm for Quantile Regression
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cu…
quantile regressionregressionApproximation errors of online sparsification criteria
Many machine learning frameworks, such as resource-allocating networks, kernel-based methods, Gaussian processes, and radial-basis-function networks, require a sparsification scheme in order to address the online learnin…
Gaussian ProcessesFeature Selection for Ridge Regression with Provable Guarantees
We introduce single-set spectral sparsification as a deterministic sampling based feature selection technique for regularized least squares classification, which is the classification analogue to ridge regression. The me…
Classificationfeature selectionGeneral ClassificationregressionOver-the-Air Federated Learning with Compressed Sensing: Is Sparsification Necessary?
Over-the-Air (OtA) Federated Learning (FL) refers to an FL system where multiple agents apply OtA computation for transmitting model updates to a common edge server. Two important features of OtA computation, namely line…
compressed sensingFederated Learning