Computational Learning Theory

Sample Complexity

  1. The learner proposes instances, as queries to teacher: Learner proposes instance $x$, teacher provides $c(x)$.
  2. The teacher (who knows $c$) provides training examples teacher provides sequence of examples of form $\langle x, c(x) \rangle$.
  3. There is some random process that proposes the instances. $x$ is generated randomly, teacher provides $c(x)$.

José M. Vidal .

4 of 26