PAC Learning with Multiple Correct Answers

Steve Hanneke; Farnam Mansouri; Alireza F. Pour; Amirreza Shaeiri; Kun Wang

cs.LGNov 3, 2026

PAC Learning with Multiple Correct Answers

Authors: Steve Hanneke, Farnam Mansouri, Alireza F. Pour, Amirreza Shaeiri, Kun Wang

Organizations: Department of Computer Sciences, Purdue University, USA. · University of Waterloo and Vector Institute, Canada.

Abstract

We study PAC learning when each example comes with a set of at most $\ell$ correct labels and a prediction is correct if it belongs to this set. Training may reveal the full set, only whether a proposed label is correct (bandit feedback), or one correct label chosen by a demonstrator (demonstrations). Our main finding is that demonstrations can be much harder than full sets, and even than bandit feedback, both in which classes can be learned and in how many examples are needed. For finite label spaces, a generalized Natarajan dimension characterizes learnability from full sets and from bandit feedback, in both the realizable and the agnostic setting. From demonstrations, however, a class is realizably learnable if and only if the intersections of at most $\ell+1$ of its hypotheses are learnable from full sets. Already with three labels, this condition can fail for a class learnable from a single full-set example or even a single bandit answer. When the condition holds, we show that $\widetilde O(\varepsilon^{-\ell})$ demonstrations suffice, and the exponent $\ell$ cannot be improved in general, even for classes learnable from $\widetilde O(1/\varepsilon)$ full sets or bandit answers. For countable label spaces and $\ell \geq 2$ , our packed dimension, which asks for many disjoint groups of at most $\ell+1$ hypotheses with no common label, characterizes full-set learnability, and demonstrations still reduce to intersections. Agnostic learning from demonstrations, already for finite label spaces, is not determined by the dimensions of the intersection class that characterize realizable learning. Finally, we show that the uniform bound $\ell$ on the number of correct labels is essential. Without this bound, it is impossible to characterize learnability by any dimension determined by finite subclasses.

Figures & tables

Setting	Learnable if and only if	Sample complexity
finite ${\mathcal{Y}}$ , full set	$d^{\cap}_{\mathrm{N}}({\mathcal{H}})<\infty$	$\widetilde{O}_{\ell}\bigl((d+\log\frac{1}{\delta})/\varepsilon\bigr)$
finite ${\mathcal{Y}}$ , bandit	$d^{\cap}_{\mathrm{N}}({\mathcal{H}})<\infty$	$\widetilde{O}_{\ell}\bigl(k\,d\,\varepsilon^{-1}\log\frac{1}{\delta}\bigr)$
finite ${\mathcal{Y}}$ , one correct label	$d^{\cap}_{\mathrm{N}}(\mathcal{I}_{\ell+1}({\mathcal{H}}))<\infty$	$\widetilde{O}_{\ell}\bigl(d\,\varepsilon^{-\ell}\log\frac{1}{\delta}\bigr)$
countable ${\mathcal{Y}}$ , full set	$d^{\cap}_{\mathrm{pack},\gamma}({\mathcal{H}})<\infty$	$\widetilde{O}_{\ell,\gamma}\bigl((p+\log\frac{1}{\delta})/\varepsilon\bigr)$
countable ${\mathcal{Y}}$ , one correct label	$d^{\cap}_{\mathrm{pack},\gamma}(\mathcal{I}_{\ell+1}({\mathcal{H}}))<\infty$	$\widetilde{O}_{\ell,\gamma}\bigl(p\,\varepsilon^{-\ell}\log\frac{1}{\delta}\bigr)$
agnostic, one correct label	$d^{\cap}_{\mathrm{DS}}(\widetilde{\mathcal{H}})<\infty$ and local compatibility (nondegenerate ${\mathcal{H}}$ )

Table 1: Summary of results. Here

d

and

p

denote the dimensions in the second column,

k=|{\mathcal{Y}}|

\mathcal{I}_{\ell+1}({\mathcal{H}})

is the class of intersections of at most

\ell+1

hypotheses of

{\mathcal{H}}

(defined before Theorem B ),

\widetilde{\mathcal{H}}

is the collapsed class (defined before Theorem F ), and

\widetilde{O}

hides logarithmic factors. The bounds are for the realizable setting; the bandit bound is from Theorem 29 . Under full-set feedback, and under bandit feedback with finite label spaces, realizable and agnostic learnability coincide.

PAC Learning

Probably approximately correct (PAC) learning studies when finite samples can yield predictors that generalize with bounded error and confidence.

See all 48 papers

Oct 16, 2026

PAC Learning with Query Feedback

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/\varepsilon)

and an upper bound of

\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

\widetilde{O}(D/\varepsilon)

, yielding a characterization up to logarithmic factors.

Chase Hutton, Adam Melrod, Han Shao

University of Maryland · Harvard University

PAC Learning Multiclass Classification Active Learning

Ask PDF

Aug 31, 2026

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

How much does high confidence cost when a multiclass learner sees only whether its prediction is correct? We separate two behaviors in realizable bandit PAC learning. An anchored dimension gives a general lower bound that is attained, up to universal constants, by a family of product-block classes. In contrast, for

n\ge16

divisible by four, an affine multiplexer with bandit DS dimension

2n-1

has sample complexity

Θ((n\min\{n,\ln(1/δ)\}+\ln(1/δ))/\varepsilon)

in the standard accuracy and confidence regime. Its lower bound applies to adaptive randomized learners with improper outputs. The obstruction is that evidence collected against one candidate group cannot be reused against the others. The better of two algorithms matches this cost. One finds the correct group through a positive response. The other exhausts the rank of successive groups. The resulting confidence profile rules out a universal additive-confidence bound linear in the bandit DS dimension. Moreover, classes with identical anchored dimension, bandit DS dimension, and pointwise label width can have polynomially different sample complexities. We also sharpen the confidence accounting in ListCascade and show how one positive response replaces the bandit DS dimension by the anchored dimension in a general upper bound.

Guangjian Zhang, Zhengyi Yang, Xiaoyang Wang

PAC Learning Statistical Learning Theory Sample Complexity Multiclass Classification

Ask PDF

May 25, 2026

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space

\mathcal{X}

and a label space

\mathcal{Y}

, as in classical multiclass PAC learning, but the learner does not observe the labels of the i.i.d. training examples. Instead, in each round, it receives an unlabeled instance, predicts its label, and receives bandit feedback indicating only whether the prediction is correct. Despite this restriction, the goal remains the same as in classical PAC learning. We provide a general characterization of the optimal sample complexity of this problem, sharp for every concept class up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the bandit

\mathrm{DS}

dimension, defined via generalized combinatorial structures we call pseudo-boxes. These extend the pseudo-cubes underlying the

\mathrm{DS}

dimension by allowing a different number of neighbors in each coordinate. In contrast to the

\mathrm{DS}

dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit

\mathrm{DS}

dimension aggregates the number of neighbors across coordinates, leading to a characterization in which the sample complexity scales with the total number of neighbors. We also propose a general learning algorithm achieving the upper bound, based on an algorithmic principle called ListCascade, which connects bandit learning to list learning and may be of independent interest.

Steve Hanneke, Qinglin Meng, Shay Moran +1

Department of Computer Science Purdue University West Lafayette, IN, USA · Faculties of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology and Google Research Haifa, Israel

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Ask PDF

Abstract

PAC Learning

Explore similar work

PAC Learning with Query Feedback

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting