Regret to the best vs. regret to the average
Regret to the best vs. regret to the average
复制标题
对最好的遗憾与对平均的遗憾
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Jennifer Wortman Vaughan
中科院分区：
文献类型：
--
作者：
Eyal Even;Michael Kearns;Y. Mansour;Jennifer Wortman Vaughan
摘要在专家环境下，我们研究了在线后悔最小化算法。在这种设置中，算法在每个时间步选择专家的分布，并接收专家瞬时收益的加权平均值。我们考虑双标准设置，不仅检查对最好的专家的遗憾的标准概念，而且检查对所有专家的平均遗憾，对任何给定的固定专家的遗憾，或对最差的专家的遗憾。这项研究既导致了对现有无遗憾算法局限性的新理解，也导致了具有新的性能保证的新算法的出现。更具体地说，我们证明了任何仅实现
$O(SQRT{T})$
对T试验序列中最好的专家的累积后悔，在最坏的情况下，必须遭受后悔
$varOmega(SQRT{T})$
对于包括许多现有的无遗憾算法(如指数加权和跟随扰动的领导者)的一大类更新规则，最好的遗憾和平均的遗憾的乘积在最坏的情况下是Ω(T)。然后描述和分析了两种替代的新算法，这两种算法都只实现了累积错误
$O(SQRT{T}LOG T)$
对最好的专家，只对任何给定的专家固定分配感到遗憾(即，不依赖于T或专家数量N)。第一种算法的关键在于，根据观察到的专家表现差异，逐步增加更新的“进攻性”。第二种算法是对标准指数更新算法的简单改进。
AbstractWe study online regret minimization algorithms in an experts setting. In this setting, the algorithm chooses a distribution over experts at each time step and receives a gain that is a weighted average of the experts’ instantaneous gains. We consider a bicriteria setting, examining not only the standard notion of regret to the best expert, but also the regret to the average of all experts, the regret to any given fixed mixture of experts, or the regret to the worst expert. This study leads both to new understanding of the limitations of existing no-regret algorithms, and to new algorithms with novel performance guarantees. More specifically, we show that any algorithm that achieves only
$O(sqrt{T})$
cumulative regret to the best expert on a sequence of T trials must, in the worst case, suffer regret
$varOmega(sqrt{T})$
to the average, and that for a wide class of update rules that includes many existing no-regret algorithms (such as Exponential Weights and Follow the Perturbed Leader), the product of the regret to the best and the regret to the average is, in the worst case, Ω(T). We then describe and analyze two alternate new algorithms that both achieve cumulative regret only
$O(sqrt{T}log T)$
to the best expert and have only constant regret to any given fixed distribution over experts (that is, with no dependence on either T or the number of experts N). The key to the first algorithm is the gradual increase in the “aggressiveness” of updates in response to observed divergences in expert performances. The second algorithm is a simple twist on standard exponential-update algorithms.