betaFeedback

Reading v1View latest version

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.

Paper details

vlnc:W_vnk3gsaz
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
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…