Achieving All with No Parameters: AdaNormalHedge
Achieving All with No Parameters: AdaNormalHedge
复制标题
无需参数即可实现所有目标：AdaNormalHedge
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Schapire
中科院分区：
文献类型：
--
作者：
Haipeng Luo;R. Schapire
我们研究了经典的在线学习问题的预测与专家的意见，并提出了一个真正的无参数和自适应算法，同时实现多个目标，而不使用任何先验信息。这项工作的主要组成部分是NormalHedge.DT算法的改进版本（Luo和Schapire，2014），称为AdaNormalHedge。该算法一方面保证了在竞争对手损失较小时的小后悔，另一方面保证了在随机损失时的几乎恒定的后悔。另一方面，该算法能够同时与专家的任何凸组合进行竞争，但在先验和竞争者的相对熵方面存在遗憾。这解决了Chaudhuri et al.（2009）和Bauzov and Vovk（2010）提出的一个未决问题。此外，我们将结果扩展到睡眠专家设置，并提供两个应用程序来说明AdaNormalHedge的强大功能：1）与时变未知竞争对手竞争，2）几乎可以预测最佳修剪树。我们在这些应用上的结果从不同方面显著改进了以前的工作，第一个应用的特殊情况解决了Warranty和Koolen（2014）提出的另一个开放问题，即是否可以同时实现对抗性和随机损失的最佳转移后悔。
We study the classic online learning problem of predicting with expert advice, and propose a truly parameter-free and adaptive algorithm that achieves several objectives simultaneously without using any prior information. The main component of this work is an improved version of the NormalHedge.DT algorithm (Luo and Schapire, 2014), called AdaNormalHedge. On one hand, this new algorithm ensures small regret when the competitor has small loss and almost constant regret when the losses are stochastic. On the other hand, the algorithm is able to compete with any convex combination of the experts simultaneously, with a regret in terms of the relative entropy of the prior and the competitor. This resolves an open problem proposed by Chaudhuri et al. (2009) and Chernov and Vovk (2010). Moreover, we extend the results to the sleeping expert setting and provide two applications to illustrate the power of AdaNormalHedge: 1) competing with time-varying unknown competitors and 2) predicting almost as well as the best pruning tree. Our results on these applications significantly improve previous work from different aspects, and a special case of the first application resolves another open problem proposed by Warmuth and Koolen (2014) on whether one can simultaneously achieve optimal shifting regret for both adversarial and stochastic losses.
影响因子：
5.2
作者：
van der Meer JW
通讯作者：
van der Meer JW