Search papers, labs, and topics across Lattice.
This paper introduces a quasipolynomial-time learner for constant-depth circuits ($\mathsf{AC}^0$) that operates under locally sampleable graphical models, effectively bypassing the polynomial-growth constraint of previous methods. By leveraging a novel low-degree approximation for Gibbs distributions through simulated and truncated Glauber dynamics, the authors extend learning guarantees to a broader class of correlated distributions. The results include practical applications for learners in two-spin systems, such as the hard-core and Ising models, on arbitrary bounded-degree graphs near their sampling thresholds.
Learning $\mathsf{AC}^0$ circuits just got easier鈥攏ow you can do it under locally sampleable graphical models without the polynomial-growth limitation.
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.
