Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I have a good broad grasp of the field as a whole.

Is there a standard text, surveys, or lecture notes for introducing CoLT at the graduate level?

I have a basic Theory A background, but no specific knowledge of Machine Learning or Statistics. I am mostly interested in things like PAC-learning and learning automata, and less interested in things like Bayesian inference and VC theory.

Related questions


2 Answers 2


For some material more recent than Kearns and Vazirani, you could check out Rocco Servedio's lecture notes for Advanced Topics in Computational Learning Theory, or the notes from Sasha Rakhlin's class.

  • $\begingroup$ The first option looks great, are Rakhlin's notes accessible to someone without a statistics background? $\endgroup$ Jul 8, 2012 at 2:06
  • $\begingroup$ Yes, they should be. $\endgroup$
    – Aaron Roth
    Jul 8, 2012 at 11:50

Kearns and Vazirani is maybe a bit old, but good introduction.

  • 2
    $\begingroup$ thanks! Is there a good survey of post-1994 results to compliment this book? $\endgroup$ Jul 8, 2012 at 1:12

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.