Optimal anytime regret with two experts
Optimal anytime regret with two experts
复制标题
最佳随时后悔与两位专家
DOI：
10.4171/msl/38
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sikander Randhawa
中科院分区：
文献类型：
--
作者：
Nicholas J. A. Harvey;Christopher Liaw;E. Perkins;Sikander Randhawa
乘法方法是通过专家建议进行预测问题的算法。如果专家的数量很大，并且时间范围是事先知道的，那么它会渐近地实现Minimax遗憾。最佳算法也知道是否恰好有两个或三个专家，并且时间范围是事先知道的。
在任何时间范围内不知道的时间范围的情况下，可以通过加倍的技巧获得算法，但它们不是最佳的，更不用说实用了。无论专家数量如何，在任何时间设置中都没有最小值最佳算法。
我们设计了第一个最小值最佳算法，以最大程度地减少任何时间设置的遗憾。我们考虑两位专家的案例，并证明最佳遗憾是$ \ gamma \ sqrt {t} / 2 $在所有时间步骤$ t $，其中$ \ gamma $是35年前出现的自然常数布朗运动的基本特性。该算法是通过考虑连续类似物设计的，该算法是使用随机演算中的思想来解决的。
The multiplicative weights method is an algorithm for the problem of prediction with expert advice. It achieves the minimax regret asymptotically if the number of experts is large, and the time horizon is known in advance. Optimal algorithms are also known if there are exactly two or three experts, and the time horizon is known in advance.
In the anytime setting, where the time horizon is not known in advance, algorithms can be obtained by the doubling trick, but they are not optimal, let alone practical. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts.
We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is $\gamma \sqrt{t} / 2$ at all time steps $t$, where $\gamma$ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue, which is solved using ideas from stochastic calculus.
粘性布朗舍入及其在约束满足问题中的应用
DOI：
10.1137/1.9781611975994.52
发表时间：
2020
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Abbasi-Zadeh, S;Bansal, N;Guruganesh, G.;Nikolov, A;Schwartz, R;Singh, M.
通讯作者：
Singh, M.
影响因子：
3.1
作者：
Diakonikolas, Jelena;Orecchia, Lorenzo
通讯作者：
Orecchia, Lorenzo