Semi-supervised Active Linear Regression

Nived Rajaraman, Fnu Devvrit, Pranjal AwasthiNeurIPS 2022 · OpenReview

Acquiring labeled data is often the most expensive bottleneck in machine learning, requiring human expertise or costly experiments. However, in many practical scenarios, researchers do not start entirely from scratch. They often possess a small, potentially biased "starter" labeled dataset alongside a massive pool of unlabeled data.

Standard Active Learning typically assumes the learner starts with no labels and must query them iteratively. Conversely, Semi-supervised Learning usually assumes the unlabeled data is passively available to help regularize the model. This paper bridges these two paradigms by formally introducing Semi-supervised Active Regression (SSAR). The goal is to find a linear model that minimizes the squared loss over the entire dataset (both labeled and unlabeled) while querying as few new labels from the unlabeled pool as possible.

The Challenge of Existing Data Geometry

In SSAR, the learner has access to a dataset $X$ composed of $n_{\text{un}}$ unlabeled examples and $n_{\text{lab}}$ examples labeled a priori. The objective is to find a weight vector $\widehat{\beta}$ such that the squared loss is within a $(1 + \epsilon)$ factor of the optimal loss, using the minimum number of queries.

The core challenge is determining exactly how many queries are "enough" based on the specific geometry of the data you already have. If your existing labeled data already "covers" certain directions in the feature space, you shouldn't need to waste queries on points in those same directions.

The ASURA Algorithm and Reduced Rank ($R_X$)

To solve this, the authors introduce ASURA (Active semi-SUpervised Regression Algorithm). The machinery behind ASURA relies on a technique called spectral sparsification.

The foundational contribution of this work is the introduction of a new instance-dependent metric called the reduced rank ($R_X$). $R_X$ captures the "relative importance" of the unlabeled points given the points we already have labels for. Mathematically, it is defined as the trace of the unlabeled data's covariance matrix normalized by the total covariance:

$$R_X = \text{Tr}((X_{un}^T X_{un} + X_{lab}^T X_{lab})^{-1} X_{un}^T X_{un})$$

This metric perfectly encapsulates the semi-supervised active learning problem: if the existing labeled data ($X_{lab}$) is highly informative and spans the feature space well, $R_X$ is small. If $X_{lab}$ is empty (standard active learning), $R_X$ approaches the full dimension $d$.

ASURA uses a variant of the Randomized BSS (Batson-Spielman-Srivastava) algorithm to perform well-balanced sampling. Rather than picking points at random, it iteratively selects queries such that the resulting weighted subset is a strong representative of the full dataset's spectral properties. Furthermore, ASURA employs an aggressive stopping criterion, terminating queries once it satisfies the requirements dictated by the reduced rank $R_X$.

Key Results: Optimal Query Complexity

The theoretical guarantees provided by ASURA are instance-wise optimal. The algorithm queries at most $O(R_X/\epsilon)$ labels to achieve a $(1+\epsilon)$ approximation of the optimal loss with constant probability.

Summary of upper and lower bounds for Semi-Supervised Active Regression (SSAR).

Crucially, for the distributional version of the problem (where labels contain Gaussian noise), the authors prove a matching lower bound of $\Omega(R_X/\epsilon)$. This demonstrates that no algorithm can fundamentally achieve better query complexity than ASURA for a given data geometry.

Unifying Ridge and Kernel Ridge Regression

A powerful insight of this paper is that active ridge regression and active kernel ridge regression are simply special cases of the SSAR framework. In ridge regression, the "labeled data" can be viewed mathematically as a scaled identity matrix representing the prior.

By applying ASURA to these settings, the authors resolve long-standing query complexity bounds:

  • Active Ridge Regression: The optimal query complexity is shown to be exactly proportional to the statistical dimension, $O(\text{sd}_\lambda/\epsilon)$.
  • Active Kernel Ridge Regression: Previous state-of-the-art methods suffered from a logarithmic dependence on the total number of data points ($n$). ASURA removes this $\log(n)$ factor, proving that the complexity depends only on the effective dimension ($d_\lambda$) and the error tolerance, achieving $O(d_\lambda/\epsilon)$.
Summary of upper and lower bounds for Active Ridge and Kernel Ridge Regression.

Limitations and Future Directions

While this paper provides a robust theoretical foundation and optimal query complexity bounds, it is primarily a theoretical work. The authors note a few limitations that pave the way for future research:

  1. Computational Cost: While the query complexity (number of human labels needed) is optimal, the computational complexity of ASURA involves Singular Value Decompositions (SVDs) and matrix inversions. Designing "near-linear time" versions of these algorithms for massive datasets remains an open challenge.
  2. Beyond Squared Loss: The current theoretical guarantees are strictly limited to squared loss (linear regression). Extending these instance-optimal bounds to other loss functions, such as logistic regression or general Generalized Linear Models (GLMs), represents a significant theoretical hurdle.
  3. Agnostic Lower Bounds: While a matching lower bound is provided for the distributional (noisy) case, establishing a general lower bound for the purely agnostic (arbitrary labels) case remains an open question.

Summary updated

Abstract

Labeled 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 labeled, 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. Here, the learner has access to a dataset $X \in \mathbb{R}^{(n_{\text{un}}+n_{\text{lab}}) \times d}$ composed of $n_{\text{un}}$ unlabeled examples that a learner can actively query, and $n_{\text{lab}}$ examples labeled a priori. Denoting the true labels by $Y \in \mathbb{R}^{n_{\text{un}} + n_{\text{lab}}}$, the learner's objective is to find $\widehat{\beta} \in \mathbb{R}^d$ such that, $$ \| X \widehat{\beta} - Y \|_2^2 \le (1 + \epsilon) \min_{\beta \in \mathbb{R}^d} \| X \beta - Y \|_2^2 $$ while querying the labels of as few unlabeled points as possible. In this paper, we introduce an instance dependent parameter called the reduced rank, denoted $\text{R}_X$, and propose an efficient algorithm with query complexity $O(\text{R}_X/\epsilon)$. 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'', $\textsf{sd}_\lambda$ and ``effective dimension'', $d_\lambda$ of the problem respectively, where $\lambda \ge 0$ denotes the regularization parameter. Finally, we introduce a distributional version of the problem as a special case of the agnostic formulation we consider earlier; here, for every $X$, we prove a matching instance-wise lower bound of $\Omega (\text{R}_X / \epsilon)$ on the query complexity of any algorithm.
BibTeX
@inproceedings{rajaraman2022semi,
  author = {Nived Rajaraman and Fnu Devvrit and Pranjal Awasthi},
  title = {{Semi-supervised Active Linear Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=i-UdJ6fWUFc},
}
Figure