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,...).

  • 1
    $\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, 2020 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, 2021 at 11:36

2 Answers 2


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


Supplementing the answer by @jpmuc, the distinction between computational and statistical learning seems to be a historical accident, and the theories are slowly merging (and sometimes being taught) as a single unified 'learning theory'. Computational and statistical learning theory are increasingly used as synonyms.

The main idea to come out of computational learning theory thus far is PAC learning, whose formulations often make use of the main contribution of statistical learning theory, the VC dimension.

For more detail and references: https://machinelearningmastery.com/introduction-to-computational-learning-theory/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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