论文标题
测试Ising模型中结构变化的限制
Limits on Testing Structural Changes in Ising Models
论文作者
论文摘要
我们提出了有关检测Ising模型稀疏变化的新型信息理论限制，这是在许多应用程序中由于某些外部刺激而发生网络变化的问题。我们表明，从最小值意义上讲，用于检测稀疏变化的样本复杂性即使在具有局部稀疏性的设置中学习整个模型也没有比学习整个模型更好。鉴于植根于稀疏恢复方法的先前工作，这是一个令人惊讶的事实，这表明在这种情况下，样本复杂性仅随着网络变化的数量而定。为了阐明何时比结构化学习更容易，我们考虑在森林结构图中测试边缘缺失，而高温铁磁体作为案例研究。我们为这些表明，对小变化的测试同样困难，但是\ emph {大}变化的测试与结构学习完全分离。这些结果表明，对图形模型的测试可能不适合诸如限制的强凸度以用于稀疏模式恢复之类的概念，而算法开发则应用于检测大型变化。
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.
