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.

在线学习方法在最小假设下产生顺序遗憾界限，并为统计学习提供期望风险界限；然而，最近的研究结果表明，在许多重要情况下，遗憾界限可能无法保证统计背景下紧致的高概率风险界限。本研究通过将通用在线学习算法应用于在线到批次转换，通过对定义遗憾的损失函数进行一般的二阶校正，获得了几个经典统计估计问题（如离散分布估计、线性回归、逻辑回归和条件密度估计）的几乎最优的高概率风险界限；我们的分析依赖于在线学习算法的不恰当性，因为它们不限制使用给定参考类别的预测器；我们的估计器的不恰当性使得在各种问题参数上显著改善了依赖；最后，我们讨论了我们的顺序算法与现有批处理算法之间的一些计算上的优势。

通过顺序预测器获得高概率风险边界