通过编码理论新思路，用更少轮次实现高效学习。
Boosting with List-Decodable Codes
- 将弱学习器输出视为被污染的码字，用列表解码找候选强假设。
- 对满足异或封闭性的概念类，仅需O(log(1/ε))轮即可强学习。
- 适合研究学习理论与编码结合的学者，尤其关注高效学习算法者。
Boosting 是一种基础技术，可通用提升学习算法的精度（Schapire 1989）。现有方法在所有概念类上需调用 $O(\log(\frac{1}{\varepsilon})/\gamma^2)$ 次 $\gamma$-优势弱学习器，且此轮数下界已被证明为最优（Freund 1995）。本文发现：若概念类 $\mathcal{F}$ 满足 $O(\log \frac{1}{\gamma})$-XOR 封闭性，则可突破该下界。我们提出新提升算法，对任意满足此性质的 $\mathcal{F}$，仅需 $O(\log \frac{1}{\varepsilon})$ 次弱学习器调用和单批次 $\tilde{O}(\log(\frac{1}{\varepsilon})/\gamma^2)$ 额外样本，即可强学习 $\mathcal{F}$。该算法源于提升与列表可解码码的新简单关联：将目标函数视为消息，对编码后的函数运行弱学习器，其输出视为受损码字；将其输入列表解码器，获得候选假设列表，其中至少有一个是原函数的强假设；利用额外样本选出并输出该强假设。
原文摘要 · Abstract (English)
Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}ε)/γ^2)$ calls to a $γ$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}γ)$-XOR, strong learns $\mathcal{F}$ using $O(\log \frac{1}ε)$ calls to a $γ$-advantage weak learner and a single batch of $\tilde{O}(\log(\frac{1}ε)/γ^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。