Learning $\mathsf{AC}^0$ Under Graphical Models
2026-04-07 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors build on a famous algorithm by Linial, Mansour, and Nisan for learning simple Boolean circuits from random examples, which worked well when inputs are independent. They address the harder problem of learning when inputs are correlated, not independent, especially in structured settings called graphical models that have local dependencies. The key idea is creating new sampling methods that let them apply low-degree polynomial approximations, previously used only for independent inputs, to these more complex scenarios. Their methods can also be applied to other types of functions beyond simple circuits.
Learning theoryAC^0 circuitsGraphical modelsStrong spatial mixingLow-degree polynomial approximationFourier analysisQuasipolynomial-time algorithmsMonotone functionsHalfspaces
Authors
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan
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.