Query complexity for exact learning of multidimensional labeled boxes
Query Complexity of Learning Axis-Aligned Partitions
Data Structures and AlgorithmsComputational GeometryMachine Learning
Summary
Imagine you have many points in space that belong to different boxes, and you want to figure out which point belongs to which box by asking the smallest number of yes-or-no questions. The authors study how many such questions you must ask to perfectly identify all point labels in different scenarios, including when boxes overlap, are disjoint, or come from structured patterns like decision trees. They find the most efficient known ways to learn these labels exactly and when some algorithms are better than others, depending on the complexity and arrangement of these boxes.
What this means in practice
- •For data engineers: Determine the minimal queries needed to label high-dimensional data points using box-shaped clusters for efficient data classification.
- •For machine learning engineers: Optimize active learning strategies when training classifiers that partition data through axis-aligned regions to reduce labeling costs.
A theory result. No direct application yet.
Authors
Hadley Black, Arya Mazumdar, Barna Saha, Geelon So
Abstract
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $Θ(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $Θ(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.