Lower Bounds on Active Learning for Graphical Model Selection
  We consider the problem of estimating the underlying graph associated with a
Markov random field, with the added twist that the decoding algorithm can
iteratively choose which subsets of nodes to sample based on the previous
samples, resulting in an active learning setting. Considering both Ising and
Gaussian models, we provide algorithm-independent lower bounds for
high-probability recovery within the class of degree-bounded graphs. Our main
results are minimax lower bounds for the active setting that match the best
known lower bounds for the passive setting, which in turn are known to be tight
in several cases of interest. Our analysis is based on Fano's inequality, along
with novel mutual information bounds for the active learning setting, and the
application of restricted graph ensembles. While we consider ensembles that are
similar or identical to those used in the passive setting, we require different
analysis techniques, with a key challenge being bounding a mutual information
quantity associated with observed subsets of nodes, as opposed to full
observations.
