WorksComputer Science
Query Complexity of Learning Axis-Aligned Partitions
Abstract
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let be a set of points, labeled by a collection of boxes: the label of each point in is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in 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 . When the boxes are disjoint, we examine two regimes. In the large- regime, CAL remains minimax-optimal. For the constant- regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a 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 that is additive in and , generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.
Introduction
This work establishes the query complexity of learning high-dimensional boxes under the setting of pool-based active learning with label queries [2 Das04, Set09]. Let be any finite set of points and be a set of labels. The goal of a learner is to recover an unknown labeling when provided access to a label oracle: upon being given a query , the oracle supplies the label . The basic problem is to understand how many queries the learner needs before being able to deduce the label of every point in .
We study the family of axis-aligned partitions, or more plainly, box partitions. A labeling is a box partition if it is induced by boxes: for each label , there is a box such that the points in the th class are given by . There are so that
A simple example of box partitions is the family of axis-aligned halfspaces (decision stumps). These are box partitions that split in two, based on which side of an axis-aligned halfspace points fall; the splitting halfspace can also be seen as the face along which two adjacent, unbounded boxes meet. Another example is the family of box partitions induced by the leaves of decision trees, which generalize decision stumps via recursion. Decision trees assign two instances the same label if and only if they are contained in the same leaf of the tree. Beyond decision stumps and decision trees, this work considers a hierarchy of box partitions (see Figure 1). With increasing structure, they are:

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.
General box partitions: These constitute the broadest class of axis-aligned partitions. The only requirement is that the induced labeling is well-defined, meaning that each point in is contained in precisely one of the underlying boxes. The boxes themselves may overlap in .
Disjoint box partitions: The boxes must be disjoint, for distinct .
Decision trees: The boxes are disjoint and admit a decision-tree structure. This means that there is a binary tree where each leaf is identified with a label in . For each internal node in the binary tree, there is a dimension and a threshold that splits its left and right descendants: a descendant is to the left if and only if .
Main Results
We study the query complexity of learning axis-aligned partitions through a series of classic active learning algorithms. Besides giving specialized upper bounds, the main contribution of this work establishes lower bounds across these settings. This illuminates the way in which different sources of geometric structure affect the hardness of learning, and how different algorithms can leverage it.
The first result is Theorem 1.1 for learning general class of box partitions. It establishes a tight query complexity of , where is the number of points, is the number of labels, and is the number of dimensions. Formally:
Theorem 1.1 (General Boxes). Let . Consider the problem of learning a general -box partition over a worst-case set of points in -dimensions.
The expected query complexity of this problem is .
For any , the -round query complexity is .
In particular, there is an algorithm achieving the optimal query complexity with a round budget. Our lower bounds hold even against randomized algorithms.
A canonical active learning algorithm achieves minimax-optimality: it is enough to run CAL, which is named after the authors who introduced it in [CAL94]. This algorithm sequentially chooses a random point whose label the learner cannot determine yet, and asks the oracle for the ground-truth label. Furthermore, batched-CAL is minimax-optimal even in settings where the learner is limited to rounds of interactions with the oracle. We prove this theorem in § 2.
The upper bounds achieved by CAL and its round-aware variant certainly apply to any class of box partitions, including disjoint box partitions and decision trees. The same is not necessarily true for the lower bound. If there is additional structure, can it be leveraged to speed up learning?
The next result Theorem 1.2 focuses on disjoint box partitions in two main regimes. In the large- regime with boxes, CAL remains minimax-optimal: the query complexity is lower bounded by , which matches the upper bound for general box partitions. On the other hand, in the small- regime where the number of boxes is constant, the upper bound for disjoint boxes can be a -factor smaller than the lower bound for general boxes:
Theorem 1.2 (Disjoint Boxes). Let . There is a randomized algorithm that learns any disjoint -box partition over a worst-case set of points in -dimensions using in expectation
queries.
When , the upper bound is matched with a lower bound of queries.
We prove this theorem in § 3. In the small- regime, the algorithm that achieves the faster rate is another classic active learning algorithm called the Halving algorithm, or rather, a slightly more optimized version of it found in [Mos82] and [Heg95]. Let’s call it Halving++. While CAL is essentially content to query a random point with an ambiguous label, Halving++ seeks particularly informative points to query. One combinatorial quantity that controls the query complexity of Halving++ is the extended teaching dimension [Heg95]. We prove a query complexity upper bound by way of bounding the extended teaching dimension of disjoint boxes. The proofs are in § 3. Compared to general boxes, the faster rate for disjoint boxes cannot only be attributed to the presence of additional structure; the learner also needs to take advantage of it. Section B gives an instance of a disjoint-box problem where CAL provably fails to exploit the structure that Halving++ successfully leverages.
The final result is Theorem 1.3, which considers box partitions induced by the leaves of a decision tree. Importantly, these decision trees are distinct from the more common binary-valued decision trees; the induced labeling here is a multi-class function, where the number of classes is equal to the number of non-empty leaves.6 For constant-sized trees, the query complexity has additive upper and lower bounds of . Thus, there is a further separation between this setting and the general box setting, which has a multiplicative lower bound of . We show:
Theorem 1.3 (Decision Trees). Let and . There is a deterministic algorithm that learns any box-partition induced by the leaves of a -leaf decision tree using at most
If the decision tree is a decision list, then the query complexity is upper bounded by , and it is lower bounded by when .
To achieve this additive upper bound on query complexity, we make use of a ‘parallel binary search’ algorithm, which was introduced by [10]. The parallel binary search algorithm is a minimax-optimal learner for decision stumps. Theorem 1.3 can be viewed as a generalization of that result, establishing the query complexity not just for decision stumps, but for constant-sized decision trees. The lower bound we provide here holds even for decision lists, which are decision trees whose internal nodes form a path graph. The proofs of these results are provided in § 4.
A high-level summary of our main results is given in Table 1. The next section also provides some high-level sketch of the technical ideas in this work.
| Partition class | Regime | Bound | Result |
| Boxes | all | Theorem 1.1 | |
| Disjoint boxes | Theorem 1.2 | ||
| Disjoint boxes | Theorem 1.2 | ||
| Decision-tree leaves | Theorem 1.3 | ||
| Decision stumps | [10] |
Table 1. Summary of the query complexity of learning box partitions.
Technical Overview
General box partitions. Theorem 1.1 provides a query complexity upper bound for CAL and a round-constrained variant. It also gives a matching lower bound construction. The upper bounds rely on a simple observation that applies to any box partition. Suppose that a learner has seen a set of points with the same label . Then, every point in contained in the bounding box of must also be labeled , and CAL will not query these points. The upper bounds follow from determining the rate that these labeled bounding boxes grow before they fully cover .
The lower bounds throughout this work are built on the fact that learning a monotone function from label queries requires queries. The constructions find ways to embed many independent copies of these one-dimensional threshold learning problems into the various box learning settings. For general box partitions, we embed threshold problems, each consisting of points. Thus, we obtain an lower bound.
These lower bounds are rather non-trivial to find. Consider even boxes. It is clear how one threshold learning problem over points can be embedded into a 2-box learning problem: if we arrange the points in a line, then each threshold can be induced by a pair of adjacent boxes. But this construction only gives an lower bound, not the stronger . The problem is that only a single face of each of the boxes contributes to hardness. Intuitively, naive construction under-utilizes the set of faces available from each box. The question is how to place the points so that all faces of the two boxes can interact with each other to admit independent threshold learning problems. The construction we give achieves this using overlapping boxes. It turns out that to extract this hardness for general , it is necessary that boxes are able to overlap.
Disjoint box partitions. Theorem 1.2 consists of two parts. It shows a lower bound for disjoint boxes in the large- regime that continues to match the general-box upper bound. It also shows that in the small- regime with disjoint boxes, it is possible to beat the general-box lower bound.
The lower bound in the large- regime is a construction that embeds independent threshold learning problems into a disjoint box learning problem. When , we will embed a threshold learning problem onto every edge of a Boolean hypercube (note there are edges). To do this, place points along each edge of the hypercube, and extend a box out of each vertex onto its incident edges; see Figure 3. The problem is that the threshold learning problems induced this way are not automatically independent, as the boxes may intersect near the center of the Boolean hypercube. However, we carefully design point configurations that manage to preserve independence, thus obtaining an lower bound.

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.
The second part shows that Halving++ beats the general-box lower bound by a -factor in the constant regime. This follows from an upper bound on the query complexity of Halving++ [Mos82, Heg95]. To specialize the bound, we bound the extended teaching dimension of disjoint-box partitions, as well as the number of such partitions of . Beating the general-box lower bound in certain regimes is possible because disjoint boxes have additional structure: every pair of box can be separated by an axis-aligned halfspace. The labeling induced by disjoint boxes can be specified either through the set of thresholds associated to the faces of the boxes, or through a set of halfspaces that separate every pair of label class. In a sense, CAL learns only by recovering the thresholds. Halving++ can be strictly more label-efficient, and it does so intuitively by leveraging this alternative specification, which is independent of . For constant order , we show that this is ultimately the source of the -factor savings.
Decision trees. In Theorem 1.3 we consider the class of disjoint box partitions that are induced by -leaf decision trees. While the upper bounds from Theorem 1.1 and Theorem 1.2 extend to this setting, we show that the additional structure of decision trees enables improved query bounds, at least when is relatively small. [10] gave a query learner for the class of 2-leaf decision trees (or decision stumps). Intuitively, if we compare 2-box partitions, the gap between the sample complexity for general boxes and for decision stumps comes from the fact that a 2-leaf tree is specified by a single axis-aligned hyperplane. Our lower bound for general boxes shows that one essentially needs to learn all the faces of the two boxes.
More generally, for , when a labeling is induced by a decision tree, we are guaranteed the existence of a single axis-aligned hyperplane that separates the labels into two non-empty sets (see Definition 4.1, and , and this same structure repeats on each side. If this subset is known in advance, then one can apply the decision stump learner to recover . Extending this observation, if the label-splits are provided at each level of the tree, this would yield a query algorithm. This shows that naively guessing every such tree yields a query algorithm (see Remark 4.4). In Theorem 1.3, we reduce the -dependence to with a more careful recursive strategy that avoids brute-force enumeration. At a very high level, we obtain this improvement by certifying correct label-splits at the leaves and propagating this information through recursion. This allows us to make permanent progress without guessing the correct tree all at once.
Open Questions
The aim of our work is to obtain a comprehensive understanding of the query complexity of learning natural axis-aligned partitions over worst-case point-sets. The following gaps remain, which we leave as interesting directions for follow up work, and which we believe will require new insights.
Improved bounds for disjoint boxes in the intermediate- regime. When , we obtain a lower bound, matching our upper bound for general -box partitions. However, when , our bounds are not tight, and our upper bounds in Theorem 1.2 demonstrate a separation from general boxes when is sufficiently small. Therefore, as becomes small, there is a moment where box disjointness supplies more geometric structure that can be exploited by a learner. Obtaining sharper bounds in this regime would require finding new ways to use this geometry, and we believe this is a worthwhile future direction.
Improved bounds for decision trees. Decision trees are an extremely natural specialized class of box partitions to consider. While we obtain bounds that are tight for any constant number of classes, it is not clear what the true dependence on is for this problem. We believe this is a very interesting open question to resolve.
Related Work
There is an extensive line of research in exact query learning and active learning; as an inexhaustive list, see [2 Das04, 4 Set09, 9 HY15], and references therein. This work belongs to a subarea concerned with learning geometric concept classes, in which the label function is induced by fundamental objects like balls, boxes, halfspaces, convex sets, and decision trees [6, 7, 8 GSSS13, 1, 5, 10 SMLG+26].
This work establishes the query complexity of active learning axis-aligned partitions under various structural assumptions, and our main contributions are our lower bound constructions. Our results complement existing work. A prior result for learning general -box partitions is given by [5]. They provide a generic algorithm for multi-class active learning, which uses queries when specialized to boxes. In a more specific two-class setting, [10] establishes that the query complexity for axis-aligned halfspaces is .
This work shows that CAL [CAL94], a standard active learning algorithm, is minimax-optimal for general boxes. The first generic upper bound of the sample complexity of CAL was given by [3], and they also provide a specialized analysis for the 1-dimensional linear threshold. Our upper bound can be seen as a generalization of the analysis for 1-dimensional thresholds: a set of boxes in dimensions can be specified by a set of thresholds. We also show that a variant of the Halving algorithm [Heg95] can exploit additional structure, and that it strictly beats CAL in certain regimes for learning disjoint boxes. The most structured concept class we consider generalizes decision stumps; they are induced by the leaves of decision trees [MDRF20, HKLM21]. For these tree-based partitions, we also give a minimax-optimal learner for constant number of classes.
The lower bounds we prove arise from embedding many independent copies of a threshold learning problem into various box-learning problems. In the round-constrained setting, lower bounds also arise from corresponding bounds for threshold learning provided by [11].
Notation. For any , we let denote the closed interval from to . Given a finite set of points , denote its bounding box by
General Box Partitions
In this section, we prove Theorem 1.1, which considers learning a general box partition: there is a set of potentially-overlapping boxes that induce a partition of
We divide up the results. The upper bound without round constraints is given by Theorem 2.1. The upper bound with round constraints is in Theorem 2.2. The lower bound is given in Theorem 2.4.
Learning General Box Partitions
A standard active learning algorithm CAL [CAL94] achieves the query complexity upper bound. It is an iterative algorithm that maintains a disagreement region. This region is the subset of points of whose labels cannot be deduced yet: it contains a point if there are at least two valid labelings that disagree on how to label , but that are nevertheless consistent with the observed data. Every round, the learner randomly selects a point from this region and asks the oracle for its label. In the case of learning boxes, if is a set of points that have been labeled , then the learner may deduce that every point in the bounding box is also labeled . The disagreement region shrinks over the course of the algorithm, and the learner stops when this region vanishes. The following upper bound is similar in spirit to Theorem 4.1 of [3].
Theorem 2.1. There is a randomized algorithm that learns an arbitrary -box partition in dimensions over points using at most label queries in expectation.
Proof. The algorithm is defined as follows.
Initialize a partial function as for all . For each , let throughout the execution. We will maintain the invariant
Choose a permutation uniformly at random.
For each , let and do the following: (a) If , then continue. (b) If , then query . Set , and also set for all points .
The correctness of the algorithm is clear by inspection. We now analyze the expected number of queries over the randomness of . Whether or not a point with label is queried depends only on the ordering that induces on . Let denoted this restriction of where . Observe that for each , is queried if and only if it is not contained in the bounding box of . Equivalently, is queried if and only if it is a maximal point7 among . Since -dimensional boxes have at most maximal points, and is uniform random among , the probability is queried is at most . Let denote the total number of queries made by the algorithm on permutation , where is the number of queries in . By linearity of expectation,
Applying linearity of expectation over all labels yields
by Jensen’s inequality.
Next we consider an -round variant of CAL. The proof is in Section A.
Theorem 2.2 (-round algorithm). For any , there is an -round randomized algorithm which learns an arbitrary -box partition in -dimensions over points using
queries in expectation. In particular, when , this recovers the optimal query complexity , while improving on the round complexity in Theorem 2.1 by a factor.
Matching Lower Bound
The simplest, nontrivial setting for learning box partitions is when and . Here, the problem is simply to learn a threshold between two classes. In this case, we can of course run binary search, which optimally solves the problem using at most queries. The following result provides a lower bound for the threshold learning problem, with and without round constraints.
Theorem 2.3 (Threshold Learning Lower Bound, Theorem 3 of [11]). Consider exactly learning a monotone function with query access. Suppose that a randomized algorithm solves this problem on every input with success probability at least . Then, there exists such that the expected number of queries made is at least . Moreover, if uses rounds of adaptivity, then there exists such that the expected number of queries made is at least .
To obtain query lower bounds for general , we will show that a set of independent threshold learning problems with points each can be reduced to learning a general -box partition over a set of points of size . We obtain a lower bound for the round-unconstrained setting, and a lower bound of for the -round setting:
Theorem 2.4 (Lower bound for general boxes). Let be even. Let be a natural number. Suppose a randomized algorithm learns any -box partition over points in with success probability . Then, there exists a problem instance such that the expected number of queries made is at least . Moreover, if the algorithm uses rounds of adaptivity, then there exists a problem instance such that the expected number of queries made is at least .
Proof. Let . Let be a collection of independent monotone functions, where ranges over . We construct a reduction from learning these thresholds to learning a -box partition over points as follows.
Let’s start with the case. We drop the index as it now ranges over the singleton . Define the map by
where the th coordinate
We can think of ’s as a collection of affine embeddings of into . Define the set
By construction, the map is bijective. Define the labeling by
This is visualized in Figure 2. We claim the following:
Figure 2. A visualization of the construction in Theorem 2.4. This shows a projection of the 2-box construction onto the th coordinates. It embeds a threshold problem, where the threshold is marked by a white diamond. Many other points project to the black origin.
Claim 2.5. The labeling is a 2-box partition. Moreover, the following hold:
(a) The set of threshold functions ’s can be computed from .
(b) Every query to a box-label oracle can be simulated by a query to one threshold-label oracle.
In particular, this claim shows that any box-learning algorithm that learns with success probability can be converted into an algorithm that learns the original set of thresholds with the same success probability using the same number of queries. By Theorem 2.3, we immediately have that the number of queries that the box-learning algorithm makes to a label oracle is at least
We now prove the claim. The subclaims (a) and (b) are direct, and they are conceptually converses of each other. We can compute from since is equal to . On the other hand, a query to the box-label oracle can be simulated by querying .
Proof that is a 2-box partition. Let be a threshold for , so that
Define the boxes and as follows. Let be the projection onto the th and th components for . Then:
These two boxes are defined so that if and only if . Indeed for all ,
Recall that the -coordinates of is . The second condition is equivalent to , while the third is equivalent to . Thus, is a 2-box partition.
Generalization to . We now make translated copies of the 2-box construction with , so that there are a total of -classes. Define the point set as
where in the th copy, we translate each point by the vector . As before, each point in corresponds to a unique set of indices . Letting denote this bijection, we define similarly, where when . In this way, we obtain an embedding of independent threshold problems and the stated lower bound. ▫
Disjoint Box Partitions
In this section we prove our results for disjoint -box partitions stated in Theorem 1.2. We start by proving our lower bound in § 3.1 for the large- regime, then obtain a separation between disjoint and general boxes in § 3.2 with an improved algorithm for the small- regime.
Matching Lower Bound in the Large- Regime
We prove the following lower bound for learning disjoint -box partitions. In particular, we obtain a query lower bound for fully adaptive, randomized algorithms when , showing that when is sufficiently large, disjointness does not make the learning problem easier.
Theorem 3.1 (Lower bound for disjoint boxes). Let be a power of two and . Define and let be a natural number. Suppose a randomized algorithm learns any disjoint -box partition over points in with success probability . Then, there exists a problem instance such that the expected number of queries made is at least . Moreover, if the algorithm uses rounds of adaptivity, then there exists a problem instance such that the expected number of queries made is at least .
Proof. We first prove the theorem when , and thus . The more general case will follow easily from this setting. For the sake of simplicity, assume that divides . We will construct a set of points and a family of boxes that induce independent threshold learning problems, each on a set of points. The lower bound will then follow by applying Theorem 2.3 across each independent threshold problem.
Our construction is built on the -dimensional hypercube, . Each vertex corresponds to a label induced by a box such that . These boxes are disjoint.
Notation. Given and , we let denote the context vector obtained by removing the -th bit of . For a context vector and coordinate , we use the pair to identify the hypercube edge with context in direction .
The construction. Our objective is to induce an independent threshold learning problem along each edge . For each dimension and context , we define a disjoint family of intervals as follows:
These intervals are of uniform length, . Note that what is currently left undefined is the ordering of the intervals according to their context vectors, . This turns out to be a critical aspect of the construction, which we will discuss and define later.
On each edge , we induce a threshold learning problem on the segment
To do this, we let be a set of uniformly spaced interior points along this segment. Concretely, if , then define
and
We define the full point-set as
A threshold is then chosen somewhere in this interval. Concretely,
is one of possible values. Then, given a threshold profile
the box for label is defined as
The additive term is simply to ensure that the following closed intervals are disjoint:
Note that the union of these boxes indeed cover , regardless of the threshold profile . The crux of the construction is to show that all threshold profiles are realizable while maintaining box disjointness, i.e. for all .
Completing the proof assuming realizability of all threshold profiles. We first note that if the above is possible, then this completes the proof. Learning each threshold on amounts to learning a monotone function on a domain of size . The needed lower bound for learning each threshold is therefore given by Theorem 2.3 due to [11].
Achieving box disjointness for all threshold profiles. Note that exactly when in some dimension, the corresponding intervals are disjoint. When are adjacent, this holds as
However, it is not clear a priori how to make this hold for all where . Suppose , and for some . A sufficient property to guarantee disjointness is . More generally, for every where , we need the following to hold: there exists a coordinate such that , and . Recall that the threshold is chosen from the interval partition corresponding to the edge (recall eq. (2)). The ordering on these intervals has not yet been defined. We now define their ordering in such a way that the desired property is satisfied for all threshold profiles. For each , we will define a total order over so that together have the following property.
Definition 3.2 (Coherent family of orderings). Call total orders over context vectors coherent if the following holds. Let be any two non-adjacent vertices, i.e. . Then, there is a coordinate on which they differ such that the context of the -bit-0 vertex precedes the context of the -bit-1 vertex in . I.e. if , , we have and if , , we have .
The existence of a coherent family of total orders (according to Definition 3.2) completes the proof by the above argument. We now establish the existence of such a family. (See Figure 3 for an illustration of the final construction in 2-dimensions.)
Coherent orderings of context vectors. The heart of the construction is the following coherent family of orderings yielding the necessary structure.
Definition 3.3. For each , let be a total order on the contexts defined as follows. For each , look at the first bit where they differ. Suppose , . If , then . If , then . In other words, is a lexicographic order where all bits before use the reversed bit order and all bits after use the standard bit order.
Claim 3.4 (Coherence property). The family of orderings defined in Definition 3.3 satisfies the coherence property of Definition 3.2.
Proof. Let be the first two bits where and differ. First, suppose that , (the opposite case is symmetric). Observe that is the first bit on which the context vectors and disagree. Since , we then have by definition of the ordering .
Now, suppose , (again, the opposite case is symmetric). Observe that is the first bit on which the context vectors and disagree. Since , we then have by definition of the ordering .
Generalizing beyond the case. We have completed the proof for the case when . We now extend beyond this setting. For simplicity, we will assume is some power of 2.
. In this case, we can simply apply the previous construction in -dimensions and pad the instance with dummy coordinates. We have , establishing the lower bound claimed in Theorem 3.1.
. In this case, we create copies of the previous construction in dimensions, translated along the first coordinate. The points are divided evenly among these copies. It can be easily verified that this again results in the lower bound claimed in Theorem 3.1.
This completes the proof of Theorem 3.1.
Beating the General Box Lower Bound in the Small- Regime
In § 2, we saw that learning a labeling induced by boxes can require at least queries when is constant order. These boxes were allowed to overlap, although no data points may lie in the overlapping region. It turns out that if the boxes are guaranteed to be induced by disjoint boxes, then in the small- regime, it is possible to beat the lower bound. The next result, Theorem 3.5, shows that when is constant order, there is an upper bound of queries for learning the restricted class of disjoint boxes, which shaves off a factor of .
The algorithm that achieves this faster rate is a variant of a classic learning algorithm, which we refer to as Halving++, described in [Heg95]. Compared to CAL, Halving++ selects query points more carefully by searching for more informative points to query. It turns out that the more methodical selection is needed; we show in Section B that there are disjoint-box problems where CAL requires queries to learn, strictly separating CAL and Halving++.
Theorem 3.5 (Disjoint Boxes). Let . There is a deterministic algorithm that learns the labeling of a disjoint -box partition over a worst-case set of points in using
Proof. The proof of this uses a classic learning theory result bounding the query complexity through the extended teaching dimension of a binary concept class [Mos82, Heg95].
Definition 3.6 (Extended teaching dimension). Let be a finite set and let . For any , a subset is a specifying set for with respect to the concept class if at most one element satisfies for all . The extended teaching dimension of is
Theorem 3.7 (Query complexity bound, [Mos82, Heg95]). Let be a concept class. If and , there is a deterministic algorithm that identifies any concept in using at most
First, we convert the problem of learning a -box partition into one of learning a binary concept class. Let . Each labeling is associated to an element of
Let denote the concept class
To recover the ground truth labeling , it is enough to recover its associated concept . Every coordinate query to can be simulated by a single label query to , so it follows that by running the algorithm from Theorem 3.7 as a black-box, we can learn any by making at most
where is any upper bound on the extended teaching dimension. The result follows immediately from Lemmas 3.8 and 3.9 below, which bound and .
Lemma 3.8. Let be the class of disjoint -box partitions on defined in (3). Then:
Proof. Fix any . While is not necessary associated with a disjoint -box labeling, but we can still interpret it as assigning each point to a possibly empty set of labels, where the assignment is . There are three cases:
If there is an assigned zero labels or strictly more than one label, then the following set is a specifying set for with respect to . No such that for all and .
Suppose that each is assigned precisely one label. For each , let be the bounding box of points assigned the label by . In each dimension of this bounding box, we can let and be the left- and rightmost points out of all points labeled . Define to be the union of these bounding points, so that is a set of size at most . There is precisely one (not necessarily disjoint) box partition that induces the same labeling on .
By definition, the extending teaching dimension of is at most .
Lemma 3.9. There are at most disjoint -box partitions on any -point set .
Proof. Define . We will construct a family of test functions parametrized by such that the following holds: for any disjoint -box labeling and pair of distinct labels , there is a test function such that
Thus, is completely determined by a set of parameters , and
The claim holds because . We just need to construct the family of test functions.
For any labeling and pair of distinct labels , let and respectively be the bounding boxes of points in class and . These two boxes are disjoint if and only if there exists a separating dimension such that the projection of these boxes onto the th dimension is two disjoint intervals. Let minimize the distance to after projecting to the th dimension
Let for any . This is well-defined because is either strictly greater or strictly less than the th coordinate of every . A simple test to distinguish points in class and is the following test parametrized by
By construction, for all and for all $x_1 \in B_1.
Remark 3.10 (Applying the ETD argument to general boxes). *The same argument can be applied to the earlier, general setting of learning potentially-overlapping boxes. The proof of Lemma 3.8, which gave a bound of on the extended teaching dimension, also applies to general boxes; nowhere was disjointness used. The bound on the number of -box partitions can be upper bounded by , each box can be identified with two endpoints in each dimension. Then, Theorem 3.7 yields
queries.
This upper bound is worse than Theorem 1.1, although it is likely that the analysis is loose. But, for disjoint boxes, the savings achieved in Theorem 3.5 intuitively relies the fact that we can distinguish those boxes by a set of separating hyperplanes, rather than their endpoints.
Decision Trees
In this section we prove our results for decision trees stated in Theorem 1.3.
Definition 4.1 (Decision trees). Let be a label set of size . A function is a -leaf decision tree if either (a) , or (b) there exists , , and a strict subset such that the following hold:
restricted on is a -leaf decision tree with label set and
restricted on is a -leaf decision tree with label set .
A -leaf decision list is defined analogously, with the added restriction that is a singleton.
A decision stump is a 2-leaf decision tree. Our results in this section use the following learner for decision stumps as a black-box.
Theorem 4.2 (Corollary 2 item (1) of [10]). Let be an arbitrary set of points. There exists a deterministic algorithm, that exactly learns an arbitrary decision stump using queries. If the input is not realizable by a decision stump, the algorithm still halts within the claimed query budget and returns some labeling .
We use stumpLearn to denote the algorithm of Theorem 4.2. To see that the claim holds regarding inputs not realizable by decision stumps, one can simply truncate the learner at its promised worst-case query depth. If the learner is not done by this point, complete the labeling arbitrarily and return the result. Of course, correctness is only guaranteed in the realizable case.
Decision Tree Learner
We prove the following theorem, obtaining a upper bound.
Theorem 4.3. Let be an arbitrary label-set of size . There is a deterministic algorithm, which for any set of points, learns an unknown labeling induced by a -leaf decision tree using
queries. If is induced by a -leaf decision list, then the query complexity is .
Before proving Theorem 4.3, we remark that it is fairly direct to obtain a learner by enumerating all decision trees over the label set and applying stumpLearn at every internal node.
Remark 4.4 (A simple tree-enumeration algorithm). We give a sketch of a query algorithm. Let be a binary tree with leaves where every non-leaf has exactly two children. Note that there are exactly (the -th Catalan number) choices for . Then, let be a bijective map from the label set to the leaves of (there are such maps). For a node in , let denote the set of labels associated by to some leaf-descendant of . Now, for each of the non-leaf nodes , run stumpLearn (Theorem 4.2) with Boolean oracle . Combining the outputs of these calls to the stump learner yields a candidate labeling . By Definition 4.1, there exists at least one choice of such that . It is then straightforward to determine which of these candidate labelings is the correct one using at most one query per candidate. The total query complexity is
Our improvement over the brute-force enumeration described in Remark 4.4 comes from the following two observations:
There is a simple procedure (Claim 4.5) to certify correctness at the leaves, i.e. when the label-set is a singleton. This allows us to make permanent progress (by labeling one class) without needing to guess the entire correct binary tree over the labels all at once.
Given label-set , there exists where the root-level partition on the labels is such that . As a result, the recurrence governing the query complexity has the form .
Decision tree learner. We now describe the algorithm, which uses the following subroutine in addition to the stump learner of Theorem 4.2.
Claim 4.5 (Monochromatic Certification). Let be a labeling induced by a box partition, , and . There is a deterministic procedure monoCert using at most queries that decides whether or not .
Proof. The procedure simply queries all points in the set
of extremal points in with respect to each coordinate. Clearly . We then accept if and only if . Clearly, if , then . Conversely, since , if , then .
Given , our algorithm is defined recursively as follows.
DTLearn:
Base cases. If , return the empty labeling. If , run monoCert (Claim 4.5). If it accepts, return the constant labeling , otherwise return FAIL.
If , then let and repeat the following procedure defined in item (3) times, or until . (See line (3e).)
For every where , do the following: (a) Define where . (b) Run stumpLearn and let denote the returned Boolean labeling. (c) Let . (d) Run DTLearn. If it returns FAIL, then continue. If it returns a labeling , then assign these labels to and set . (e) If , return the accumulated labeling on the original input set.
If after repetitions of item (3), we have , then return FAIL.
Before proving correctness, we give some intuition for the above learner. Since is a decision tree, for some choice of in line (3), the Boolean labeling in line (3a) is a decision stump. By correctness of the decision stump learner, this implies that is a -leaf decision tree and thus by induction the points in are correctly labeled in line (3d). This removes at least one of the classes from , which is the reason that at most repetitions of (3) are needed. Importantly, even when is not a decision stump, any labeling returned by the recursive call is correct, preventing us from ever mislabeling points.
Correctness Proof
Lemma 4.6 (Soundness). Suppose satisfies where are disjoint axis-parallel boxes. Let be a candidate label set for . If DT Learn returns a labeling , then .
Proof. Every label assignment returned by DT Learn ultimately comes from a successful monochromatic certification at a singleton base case. Claim 4.5 guarantees that every such assignment is correct, regardless of whether the candidate label set contains all true labels. A complete labeling is returned only after every point has received a label.
Lemma 4.7 (Correctness). Suppose is induced by a -leaf decision tree where . Then DT Learn always returns the correct labeling .
Proof. The proof is by induction on . The case is clear and the case follows from Claim 4.5. Now, let . Consider the set defined in line (2) and consider some iteration of step (3) in which . We argue that one iteration of step (3) correctly labels all points in at least one of the labels. (Therefore, repetitions are enough, as claimed in line (2).) Note that by Lemma 4.6, a recursive call will never incorrectly label points.
First, suppose is constant, for some . Then, in step (3), the algorithm will try , in which (in line (3a)). This will result stumpLearn returning the all-1 labeling of and sets in line (3c). Line (3d) then invokes the base case, accepts, and labels all of .
Now, suppose contains at least 2 labels from . Note that is itself induced by a -leaf decision tree where (this holds for any subset of ). Therefore, there exists some where such that either iff (for some ) or iff . In some iteration of line (3), the algorithm tries this . The guarantee of stumpLearn (Theorem 4.2) implies that and thus . By induction, the recursive call to DT Learn successfully returns a labeling on , which by Lemma 4.6 is guaranteed to be correct. Therefore, at the end of step (3d) all points with labels in are removed from .
We have shown that every repetition of line (3) successfully learns at least one of the labels. Combining with Lemma 4.6, this shows that after at most repetitions, the algorithm returns the correct labeling, .
Query Complexity Proof
We derive the query complexity of DT Learn as follows. Fix and . Let denote the query complexity of the stump learner in -dimensions over points and let denote the query complexity of the monochromatic certification. For , let denote the query complexity of DT Learn on points in dimensions with labels. Then, by inspection, satisfies the following recurrence relation:
We now bound the recurrence, which establishes the claimed query complexity. We can expand the recurrence for as follows:
Using upper bounds and shows that the RHS above is at most
and this completes the proof.
Quadratic bound for decision lists. We now describe how to modify DTLearn to get an improved query complexity for decision lists (recall Definition 4.1). The simple change is to modify step (3) to try only singleton sets for . The algorithm is correct by the same arguments in Lemma 4.6 and Lemma 4.7. The algorithm correctly learns the labeling simply after repetitions of step (3) and only ever recurses on a singleton set of labels. Therefore, by inspection the query complexity is at most .
Lower Bound
We now prove an elementary lower bound establishing optimality of our algorithm for constant .
Theorem 4.8 (Decision List Lower Bound). Let . There exists set of points such that any randomized adaptive algorithm that learns a labeling induced by a -leaf decision list with success probability at least must use queries.
Proof. It suffices to prove an lower bound and a lower bound separately.
The bound. We first describe the construction for points. Let denote the standard unit basis vectors. For a vector , let . For a scalar , let . Our point-set is defined
Then, we consider the family of decision lists formed as follows. For each , choose a dimension . Given , we then define as
To reach any points, we can pad the point-set with arbitrary points such that for all .
Observe that such a labeling is a valid decision list (Definition 4.1). The key property of this construction is the following: for each , and for all . Therefore, learning the Boolean labeling in requires solving an unstructured search problem on elements, which requires queries for any randomized algorithm. Summing over for each shows that queries are needed.
The bound. Assume is a multiple of . It suffices to prove a lower bound for learning monotone functions . First, when , a lower bound of holds by a standard information-theoretic argument, since one needs to find a threshold in one of possible locations using queries that return a single bit of information.
Now, consider the following family of monotone functions. First, partition into intervals of length . In interval , we allow the function to take values in . Learning such a function requires the algorithm to learn the correct Boolean function restricted on each and crucially a query to gives no information about the function on any other interval. Thus, leveraging the lower bound, we obtain a lower bound of
and this completes the proof.
AI Disclosure
ChatGPT 5.6 was used during this work to explore proof ideas. All final proofs and exposition have been written and verified by the authors.
References
Query Complexity with Round Constraints
This section proves Theorem 2.2. Before we do so, we first prove the following key lemma about labelings that are induced by boxes. Consider any set of points with initially unknown labels. This lemma shows that if we label a random subset of points of size , then in expectation, we will be able to deduce the labels for all but a -fraction of points in .
Lemma A.1 (Expected coverage of a random set). Let be a set of points and let be a labeling induced by boxes. Given a fixed integer , let be a random subset of of size exactly . Let be a random variable denoting the number of points whose label cannot be inferred from . Then,
Proof. For each label , define and to be the points with label in and , respectively. Let be the number of points in . Let where is the number of points in whose label cannot be inferred from the labels , where
For each dimension , we also count the number of points in that land to the left and right of in the th dimension:
When , we use the convention . We can upper bound by the sum
We now bound . The bound on is the same and has an analogous argument. For each dimension , let denote the ordering of the points with respect to the th coordinate, breaking ties arbitrarily. For each integer , define the leftmost set of points under this ordering to be . Then:
To see this, suppose that . Every point must strictly dominate a set of points with respect to , which means that . As is chosen uniformly at random,
The last inequality holds because must miss a set of size . Using a layer-cake representation and applying the hockey-stick identity, we obtain
Putting everything together observing that always holds, we have
which completes the proof.
Proof of Theorem 2.2. The algorithm, defined as follows, can be seen as a batched-variant of CAL. Each round, instead of picking a single point from the disagreement region, randomly selects a subset of points. To formally define the algorithm, pick a permutation , then batch the points into sets. In the -th round where , query all points in the -th batch whose labels cannot already be inferred from previous queries. We will fix a sequence of batch sizes so that the expected query complexity over is minimized. Towards this, given an arbitrary schedule
the -th batch will be . We first obtain an expression for the expected query complexity of a general schedule using Lemma A.1. For , let be the random variable denoting the number of queries made in the -th round (over the randomness of ). For , conditioned on being the first points in the ordering induced by , the first such points form a uniformly random subset of of size . Therefore, to bound we can simply apply Lemma A.1 with playing the roles of respectively. We obtain
To choose a schedule that optimizes the above expected query complexity, for each , set
Substituting this into Equation (7) yields
as claimed.
Remark A.2. The optimal query complexity can be obtained by setting the round complexity to only in Theorem 2.2. From Equation (8) in the proof, we see that the -th round considers points in a batch of size
and the number of queries made in that batch is expected to be
Separation between CAL and Halving++
This section gives a construction of a disjoint-box problem where CAL uses strictly more queries in expectation than Halving++. We restate the query complexities from § 2 and § 3 here. Treating the number of boxes as a constant, they are
CAL: queries \hspace{2em} Halving++: queries.
While it seems that Halving++ attains a -factor saving, these bounds cannot be directly compared because the bound for CAL applies to general boxes, while the one for Halving++ applies to disjoint boxes; we cannot deduce that Halving++ is more label-efficient than CAL.
Nevertheless, the next result strictly separates these two algorithms. We construct a disjoint-box problem where the upper bound we proved for CAL is tight. In particular, if we let , then CAL requires queries. In contrast, for the same problem, the above query complexity of the more careful Halving++ algorithm resolves to queries.
Proposition B.1 (Query lower bound for CAL). Let . There is an -point set in so that the expected number of queries that CAL requires to learn any -disjoint box partition over is
Proof. We first give a proof when and . Let . Unbeknownst to the learner, let the labeling be a constant map that assigns every point to the same class. This is a valid two-disjoint box partition, where one of the boxes is empty.
Let’s see how CAL works; it is also described in the proof of Theorem 1.1. Say CAL makes a sequence of queries . At the end of round , it can infer the labels of points only in the set
This is because any point can be split off from the queried points via a threshold; there is a valid two-disjoint box partition that is consistent with the observed labels that assigns a different label. And so, in the next round, CAL chooses uniformly at random from the points not covered by the previous bounding box, and CAL terminates only when the bounding box covers every point in . It follows that the query complexity of CAL for this problem instance is simply the amount of time it takes for the bounding box over the queries to cover .
We can compute the expectation as follows. Let be a random ordering of the points in , where CAL iterates through and queries it if it cannot yet infer its label. Notice that CAL will query a point if it has not previously a point to the left:
Since the ordering is random, we have
where is the th harmonic number.
In higher dimensions, we can improve the bound by making a copy for each dimension. Define
When , let be constant. As in the 1-dimensional case, CAL can only infer the labels of points contained in the bounding box of its previous queries: there is always an axis-aligned halfspace splitting from any point from not contained in it. Notice that if CAL queries a point lying along the th dimension, the bounding box only grows in the th dimension, and so we may treat each dimension independently. This gives a lower bound
Finally, with general , we can make translated copies of this construction, where each copy is assigned a separate label. The same argument yields the claimed lower bound
References
- [1][AKBD16] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. Advances in Neural Information Processing Systems, 29, 2016. 7arxiv.org/abs/1606.02404
- [2][Ang87] Dana Angluin. Queries and concept learning. Mach. Learn., 2(4):319–342, 1987. 3, 7
- [3][BBL09] Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. J. Comput. Syst. Sci., 75(1):78–89, 2009. 7, 8
- [4][BBZ07] Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. Margin based active learning. In Nader H. Bshouty and Claudio Gentile, editors, Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings, volume 4539 of Lecture Notes in Computer Science, pages 35–50. Springer, 2007. 7DOI
- [5][BCLP24] Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice. Margin-based active learning of classifiers. J. Mach. Learn. Res., 25:127:1–127:45, 2024. 7
- [6][BDBK97] Shai Ben-David, Nader H Bshouty, and Eyal Kushilevitz. A composition theorem for learning algorithms with applications to geometric concept classes. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 324–333, 1997. 7
- [7][BGGM98] Nader H Bshouty, Paul W Goldberg, Sally A Goldman, and H David Mathias. Exact learning of discretized geometric concepts. SIAM journal on Computing, 28(2):674–699, 1998. 7DOI
- [8][BGM+98] Nader H Bshouty, Sally A Goldman, H David Mathias, Subhash Suri, and Hisao Tamaki. Noise-tolerant distribution-free learning of general geometric concepts. Journal of the ACM (JACM), 45(5):863–890, 1998. 7
- [9][BL13] Maria-Florina Balcan and Philip M. Long. Active and passive learning of linear separators under log-concave distributions. In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 288–316. JMLR.org, 2013. 7
- [10][BLM+26] Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, and Geelon So. Actively learning halfspaces without synthetic data. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA, volume 336 of Proceedings of Machine Learning Research, pages 708–728. PMLR, 2026. 5, 6, 7, 16arxiv.org/abs/2509.20848
- [11][BPR20] Simina Brânzei, Dimitris Paparas, and Nicholas J. Recker. Searching, sorting, and cake cutting in rounds. CoRR, abs/2012.00738, 2020. 7, 9, 13
