提出新算法，可在任意有界度图上高效学习常数深度电路。
Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
- 基于截断的Glauber动态构造吉布斯分布的低度近似。
- 在逼近采样阈值的条件下，成功学习硬核模型与伊辛模型。
- 适用于可高效局部采样的图模型，突破前人多项式增长限制。
常数深度电路的学习问题在计算学习理论中具有深远意义。林尼亚尔、曼索尔和尼斯安（J. ACM 1993）通过引入低度算法，首次实现了在均匀分布下对$$\mathsf{AC}^0$的准多项式时间学习。然而，对更广泛相关分布的类似学习保证仍是一个长期挑战。最近，钱德拉塞卡拉、盖通德、莫伊特拉与瓦西里安（arXiv 2026）将这些保证扩展到具有强空间混合性和多项式增长的有界度图模型上的吉布斯分布。本文提出一种在可高效局部采样的图模型下对$$\mathsf{AC}^0$的准多项式时间学习算法，绕过了先前工作中的多项式增长要求。核心是通过模拟并适当截断经典Glauber动力学，建立了吉布斯分布的新低度近似。作为应用，该框架在逼近各自采样阈值的条件下，为两类自旋系统——包括硬核模型与伊辛模型——提供了学习器，适用于任意有界度图。
原文摘要 · Abstract (English)
The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for $\mathsf{AC}^0$ under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for $\mathsf{AC}^0$ under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。