A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM|STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155719 |
| _version_ | 1811084725844967424 |
|---|---|
| author | Gaitonde, Jason Mossel, Elchanan |
| author_facet | Gaitonde, Jason Mossel, Elchanan |
| author_sort | Gaitonde, Jason |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T12:56:39Z |
| format | Article |
| id | mit-1721.1/155719 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:56:39Z |
| publishDate | 2024 |
| publisher | ACM|STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557192024-09-19T04:56:30Z A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width Gaitonde, Jason Mossel, Elchanan STOC ’24, June 24–28, 2024, Vancouver, BC, Canada We revisit the well-studied problem of e ciently learning the underlying structure and parameters of an Ising model from data. Current algorithmic approaches achieve essentially optimal sample complexity when samples are generated i.i.d. from the stationary measure and the underlying model satis es “width” constraints that bound the total ℓ1 interaction involving each node. However, these assumptions are not satis ed in some important settings of interest, like temporally correlated data or more complicated models (like spin glasses) that do not satisfy width bounds. We analyze a simple existing approach based on node-wise logistic regression, and show it provably succeeds at e ciently recovering the underlying Ising model in several new settings: (1) Given dynamically generated data from a wide variety of Markov chains, including Glauber, block, and round-robin dynamics, logistic regression recovers the parameters with sample complexity that is optimal up to log log factors. This generalizes the specialized algorithm of Bresler, Gamarnik, and Shah (IEEE Trans. Inf. Theory ’18) for structure recovery in bounded degree graphs from Glauber dynamics. (2) For the Sherrington-Kirkpatrick model of spin glasses, given poly() independent samples, logistic regression recovers the parameters in most of the proven high-temperature regime via a simple reduction to weaker structural properties of the measure. This improves on recent work of Anari, Jain, Koehler, Pham, and Vuong (SODA ’24) which gives distribution learning at higher temperature. (3) As a simple byproduct of our techniques, logistic regression achieves an exponential improvement in learning from samples in the M-regime of data considered by Dutt, Lokhov, Vu ray, and Misra (ICML ’21) as well as novel guarantees for learning from the adversarial Glauber dynamics of Chin, Moitra, Mossel, and Sandon. Our approach thus provides a signi cant generalization of the elegant analysis of logistic regression by Wu, Sanghavi, and Dimakis (Neurips ’19) without any algorithmic modi cation in each setting 2024-07-19T15:36:34Z 2024-07-19T15:36:34Z 2024-06-10 2024-07-01T07:49:02Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155719 Gaitonde, Jason and Mossel, Elchanan. 2024. "A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width." PUBLISHER_CC en 10.1145/3618260.3649674 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM|STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Gaitonde, Jason Mossel, Elchanan A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title_full | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title_fullStr | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title_full_unstemmed | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title_short | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width |
| title_sort | unified approach to learning ising models beyond independence and bounded width |
| url | https://hdl.handle.net/1721.1/155719 |
| work_keys_str_mv | AT gaitondejason aunifiedapproachtolearningisingmodelsbeyondindependenceandboundedwidth AT mosselelchanan aunifiedapproachtolearningisingmodelsbeyondindependenceandboundedwidth AT gaitondejason unifiedapproachtolearningisingmodelsbeyondindependenceandboundedwidth AT mosselelchanan unifiedapproachtolearningisingmodelsbeyondindependenceandboundedwidth |