Reduced Label Complexity For Tight $\ell_2$ Regression
Alex Gittens Malik Magdon-Ismail
Given data ${\rm 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{\rm 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 $\Omega(\sqrt{n})$. Open
question: Can label complexity be reduced by $\Omega(n)$ with tight
$(1+d/n)$-approximation?