betaFeedback

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 X⊂RdX \subset \mathbb{R}^d be a set of nn points, labeled by a collection of kk boxes: the label of each point in XX is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in XX 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 Θ(kdlog⁡(n/kd))Θ(kd \log (n/kd)). When the boxes are disjoint, we examine two regimes. In the large-kk regime, CAL remains minimax-optimal. For the constant-kk regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a log⁡(d)\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)Θ(d + \log n) that is additive in dd and log⁡n\log n, 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 X⊂RdX \subset\mathbb{R}^{d} be any finite set of nn points and Y:=[k]Y := [k] be a set of kk labels. The goal of a learner is to recover an unknown labeling f:X→Yf : X \to Y when provided access to a label oracle: upon being given a query x∈Xx \in X, the oracle supplies the label f(x)f(x). The basic problem is to understand how many queries the learner needs before being able to deduce the label of every point in XX.

We study the family of axis-aligned partitions, or more plainly, box partitions. A labeling ff is a box partition if it is induced by kk boxes: for each label y∈Yy \in Y, there is a box By⊂RdB_y \subset\mathbb{R}^{d} such that the points in the yyth class are given by f−1(y)=X∩Byf^{-1}(y) = X \cap B_y. There are ay,i≤by,i∈R∪{±∞}a_{y,i} \le b_{y,i} \in\mathbb{R} \cup\{\pm\infty\} so that

∀x∈X,f(x)=y⟺x∈By,where By=∏i=1d[ay,i,by,i].\forall x \in X,\quad f(x) = y \quad\Longleftrightarrow\quad x \in B_y,\qquad\text{where } B_y = \prod_{i=1}^{d}[a_{y,i},b_{y,i}].

A simple example of box partitions is the family of axis-aligned halfspaces (decision stumps). These are box partitions that split XX 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:

Axis-aligned partitions induced by general boxes, disjoint boxes, and the leaves of a decision tree

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 XX is contained in precisely one of the underlying boxes. The boxes themselves may overlap in Rd\mathbb{R}^{d}.

  • Disjoint box partitions: The boxes must be disjoint, By∩By′=∅B_y \cap B_{y'} = \emptyset for distinct y,y′∈Yy,y' \in Y.

  • 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 YY. For each internal node in the binary tree, there is a dimension i∈[d]i \in[d] and a threshold τ∈R\tau\in\mathbb{R} that splits its left and right descendants: a descendant y∈Yy \in Y is to the left if and only if f−1(y)⊂{x∈Rd:xi<τ}f^{-1}(y) \subset\{x \in\mathbb{R}^{d} : x_i < \tau\}.

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 Θ(kdlog⁡(n/kd))\Theta(kd\log(n/kd)), where n:=∣X∣n := |X| is the number of points, k:=∣Y∣k := |Y| is the number of labels, and dd is the number of dimensions. Formally:

Theorem 1.1 (General Boxes). Let n≥k≥2n \ge k \ge2. Consider the problem of learning a general kk-box partition over a worst-case set of nn points in dd-dimensions.

  • The expected query complexity of this problem is Θ(kdlog⁡(1+nkd))\Theta\left(kd\log\left(1+\frac{n}{kd}\right)\right).

  • For any 1≤r≤log⁡2(n/kd)1 \le r \le\log_{2}(n/kd), the rr-round query complexity is Θ(rkd(1+nkd)1/r)\Theta\left(rkd\left(1+\frac{n}{kd}\right)^{1/r}\right).

In particular, there is an algorithm achieving the optimal query complexity with a 1+log⁡2(1+n/dk)1+\log_{2}(1+n/dk) 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 rr 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-kk regime with k≥2dk \ge2^d boxes, CAL remains minimax-optimal: the query complexity is lower bounded by Ω(kdlog⁡(n/kd))\Omega(kd \log(n/kd)), which matches the upper bound for general box partitions. On the other hand, in the small-kk regime where the number of boxes k=O(1)k = O(1) is constant, the upper bound for disjoint boxes can be a log⁡(d)\log(d)-factor smaller than the lower bound for general boxes:

Theorem 1.2 (Disjoint Boxes). Let d,k≥2d, k \ge2. There is a randomized algorithm that learns any disjoint kk-box partition over a worst-case set of nn points in dd-dimensions using in expectation

O(min⁡{n,kdlog⁡(1+nkd),k3dlog⁡nlog⁡(kd)})O\left(\min\left\{n, kd\log\left(1+\frac{n}{kd}\right), \frac{k^3d\log n}{\log(kd)}\right\}\right)

queries.

When k≥2Ω(d)k \ge2^{\Omega(d)}, the upper bound is matched with a lower bound of Ω(kdlog⁡nkd)\Omega\left(kd\log\frac{n}{kd}\right) queries.

We prove this theorem in § 3. In the small-kk 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 kk is equal to the number of non-empty leaves.6 For constant-sized trees, the query complexity has additive upper and lower bounds of Θk(d+log⁡n)\Theta_k(d+\log n). Thus, there is a further separation between this setting and the general box setting, which has a multiplicative lower bound of Ωk(dlog⁡n)\Omega_k(d\log n). We show:

Theorem 1.3 (Decision Trees). Let k,d≥2k,d \ge2 and n≥d(k−1)n \ge d(k-1). There is a deterministic algorithm that learns any box-partition induced by the leaves of a kk-leaf decision tree using at most

2O(k)(d+log⁡n) queries.2^{O(k)}(d+\log n)\ \text{queries}.

If the decision tree is a decision list, then the query complexity is upper bounded by O(k2(d+log⁡n))O(k^2(d+\log n)), and it is lower bounded by Ω(k(d+log⁡(n/k)))\Omega(k(d+\log(n/k))) when n≥dn \ge d.

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 classRegimeBoundResult
BoxesallΘ(kdlog⁡nkd)\Theta\left(kd\log\frac{n}{kd}\right)Theorem 1.1
Disjoint boxesk≥2dk \ge2^dΘ(kdlog⁡nkd)\Theta\left(kd\log\frac{n}{kd}\right)Theorem 1.2
Disjoint boxesk=O(1)k = O(1)O(dlog⁡nlog⁡d)O\left(\frac{d\log n}{\log d}\right)Theorem 1.2
Decision-tree leavesk=O(1)k = O(1)Θ(d+log⁡n)\Theta(d+\log n)Theorem 1.3
Decision stumpsk=2k = 2Θ(d+log⁡n)\Theta(d+\log n)[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 S={x1,…,xm}S=\{x_1,\ldots,x_m\} with the same label yy. Then, every point in XX contained in the bounding box of SS must also be labeled yy, 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 XX.

The lower bounds throughout this work are built on the fact that learning a monotone function f:[n]→{0,1}f:[n]\to\{0,1\} from label queries requires Θ(log⁡n)\Theta(\log n) 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 Θ(kd)\Theta(kd) threshold problems, each consisting of Θ(n/kd)\Theta(n/kd) points. Thus, we obtain an Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) lower bound.

These lower bounds are rather non-trivial to find. Consider even k=2k = 2 boxes. It is clear how one threshold learning problem over nn 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 Ω(log⁡n)\Omega(\log n) lower bound, not the stronger Ω(dlog⁡(n/d))\Omega(d\log(n/d)). The problem is that only a single face of each of the boxes contributes to hardness. Intuitively, naive construction under-utilizes the set of 2d2d faces available from each box. The question is how to place the points so that all Θ(d)\Theta(d) faces of the two boxes can interact with each other to admit Θ(d)\Theta(d) independent threshold learning problems. The construction we give achieves this using overlapping boxes. It turns out that to extract this hardness for general kk, 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-kk regime that continues to match the general-box upper bound. It also shows that in the small-kk regime with disjoint boxes, it is possible to beat the general-box lower bound.

The lower bound in the large-kk regime is a construction that embeds Θ(kd)\Theta(kd) independent threshold learning problems into a disjoint box learning problem. When k=2dk = 2^d, we will embed a threshold learning problem onto every edge of a Boolean hypercube (note there are d2d−1=Θ(kd)d2^{d-1} = \Theta(kd) 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 Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) lower bound.

Two point configurations on the edges of a two-dimensional Boolean hypercube

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 log⁡(d)\log(d)-factor in the k=Θ(1)k = \Theta(1) 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 XX. 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 2kd2kd thresholds associated to the faces of the boxes, or through a set of Θ(k2)\Theta(k^2) halfspaces that separate every pair of label class. In a sense, CAL learns only by recovering the 2kd2kd thresholds. Halving++ can be strictly more label-efficient, and it does so intuitively by leveraging this alternative specification, which is independent of dd. For constant order kk, we show that this is ultimately the source of the log⁡(d)\log(d)-factor savings.

Decision trees. In Theorem 1.3 we consider the class of disjoint box partitions that are induced by kk-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 kk is relatively small. [10] gave a O(d+log⁡n)O(d + \log n) query learner for the class of 2-leaf decision trees (or decision stumps). Intuitively, if we compare 2-box partitions, the gap between the Θ(dlog⁡(n/d))\Theta(d\log(n/d)) sample complexity for general boxes and Θ(d+log⁡n)\Theta(d + \log n) 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 Ω(d)\Omega(d) faces of the two boxes.

More generally, for k≥2k \ge2, when a labeling f:X→Yf : X \to Y 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, A⊂YA \subset Y and Y∖AY \setminus A, and this same structure repeats on each side. If this subset AA is known in advance, then one can apply the decision stump learner to recover gA(x)=1(f(x)∈A)g_A(x) = 1(f(x) \in A). Extending this observation, if the label-splits are provided at each level of the tree, this would yield a O(k(d+log⁡n))O(k(d + \log n)) query algorithm. This shows that naively guessing every such tree yields a kO(k)(d+log⁡n)k^{O(k)}(d + \log n) query algorithm (see Remark 4.4). In Theorem 1.3, we reduce the kk-dependence to 2O(k)2^{O(k)} 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-kk regime. When k≥2Ω(d)k \ge2^{\Omega(d)}, we obtain a Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) lower bound, matching our upper bound for general kk-box partitions. However, when k<2o(d)k < 2^{o(d)}, our bounds are not tight, and our upper bounds in Theorem 1.2 demonstrate a separation from general boxes when kk is sufficiently small. Therefore, as kk 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 kk 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 kk-box partitions is given by [5]. They provide a generic algorithm for multi-class active learning, which uses O(kdlog⁡klog⁡n)O(kd\log k\log n) queries when specialized to boxes. In a more specific two-class setting, [10] establishes that the query complexity for axis-aligned halfspaces is Θ(d+log⁡n)\Theta(d+\log n).

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 kk boxes in dd dimensions can be specified by a set of kdkd 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 a≤b∈R∪{±∞}a \le b \in\mathbb{R} \cup\{\pm\infty\}, we let [a,b][a,b] denote the closed interval from aa to bb. Given a finite set of points S⊆RdS \subseteq\mathbb{R}^d, denote its bounding box by

