High-Probability Risk Bounds via Sequential Predictors

Understand

Online learning methods yield sequential regret bounds under minimal assumptions and provide in-expectation risk bounds for statistical learning.

• However, despite the apparent advantage of online guarantees over their statistical counterparts, recent findings indicate that in many important cases, regret bounds may not guarantee tight high-probability risk bounds in the statistical setting.
• In this work we show that online to batch conversions applied to general online learning algorithms can bypass this limitation.
• Via a general second-order correction to the loss function defining the regret, we obtain nearly optimal high-probability risk bounds for several classical statistical estimation problems, such as discrete distribution estimation, linear regression, logistic regression, and conditional density estimation.