# Actively Learning Halfspaces without Synthetic Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 25 Sep 2025.

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

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Generalized comparison trees for point-location problems](https://mlsanity.com/paper/1804.08237/) (2018)
- [Adaptive Exact Learning of Decision Trees from Membership Queries](https://mlsanity.com/paper/1901.07750/) (2019)
- [Solving k-SUM using few linear queries](https://mlsanity.com/paper/1512.06678/) (2015)
- [Optimal Sparse Recovery with Decision Stumps](https://mlsanity.com/paper/2303.04301/) (2023)
- [Learning Boolean Halfspaces with Small Weights from Membership Queries](https://mlsanity.com/paper/1405.1535/) (2014)
- [Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements](https://mlsanity.com/paper/2502.16008/) (2025)

## Abstract (arXiv)

In the classic point location problem, one is given an arbitrary dataset X subset ℝd of n points with query access to an unknown halfspace f : ℝd → 0,1, and the goal is to learn the label of every point in X. This problem is extremely well-studied and a nearly-optimal widetildeO(d log n) query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of X (point synthesis), and in fact without this power there is an Omega(n) query lower bound due to Dasgupta (NeurIPS 2004). In this work our goal is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the Omega(n) lower bound, we consider learning halfspaces whose normal vectors come from a set of size D, and show tight bounds of Theta(D + log n). As a corollary, we obtain an optimal O(d + log n) query deterministic learner for axis-aligned halfspaces, closing a previous gap of O(d log n) vs. Omega(d + log n). In fact, our algorithm solves the more general problem of learning a Boolean function f over n elements which is monotone under at least one of D provided orderings. Our technical insight is to exploit the structure in these orderings to perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that O(min(D + log(1/varepsilon), 1/varepsilon) · log D) queries suffice to learn f within error varepsilon, even in a setting when f can be adversarially corrupted on a cvarepsilon-fraction of points, for a sufficiently small constant c. This bound is optimal up to a log D factor, including in the realizable setting.