# Active Learning of Classifiers with Label and Seed Queries

arXiv: https://arxiv.org/abs/2209.03996 · HTML: https://mlsanity.com/paper/2209.03996/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 8 Sep 2022.

## Builds on (most cited first, 8 of 8)

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Search Improves Label for Active Learning](https://mlsanity.com/paper/1602.07265/) (2016)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)

## Built on by (most cited first, 2 of 2)

- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)

## Abstract (arXiv)

We study exact active learning of binary and multiclass classifiers with margin. Given an n-point set X subset ℝm, we want to learn any unknown classifier on X whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin γ requires in the worst case Omegabig(1+frac1γbig)(m-1)/2 queries. On the other hand, using the more powerful seed queries (a variant of equivalence queries), the target classifier could be learned in O(m log n) queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time operatornamepoly(n+m) using only O(m2 log n) label queries and Obig(m log fracmγbig) seed queries; the result extends to k-class classifiers at the price of a k!k2 multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs Omegabig(k m log frac1γbig) seed and label queries to learn a k-class classifier with strong convex hull margin γ.