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

• URL: http://arxiv.org/abs/2607.08303v1
• Date: Thu, 09 Jul 2026 09:46:05 GMT
• Title: Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
• Abstract summary: We give a quasipolynomial-time learner for $mathsfAC0$ under graphical models with strong spatial mixing and growth.<n>The framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs.
• Score: 1.4816117998909835
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Learning $\mathsf{AC}^0$ Under Graphical Models [21.66293630099673]
  We show how new sampling algorithms allow us to transfer statements about low-degree approximation under the uniform setting to graphical models.<n>Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.
  arXiv  Detail & Related papers  (2026-04-07T17:20:35Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• Structure Learning in Gaussian Graphical Models from Glauber Dynamics [6.982878344925993]
  We present the first algorithm for Gaussian model selection when data are sampled according to the Glauber dynamics.<n>We provide guarantees on the computational and statistical complexity of the proposed algorithm's structure learning performance.
  arXiv  Detail & Related papers  (2024-12-24T18:49:13Z)
• Differentiable DG with Neural Operator Source Term Correction [0.0]
  We introduce an end-to-end differentiable framework for solving the compressible Navier-Stokes equations.<n>This integrated approach combines a differentiable discontinuous Galerkin solver with a neural network source term.<n>We demonstrate the performance of the proposed framework through two examples.
  arXiv  Detail & Related papers  (2023-10-29T04:26:23Z)
• Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
  We develop continuous-time (birth-death) and discrete-time (reversible jump) Markov chain Monte Carlo (MCMC) algorithms that efficiently explore the posterior over graph space.<n>The algorithms scale to large graph spaces, enabling parallel exploration for graphs with over 1,000 nodes.
  arXiv  Detail & Related papers  (2023-06-30T20:37:40Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Efficient Learning of Quadratic Variance Function Directed Acyclic Graphs via Topological Layers [18.91995406229772]
  We study a special class of non-Gaussian DAG models, where the conditional variance of each node given its parents is a quadratic function of its conditional mean. To facilitate learning, we introduce a novel concept of topological layers, and develop an efficient DAG learning algorithm.
  arXiv  Detail & Related papers  (2021-11-01T07:44:16Z)
• GIST: Distributed Training for Large-Scale Graph Convolutional Networks [18.964079367668262]
  GIST is a hybrid layer and graph sampling method, which disjointly partitions the global model into several, smaller sub-GCNs. This distributed framework improves model performance and significantly decreases wall-clock training time. GIST seeks to enable large-scale GCN experimentation with the goal of bridging the existing gap in scale between graph machine learning and deep learning.
  arXiv  Detail & Related papers  (2021-02-20T19:25:38Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  We show that global convergence is statistically intractable even for one-layer neural net bandit with a deterministic reward. For both nonlinear bandit and RL, the paper presents a model-based algorithm, Virtual Ascent with Online Model Learner (ViOL)
  arXiv  Detail & Related papers  (2021-02-08T12:41:56Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.