PaperlayerView exact revision on arXiv

Source-linked AI summary

Query Complexity of Learning Axis-Aligned Partitions

Hadley Black, Arya Mazumdar, Barna Saha, Geelon So

arXiv:2610.35495v1cs.DScs.CGcs.LG

TL;DR

The paper asks how many label queries are needed to exactly learn box partitions over finite point sets, and how geometric structure affects that cost. It analyzes classic active-learning algorithms across unrestricted, disjoint, and decision-tree-induced boxes, establishing tight bounds in key regimes.

  • Problem

    The paper studies the query complexity of exactly recovering labels on a finite point set when labels are induced by boxes.

    Source: §1 · p. 3

  • Method

    The authors analyze classic active-learning algorithms and construct lower bounds across box-partition classes with different structural assumptions.

    Source: §1.1 · p. 3

  • Results

    For disjoint boxes, bounds match the general-box rate when k is large, while constant k can yield a log(d)-factor improvement; intermediate-k bounds remain unresolved.

    Source: §1.1 · p. 4, §1.2 · p. 6, §1.3 · p. 7

  • Takeaways & Limitations

    The results show that disjointness can be exploited for constant k, and constant-sized decision trees have additive Θ_k(d + log n) query complexity.

    Source: §1.1 · pp. 4–5

    Bounds for disjoint boxes are not tight when k < 2^o(d), and the true dependence on k for decision-tree learning remains open.

    Source: §1.3 · p. 7

Abstract

from arXiv · show

This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $\Theta(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Heged\"{u}s 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $\Theta(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.

1 Introduction

The paper studies exact label-query learning of box partitions over finite point sets, comparing unrestricted boxes, disjoint boxes, and decision-tree-induced partitions. It establishes query bounds across these settings and examines how geometric structure changes the achievable complexity.

1.1 Main Results

  • Θ(kd log(n/kd)) queries are necessary and sufficient for learning general box partitions, with lower bounds holding even against randomized algorithms.CAL achieves the optimal query complexity, including in a round-constrained variant.Source: §1.1 · pp. 3–4
  • For disjoint boxes, CAL remains minimax-optimal when k ≥ 2^Ω(d), while Halving++ can save a log(d) factor when k is constant.Halving++ leverages an alternative specification by Θ(k^2) separating halfspaces, unlike CAL's reliance on the boxes' 2kd face thresholds.Source: §1.1 · p. 4, §1.2 · p. 6
  • For constant-sized decision trees, query complexity is Θ_k(d + log n), an additive bound that improves on the multiplicative general-box lower bound.The upper bound is 2^O(k)(d + log n); decision lists have an O(k^2(d + log n)) upper bound and an Ω(k(d + log(n/k))) lower bound when n ≥ d.Source: §1.1 · p. 5

1.2 Technical Overview

  • The lower-bound constructions embed independent one-dimensional threshold-learning problems into box-learning instances; general boxes embed Θ(kd) problems of size Θ(n/kd).For disjoint boxes with k = 2d, the construction places points along Boolean-hypercube edges and designs configurations to preserve independence.Source: §1.2 · pp. 5–6
  • For decision trees, recursive certification of correct label splits reduces the k-dependence to 2^O(k), avoiding brute-force enumeration of candidate trees.Knowing the label splits would yield an O(k(d + log n)) learner by applying a decision-stump learner at each level.Source: §1.2 · p. 6

1.3 Open Questions

  • Bounds for disjoint boxes are not tight when k < 2^o(d), leaving the intermediate-k regime as an open direction.The paper identifies sharper bounds that exploit disjointness geometry as a future research direction.Source: §1.3 · p. 7
  • The true dependence on k for decision-tree partitions remains open, despite tight bounds for any constant number of classes.Source: §1.3 · p. 7

1.4 Related Work

  • The work complements prior general-box and decision-stump results, including O(kd log k log n) queries for general boxes and Θ(d + log n) for axis-aligned halfspaces.The paper attributes its main contributions to lower-bound constructions and gives minimax-optimal learners for general boxes and constant-class tree partitions.Source: §1.4 · p. 7

2 General Box Partitions

This section establishes query bounds for learning general box partitions, including potentially overlapping boxes. CAL supplies the upper bound, while reductions from independent threshold problems establish lower bounds, including for round-limited learning.

2.1 Learning General Box Partitions

  • CAL learns arbitrary k-box partitions with at most 4kd log(1 + n/kd) expected label queries.It maintains the disagreement region and queries an unresolved point; labeled-point bounding boxes let it infer labels for other points.Source: §2.1 · p. 8
  • With r rounds, a randomized algorithm learns arbitrary box partitions using the query bound of Theorem 2.2; at r = log(n/2dk), it recovers the optimal query rate.At that round budget, the query complexity is O(kd log(n/kd)), with Θ(kd) fewer rounds than Theorem 2.1.Source: §2.1 · p. 9

2.2 Matching Lower Bound

  • For even k,d, any randomized learner needs Ω(kd log m) expected queries on some instance, and Ω(rkdm^1/r) with r rounds.The lower-bound construction embeds independent threshold problems into a box partition.Source: §2.2 · pp. 9, 11
  • The lower-bound reduction encodes each threshold across paired coordinates, then uses translated copies to embed independent threshold problems for general k.Each box-learning query can be simulated by a threshold-oracle query, preserving the lower bound.Source: §2.2 · pp. 10–11

3 Disjoint Box Partitions

For disjoint box partitions, the section proves a lower bound matching the general-box rate when k is large, but gives a faster algorithm when k is constant. The lower-bound construction embeds independent threshold problems using a coherent family of orderings.

3.1 Matching Lower Bound in the Large-k Regime

  • When k ≥ 2d, disjoint-box learning requires Ω(kd log m) expected queries on some instance, matching the general-box upper-bound rate.The construction embeds Θ(kd) independent threshold problems; coherent orderings of context vectors make the threshold choices compatible with disjoint boxes.Source: §3.1 · pp. 11, 13
  • The large-k lower bound begins with k = 2^d, placing points along hypercube edges to encode threshold problems and extending a disjoint box from each vertex.The construction generalizes to other k by padding dimensions or translating copies.Source: §3.1 · pp. 11, 13, 14

3.2 Beating the General Box Lower Bound in the Small-k Regime

  • For constant k, disjoint boxes admit an upper bound of O(kd log(n)/log(d)) queries, improving by a log(d) factor over the general-box lower bound.The algorithm, Halving++, selects particularly informative points to query; CAL can require Ω(kd log(n/kd)) queries on some disjoint-box problems.Source: §3.2 · p. 14
  • Halving++ uses an extended-teaching-dimension argument by converting box labelings into a binary concept class over X × [k].Each coordinate query in that class can be simulated by one label query.Source: §3.2 · p. 14

X ) and |Ck-DISJ

The ETD argument bounds the extended teaching dimension of disjoint box partitions by 2kd, using separating tests for pairs of labels. Combined with a bound on the number of partitions, it yields an upper bound that the authors note is worse than Theorem 1.1.

X ) and |Ck-DISJ

  • The extended teaching dimension of disjoint k-box partitions is at most 2kd.For two labels, a separating dimension and a suitably chosen point define a test distinguishing their classes.Source: X ) and |Ck-DISJ · p. 15
  • The ETD argument also applies to general boxes, since its bound does not use disjointness.The resulting query upper bound is 8k²d² log n log(2kd).Source: X ) and |Ck-DISJ · pp. 15–16
  • The resulting upper bound is worse than Theorem 1.1, though the authors suggest its analysis may be loose.For disjoint boxes, the savings intuitively rely on distinguishing boxes with Θ(k²) separating hyperplanes rather than Θ(kd) endpoints.Source: X ) and |Ck-DISJ · p. 16

4 Decision Trees

