Show simple item record

dc.contributor.authorGangrade, Adityaen_US
dc.contributor.authorNazer, Bobaken_US
dc.contributor.authorSaligrama, Venkateshen_US
dc.date.accessioned2021-11-29T20:58:27Z
dc.date.available2021-11-29T20:58:27Z
dc.date.issued2020
dc.identifier.citationA. 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.urihttps://hdl.handle.net/2144/43421
dc.description.abstractWe 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.urihttps://arxiv.org/abs/2011.03678
dc.language.isoen_US
dc.relation.ispartofAdvances in Neural Information Processing Systems
dc.subjectInformation theoryen_US
dc.subjectIsing modelsen_US
dc.subjectStatistics theoryen_US
dc.titleLimits on testing structural changes in Ising modelsen_US
dc.typeConference materialsen_US
pubs.elements-sourcemanual-entryen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Engineeringen_US
pubs.organisational-groupBoston University, College of Engineering, Department of Electrical & Computer Engineeringen_US
dc.identifier.mycv612683


This item appears in the following Collection(s)

Show simple item record