提出更高效的布尔析取式学习算法，显著降低计算复杂度。
Faster Algorithms for Agnostically Learning Disjunctions and their Implications
- 设计新算法实现 $2^{\tilde{O}(n^{1/3})}$ 复杂度
- 首次在分布无关的抗干扰学习中实现对统计查询模型的超越
- 适用于需要高效鲁棒学习的机器学习场景
我们研究在无分布假设的抗干扰帕累托学习（agnostic PAC）模型下学习布尔析取式的算法任务。现有最优算法为 $L_1$-多项式回归，复杂度为 $2^{\tilde{O}(n^{1/2})}$，该复杂度在相关性统计查询（CSQ）算法类中几乎不可改进。本文提出一种新的抗干扰学习算法，复杂度降至 $2^{\tilde{O}(n^{1/3})}$，并可在统计查询（SQ）模型中实现，首次在分布无关的抗干扰学习中实现了对CSQ模型的分离。
原文摘要 · Abstract (English)
We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound is known to be nearly best possible within the class of Correlational Statistical Query (CSQ) algorithms. In this work, we develop an agnostic learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our algorithm can be implemented in the Statistical Query (SQ) model, providing the first separation between the SQ and CSQ models in distribution-free agnostic learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。