Smoothness, Low Noise and Fast Rates
Nathan Srebro, Karthik Sridharan, Ambuj Tewari · arXiv (Cornell University) · 2010
We establish an excess risk bound of Õ HR 2 n + √ HL∗Rn for ERM with an H-smooth loss function and a hypothesis class with Rademacher complexity Rn, where L ∗ is the best risk achievable by the hypothesis class. For typical hypothesis classes where Rn = √ R/n, this translates to a learning rate of Õ (RH/n) in the separable (L ∗ = 0) case and Õ RH/n + √ L ∗) RH/n more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective. 1