Optimistic Rates for Learning with a Smooth Loss

We establish an excess risk bound of O(HR2n + √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 O(RH/n) in the separable (L* = 0) case and O(RH/n + √L*RH/n) more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective.