betaFeedback

WorksComputer Science

PAC Learning with Query Feedback

Abstract

We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of Ω(D/ε)Ω(D/\varepsilon) and an upper bound of O~(D2/ε)\widetilde{O}(D^2/\varepsilon), suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to O~(D/ε)\widetilde{O}(D/\varepsilon), yielding a characterization up to logarithmic factors.

Introduction

In the multiclass PAC learning problem, a learner is tasked with classifying objects into one of KK possible labels. A natural variant of this problem arises when, upon making a prediction on a training example, the learner receives only binary feedback indicating whether its prediction was correct, rather than being given the true label. This setting, known as multiclass PAC learning with bandit feedback, was introduced and studied in the PAC framework by Daniely et al. [8, 9], and its sample complexity was recently characterized, up to logarithmic factors, by Hanneke et al. [13] in terms of a combinatorial parameter called the bandit DS dimension.

Bandit feedback models situations in which a learner chooses an action and observes only whether it succeeds. As motivation, Hanneke et al. [13] describe a treatment scenario in which each patient is assumed to respond to exactly one of the available drugs. Administering a drug then tests a single candidate label: the learner observes whether that drug was effective, but an unsuccessful treatment does not reveal which drug would have worked.

Binary feedback need not be limited to testing a single candidate label: an action may instead test whether the true label belongs to a subset of labels. For example, suppose the goal is to identify which of KK bacterial species caused a patient’s infection, and each available drug is effective against a known subset of these species. Under the simplifying assumption that treatment succeeds exactly when the responsible bacterium belongs to that subset, administering a drug reveals whether the true label lies in the corresponding subset. This leads naturally to what we call query feedback: the learner asks whether the true label belongs to a chosen subset of the label space, and the family of subsets it may ask about is fixed in advance.

Formally, we study the following problem. Let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}} be a hypothesis class over an instance space X\mathcal{X} and a finite label space Y\mathcal{Y} with ∣Y∣=K|\mathcal{Y}| = K, and let Q⊆2Y\mathcal{Q} \subseteq2^{\mathcal{Y}} be a fixed family of available © C. Hutton, A. Melrod & H. Shao. queries. We consider the realizable setting, in which an unknown target h∗∈Hh^* \in\mathcal{H} determines the label of every instance. Training proceeds over mm rounds. On round tt, the learner observes an instance xtx_t drawn from an unknown distribution D\mathcal{D} on X\mathcal{X}, chooses a query Qt∈QQ_t \in\mathcal{Q}, which may depend on xtx_t and on the history of the interaction, and receives the single query response bt=1{h∗(xt)∈Qt}b_t = 1\{h^*(x_t) \in Q_t\} as feedback. After mm rounds, the learner outputs a classifier h^:X→Y\hat{h}: \mathcal{X} \to\mathcal{Y}, and the goal is that its error Pr⁡X∼D[h^(X)≠h∗(X)]\Pr_{X \sim\mathcal{D}}[\hat{h}(X) \ne h^*(X)] is at most ε\varepsilon with probability at least 1−δ1-\delta. We denote by mQ(H;ε,δ)m_{\mathcal{Q}}(\mathcal{H}; \varepsilon, \delta) the smallest number of rounds for which some learner achieves this guarantee for every distribution D\mathcal{D} and every target h∗∈Hh^* \in\mathcal{H}.

Observe that taking Qsing:={{y}:y∈Y}\mathcal{Q}_{\mathrm{sing}} := \{\{y\} : y \in\mathcal{Y}\} recovers multiclass PAC learning with bandit feedback. For more general Q\mathcal{Q}, the structure of the available queries can make learning considerably more efficient. Whereas under bandit feedback an incorrect prediction eliminates a single candidate label, a query that divides the candidate labels into two groups of comparable size rules out many of them at once. Not every query about a large subset is useful however. Indeed, a query containing all remaining candidates reveals nothing. What matters is whether the allowed queries can separate labels that the learner still needs to distinguish. In this work we study how this ability governs the number of examples required to learn:

Given a hypothesis class H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}} and a family of legal queries Q⊆2Y\mathcal{Q} \subseteq2^{\mathcal{Y}}, how many training rounds are necessary and sufficient for PAC learning H\mathcal{H} when the learner receives only query feedback from Q\mathcal{Q}?

The bandit DS dimension of Hanneke et al. [13] is a natural starting point to answering this question. As such, let us briefly recall its definition. The main combinatorial objects used to define the bandit DS dimension are pseudo-boxes: finite sets WW of label vectors, realized by H\mathcal{H} on instances x1,…,xdx_1,\ldots,x_d, such that every vector in WW has, for each coordinate ii, at least NiN_i neighbors in WW that differ from it only at xix_i. The dimension is then the largest total ∑iNi\sum_i N_i that H\mathcal{H} realizes in this way. The dimension essentially counts locally indistinguishable alternatives: hypotheses that differ from one another only at a single instance which bandit feedback can rule out only one at a time. For general query families, however, this metric is no longer enough. The same set of candidate labels can be difficult to distinguish when queries test one label at a time, but easy when suitable subset queries are available. A dimension for our setting must therefore account both for the hypothesis class H\mathcal{H}, which determines which labels the learner needs to distinguish, and for the query family Q\mathcal{Q}, which determines how many rounds it takes to distinguish them. Our main contribution is to identify such a dimension and establish upper and lower bounds on the sample complexity in terms of it.

Overview and Main Results

We call this parameter the query dimension DQ(H)D_{\mathcal{Q}}(\mathcal{H}). To define it, we first assign each nonempty candidate set C⊆YC \subseteq\mathcal{Y} a normalized refinement cost pQ(C)p_{\mathcal{Q}}(C), which measures the depth of an available query tree relative to the refinement it achieves. We then aggregate these costs across instances in the manner of the bandit DS dimension. We give an informal description here and refer the reader to § 5.1 for the formal definitions.

The cost of distinguishing labels. Fix a finite set C⊆YC \subseteq\mathcal{Y} with ∣C∣≥2|C| \ge2. We model an adaptive strategy for distinguishing the labels in CC as a decision tree. Specifically, we define a Q\mathcal{Q}-decision tree to be a binary tree whose internal nodes are labeled by queries from Q\mathcal{Q}, with the two branches out of a node labeled AA corresponding to the two possible responses. A label y∈Cy \in C follows the branch indexed by 1{y∈A}\mathbf{1}\{y \in A\} at each node it visits. Labels that reach the same leaf remain indistinguishable, so the leaves induce a partition ΠT(C)\Pi_T(C) of CC into cells. We say that the tree completely refines CC if every cell is a singleton. Complete refinement is not always achievable, as two labels may be indistinguishable under every query in Q\mathcal{Q}.

The minimum depth of a tree that completely refines CC is a natural measure of difficulty. For our purposes, however, it is useful to account for partial refinement as well. A tree TT that induces ∣ΠT(C)∣|\Pi_T(C)| cells has created ∣ΠT(C)∣−1|\Pi_T(C)|-1 new cells out of the ∣C∣−1|C|-1 needed for complete refinement, and we regard the ratio of these two numbers as the fraction of complete refinement it achieves. The query-refinement cost of CC is the depth of a tree divided by the fraction of refinement it achieves, minimized over trees:

ρQ(C):=min⁡Tdepth⁡(T)∣C∣−1∣ΠT(C)∣−1,\rho_{\mathcal{Q}}(C) := \min_T \operatorname{depth}(T)\frac{|C|-1}{|\Pi_T(C)|-1},

where the minimum ranges over Q\mathcal{Q}-decision trees that induce at least two cells on CC. For a tree that completely refines CC the ratio is simply its depth; for a partial refinement, the depth is scaled up by the reciprocal of the progress made. We set ρQ(C):=0\rho_{\mathcal{Q}}(C) := 0 when ∣C∣=1|C| = 1, and ρQ(C):=∞\rho_{\mathcal{Q}}(C) := \infty when no query in Q\mathcal{Q} separates any two labels of CC.

This normalization has a useful interpretation in terms of prediction. Consider a learner that asks tt queries about an unknown label y∈Cy \in C and then guesses yy. Each query may depend on the responses to the previous ones, so the queries the learner can ask form a Q\mathcal{Q}-decision tree of depth tt, and its guess is a function of the responses, that is, of the leaf that yy reaches. Every deterministic learner is thus described by a Q\mathcal{Q}-decision tree together with a guessed label at each leaf, and a randomized learner is simply a mixture of such learners. Now consider a leaf of the learner’s tree and the cell of labels in CC that reach it. The learner cannot distinguish these labels, so it guesses the same label for all of them and is correct for at most one. The learner is therefore correct on at most ∣ΠT(C)∣|\Pi_T(C)| of the labels in CC. By the definition of ρQ(C)\rho_{\mathcal{Q}}(C), a tree of depth tt induces at most 1+t(∣C∣−1)/ρQ(C)1+t(|C|-1)/\rho_{\mathcal{Q}}(C) cells, so if yy is drawn uniformly from CC, the learner guesses it correctly with probability at most

∣ΠT(C)∣∣C∣≤1∣C∣+tρQ(C)⋅∣C∣−1∣C∣≤12+tρQ(C).(1)\frac{|\Pi_T(C)|}{|C|} \le\frac{1}{|C|}+\frac{t}{\rho_{\mathcal{Q}}(C)}\cdot\frac{|C|-1}{|C|} \le\frac{1}{2}+\frac{t}{\rho_{\mathcal{Q}}(C)}. \tag*{(1)}

Thus, a learner that asks substantially fewer than ρQ(C)\rho_{\mathcal{Q}}(C) queries cannot identify a uniformly chosen label from CC with high probability.

From a set of labels to a hypothesis class. The query dimension aggregates query-refinement costs across instances using the local structure of the pseudo-boxes of Hanneke et al. [13]. A witness consists of distinct instances x1,…,xdx_1,\ldots,x_d and a nonempty finite set WW of label vectors realized by H\mathcal{H} on them, that is, W⊆H∣x1:d:={(h(x1),…,h(xd)):h∈H}W \subseteq\mathcal{H}|_{x_{1:d}} := \{(h(x_1),\ldots,h(x_d)) : h \in\mathcal{H}\}. For v∈Wv \in W and i∈[d]i \in[d], define the ii-line through vv by LiW(v):={ui:u∈W,u−i=v−i}L_i^W(v) := \{u_i : u \in W, u_{-i} = v_{-i}\}. This is the set of candidate labels at xix_i whose label vectors remain in WW after the labels at all other selected instances have been fixed to v−iv_{-i}. Since the corresponding vectors agree at every other coordinate, feedback at those instances cannot distinguish between these candidates. The cost ρQ(LiW(v))\rho_{\mathcal{Q}}(L_i^W(v)) therefore measures a local ambiguity whose resolution requires queries at xix_i. To obtain a coordinate cost that is uniform over the choice of target vector in WW, we define

ri(W):=min⁡v∈WρQ(LiW(v)).r_i(W) := \min_{v\in W} \rho_Q\left(L_i^W(v)\right).

Every ii-line in WW thus has query-refinement cost at least ri(W)r_i(W). These coordinate costs contribute additively, reflecting the fact that the ambiguity at each instance must be resolved independently through queries at that instance. Accordingly, we define the query dimension as the supremum of the total cost over all witnesses:

DQ(H):=sup⁡W⊆H∣x1:d∑i=1dri(W).D_Q(\mathcal{H}) := \sup_{W\subseteq\mathcal{H}|_{x_{1:d}}} \sum_{i=1}^{d} r_i(W).

This definition retains the additive structure of the bandit DS dimension while replacing local neighbor counts by query-refinement costs. Indeed, under singleton queries, ρQsing(L)=∣L∣−1\rho_{Q_{\mathrm{sing}}}(L)=|L|-1, so the cost of an ii-line through vv is exactly the number of vectors in WW that differ from vv only at coordinate ii. Consequently, ri(W)r_i(W) is the minimum such neighbor count, as in the pseudo-boxes of Hanneke et al. [13], and DQsing(H)=BDS⁡(H)D_{Q_{\mathrm{sing}}}(\mathcal{H})=\operatorname{BDS}(\mathcal{H}). For a general query family, the contribution of a coordinate depends instead on how efficiently the available queries distinguish the labels on its lines. This cost can be substantially smaller than the number of alternatives, allowing the dimension to reflect both the local structure of the hypothesis class and the information provided by the query family.

Sample-complexity bounds. Our main result bounds the sample complexity in terms of the query dimension.

Theorem 2.1 (Sample complexity with query feedback, informal) Let H⊆YX\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} be a hypothesis class and Q⊆2Y\mathcal{Q}\subseteq2^{\mathcal{Y}} a query family, with D:=DQ(H)<∞D:=D_Q(\mathcal{H})<\infty and K:=∣Y∣K:=|\mathcal{Y}|. For every 0<ε,δ≤1/8,0<\varepsilon,\delta\le1/8,1

Ω(D+ln⁡(1/δ)ε)≤mQ(H;ε,δ)≤O~(D2ε),(2)\Omega\left(\frac{D+\ln(1/\delta)}{\varepsilon}\right)\le m_Q(\mathcal{H};\varepsilon,\delta)\le\widetilde{O}\left(\frac{D^2}{\varepsilon}\right), \tag*{(2)}

where O~\widetilde{O} hides factors polylogarithmic in KK and 1/δ1/\delta.

Comparison of dimensions. This learning problem has less informative feedback than in traditional multiclass PAC learning. On the other hand, depending on the queries allowed, the feedback can be even incomparable to bandit feedback. Nevertheless, we prove a comparison on the level of the relevant combinatorial dimensions (Proposition 5.6):

DS⁡(H)≤DQ(H)≤BDS⁡(H).\operatorname{DS}(\mathcal{H})\le D_Q(\mathcal{H})\le\operatorname{BDS}(\mathcal{H}).

Balanced queries. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to O~(DQ(H)/ε)\widetilde{O}(D_Q(\mathcal{H})/\varepsilon). This gives a characterization up to logarithmic factors; see § 5.6.

Overview of the proof of Theorem 2.1

Lower bound. We follow the lower-bound construction of Hanneke et al. [13]. In the bandit setting, the argument at a single instance relies on the fact that an unsuccessful prediction eliminates only one candidate label. This need not hold for general queries, which may eliminate many candidates at once, so we use Equation (1) in its place: a learner that asks nn queries about a label drawn uniformly from CC identifies it with probability at most 1/2+n/ρQ(C)1/2+n/\rho_Q(C).

Fix a witness WW on instances x1,…,xdx_1,\ldots,x_d with coordinate costs r1,…,rdr_1,\ldots,r_d and total cost R=∑iriR=\sum_i r_i. We consider distributions supported on these instances and choose the target vector uniformly from WW. The obstacle to applying Equation (1) at an instance xix_i is that the learner’s queries there may depend on feedback it received at other instances. We remove this obstacle by revealing to the learner the target’s labels at all witness instances other than xix_i. This can only help the learner, but it leaves the label at xix_i uniform on an ii-line CC with ρQ(C)≥ri\rho_Q(C)\ge r_i, and once the sampled instances and the learner’s randomness are also fixed, every response at another instance can be computed from the revealed labels. The learner’s prediction at xix_i is then determined by the responses at xix_i alone, so it is given by a QQ-decision tree on CC whose depth is the number nn of visits to xix_i, and Equation (1) bounds its probability of being correct by 1/2+n/ri1/2+n/r_i. Thus the learner errs at xix_i with constant probability whenever the number of visits to xix_i is a small multiple of rir_i.

We then choose the sampling distribution to make these visits infrequent, while assigning enough mass to the difficult instances that the learner cannot ignore them. We select an anchor of minimum coordinate cost and restrict WW to the vectors with a fixed label at the anchor, which leaves the lines at the other coordinates unchanged. The anchor receives mass 1−8ε1-8\varepsilon, and the remaining 8ε8\varepsilon is divided among the other instances in proportion to their coordinate costs; since the anchor has the smallest cost, these instances have total cost at least R/2R/2. Visits to the anchor reveal nothing about the target, and in mm rounds a non-anchor instance xix_i is visited about mεri/Rm\varepsilon r_i/R times in expectation. If mm is a sufficiently small multiple of R/εR/\varepsilon, the learner therefore errs at each non-anchor instance with constant probability, which gives expected error at least 3ε3\varepsilon on instances of total mass 8ε8\varepsilon, and hence error greater than ε\varepsilon with constant probability for some target. Choosing a witness of total cost DD gives the lower bound Ω(D/ε)\Omega(D/\varepsilon).

Upper bound. Our learner repeatedly halves a list of candidate labels at every instance xx, starting from C(x)=H(x):={h(x):h∈H}C(x)=\mathcal{H}(x):=\{h(x):h\in\mathcal{H}\}. Each stage constructs at each instance a distribution over legal queries based on the current list. Using fresh examples and one sampled query per example, the learner trains a binary predictor χ×Q→{0,1}\chi\times\mathcal{Q}\to\{0,1\} of the target’s query responses. For each xx, it then selects the candidate whose responses best match this predictor and retains candidates whose responses are close to those of the selected candidate. Both comparisons measure disagreement under the same query distribution. The distributions and retention threshold ensure that every nonsingleton list remains nonempty and shrinks by at least half; singleton lists are unchanged. After ⌈log⁡2K⌉\lceil\log_2 K\rceil stages, the learner outputs the sole remaining label at each instance.

The query distribution at each instance in a stage is induced by a particular query tree. Write D:=DQ(H)D:=D_Q(\mathcal{H}). Every nonsingleton C⊆H(x)C\subseteq\mathcal{H}(x) admits a halving tree of depth at most τ=O(Dlog⁡K)\tau=O(D\log K), whose leaves contain at most ∣C∣/2|C|/2 candidates (Lemma 5.8). Weighting the tree’s queries by the number of candidates that reach each node yields a distribution λC\lambda_C with a useful separation property. Represent a label yy by its query trace, the binary function A↦1{y∈A}A\mapsto\mathbf{1}\{y\in A\}, and measure trace disagreement by LλC(y,z):=Pr⁡A∼λC[1{y∈A}≠1{z∈A}]L_{\lambda_C}(y,z) := \Pr_{A\sim\lambda_C}[1\{y \in A\} \ne1\{z \in A\}]. Then

∣{z∈C:LλC(y,z)≤12τ}∣≤∣C∣2,y∈C,\left|\left\{z \in C : L_{\lambda_C}(y,z) \le\frac{1}{2\tau}\right\}\right| \le\frac{|C|}{2}, \qquad y \in C,

by Lemma 6.4. Thus a small neighborhood of any candidate trace contains at most half the list. Choosing a candidate close to the target trace and retaining its neighborhood halves the list without discarding the target.

The other ingredient is binary PAC learning under these same query distributions. The observed responses are realized by the class RQ(H):={rh:h∈H}\mathcal{R}_{\mathcal{Q}}(\mathcal{H}) := \{r_h : h \in\mathcal{H}\} of functions rh(x,A):=1{h(x)∈A}r_h(x,A) := 1\{h(x) \in A\} on instance–query pairs. A binary predictor’s error is exactly its average trace disagreement under the query distributions used for list reduction. Selecting the closest candidate trace then bounds the probability mass on which a stage newly discards the target by O(τ)O(\tau) times this binary error (Lemma 6.5).

Finally, the response class has VC dimension d=O(Dlog⁡K)d = O(D \log K) (Lemma 5.10). Dividing the error and failure among the O(log⁡K)O(\log K) stages gives total sample complexity

O~(τdϵ)=O~(D2ϵ).\widetilde{O}\left(\frac{\tau d}{\epsilon}\right) = \widetilde{O}\left(\frac{D^2}{\epsilon}\right).

The two factors of DD have distinct sources: the response-class dimension controls the cost of learning query responses, while the tree depth controls how accurately those responses must be learned to retain the target during list reduction. The full proof appears in § 6.1.

Related Work

Multiclass learning with bandit feedback. Bandit feedback for multiclass prediction was introduced in the online setting by Kakade et al. (2008), whose Banditron is a bandit version of the multiclass perceptron. Daniely and Helbertal [6] quantified what this feedback costs an online learner: a factor of O(Klog⁡K)O(K \log K) on the number of mistakes in the realizable case and Θ~(K)\widetilde{\Theta}(\sqrt{K}) on the regret in the agnostic case. The PAC formulation is due to Daniely et al. [8, 9], who bounded its sample complexity in terms of the Natarajan dimension and showed that withholding the label can cost a factor of order KK. These bounds leave a gap for general classes, and a characterization of the sample complexity of an arbitrary class came only recently: Hanneke et al. [13] show that it is governed, up to logarithmic factors, by the bandit DS dimension, and give an algorithm that attains the bound by learning a sequence of progressively shorter lists of candidate labels.

The paper of Hanneke et al. [13] is the immediate predecessor of ours. The witnesses in our lower bound are their pseudo-boxes and our hard distribution is adapted from theirs; what changes is the quantity charged to a coordinate. A pseudo-box charges a coordinate by the number of alternative labels it contains, which is the right measure when a query can eliminate one label at a time. The query dimension charges it by the cost of separating those alternatives with the queries that are actually available. The two agree when every query is a singleton (Proposition 5.7), and the cost can be far smaller than the count when the queries are more informative.

Outside the realizable PAC setting, Erez et al. [11] determine the minimax regret of online bandit classification with a finite class over TT rounds, Θ~(min⁡{∣H∣+T,KTlog⁡∣H∣})\widetilde{\Theta}(\min\{|\mathcal{H}|+\sqrt{T},\sqrt{KT\log|\mathcal{H}|}\}), and Erez et al. [10] give an agnostic PAC learner for finite classes that uses O((poly⁡(K)+ϵ−2)log⁡(∣H∣/δ))O((\operatorname{poly}(K)+\epsilon^{-2})\log(|\mathcal{H}|/\delta)) examples, so the factor of KK paid in the realizable case disappears from the leading term as ϵ→0\epsilon\to0.

Multiclass learnability. For a finite label space, PAC learnability of a multiclass class is governed by its Natarajan dimension [1] (Natarajan 1989), up to a factor logarithmic in KK. For label spaces of unbounded size the right parameter is the DS dimension of Daniely and Shalev-Shwartz [7], defined through pseudo-cubes, finite sets of label vectors in which every vector has an alternative in each coordinate. Brukhim et al. [2] proved that the DS dimension characterizes multiclass PAC learnability, and Charikar and Pabbaraju [4] carried the characterization over to list learning, in which the learner outputs a short list that should contain the correct label.

Partial labels and label-subset queries. A query response is a candidate set for the label: a positive answer to AA places h∗(x)h^*(x) in AA, and a negative answer places it in Y∖A\mathcal{Y} \setminus A. Learning from candidate sets is the subject of partial-label learning, also called superset-label learning [5] (Liu and Dietterich 2014), and a complementary label (Ishida et al., 2017), which names a class the example does not belong to, is exactly what a negative bandit response provides. In these models the candidate sets are produced by the annotator or the environment, and the analysis asks when the classifier can be recovered from them. Here the sets are produced by the learner, one per example, from a prescribed family, and the question is how many examples this costs.

Protocols in which the learner chooses its own label-subset questions have been studied mostly from the algorithmic side. Hu et al. (2019) let an active learner pick both an example and a binary question about a composite class in a label hierarchy, with further questions about the same example allowed; their evaluation is empirical. The closest protocol to ours is the streaming variant of active labeling in Cabannes et al. [3], which permits one membership query per arriving example, chosen from a fixed family of label subsets. Their concern is optimization: they show that such answers suffice to form unbiased stochastic gradients, prove minimax rates for median regression, and treat classification through surrogate losses. Su et al. (2026) fix the querying rule instead, drawing the subset uniformly among those of a given size, and study unbiased and corrected estimators of the classification risk. None of these works asks how many examples a given hypothesis class requires under a given query family, which is the question studied here.

Model

Let X\mathcal{X} be an instance space, let Y\mathcal{Y} be a finite label space of size K:=∣Y∣≥2K := \lvert\mathcal{Y}\rvert\ge2, and let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}} be a nonempty hypothesis class. We fix a family Q⊆2Y\mathcal{Q} \subseteq2^{\mathcal{Y}} of available queries. We work in the realizable setting: an unknown target h∗∈Hh^* \in\mathcal{H} determines the labels, and instances are drawn independently from an unknown distribution D\mathcal{D} on X\mathcal{X}.

Learning with query feedback

The error of a classifier h:X→Yh:\mathcal{X} \to\mathcal{Y} is its probability of disagreeing with the target on a fresh instance:

LD(h,h∗):=Pr⁡X∼D[h(X)≠h∗(X)].L_{\mathcal{D}}(h,h^*) := \Pr_{X \sim\mathcal{D}}[h(X) \ne h^*(X)].

The goal is to output a classifier with small error, despite observing only query responses during training. Query feedback. On round tt, the learner observes an instance xt∼Dx_t \sim D, chooses a query Qt∈QQ_t \in\mathcal{Q}, and receives the response

bt=1{h∗(xt)∈Qt}.b_t = 1\{h^*(x_t) \in Q_t\}.

The query may depend on xtx_t, the preceding observations (xs,Qs,bs)s<t(x_s, Q_s, b_s)_{s<t}, and the learner’s internal randomness. After mm rounds, the learner returns a classifier h^:X→Y\widehat{h}: \mathcal{X} \to\mathcal{Y}, which need not belong to H\mathcal{H}. We measure the number of rounds needed to achieve the usual PAC guarantee.

Definition 4.1 (Realizable sample complexity). For ϵ,δ∈(0,1)\epsilon, \delta\in(0,1), the sample complexity of H\mathcal{H} with query feedback from Q\mathcal{Q}, denoted by mQ(H;ϵ,δ)m_{\mathcal{Q}}(\mathcal{H}; \epsilon, \delta), is the least nonnegative integer mm for which there exists a learner satisfying

Pr⁡[LD(h^,h∗)>ϵ]≤δ\Pr\left[L_D(\widehat{h}, h^*) > \epsilon\right] \leq\delta

after mm rounds, for every distribution DD on X\mathcal{X} and every target h∗∈Hh^* \in\mathcal{H}. The probability is over the sampled instances and the learner’s internal randomness. We set mQ(H;ϵ,δ)=∞m_{\mathcal{Q}}(\mathcal{H}; \epsilon, \delta) = \infty if no such mm exists.

Combinatorial Dimension

We define the query dimension and compare it with the DS and bandit DS dimensions. We then bound two quantities used in the upper bound of § 6.1: identification depth and the VC dimension of the extended response class. We conclude with a characterization up to logarithmic factors for balanced query families. Proofs not included here appear in Section B.

Query refinement

We use decision trees to measure the information obtainable about an unknown label through queries from Q\mathcal{Q}.

Definition 5.1 (Q\mathcal{Q}-decision tree). A Q\mathcal{Q}-decision tree TT is a finite rooted binary tree whose internal nodes are labeled by queries from Q\mathcal{Q}, with the two outgoing edges indexed by 0 and 1. At a node labeled by AA, a label y∈Yy \in\mathcal{Y} follows the edge indexed by 1{y∈A}1\{y \in A\}. The depth depth⁡(T)\operatorname{depth}(T) is the maximum number of internal nodes on a root-to-leaf path.

For a nonempty C⊆YC \subseteq\mathcal{Y}, let ΠT(C)\Pi_T(C) be the partition of CC into the nonempty sets of labels reaching the same leaf. We say that tree completely refines CC if every cell is a singleton. For ∣C∣≥2|C| \geq2, a tree inducing q≥2q \geq2 cells achieves a fraction (q−1)/(∣C∣−1)(q-1)/(|C|-1) of the refinement needed to isolate every label. We measure its cost by dividing its depth by this fraction.

Definition 5.2 (Query-refinement cost). For a nonempty C⊆YC \subseteq\mathcal{Y}, set ρQ(C):=0\rho_{\mathcal{Q}}(C) := 0 if ∣C∣=1|C| = 1. For ∣C∣≥2|C| \geq2, define

ρQ(C):=inf⁡T a Q-decision tree∣ΠT(C)∣≥2depth⁡(T)∣C∣−1∣ΠT(C)∣−1,(3)\rho_{\mathcal{Q}}(C) := \inf_{\substack{T\ \text{a }\mathcal{Q}\text{-decision tree}\\ |\Pi_T(C)|\geq2}} \operatorname{depth}(T)\frac{|C|-1}{|\Pi_T(C)|-1}, \tag*{(3)}

with value ∞\infty if no such tree exists.

A complete refinement costs its depth, but a partial refinement may have smaller normalized cost. The following bounds relate this cost to the number of candidate labels.

Lemma 5.3 For every C⊆YC \subseteq\mathcal{Y} with ∣C∣≥2|C| \ge2,

ρQ(C)≥log⁡2∣C∣.\rho_Q(C) \ge\log_2 |C|.

If ρQ(C)<∞\rho_Q(C) < \infty, then ρQ(C)≤∣C∣−1\rho_Q(C) \le|C| - 1. In particular, for distinct a,b∈Ya,b \in\mathcal{Y}, the cost ρQ({a,b})\rho_Q(\{a,b\}) is 11 if some query separates aa and bb, and ∞\infty otherwise.

The query dimension

To define the query dimension, we use the witness structure of the bandit DS dimension, with refinement costs in place of neighbor counts. Write H(x):={h(x):h∈H}\mathcal{H}(x) := \{h(x) : h \in\mathcal{H}\} and, for distinct instances x1:d=(x1,…,xd)x_{1:d} = (x_1,\ldots,x_d),

H∣x1:d:={(h(x1),…,h(xd)):h∈H}.\mathcal{H}|_{x_{1:d}} := \{(h(x_1),\ldots,h(x_d)) : h \in\mathcal{H}\}.

A witness for H\mathcal{H} consists of such a sequence and a nonempty finite set W⊆H∣x1:dW \subseteq\mathcal{H}|_{x_{1:d}}. For v∈Wv \in W and i∈[d]i \in[d], let v−iv_{-i} denote vv with coordinate ii deleted. The ii-line through vv is

LiW(v):={ui:u∈W, u−i=v−i}.L_i^W(v) := \{u_i : u \in W,\, u_{-i} = v_{-i}\}.

It contains the labels at xix_i allowed by WW when the other coordinates are fixed to those of vv. We assign coordinate ii the minimum refinement cost of its lines and sum these costs over coordinates:

ri(W):=min⁡v∈WρQ(LiW(v)),rQ(W):=∑i=1dri(W).r_i(W) := \min_{v \in W} \rho_Q\left(L_i^W(v)\right), \qquad r_Q(W) := \sum_{i=1}^{d} r_i(W).

Definition 5.4 (Query dimension) The query dimension of H\mathcal{H} is

DQ(H):=sup⁡d≥1, x1:d∈X distinct∅≠W⊆H∣x1:d, ∣W∣<∞rQ(W).(4)D_Q(\mathcal{H}) := \sup_{\substack{d \ge1,\ x_{1:d} \in\mathcal{X}\ \mathrm{distinct}\\ \varnothing\ne W \subseteq\mathcal{H}|_{x_{1:d}},\ |W|<\infty}} r_Q(W). \tag*{(4)}

with value zero if there are no witnesses.

We say that QQ separates H\mathcal{H} pointwise if, for every x∈Xx \in\mathcal{X} and every pair of distinct labels a,b∈H(x)a,b \in\mathcal{H}(x), some query contains exactly one of aa and bb.

Lemma 5.5 For every x∈Xx \in\mathcal{X} and every nonempty C⊆H(x)C \subseteq\mathcal{H}(x),

ρQ(C)≤DQ(H).\rho_Q(C) \le D_Q(\mathcal{H}).

Consequently, if DQ(H)<∞D_Q(\mathcal{H}) < \infty, then QQ separates H\mathcal{H} pointwise.

Proof. The set CC is a witness on the single instance xx, with cost ρQ(C)\rho_Q(C). An unseparated pair in H(x)\mathcal{H}(x) would therefore give infinite query dimension by Lemma 5.3. ■

Comparison with existing dimensions

A DS witness, or pseudo-cube, requires at least one alternative label in every coordinate line and is assigned its number of coordinates [7, 2]. A BDS witness requires at least Ni≥1N_i \ge1 alternatives in each ii-line and is assigned the weight ∑iNi\sum_i N_i [13]. The corresponding dimensions maximize these quantities over witnesses. Formal definitions appear in Section A.1. The below proposition shows that the query dimension is lower bounded by the DS dimension and upper bounded by the bandit DS dimension.

Proposition 5.6 (Comparison of dimensions) If DQ(H)<∞D_Q(\mathcal{H}) < \infty, then

DS⁡(H)≤DQ(H)≤BDS⁡(H)≤(K−1)DS⁡(H).(5)\operatorname{DS}(\mathcal{H}) \le D_Q(\mathcal{H}) \le\operatorname{BDS}(\mathcal{H}) \le(K-1)\operatorname{DS}(\mathcal{H}). \tag*{(5)}

More generally, these inequalities hold, allowing infinite values, whenever Q\mathcal{Q} separates H\mathcal{H} pointwise.

For singleton queries, the query dimension recovers the bandit DS dimension exactly.

Proposition 5.7 Let Qsing:={{y}:y∈Y}\mathcal{Q}_{\mathrm{sing}} := \{\{y\}:y \in\mathcal{Y}\}. For every nonempty C⊆YC \subseteq\mathcal{Y},

ρQsing(C)=∣C∣−1.(6)\rho_{\mathcal{Q}_{\mathrm{sing}}}(C) = |C| - 1. \tag*{(6)}

Consequently, DQsing(H)=BDS⁡(H)D_{\mathcal{Q}_{\mathrm{sing}}}(\mathcal{H}) = \operatorname{BDS}(\mathcal{H}).

Identification depth

For a nonempty C⊆YC \subseteq\mathcal{Y}, the identification depth τQ(C)\tau_{\mathcal{Q}}(C) is the least depth of a Q\mathcal{Q}-decision tree that completely refines CC, with value ∞\infty if no such tree exists. In particular, τQ(C)=0\tau_{\mathcal{Q}}(C) = 0 for a singleton. Unlike the refinement cost, this quantity requires exact identification of every candidate label. The following lemma shows that the identification depth of CC can be bounded in terms of the query dimension.

Lemma 5.8 Let D:=DQ(H)<∞D := D_Q(\mathcal{H}) < \infty. For every x∈Xx \in\mathcal{X} and every C⊆H(x)C \subseteq\mathcal{H}(x) with ∣C∣≥2|C| \ge2,

τQ(C)=O(Dlog⁡∣C∣).\tau_{\mathcal{Q}}(C) = O(D \log|C|).

The extended response class

For a fixed target, the response to a query is a binary function of the instance–query pair. The upper-bound algorithm learns these functions on X×Q\mathcal{X} \times\mathcal{Q}. Formally, we shall consider the following class of binary functions.

Definition 5.9 (Extended response class) For h∈Hh \in\mathcal{H}, define rh:X×Q→{0,1}r_h:\mathcal{X} \times\mathcal{Q} \to\{0,1\} by

rh(x,A):=1{h(x)∈A}.r_h(x,A) := \mathbf{1}\{h(x) \in A\}.

The extended response class of H\mathcal{H} and its VC dimension are

RQ(H):={rh:h∈H},dQ(H):=VC⁡(RQ(H)).\mathcal{R}_{\mathcal{Q}}(\mathcal{H}) := \{r_h:h \in\mathcal{H}\}, \qquad d_{\mathcal{Q}}(\mathcal{H}) := \operatorname{VC}(\mathcal{R}_{\mathcal{Q}}(\mathcal{H})).

The next lemma shows that the VC dimension of this extended response class is upper bounded by the query dimension, up to logarithmic factors in KK.

Lemma 5.10 (VC dimension of the extended response class) If dN:=Ndim⁡(H)<∞d_N := \operatorname{Ndim}(\mathcal{H}) < \infty, then

dQ(H)=O(dNlog⁡2K).d_Q(\mathcal{H}) = O(d_N \log_2 K).

In particular, if DQ(H)<∞D_Q(\mathcal{H}) < \infty, then

dQ(H)=O(DQ(H)log⁡2K).d_Q(\mathcal{H}) = O(D_Q(\mathcal{H}) \log_2 K).

Balanced query families

The general upper bound is quadratic in the query dimension. We now show that this dependence becomes linear, up to logarithmic factors, when the available queries can split every candidate set into two parts of comparable size.

Definition 5.11 (Balanced query family) Fix β∈(0,1/2]\beta\in(0, 1/2]. A query family QQ is β\beta-balanced for H\mathcal{H} if, for every x∈Xx \in\mathcal{X} and every C⊆H(x)C \subseteq\mathcal{H}(x) with ∣C∣≥2|C| \ge2, some A∈QA \in Q satisfies

max⁡{∣C∩A∣,∣C∖A∣}≤(1−β)∣C∣.(7)\max\{|C \cap A|, |C \setminus A|\} \le(1-\beta)|C|. \tag*{(7)}

Thus, regardless of the response, the query eliminates at least a β\beta fraction of the candidate labels. This condition yields the following sample-complexity guarantee.

Theorem 5.12 (Balanced queries) Suppose that QQ is β\beta-balanced for H\mathcal{H} and that D:=DQ(H)∈(0,∞)D := D_Q(\mathcal{H}) \in(0,\infty). For every 0<ε,δ≤1/80 < \varepsilon, \delta\le1/8,

mQ(H;ε,δ)=O~β(Dε).(8)m_Q(\mathcal{H}; \varepsilon, \delta) = \widetilde{O}_{\beta}\left(\frac{D}{\varepsilon}\right). \tag*{(8)}

If H\mathcal{H} is non-trivial in the sense of Definition 6.1, then O~β\widetilde{O}_{\beta} can be replaced by Θ~β\widetilde{\Theta}_{\beta}. The suppressed factors are polylogarithmic in KK and 1/δ1/\delta, and the implicit constants may depend on β\beta.

The improvement comes from the depth of the trees used for list halving. The upper-bound algorithm requires only a tree whose cells contain at most half the original candidates, rather than one that identifies every label exactly. Under the balancing condition, each split reduces the remaining candidate set by a factor of at most 1−β1-\beta. Repeated splitting therefore produces a halving tree of depth O(1/β)O(1/\beta), independent of DD.

Substituting this depth bound into the list-halving bound of Lemma B.1, together with the response-class bound of Lemma 5.10, gives the upper bound linear in DD up to logarithmic factors. The matching lower bound under non-triviality follows from Theorem 6.3.

Algorithm and Analysis

This section states and proves our main result: an upper bound and a lower bound on the sample complexity of learning with query feedback, both in terms of the query dimension D:=DQ(H)D := D_Q(\mathcal{H}). The upper bound is achieved by an algorithm that learns to shrink a list of candidate labels at every instance, and it holds whenever DD is finite. The lower bound requires in addition that the dimension be witnessed on more than one instance.

Definition 6.1 (Non-trivial class) The class H\mathcal{H} is non-trivial under Q\mathcal{Q} if DQ(H)D_Q(\mathcal{H}) is finite and is witnessed on at least two instances, that is, if there exist d≥2d \ge2, distinct instances x1,…,xd∈Xx_1,\ldots,x_d \in\mathcal{X}, and a finite nonempty mathcalW⊆H∣x1:dmathcal{W} \subseteq\mathcal{H}|_{x_{1:d}} with rQ(W)=DQ(H)r_Q(W) = D_Q(\mathcal{H}).

This condition is analogous to the non-triviality condition used by Hanneke et al. [13]. It is required only for the lower bound.

Theorem 6.2 (Sample-complexity upper bound) Fix H\mathcal{H} and Q\mathcal{Q} with D:=DQ(H)<∞D := D_Q(\mathcal{H}) < \infty. For every ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2),

mQ(H;ε,δ)=O(Dlog⁡3Kε(Dlog⁡K+log⁡1δ)).(9)m_Q(\mathcal{H};\varepsilon,\delta) = O\left(\frac{D\log^3 K}{\varepsilon}\left(D\log K+\log\frac{1}{\delta}\right)\right). \tag*{(9)}

In particular, mQ(H;ε,δ)=O~(D2/ε)m_Q(\mathcal{H};\varepsilon,\delta) = \widetilde{O}(D^2/\varepsilon), where O~\widetilde{O} hides factors polylogarithmic in KK and 1/δ1/\delta. For comparison, we prove the following lower bound, which has the same dependence on ε\varepsilon and is linear in DD.

Theorem 6.3 (Sample-complexity lower bound) Let H\mathcal{H} be non-trivial under Q\mathcal{Q} be non-trivial, and write D:=DQ(H)D := D_Q(\mathcal{H}). For every 0<ε,δ≤1/80 < \varepsilon,\delta\le1/8,

mQ(H;ε,δ)=Ω(D+log⁡(1/δ)ε).(10)m_Q(\mathcal{H};\varepsilon,\delta) = \Omega\left(\frac{D+\log(1/\delta)}{\varepsilon}\right). \tag*{(10)}

Together, Theorems 6.2 and 6.3 prove Theorem 2.1. The two bounds differ by a factor of order DD, up to logarithmic factors.

Proof of the upper bound

The learner maintains a nonempty list of candidate labels at every instance and repeatedly halves these lists. Each stage learns to predict query responses, then uses the predictor to choose which candidates to retain. We first describe the algorithm, then prove that its query distributions guarantee list reduction and that accurate response prediction prevents the target from being discarded on too much probability mass.

The list-halving algorithm. Write D:=DQ(H)<∞D := D_Q(\mathcal{H}) < \infty. If every H(x)\mathcal{H}(x) is a singleton, the learner can output its unique element without any samples. Otherwise D≥1D \ge1 and Q≠∅\mathcal{Q} \ne\emptyset by Lemmas 5.3 and 5.5; fix A0∈QA_0 \in\mathcal{Q}. Let d:=dQ(H)d := d_Q(\mathcal{H}), and fix an integer τ≥1\tau\ge1 such that every nonsingleton C⊆H(x)C \subseteq\mathcal{H}(x) admits a halving tree: a Q\mathcal{Q}-decision tree whose leaves each contain at most ∣C∣/2|C|/2 candidates and whose depth is at most τ\tau. By Lemmas 5.8 and 5.10, we may take

τ=O(Dlog⁡K),d=O(Dlog⁡K).(11)\tau= O(D\log K), \qquad d = O(D\log K). \tag*{(11)}

For each nonsingleton CC, fix such a tree and pad every path to length τ\tau using A0A_0. Define a query distribution λC\lambda_C by choosing a uniform candidate from CC, choosing a uniform position on its path, and returning the query at that position. For a singleton CC, let λC\lambda_C be the point mass at A0A_0.

To compare labels, represent y∈Yy \in\mathcal{Y} by its query trace tr⁡y(A):=1{y∈A}\operatorname{tr}_y(A) := 1\{y \in A\}. For binary functions u,v:Q→{0,1}u,v:\mathcal{Q}\to\{0,1\} and a query distribution λ\lambda, write

Lλ(u,v):=Pr⁡A∼λ[u(A)≠v(A)],Lλ(y,z):=Lλ(tr⁡y,tr⁡z).L_\lambda(u,v) := \Pr_{A\sim\lambda}[u(A)\ne v(A)], \qquad L_\lambda(y,z) := L_\lambda(\operatorname{tr}_y,\operatorname{tr}_z).

This disagreement measure satisfies the triangle inequality.

Algorithm 1 gives the learner. Here BinaryPAC is the learner for RQ(H)\mathcal{R}_{\mathcal{Q}}(\mathcal{H}) supplied by Fact A.5. A call with accuracy γ\gamma and failure probability η\eta uses n=O((d+log⁡(1/η))/γ)n=O((d+\log(1/\eta))/\gamma) examples.

Algorithm 1: Learning with query feedback by list halving

Input: H\mathcal{H}, Q\mathcal{Q}, ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2); query distributions λC\lambda_C defined above.

S←⌈log⁡2K⌉S\leftarrow\lceil\log_2 K\rceil, γ←ε/(4τS)\gamma\leftarrow\varepsilon/(4\tau S), η←δ/S\eta\leftarrow\delta/S

C0(x)←H(x)C_0(x)\leftarrow\mathcal{H}(x) for every x∈Xx\in\mathcal{X}

for t=0,…,S−1t=0,\ldots,S-1 do

λt,x←λCt(x)\lambda_{t,x}\leftarrow\lambda_{C_t(x)} for every x∈Xx\in\mathcal{X}

Collect nn fresh examples: at each Xi∼DX_i\sim\mathcal{D}, draw Ai∼λt,XiA_i\sim\lambda_{t,X_i}, and request

bi=1{h∗(Xi)∈Ai}b_i=1\{h^*(X_i)\in A_i\}

gt←BinaryPAC⁡({((Xi,Ai),bi)}i=1n;γ,η)g_t\leftarrow\operatorname{BinaryPAC}(\{((X_i,A_i),b_i)\}_{i=1}^n;\gamma,\eta)

foreach x∈Xx\in\mathcal{X} do

ft(x)∈arg⁡min⁡y∈Ct(x)Lλt,x(gt(x,⋅),tr⁡y)f_t(x)\in\arg\min_{y\in C_t(x)}L_{\lambda_{t,x}}(g_t(x,\cdot),\operatorname{tr}_y)

Ct+1(x)←{y∈Ct(x):Lλt,x(ft(x),y)≤1/(2τ)}C_{t+1}(x)\leftarrow\{y\in C_t(x):L_{\lambda_{t,x}}(f_t(x),y)\le1/(2\tau)\}

end

end

Output: h^(x)\widehat{h}(x), the unique element of CS(x)C_S(x), for every xx.

At each stage, the learner selects the candidate whose responses best match the binary predictor and retains a small neighborhood of that candidate’s trace. The two lemmas below explain why this update halves each nonsingleton list while usually retaining the target.

From halving trees to single-query distributions. A halving tree tells us how several adaptive queries can reduce a candidate set, but the learner may ask only one query per example. We therefore use the tree to design a distribution rather than execute it. The construction of λC\lambda_C gives more weight to queries reached by many candidates. Consequently, labels that separate before the candidate set has halved must disagree on a query with significant probability. This yields the following geometric guarantee.

Lemma 6.4 (Queries from a halving tree) Let C⊆YC\subseteq\mathcal{Y} be nonsingleton and admit a halving tree of depth at most τ\tau. The distribution λC\lambda_C constructed above satisfies

∣{z∈C:LλC(y,z)≤12τ}∣≤∣C∣2,y∈C.(12)\left|\left\{z\in C:L_{\lambda_C}(y,z)\le\frac{1}{2\tau}\right\}\right|\le\frac{|C|}{2},\qquad y\in C. \tag*{(12)}

Proof. For a node uu of the padded tree, let CuC_u be the candidates reaching it and, if uu is internal, let AuA_u be its query. By construction,

λC(A)=1τ∣C∣∑u internalAu=A∣Cu∣.(13)\lambda_C(A) = \frac{1}{\tau|C|} \sum_{\substack{u\ \mathrm{internal}\\ A_u=A}} |C_u|. \tag*{(13)}

These weights sum to one because every candidate visits exactly τ\tau internal nodes. Fix y∈Cy \in C, and let uyu_y be the first node on its path with ∣Cuy∣≤∣C∣/2|C_{u_y}| \le|C|/2. Such a node exists by the halving property. Any z∈C∖Cuyz \in C \setminus C_{u_y} diverges from yy at a strict ancestor ww of uyu_y. Thus ∣Cw∣>∣C∣/2|C_w| > |C|/2, and the query AwA_w separates yy and zz. It follows that

LλC(y,z)≥λC(Aw)≥∣Cw∣τ∣C∣≥12τ.L_{\lambda_C}(y,z) \ge\lambda_C(A_w) \ge\frac{|C_w|}{\tau|C|} \ge\frac{1}{2\tau}.

The ball in (12) is therefore contained in CuyC_{u_y}, which has at most ∣C∣/2|C|/2 candidates. ■

From response prediction to list halving. The preceding lemma guarantees that every nonsingleton list shrinks by at least half, regardless of the chosen center. The remaining task is to retain the target on most instances where it is still a candidate. The next lemma shows that choosing the candidate trace closest to the response predictor controls the probability mass of newly discarded targets in terms of the predictor’s average binary error.

Lemma 6.5 (Halving the candidate lists) Fix nonempty lists C(x)⊆H(x)C(x) \subseteq H(x), x∈Xx \in\mathcal{X}, and ε′,δ′∈(0,1/2)\varepsilon', \delta' \in(0,1/2). One stage of Algorithm 1, with binary accuracy γ:=ε′/(4τ)\gamma:= \varepsilon'/(4\tau) and failure probability δ′\delta', uses

O(τε′(d+log⁡1δ′))(14)O\left(\frac{\tau}{\varepsilon'}\left(d+\log\frac{1}{\delta'}\right)\right) \tag*{(14)}

query-feedback examples and returns nonempty subsets C′(x)⊆C(x)C'(x) \subseteq C(x) satisfying

∣C′(x)∣≤max⁡{1,∣C(x)∣2}.|C'(x)| \le\max\left\{1,\frac{|C(x)|}{2}\right\}.

For every distribution D\mathcal{D} and target h∗∈Hh^* \in\mathcal{H}, with probability at least 1−δ′1-\delta',

D({x:h∗(x)∈C(x)∖C′(x)})≤ε′.(15)\mathcal{D}\left(\left\{x:h^*(x)\in C(x)\setminus C'(x)\right\}\right)\le\varepsilon'. \tag*{(15)}

Proof. Set λx:=λC(x)\lambda_x := \lambda_{C(x)}, and let μ\mu be the distribution of (X,A)(X,A) obtained by drawing X∼DX \sim\mathcal{D} and A∼λXA \sim\lambda_X. The stage observes i.i.d. binary examples with label rh∗(X,A)=1{h∗(X)∈A}r_{h^*}(X,A)=\mathbb{1}\{h^*(X)\in A\}. By Fact A.5, the stated sample size suffices to return g:X×Q→{0,1}g:\mathcal{X}\times\mathcal{Q}\to\{0,1\} with binary error at most γ=ε′/(4τ)\gamma=\varepsilon'/(4\tau), except with probability δ′\delta'. For y∈Yy\in\mathcal{Y}, define

ℓx(y):=Lλx(g(x,⋅),tr⁡y).\ell_x(y):=L_{\lambda_x}(g(x,\cdot),\operatorname{tr}_y).

On the binary learner’s success event we have that

EX∼D[ℓX(h∗(X))]=Pr⁡(X,A)∼μ[g(X,A)≠rh∗(X,A)]≤γ.(16)\mathbb{E}_{X\sim\mathcal{D}}[\ell_X(h^*(X))]=\Pr_{(X,A)\sim\mu}[g(X,A)\ne r_{h^*}(X,A)]\le\gamma. \tag*{(16)}

The predictor g(x,⋅)g(x,\cdot) need not itself be a label trace. The algorithm therefore chooses a closest candidate trace and keeps its ball:

f(x)∈arg⁡min⁡y∈C(x)ℓx(y),C′(x):={y∈C(x):Lλx(f(x),y)≤12τ}.(17)f(x) \in\arg\min_{y\in C(x)} \ell_x(y), \qquad C'(x) := \left\{y\in C(x): L_{\lambda_x}(f(x),y) \le\frac{1}{2\tau}\right\}. \tag*{(17)}

The new list contains f(x)f(x), so is nonempty. Singleton lists remain unchanged, and Lemma 6.4 halves every other list, regardless of the predictor’s accuracy.

To control target loss, consider any xx with h∗(x)∈C(x)h^*(x)\in C(x). The triangle inequality and the minimizing property of f(x)f(x) give

Lλx(f(x),h∗(x))≤ℓx(f(x))+ℓx(h∗(x))≤2ℓx(h∗(x)).(18)L_{\lambda_x}(f(x),h^*(x)) \le\ell_x(f(x))+\ell_x(h^*(x)) \le2\ell_x(h^*(x)). \tag*{(18)}

Thus the target survives whenever ℓx(h∗(x))≤1/(4τ)\ell_x(h^*(x))\le1/(4\tau). On the event (16), Markov’s inequality now yields

D({x:h∗(x)∈C(x)∖C′(x)})≤Pr⁡X∼D[ℓX(h∗(X))>14τ]\mathcal{D}\left(\left\{x:h^*(x)\in C(x)\setminus C'(x)\right\}\right) \le\Pr_{X\sim\mathcal{D}}\left[\ell_X(h^*(X))>\frac{1}{4\tau}\right]
≤4τEX∼D[ℓX(h∗(X))]≤4τγ=ε′.\le4\tau\mathbb{E}_{X\sim\mathcal{D}}[\ell_X(h^*(X))]\le4\tau\gamma=\varepsilon'.

Completing the proof. We now iterate the one-stage guarantee. List shrinkage holds deterministically; only the mass of newly discarded targets requires a high-probability bound.

Proof of Theorem 6.2 Fix D\mathcal{D} and h∗∈Hh^*\in\mathcal{H}, and run Algorithm 1 with S=⌈log⁡2K⌉S=\lceil\log_2 K\rceil. At each stage, Lemma 6.5 applies with ε′=ε/S\varepsilon'=\varepsilon/S and δ′=δ/S\delta'=\delta/S. The lists remain nonempty and satisfy

∣Ct(x)∣≤max⁡{1,2−t∣H(x)∣},x∈X,0≤t≤S.|C_t(x)|\le\max\{1,2^{-t}|\mathcal{H}(x)|\},\qquad x\in\mathcal{X},\quad0\le t\le S.

Hence every final list CS(x)C_S(x) is a singleton, so the output h^\hat{h} is well defined. For 0≤t<S0\le t<S, let

Et:={x:h∗(x)∈Ct(x)∖Ct+1(x)}.E_t:=\{x:h^*(x)\in C_t(x)\setminus C_{t+1}(x)\}.

Conditional on the history before stage tt, the lists CtC_t and the query distributions are fixed and by Lemma 6.5 we have the probability that D(Et)>ε/S\mathcal{D}(E_t)>\varepsilon/S is at most δ/S\delta/S. Averaging over histories and taking a union bound, with probability at least 1−δ1-\delta, D(Et)≤ε/S\mathcal{D}(E_t)\le\varepsilon/S for every stage.

The lists are nested and initially contain the target. Each incorrect final prediction therefore corresponds to exactly one stage at which the target was discarded: the sets EtE_t are disjoint and their union is the final error set. On the preceding success event,

LD(h^,h∗)=∑t=0S−1D(Et)≤ε.L_{\mathcal{D}}(\hat{h},h^*)=\sum_{t=0}^{S-1}\mathcal{D}(E_t)\le\varepsilon.

Finally, summing (14) over the SS stages gives

m=O(τS2ε(d+log⁡Sδ))=O(Dlog⁡3Kε(Dlog⁡K+log⁡1δ)),\begin{aligned} m=O\left(\frac{\tau S^2}{\varepsilon}\left(d+\log\frac{S}{\delta}\right)\right) \\ &=O\left(\frac{D\log^3 K}{\varepsilon}\left(D\log K+\log\frac{1}{\delta}\right)\right), \end{aligned}

where we used (11), S=O(log⁡K)S=O(\log K), and log⁡S=O(Dlog⁡K)\log S=O(D\log K) since D≥1D\ge1. This proves (9).

Proof of the lower bound

In this section we prove Theorem 6.3 by constructing two hard cases, following the lower-bound argument of Hanneke et al. [13]. In the bandit setting, that argument rests on the fact that an unsuccessful prediction eliminates a single candidate label. A general query may eliminate many labels at once, so we instead bound the probability of a correct prediction at an instance directly in terms of the refinement cost of the candidate labels there (Lemma 6.6). The bound concerns a single deterministic decision tree, whereas the learner’s queries at one instance may depend on the feedback it received at others; Lemma 6.7 shows that this adaptivity is immaterial. We then apply the bound to a distribution in which most samples fall on an uninformative point (Lemma 6.8). The dependence on δ\delta comes from a separate two-point construction.

Lemma 6.6 Let C⊆YC \subseteq\mathcal{Y} have M≥2M \ge2 elements, and let TT be a QQ-decision tree of depth at most nn whose leaves are labeled by elements of Y\mathcal{Y}. Writing T(y)T(y) for the label of the leaf reached by yy,

Pr⁡Y∼Unif⁡(C)[T(Y)=Y]≤1M+nρQ(C)⋅M−1M.(19)\Pr_{Y \sim\operatorname{Unif}(C)}[T(Y)=Y] \le\frac{1}{M}+\frac{n}{\rho_Q(C)}\cdot\frac{M-1}{M}. \tag*{(19)}

Proof. Let q:=∣ΠT(C)∣q := |\Pi_T(C)|. Labels in the same cell reach the same leaf and receive the same output, so at most one label per cell is predicted correctly, and the probability in (19) is at most q/Mq/M. If q=1q=1, this is the claim. If q≥2q \ge2, then TT is admissible in the infimum {(5.1)} defining ρQ(C)\rho_Q(C), so

ρQ(C)≤depth⁡(T)M−1q−1≤nM−1q−1,that is,q≤1+n(M−1)ρQ(C).\rho_Q(C) \le\operatorname{depth}(T)\frac{M-1}{q-1} \le n\frac{M-1}{q-1}, \qquad\text{that is,}\qquad q \le1+\frac{n(M-1)}{\rho_Q(C)}.

Dividing by MM proves (19).

The learner’s queries at an instance may depend on the responses it has received at other instances. The next lemma shows that, once the target’s labels at the other instances are fixed, the learner’s prediction at an instance is computed by a decision tree whose depth is the number of visits to that instance.

Lemma 6.7 Let W⊆H∣x1:dW \subseteq\mathcal{H}|_{x_{1:d}} be a witness, and choose a representative hv∈Hh_v \in\mathcal{H} for each v∈Wv \in W. Suppose that a learner interacts with target hUh_U, where UU is supported on WW, and every sampled instance belongs to {x1,…,xd}\{x_1,\ldots,x_d\}. Let NiN_i be the number of occurrences of xix_i in the sample. After fixing U−iU_{-i}, the instance sequence, and the learner’s internal randomness, there is a deterministic QQ-decision tree TT of depth at most NiN_i, with leaves labeled by elements of Y\mathcal{Y}, such that the learner’s final prediction at xix_i equals T(Ui)T(U_i).

Proof. We construct TT by simulating the learner on the fixed instance sequence, maintaining a tree in which each node records a history. Initially, the tree is a single root recording the empty history.

  • In a round at xjx_j with j≠ij \ne i, we extend the history at each leaf by the learner’s query and the response determined by U−iU_{-i}. The tree itself does not change.

  • In a round at xix_i, each leaf uu has a query qu∈Qq_u \in Q that the learner issues given the history at the leaf. We then attach to uu two children, one for each possible response to quq_u. Each child records the history at uu extended by quq_u and that response.

After the last round, we label each leaf by the learner’s final prediction at xix_i given the history at that leaf. The tree branches only in the NiN_i rounds at xix_i, so has depth at most NiN_i, and by construction the learners prediction at xix_i is T(Ui)T(U_i).

We now choose the hard distribution. It places most of its mass on a fixed instance at which all candidate targets agree, and distributes the remaining mass among the other witness instances in proportion to their coordinate costs, so that the expected number of visits to each of them is small compared with the cost of its lines.

Lemma 6.8 Let W⊆H∣x1:dW \subseteq\mathcal{H}|_{x_{1:d}} be a witness on d≥2d \ge2 instances with total cost R:=rQ(W)∈(0,∞)R := r_{\mathcal{Q}}(W) \in(0,\infty). For every 0<ε≤1/80 < \varepsilon\le1/8,

mQ(H;ε,1/8)≥R128ε.(20)m_{\mathcal{Q}}(\mathcal{H};\varepsilon,1/8) \ge\frac{R}{128\varepsilon}. \tag*{(20)}

Proof Write ri:=ri(W)r_i := r_i(W), and relabel the coordinates so that r1=min⁡irir_1 = \min_i r_i. Since r1r_1 is minimal,

R−1:=∑i=2dri≥R2>0.R_{-1} := \sum_{i=2}^{d} r_i \ge\frac{R}{2} > 0.

Fix bb such that the slice Wb:={v∈W:v1=b}W_b := \{v \in W : v_1 = b\} is nonempty. For i≥2i \ge2, every ii-line of WW meeting WbW_b lies entirely in WbW_b, so every ii-line of WbW_b is an ii-line of WW and has refinement cost at least rir_i. Draw UU uniformly from WbW_b and let hU∈Hh_U \in\mathcal{H} realize UU. Independently of UU, draw the training instances from the distribution D\mathcal{D} on x1,…,xdx_1,\ldots,x_d given by

D(x1)=1−8ε,D(xi)=8εriR−1,2≤i≤d,\mathcal{D}(x_1) = 1 - 8\varepsilon,\qquad\mathcal{D}(x_i) = \frac{8\varepsilon r_i}{R_{-1}},\qquad2 \le i \le d,

where ε≤1/8\varepsilon\le1/8 ensures D(x1)≥0\mathcal{D}(x_1) \ge0.

Consider any (possibly randomized) learner that uses m≤R−1/(64ε)m \le R_{-1}/(64\varepsilon) rounds and outputs h^\hat{h}. Let NiN_i count the occurrences of xix_i in the instance sequence, so that ENi=mD(xi)\mathbb{E}N_i = m\mathcal{D}(x_i). Fix i≥2i \ge2 with ri>0r_i > 0. Conditional on U−iU_{-i}, the instance sequence, and the learner’s random seed, UiU_i is uniform on the ii-line through U−iU_{-i}; as noted above, this line has refinement cost at least rir_i. By Lemma 6.7, the interaction then reduces to a decision tree of depth at most NiN_i. Applying Lemma 6.6 and averaging over the conditioning gives

Pr⁡[h^(xi)≠Ui]≥12−ENiri=12−8εmR−1≥38.\Pr[\hat{h}(x_i) \ne U_i] \ge\frac{1}{2} - \frac{\mathbb{E}N_i}{r_i} = \frac{1}{2} - \frac{8\varepsilon m}{R_{-1}} \ge\frac{3}{8}.

Thus, writing

Z:=∑i=2dD(xi)1{h^(xi)≠Ui}Z := \sum_{i=2}^{d} \mathcal{D}(x_i)1\{\hat{h}(x_i) \ne U_i\}

for the error away from the first coordinate, we have 0≤Z≤8ε0 \le Z \le8\varepsilon and EZ≥3ε\mathbb{E}Z \ge3\varepsilon. Markov’s inequality yields

Pr⁡[Z≤ε]=Pr⁡[8ε−Z≥7ε]≤8ε−EZ7ε≤57,\Pr[Z \le\varepsilon] = \Pr[8\varepsilon- Z \ge7\varepsilon] \le\frac{8\varepsilon- \mathbb{E}Z}{7\varepsilon} \le\frac{5}{7},

so Pr⁡[Z>ε]≥2/7>1/8\Pr[Z > \varepsilon] \ge2/7 > 1/8.

Since hUh_U realizes UU, the error of h^\hat{h} with respect to hUh_U under D\mathcal{D} is at least ZZ. As the probability above averages over UU, there is a fixed u∈Wbu \in W_b such that, with target huh_u, the learner’s error exceeds ε\varepsilon with probability greater than 1/81/8; that is, the learner fails the (ε,1/8)(\varepsilon,1/8)-PAC guarantee. Hence no (ε,1/8)(\varepsilon,1/8)-PAC learner uses m≤R−1/(64ε)m \le R_{-1}/(64\varepsilon) rounds, and (20) follows from R−1≥R/2R_{-1} \ge R/2.

Proof of Theorem 6.3 By non-triviality and Lemma 6.8,

mQ(H;ε,δ)≥mQ(H;ε,1/8)≥D128ε.m_{\mathsf{Q}}(\mathcal{H};\varepsilon,\delta) \ge m_{\mathsf{Q}}(\mathcal{H};\varepsilon,1/8) \ge\frac{D}{128\varepsilon}.

For the confidence dependence, non-triviality ensures that H\mathcal{H} contains two hypotheses that agree at one instance and disagree at another. Then a standard two-point lower bound (see the lower-bound proof of Hanneke et al. [13]) yields

mQ(H;ε,δ)≥Ω(log⁡(1/δ)ε).m_{\mathsf{Q}}(\mathcal{H};\varepsilon,\delta) \ge\Omega\left(\frac{\log(1/\delta)}{\varepsilon}\right).

Combining the two lower bounds proves the theorem.

Discussion

In this work, we introduced the query dimension for multiclass PAC learning with query feedback and establish a lower bound linear in this dimension and an upper bound quadratic in it, up to logarithmic factors. For balanced query families, the upper bound is linear and therefore matches the lower bound up to logarithmic factors. The main open question is whether a corresponding characterization holds for arbitrary query families. Further directions include extending the analysis to the agnostic setting and determining which logarithmic factors are necessary.

AI acknowledgment In addition to literature review, we used GPT 6 to assist with the editing and drafting of this paper. Additionally, the proofs of Lemmas 5.8 and 5.10 are due to GPT 6. The authors verified the correctness and originality of all content in the paper and take full responsibility for its content.

Learning-Theoretic Background

Combinatorial dimensions

We first recall the VC and Natarajan dimensions, which are used to control the binary learning problems in the upper bound. We then recall the DS and bandit DS dimensions, whose local witness structure underlies the query dimension.

Definition A.1 (VC dimension) Let H⊆{0,1}Z\mathcal{H} \subseteq\{0,1\}^{\mathcal{Z}} be a binary hypothesis class. Distinct points z1,…,zd∈Zz_1,\ldots,z_d \in\mathcal{Z} are shattered by H\mathcal{H} if

H∣z1:d={0,1}d.\mathcal{H}|_{z_{1:d}} = \{0,1\}^{d}.

The VC dimension VC⁡(H)\operatorname{VC}(\mathcal{H}) is the supremum of the sizes of shattered sets.

For multiclass hypotheses, the Natarajan dimension allows the two labels used in the shattering condition to vary from one instance to another.

Definition A.2 (Natarajan dimension) Let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}}. Distinct instances x1,…,xd∈Xx_1,\ldots,x_d \in\mathcal{X} are Natarajan-shattered by H\mathcal{H} if there exist labels ai,bi∈Ya_i,b_i \in\mathcal{Y} with ai≠bia_i \ne b_i for every i∈[d]i \in[d] such that

∏i=1d{ai,bi}⊆H∣x1:d.\prod_{i=1}^{d}\{a_i,b_i\} \subseteq\mathcal{H}|_{x_{1:d}}.

The Natarajan dimension Ndim⁡(H)\operatorname{Ndim}(\mathcal{H}) is the supremum of the sizes of Natarajan-shattered sets.

Both dimensions are defined to be zero if no nonempty set is shattered and infinite if arbitrarily large finite sets are shattered. When Y={0,1}\mathcal{Y}=\{0,1\}, the two definitions coincide.

The DS dimension. A nonempty finite set W⊆YdW \subseteq\mathcal{Y}^{d} is a pseudo-cube if ∣LiW(v)∣≥2|L_i^W(v)| \ge2 for every v∈Wv \in W and every i∈[d]i \in[d].

Definition A.3 (DS dimension ([7, 2])) Let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}}. The DS dimension DS⁡(H)\operatorname{DS}(\mathcal{H}) is the supremum of the integers d≥1d \ge1 for which there exist distinct instances x1,…,xd∈Xx_1,\ldots,x_d \in\mathcal{X} such that H∣x1:d\mathcal{H}|_{x_{1:d}} contains a pseudo-cube. Its value is zero if no such witness exists and infinite if such witnesses have arbitrarily many coordinates.

The bandit DS dimension. The bandit DS dimension of Hanneke et al. [13] is defined through a local condition on finite sets of label vectors. For u,v∈Ydu,v \in\mathcal{Y}^{d} and i∈[d]i \in[d], we say that uu is an ii-neighbor of vv if

u−i=v−iandui≠vi.u_{-i}=v_{-i}\qquad\text{and}\qquad u_i\ne v_i.

Thus, an ii-neighbor provides an alternative label at coordinate ii without changing any other coordinate. A nonempty finite set W⊆YdW \subseteq\mathcal{Y}^{d} is a pseudo-box with multiplicities N1,…,NdN_1,\ldots,N_d if every v∈Wv \in W has at least NiN_i distinct ii-neighbors in WW for each i∈[d]i \in[d]. Here N1,…,NdN_1,\ldots,N_d are positive integers. Following the formal definition in Hanneke et al. [13], the multiplicity NiN_i counts neighbors, rather than including the label of vv itself.

Definition A.4 (Bandit DS dimension (Hanneke et al. [13])) Let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}}. Distinct instances x1,…,xdx_1,\ldots,x_d, together with positive integers N1,…,NdN_1,\ldots,N_d, are BDS-shattered by H\mathcal{H} if H∣x1:d\mathcal{H}|_{x_{1:d}} contains a pseudo-box with these multiplicities. The bandit DS dimension of H\mathcal{H} is

BDS⁡(H):=sup⁡{∑i=1dNi:d≥1, x1,…,xd∈X distinct,N1,…,Nd∈N,(x1:d,N1:d) is BDS-shattered by H}.\operatorname{BDS}(\mathcal{H}) := \sup\left\{\sum_{i=1}^{d}N_i:\begin{array}{l} d\ge1,\ x_1,\ldots,x_d\in\mathcal{X}\text{ distinct},\\ N_1,\ldots,N_d\in\mathbb{N},\\ (x_{1:d},N_{1:d})\text{ is BDS-shattered by }\mathcal{H} \end{array}\right\}.

The value is zero if no such witness exists and infinite if the displayed sums are unbounded.

Unlike Natarajan shattering, the pseudo-box condition does not require a full Cartesian product of label choices. It requires only that each vector have the prescribed number of alternatives in every coordinate.

Learning and growth bounds

The upper-bound proof uses a realizable binary PAC learner at each stage. The following guarantee is for the full-information model, in which every training example is accompanied by its binary label.

Fact A.5 (Realizable binary PAC learning (Hanneke, [12])) Let H⊆{0,1}Z\mathcal{H} \subseteq\{0,1\}^{\mathcal{Z}} be a nonempty binary class with VC⁡(H)=d<∞\operatorname{VC}(\mathcal{H})=d<\infty. There is a universal constant Cbin>0C_{\mathrm{bin}}>0 such that, for every ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2), a possibly improper learner achieves error at most ε\varepsilon with probability at least 1−δ1-\delta using

⌈Cbind+log⁡(1/δ)ε⌉(21)\left\lceil C_{\mathrm{bin}}\frac{d+\log(1/\delta)}{\varepsilon}\right\rceil \tag*{(21)}

i.i.d. labeled examples. The guarantee holds for every distribution on Z\mathcal{Z} and every target in H\mathcal{H}.

To bound the VC dimensions of the binary classes arising in the reduction, we use the following growth bound of Haussler and Long (1995). It controls the number of label vectors realized on finitely many instances in terms of the Natarajan dimension.

Fact A.6 (Natarajan–Sauer growth bound) Let H⊆YX\mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}} have Natarajan dimension 1≤n<∞1 \le n < \infty, where ∣Y∣=K|\mathcal{Y}|=K. For every r≥nr \ge n and every choice of distinct instances x1,…,xrx_1,\ldots,x_r,

∣H∣x1:r∣≤(erK2n)n.(22)|\mathcal{H}|_{x_{1:r}}| \le\left(\frac{e r K^2}{n}\right)^n . \tag*{(22)}

Proofs for the Combinatorial Dimension

Elementary refinement bounds

Proof of Lemma 5.3 Write n:=∣C∣n:=|\mathcal{C}|. An admissible tree of depth tt inducing qq cells satisfies 2≤q≤n2\le q\le n and q≤2tq\le2^t. Hence

tq−1≥(n−1)log⁡2qq−1≥log⁡2n,\frac{t}{q-1}\ge(n-1)\frac{\log_2 q}{q-1}\ge\log_2 n,

where the last inequality uses that u↦log⁡2u/(u−1)u\mapsto\log_2 u/(u-1) is decreasing for u>1u>1. Taking the infimum proves the lower bound. If a tree induces at least two cells on C\mathcal{C}, some query separates two labels in C\mathcal{C}. The depth-one tree for that query induces two nonempty cells and has cost n−1n-1, proving the upper bound. The two-label claim follows. ▪

Comparison with existing dimensions

Proof of Proposition 5.6 In a pseudo-cube on dd coordinates, every line has at least two labels and hence refinement cost at least one by Lemma 5.3. Its query cost is therefore at least dd, proving DS(H)≤DQ(H)D_{\mathrm{S}}(\mathcal{H})\le D_{\mathrm{Q}}(\mathcal{H}).

For the middle inequality, assume that Q\mathcal{Q} separates H\mathcal{H} pointwise, as follows from finite query dimension by Lemma 5.5. Every nonsingleton subset of H(x)\mathcal{H}(x) is split by some query, so Lemma 5.3 gives

ρQ(C)≤∣C∣−1for every nonempty C⊆H(x).\rho_{\mathcal{Q}}(C)\le|C|-1 \qquad\text{for every nonempty } C\subseteq\mathcal{H}(x).

Fix a witness WW and set

mi:=min⁡v∈W(∣LiW(v)∣−1),I:={i∈[d]:mi>0}.m_i := \min_{v \in W}(\lvert L_i^W(v)\rvert- 1), \qquad I := \{i \in[d] : m_i > 0\}.

Then rQ(W)≤∑imir_Q(W) \le\sum_i m_i. If I≠∅I \ne\varnothing, project WW onto the coordinates in II. For each projected vector, choose a preimage v∈Wv \in W. For every i∈Ii \in I, the ii-neighbors of vv project to distinct ii-neighbors of the projected vector. The projection is therefore a BDS witness with multiplicities (mi)i∈I(m_i)_{i \in I}, giving ∑imi≤BDS⁡(H)\sum_i m_i \le\operatorname{BDS}(\mathcal{H}). This inequality is immediate if I=∅I = \varnothing. Taking the supremum over WW proves DQ(H)≤BDS⁡(H)D_Q(\mathcal{H}) \le\operatorname{BDS}(\mathcal{H}).

Finally, a BDS witness with positive multiplicities N1,…,NdN_1,\ldots,N_d is also a pseudo-cube, so d≤DS⁡(H)d \le\operatorname{DS}(\mathcal{H}). Since Ni≤K−1N_i \le K - 1 for every ii,

∑i=1dNi≤d(K−1)≤(K−1)DS⁡(H).\sum_{i=1}^{d} N_i \le d(K-1) \le(K-1)\operatorname{DS}(\mathcal{H}).

Taking the supremum proves the last inequality.

Singleton queries

