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

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

URL: http://arxiv.org/abs/2604.06109v1
Date: Tue, 07 Apr 2026 17:20:35 GMT
Title: Learning $\mathsf{AC}^0$ Under Graphical Models
Abstract summary: 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.
Score: 21.66293630099673
License: http://creativecommons.org/licenses/by/4.0/
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.

Related papers

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models [1.4816117998909835]
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.
arXiv Detail & Related papers (2026-07-09T09:46:05Z)
Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model [53.6316818897326]
We propose a gradient-based algorithm for training a two-layer neural network in time.<n>We show that our algorithm learns a sparse representation that strongly aligns with the unknown signal $star$.<n>We extend our approach to the setting where $star$ is $k$-sparse for $k = o(sqrtd)$ by introducing a novel weight technique.
arXiv Detail & Related papers (2026-06-13T09:34:39Z)
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)
Beyond Softmax: A Natural Parameterization for Categorical Random Variables [61.709831225296305]
We introduce the $textitcatnat$ function, a function composed of a sequence of hierarchical binary splits.<n>A rich set of experiments show that the proposed function improves the learning efficiency and yields models characterized by consistently higher test performance.
arXiv Detail & Related papers (2025-09-29T12:55:50Z)
Learning with Exact Invariances in Polynomial Time [43.81087760363805]
We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression.<n>Our approach achieves the same excess population risk as the original kernel regression problem.
arXiv Detail & Related papers (2025-02-27T04:49:52Z)
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
We study the efficient learnability of low-degree threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions.
arXiv Detail & Related papers (2024-03-31T02:03:35Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z)
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
arXiv Detail & Related papers (2020-11-09T18:32:22Z)
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
arXiv Detail & Related papers (2020-10-04T22:19:06Z)

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