Online Learning with Predictable Sequences
Online Learning with Predictable Sequences
复制标题
DOI：
--
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
A. Rakhlin;Karthik Sridharan
中科院分区：
文献类型：
--
作者：
A. Rakhlin;Karthik Sridharan
我们提出了在线线性优化的方法，利用良性（而不是最坏情况下）的序列。特别地，如果学习器遇到的序列被一个已知的“可预测过程”很好地描述，则与典型的最坏情况界限相比，所提出的算法享有更紧的界限。此外，如果序列不是良性的，该方法实现了通常的最坏情况下的遗憾界限。我们的方法可以被看作是一种在在线学习的范例中添加有关序列的先验知识的方法。该设置被示出为包含部分和边信息。方差和路径长度边界[11，9]可以被视为具有简单可预测序列的在线学习的特定示例。我们进一步扩展了我们的方法和结果，包括与一组可能的可预测过程（模型）竞争，也就是“学习”可预测过程本身，同时使用它来获得更好的后悔保证。我们表明，这样的模型选择是可能的，在各种假设下的可用反馈。我们的研究结果表明了一个有前途的方向，进一步的研究与潜在的应用，股票市场和时间序列预测。
We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specically if the sequence encountered by the learner is described well by a known \predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Additionally, the methods achieve the usual worst-case regret bounds if the sequence is not benign. Our approach can be seen as a way of adding prior knowledge about the sequence within the paradigm of online learning. The setting is shown to encompass partial and side information. Variance and path-length bounds [11, 9] can be seen as particular examples of online learning with simple predictable sequences. We further extend our methods and results to include competing with a set of possible predictable processes (models), that is \learning" the predictable process itself concurrently with using it to obtain better regret guarantees. We show that such model selection is possible under various assumptions on the available feedback. Our results suggest a promising direction of further research with potential applications to stock market and time series prediction.