{"ID":6267128,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08303","arxiv_id":"2607.08303","title":"Learning $\\mathsf{AC}^0$ under Locally Sampleable Graphical Models","abstract":"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.","short_abstract":"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, obta...","url_abs":"https://arxiv.org/abs/2607.08303","url_pdf":"https://arxiv.org/pdf/2607.08303v1","authors":"[\"Weiming Feng\",\"Xiongxin Yang\",\"Yixiao Yu\",\"Yiyao Zhang\"]","published":"2026-07-09T09:46:05Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DS\"]","methods":"[]","has_code":false}