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?
Categories: cs.LG cs.DS
