Does MCMC belong to the statistical query model?

Question

It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, gaussian discriminant analysis, EM, and backpropagation for neural networks. (See, e.g., http://papers.nips.cc/paper/3150-map-reduce-for-machine-learning-on-multicore.pdf for proofs.)

According to Feldman et al. (http://arxiv.org/pdf/1201.1214v5.pdf), it seems that MCMC also belongs to the SQ model. However, I didn't find any concrete proofs for this simple fact in existing literature. So, does MCMC directly falls into the SQ model? Or it requires modifications to fit in?

Answer 1

Let me first clarify what the paper states: "Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an [meaning SQ] oracle". So the question is not really whether MCMC "falls into the SQ framework" (the framework does not place any restrictions on computation) but whether the access to data samples that is necessary to run the algorithm can be replaced with access to an SQ oracle without invalidating the guarantees provided by the algorithm. One can also show that an algorithm for which we have no guarantees is an SQ algorithm but that requires an implementation using an "unbiased" oracle (referred to as 1-STAT in the paper). Lower bounds that can be proved against such an oracle are weaker.

Now regarding MCMC with SQs: the main way to apply MCMC to these kinds of problems that we had in mind in described in an example at the bottom of page 4. Please also take a look at the proof of Thm. 9 here in a follow up paper on this type of techniques: http://arxiv.org/pdf/1311.4821v5.pdf