Learning Juntas Under Markov Random Fields

Abstract

We give an algorithm for learning $O(\log n)$ juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework, where only the external field has been randomly perturbed. This is a broad generalization of the work of Kalai and Teng, who gave an algorithm that succeeded with respect to smoothed *product* distributions (i.e., MRFs whose dependency graph has no edges). Our algorithm has two phases: (1) an unsupervised structure learning phase and (2) a greedy supervised learning algorithm. This is the first example where algorithms for learning the structure of undirected graphical models have downstream applications to supervised learning.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Chandrasekaran and Klivans. "Learning Juntas Under Markov Random Fields." Advances in Neural Information Processing Systems, 2025.

Markdown

[Chandrasekaran and Klivans. "Learning Juntas Under Markov Random Fields." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/chandrasekaran2025neurips-learning/)

BibTeX

@inproceedings{chandrasekaran2025neurips-learning,
  title     = {{Learning Juntas Under Markov Random Fields}},
  author    = {Chandrasekaran, Gautam and Klivans, Adam},
  booktitle = {Advances in Neural Information Processing Systems},
  year      = {2025},
  url       = {https://mlanthology.org/neurips/2025/chandrasekaran2025neurips-learning/}
}