Tight Lower Bounds for Multiplicative Weights Algorithmic Families
Tight Lower Bounds for Multiplicative Weights Algorithmic Families
复制标题
乘法权重算法族的严格下界
DOI：
10.4230/lipics.icalp.2017.48
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Balasubramanian Sivan
中科院分区：
文献类型：
--
作者：
N. Gravin;Y. Peres;Balasubramanian Sivan
我们根据专家建议研究预测的基本问题，并为该问题的一大类算法开发遗憾下限。我们开发了简单的对抗性原语，它们可以进行各种组合，从而为许多算法系列带来明显的下限。我们使用这些原语来证明经典的乘法权重算法（MWA）具有 (T*ln(k)/2)^{0.5}（其中 T 是时间范围，k 是专家数量）的遗憾，从而完全缩小了上限和下限之间的差距。我们进一步展示了比 MWA 更通用的算法系列的遗憾下限 (2/3)* (T*ln(k)/2)^{0.5}，其中学习率可以随时间任意变化，甚至可以随时间从任意分布中选取。我们还使用我们的基元在 MWA 的几何水平设置中构建对手，以精确地表征 2 个专家情况下的遗憾为 0.391/(\delta)^{0.5}，以及任意数量专家 k 的情况下限为 (1/2)*(ln(k)/(2*\delta))^{0.5}（这里 delta 是游戏在任何给定回合中结束的概率）。
We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial primitives, that lend themselves to various combinations leading to sharp lower bounds for many algorithmic families. We use these primitives to show that the classic Multiplicative Weights Algorithm (MWA) has a regret of (T*ln(k)/2)^{0.5} (where T is the time horizon and k is the number of experts), there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of (2/3)* (T*ln(k)/2)^{0.5} for a much more general family of algorithms than MWA, where the learning rate can be arbitrarily varied over time, or even picked from arbitrary distributions over time. We also use our primitives to construct adversaries in the geometric horizon setting for MWA to precisely characterize the regret at 0.391/(\delta)^{0.5} for the case of 2 experts and a lower bound of (1/2)*(ln(k)/(2*\delta))^{0.5}, for the case of arbitrary number of experts k (here \delta is the probability that the game ends in any given round).