跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.05133 · v2

PAC Learning with Multiple Correct Answers

Steve HannekeFarnam MansouriAlireza F. PourAmirreza ShaeiriKun Wang
cs.LG
首次提交 2026-11-04 00:15
版本更新 2026-11-04 14:37
雷达观测 2026-11-05 11:10
arXiv ↗PDF ↗

摘要

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.

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存，登录后共享已有结果。

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

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 (emonstrationsdemonstrations). 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.

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-04 14:37 · 最新观测版本

PAC Learning with Multiple Correct Answers

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.

查看此版本解读 →查看此版本原文 ↗
v1 · 2026-11-04 00:15

PAC Learning with Multiple Correct Answers

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 (emonstrations). 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.

查看此版本解读 →查看此版本原文 ↗