证明平滑提升的样本复杂度下界，揭示其理论极限
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
- 设计一类可弱学习的样本集，支持平滑分布上的γ优势
- 强学习在均匀分布下需约1/γ²倍于弱学习的样本数
- 揭示平滑提升与硬核定理间深层联系，解决理论瓶颈
平滑提升器生成的分布不会对任一样本赋予过高权重。最初因其抗噪声能力被提出，后应用于差分隐私、可复现性及量子学习理论。本文研究并确定了平滑提升的样本复杂度：存在一类问题，可在m个样本上以γ优势实现弱学习，但在均匀分布下的强学习需至少˜Ω(1/γ²)·m个样本，该结果与现有平滑提升器的开销一致。这首次区分了平滑提升与分布无关提升（后者开销为O(1/γ)）。本工作还深化了对复杂性理论中Impagliazzo硬核定理的理解，所有已知证明均可归入平滑提升框架。对于大小为s的电路难以计算的函数f，硬核定理给出一个输入集，使其在大小为s'的电路下极难计算。但已有方法存在电路规模损失（s' ≪ s）。回答Trevisan的问题，我们证明该损失不可避免，且现有参数已达最优。
原文摘要 · Abstract (English)
Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to $γ$-advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tildeΩ(1/γ^2)\cdot m$ samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is $O(1/γ)$. Our work also sheds new light on Impagliazzo's hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function $f$ that is mildly hard against size-$s$ circuits, the hardcore theorem provides a set of inputs on which $f$ is extremely hard against size-$s'$ circuits. A downside of this important result is the loss in circuit size, i.e. that $s' \ll s$. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。