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$ 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 '14 at 18:38
  • $\begingroup$ You can also find similar results from online learning perspective: ocobook.cs.princeton.edu/OCObook.pdf $\endgroup$ – Daniel Nov 5 '14 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.