Lower Bounds for Two-Sample Structural Change Detection in Ising and Gaussian Models
This work addresses the fundamental limits of change detection in graphical models, which is incremental as it builds on prior structure learning results to show optimality in certain regimes.
The paper tackles the problem of detecting structural changes between two Markov random fields, specifically Ising and Gaussian models, by establishing information-theoretic lower bounds on sample sizes required for reliable detection. It shows that for Ising models, Ω(d²/(log d)² log p) samples per dataset are needed, and for Gaussian models, Ω(γ⁻² log p) samples per dataset are required, closely matching existing structure learning bounds.
The change detection problem is to determine if the Markov network structures of two Markov random fields differ from one another given two sets of samples drawn from the respective underlying distributions. We study the trade-off between the sample sizes and the reliability of change detection, measured as a minimax risk, for the important cases of the Ising models and the Gaussian Markov random fields restricted to the models which have network structures with $p$ nodes and degree at most $d$, and obtain information-theoretic lower bounds for reliable change detection over these models. We show that for the Ising model, $Ω\left(\frac{d^2}{(\log d)^2}\log p\right)$ samples are required from each dataset to detect even the sparsest possible changes, and that for the Gaussian, $Ω\left( γ^{-2} \log(p)\right)$ samples are required from each dataset to detect change, where $γ$ is the smallest ratio of off-diagonal to diagonal terms in the precision matrices of the distributions. These bounds are compared to the corresponding results in structure learning, and closely match them under mild conditions on the model parameters. Thus, our change detection bounds inherit partial tightness from the structure learning schemes in previous literature, demonstrating that in certain parameter regimes, the naive structure learning based approach to change detection is minimax optimal up to constant factors.