🤖 machine learning

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

This paper presents a quasipolynomial-time algorithm for learning $\mathsf{AC}^0$ circuits under graphical models with efficient local samplers by introducing a new low-degree approximation via truncated Glauber dynamics, thereby extending prior learning guarantees to arbitrary bounded-degree graphs without requiring polynomial growth.

Original authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize patterns in a very crowded, chaotic room. The room is full of people (variables) who are all whispering to their neighbors. If you shout a question to one person, the answer they give depends heavily on what their friends are saying. This is what scientists call a Gibbs distribution or a graphical model: a system where everything is connected and correlated, making it a nightmare to predict or learn from.

For a long time, computer scientists had a superpower for learning patterns, but it only worked in a "quiet room" where everyone shouted their answers independently (called a product distribution). In 2026, a team of researchers (Feng, Yang, Yu, and Zhang) managed to bring this superpower into the noisy, crowded room, but they hit a wall: they could only do it if the room wasn't too big or complex (specifically, if the number of people within a certain distance didn't grow too fast, a rule called polynomial growth).

The Big Breakthrough
This paper proves that you don't need that "room size" rule to teach the robot. The authors show that as long as the room has a local sampler—a clever way to figure out what one person is saying by only peeking at a tiny, local neighborhood of friends—you can teach the robot to learn AC0 circuits (which are basically simple, shallow decision-making machines) with high accuracy.

They didn't just guess this; they proved it mathematically. They built a new learning algorithm that runs in quasipolynomial time (which is fast enough to be useful, though not instant) and works on any graph with a limited number of neighbors per person, even if the graph is a giant, complex web like an expander graph or a random network where the "crowd" grows exponentially.

How They Did It: The "Time-Traveling" Detective
To make this work, the authors used a brilliant trick involving a game of "telephone" played in reverse.

