在相关分布下高效学习低深度电路，突破传统独立假设限制。
Learning $\mathsf{AC}^0$ Under Graphical Models
- 用采样算法绕过傅里叶分析瓶颈，实现非独立输入下的学习
- 在强空间混合的图模型上，实现准多项式时间学习
- 适用于单调函数、半空间等其他经典函数类，方法具通用性
Linial、Mansour 与 Nisan（J. ACM 1993）提出一个准多项式时间算法，可在均匀分布下学习常数深度电路。该工作开创了低度算法这一重要方向，但其依赖于独立同分布假设，在现实场景中难以成立。本文首次在更自然的相关分布下，针对任意具有多项式增长且满足强空间混合的图模型，给出 $ extsf{AC}^0$ 的准多项式时间学习算法。核心挑战在于克服傅里叶分析在相关分布中的失效问题，我们通过设计新型采样算法，将均匀分布下的低度多项式逼近结论推广至图模型。该方法具有通用性，可扩展至单调函数和半空间等经典函数类。
原文摘要 · Abstract (English)
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introducing the $\textit{low-degree algorithm}$. However, an important critique of many results and techniques in the area is the reliance on product structure, which is unlikely to hold in realistic settings. Obtaining similar learning guarantees for more natural correlated distributions has been a longstanding challenge in the field. In particular, we give quasipolynomial-time algorithms for learning $\mathsf{AC}^0$ substantially beyond the product setting, when the inputs come from any graphical model with polynomial growth that exhibits strong spatial mixing. The main technical challenge is in giving a workaround to Fourier analysis, which we do by showing how new sampling algorithms allow us to transfer statements about low-degree polynomial approximation under the uniform setting to graphical models. Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。