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

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 $\mathrm{\parallel }\mathrm{X}\mathbf{w}-\mathbf{y}{\mathrm{\parallel }}^2$. We give a polynomial algorithm that, \emph{oblivious to $\mathbf{y}$}, throws out $n\mathrm{/}(d+\sqrt{n})$ data points and is a $(1+d\mathrm{/}n)$-approximation to optimal in expectation. The motivation is tight approximation with reduced label complexity (number of labels revealed). We reduce label complexity by $\mathrm{\Omega }(\sqrt{n})$. Open question: Can label complexity be reduced by $\mathrm{\Omega }(n)$ with tight $(1+d\mathrm{/}n)$-approximation?