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


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$ – Artem Kaznatcheev Jul 8 '12 at 2:06
  • $\begingroup$ Yes, they should be. $\endgroup$ – Aaron Roth Jul 8 '12 at 11:50

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.