Part of Advances in Neural Information Processing Systems 23 (NIPS 2010)

*Nathan Srebro, Karthik Sridharan, Ambuj Tewari*

<p>We establish an excess risk bound of O(H R<em>n^2 + sqrt{H L*} R</em>n) for ERM with an H-smooth loss function and a hypothesis class with Rademacher complexity R<em>n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R</em>n = sqrt{R/n}, this translates to a learning rate of ̃ O(RH/n) in the separable (L* = 0) case and O(RH/n + sqrt{L* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective.</p>

Do not remove: This comment is monitored to verify that the site is working properly