What relations and differences are between statistical learning theory and computational learning theory?

Are they about the same topic? Solve the same problems, and use the same methods?

For example, the former says it is the theory of prediction (regression, classification,...).

  • $\begingroup$ This is actually a great question. I was keen on asking a similar one but I thought this entails the same properties of the question I wanted to ask. I've seen lots of books, lots of google searches, and wikipedia pages. I think both questions are related in terms of phrasing them as sample complexity questions but I've been unable to find any resources to indicate work done in this domain prior to PAC. All books I've seen start from PAC which lead me to wonder what happened prior to PAC. $\endgroup$
    – Kirk Walla
    Mar 4 '20 at 17:00
  • $\begingroup$ The way I see it, it's all about the first word in each of the terms. CLT adopts a computational point of view, trying to derive facts about a learning problem, whereas SLT adopts a statistical point of view, applying statistics to answer questions about the application of a particular algorithm to a problem. $\endgroup$
    – David Cian
    Jan 16 at 11:36

Computational learning, more concretely the probably approximately correct (PAC) framework, answers questions like: how many training examples are needed for a learner to learn with high probability a good hypothesis? how much computational effort do I need to learn with high probability such hypothesis? It does not deal with the concrete classifier you are working with. It is about what you can and cannot learn with some samples at hand.

In statistical learning theory you rather answer questions of the sort: how many training samples will the classifier misclassify before it has converged to a good hypothesis? i.e. how hard is it to train a classifier, and what warranties do I have on its performance?

Regretfully I do not know a source where these two areas are described/compared in an unified manner. Still, though not much hope that helps


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.