bbox⁡(S)=∏i=1d[min⁡x∈Sxi,max⁡x∈Sxi].\operatorname{bbox}(S) = \prod_{i=1}^{d} \left[\min_{x \in S} x_i, \max_{x \in S} x_i\right].

General Box Partitions

In this section, we prove Theorem 1.1, which considers learning a general box partition: there is a set of kk potentially-overlapping boxes B1,…,Bk⊂RdB_1,\ldots,B_k \subset\mathbb{R}^d that induce a partition of XX

X = (X \cap B_1) \mathbin{\mathaccent\cdot\cup} \cdots\mathbin{\mathaccent\cdot\cup} (X \cap B_k).

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 XX whose labels cannot be deduced yet: it contains a point xx if there are at least two valid labelings that disagree on how to label xx, 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 SS is a set of points that have been labeled yy, then the learner may deduce that every point in the bounding box bbox⁡(S)\operatorname{bbox}(S) is also labeled yy. 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 kk-box partition in dd dimensions over nn points using at most 4kdlog⁡(1+nkd)4kd\log(1+\frac{n}{kd}) label queries in expectation.

Proof. The algorithm is defined as follows.

  1. Initialize a partial function h:X→[k]∪{∗}h:X\to[k]\cup\{\ast\} as h(x)=∗h(x)=\ast for all x∈Xx\in X. For each y∈[k]y\in[k], let Xh,y={x∈X:h(x)=y}X_{h,y}=\{x\in X:h(x)=y\} throughout the execution. We will maintain the invariant

Xh,y⊆Xy.X_{h,y}\subseteq X_y.
  1. Choose a permutation π:[n]→X\pi:[n]\to X uniformly at random.

  1. For each i≤ni\le n, let x=π(i)x=\pi(i) and do the following: (a) If h(x)≠∗h(x)\ne\ast, then continue. (b) If h(x)=∗h(x)=\ast, then query f(x)f(x). Set h(x)=f(x)h(x)=f(x), and also set h(z)=f(x)h(z)=f(x) for all points z∈bbox⁡(Xh,f(x))z\in\operatorname{bbox}(X_{h,f(x)}).

The correctness of the algorithm is clear by inspection. We now analyze the expected number of queries over the randomness of π\pi. Whether or not a point with label yy is queried depends only on the ordering that π\pi induces on XyX_y. Let πy:[ny]→Xy\pi_y:[n_y]\to X_y denoted this restriction of π\pi where ny:=∣Xy∣n_y:=|X_y|. Observe that for each t≤nyt\le n_y, πy(t)\pi_y(t) is queried if and only if it is not contained in the bounding box of πy(1),…,πy(t−1)\pi_y(1),\ldots,\pi_y(t-1). Equivalently, πy(t)\pi_y(t) is queried if and only if it is a maximal point7 among πy(1),…,πy(t)\pi_y(1),\ldots,\pi_y(t). Since dd-dimensional boxes have at most 2d2d maximal points, and πy(t)\pi_y(t) is uniform random among πy(1),…,πy(t)\pi_y(1),\ldots,\pi_y(t), the probability πy(t)\pi_y(t) is queried is at most 2d/t2d/t. Let Q(π)=∑yQy(π)Q(\pi)=\sum_y Q_y(\pi) denote the total number of queries made by the algorithm on permutation π\pi, where Qy(π)Q_y(\pi) is the number of queries in XyX_y. By linearity of expectation,

Eπy[Qy(π)]=∑t=1nyPr⁡πy[πy(t) is queried]≤∑t=1nymin⁡(1,2dt)≤∑t=1ny4d2d+t≤4d∫0nydx2d+x=4dln⁡(1+ny2d).(1)\begin{aligned} \mathbb{E}_{\pi_y}[Q_y(\pi)] = \sum_{t=1}^{n_y}\Pr_{\pi_y}[\pi_y(t)\text{ is queried}] \\ &\le\sum_{t=1}^{n_y}\min\left(1,\frac{2d}{t}\right)\le\sum_{t=1}^{n_y}\frac{4d}{2d+t}\le4d\int_0^{n_y}\frac{dx}{2d+x}=4d\ln\left(1+\frac{n_y}{2d}\right). \tag*{(1)} \end{aligned}

Applying linearity of expectation over all kk labels yields

Eπ[Q(π)]≤4d∑y=1kln⁡(1+ny2d)≤4kdln⁡(1+n2kd)\mathbb{E}_{\pi}[Q(\pi)] \le4d \sum_{y=1}^{k} \ln\left(1+\frac{n_y}{2d}\right) \le4kd\ln\left(1+\frac{n}{2kd}\right)

by Jensen’s inequality.

Next we consider an rr-round variant of CAL. The proof is in Section A.

Theorem 2.2 (rr-round algorithm). For any 1≤r≤log⁡(n/2dk)1 \le r \le\log(n/2dk), there is an rr-round randomized algorithm which learns an arbitrary kk-box partition in dd-dimensions over nn points using

2rkd⋅(n2dk)1/r2rkd\cdot\left(\frac{n}{2dk}\right)^{1/r}

queries in expectation. In particular, when r=log⁡(n/2dk)r=\log(n/2dk), this recovers the optimal query complexity O(kdlog⁡(n/kd))O(kd\log(n/kd)), while improving on the round complexity in Theorem 2.1 by a Θ(kd)\Theta(kd) factor.

Matching Lower Bound

The simplest, nontrivial setting for learning box partitions is when k=2k=2 and d=1d=1. 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 log⁡2n\log_2 n 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 f:[n]→{0,1}f:[n]\to\{0,1\} with query access. Suppose that a randomized algorithm AA solves this problem on every input ff with success probability at least 2/32/3. Then, there exists ff such that the expected number of queries made is at least Ω(log⁡n)\Omega(\log n). Moreover, if AA uses 1≤r≤log⁡2n1\le r\le\log_2 n rounds of adaptivity, then there exists ff such that the expected number of queries made is at least Ω(rn1/r)\Omega(rn^{1/r}).

To obtain query lower bounds for general k,d≥2k,d\ge2, we will show that a set of Θ(kd)\Theta(kd) independent threshold learning problems with mm points each can be reduced to learning a general kk-box partition over a set of points of size n=Θ(kdm)n=\Theta(kdm). We obtain a lower bound Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) for the round-unconstrained setting, and a lower bound of Ω(rkd(n/kd)1/r)\Omega(rkd(n/kd)^{1/r}) for the rr-round setting:

Theorem 2.4 (Lower bound for general boxes). Let k,d≥2k,d\ge2 be even. Let 2≤m≤4nkd2\le m\le\frac{4n}{kd} be a natural number. Suppose a randomized algorithm learns any kk-box partition over nn points in Rd\mathbb{R}^d with success probability 2/32/3. Then, there exists a problem instance such that the expected number of queries made is at least Ω(kdlog⁡m)\Omega(kd\log m). Moreover, if the algorithm uses 1≤r≤log⁡2m1\le r\le\log_2m rounds of adaptivity, then there exists a problem instance such that the expected number of queries made is at least Ω(rkdm1/r)\Omega(rkdm^{1/r}).

Proof. Let C=kd4C=\frac{kd}{4}. Let fi,j:[m]→{0,1}f_{i,j}:[m]\to\{0,1\} be a collection of CC independent monotone functions, where (i,j)(i,j) ranges over [k/2]×[d/2][k/2]\times[d/2]. We construct a reduction from learning these thresholds to learning a kk-box partition over CmCm points as follows.

Let’s start with the k=2k=2 case. We drop the index ii as it now ranges over the singleton {1}\{1\}. Define the map ϕ:[d/2]×[m]→Rd\phi:[d/2]\times[m]\to\mathbb{R}^d by

ϕ(j,t)≡ϕj(t)=(0,…,0, m−t, t, 0,…,0).\phi(j,t)\equiv\phi_j(t)=\left(0,\ldots,0,\ m-t,\ t,\ 0,\ldots,0\right).

where the (2j−1,2j)(2j-1,2j)th coordinate

