提出首个线性样本复杂度的鲁棒学习算法，无需额外假设且近似合法。
Simplifying Adversarially Robust PAC Learning with Tolerance
- 设计近似合法的不当学习器，实现线性样本复杂度
- 在容忍设置下达到与已有半监督算法相当的性能
- 算法简洁，避免复杂子程序，适合理论研究者
对抗鲁棒PAC学习一直具有挑战性，现有最优学习器依赖复杂的压缩方案，导致样本复杂度指数级于VC维。近期工作引入容忍设置，虽改善了复杂度，但算法或仍不当、或需对假设类额外假设。本文首次证明存在简单学习器，可在不加假设条件下实现线性于VC维的样本复杂度。尽管该学习器不当，但输出的假设与某个真实假设“相似”。此外，利用该算法构造的半监督学习器，在容忍设置下表现接近Attias等人的非容忍半监督算法，但避免使用复杂子程序，且为“几乎合法”。
原文摘要 · Abstract (English)
Adversarially robust PAC learning has proved to be challenging, with the currently best known learners [Montasser et al., 2021a] relying on improper methods based on intricate compression schemes, resulting in sample complexity exponential in the VC-dimension. A series of follow up work considered a slightly relaxed version of the problem called adversarially robust learning with tolerance [Ashtiani et al., 2023, Bhattacharjee et al., 2023, Raman et al., 2024] and achieved better sample complexity in terms of the VC-dimension. However, those algorithms were either improper and complex, or required additional assumptions on the hypothesis class H. We prove, for the first time, the existence of a simpler learner that achieves a sample complexity linear in the VC-dimension without requiring additional assumptions on H. Even though our learner is improper, it is "almost proper" in the sense that it outputs a hypothesis that is "similar" to a hypothesis in H. We also use the ideas from our algorithm to construct a semi-supervised learner in the tolerant setting. This simple algorithm achieves comparable bounds to the previous (non-tolerant) semi-supervised algorithm of Attias et al. [2022a], but avoids the use of intricate subroutines from previous works, and is "almost proper."
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。