We prove that finding an optimal subset selection strategy is NP-hard even for a restricted class of Gaussian Processes, called Gaussian Free Fields (GFF). We give a dynamic programming algorithm for Gaussian Processes on bounded tree-width graphs, which yields a fully polynomial time approximation scheme for the case of GFFs on such graphs. For general Gaussian Processes on bounded tree-width graphs, our algorithm’s running time depends polynomially on the condition number of the covariance matrix. We also give a greedy constant-factor approximation algorithm for GFFs on arbitrary graphs.
We consider both adaptive and non-adaptive subset selection for Ising Models. For the simple 1-dimensional ferromagnetic Ising Model, we demonstrate that adaptive strategies outperform non-adaptive strategies, and give a simple adaptive strategy whose error is at most a constant times that of the optimal adaptive strategy for the same observation budget. We prove that it is NP-hard to compute an optimal non-adaptive strategy for ferromagnetic Ising Models on general graphs.
For Mixture Models, we define a “maximum-a-posteriori” oracle and discuss how it differs from other oracle models. Then we demonstrate the advantage provided by this oracle by giving an algorithm which estimates the parameters of a mixture of high-dimensional spherical Gaussians under a weaker separation condition and more efficiently than known unsupervised algorithms.