Efficient learning algorithms for changing environments
Efficient learning algorithms for changing environments
复制标题
DOI：
10.1145/1553374.1553425
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Elad Hazan;Seshadhri Comandur
中科院分区：
文献类型：
--
作者：
Elad Hazan;Seshadhri Comandur
我们在不断变化的环境中研究在线学习。遗憾的标准度量界定了在线学习者的成本与事后最佳决定之间的差异。因此，遗憾的是，最大程度地减少算法倾向于融合到静态的最佳最佳，显然是在不断变化的环境中的次优行为。另一方面，提出的各种指标旨在加强后悔并允许更多动态算法产生效率低下的算法。我们提出了一个不同的性能指标，该指标加强了遗憾的标准指标，并相对于不断变化的比较器来衡量性能。然后，我们描述了一系列基于数据流的减排，这些减少将算法转化为最小化（标准）遗憾（尽管仅产生多层计算开销），但将遗憾（标准）遗憾转化为自适应算法。使用此减少，我们为在线凸优化的问题获得有效的低自适应regret算法。这可以应用于各种学习方案，即在线投资组合选择，为此我们描述了显示适应性优势的实验结果。
We study online learning in an oblivious changing environment. The standard measure of regret bounds the difference between the cost of the online learner and the best decision in hindsight. Hence, regret minimizing algorithms tend to converge to the static best optimum, clearly a suboptimal behavior in changing environments. On the other hand, various metrics proposed to strengthen regret and allow for more dynamic algorithms produce inefficient algorithms. We propose a different performance metric which strengthens the standard metric of regret and measures performance with respect to a changing comparator. We then describe a series of data-streaming-based reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead. Using this reduction, we obtain efficient low adaptive-regret algorithms for the problem of online convex optimization. This can be applied to various learning scenarios, i.e. online portfolio selection, for which we describe experimental results showing the advantage of adaptivity.