ϕ(j,t)≡ϕj(t)=(0,…,0, m−t, t, 0,…,0).\begin{aligned} \phi(j,t)&\equiv\phi_j(t)=\left(0,\ldots,0,\ m-t,\ t,\ 0,\ldots,0\right). \end{aligned}

We can think of ϕj\phi_j’s as a collection of d/2d/2 affine embeddings of [m][m] into Rd\mathbb{R}^d. Define the set

X=⋃j∈[d/2]ϕj([m]).X = \bigcup_{j\in[d/2]} \phi_j([m]).

By construction, the map ϕ:[d/2]×[m]→X\phi:[d/2]\times[m]\to X is bijective. Define the labeling f:X→{0,1}f:X\to\{0,1\} by

x=ϕ(j,t)⟹f(x)=fj(t).x=\phi(j,t) \quad\Longrightarrow\quad f(x)=f_j(t).

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 (2j−1,2j)(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.

Claim 2.5. The labeling ff is a 2-box partition. Moreover, the following hold:

(a) The set of CC threshold functions fjf_j’s can be computed from ff.

(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 ff with success probability pp can be converted into an algorithm that learns the original set of thresholds with the same success probability pp 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

C⋅Ω(max⁡{nm1/r,log⁡2m}).C\cdot\Omega\left(\max\left\{nm^{1/r},\log_2 m\right\}\right).

We now prove the claim. The subclaims (a) and (b) are direct, and they are conceptually converses of each other. We can compute fjf_j from ff since fj(t)f_j(t) is equal to f(ϕj(t))f(\phi_j(t)). On the other hand, a query x=ϕ(j,t)x=\phi(j,t) to the box-label oracle can be simulated by querying fj(t)f_j(t).

Proof that ff is a 2-box partition. Let 0<τj<m+10<\tau_j<m+1 be a threshold for fjf_j, so that

fj(t)={0t<τj1t>τj.f_j(t)= \begin{cases} 0 & t<\tau_j \\ 1 & t>\tau_j. \end{cases}

Define the boxes B0B_0 and B1B_1 as follows. Let Πj:Rd→R2\Pi_j:\mathbb{R}^d\to\mathbb{R}^2 be the projection onto the (2j−1)(2j-1)th and (2j)(2j)th components for j∈[d/2]j\in[d/2]. Then:

Πj(B0)=[0,m]×[0,τj]andΠj(B1)=[0,m−τj]×[0,m].\Pi_j(B_0)=[0,m]\times[0,\tau_j]\qquad\text{and}\qquad\Pi_j(B_1)=[0,m-\tau_j]\times[0,m].

These two boxes are defined so that y=fj(t)y=f_j(t) if and only if ϕ(j,t)∈By\phi(j,t)\in B_y. Indeed for all t∈[m]t\in[m],

fj(t)=0⟺t<τj⟺m−t>m−τj.f_j(t)=0 \quad\Longleftrightarrow\quad t<\tau_j \quad\Longleftrightarrow\quad m-t>m-\tau_j.

Recall that the (2j−1,2j)(2j-1,2j)-coordinates of ϕ(j,t)\phi(j,t) is (m−t,t)(m-t,t). The second condition is equivalent to ϕ(j,t)∈B0\phi(j,t)\in B_0, while the third is equivalent to ϕ(j,t)∉B1\phi(j,t)\notin B_1. Thus, ff is a 2-box partition.

Generalization to k≥2k\ge2. We now make k/2k/2 translated copies of the 2-box construction with m≤4nkdm\le\frac{4n}{kd}, so that there are a total of kk-classes. Define the point set as

X=⋃i∈[k/2]⋃j∈[d/2]ϕj([m])+(mi)1,X=\bigcup_{i\in[k/2]}\bigcup_{j\in[d/2]}\phi_j([m])+(mi)\mathbf{1},

where in the iith copy, we translate each point by the vector (mi,…,mi)(mi,\ldots,mi). As before, each point in XX corresponds to a unique set of indices (i,j,t)∈[k/2]×[d/2]×[m](i,j,t)\in[k/2]\times[d/2]\times[m]. Letting ϕ:(i,j,t)↦x\phi:(i,j,t)\mapsto x denote this bijection, we define ff similarly, where f(x)=2i+fi,j(t)f(x)=2i+f_{i,j}(t) when x=ϕ(i,j,t)x=\phi(i,j,t). In this way, we obtain an embedding of CC independent threshold problems and the stated lower bound. ▫

Disjoint Box Partitions

In this section we prove our results for disjoint kk-box partitions stated in Theorem 1.2. We start by proving our lower bound in § 3.1 for the large-kk regime, then obtain a separation between disjoint and general boxes in § 3.2 with an improved algorithm for the small-kk regime.

Matching Lower Bound in the Large-kk Regime

We prove the following lower bound for learning disjoint kk-box partitions. In particular, we obtain a Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) query lower bound for fully adaptive, randomized algorithms when k≥2dk\ge2^d, showing that when kk is sufficiently large, disjointness does not make the learning problem easier.

Theorem 3.1 (Lower bound for disjoint boxes). Let k≥2k\ge2 be a power of two and d≥1d\ge1. Define L=min⁡(d,log⁡2k)L=\min(d,\log_2 k) and let 2≤m≤2nkd2\le m\le\frac{2n}{kd} be a natural number. Suppose a randomized algorithm learns any disjoint kk-box partition over nn points in Rd\mathbb{R}^d with success probability 2/32/3. Then, there exists a problem instance such that the expected number of queries made is at least Ω(kLlog⁡m)\Omega(kL\log m). Moreover, if the algorithm uses 1≤r≤log⁡2m1\le r\le\log_2m rounds of adaptivity, then there exists a problem instance such that the expected number of queries made is at least Ω(rkLm1/r)\Omega(rkLm^{1/r}).

Proof. We first prove the theorem when k=2dk=2^d, and thus L=dL=d. The more general case will follow easily from this setting. For the sake of simplicity, assume that kdkd divides 2n2n. We will construct a set X⊆RdX\subseteq\mathbb{R}^d of nn points and a family of k=2dk=2^d boxes that induce kd/2kd/2 independent threshold learning problems, each on a set of m=2n/dkm=2n/dk points. The lower bound will then follow by applying Theorem 2.3 across each independent threshold problem.

Our construction is built on the dd-dimensional hypercube, {0,1}d\{0,1\}^d. Each vertex u∈{0,1}du\in\{0,1\}^d corresponds to a label induced by a box BuB_u such that u∈Bu⊆[0,1]du\in B_u\subseteq[0,1]^d. These boxes are disjoint.

Notation. Given u∈{0,1}du\in\{0,1\}^d and p∈[d]p\in[d], we let u−p∈{0,1}d−1u_{-p}\in\{0,1\}^{d-1} denote the context vector obtained by removing the pp-th bit of uu. For a context vector z∈{0,1}d−1z\in\{0,1\}^{d-1} and coordinate p∈[d]p\in[d], we use the pair (p,z)(p,z) to identify the hypercube edge with context zz in direction pp.

The construction. Our objective is to induce an independent threshold learning problem along each edge (p,z)(p,z). For each dimension p∈[d]p\in[d] and context z∈{0,1}d−1z\in\{0,1\}^{d-1}, we define a disjoint family of intervals as follows:

I(p)={I(p,z)⊆[0,1]:z∈{0,1}d−1} such that ⋃z∈{0,1}d−1I(p,z)=[0,1].(2)\mathcal{I}(p)=\left\{I(p,z)\subseteq[0,1]:z\in\{0,1\}^{d-1}\right\}\text{ such that }\bigcup_{z\in\{0,1\}^{d-1}}I(p,z)=[0,1]. \tag*{(2)}

These intervals are of uniform length, 2−(d−1)2^{-(d-1)}. Note that what is currently left undefined is the ordering of the intervals according to their context vectors, zz. This turns out to be a critical aspect of the construction, which we will discuss and define later.

On each edge (p,z)∈[d]×{0,1}d−1(p,z) \in[d] \times\{0,1\}^{d-1}, we induce a threshold learning problem on the segment

L(p,z)={x∈[0,1]d:x−p=z and xp∈I(p,z)}.L(p,z) = \left\{x \in[0,1]^{d}: x_{-p} = z \text{ and } x_p \in I(p,z)\right\}.

To do this, we let X(p,z)⊂L(p,z)X(p,z) \subset L(p,z) be a set of ndd−1=2nkd=m\frac{n}{d^{d-1}} = \frac{2n}{kd} = m uniformly spaced interior points along this segment. Concretely, if I(p,z)=[a,a+h]I(p,z) = [a,a+h], then define

δ=h2m+2\delta= \frac{h}{2m+2}

and

X(p,z)={x∈[0,1]d:x−p=z,xp∈{a+2iδ:1≤i≤m}}.X(p,z) = \left\{x \in[0,1]^d: x_{-p} = z, x_p \in\{a+2i\delta: 1 \le i \le m\}\right\}.

We define the full point-set as

X=⋃p∈[d],z∈{0,1}d−1X(p,z).X = \bigcup_{p \in[d],z \in\{0,1\}^{d-1}} X(p,z).

A threshold τ(p,z)∈I(p,z)\tau(p,z) \in I(p,z) is then chosen somewhere in this interval. Concretely,

τ(p,z)∈{a+(2i+1)δ:0≤i≤m}\tau(p,z) \in\left\{a+(2i+1)\delta: 0 \le i \le m\right\}

is one of m+1m+1 possible values. Then, given a threshold profile

T={τ(p,z):p∈[d],z∈{0,1}d−1}T = \left\{\tau(p,z): p \in[d], z \in\{0,1\}^{d-1}\right\}

the box for label u∈{0,1}du \in\{0,1\}^{d} is defined as

Bu=(∏p∈[d]:up=0[0,τ(p,u−p)−δ/2])×(∏p∈[d]:up=1[τ(p,u−p)+δ/2,1]).B_u = \left(\prod_{p \in[d]:u_p=0} [0,\tau(p,u_{-p})-\delta/2]\right) \times \left(\prod_{p \in[d]:u_p=1} [\tau(p,u_{-p})+\delta/2,1]\right).

The additive ±δ/2\pm\delta/2 term is simply to ensure that the following closed intervals are disjoint:

[0,τ(p,u−p)−δ/2]and[τ(p,u−p)+δ/2,1].[0,\tau(p,u_{-p})-\delta/2] \quad\text{and} \quad[\tau(p,u_{-p})+\delta/2,1].

Note that the union of these boxes indeed cover XX, regardless of the threshold profile TT. The crux of the construction is to show that all (m+1)kd/2=(2nkd+1)kd/2(m+1)^{kd/2} = \left(\frac{2n}{kd}+1\right)^{kd/2} threshold profiles are realizable while maintaining box disjointness, i.e. Bu∩Bv=∅B_u \cap B_v = \varnothing for all u≠v∈{0,1}du \ne v \in\{0,1\}^{d}.

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 X(p,z)X(p,z) amounts to learning a monotone function on a domain of size m=2nkdm = \frac{2^n}{kd}. 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 Bu∩Bv=∅B_u \cap B_v = \varnothing exactly when in some dimension, the corresponding intervals are disjoint. When u,vu,v are adjacent, this holds as

[0,τ(p,u−p)−δ/2]∩[τ(p,u−p)+δ/2,1]=∅.[0,\tau(p,u_{-p})-\delta/2]\cap[\tau(p,u_{-p})+\delta/2,1]=\varnothing.

However, it is not clear a priori how to make this hold for all u,vu,v where d(u,v)≥2d(u,v)\ge2. Suppose up=0u_p=0, vp=1v_p=1 and uq≠vqu_q\ne v_q for some q≠p∈[d]q\ne p\in[d]. A sufficient property to guarantee disjointness is τ(p,u−p)<τ(p,v−p)\tau(p,u_{-p})<\tau(p,v_{-p}). More generally, for every u,vu,v where d(u,v)≥2d(u,v)\ge2, we need the following to hold: there exists a coordinate pp such that up=0u_p=0, vp=1v_p=1 and τ(p,u−p)<τ(p,v−p)\tau(p,u_{-p})<\tau(p,v_{-p}). Recall that the threshold τ(p,u−p)∈I(p,u−p)\tau(p,u_{-p})\in I(p,u_{-p}) is chosen from the interval partition corresponding to the edge (p,u−p)(p,u_{-p}) (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 p∈[d]p\in[d], we will define a total order ≺p\prec_p over z∈{0,1}d−1z\in\{0,1\}^{d-1} so that (≺1,≺2,…,≺d)(\prec_1,\prec_2,\ldots,\prec_d) together have the following property.

Definition 3.2 (Coherent family of orderings). Call total orders (≺1,≺2,…,≺d)(\prec_1,\prec_2,\ldots,\prec_d) over context vectors {0,1}d−1\{0,1\}^{d-1} coherent if the following holds. Let x≠y∈{0,1}dx\ne y\in\{0,1\}^d be any two non-adjacent vertices, i.e. d(x,y)≥2d(x,y)\ge2. Then, there is a coordinate pp on which they differ such that the context of the pp-bit-0 vertex precedes the context of the pp-bit-1 vertex in ≺p\prec_p. I.e. if xp=0x_p=0, yp=1y_p=1, we have x−p≺py−px_{-p}\prec_p y_{-p} and if xp=1x_p=1, yp=0y_p=0, we have y−p≺px−py_{-p}\prec_p x_{-p}.

The existence of a coherent family of total orders (≺1,≺2,…,≺d)(\prec_1,\prec_2,\ldots,\prec_d) (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 p∈[d]p\in[d], let ≺p\prec_p be a total order on the contexts {0,1}[d]∖{p}\{0,1\}^{[d]\setminus\{p\}} defined as follows. For each u,v∈{0,1}[d]∖{p}u,v\in\{0,1\}^{[d]\setminus\{p\}}, look at the first bit qq where they differ. Suppose uq=0u_q=0, vq=1v_q=1. If q<pq<p, then v≺puv\prec_p u. If q>pq>p, then u≺pvu\prec_p v. In other words, ≺p\prec_p is a lexicographic order where all bits before pp use the reversed bit order and all bits after pp use the standard bit order.

Claim 3.4 (Coherence property). The family of orderings (≺1,≺2,…,≺d)(\prec_1,\prec_2,\ldots,\prec_d) defined in Definition 3.3 satisfies the coherence property of Definition 3.2.

Proof. Let a<ba<b be the first two bits where xx and yy differ. First, suppose that xab=00x_{ab}=00, yab=11y_{ab}=11 (the opposite case is symmetric). Observe that bb is the first bit on which the context vectors x−bx_{-b} and y−by_{-b} disagree. Since a<ba<b, we then have x−a≺ay−ax_{-a}\prec_a y_{-a} by definition of the ordering ≺a\prec_a.

Now, suppose xab=01x_{ab}=01, yab=10y_{ab}=10 (again, the opposite case is symmetric). Observe that aa is the first bit on which the context vectors x−bx_{-b} and y−by_{-b} disagree. Since a<ba<b, we then have y−b≺bx−by_{-b}\prec_b x_{-b} by definition of the ordering ≺b\prec_b. □\square

Generalizing beyond the k=2dk=2^d case. We have completed the proof for the case when k=2dk=2^d. We now extend beyond this setting. For simplicity, we will assume k=2ℓk=2^\ell is some power of 2.

  • ℓ<d\ell<d. In this case, we can simply apply the previous construction in ℓ\ell-dimensions and pad the instance with d−ℓd-\ell dummy coordinates. We have ℓ=log⁡2k=min⁡(d,log⁡2k)\ell=\log_2 k=\min(d,\log_2 k), establishing the lower bound claimed in Theorem 3.1.

  • ℓ>d\ell> d. In this case, we create 2ℓ−d2^{\ell-d} copies of the previous construction in dd dimensions, translated along the first coordinate. The nn 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-kk Regime

In § 2, we saw that learning a labeling induced by kk boxes can require at least Ωk(dlog⁡(n/d))\Omega_k(d\log(n/d)) queries when kk 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-kk regime, it is possible to beat the lower bound. The next result, Theorem 3.5, shows that when kk is constant order, there is an upper bound of Ok(dlog⁡(n)/log⁡(d))O_k(d\log(n)/\log(d)) queries for learning the restricted class of disjoint boxes, which shaves off a factor of log⁡(d)\log(d).

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 Ω(kdlog⁡(n/kd))\Omega(kd\log(n/kd)) queries to learn, strictly separating CAL and Halving++.

Theorem 3.5 (Disjoint Boxes). Let d,k≥2d, k \ge2. There is a deterministic algorithm that learns the labeling of a disjoint kk-box partition over a worst-case set of nn points in Rd\mathbb{R}^d using

O(min⁡{n,k3dlog⁡nlog⁡(kd)}) queries.O\left(\min\left\{n,\frac{k^3d\log n}{\log(kd)}\right\}\right)\text{ queries.}

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 ZZ be a finite set and let C⊂{0,1}Z\mathcal{C} \subset\{0,1\}^{Z}. For any h∈{0,1}Zh \in\{0,1\}^{Z}, a subset S⊂ZS \subset Z is a specifying set for hh with respect to the concept class C\mathcal{C} if at most one element f∈Cf \in\mathcal{C} satisfies f(z)=h(z)f(z)=h(z) for all z∈Sz \in S. The extended teaching dimension of C\mathcal{C} is

ETD⁡(C)=max⁡h∈{0,1}Zmin⁡{∣S∣:S is a specifying set for h with respect to C}.\operatorname{ETD}(\mathcal{C})=\max_{h\in\{0,1\}^{Z}}\min\{|S|:S\text{ is a specifying set for }h\text{ with respect to }\mathcal{C}\}.

Theorem 3.7 (Query complexity bound, [Mos82, Heg95]). Let C⊂{0,1}Z\mathcal{C} \subset\{0,1\}^{Z} be a concept class. If ETD⁡(C)≥2\operatorname{ETD}(\mathcal{C}) \ge2 and max⁡{3,ETD⁡(C)}≤E\max\{3,\operatorname{ETD}(\mathcal{C})\}\le E, there is a deterministic algorithm that identifies any concept in C\mathcal{C} using at most

2Elog⁡2∣C∣log⁡2E adaptive coordinate queries.\frac{2E\log_2|\mathcal{C}|}{\log_2 E}\text{ adaptive coordinate queries.}

First, we convert the problem of learning a kk-box partition into one of learning a binary concept class. Let Z=X×[k]Z=X\times[k]. Each labeling f:X→[k]f:X\to[k] is associated to an element of f~∈{0,1}Z\widetilde{f}\in\{0,1\}^{Z}

f~(x,y)=1⟺f(x)=y.\widetilde{f}(x,y)=1\quad\Longleftrightarrow\quad f(x)=y.

Let CXk-DISJ⊂{0,1}Z\mathcal{C}^{k\text{-DISJ}}_X\subset\{0,1\}^{Z} denote the concept class

CXk-DISJ={f~:f is a disjoint k-box partition on X}.(3)\mathcal{C}^{k\text{-DISJ}}_X=\{\widetilde{f}:f\text{ is a disjoint }k\text{-box partition on }X\}. \tag*{(3)}

To recover the ground truth labeling f:X→[k]f:X\to[k], it is enough to recover its associated concept f~\widetilde{f}. Every coordinate query to z=(x,y)z=(x,y) can be simulated by a single label query to xx, so it follows that by running the algorithm from Theorem 3.7 as a black-box, we can learn any ff by making at most

min⁡{n,2Elog⁡2∣CXk-DISJ∣log⁡2E} adaptive label queries,\min\left\{n,\frac{2E\log_2\left|\mathcal{C}^{k\text{-DISJ}}_X\right|}{\log_2 E}\right\}\text{ adaptive label queries,}

where E≥3E \ge3 is any upper bound on the extended teaching dimension. The result follows immediately from Lemmas 3.8 and 3.9 below, which bound ETD⁡(CXk-DISJ)\operatorname{ETD}(C^{k\text{-DISJ}}_X) and ∣CXk-DISJ∣|C^{k\text{-DISJ}}_X|.

Lemma 3.8. Let CXk-DISJC^{k\text{-DISJ}}_X be the class of disjoint kk-box partitions on X⊂RdX \subset\mathbb{R}^d defined in (3). Then:

ETD⁡(CXk-DISJ)≤2kd.\operatorname{ETD}(C^{k\text{-DISJ}}_X) \le2kd.

Proof. Fix any h∈{0,1}Zh \in\{0,1\}^{Z}. While hh is not necessary associated with a disjoint kk-box labeling, but we can still interpret it as assigning each point x∈Xx \in X to a possibly empty set of labels, where the assignment is x↦{y∈[k]:h(x,y)=1}x \mapsto\{y \in[k] : h(x,y)=1\}. There are three cases:

  • If there is an x∈Xx \in X assigned zero labels or strictly more than one label, then the following set S={(x,y):y∈[k]}S = \{(x,y) : y \in[k]\} is a specifying set for hh with respect to CC. No f~∈CXk-DISJ\widetilde{f} \in C^{k\text{-DISJ}}_X such that f~(x,y)=h(x,y)\widetilde{f}(x,y)=h(x,y) for all x∈Sx \in S and y∈[k]y \in[k].

  • Suppose that each x∈Xx \in X is assigned precisely one label. For each y∈[k]y \in[k], let ByB_y be the bounding box of points assigned the label yy by hh. In each dimension of this bounding box, we can let xy,i,Lx_{y,i,L} and xy,i,Rx_{y,i,R} be the left- and rightmost points out of all points labeled yy. Define SS to be the union of these bounding points, so that SS is a set of size at most 2kd2kd. There is precisely one (not necessarily disjoint) box partition that induces the same labeling on SS.

By definition, the extending teaching dimension of CXk-DISJC^{k\text{-DISJ}}_X is at most 2kd2kd.

Lemma 3.9. There are at most (2kdn)(k2)(2kdn)^{\binom{k}{2}} disjoint kk-box partitions on any nn-point set X⊂RdX \subset\mathbb{R}^d.

Proof. Define Θ=X×[d]×{−1,+1}\Theta= X \times[d] \times\{-1,+1\}. We will construct a family of test functions tθ:X→{0,1}t_\theta: X \to\{0,1\} parametrized by θ∈Θ\theta\in\Theta such that the following holds: for any disjoint kk-box labeling f:X→[k]f : X \to[k] and pair of distinct labels y0,y1∈[k]y_0,y_1 \in[k], there is a test function tθt_\theta such that

f(x)=y0⇒tθ(x)=0andf(x)=y1⇒tθ(x)=1.f(x)=y_0 \Rightarrow t_\theta(x)=0 \qquad\text{and} \qquad f(x)=y_1 \Rightarrow t_\theta(x)=1.

Thus, ff is completely determined by a set of (k2)\binom{k}{2} parameters {θ(f,ℓ0,ℓ1):1≤ℓ0<ℓ1≤k}\{\theta(f,\ell_0,\ell_1) : 1 \le\ell_0 < \ell_1 \le k\}, and

∣CXk-DISJ∣≤∣Θ∣(k2).|C^{k\text{-DISJ}}_X| \le|\Theta|^{\binom{k}{2}}.

The claim holds because ∣Θ∣=2dn|\Theta|=2dn. We just need to construct the family of test functions.

For any labeling f:X→[k]f : X \to[k] and pair of distinct labels y0,y1∈[k]y_0,y_1 \in[k], let B0B_0 and B1B_1 respectively be the bounding boxes of points in class y0y_0 and y1y_1. These two boxes are disjoint if and only if there exists a separating dimension i∈[d]i \in[d] such that the projection of these boxes onto the iith dimension is two disjoint intervals. Let x∈X∩B1x \in X \cap B_1 minimize the distance to B0B_0 after projecting to the iith dimension

min⁡x0∈B0∣x0(i)−x(i)∣≤min⁡xj∈X∩Bj∣x0(i)−x1(i)∣.\min_{x_0 \in B_0} |x_0(i)-x(i)| \le\min_{x_j \in X \cap B_j} |x_0(i)-x_1(i)|.

Let s=sign⁡(x(i)−x0(i))s=\operatorname{sign}(x(i)-x_0(i)) for any x0∈B0x_0 \in B_0. This is well-defined because x(i)x(i) is either strictly greater or strictly less than the iith coordinate of every x0∈B0x_0 \in B_0. A simple test to distinguish points in class ℓ0\ell_0 and ℓ1\ell_1 is the following test parametrized by θ=(i,x,s)\theta=(i,x,s)

tθ(x′)=1{s⋅x′(i)≥s⋅x(i)}.t_\theta(x')=\mathbf{1}\{s \cdot x'(i) \ge s \cdot x(i)\}.

By construction, tθ(x0)=0t_\theta(x_0)=0 for all x0∈B0x_0 \in B_0 and tθ(x1)=1t_\theta(x_1)=1 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 kk potentially-overlapping boxes. The proof of Lemma 3.8, which gave a bound of 2kd2kd on the extended teaching dimension, also applies to general boxes; nowhere was disjointness used. The bound on the number of kk-box partitions can be upper bounded by n2kdn^{2kd}, each box can be identified with two endpoints in each dimension. Then, Theorem 3.7 yields

8k2d2log⁡nlog⁡(2kd)\frac{8k^{2}d^{2}\log n}{\log(2kd)}

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 Θ(k2)\Theta(k^{2}) separating hyperplanes, rather than their Θ(kd)\Theta(kd) endpoints.

Decision Trees

In this section we prove our results for decision trees stated in Theorem 1.3.

Definition 4.1 (Decision trees). Let YY be a label set of size ∣Y∣=k≥1|Y| = k \ge1. A function f:Rd→Yf : \mathbb{R}^{d} \to Y is a kk-leaf decision tree if either (a) k=1k = 1, or (b) there exists i∈[d]i \in[d], τ∈R\tau\in\mathbb{R}, and a strict subset ∅≠S⊊Y\varnothing\ne S \subsetneq Y such that the following hold:

  • ff restricted on {x∈Rd:xi≤τ}\{x \in\mathbb{R}^{d} : x_i \le\tau\} is a ∣S∣|S|-leaf decision tree with label set SS and

  • ff restricted on {x∈Rd:xi>τ}\{x \in\mathbb{R}^{d} : x_i > \tau\} is a (k−∣S∣)(k - |S|)-leaf decision tree with label set Y∖SY \setminus S.

A kk-leaf decision list is defined analogously, with the added restriction that ∣S∣=1|S| = 1 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 X⊂RdX \subset\mathbb{R}^{d} be an arbitrary set of nn points. There exists a deterministic algorithm, that exactly learns an arbitrary decision stump f:X→{0,1}f : X \to\{0,1\} using O(d+log⁡n)O(d + \log n) queries. If the input ff is not realizable by a decision stump, the algorithm still halts within the claimed query budget and returns some labeling g:X→{0,1}g : X \to\{0,1\}.

We use stumpLearn(f,X)(f, X) 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 2O(k)(d+log⁡n)2^{O(k)}(d + \log n) upper bound.

Theorem 4.3. Let YY be an arbitrary label-set of size ∣Y∣=k≥1|Y| = k \ge1. There is a deterministic algorithm, which for any set X⊂RdX \subset\mathbb{R}^{d} of nn points, learns an unknown labeling f:X→Yf : X \to Y induced by a kk-leaf decision tree using

22k+O(log⁡2k)(d+log⁡n)=2O(k)(d+log⁡n)2^{2k+O(\log^{2} k)}(d + \log n) = 2^{O(k)}(d + \log n)

queries. If ff is induced by a kk-leaf decision list, then the query complexity is O(k2(d+log⁡n))O(k^{2}(d + \log n)).

Before proving Theorem 4.3, we remark that it is fairly direct to obtain a kO(k)(d+log⁡n)k^{O(k)}(d + \log n) 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 kO(k)(d+log⁡n)k^{O(k)}(d + \log n) query algorithm. Let TT be a binary tree with kk leaves where every non-leaf has exactly two children. Note that there are exactly Ck−1C_{k-1} (the (k−1)(k - 1)-th Catalan number) choices for TT. Then, let ϕ\phi be a bijective map from the label set YY to the leaves of TT (there are k!k! such maps). For a node uu in TT, let Y⊆YY \subseteq Y denote the set of labels associated by ϕ\phi to some leaf-descendant of uu. Now, for each of the k−1k - 1 non-leaf nodes uu, run stumpLearn (Theorem 4.2) with Boolean oracle gu(x)=1(f(x)∈YrightT(u))g_u(x) = 1(f(x) \in Y_{\mathrm{right}_{T}(u)}). Combining the outputs of these calls to the stump learner yields a candidate labeling fT,ϕ:X→Yf_{T,\phi} : X \to Y. By Definition 4.1, there exists at least one choice of (T,ϕ)(T,\phi) such that fT,ϕ=ff_{T,\phi} = f. It is then straightforward to determine which of these Ck−1k!C_{k-1}k! candidate labelings is the correct one using at most one query per candidate. The total query complexity is

O(Ck−1k!(d+log⁡n))=kO(k)(d+log⁡n).O(C_{k-1}k!(d + \log n)) = k^{O(k)}(d + \log n).

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 YY, there exists ∅⊂A∗⊂Y\varnothing\subset A^* \subset Y where the root-level partition on the labels is (A∗,Y∖A∗)(A^*, Y \setminus A^*) such that ∣A∗∣≤⌊∣Y∣/2⌋\lvert A^* \rvert\le\lfloor\lvert Y \rvert/2 \rfloor. As a result, the recurrence governing the query complexity has the form Q(k)≲2kQ(k/2)Q(k) \lesssim2^k Q(k/2).

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 f:X→Yf : X \to Y be a labeling induced by a box partition, Z⊆XZ \subseteq X, and y∈Yy \in Y. There is a deterministic procedure monoCert(f,Z,y)(f, Z, y) using at most 2d2d queries that decides whether or not f∣Z≡yf|_Z \equiv y.

Proof. The procedure simply queries all points in the set

EZ={arg⁡min⁡z∈Z zi,arg⁡max⁡z∈Z zi:i∈[d]}E_Z = \left\{ \underset{z \in Z}{\arg\min}\ z_i, \underset{z \in Z}{\arg\max}\ z_i : i \in[d] \right\}

of extremal points in ZZ with respect to each coordinate. Clearly ∣EZ∣≤2d\lvert E_Z \rvert\le2d. We then accept if and only if f∣EZ≡yf|_{E_Z} \equiv y. Clearly, if f∣EZ≢yf|_{E_Z} \not\equiv y, then f∣Z≢yf|_Z \not\equiv y. Conversely, since Z⊆bbox⁡(EZ)Z \subseteq\operatorname{bbox}(E_Z), if f∣EZ≡yf|_{E_Z} \equiv y, then f∣Z≡yf|_Z \equiv y. □\square

Given f:X→Yf : X \to Y, our algorithm is defined recursively as follows.

DTLearn(f,X,Y)(f, X, Y):

  1. Base cases. If X=∅X = \varnothing, return the empty labeling. If Y={y}Y = \{y\}, run monoCert(f,X,y)(f, X, y) (Claim 4.5). If it accepts, return the constant labeling f∣X≡yf|_X \equiv y, otherwise return FAIL.

  2. If ∣Y∣=k≥2\lvert Y \rvert= k \ge2, then let R←XR \leftarrow X and repeat the following procedure defined in item (3) kk times, or until R=∅R = \varnothing. (See line (3e).)

  3. For every A⊂YA \subset Y where 1≤∣A∣≤⌊k/2⌋1 \le\lvert A \rvert\le\lfloor k/2 \rfloor, do the following: (a) Define gA:R→{0,1}g_A : R \to\{0,1\} where gA(x)=1(f(x)∈A)g_A(x) = 1(f(x) \in A). (b) Run stumpLearn(gA,R)(g_A, R) and let g~A\widetilde{g}_A denote the returned Boolean labeling. (c) Let XA={x∈R:g~A(x)=1}X_A = \{x \in R : \widetilde{g}_A(x) = 1\}. (d) Run DTLearn(f∣XA,XA,A)(f|_{X_A}, X_A, A). If it returns FAIL, then continue. If it returns a labeling hA:XA→Ah_A : X_A \to A, then assign these labels to XAX_A and set R←R∖XAR \leftarrow R \setminus X_A. (e) If R=∅R = \varnothing, return the accumulated labeling on the original input set.

  4. If after kk repetitions of item (3), we have R≠∅R \ne\varnothing, then return FAIL.

Before proving correctness, we give some intuition for the above learner. Since ff is a decision tree, for some choice of AA in line (3), the Boolean labeling gAg_A in line (3a) is a decision stump. By correctness of the decision stump learner, this implies that f∣XAf|_{X_A} is a ∣A∣\lvert A\rvert-leaf decision tree and thus by induction the points in XAX_A are correctly labeled in line (3d). This removes at least one of the kk classes from RR, which is the reason that at most kk repetitions of (3) are needed. Importantly, even when gAg_A 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 f:X→Yf:X\to Y satisfies f−1(y)=X∩Byf^{-1}(y)=X\cap B_y where {By:y∈Y}\{B_y:y\in Y\} are disjoint axis-parallel boxes. Let Y′Y' be a candidate label set for ff. If DT Learn(f,X,Y′)(f,X,Y') returns a labeling hh, then f=hf=h.

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 Y′Y' contains all true labels. A complete labeling is returned only after every point has received a label.

Lemma 4.7 (Correctness). Suppose f:X→Yf:X\to Y is induced by a ℓ\ell-leaf decision tree where ℓ≤∣Y∣\ell\leq|Y|. Then DT Learn(f,X,Y)(f,X,Y) always returns the correct labeling ff.

Proof. The proof is by induction on k=∣Y∣k=|Y|. The case X=∅X=\emptyset is clear and the case k=1k=1 follows from Claim 4.5. Now, let k≥2k\geq2. Consider the set RR defined in line (2) and consider some iteration of step (3) in which R≠∅R\ne\emptyset. We argue that one iteration of step (3) correctly labels all points in at least one of the kk labels. (Therefore, kk repetitions are enough, as claimed in line (2).) Note that by Lemma 4.6, a recursive call will never incorrectly label points.

First, suppose f∣R≡yf|_R\equiv y is constant, for some y∈Yy\in Y. Then, in step (3), the algorithm will try A={y}A=\{y\}, in which g{y}≡1g_{\{y\}}\equiv1 (in line (3a)). This will result stumpLearn(g{y},R)(g_{\{y\}},R) returning the all-1 labeling of RR and sets XA=RX_A=R in line (3c). Line (3d) then invokes the base case, accepts, and labels all of RR.

Now, suppose RR contains at least 2 labels from YY. Note that f∣R:R→Yf|_R:R\to Y is itself induced by a k′k'-leaf decision tree where k′≤kk'\leq k (this holds for any subset of XX). Therefore, there exists some A∗⊂YA^*\subset Y where 1≤∣A∗∣≤⌊k/2⌋1\leq|A^*|\leq\lfloor k/2\rfloor such that either f(x)∈A∗f(x)\in A^* iff xi≤τx_i\leq\tau (for some i,τi,\tau) or f(x)∈A∗f(x)\in A^* iff xi>τx_i>\tau. In some iteration of line (3), the algorithm tries this A∗A^*. The guarantee of stumpLearn(gA∗,R)(g_{A^*},R) (Theorem 4.2) implies that g^A∗=gA∗\widehat{g}_{A^*}=g_{A^*} and thus XA∗={x∈R:f(x)∈A∗}X_{A^*}=\{x\in R:f(x)\in A^*\}. By induction, the recursive call to DT Learn(f∣XA∗,XA∗,A∗)(f|_{X_{A^*}},X_{A^*},A^*) successfully returns a labeling on XA∗X_{A^*}, which by Lemma 4.6 is guaranteed to be correct. Therefore, at the end of step (3d) all points with labels in A∗A^* are removed from RR.

We have shown that every repetition of line (3) successfully learns at least one of the kk labels. Combining with Lemma 4.6, this shows that after at most kk repetitions, the algorithm returns the correct labeling, ff.

Query Complexity Proof

We derive the query complexity of DT Learn as follows. Fix dd and nn. Let qs=O(d+log⁡n)q_s=O(d+\log n) denote the query complexity of the stump learner in dd-dimensions over nn points and let qc=2dq_c=2d denote the query complexity of the monochromatic certification. For k≥1k\geq1, let Q(k)Q(k) denote the query complexity of DT Learn on nn points in dd dimensions with kk labels. Then, by inspection, QQ satisfies the following recurrence relation:

Q(1)≤qc and Q(k)≤k2k(qs+Q(⌊k/2⌋)) when k≥2.(4)Q(1)\leq q_c\text{ and }Q(k)\leq k2^k\left(q_s+Q\left(\left\lfloor k/2\right\rfloor\right)\right)\text{ when }k\geq2. \tag*{(4)}

We now bound the recurrence, which establishes the claimed query complexity. We can expand the recurrence for k≥2k\geq2 as follows:

Q(k)≤k2k(qs+Q(⌊k/2⌋))≤k2kqs+k2k(k2⋅2k/2(qs+Q(⌊⌊k/2⌋/2⌋))) ⋮≤(qs+qc)∑t=0⌊log⁡2k⌋(∏j=0tk2j2k/2j)(5)\begin{aligned} Q(k)&\leq k2^k\left(q_s+Q\left(\left\lfloor k/2\right\rfloor\right)\right)\\ &\leq k2^kq_s+k2^k\left(\frac{k}{2}\cdot2^{k/2}\left(q_s+Q\left(\left\lfloor\left\lfloor k/2\right\rfloor/2\right\rfloor\right)\right)\right)\\ &\ \vdots\\ &\leq(q_s+q_c)\sum_{t=0}^{\lfloor\log_2 k\rfloor}\left(\prod_{j=0}^{t}\frac{k}{2^j}2^{k/2^j}\right) \tag*{(5)} \end{aligned}

Using upper bounds t≤⌊log⁡2k⌋t \le\lfloor\log_{2} k \rfloor and k/2j≤kk/2^{j} \le k shows that the RHS above is at most

(qs+qc)⋅(log⁡2k+1)⋅∏j=0⌊log⁡2k⌋k2k/2j≤(qs+qc)(log⁡2k+1)⋅klog⁡2k+1⋅22k≤22k+O(log⁡2k)⋅(qs+qc)(6)(q_s + q_c) \cdot(\log_{2} k + 1) \cdot\prod_{j=0}^{\lfloor\log_{2} k \rfloor} k^{2k/2^{j}} \le(q_s + q_c)(\log_{2} k + 1) \cdot k^{\log_{2} k+1} \cdot2^{2k} \le2^{2k+O(\log^{2} k)} \cdot(q_s + q_c) \tag*{(6)}

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 AA. The algorithm is correct by the same arguments in Lemma 4.6 and Lemma 4.7. The algorithm correctly learns the labeling simply after kk repetitions of step (3) and only ever recurses on a singleton set of labels. Therefore, by inspection the query complexity is at most k2(qs+qc)k^{2}(q_s + q_c).

Lower Bound

We now prove an elementary lower bound establishing optimality of our algorithm for constant kk.

Theorem 4.8 (Decision List Lower Bound). Let d,k≥2d, k \ge2. There exists set X⊂RdX \subset\mathbb{R}^{d} of n≥d(k−1)n \ge d(k - 1) points such that any randomized adaptive algorithm that learns a labeling f:X→[k]f : X \to[k] induced by a kk-leaf decision list with success probability at least 2/32/3 must use Ω(k(d+log⁡(n/k)))\Omega(k(d + \log(n/k))) queries.

Proof. It suffices to prove an Ω(kd)\Omega(kd) lower bound and a Ω(klog⁡(n/k))\Omega(k\log(n/k)) lower bound separately.

The Ω(kd)\Omega(kd) bound. We first describe the construction for n=d(k−1)n = d(k - 1) points. Let U={e1,…,ed}U = \{e_1, \ldots, e_d\} denote the standard unit basis vectors. For a vector vv, let U+v={u+v:u∈U}U + v = \{u + v : u \in U\}. For a scalar c∈Rc \in\mathbb{R}, let cˉ=(c,c,…,c)∈Rd\bar{c} = (c, c, \ldots, c) \in\mathbb{R}^{d}. Our point-set XX is defined

X:=⋃y=1k−1(U+yˉ).X := \bigcup_{y=1}^{k-1}(U + \bar{y}).

Then, we consider the family of decision lists formed as follows. For each y∈[k−1]y \in[k - 1], choose a dimension iy∈[d]i_y \in[d]. Given α=(i1,…,ik−1)∈[d]k−1\alpha= (i_1, \ldots, i_{k-1}) \in[d]^{k-1}, we then define fα:Rd→[k]f_{\alpha} : \mathbb{R}^{d} \to[k] as

fα(x)=min⁡({y∈[k−1]:xiy≤y+0.5}∪{k}).f_{\alpha}(x) = \min\left(\{y \in[k - 1] : x_{i_y} \le y + 0.5\} \cup\{k\}\right).

To reach any n≥d(k−1)n \ge d(k - 1) points, we can pad the point-set with n−d(k−1)n - d(k - 1) arbitrary points zz such that zi>kz_i > k for all i∈[d]i \in[d].

Observe that such a labeling is a valid decision list (Definition 4.1). The key property of this construction is the following: for each y∈[k−1]y \in[k - 1], f(eiy+yˉ)=y+1f(e_{i_y} + \bar{y}) = y + 1 and f(ei+yˉ)=yf(e_i + \bar{y}) = y for all i∈[d]∖{iy}i \in[d] \setminus\{i_y\}. Therefore, learning the Boolean labeling in U+yˉU + \bar{y} requires solving an unstructured search problem on dd elements, which requires Ω(d)\Omega(d) queries for any randomized algorithm. Summing over U+yˉU + \bar{y} for each y∈[k−1]y \in[k - 1] shows that Ω(kd)\Omega(kd) queries are needed.

The Ω(klog⁡(n/k))\Omega(k\log(n/k)) bound. Assume nn is a multiple of k−1k - 1. It suffices to prove a lower bound for learning monotone functions f:[n]→[k]f : [n] \to[k]. First, when k=2k = 2, a lower bound of Ω(log⁡n)\Omega(\log n) holds by a standard information-theoretic argument, since one needs to find a threshold in one of nn possible locations using queries that return a single bit of information.

Now, consider the following family of monotone functions. First, partition [n][n] into k−1k - 1 intervals I1,…,Ik−1I_1, \ldots, I_{k-1} of length n/(k−1)n/(k - 1). In interval IyI_y, we allow the function to take values in {y,y+1}\{y, y + 1\}. Learning such a function requires the algorithm to learn the correct Boolean function restricted on each IyI_y and crucially a query to x∈Iyx \in I_y gives no information about the function on any other interval. Thus, leveraging the k=2k = 2 lower bound, we obtain a lower bound of

(k−1)⋅Ω(log⁡(nk−1))=Ω(klog⁡(n/k))(k - 1) \cdot\Omega\left(\log\left(\frac{n}{k - 1}\right)\right) = \Omega(k\log(n/k))

and this completes the proof. □\square

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 kk boxes. Consider any set of points XX with initially unknown labels. This lemma shows that if we label a random subset of points Z⊆XZ \subseteq X of size O(kdm)O(kdm), then in expectation, we will be able to deduce the labels for all but a O(1m)O\left(\frac{1}{m}\right)-fraction of points in XX.

Lemma A.1 (Expected coverage of a random set). Let X⊂RdX \subset\mathbb{R}^{d} be a set of ∣X∣=n|X| = n points and let f:X→[k]f : X \to[k] be a labeling induced by kk boxes. Given a fixed integer 0≤m≤n0 \le m \le n, let Z⊆XZ \subseteq X be a random subset of XX of size exactly mm. Let QQ be a random variable denoting the number of points whose label cannot be inferred from f(Z)f(Z). Then,

EZ[Q]≤2d∑j=1kmin⁡(∣f−1(j)∣,n−mm+1)≤2dk⋅n−mm+1.\mathbb{E}_{Z}[Q] \le2d \sum_{j=1}^{k} \min\left(\left|f^{-1}(j)\right|,\frac{n-m}{m+1}\right) \le2dk \cdot\frac{n-m}{m+1}.

Proof. For each label y∈[k]y \in[k], define XyX_y and ZyZ_y to be the points with label yy in XX and ZZ, respectively. Let ny=∣Xy∣n_y = |X_y| be the number of points in XyX_y. Let Q=∑yQyQ = \sum_y Q_y where QyQ_y is the number of points in XyX_y whose label cannot be inferred from the labels f(Z)f(Z), where

the label f(x)=y can be inferred from f(Z)⟺x∈bbox⁡(Zy)=∏i=1d[ay,i,by,i].\text{the label } f(x)=y \text{ can be inferred from } f(Z) \Longleftrightarrow x \in\operatorname{bbox}(Z_y)=\prod_{i=1}^{d}[a_{y,i},b_{y,i}].

For each dimension i∈[d]i \in[d], we also count the number of points in XyX_y that land to the left and right of bbox⁡(Zy)\operatorname{bbox}(Z_y) in the iith dimension:

Ly,i=#{x∈Xy:xi<ay,i}andRy,i=#{x∈Xy:xi>by,i}.L_{y,i}=\#\{x\in X_y:x_i<a_{y,i}\}\qquad\text{and}\qquad R_{y,i}=\#\{x\in X_y:x_i>b_{y,i}\}.

When Zy=∅Z_y=\emptyset, we use the convention Ly,i=Ry,i=nyL_{y,i}=R_{y,i}=n_y. We can upper bound QyQ_y by the sum

Qy≤∑i=1dLy,i+Ry,i.Q_y\leq\sum_{i=1}^{d}L_{y,i}+R_{y,i}.

We now bound EZ[Ly,i]\mathbb{E}_Z[L_{y,i}]. The bound on EZ[Ry,i]\mathbb{E}_Z[R_{y,i}] is the same and has an analogous argument. For each dimension i∈[d]i\in[d], let rank⁡y,i(x)\operatorname{rank}_{y,i}(x) denote the ordering of the points x∈Xyx\in X_y with respect to the iith coordinate, breaking ties arbitrarily. For each integer ℓ≥0\ell\geq0, define the ℓ\ell leftmost set of points under this ordering to be Xy,i≤ℓ={x∈Xy:rank⁡y,i(x)≤ℓ}X_{y,i}^{\leq\ell}=\{x\in X_y:\operatorname{rank}_{y,i}(x)\leq\ell\}. Then:

Ly,i≥ℓ⟹Z∩Xy,i≤ℓ=∅.L_{y,i}\geq\ell\qquad\Longrightarrow\qquad Z\cap X_{y,i}^{\leq\ell}=\emptyset.

To see this, suppose that Ly,i≥ℓL_{y,i}\geq\ell. Every point z∈Zyz\in Z_y must strictly dominate a set of Ly,iL_{y,i} points with respect to rank⁡y,i\operatorname{rank}_{y,i}, which means that rank⁡y,i(z)>ℓ\operatorname{rank}_{y,i}(z)>\ell. As ZZ is chosen uniformly at random,

Pr⁡Z[Ly,i≥ℓ]≤Pr⁡Z[Z∩Xy,i≤ℓ=∅]≤(n−ℓm)(nm),for all 1≤ℓ≤ny.\Pr_Z\left[L_{y,i}\geq\ell\right]\leq\Pr_Z\left[Z\cap X_{y,i}^{\leq\ell}=\emptyset\right]\leq\frac{\binom{n-\ell}{m}}{\binom{n}{m}},\qquad\text{for all }1\leq\ell\leq n_y.

The last inequality holds because ZZ must miss a set of size ℓ\ell. Using a layer-cake representation and applying the hockey-stick identity, we obtain

EZ[Ly,i]≤∑ℓ=1n−mPr⁡Z[Ly,i≥ℓ]≤∑ℓ=1n−m(n−ℓm)(nm)=∑t=mn−1(tm)(nm)=(nm+1)(nm)=n−mm+1.\mathbb{E}_Z[L_{y,i}]\leq\sum_{\ell=1}^{n-m}\Pr_Z\left[L_{y,i}\geq\ell\right]\leq\sum_{\ell=1}^{n-m}\frac{\binom{n-\ell}{m}}{\binom{n}{m}}=\sum_{t=m}^{n-1}\frac{\binom{t}{m}}{\binom{n}{m}}=\frac{\binom{n}{m+1}}{\binom{n}{m}}=\frac{n-m}{m+1}.

Putting everything together observing that Qy≤nyQ_y\leq n_y always holds, we have

EZ[Q]=∑y∈[k]EZ[Qy]≤2d∑y∈[k]min⁡{ny,n−mm+1},\mathbb{E}_Z[Q]=\sum_{y\in[k]}\mathbb{E}_Z[Q_y]\leq2d\sum_{y\in[k]}\min\left\{n_y,\frac{n-m}{m+1}\right\},

which completes the proof. □\square

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 π:[n]→X\pi:[n]\to X, then batch the points into rr sets. In the tt-th round where 1≤t≤r1\leq t\leq r, query all points in the tt-th batch whose labels cannot already be inferred from previous queries. We will fix a sequence of rr batch sizes so that the expected query complexity over π\pi is minimized. Towards this, given an arbitrary schedule

0=s0<s1<⋯<sr=n,0=s_0<s_1<\cdots<s_r=n,

the tt-th batch will be (π(i):st−1<i≤st)(\pi(i): s_{t-1}<i\le s_t). We first obtain an expression for the expected query complexity of a general schedule using Lemma A.1. For 1≤t≤r1\le t\le r, let QtQ_t be the random variable denoting the number of queries made in the tt-th round (over the randomness of π\pi). For t≥2t\ge2, conditioned on Y⊆XY\subseteq X being the first ∣Y∣=st|Y|=s_t points in the ordering induced by π\pi, the first st−1s_{t-1} such points form a uniformly random subset of YY of size st−1s_{t-1}. Therefore, to bound Eπ[Qt]\mathbb{E}_{\pi}[Q_t] we can simply apply Lemma A.1 with st,st−1s_t,s_{t-1} playing the roles of n,mn,m respectively. We obtain

Eπ[Q]=s1+∑t=2rEπ[Qt]≤s1+2dk∑t=2rst−st−1st−1+1≤s1+2dk∑t=2rstst−1+1(7)\mathbb{E}_{\pi}[Q]=s_1+\sum_{t=2}^{r}\mathbb{E}_{\pi}[Q_t]\le s_1+2dk\sum_{t=2}^{r}\frac{s_t-s_{t-1}}{s_{t-1}+1}\le s_1+2dk\sum_{t=2}^{r}\frac{s_t}{s_{t-1}+1} \tag*{(7)}

To choose a schedule that optimizes the above expected query complexity, for each 1≤t≤r1\le t\le r, set

st=⌊2dk⋅(n2dk)t/r⌋.(8)s_t=\left\lfloor2dk\cdot\left(\frac{n}{2dk}\right)^{t/r}\right\rfloor. \tag*{(8)}

Substituting this into Equation (7) yields

Eπ[Q]≤2dk⋅(n2dk)1/r+2dk∑t=2r(n2dk)1/r=2dkr(n2dk)1/r\mathbb{E}_{\pi}[Q]\le2dk\cdot\left(\frac{n}{2dk}\right)^{1/r}+2dk\sum_{t=2}^{r}\left(\frac{n}{2dk}\right)^{1/r}=2dkr\left(\frac{n}{2dk}\right)^{1/r}

as claimed.

Remark A.2. The optimal O(kdlog⁡(n/dk))O(kd\log(n/dk)) query complexity can be obtained by setting the round complexity to only r=log⁡2(n/2dk)r=\log_2(n/2dk) in Theorem 2.2. From Equation (8) in the proof, we see that the tt-th round considers points in a batch of size

st−st−1≈2dk⋅2t−1s_t-s_{t-1}\approx2dk\cdot2^{t-1}

and the number of queries made in that batch is expected to be

≲2dk⋅stst−1≈2kd.\lesssim2dk\cdot\frac{s_t}{s_{t-1}}\approx2kd.

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 k=O(1)k=O(1) as a constant, they are

CAL: Ok(dlog⁡(n/d))O_k(d\log(n/d)) queries \hspace{2em} Halving++: Ok(dlog⁡(n)/log⁡(d))O_k(d\log(n)/\log(d)) queries.

While it seems that Halving++ attains a log⁡(d)\log(d)-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 n=d2n=d^2, then CAL requires Ω(dlog⁡d)\Omega(d\log d) queries. In contrast, for the same problem, the above query complexity of the more careful Halving++ algorithm resolves to O(d)O(d) queries.

Proposition B.1 (Query lower bound for CAL). Let k≥2k\ge2. There is an nn-point set XX in Rd\mathbb{R}^d so that the expected number of queries that CAL requires to learn any kk-disjoint box partition over XX is

Ω(kdlog⁡(n/kd)) queries.\Omega(kd\log(n/kd))\text{ queries}.

Proof. We first give a proof when k=2k = 2 and d=1d = 1. Let X=[n]X = [n]. Unbeknownst to the learner, let the labeling f(x)≡yf(x) \equiv y 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 (qt)t(q_t)_t. At the end of round tt, it can infer the labels of points only in the set

X∩bbox⁡(q1,…,qt).X \cap\operatorname{bbox}(q_1,\ldots,q_t).

This is because any point x∈X∖bbox⁡(q1,…,qt)x \in X \setminus\operatorname{bbox}(q_1,\ldots,q_t) 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 xx a different label. And so, in the next round, CAL chooses qt+1q_{t+1} 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 XX. It follows that the query complexity QCALQ_{\mathrm{CAL}} of CAL for this problem instance is simply the amount of time it takes for the bounding box over the queries to cover XX.

We can compute the expectation E[QCAL]\mathbb{E}[Q_{\mathrm{CAL}}] as follows. Let π:[n]→X\pi: [n] \to X be a random ordering of the points in XX, where CAL iterates through π(s)\pi(s) and queries it if it cannot yet infer its label. Notice that CAL will query a point i∈Xi \in X if it has not previously a point to the left:

∀j<i,π−1(i)<π−1(j)⟹CAL queries i.\forall j < i,\quad\pi^{-1}(i) < \pi^{-1}(j) \quad\Longrightarrow\quad\text{CAL queries } i.

Since the ordering is random, we have

E[QCAL]≥∑i=1nPr⁡(CAL queries i)≥∑i=1n1i=H(n),\mathbb{E}[Q_{\mathrm{CAL}}] \ge\sum_{i=1}^{n} \Pr(\text{CAL queries } i) \ge\sum_{i=1}^{n} \frac{1}{i} = H(n),

where H(n)≥log⁡(n)H(n) \ge\log(n) is the nnth harmonic number.

In higher dimensions, we can improve the bound by making a copy for each dimension. Define

X=⋃i=1d{αei:α∈[n/d]}.X = \bigcup_{i=1}^{d} \{\alpha e_i : \alpha\in[n/d]\}.

When k=2k = 2, let f(x)≡yf(x) \equiv y 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 bbox⁡(q1,…,qt)\operatorname{bbox}(q_1,\ldots,q_t) from any point from XX not contained in it. Notice that if CAL queries a point αei\alpha e_i lying along the iith dimension, the bounding box only grows in the iith dimension, and so we may treat each dimension independently. This gives a lower bound

E[QCAL]≥dlog⁡(n/d).\mathbb{E}[Q_{\mathrm{CAL}}] \ge d\log(n/d).

Finally, with general k≥2k \ge2, we can make (k−1)(k - 1) translated copies of this construction, where each copy is assigned a separate label. The same argument yields the claimed lower bound

E[QCAL]≥(k−1)dlog⁡(n/kd).\mathbb{E}[Q_{\mathrm{CAL}}] \ge(k - 1)d\log(n/kd).

References

  1. [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. [2][Ang87] Dana Angluin. Queries and concept learning. Mach. Learn., 2(4):319–342, 1987. 3, 7
  3. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_vnk3gsaz
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 5.6

View statement
Looking for related papers…
Contents