Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.00764 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912408313790464 |
|---|---|
| author | Chandrasekaran, Gautam Klivans, Adam |
| author_facet | Chandrasekaran, Gautam Klivans, Adam |
| contents | 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 an undirected graphical model lead to provably efficient algorithms for supervised learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Juntas under Markov Random Fields Chandrasekaran, Gautam Klivans, Adam Machine Learning Data Structures and Algorithms 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 an undirected graphical model lead to provably efficient algorithms for supervised learning. |
| title | Learning Juntas under Markov Random Fields |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.00764 |