The Power of Comparisons for Actively Learning Linear Classifiers

Max Hopkins, Daniel M. Kane, Shachar Lovett

Introduction

Active learning represents a paradigm shift in machine learning, where the learner adaptively selects which data points to have labeled by an expert, rather than passively receiving a random dataset. The theoretical promise of active learning is an exponential reduction in sample complexity compared to passive learning. However, for one of the most fundamental classes of models—linear separators (hyperplanes)—this promise often remains unfulfilled in high-dimensional spaces. Specifically, when the separator is non-homogeneous (does not pass through the origin), standard label queries fail to provide significant speedups over random sampling.

This research explores a transformative approach: augmenting the learner's toolkit with comparison queries. By asking an oracle which of two points is further from the decision boundary, rather than just asking for a binary label, we can bypass traditional complexity bottlenecks and achieve exponential improvements in both the Probably Approximately Correct (PAC) and the ultra-strict Reliable and Probably Useful (RPU) learning models.

The Challenge: Non-Homogeneity and the RPU Model

In high-dimensional linear classification, the difficulty often stems from the "offset" or bias term of the hyperplane. In the standard PAC model, if the hyperplane is non-homogeneous, the number of labels required to reach an error $\epsilon$ typically scales as $\Omega(1/\epsilon)$, matching the lower bound of passive learning.

The situation is even more dire in the Reliable and Probably Useful (RPU) model. In this setting, the learner is strictly forbidden from making mistakes; it must either output the correct label or admit "I don't know." Historically, RPU learning for linear separators was considered intractably expensive because its sample complexity was tied to the number of vertices in a random polytope, a value that grows exponentially with the dimension $d$.

Methodology: Harnessing Comparison Queries

The core innovation of this work is the formalization and analysis of comparison queries. For a linear classifier defined by $h(x) = \langle v, x \rangle + b$, a standard label query returns $\text{sgn}(h(x))$. In contrast, a comparison query returns $\text{sgn}(h(x) - h(x'))$, effectively indicating which point is "more positive."

Key Innovations

  1. Homogenization through Differences: Mathematically, a comparison between $x$ and $x'$ is equivalent to asking for the label of the difference vector $x - x'$ on a version of the hyperplane that passes through the origin. This allows the algorithm to decouple the search for the separator's direction ($v$) from the search for its offset ($b$).
  2. Average Inference Dimension: The authors introduce a new complexity measure that extends the "inference dimension" framework. This measure quantifies the probability that a random sample can "infer" the labels of other points in the distribution without additional queries, providing a tighter bound on active learning performance.
  3. Hybrid Algorithmic Strategies: The paper proposes algorithms that combine traditional active learning (like the Balcan-Long algorithm) with "noisy thresholding" techniques. These hybrid methods use comparisons to pinpoint the hyperplane's offset with high precision.

Theoretical Results: Breaking Complexity Barriers

The introduction of comparison queries leads to dramatic improvements in query complexity across different learning regimes.

PAC Learning Improvements

In the PAC setting, particularly under log-concave distributions, the use of comparison queries reduces the query complexity from the passive/label-only regime of $\Omega(1/\epsilon)$ to approximately $\tilde{O}(d \log(1/\epsilon))$. This represents an exponential speedup relative to the error parameter $\epsilon$.

Query complexity comparisons for the PAC learning model across different query types and settings.

RPU Learning Tractability

Perhaps the most striking result is in the RPU model. By utilizing comparison queries, the learner can gain enough geometric information about the distribution to bypass the exponential bottleneck. The complexity shifts from being exponential in dimension $d$ to being polynomial in $d$ and logarithmic in $1/\epsilon$, making "no-mistakes" learning feasible for the first time in high dimensions.

Query complexity comparisons for the RPU learning model, highlighting the shift from exponential to polynomial complexity in dimension.

Conclusion and Future Directions

This research demonstrates that the type of question asked is just as important as the strategy for asking it. Comparison queries provide a powerful geometric lever that "supercharges" active learning for linear classifiers. While these results are theoretically robust for log-concave and s-concave distributions, several avenues for future work remain.

One primary challenge is the "Perfect Oracle" assumption; real-world human comparisons are often noisy or inconsistent, requiring more resilient algorithms. Additionally, extending these results to the "agnostic" setting—where data may not be perfectly linearly separable—remains a significant open problem. Nevertheless, this work provides a new foundation for efficient, reliable machine learning in complex, high-dimensional environments.

Summary updated

BibTeX
@inproceedings{hopkins2020power,
  author = {Max Hopkins and Daniel M. Kane and Shachar Lovett},
  title = {{The Power of Comparisons for Actively Learning Linear Classifiers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure