# Active Learning Polynomial Threshold Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 24 Jan 2022.

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

- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Approximate Correlation Clustering Using Same-Cluster Queries](https://mlsanity.com/paper/1712.06865/) (2017)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Generalized comparison trees for point-location problems](https://mlsanity.com/paper/1804.08237/) (2018)
- [Active Learning a Convex Body in Low Dimensions](https://mlsanity.com/paper/1903.03693/) (2019)
- [Solving k-SUM using few linear queries](https://mlsanity.com/paper/1512.06678/) (2015)

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

- [Active Learning with Label Comparisons](https://mlsanity.com/paper/2204.04670/) (2022)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [A Reverse Causal Framework to Mitigate Spurious Correlations for Debiasing Scene Graph Generation](https://mlsanity.com/paper/2505.23451/) (2025)

## Abstract (arXiv)

We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access to the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-d univariate PTFs in tildeO(d3log(1/varepsilonδ)) queries. We also provide near-optimal algorithms and analyses for active learning PTFs in several average case settings. Finally, we prove that access to derivatives is insufficient for active learning multivariate PTFs, even those of just two variables.