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
- 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$).
- 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.
- 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$.
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.
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