Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So · 2025
Read Actively Learning Halfspaces without Synthetic Data by Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20848.txt.
Introduction
Learning which side of a boundary each point lies on can be done with surprisingly few questions, if you may invent your own test points. Hadley Black and four co-authors remove that luxury in a 2025 paper published in COLT 2026. The task is actively learning halfspaces without synthetic data.
A classic result needs only about d log n queries when arbitrary points may be queried. Without synthesis, an older lower bound says learning every label could take as many queries as there are points. The authors design algorithms that work within the given dataset alone. They use structural assumptions to get around the worst case. The work matters wherever queries must be real examples, such as labeled medical or survey data.
Catalog record
| CREATOR | Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20848
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Actively Learning Halfspaces without Synthetic Data Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So Abstract In the classic point location problem, one is given an arbitrary dataset X ⊂ ℝ d X\subset\mathbb{R}^{d} of n n points with query access to an unknown halfspace f : ℝ d → { 0 , 1 } f\colon\mathbb{R}^{d}\to\{0,1\} , and the goal is to learn the label of every point in X X . This problem is extremely well-studied and a nearly-optimal O ~ ( d log n ) \smash{\widetilde{O}(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 X (point synthesis), and in fact without this power there is an Ω ( n ) \Omega(n) query lower bound due to Dasgupta (NeurIPS 2004). Nonetheless, query access to arbitrary synthesized data points is unrealistic in many contexts. Our objective in this work is to design efficient algorithms for learning halfspaces without point synthesis . To circumvent the Ω ( n ) \Omega(n) lower bound, we consider learning halfspaces whose normal vectors come from a known set of size D D , and show tight bounds of Θ ( D + log n ) \Theta(D+\log n) . As a corollary, we obtain an optimal O ( d + log n ) O(d+\log n) query deterministic learner for the fundamental class of decision stumps (depth-one decision trees, or axis-aligned halfspaces), closing a previous gap of O ( d log n ) O(d\log n) vs. Ω ( d + log n ) \Omega(d+\log n) left open in the active learning literature. In fact, our algorithm solves the more general problem of learning a Boolean function f f over n n elements which is monotone under at least one of D D provided orderings of these elements. Our technical insight is to exploit the structure in these orderings to essentially 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 / ε ) , 1 / ε ) ⋅ log D ) O(\min(D+\log(1/\varepsilon),1/\varepsilon)\cdot\log D) queries suffice to learn f f within error ε \varepsilon , even in a setting when f f can be adversarially corrupted on a c ε c\varepsilon -fraction of points, for a sufficiently small constant c c . This bound is optimal up to a log D \log D factor, including in the realizable setting. 1 Introduction Halfspaces, or linear threshold functions (LTFs), are one of the most fundamental and well-studied objects in computer science and geometry, with numerous applications in machine learning, optimization, and beyond. The halfspace with normal vector u\in S^{d-1} and threshold t\in\mathbb{R} bisects \mathbb{R}^{d} into two regions, classifying x using the rule \mathbf{1}(\langle u,x\rangle>t) . In this work, we consider the following halfspace learning question. Given a dataset X\subset\mathbb{R}^{d} partitioned into two classes by an unknown halfspace f\colon\mathbb{R}^{d}\to\{0,1\} , we are allowed to adaptively query the label f(x) for any x\in X and our goal is to learn the label of every point (or an all but \varepsilon -fraction of points) in X . If an algorithm is allowed to query points outside of X , then we say it uses point synthesis . With point synthesis, there is an information-theoretic lower bound of \Omega(d\log n) queries and there has been extensive work on obtaining upper bounds adH 84 ; Mei 93 ; CIO 16 ; KLM 18 ; ES 19 culminating 1 1 1 Many works in this area refer to the dual problem of point location . Here the goal is to determine the cell containing a hidden point in an arrangement of n hyperplanes with the ability to query on which side of any given hyperplane the point lies. This is well-known to be equivalent to the halfspace learning question and so they are often referred to interchangeably in the literature. in a O(d\log^{2}d\log n) query algorithm due to HKLM 20 . However, the ability to synthesize and query arbitrary data points is a strong assumption which may be infeasible in many settings, and our primary motivation in this work is to investigate when and how this can be avoided. The bad news is that, in general, without point synthesis no non-trivial algorithm is possible due to the following simple \Omega(n) lower bound observed by Das 04 which holds even in two dimensions: for a set X of n distinct points on the unit circle, it is straightforward to design a family of halfspaces \{f_{x}\colon x\in X\} such that f_{x} uniquely assigns f_{x}(x)=1 among all points in X , and thus one must query every point in order to learn every label 2 2 2 Note that this argument holds for any choice of n distinct points on the unit circle. For instance, this demonstrates an \Omega(n) lower bound even for the class of halfspaces whose normal vector comes from an arbitrarily narrow cone. . Learning halfspaces optimally in bounded directions. The above lower bound comes from the fact that there are an unbounded number of directions the halfspace can be in, and each direction can be used to separate a single point in X from the rest. Thus, to circumvent this hardness without weakening the assumption of a worst-case point set, it is necessary to bound the number of directions parameterizing the halfspace. It is not too hard to see that if D\leq n directions are allowed, then the above argument gives an \Omega(D) lower bound and \Omega(\log n) queries are needed (to determine the threshold) even in one dimension, leading to an \Omega(D+\log n) lower bound. On the other hand it is not too challenging to design an algorithm using O(D\log n) queries by projecting X along each allowed direction, and performing a binary search independently using the ordering on X induced by each projection. This algorithm simply exploits the fact that the labels are monotone along the correct direction. In fact, even for the simple special case of axis-aligned halfspaces (depth-one decision trees) in \mathbb{R}^{d} , there is a gap of O(d\log n) vs. \Omega(d+\log n) that exists in the active learning literature HY 15 . We investigate the core algorithmic question underlying this gap: can we exploit structure beyond monotonicity of the labels to go beyond a naive, independent application of binary search? We give an affirmative answer, designing a new algorithm that achieves the optimal O(D+\log n) query complexity, thus closing this gap. A new "parallel" binary search learning algorithm. In fact, we design an optimal algorithm for the following generalization of the above problem, which we believe may be of general interest: given a set X of size n , query access to a function f\colon X\to\{0,1\} , and D permutations \sigma_{1},\ldots,\sigma_{D}\colon X\to[n] such that f\circ\sigma_{i^{\star}}^{-1}\colon[n]\to\{0,1\} is monotone for some i^{\star}\in[D] , we wish to learn f(X) using few queries 3 3 3 The halfspace