首个可验证学习高斯分布下马萨特噪声半空间的算法
Testable Learning of General Halfspaces under Massart Noise
- 设计测试-学习协同框架，满足通过即输出近优解
- 复杂度为 d^{polylog(min{1/γ, 1/ε})}，逼近理论下界
- 提出带乘性误差的符号函数新多项式逼近法
我们研究在高斯分布下对一般马萨特半空间进行可验证学习的算法任务。在可验证学习设定中，目标是设计一个测试器-学习器对，满足：(1) 若测试器接受，则学习器输出一个假设及证明其接近最优错误率的证书；(2) 当数据满足底层假设时，测试器几乎不可能拒绝。本文的主要成果是首个针对具有马萨特噪声和高斯边缘的一般半空间的可验证学习算法。该算法复杂度为 $d^{ ext{polylog}( ext{min}igrace{1/γ, 1/εigrace})}$，其中 $ε$ 为超出误差，$γ$ 为目标半空间的偏差，其量级与非可验证设置下的已知准多项式统计查询下界一致。算法分析依赖于一种新的符号函数乘性误差多项式夹逼构造，可能具有更广泛意义。
原文摘要 · Abstract (English)
We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-learner pair satisfying the following properties: (1) if the tester accepts, the learner outputs a hypothesis and a certificate that it achieves near-optimal error, and (2) it is highly unlikely that the tester rejects if the data satisfies the underlying assumptions. Our main result is the first testable learning algorithm for general halfspaces with Massart noise and Gaussian marginals. The complexity of our algorithm is $d^{\mathrm{polylog}(\min\{1/γ, 1/ε\})}$, where $ε$ is the excess error and $γ$ is the bias of the target halfspace, which qualitatively matches the known quasi-polynomial Statistical Query lower bound for the non-testable setting. The analysis of our algorithm hinges on a novel sandwiching polynomial approximation to the sign function with multiplicative error that may be of broader interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。