在恶意噪声下高效学习常深电路，首次实现最优噪声容忍度。
Learning Constant-Depth Circuits in Malicious Noise Models
- 用异常值剔除法结合布雷弗曼定理，抵御恶意噪声干扰。
- 可在高达1/4的恶意噪声下成功学习，达到理论最优水平。
- 适合关注鲁棒学习与复杂电路建模的研究者。
Linial、Mansour 和 Nisan 的开创性工作提出了一个准多项式时间算法，用于在超立方体均匀分布下学习常深电路（AC⁰）。然而，将该算法推广至恶意噪声环境——即协变量和标签均可能被敌意破坏——一直未得到解决。本文在此方面取得突破，受近期分布偏移学习研究启发，实现了类似运行时间的算法，该时间已被假设各种密码学原语存在时证明为最优。我们的证明采用简单的异常值剔除方法，并结合 Braverman 定理以欺骗常深电路。最终实现了对噪声率的最佳可能依赖关系，在最严苛的噪声模型（即污染或所谓的“恶劣噪声”）下仍能成功学习。
原文摘要 · Abstract (English)
The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits ($\mathsf{AC}^0$) with respect to the uniform distribution on the hypercube. Extending their algorithm to the setting of malicious noise, where both covariates and labels can be adversarially corrupted, has remained open. Here we achieve such a result, inspired by recent work on learning with distribution shift. Our running time essentially matches their algorithm, which is known to be optimal assuming various cryptographic primitives. Our proof uses a simple outlier-removal method combined with Braverman's theorem for fooling constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model (i.e., contamination or so-called "nasty noise").
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。