# Point Location and Active Learning: Learning Halfspaces Almost Optimally

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

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

- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [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)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)
- [Do PAC-Learners Learn the Marginal Distribution?](https://mlsanity.com/paper/2302.06285/) (2023)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Actively Learning Halfspaces without Synthetic Data](https://mlsanity.com/paper/2509.20848/) (2025)
- [On the Sample Complexity of Active Learning with Membership Queries](https://mlsanity.com/paper/2609.27241/) (2026)
- [Optimal Quantum-Classical Separations for Exact Learning](https://mlsanity.com/paper/2609.38073/) (2026)

## Abstract (arXiv)

Given a finite set X subset ℝd and a binary linear classifier c: ℝd → 0,1, how many queries of the form c(x) are required to learn the label of every point in X? Known as textitpoint location, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth tildeO(dlog(|X|)), improving on the previous best of tildeO(d2log(|X|)) from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, we prove a novel characterization of Barthe's Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that X may be transformed into approximate isotropic position if and only if there exists no k-dimensional subspace with more than a k/d-fraction of X, and provide a similar characterization for exact isotropic position.