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?
$\begingroup$
$\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$– AryehJul 22, 2014 at 18:38
-
$\begingroup$ You can also find similar results from online learning perspective: ocobook.cs.princeton.edu/OCObook.pdf $\endgroup$– DanielNov 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$– StudentApr 1, 2022 at 12:26
Add a comment
|