In the classic point location problem, given an arbitrary dataset $X \subset \mathbb{R}^d$ with $n$ points and query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,1\}$, the goal is to learn the label of every point in $X$. This problem is well-studied, with a nearly-optimal query algorithm of $\widetilde{O}(d \log n)$ provided by Hopkins-Kane-Lovett-Mahajan. However, their algorithm allows querying arbitrary points outside of $X$ (point synthesis), and without this capability, there is an $\Omega(n)$ query lower bound established by Dasgupta.
This work aims 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$, demonstrating tight bounds of $\Theta(D + \log n)$. As a corollary, we achieve an optimal $O(d + \log n)$ query deterministic learner for axis-aligned halfspaces, closing the gap between $O(d \log n)$ and $\Omega(d + \log n)$.
Our algorithm also addresses the more general problem of learning a Boolean function $f$ over $n$ elements that is monotone under at least one of $D$ provided orderings. Our key insight is leveraging the structure in these orderings to conduct a parallel binary search instead of processing each ordering sequentially.
Furthermore, we apply our exact learning algorithm to derive nearly optimal algorithms for PAC-learning. We show that $O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)$ queries suffice to learn $f$ within error $\varepsilon$, even when $f$ can be adversarially corrupted on a $c\varepsilon$ fraction of points, for a sufficiently small constant $c$. This bound is optimal up to a $\log D$ factor, including in the realizable setting.
Blogger's Review: The algorithm proposed in this paper efficiently learns halfspaces without synthetic data, bridging the gap between theory and practice. By utilizing a parallel binary search method, the authors overcome the limitations of traditional approaches, demonstrating strong adaptability and broad applicability potential.