Query Complexity of Learning Axis-Aligned Partitions

Hadley Black; Arya Mazumdar; Barna Saha; Geelon So

cs.DSOct 26, 2026

Query Complexity of Learning Axis-Aligned Partitions

Authors: Hadley Black, Arya Mazumdar, Barna Saha, Geelon So

Organizations: Baruch College, CUNY. · UC San Diego. · ETH Zürich.

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.

Figures & tables

Panel of Figure 1 — Figure 1: Axis-aligned partitions induced by (a) general boxes, (b) disjoint boxes, and (c) the leaves of a decision tree. These classes form a strictly descending chain: (a) is a box partition with two labels that cannot be induced by any disjoint box partition, and (b) is a disjoint box partition with four labels that cannot be induced by any decision tree.

Partition class	Regime	Bound	Result
Boxes	all	$\Theta\left(kd\log\frac{n}{kd}\right)$	Theorem 1.1
Disjoint boxes	$k\geq 2^{d}$	$\Theta\left(kd\log\frac{n}{kd}\right)\vphantom{\left(\frac{d\log n}{\log d}\right)}$	Theorem 1.2
Disjoint boxes	$k=O(1)$	$O\left(\frac{d\log n}{\log d}\right)$	Theorem 1.2
Decision-tree leaves	$k=O(1)$	$\Theta\left(d+\log n\vphantom{\frac{n}{kd}}\right)$	Theorem 1.3
Decision stumps	$k=2$	$\Theta\left(d+\log n\vphantom{\frac{n}{kd}}\right)$	BLM+ (26)

Table 1: Summary of the query complexity of learning box partitions.

Panel of Figure 2 — Figure 2: A visualization of the construction in Theorem 2.4 . This shows a projection of the 2-box construction onto the $(2j-1,2j)$ th coordinates. It embeds a threshold problem, where the threshold is marked by a white diamond. Many other points project to the black origin.

Panel of Figure 3 — Figure 3: A visualization for the construction in Theorem 3.1 . The left and right subfigures give two point configurations on the edges of the two-dimensional Boolean hypercube. The left configuration fails to embed a set of independent threshold problems, since thresholds induced by overlapping boxes, like the one shown, are immediately ruled out. The point configuration on the right embeds an independent set of threshold problems per edge using a coherent family of total orderings over context vectors. In particular, the horizontal edges are ordered top-to-bottom and the vertical edges are ordered left-to-right.

Query Complexity

Query complexity studies how many oracle or data-access queries algorithms need to learn, decide, estimate, or optimize a problem.

See all 31 papers

Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego
PAC Learning with Query Feedback
Oct 16, 2026Chase Hutton, Adam Melrod, Han ShaoPAC Learning Multiclass Classification
University of Maryland · Harvard University
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicQuery Complexity Clustering
Dartmouth College · The Chinese University of Hong Kong (Shenzhen) · CNRS and Universit´e Paris Cit´e

Sep 25, 2025J/K move · Enter open · S save

Actively Learning Halfspaces without Synthetic Data

Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha+1

Baruch College, CUNY · Aarhus University · University of California, San Diego

Query Complexity Boolean Function Learning Active Learning Halfspace Learning PAC Learning

Open paper AskPDF arXiv

In the classic point location problem, one is given an arbitrary dataset

X \subset \mathbb{R}^d

n

points with query access to an unknown halfspace

f : \mathbb{R}^d \to \{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

\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

(point synthesis), and in fact without this power there is an

Ω(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

Ω(n)

lower bound, we consider learning halfspaces whose normal vectors come from a set of size

D

, and show tight bounds of

Θ(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.

Ω(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) \cdot \log D)

queries suffice to learn

f

within error

\varepsilon

, even in a setting 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.

Abstract

Query Complexity

Explore similar work

Actively Learning Halfspaces without Synthetic Data

PAC Learning with Query Feedback

Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds