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 and an upper bound of , 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 , yielding a characterization up to logarithmic factors.
Introduction
In the multiclass PAC learning problem, a learner is tasked with classifying objects into one of 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 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 be a hypothesis class over an instance space and a finite label space with , and let be a fixed family of available © C. Hutton, A. Melrod & H. Shao. queries. We consider the realizable setting, in which an unknown target determines the label of every instance. Training proceeds over rounds. On round , the learner observes an instance drawn from an unknown distribution on , chooses a query , which may depend on and on the history of the interaction, and receives the single query response as feedback. After rounds, the learner outputs a classifier , and the goal is that its error is at most with probability at least . We denote by the smallest number of rounds for which some learner achieves this guarantee for every distribution and every target .
Observe that taking recovers multiclass PAC learning with bandit feedback. For more general , 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 and a family of legal queries , how many training rounds are necessary and sufficient for PAC learning when the learner receives only query feedback from ?
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 of label vectors, realized by on instances , such that every vector in has, for each coordinate , at least neighbors in that differ from it only at . The dimension is then the largest total that 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 , which determines which labels the learner needs to distinguish, and for the query family , 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 . To define it, we first assign each nonempty candidate set a normalized refinement cost , 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 with . We model an adaptive strategy for distinguishing the labels in as a decision tree. Specifically, we define a -decision tree to be a binary tree whose internal nodes are labeled by queries from , with the two branches out of a node labeled corresponding to the two possible responses. A label follows the branch indexed by at each node it visits. Labels that reach the same leaf remain indistinguishable, so the leaves induce a partition of into cells. We say that the tree completely refines if every cell is a singleton. Complete refinement is not always achievable, as two labels may be indistinguishable under every query in .
The minimum depth of a tree that completely refines is a natural measure of difficulty. For our purposes, however, it is useful to account for partial refinement as well. A tree that induces cells has created new cells out of the 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 is the depth of a tree divided by the fraction of refinement it achieves, minimized over trees:
where the minimum ranges over -decision trees that induce at least two cells on . For a tree that completely refines the ratio is simply its depth; for a partial refinement, the depth is scaled up by the reciprocal of the progress made. We set when , and when no query in separates any two labels of .
This normalization has a useful interpretation in terms of prediction. Consider a learner that asks queries about an unknown label and then guesses . Each query may depend on the responses to the previous ones, so the queries the learner can ask form a -decision tree of depth , and its guess is a function of the responses, that is, of the leaf that reaches. Every deterministic learner is thus described by a -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 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 of the labels in . By the definition of , a tree of depth induces at most cells, so if is drawn uniformly from , the learner guesses it correctly with probability at most
Thus, a learner that asks substantially fewer than queries cannot identify a uniformly chosen label from 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 and a nonempty finite set of label vectors realized by on them, that is, . For and , define the -line through by . This is the set of candidate labels at whose label vectors remain in after the labels at all other selected instances have been fixed to . Since the corresponding vectors agree at every other coordinate, feedback at those instances cannot distinguish between these candidates. The cost therefore measures a local ambiguity whose resolution requires queries at . To obtain a coordinate cost that is uniform over the choice of target vector in , we define
Every -line in thus has query-refinement cost at least . 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:
This definition retains the additive structure of the bandit DS dimension while replacing local neighbor counts by query-refinement costs. Indeed, under singleton queries, , so the cost of an -line through is exactly the number of vectors in that differ from only at coordinate . Consequently, is the minimum such neighbor count, as in the pseudo-boxes of Hanneke et al. [13], and . 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 be a hypothesis class and a query family, with and . For every 1
where hides factors polylogarithmic in and .
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):
Balanced queries. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to . 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 queries about a label drawn uniformly from identifies it with probability at most .
Fix a witness on instances with coordinate costs and total cost . We consider distributions supported on these instances and choose the target vector uniformly from . The obstacle to applying Equation (1) at an instance 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 . This can only help the learner, but it leaves the label at uniform on an -line with , 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 is then determined by the responses at alone, so it is given by a -decision tree on whose depth is the number of visits to , and Equation (1) bounds its probability of being correct by . Thus the learner errs at with constant probability whenever the number of visits to is a small multiple of .
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 to the vectors with a fixed label at the anchor, which leaves the lines at the other coordinates unchanged. The anchor receives mass , and the remaining 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 . Visits to the anchor reveal nothing about the target, and in rounds a non-anchor instance is visited about times in expectation. If is a sufficiently small multiple of , the learner therefore errs at each non-anchor instance with constant probability, which gives expected error at least on instances of total mass , and hence error greater than with constant probability for some target. Choosing a witness of total cost gives the lower bound .
Upper bound. Our learner repeatedly halves a list of candidate labels at every instance , starting from . 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 of the target’s query responses. For each , 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 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 . Every nonsingleton admits a halving tree of depth at most , whose leaves contain at most candidates (Lemma 5.8). Weighting the tree’s queries by the number of candidates that reach each node yields a distribution with a useful separation property. Represent a label by its query trace, the binary function , and measure trace disagreement by . Then
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 of functions 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 times this binary error (Lemma 6.5).
Finally, the response class has VC dimension (Lemma 5.10). Dividing the error and failure among the stages gives total sample complexity
The two factors of 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 on the number of mistakes in the realizable case and 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 . 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 rounds, , and Erez et al. [10] give an agnostic PAC learner for finite classes that uses examples, so the factor of paid in the realizable case disappears from the leading term as .
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 . 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 places in , and a negative answer places it in . 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 be an instance space, let be a finite label space of size , and let be a nonempty hypothesis class. We fix a family of available queries. We work in the realizable setting: an unknown target determines the labels, and instances are drawn independently from an unknown distribution on .
Learning with query feedback
The error of a classifier is its probability of disagreeing with the target on a fresh instance:
The goal is to output a classifier with small error, despite observing only query responses during training. Query feedback. On round , the learner observes an instance , chooses a query , and receives the response
The query may depend on , the preceding observations , and the learner’s internal randomness. After rounds, the learner returns a classifier , which need not belong to . We measure the number of rounds needed to achieve the usual PAC guarantee.
Definition 4.1 (Realizable sample complexity). For , the sample complexity of with query feedback from , denoted by , is the least nonnegative integer for which there exists a learner satisfying
after rounds, for every distribution on and every target . The probability is over the sampled instances and the learner’s internal randomness. We set if no such 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 .
Definition 5.1 (-decision tree). A -decision tree is a finite rooted binary tree whose internal nodes are labeled by queries from , with the two outgoing edges indexed by 0 and 1. At a node labeled by , a label follows the edge indexed by . The depth is the maximum number of internal nodes on a root-to-leaf path.
For a nonempty , let be the partition of into the nonempty sets of labels reaching the same leaf. We say that tree completely refines if every cell is a singleton. For , a tree inducing cells achieves a fraction 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 , set if . For , define
with value 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 with ,
If , then . In particular, for distinct , the cost is if some query separates and , and 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 and, for distinct instances ,
A witness for consists of such a sequence and a nonempty finite set . For and , let denote with coordinate deleted. The -line through is
It contains the labels at allowed by when the other coordinates are fixed to those of . We assign coordinate the minimum refinement cost of its lines and sum these costs over coordinates:
Definition 5.4 (Query dimension) The query dimension of is
with value zero if there are no witnesses.
We say that separates pointwise if, for every and every pair of distinct labels , some query contains exactly one of and .
Lemma 5.5 For every and every nonempty ,
Consequently, if , then separates pointwise.
Proof. The set is a witness on the single instance , with cost . An unseparated pair in 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 alternatives in each -line and is assigned the weight [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 , then
More generally, these inequalities hold, allowing infinite values, whenever separates pointwise.
For singleton queries, the query dimension recovers the bandit DS dimension exactly.
Proposition 5.7 Let . For every nonempty ,
Consequently, .
Identification depth
For a nonempty , the identification depth is the least depth of a -decision tree that completely refines , with value if no such tree exists. In particular, 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 can be bounded in terms of the query dimension.
Lemma 5.8 Let . For every and every with ,
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 . Formally, we shall consider the following class of binary functions.
Definition 5.9 (Extended response class) For , define by
The extended response class of and its VC dimension are
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 .
Lemma 5.10 (VC dimension of the extended response class) If , then
In particular, if , then
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 . A query family is -balanced for if, for every and every with , some satisfies
Thus, regardless of the response, the query eliminates at least a fraction of the candidate labels. This condition yields the following sample-complexity guarantee.
Theorem 5.12 (Balanced queries) Suppose that is -balanced for and that . For every ,
If is non-trivial in the sense of Definition 6.1, then can be replaced by . The suppressed factors are polylogarithmic in and , and the implicit constants may depend on .
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 . Repeated splitting therefore produces a halving tree of depth , independent of .
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 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 . The upper bound is achieved by an algorithm that learns to shrink a list of candidate labels at every instance, and it holds whenever 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 is non-trivial under if is finite and is witnessed on at least two instances, that is, if there exist , distinct instances , and a finite nonempty with .
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 and with . For every ,
In particular, , where hides factors polylogarithmic in and . For comparison, we prove the following lower bound, which has the same dependence on and is linear in .
Theorem 6.3 (Sample-complexity lower bound) Let be non-trivial under be non-trivial, and write . For every ,
Together, Theorems 6.2 and 6.3 prove Theorem 2.1. The two bounds differ by a factor of order , 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 . If every is a singleton, the learner can output its unique element without any samples. Otherwise and by Lemmas 5.3 and 5.5; fix . Let , and fix an integer such that every nonsingleton admits a halving tree: a -decision tree whose leaves each contain at most candidates and whose depth is at most . By Lemmas 5.8 and 5.10, we may take
For each nonsingleton , fix such a tree and pad every path to length using . Define a query distribution by choosing a uniform candidate from , choosing a uniform position on its path, and returning the query at that position. For a singleton , let be the point mass at .
To compare labels, represent by its query trace . For binary functions and a query distribution , write
This disagreement measure satisfies the triangle inequality.
Algorithm 1 gives the learner. Here BinaryPAC is the learner for supplied by Fact A.5. A call with accuracy and failure probability uses examples.
Algorithm 1: Learning with query feedback by list halving
Input: , , ; query distributions defined above.
, ,
for every
for do
for every
Collect fresh examples: at each , draw , and request
foreach do
end
end
Output: , the unique element of , for every .
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 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 be nonsingleton and admit a halving tree of depth at most . The distribution constructed above satisfies
Proof. For a node of the padded tree, let be the candidates reaching it and, if is internal, let be its query. By construction,
These weights sum to one because every candidate visits exactly internal nodes. Fix , and let be the first node on its path with . Such a node exists by the halving property. Any diverges from at a strict ancestor of . Thus , and the query separates and . It follows that
The ball in (12) is therefore contained in , which has at most 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 , , and . One stage of Algorithm 1, with binary accuracy and failure probability , uses
query-feedback examples and returns nonempty subsets satisfying
For every distribution and target , with probability at least ,
Proof. Set , and let be the distribution of obtained by drawing and . The stage observes i.i.d. binary examples with label . By Fact A.5, the stated sample size suffices to return with binary error at most , except with probability . For , define
On the binary learner’s success event we have that
The predictor need not itself be a label trace. The algorithm therefore chooses a closest candidate trace and keeps its ball:
The new list contains , 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 with . The triangle inequality and the minimizing property of give
Thus the target survives whenever . On the event (16), Markov’s inequality now yields
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 and , and run Algorithm 1 with . At each stage, Lemma 6.5 applies with and . The lists remain nonempty and satisfy
Hence every final list is a singleton, so the output is well defined. For , let
Conditional on the history before stage , the lists and the query distributions are fixed and by Lemma 6.5 we have the probability that is at most . Averaging over histories and taking a union bound, with probability at least , 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 are disjoint and their union is the final error set. On the preceding success event,
Finally, summing (14) over the stages gives
where we used (11), , and since . 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 comes from a separate two-point construction.
Lemma 6.6 Let have elements, and let be a -decision tree of depth at most whose leaves are labeled by elements of . Writing for the label of the leaf reached by ,
Proof. Let . 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 . If , this is the claim. If , then is admissible in the infimum {(5.1)} defining , so
Dividing by 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 be a witness, and choose a representative for each . Suppose that a learner interacts with target , where is supported on , and every sampled instance belongs to . Let be the number of occurrences of in the sample. After fixing , the instance sequence, and the learner’s internal randomness, there is a deterministic -decision tree of depth at most , with leaves labeled by elements of , such that the learner’s final prediction at equals .
Proof. We construct 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 with , we extend the history at each leaf by the learner’s query and the response determined by . The tree itself does not change.
In a round at , each leaf has a query that the learner issues given the history at the leaf. We then attach to two children, one for each possible response to . Each child records the history at extended by and that response.
After the last round, we label each leaf by the learner’s final prediction at given the history at that leaf. The tree branches only in the rounds at , so has depth at most , and by construction the learners prediction at is .
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 be a witness on instances with total cost . For every ,
Proof Write , and relabel the coordinates so that . Since is minimal,
Fix such that the slice is nonempty. For , every -line of meeting lies entirely in , so every -line of is an -line of and has refinement cost at least . Draw uniformly from and let realize . Independently of , draw the training instances from the distribution on given by
where ensures .
Consider any (possibly randomized) learner that uses rounds and outputs . Let count the occurrences of in the instance sequence, so that . Fix with . Conditional on , the instance sequence, and the learner’s random seed, is uniform on the -line through ; as noted above, this line has refinement cost at least . By Lemma 6.7, the interaction then reduces to a decision tree of depth at most . Applying Lemma 6.6 and averaging over the conditioning gives
Thus, writing
for the error away from the first coordinate, we have and . Markov’s inequality yields
so .
Since realizes , the error of with respect to under is at least . As the probability above averages over , there is a fixed such that, with target , the learner’s error exceeds with probability greater than ; that is, the learner fails the -PAC guarantee. Hence no -PAC learner uses rounds, and (20) follows from .
Proof of Theorem 6.3 By non-triviality and Lemma 6.8,
For the confidence dependence, non-triviality ensures that 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
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 be a binary hypothesis class. Distinct points are shattered by if
The VC dimension 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 . Distinct instances are Natarajan-shattered by if there exist labels with for every such that
The Natarajan dimension 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 , the two definitions coincide.
The DS dimension. A nonempty finite set is a pseudo-cube if for every and every .
Definition A.3 (DS dimension ([7, 2])) Let . The DS dimension is the supremum of the integers for which there exist distinct instances such that 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 and , we say that is an -neighbor of if
Thus, an -neighbor provides an alternative label at coordinate without changing any other coordinate. A nonempty finite set is a pseudo-box with multiplicities if every has at least distinct -neighbors in for each . Here are positive integers. Following the formal definition in Hanneke et al. [13], the multiplicity counts neighbors, rather than including the label of itself.
Definition A.4 (Bandit DS dimension (Hanneke et al. [13])) Let . Distinct instances , together with positive integers , are BDS-shattered by if contains a pseudo-box with these multiplicities. The bandit DS dimension of is
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 be a nonempty binary class with . There is a universal constant such that, for every , a possibly improper learner achieves error at most with probability at least using
i.i.d. labeled examples. The guarantee holds for every distribution on and every target in .
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 have Natarajan dimension , where . For every and every choice of distinct instances ,
Proofs for the Combinatorial Dimension
Elementary refinement bounds
Proof of Lemma 5.3 Write . An admissible tree of depth inducing cells satisfies and . Hence
where the last inequality uses that is decreasing for . Taking the infimum proves the lower bound. If a tree induces at least two cells on , some query separates two labels in . The depth-one tree for that query induces two nonempty cells and has cost , proving the upper bound. The two-label claim follows. ▪
Comparison with existing dimensions
Proof of Proposition 5.6 In a pseudo-cube on 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 , proving .
For the middle inequality, assume that separates pointwise, as follows from finite query dimension by Lemma 5.5. Every nonsingleton subset of is split by some query, so Lemma 5.3 gives
Fix a witness and set
Then . If , project onto the coordinates in . For each projected vector, choose a preimage . For every , the -neighbors of project to distinct -neighbors of the projected vector. The projection is therefore a BDS witness with multiplicities , giving . This inequality is immediate if . Taking the supremum over proves .
Finally, a BDS witness with positive multiplicities is also a pseudo-cube, so . Since for every ,
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- tree therefore induces at most nonempty cells on , giving refinement cost at least . For , one query with 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 , including when the dimensions are infinite. Conversely, a BDS witness with multiplicities has at least labels in every -line. Its query cost is therefore at least by (5.4). Taking the supremum proves the reverse inequality.
Identification depth
Proof of Lemma 5.8 Fix . Let for , with . We prove by induction on that every nonempty satisfies
The case follows from . For , choose a tree attaining , which is finite by Lemma 5.5. Let be its nonempty cells, where . Then
Each cell has at most labels and is contained in , so the induction hypothesis gives for every . Attaching an identification tree for each cell to its corresponding leaf yields
The last inequality follows from
Since for , the result follows.
The extended response class
Proof of Lemma 5.10 Suppose distinct pairs are shattered by , and let be the distinct instances among the , so . Each label vector on these instances determines all responses. Consequently,
If , then , giving . If , the Natarajan–Sauer growth bound of Haussler and Long (1995) (Fact A.6) gives
Writing and taking logarithms yields
Since , every finite shattered set has size . 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 , every nonsingleton , , admits a -decision tree of depth at most whose nonempty cells have size at most . If and , then for ,
Proof When all the sets are singletons, learning requires no samples. Otherwise . By Lemma 6.4, a halving tree of depth at most supplies a query distribution for which every ball of radius contains at most half the candidates. The proof of Lemma 6.5 uses its depth parameter only through this property. With in place of , that proof gives a list-halving step using
samples and, with probability at least , discards the target on probability mass at most . Initialize the lists to and apply such steps, each using fresh samples and parameters and . The final lists are singletons. A union bound over the conditional failure probabilities shows that, with probability at least , the total probability mass on which the target has been discarded is at most . Summing the sample counts proves (B.1).
Proof of Theorem 5.12 Set
For any nonsingleton , recursively apply balanced splits, stopping each branch when its candidate set has size at most . After queries, any branch that has not stopped contains at most candidates. Since , this gives a halving tree of depth at most .
By Lemmas B.1 and 5.10, with ,
Since implies , this is when factors polylogarithmic in and are suppressed. If is non-trivial, Theorem 6.3 gives for , proving the characterization.
References
- [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]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]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]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]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]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]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]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]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]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]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]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]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.