I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class Lemma, Covering Numbers, Chaining, Dudley's Theorem, Pseudodimension, Fat Shattering Dimension, Packing Numbers, Rademacher Composition, and possibly other results / tools that I'm not aware of.

Is there a website, survey, collection of articles, or, best of all, a book covering these topics?

Alternatively, I'm looking at examples of how to bound the Rademacher average for simple classes, in the same way that people use axis-aligned rectangles to show how to bound VC-dimension.

Thanks in advance.

up vote 7 down vote accepted

I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi. In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by Ashwinkumar, but (I believe?) originates in the probability book by Ledoux & Talagrand, which is not free), and applies these to standard classification methods (boosting and support vector machines are discussed, both due to their popularity, and since they are trained via ERM). This text dates from 2005, so it also has some of the other somewhat recent topics you mentioned, for instance Local Rademacher Complexities, and there's even a tiny plug to chaining. Lastly, while the manuscript is quite short, it has copious references which I believe you would find extremely useful.

Some of the other topics you mention are old enough to be in "A probabilistic Theory of Pattern Recognition" by Devroye, Györfi, and Lugosi (in particular, it has for more on packing than any other text I know). Although it lacks some of the newer topics you mention, this is a standard book that everyone I've met in learning theory has carried on their shelves. Maybe try to locate a table of contents and index for the book, and thumb through it.

Some of the other topics you mention I have not seen treated thoroughly in a book, but they have appeared in a number of course notes. For instance, if you go to Sham Kakade's page at UPenn, you will find links to two learning theory courses (one was at TTI-C, with Ambuj Tewari), and you will see the topic links match some of the things you have discussed, and have not appeared in my answers or elsewhere. There are plenty of good courses at various schools; Avrim Blum has excellent, extremely readable notes for his learning theory course (his analysis of winnow is the shortest, cleanest, and most intuitive I've ever seen!).

Some of these are maybe a little too new, though, and you'll have to go to the source material. But if you are really just trying to pick up a grab bag of techniques, I think the survey up top and the lectures to a couple learning theory classes will serve you a long way.

Also, you sound like you're looking for advanced texts, but I'd also like to plug two introductory texts which people enjoy very much. One is "an introduction to computational learning theory", by Kearns and (U.) Vazirani, which while old (for instance, boosting is presented only via Robert Schapire's original construction, and the emphasis is on PAC rather than agnostic learning), is presented well and has good intuition. Personally, I got my basics in Introduction to statistical learning theory, by the same authors as the above survey (but appearing in the order Bousquet, Boucheron, Lugosi?); it has nice exposition and was the first time that generalization theory really started to click for me.

This was a recently taught course. http://www.cs.huji.ac.il/~shais/Handouts.pdf. I haven't carefully read through it, but chapter 7 has material on Rademacher Complexities. Hope it helps.

  • Thank you @Ashwinkumar. I like the fact that some of these notes are from a book that is being currently written. – Matteo Nov 19 '11 at 4:43

The book by Cesa-Bianchi and Lugosi has much of the modern aspects of generalization bounds and learning theory.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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