Research map / Learning theory and algorithms / Sample complexity

Learning Juntas under Markov Random Fields

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends smoothed-analysis junta learning from product distributions to smoothed Markov Random Fields with known bounded-degree dependency graphs, via a Markov-conditioned correlation statistic and brute-force learning on the found relevant variables.

Problem

Learning k-juntas (with k = O(log n)) under distributions that are MRFs with only external-field perturbation (smoothed), where prior smoothed results only covered product distributions.

Approach

Replace the unconditional label-feature correlation statistic with one conditioned on the neighbourhood of each variable in the dependency graph (exploiting the Markov property to kill irrelevant-variable correlations), prove relevant variables have a neighbourhood restriction with large statistic under smoothing, then brute-force learn the junta on the found variables.

Key results

• Algorithm learns a k-junta exactly (zero error w.h.p.) under (sigma,lambda)-smooth MRFs with known degree-d dependency graph using N = poly(log n, exp(lambda(d+k)), 2^{d+k}, sigma^{-k}, 1/delta) samples.
• For d, k = O(log n) and lambda, sigma = O(1), the algorithm runs in polynomial time.
• Relevant-variable statistic I(i,rho) is exactly zero for irrelevant variables under Markov property, and at least gamma^2 (sigma exp(-lambda)/16)^{k+2} for some neighbourhood restriction of relevant variables with probability 1-gamma.

Surprising findings

• Structure learning of the MRF dependency graph is used directly to enable efficient supervised learning, which the authors say is the first such example.

Limitations

• Requires the dependency graph G to be known (or learned separately with poly(n^t, 2^lambda) cost).
• Runtime is only polynomial for O(log n) degree and junta size; exponential in k and d otherwise.
• Only the external field is smoothed, and bounded derivative norm lambda is assumed.

Experimental setup

Metrics: sample complexity running time exact recovery probability

Baselines: Kalai and Teng (smoothed product distributions) Kanade and Mossel random walk learner brute force n^{O(k)} search

Builds on: Kalai and Teng smoothed product distribution learning Hammersley-Clifford theorem polynomial anticoncentration lemma

Closest papers by meaning

• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma (AAAI 2023 · similarity 0.87)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.84)
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.83)
• Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.83)
• Learning Partitions from Context (NeurIPS 2024 · similarity 0.83)
• The Benefits of Temporal Correlations: SGD Efficiently Learns k-Juntas from Random Walks (NeurIPS 2026 · similarity 0.83)