The computational power of optimization in online learning
The computational power of optimization in online learning
复制标题
在线学习中优化的计算能力
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tomer Koren
中科院分区：
文献类型：
--
作者：
Elad Hazan;Tomer Koren
我们考虑了专家“优化”的基本预测问题：有一个黑盒优化的Oracle可以在不断的时间内回顾一下，在此期间，它可以在不断的时间内进行回顾设置，我们给出了一种新颖的在线算法，该算法在总计O（√n）计算时间的N型专家方面消失了。 Oracle模型，因此与标准的无甲骨文设置相比，表现出二次加速度，其中所需的消失遗憾时间为θ（n）。统计学习：在后者中，优化的甲骨文 - 即有效的经验风险最小化器，可以学习有限的假设n的尺寸n（logn）。在重复的零和游戏中学习，在玩家可以在不变的时间内访问其对选项的任何混合策略的最佳响应的环境。在此设置中的游戏为θ（√n），在无甲骨文的设置上再次产生二次改进，其中已知θ（n）很紧。
We consider the fundamental problem of prediction with expert advice where the experts are “optimizable”: there is a black-box optimization oracle that can be used to compute, in constant time, the leading expert in retrospect at any point in time. In this setting, we give a novel online algorithm that attains vanishing regret with respect to N experts in total O(√N) computation time. We also give a lower bound showing that this running time cannot be improved (up to log factors) in the oracle model, thereby exhibiting a quadratic speedup as compared to the standard, oracle-free setting where the required time for vanishing regret is Θ(N). These results demonstrate an exponential gap between the power of optimization in online learning and its power in statistical learning: in the latter, an optimization oracle—i.e., an efficient empirical risk minimizer—allows to learn a finite hypothesis class of size N in time O(logN). We also study the implications of our results to learning in repeated zero-sum games, in a setting where the players have access to oracles that compute, in constant time, their best-response to any mixed strategy of their opponent. We show that the runtime required for approximating the minimax value of the game in this setting is Θ(√N), yielding again a quadratic improvement upon the oracle-free setting, where Θ(N) is known to be tight.