Learning $\mathsf{AC}^0$ Under Graphical Models

Gautam Chandrasekaran; Jason Gaitonde; Ankur Moitra; Arsen Vasilyan

cs.LGApr 7, 2026

Learning $\mathsf{AC}^0$ Under Graphical Models

Authors: Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan

Organizations: University of Texas at Austin. · Duke University. · Massachusetts Institute of Technology.

Abstract

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.

Figures & tables

Function Class	Uniform	Graphical Models ( this work )
Polysize Constant-Depth Circuits	$O(\log^{d-1}(n)\cdot\log(1/\varepsilon))$ [ 90 ]	$O(\log^{Cd}(n)\cdot\log(1/\varepsilon))$
Monotone Functions	$O(\sqrt{n}/\varepsilon)$ [ 18 ]	$O(\log^{C}(n)\cdot\sqrt{n}/\varepsilon)$

Table 1: Comparison of

\ell_{2}

-approximation degree between uniform distribution and graphical models satisfying small spatial mixing, polynomial neighborhood growth and bounded marginals. The constant

C

in the second column is a distribution dependent quantity and

d

is the depth of the circuit. We refer to Theorems 7.2 and 7.11 for the precise statements.

Function Class	Uniform	Dobrushin Ising Model ( this work )
Halfspaces	$O(\log(1/\varepsilon)/\varepsilon^{2})$ [ 36 ]	$O(\log^{2}(1/\varepsilon)/\varepsilon^{2})$

Table 2: Comparison of

\ell_{1}

-approximation degree for halfspaces between uniform distribution and Ising models under Dobrushin’s condition. We refer to Theorem 8.16 for a precise statement.

r:=\frac{\log\left(\frac{4C_{\mathsf{SSM}}n}{\eta\cdot\varepsilon}\right)}{\delta};

Algorithm 1

\bm{y}=\mathsf{SSMSamp}(\bm{x};\mu,\varepsilon)

T_{u}=\{\mathrm{Pa}(u)\}

Algorithm 2

\bm{y}=\mathsf{TreeSamp}(\bm{x};\mu,v)

r:=\frac{2\log(n/2\varepsilon^{\prime})}{\eta};

Algorithm 3

\bm{y}=\mathsf{LocalTreeSamp}(\bm{x};\mu,v,\varepsilon^{\prime})

Low-Degree Polynomial Method

See all 15 papers

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
Jul 9, 2026Weiming Feng, Xiongxin Yang, Yixiao Yu +1Boolean Function Learning Low-Degree Polynomial Method
School of Computing and Data Science, The University of Hong Kong. · Department of Computer Science, University of California, Santa Barbara. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1Sample Compression Halfspace Learning
Purdue University · Stanford University · Google Research +1
Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego

Jul 9, 2026J/K move · Enter open · S save

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models

Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

School of Computing and Data Science, The University of Hong Kong. · Department of Computer Science, University of California, Santa Barbara. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning Low-Degree Polynomial Method

Open paper AskPDF arXiv

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.

Abstract

Low-Degree Polynomial Method

Explore similar work

Learning AC0\mathsf{AC}^0AC0 under Locally Sampleable Graphical Models

What is Learnable in Valiant's Theory of the Learnable?

Actively Learning Halfspaces without Synthetic Data

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models