Proof of Proposition 5.7 Under singleton queries, a positive response identifies the label, so only the all-negative branch of a decision tree can continue to split candidates. A depth-tt tree therefore induces at most t+1t+1 nonempty cells on CC, giving refinement cost at least ∣C∣−1\lvert C\rvert- 1. For ∣C∣≥2\lvert C\rvert\ge2, one query {y}\{y\} with y∈Cy \in C attains this cost; for a singleton, the cost is zero by definition. This proves (5.4).

Singleton queries separate all labels, so Proposition 5.6 gives DQsing(H)≤BDS⁡(H)D_{Q_{\mathrm{sing}}}(\mathcal{H}) \le\operatorname{BDS}(\mathcal{H}), including when the dimensions are infinite. Conversely, a BDS witness with multiplicities N1,…,NdN_1,\ldots,N_d has at least Ni+1N_i+1 labels in every ii-line. Its query cost is therefore at least ∑iNi\sum_i N_i by (5.4). Taking the supremum proves the reverse inequality.

Identification depth

Proof of Lemma 5.8 Fix x∈Xx \in\mathcal{X}. Let Hj:=∑r=1j1/rH_j := \sum_{r=1}^{j} 1/r for j≥1j \ge1, with H0:=0H_0 := 0. We prove by induction on n:=∣C∣n := \lvert C\rvert that every nonempty C⊆H(x)C \subseteq\mathcal{H}(x) satisfies

τQ(C)≤Hn−1D.\tau_Q(C) \le H_{n-1}D.

The case n=1n=1 follows from τQ(C)=0\tau_Q(C)=0. For n≥2n \ge2, choose a tree TT attaining ρQ(C)\rho_Q(C), which is finite by Lemma 5.5. Let C1,…,CkC_1,\ldots,C_k be its nonempty cells, where k≥2k \ge2. Then

depth⁡(T)=k−1n−1ρQ(C)≤k−1n−1D.\operatorname{depth}(T) = \frac{k-1}{n-1}\rho_Q(C) \le\frac{k-1}{n-1}D.

Each cell has at most n−k+1n-k+1 labels and is contained in H(x)\mathcal{H}(x), so the induction hypothesis gives τQ(Cj)≤Hn−kD\tau_Q(C_j) \le H_{n-k}D for every jj. Attaching an identification tree for each cell to its corresponding leaf yields

τQ(C)≤depth⁡(T)+max⁡jτQ(Cj)≤(k−1n−1+Hn−k)D≤Hn−1D.\begin{aligned} \tau_Q(C) \le\operatorname{depth}(T) + \max_j \tau_Q(C_j) \\ &\le\left(\frac{k-1}{n-1} + H_{n-k}\right)D \\ &\le H_{n-1}D. \end{aligned}

The last inequality follows from

Hn−1−Hn−k=∑r=n−k+1n−11r≥k−1n−1.H_{n-1} - H_{n-k} = \sum_{r=n-k+1}^{n-1} \frac{1}{r} \ge\frac{k-1}{n-1}.

Since Hn−1=O(log⁡n)H_{n-1}=O(\log n) for n≥2n \ge2, the result follows.

The extended response class

Proof of Lemma 5.10 Suppose q≥1q \ge1 distinct pairs (x1,A1),…,(xq,Aq)(x_1,A_1),\ldots,(x_q,A_q) are shattered by RQ(H)\mathcal{R}_Q(\mathcal{H}), and let z1,…,zrz_1,\ldots,z_r be the distinct instances among the xix_i, so r≤qr \le q. Each label vector on these instances determines all qq responses. Consequently,

2q≤∣H∣z1:r.2^q \le\lvert\mathcal{H}\rvert_{z_{1:r}}.

If r≤dNr \le d_N, then 2q≤Kr2^q \le K^r, giving q≤dNlog⁡2Kq \le d_N\log_2 K. If r>dNr>d_N, the Natarajan–Sauer growth bound of Haussler and Long (1995) (Fact A.6) gives

2q≤∣H∣z1:r≤(erK2dN)dN≤(eqK2dN)dN.2^q \le\lvert\mathcal{H}\rvert_{z_{1:r}} \le\left(\frac{erK^2}{d_N}\right)^{d_N} \le\left(\frac{eqK^2}{d_N}\right)^{d_N}.

Writing a:=q/dNa:=q/d_N and taking logarithms yields

a≤log⁡2e+2log⁡2K+log⁡2a.a \le\log_2 e + 2\log_2 K + \log_2 a.

Since a=O(log⁡2K)a=O(\log_2 K), every finite shattered set has size O(dNlog⁡2K)O(d_N\log_2 K). This proves the first claim. The second follows from Proposition 5.6.

Balanced queries

We first record the dependence of the list-halving argument on the depth of the available halving trees. This separates the algorithmic bound from the particular estimate of that depth used in Theorem 6.2.

Lemma B.1 (List halving with a uniform depth bound) Suppose that, for some integer b≥1b \ge1, every nonsingleton C⊆H(x)C \subseteq\mathcal{H}(x), x∈Xx \in\mathcal{X}, admits a QQ-decision tree of depth at most bb whose nonempty cells have size at most ∣C∣/2\lvert C\rvert/2. If d:=dQ(H)<∞d:=d_Q(\mathcal{H})<\infty and S:=⌈log⁡2K⌉S:=\lceil\log_2 K\rceil, then for ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2),

mQ(H;ε,δ)=O(bS2ε[d+log⁡Sδ]).(23)m_Q(\mathcal{H};\varepsilon,\delta)=O\left(\frac{bS^2}{\varepsilon}\left[d+\log\frac{S}{\delta}\right]\right). \tag*{(23)}

Proof When all the sets H(x)\mathcal{H}(x) are singletons, learning requires no samples. Otherwise Q≠∅Q \ne\varnothing. By Lemma 6.4, a halving tree of depth at most bb supplies a query distribution for which every ball of radius 1/(2b)1/(2b) contains at most half the candidates. The proof of Lemma 6.5 uses its depth parameter only through this property. With bb in place of τ\tau, that proof gives a list-halving step using

O(b′ε[d+log⁡1δ′])O\left(\frac{b'}{\varepsilon}\left[d+\log\frac{1}{\delta'}\right]\right)

samples and, with probability at least 1−δ′1-\delta', discards the target on probability mass at most ε′\varepsilon'. Initialize the lists to H(x)\mathcal{H}(x) and apply SS such steps, each using fresh samples and parameters ε′=ε/S\varepsilon'=\varepsilon/S and δ′=δ/S\delta'=\delta/S. The final lists are singletons. A union bound over the conditional failure probabilities shows that, with probability at least 1−δ1-\delta, the total probability mass on which the target has been discarded is at most Sε′=εS\varepsilon'=\varepsilon. Summing the sample counts proves (B.1).

Proof of Theorem 5.12 Set

b:=⌈ln⁡2−ln⁡(1−β)⌉.b:=\left\lceil\frac{\ln2}{-\ln(1-\beta)}\right\rceil.

For any nonsingleton C⊆H(x)C\subseteq\mathcal{H}(x), recursively apply balanced splits, stopping each branch when its candidate set has size at most ∣C∣/2|C|/2. After tt queries, any branch that has not stopped contains at most (1−β)t∣C∣(1-\beta)^t|C| candidates. Since (1−β)b≤1/2(1-\beta)^b\le1/2, this gives a halving tree of depth at most b=O(1/β)b=O(1/\beta).

By Lemmas B.1 and 5.10, with S:=⌈log⁡2K⌉S:=\lceil\log_2 K\rceil,

mQ(H;ε,δ)=O(S2βε[Dlog⁡(2K)+log⁡Sδ]).(24)m_Q(\mathcal{H};\varepsilon,\delta) =O\left(\frac{S^2}{\beta\varepsilon}\left[D\log(2K)+\log\frac{S}{\delta}\right]\right). \tag*{(24)}

Since D>0D>0 implies D≥1D\ge1, this is O~β(D/ε)\widetilde{O}_{\beta}(D/\varepsilon) when factors polylogarithmic in KK and 1/δ1/\delta are suppressed. If H\mathcal{H} is non-trivial, Theorem 6.3 gives Ω((D+log⁡(1/δ))/ε)\Omega((D+\log(1/\delta))/\varepsilon) for 0<ε,δ≤1/80<\varepsilon,\delta\le1/8, proving the characterization.

References

  1. [1]Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, . . . , n}-valued functions. Journal of Computer and System Sciences, 50(1):74–86, 1995. doi: 10.1006/jcss.1995.1008. URL https://doi.org/10.1006/jcss.1995.1008.
  2. [2]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00093. URL https://arxiv.org/abs/2203.01550.
  3. [3]Vivien Cabannes, Francis Bach, Vianney Perchet, and Alessandro Rudi. Active labeling: Streaming stochastic gradients. In Advances in Neural Information Processing Systems, volume 35, pages 17568–17581. Curran Associates, Inc., 2022. doi: 10.52202/068431-1277. URL https://proceedings.neurips.cc/paper_files/paper/2022/hash/6fee03d84375a159ecd3769ebbacae83-Abstract-Conference.html.
  4. [4]Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1713–1726. Association for Computing Machinery, 2023. doi: 10.1145/3564246.3585190. URL https://arxiv.org/abs/2211.04956.
  5. [5]Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12(42):1501–1536, 2011. URL https://www.jmlr.org/papers/v12/cour11a.html.
  6. [6]Amit Daniely and Tom Helbertal. The price of bandit information in multiclass online classification. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 93–104. PMLR, 2013. URL https://proceedings.mlr.press/v30/Daniely13.html.arxiv.org/abs/1302.1043
  7. [7]Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 287–316. PMLR, 2014. URL https://proceedings.mlr.press/v35/daniely14b.html.arxiv.org/abs/1405.2420
  8. [8]Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 207–232. PMLR, 2011. URL https://proceedings.mlr.press/v19/daniely11a.html.
  9. [9]Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16(72):2377–2404, 2015. URL https://www.jmlr.org/papers/v16/daniely15a.html.
  10. [10]Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran. Fast rates for bandit PAC multiclass classification. In Advances in Neural Information Processing Systems, volume 37, pages 75152–75176. Curran Associates, Inc., 2024a. doi: 10.52202/079017-2392. URL https://proceedings.neurips.cc/paper_files/paper/2024/hash/8957cfb29ae633d6e8c3615be038d4d6-Abstract-Conference.html.DOI
  11. [11]Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran. The real price of bandit information in multiclass classification. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1573–1598. PMLR, 2024b. URL https://proceedings.mlr.press/v247/erez24a.html.arxiv.org/abs/2405.10027
  12. [12]Steve Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1–15, 2016. URL https://jmlr.org/papers/v17/15-389.html.arxiv.org/abs/1507.00473
  13. [13]Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri. PAC learning with bandit feedback: Sharp sample complexity in the realizable setting. arXiv preprint arXiv:2605.25678, 2026. doi: 10.48550/arXiv.2605.25678. URL https://arxiv.org/abs/2605.25678.

Paper details

vlnc:W_62tgkp86
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 10

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents