Machine Learning

Computational Learning Theory

We investigate theoretical properties of learning problems.

Computational learning theory analyses complexity of learning.
Ana Ozaki

Computational learning theory studies theoretical aspects of machine learning.

  • How can we formally define learnability?
  • What is the complexity of learning?
  • Which formal guarantees can be given to the outcome of a learning process?
  • Can we reduce one learning problem to another?

These are some of the basic but also fundamental questions in the quest for a clear and solid understanding of whether and how machines can learn. We are interested in carefully defining the conditions of learning problems so that theoretical questions involving learnability, complexity, and reducibility can be formally investigated and understood.