Introduction

Can we identify easy-difficult classes of learning problems? regardless of learning algorithm?
Can we determine the number of training examples needed to (probably) learn a concept?
Does it matter the order in which examples are presented? How?
How well can we learn this concept?
Computational Learning Theory addresses these questions.
We will address the
- Sample complexity
- Computational complexity
- Mistake bound