<p><em>Fast rates</em> generally refers to generalization bounds interpolating between the $1/n$ consistent rate and the $1/\sqrt n$ agnostic rate. I am aware of two basic approaches for obtaining these: (1) Talagrand's Bernstein-type inequality for empirical processes and (2) PAC-Bayesian bounds. Question: are there other methods? More to the point, is there a clean, user-friendly set of notes on this, suitable for (advanced) students?</p>

CC BY-SA 3.0
2014-07-22T18:38:08.230Z
I think I've resolved this to my satisfaction. The "relative deviations" (sec. 5.1) of "Theory of Classification: a Survey of Some Recent Advances: by Boucheron, Bousquet and Lugosi gives a very clean argument based on symmetrization.
Aryeh
CC BY-SA 3.0
2014-11-05T08:56:38.993Z
You can also find similar results from online learning perspective: http://ocobook.cs.princeton.edu/OCObook.pdf
Daniel
CC BY-SA 4.0
2022-04-01T12:26:16.270Z
Could you kindly explain why you call the $\sqrt{\frac{1}{n}}$ as the ``agnostic rate" and the ${\frac{1}{n}}$ as the consistent rate? Like, isnt the first one the natural rate that comes from Rademacher bounds? And Rademacher bounds are not agnostic - they are distribution dependent bounds. What am I missing?
Student
<machine-learning><lg.learning>
Fast rates -- cleanest proof
Aryeh
# Fast rates -- cleanest proof

(Asked by: username_0 on 2014-07-13)

*Fast rates* generally refers to generalization bounds interpolating between the $1/n$ consistent rate and the $1/\sqrt n$ agnostic rate. I am aware of two basic approaches for obtaining these: (1) Talagrand's Bernstein-type inequality for empirical processes and (2) PAC-Bayesian bounds. Question: are there other methods? More to the point, is there a clean, user-friendly set of notes on this, suitable for (advanced) students?

**Tags:** machine-learning, lg.learning

> **Comments:**
> **username_0**: I think I've resolved this to my satisfaction. The "relative deviations" (sec. 5.1) of "Theory of Classification: a Survey of Some Recent Advances: by Boucheron, Bousquet and Lugosi gives a very clean argument based on symmetrization.  
> **username_1**: You can also find similar results from online learning perspective: http://ocobook.cs.princeton.edu/OCObook.pdf  
> **username_2**: Could you kindly explain why you call the $\sqrt{\frac{1}{n}}$ as the ``agnostic rate" and the ${\frac{1}{n}}$ as the consistent rate? Like, isnt the first one the natural rate that comes from Rademacher bounds? And Rademacher bounds are not agnostic - they are distribution dependent bounds. What am I missing?  

---

## 0 answers

