平滑损失学习的乐观速率

Sep, 2010

Smoothness, Low-Noise and Fast Rates

Nathan Srebro, Karthik Sridharan, Ambuj Tewari

TL;DR本文针对H-smooth损失函数和具有Rademacher复杂度R_n的假设类的经验风险最小化，建立了O（HR_n^2 + R_n sqrt {HL*}）的过量风险界，其中L *是假设类可实现的最佳风险。针对典型的假设类，其中R_n = sqrt（R / n），在可分离（L * = 0）情况下，这相当于O（RH / n）的学习率，更普遍的情况下为O（RH / n + sqrt {L * RH / n}）。我们还针对具有平滑非负目标的在线和随机凸优化提供类似的保证。

Abstract

We establish am excess risk bound of order $H \Rad_n^2 + \sqrt{H L^*}\Rad_n$ for ERM with an H-smooth loss function and a hypothesis class with rademacher complexity $\Rad_n$, where $L^*$ is the best risk achieva