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

CC BY-SA 3.0
2011-11-19T04:43:42.103Z
Thank you @Ashwinkumar. I like the fact that some of these notes are from a book that is being currently written.
Matteo
CC BY-SA 3.0
2011-11-19T03:40:33.707Z
2011-11-19T03:40:33.707Z
Ashwinkumar B V
<p>The book by <a href="http://rads.stackoverflow.com/amzn/click/0521841089" rel="nofollow">Cesa-Bianchi and Lugosi</a> has much of the modern aspects of generalization bounds and learning theory. </p>

CC BY-SA 3.0
2011-11-19T04:22:40.757Z
2011-11-19T04:22:40.757Z
Suresh Venkat
<p>I believe you would enjoy <a href="http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf">Theory of Classification: A Survey of Recent Advances</a> 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&amp;Shai's notes referenced in the answer by Ashwinkumar, but (I believe?) originates in the probability book by Ledoux &amp; 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.</p>

<p>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.</p>

<p>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 <a href="http://www-stat.wharton.upenn.edu/~skakade/">Sham Kakade's page at UPenn</a>, 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!).</p>

<p>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.</p>

<p>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 <a href="http://www.econ.upf.edu/~lugosi/mlss_slt.pdf">Introduction to statistical learning theory</a>, 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.</p>

CC BY-SA 4.0
2020-12-05T15:30:13.610Z
Do you have any updated suggestions for references? The first article you posted seems great, but I am wondering if there has been a revision in the past decade or so.
user27182
CC BY-SA 3.0
2011-11-19T07:19:34.547Z
2011-11-19T08:16:10.837Z
2011-11-19T08:16:10.837Z
matus
<p>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.</p>

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

<p>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.</p>

<p>Thanks in advance.</p>

<reference-request><machine-learning><lg.learning><books><vc-dimension>
Resource / book for recent advances in statistical learning theory
Matteo
# Resource / book for recent advances in statistical learning theory

(Asked by: username_0 on 2011-11-19)

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.

**Tags:** reference-request, machine-learning, lg.learning, books, vc-dimension

---

## 3 answers

### Answer by username_3 on 2011-11-19. Score: 8 | Accepted answer

I believe you would enjoy [Theory of Classification: A Survey of Recent Advances](http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf) 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](http://www-stat.wharton.upenn.edu/~skakade/), 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](http://www.econ.upf.edu/~lugosi/mlss_slt.pdf), 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.

> **Comments:**
> **username_4**: Do you have any updated suggestions for references? The first article you posted seems great, but I am wondering if there has been a revision in the past decade or so.  

---

### Answer by username_1 on 2011-11-19. Score: 5

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.

> **Comments:**
> **username_0**: Thank you @Ashwinkumar. I like the fact that some of these notes are from a book that is being currently written.  

---

### Answer by username_2 on 2011-11-19. Score: 3

The book by [Cesa-Bianchi and Lugosi](http://rads.stackoverflow.com/amzn/click/0521841089) has much of the modern aspects of generalization bounds and learning theory.


---