A k-leaf decision tree recursively splits coordinates at thresholds, assigning labels to leaves. The section gives a recursive learner, proves its correctness and query bounds, and establishes a decision-list lower bound.

4.1.2 Query Complexity Proof

  • The decision-tree learner uses 2^O(k)(d + log n) queries; for k-leaf decision lists, its modified version uses O(k^2(d + log n)) queries.The decision-list version tries only singleton label sets when splitting.Source: §4.1 · p. 16, §4.1.2 · p. 19

4.1 Decision Tree Learner

  • The simple alternative enumerates binary tree shapes and label assignments, runs stump learning at internal nodes, and tests each candidate with at most one query.The improved learner avoids guessing the entire tree at once by making progress through singleton-label certification and balanced label splits.Source: §4.1 · pp. 16–17
  • The learner applies a stump learner to candidate label splits, recurses on the resulting subsets, and certifies singleton-label subsets using at most 2d queries.Certification checks extremal points in each coordinate; recursive progress removes at least one label class per successful iteration.Source: §4.1 · p. 17

4.1.1 Correctness Proof

  • A successful return is sound, and on any labeling induced by a tree with at most |Y| leaves, DTLearn returns the correct labeling.The proof combines sound singleton certifications with a split that removes at least one label class in each successful iteration.Source: §4.1.1 · p. 18

4.2 Lower Bound

  • Any randomized adaptive learner needs Ω(k(d + log(n/k))) queries on some instances of k-leaf decision lists.The construction embeds independent unstructured searches to establish an Ω(kd) component of the bound.Source: §4.2 · p. 19

AI Disclosure

The authors report using ChatGPT 5.6 to explore proof ideas; they state that they wrote and verified all final proofs and exposition.

AI Disclosure

  • ChatGPT 5.6 was used to explore proof ideas; the authors wrote and verified all final proofs and exposition.This is the disclosure provided for the work.Source: AI Disclosure · p. 20

A Query Complexity with Round Constraints

This section analyzes how random sampling can reveal labels beyond those queried, then uses that coverage analysis to design a batched variant of CAL. A suitable round schedule yields an O(kd log(n/dk)) query bound.

A Query Complexity with Round Constraints

  • The coverage lemma considers how many points remain unlabeled-inferable after querying a uniformly random subset of fixed size.It defines Q as the number of points whose labels cannot be inferred from the sampled labels.Source: A Query Complexity with Round… · p. 21
  • The batched CAL variant randomly orders points and queries, in each batch, only those whose labels cannot be inferred from earlier queries.The analysis bounds expected queries per round using the random-set coverage lemma.Source: A Query Complexity with Round… · p. 22
  • Using r = log2(n/2dk) rounds gives the optimal O(kd log(n/dk)) query complexity.The schedule is selected to minimize expected query complexity.Source: A Query Complexity with Round… · p. 23

B Separation between CAL and Halving++

A constructed disjoint-box instance separates CAL from Halving++: with n = d^2, the stated bounds are Ω(d log d) queries for CAL and O(d) for Halving++. The comparison is specific to this setting and does not establish general label-efficiency superiority.

B Separation between CAL and Halving++

  • The bounds do not establish that Halving++ is more label-efficient in general because CAL's bound covers general boxes while Halving++'s applies to disjoint boxes.The two bounds therefore cannot be directly compared beyond their stated settings.Source: B Separation between CAL and Halving++ · p. 23
  • For the same disjoint-box problem with n = d^2, CAL requires Ω(d log d) queries while Halving++ uses O(d) queries.The construction makes CAL's upper bound tight on this instance.Source: B Separation between CAL and Halving++ · p. 23
  • For a constant labeling, CAL can infer labels only inside the bounding box of its previous queries, so it continues until that box covers all points.A point outside the queried bounding box can be separated from the queried points by a threshold while remaining consistent with observations.Source: B Separation between CAL and Halving++ · p. 23
Loading 2610.35495v1…