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?