dc.contributor.author Gangrade, Aditya en_US dc.contributor.author Nazer, Bobak en_US dc.contributor.author Saligrama, Venkatesh en_US dc.date.accessioned 2021-11-29T20:58:27Z dc.date.available 2021-11-29T20:58:27Z dc.date.issued 2020 dc.identifier.citation A. Gangrade, B. Nazer, V. Saligrama. 2020. "Limits on Testing Structural Changes in Ising Models." Advances in Neural Information Processing Systems. https://arxiv.org/abs/2011.03678 dc.identifier.uri https://hdl.handle.net/2144/43421 dc.description.abstract We present novel information-theoretic limits on detecting sparse changes in Ising models, a problem that arises in many applications where network changes can occur due to some external stimuli. We show that the sample complexity for detecting sparse changes, in a minimax sense, is no better than learning the entire model even in settings with local sparsity. This is a surprising fact in light of prior work rooted in sparse recovery methods, which suggest that sample complexity in this context scales only with the number of network changes. To shed light on when change detection is easier than structured learning, we consider testing of edge deletion in forest-structured graphs, and high-temperature ferromagnets as case studies. We show for these that testing of small changes is similarly hard, but testing of \emph{large} changes is well-separated from structure learning. These results imply that testing of graphical models may not be amenable to concepts such as restricted strong convexity leveraged for sparsity pattern recovery, and algorithm development instead should be directed towards detection of large changes. en_US dc.description.uri https://arxiv.org/abs/2011.03678 dc.language.iso en_US dc.relation.ispartof Advances in Neural Information Processing Systems dc.subject Information theory en_US dc.subject Ising models en_US dc.subject Statistics theory en_US dc.title Limits on testing structural changes in Ising models en_US dc.type Conference materials en_US pubs.elements-source manual-entry en_US pubs.organisational-group Boston University en_US pubs.organisational-group Boston University, College of Engineering en_US pubs.organisational-group Boston University, College of Engineering, Department of Electrical & Computer Engineering en_US dc.identifier.mycv 612683
﻿