Title: Lower Bounds for Two-Sample Structural Change Detection in Ising and Gaussian Models,
Abstract: 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, $\Omega\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, $\Omega\left( \gamma^{-2} \log(p)\right)$ samples are
required from each dataset to detect change, where $\gamma$ 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.