Semi-supervised Active Regression

Labelled data often comes at a high cost as it may require recruiting human labelers or running costly experiments. At the same time, in many practical scenarios, one already has access to a partially labelled, potentially biased dataset that can help with the learning task at hand. Motivated by such settings, we formally initiate a study of semi-supervised active learning through the frame of linear regression. In this setting, the learner has access to a dataset X ∈ ℝ(n1+n2) × d which is composed of n1 unlabelled examples that an algorithm can actively query, and n2 examples labelled a-priori. Concretely, denoting the true labels by Y ∈ ℝn1 + n2, the learner's objective is to find widehatβ ∈ ℝd such that, beginequation | X widehatβ - Y |22 ≤ (1 + ε) minβ ∈ ℝd | X β - Y |22 endequation while making as few additional label queries as possible. In order to bound the label queries, we introduce an instance dependent parameter called the reduced rank, denoted by RX, and propose an efficient algorithm with query complexity O(RX/ε). This result directly implies improved upper bounds for two important special cases: (i) active ridge regression, and (ii) active kernel ridge regression, where the reduced-rank equates to the statistical dimension, sdλ and effective dimension, dλ of the problem respectively, where λ ≥ 0 denotes the regularization parameter. For active ridge regression we also prove a matching lower bound of O(sdλ / ε) on the query complexity of any algorithm. This subsumes prior work that only considered the unregularized case, i.e., λ = 0.