The Interplay Between Stability and Regret in Online Learning
The Interplay Between Stability and Regret in Online Learning
复制标题
在线学习中的稳定性和遗憾之间的相互作用
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Ambuj Tewari
中科院分区：
文献类型：
--
作者：
Ankan Saha;Prateek Jain;Ambuj Tewari
本文考虑了在线学习算法的稳定性及其对可学习性（有界遗憾）的影响。我们引入了一个新的量，称为{em forward regret}，它直观地衡量了在线学习算法在允许一步向前看未来的情况下有多好。我们表明，给定的稳定性，有界向前后悔是等价的有界后悔。我们还证明了有界遗憾算法的存在性意味着有界遗憾和有界前向遗憾的稳定算法的存在性。等价结果适用于一般的，可能是非凸的问题。据我们所知，我们的分析提供了第一个一般性的稳定性和遗憾之间的连接，在网上设置，不限于特定类别的算法。我们的稳定性-后悔关系为分析任何在线学习算法所引发的后悔提供了一个简单的方法。使用我们的框架，我们分析了几个现有的在线学习算法，以及“近似”版本的算法，如RDA，在每次迭代中解决一个优化问题。我们的证明比现有的分析各自的算法简单，表现出明确的稳定性和前向遗憾之间的权衡，并提供更严格的遗憾界在某些情况下。此外，使用我们的配方，我们分析了几种算法的“近似”版本，例如在每一步都需要解决一个优化问题的跟随正则化领导者（FTRL）。
This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given stability, bounded forward regret is equivalent to bounded regret. We also show that the existence of an algorithm with bounded regret implies the existence of a stable algorithm with bounded regret and bounded forward regret. The equivalence results apply to general, possibly non-convex problems. To the best of our knowledge, our analysis provides the first general connection between stability and regret in the online setting that is not restricted to a particular class of algorithms. Our stability-regret connection provides a simple recipe for analyzing regret incurred by any online learning algorithm. Using our framework, we analyze several existing online learning algorithms as well as the "approximate" versions of algorithms like RDA that solve an optimization problem at each iteration. Our proofs are simpler than existing analysis for the respective algorithms, show a clear trade-off between stability and forward regret, and provide tighter regret bounds in some cases. Furthermore, using our recipe, we analyze "approximate" versions of several algorithms such as follow-the-regularized-leader (FTRL) that requires solving an optimization problem at each step.