The Forward Game (The Sampler): Imagine a game where you start with a blank slate and update people's opinions one by one in a circle. To make this predictable, they introduced "magic dice" (called marks). If you roll a specific number, a person's opinion is forced; if you roll another, they look at their neighbors. By rolling these dice in a specific order, you can simulate the whole room's state.
The Backward Game (The Inverter): This is the magic part. Usually, if you know the final state of the room, you can't easily guess which dice were rolled to get there. But the authors realized that if the "dice" are rolled in a way that the final result doesn't depend on how the game started (a concept they call a determining mark sequence), you can run the game backwards.
The Local Detective: They showed that for many systems (like the hard-core model where neighbors can't both be "occupied," or the Ising model where neighbors like to agree or disagree), you can figure out the final opinion of just one person by only looking at a tiny, local cluster of friends and their specific dice rolls. You don't need to know the whole room's history.

The "Truncation" Trick
Here is the playful part: The authors realized that these backward-detective games usually finish very quickly. The "influence" of the starting conditions dies out fast. So, they decided to cut the game short. They told the detective, "Stop looking after you've checked about $\log(n)$ friends."

Because the detective almost always finishes before hitting the time limit, cutting the game off introduces almost no error. This "truncation" turns a complex, infinite-looking process into a simple, short list of steps. This short list can be written as a low-degree polynomial (a simple math formula). Since the formula is simple, the robot can learn it quickly using standard techniques.

What They Ruled Out
The paper explicitly argues against the idea that you need the "polynomial growth" rule (where the room can't get too crowded too fast) to learn these patterns. Previous work said, "If the room gets too big too fast, we can't learn it." This paper says, "Nope! As long as you can peek locally, the size of the room doesn't matter."

They also clarify that this is not about learning the structure of the room itself (figuring out who is friends with whom). That's a different problem. This paper assumes you already know the room's layout and just want to learn a specific rule (function) that operates inside it.

The Proof and The Numbers
The authors didn't just simulate this on a computer; they provided a rigorous mathematical proof.

They proved that for the hard-core model (where neighbors can't both be "on"), the learning works if the "fugacity" (a measure of how much people want to be "on") is less than roughly $1/(\Delta - 1)$ , where $\Delta$ is the maximum number of neighbors. This is a very tight, almost perfect condition.
For the Ising model (where neighbors interact), they proved it works if the interaction strength $\beta$ is within a specific range around 1 (roughly $1 - \frac{1}{2\Delta} < \beta < 1 + \frac{1}{2\Delta}$ ).
The learning algorithm needs roughly $n^{\log^{O(d)}(n/\varepsilon)}$ samples and time, where $n$ is the number of people, $d$ is the depth of the circuit, and $\varepsilon$ is the error you can tolerate.

The Bottom Line
This paper is a proven result. It connects the dots between "local samplers" (tools that let you peek at a small part of a system) and "learning theory" (teaching computers to find patterns). It shows that even in a chaotic, highly connected world, if you have a way to peek locally, you can teach a machine to understand the big picture without needing the world to be small or simple. It's like teaching a detective to solve a city-wide mystery just by interviewing a few blocks at a time, proving that you don't need to interview everyone to get the truth.

Technical Summary: Learning AC0 under Locally Sampleable Graphical Models

Problem Statement

The paper addresses the fundamental problem of learning constant-depth Boolean circuits (specifically the class $\text{AC}^0$ ) under correlated probability distributions. While the seminal work of Linial, Mansour, and Nisan (LMN93) established that $\text{AC}^0$ circuits admit low-degree Fourier approximations under the uniform distribution (leading to quasipolynomial-time learners), extending these guarantees to correlated distributions has remained a significant challenge.

The authors focus on learning an unknown function $f \in \text{AC}^0$ given samples $(x, f(x))$ where $x$ is drawn from a Gibbs distribution $\mu$ defined on a graphical model (a Markov Random Field). Previous progress by Chandrasekaran et al. (CGMV26) provided learning guarantees for Gibbs distributions on bounded-degree graphs, but only under the restrictive assumption of polynomial growth (i.e., the number of vertices within distance $\ell$ is polynomial in $\ell$ ). This assumption excludes important classes of graphs like expanders and Erdős-Rényi random graphs, where the volume of a ball grows exponentially.

The central question is: Can one learn $\text{AC}^0$ under Gibbs distributions on general bounded-degree graphs without the polynomial-growth requirement?

Methodology

The paper introduces a new framework that bypasses the polynomial-growth obstruction by leveraging local samplers. The core methodology involves constructing a low-degree polynomial approximation for $f$ under the Gibbs measure $\mu$ by transferring the approximation from a product space of random bits used in a sampling procedure.

1. The Samp–InvSamp Framework

The authors adapt the abstract Samp–InvSamp framework. The goal is to approximate $f$ under $\mu$ by:

Samp: A sampler that maps a string of random marks $\rho$ to a configuration $\sigma \sim \mu$ .
InvSamp: An inverse sampler that, given a configuration $\sigma$ , recovers a random mark string $\rho$ consistent with the sampling path.

If $f \circ \text{Samp}$ can be approximated by a low-degree polynomial $g$ over the product space of marks, and if $\text{InvSamp}$ has low "degree" (i.e., its output depends on only a few coordinates of $\sigma$ ), then $g \circ \text{InvSamp}$ provides a low-degree approximation for $f$ under $\mu$ .

2. Systematic-Scan Glauber Dynamics as the Sampler

Instead of relying on strong spatial mixing (which requires polynomial growth to bound the dependency radius), the authors use Systematic-Scan Glauber Dynamics as the sampler.

Forward Process: The chain starts from a fixed configuration $\sigma_0$ and updates vertices in a cyclic order $u_1, \dots, u_T$ . Each update is implemented via a deterministic rule $\psi_t$ driven by a random "mark" $\rho_t$ .
Determining Mark Sequences: A key insight is that if the mark sequence $\rho$ is "determining," the final configuration $\sigma_T$ becomes independent of the initial configuration $\sigma_0$ . This allows the fixed-initialization sampler to behave as if it were initialized from the stationary distribution $\mu$ .
Local Samplers: The authors utilize Local Computation Algorithms (LCAs) for sampling. These are automata that resolve the spin of a specific vertex $v$ by querying only a local neighborhood of the mark sequence and the initial configuration. Crucially, these local samplers terminate quickly with high probability, even on graphs with exponential growth, provided the Gibbs distribution satisfies certain mixing conditions.

3. Truncation and Low-Degree Approximation

To ensure the resulting polynomial has low degree:

The local samplers (both forward and backward) are truncated after a polylogarithmic number of steps.
The authors prove that the truncation error is small because the probability of the sampler not terminating within the truncated depth decays exponentially.
The composition of the truncated sampler/inverter with the $\text{AC}^0$ function $f$ results in a function that can be computed by a constant-depth, polynomial-size circuit over the mark space.
Using an extension of Tal's Fourier tail bounds to finite product domains (Section 4), they show that such circuits admit low-degree polynomial approximations.

Key Contributions

Removal of Polynomial Growth Assumption: The paper establishes learning guarantees for $\text{AC}^0$ under Gibbs distributions on general bounded-degree graphs, eliminating the need for the polynomial-growth assumption required by prior work (CGMV26).
New Connection between LCAs and Learning: The work bridges the gap between Local Computation Algorithms (specifically local samplers for Gibbs distributions) and the learning of Boolean functions. It demonstrates that the existence of efficient local samplers implies the existence of low-degree approximations for $\text{AC}^0$ .
Generalized Low-Degree Approximation: The authors provide a technical extension of the low-degree approximation theorem for $\text{AC}^0$ circuits from the Boolean cube to general finite product domains (Theorem 4.2), which is necessary for handling the non-Boolean mark alphabets used in the sampling simulators.
Bi-directional Good Local Sampler Condition: They define a "bi-directional good local sampler" condition (Condition 5.6) that ensures both the forward sampling and backward inversion can be performed locally and efficiently.

Results

The paper provides quasipolynomial-time learning algorithms for $\text{AC}^0$ under specific graphical models on arbitrary bounded-degree graphs:

Hard-Core Model: Learning is possible for fugacity $\lambda < (1-\eta)/(\Delta-1)$ . This condition is only a constant factor stronger than the classical Dobrushin threshold, whereas the previous strong spatial mixing condition required $\lambda < (\Delta-1)^{\Delta-1}/(\Delta-2)^\Delta$ .
Soft-Constraint Models (including Ising): Learning is possible for interaction matrices satisfying a normalized soft-constraint condition. For the Ising model with edge activity $\beta$ , learning holds when $\beta$ is within a constant factor of 1 (specifically $1 - \frac{1-\eta}{2\Delta} < \beta < (1 - \frac{1-\eta}{2\Delta})^{-1}$ ).
Complexity: The learning algorithm runs in time $n^{\log^{O(d)}(n/\varepsilon)}$ and requires $n^{\log^{O(d)}(n/\varepsilon)}$ samples, where $d$ is the circuit depth and $n$ is the number of vertices. The hidden constants depend only on the degree $\Delta$ , the circuit parameters, and the mixing parameters of the model.

Significance and Claims

The paper claims that its primary significance lies in circumventing the polynomial-growth requirement, thereby extending the scope of learnable correlated distributions to include expander graphs and random graphs. By connecting the efficiency of local samplers (a concept from the sampling literature) to the learnability of Boolean functions, the authors provide a robust mechanism for learning under dependence that does not rely on geometric constraints.

The authors modestly frame their contribution as a "new connection" and a "framework" that yields learners for specific regimes of the hard-core and Ising models. They do not claim to solve learning for all Gibbs distributions, but rather for those that admit efficient local samplers, which covers a broad and practically relevant class of models on general graphs. The work represents a step toward understanding learning under genuinely dependent distributions beyond the specific geometric settings previously studied.