Is there any work combining machine learning and the more exotic forms of complexity theory? It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for effectively analyzing data. Is there any survey of work doing this?
There is some inherent difference or dissimilarity of approaches between the two fields of applied machine learning and TCS/complexity theory.

Here is a recent workshop on the subject at the Center for Computational Intractability, Princeton with lots of videos.


  Description: Many current approaches in machine learning are heuristic: we cannot prove good bounds on either their performance or their running time. This small workshop will focus on the project of designing algorithms and approaches whose performance can be analyzed rigorously. The goal is to look beyond settings where provable bounds already exist.



Workshop: Provable Bounds in Machine Learning — August 1-2, 2012


In TCS a main area of study of "learning" sometimes maybe confusingly even also called "machine learning" is called PAC theory which stands for Probably Approximately Correct. its early 1980s origin predates much more modern research into "machine learning." wikipedia calls it part of the field computational learning theory. PAC often concerns results of learning boolean formulas given statistical samples of the distributions etc and the achievable accuracy of learning given various algorithms or limited samples.  This is studied in a rigorous theoretical way with tie-ins to complexity classes.  But it is not so much an applied study &amp; wikipedias page on machine learning does not even list it.


The Computational Complexity
of Machine Learning PhD thesis by Kearns
Xing slides on (PAC) machine learning