<p>There is some inherent difference or dissimilarity of approaches between the two fields of applied machine learning and TCS/complexity theory.</p>

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

<blockquote>
  <p>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.</p>
</blockquote>

<ul>
<li><a href="http://intractability.princeton.edu/blog/2012/07/workshop-on-provable-bounds-in-machine-learning-august-1-2-2012/" rel="nofollow">Workshop: Provable Bounds in Machine Learning — August 1-2, 2012</a></li>
</ul>

<p>In TCS a main area of study of "learning" sometimes maybe confusingly even also called "machine learning" is called <a href="http://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="nofollow">PAC theory</a> 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 <a href="http://en.wikipedia.org/wiki/Computational_learning_theory" rel="nofollow">computational learning theory</a>. 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 <a href="http://en.wikipedia.org/wiki/Machine_learning" rel="nofollow">machine learning</a> does not even list it.</p>

<ul>
<li><p><a href="http://www.cis.upenn.edu/~mkearns/papers/thesis.pdf" rel="nofollow">The Computational Complexity
of Machine Learning</a> PhD thesis by Kearns</p></li>
<li><p><a href="http://www.cs.cmu.edu/~epxing/Class/10701-08s/Lecture/lecture11-annotated.pdf" rel="nofollow">Xing slides on (PAC) machine learning</a></p></li>
</ul>

CC BY-SA 3.0
2012-10-05T19:09:05.027Z
"wikipedia calls"... do you actually know anything about the subject? 1) the wiki for machine learning has a section Theory which links to the computational learning theory page 2) the learning theory work of Valiant, Vapnik, Schapire, among others, has had a huge impact on the practice of machine learning.
Sasho Nikolov
CC BY-SA 3.0
2012-10-04T16:15:41.197Z
2012-10-05T16:49:06.117Z
2012-10-05T16:49:06.117Z
vzn
<p>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?</p>

CC BY-SA 3.0
2012-10-03T18:57:38.787Z
No survey that I know of, but check out this pointer to "quantum learning" (#5) from this post: http://blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Suresh Venkat
CC BY-SA 3.0
2012-10-04T15:05:49.837Z
machine learning regularly attacks very hard problems that are prob outside of NP for "global" optimization but inside NP or less hard than that for "local" optimization. so the whole concept of complexity class gets blurry when one is optimizing for "good enough" results which are measured more by application-dependent quality measurements & in a sense arent really known apriori to running the algorithm(s)....
vzn
CC BY-SA 3.0
2012-10-04T15:28:26.513Z
@vzn To me, that subtlety seems like all the more reason to pay attention to complexity!  It might provide some very interesting insights.
Mike Izbicki
CC BY-SA 3.0
2012-10-04T16:35:20.017Z
there certainly are connections between learning theory, circuit complexity, cryptography. but this is the corner of learning theory that's a bit removed from machine learning practice. if you are interested, i can come up with some pointers
Sasho Nikolov
CC BY-SA 3.0
2012-10-04T17:44:00.417Z
yes, another example, BDDs (binary decision diagrams) have been used in database algorithms/data mining & have strong connections to circuit complexity. but it seems to me the whole question may be a bit of a tricky premise because much machine learning is pragmatic & complexity of applied ML is often studied indirectly/empirically through analyzing _real implementations of algorithms_ rather than attempting to theoretically anticipate or strictly classify it.
vzn
<cc.complexity-theory><reference-request><machine-learning>
Is there any work combining machine learning and the more exotic forms of complexity theory?
Mike Izbicki
# Is there any work combining machine learning and the more exotic forms of complexity theory?

(Asked by: username_0 on 2012-10-03)

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?

**Tags:** cc.complexity-theory, reference-request, machine-learning

> **Comments:**
> **username_1**: No survey that I know of, but check out this pointer to "quantum learning" (#5) from this post: http://blog.computationalcomplexity.org/2012/10/quantum-workshop.html  
> **username_2**: machine learning regularly attacks very hard problems that are prob outside of NP for "global" optimization but inside NP or less hard than that for "local" optimization. so the whole concept of complexity class gets blurry when one is optimizing for "good enough" results which are measured more by application-dependent quality measurements & in a sense arent really known apriori to running the algorithm(s)....  
> **username_0**: @username_2 To me, that subtlety seems like all the more reason to pay attention to complexity!  It might provide some very interesting insights.  
> **username_3**: there certainly are connections between learning theory, circuit complexity, cryptography. but this is the corner of learning theory that's a bit removed from machine learning practice. if you are interested, i can come up with some pointers  
> **username_2**: yes, another example, BDDs (binary decision diagrams) have been used in database algorithms/data mining & have strong connections to circuit complexity. but it seems to me the whole question may be a bit of a tricky premise because much machine learning is pragmatic & complexity of applied ML is often studied indirectly/empirically through analyzing _real implementations of algorithms_ rather than attempting to theoretically anticipate or strictly classify it.  

---

## 1 answers

### Answer by username_2 on 2012-10-04. Score: 3 | Accepted answer

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](http://intractability.princeton.edu/blog/2012/07/workshop-on-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](http://en.wikipedia.org/wiki/Probably_approximately_correct_learning) 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](http://en.wikipedia.org/wiki/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 & wikipedias page on [machine learning](http://en.wikipedia.org/wiki/Machine_learning) does not even list it.

* [The Computational Complexity
  of Machine Learning](http://www.cis.upenn.edu/~mkearns/papers/thesis.pdf) PhD thesis by Kearns
* [Xing slides on (PAC) machine learning](http://www.cs.cmu.edu/~epxing/Class/10701-08s/Lecture/lecture11-annotated.pdf)

> **Comments:**
> **username_3**: "wikipedia calls"... do you actually know anything about the subject? 1) the wiki for machine learning has a section Theory which links to the computational learning theory page 2) the learning theory work of Valiant, Vapnik, Schapire, among others, has had a huge impact on the practice of machine learning.  

---

