We present methods for online linear optimization that take advantage of
benign (as opposed to worst-case) sequences. Specifically 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 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.

本文提出了一种基于可预测过程的在线线性优化算法，该算法利用了良性序列的先验知识来提高性能，并扩展到模型选择和时间序列预测领域，具有较好的应用潜力。

可预测序列的在线学习

Online Learning with Predictable Sequences

Time series prediction covers a vast field of every-day statistical
applications in medical, environmental and economic domains. In this paper we
develop nonparametric prediction strategies based on the combination of a set
of 'experts' and show the universal consistency of these strategies under a
minimum of conditions. We perform an in-depth analysis of real-world data sets
and show that these nonparametric strategies are more flexible, faster and
generally outperform ARMA methods in terms of normalized cumulative prediction
error.

本文基于一组‘专家’结合提出了非参数化的预测策略，并在最少条件下展示了这些策略的普适一致性。通过对真实数据集的深入分析表明，这些非参数化策略比 ARMA 方法更具灵活性，更快速，并且在归一化累积预测误差方面总体表现更好。