让学习者只在可采样分布上有效，能大幅降低学习难度。
Samplability makes learning easier
- 引入可采样分布限制，使学习更高效
- 存在类需指数样本的常规学习，却可多项式样本学习
- 适用于关注实际采样条件的学习算法研究者
标准PAC学习要求学习者在所有分布下都有效，包括难以采样的分布。而可采样PAC学习仅要求在可采样分布下成功。本文研究此差异，证明可采样PAC显著提升了高效学习者的性能。首先构造一个概念类：在标准PAC下需指数样本复杂度，但在可采样PAC下只需多项式样本复杂度。进一步将此统计分离提升至计算设定，得到相对于随机预言机的分离结果。证明核心是一种新引入的复杂性原语——显式回避集：成员判定容易，但采样极其困难。结果还扩展到在线学习场景，表明当对手为高效而非计算无界时，学习格局发生根本变化。
原文摘要 · Abstract (English)
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show how its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。