Reduced Label Complexity For Tight _2 Regression

Abstract

Given data XR^n d and labels yR^n the goal is find wR^d to minimize Xw-y^2. We give a polynomial algorithm that, oblivious to y, throws out n/(d+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 (n). Open question: Can label complexity be reduced by (n) with tight (1+d/n)-approximation?

Tasks

Reproductions