2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Jul 22, 2014 at 18:38
  • $\begingroup$ You can also find similar results from online learning perspective: ocobook.cs.princeton.edu/OCObook.pdf $\endgroup$
    – Daniel
    Nov 5, 2014 at 8:56
  • $\begingroup$ 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? $\endgroup$
    – Student
    Apr 1, 2022 at 12:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.