Reduced Label Complexity For Tight ${\ell }_2$ Regression

Abstract

Given data $\mathrm{X}\in {\mathbb{R}}^{n\times d}$ and labels $\mathbf{y}\in {\mathbb{R}}^n$ the goal is find $\mathbf{w}\in {\mathbb{R}}^d$ to minimize $\Vert \mathrm{X}\mathbf{w}-\mathbf{y}{\Vert }^2$. We give a polynomial algorithm that, \emph{oblivious to $\mathbf{y}$}, throws out $n/(d+\sqrt{n})$ data points and is a $(1+d/n)$-approximation to optimal in expectation. The motivation is tight approximation with reduced label complexity (number of labels revealed). We reduce label complexity by $\hat{I}\text{c◯}(\sqrt{n})$. Open question: Can label complexity be reduced by $\hat{I}\text{c◯}(n)$ with tight $(1+d/n)$-approximation?