High-Probability Risk Bounds via Sequential Predictors
Dirk van der Hoeven Nikita Zhivotovskiy Nicolò Cesa-Bianchi
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. Our
analysis relies on the fact that many online learning algorithms are improper,
as they are not restricted to use predictors from a given reference class. The
improper nature of our estimators enables significant improvements in the
dependencies on various problem parameters. Finally, we discuss some
computational advantages of our sequential algorithms over their existing batch
counterparts.