Answers are grounded in this paper and cite their sources.
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let X ⊂ Rᵈ 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.
No takes yet. Share an insight, caveat, or question.
Black et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: