Active Regression via Linear-Sample Sparsification
Active Regression via Linear-Sample Sparsification
复制标题
DOI：
--
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Xue Chen;Eric Price
中科院分区：
文献类型：
--
作者：
Xue Chen;Eric Price
我们提出了一种改善各种曲线拟合问题的样品复杂性的方法，包括用于线性回归，多项式回归和连续稀疏的傅立叶变换的主动学习。在活动线性回归问题中，人们想估计最小二乘解决方案$ \ beta^*$最小化$ \ | x \ beta -y \ | _2 $给定整个未标记的数据集$ x \ in \ mathbb {r}^ {n \ times d} $，但仅观察少数标签$ y_i $。我们表明，$ o（d）$标签足以找到常数因子近似$ \ tilde {\ beta} $：\ [\ mathbb {e} [\ | x \ tilde {\ beta} - y \ | _2^2 ] \ leq 2 \ mathbb {e} [\ | x \ beta^* - y \ | _2^2]。 \]这改善了从杠杆评分采样中$ O（D \ log D）$的最佳先前结果。我们还提供了\ emph {encuctive}设置的结果，显示$ \ tilde {\ beta} $何时将概括为新样本；这些适用于连续设置，例如多项式回归。最后，我们展示了该技术如何为非线性稀疏傅立叶变换设置产生改进的结果。
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.