Computational Learning Theory

Computational learning theory studies which concepts can be learned efficiently from examples, treating learning as a problem of computation and sample complexity.

Definition

Computational learning theory is the study of the resources, in data and computation, required to learn concepts from examples; in the probably approximately correct model a concept class is learnable if an algorithm can, from a polynomial number of samples and in polynomial time, output a hypothesis that is accurate with high probability.

Scope

This topic covers formal models of learnability: the probably approximately correct model that asks when a concept can be learned to high accuracy with high probability from polynomially many examples and computation, the mistake-bound and online-learning models, weak versus strong learnability and boosting, and connections to computational complexity. It addresses both the statistical and the algorithmic feasibility of learning.

Core questions

• Which concept classes can be learned efficiently from examples?
• How much data and computation does learning a concept require?
• What is the relationship between weak and strong learnability?
• How does learnability connect to computational complexity?

Key theories

Probably approximately correct learning

Valiant's model defines a concept class as learnable when an efficient algorithm can produce, with high probability, a hypothesis of low error from polynomially many examples, making learnability a precise computational question.

Weak learnability and boosting

A central result shows that any class learnable slightly better than chance is also strongly learnable, which led directly to boosting algorithms that amplify weak learners into accurate ones.

Statistical and computational limits

Learnability is bounded both by sample complexity, tied to capacity measures, and by computational hardness, so some classes are statistically learnable yet computationally intractable.

Clinical relevance

Computational learning theory gives the formal foundation for what learning algorithms can and cannot achieve and directly inspired practical methods, most notably boosting, which arose from the question of whether weak learners could be combined into strong ones; it frames learning as a rigorous computational discipline.

History

Valiant introduced the probably approximately correct model in 1984, giving learning a precise computational definition and founding the field. Subsequent work established sample-complexity characterizations, the equivalence of weak and strong learnability that motivated boosting, and hardness results showing the computational limits of learning.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

What does probably approximately correct mean?

It means that, with high probability over the random sample, the learner outputs a hypothesis that is approximately correct, that is, has small error on future data. Learnability requires achieving this from a number of examples and an amount of computation that grow only polynomially.

How did learning theory lead to boosting?

Researchers asked whether a learner only slightly better than random guessing could be turned into a highly accurate one. The proof that weak and strong learnability are equivalent was constructive, and that construction became the boosting algorithms used widely in practice.