Logarithmic Regret from Sublinear Hints
Logarithmic Regret from Sublinear Hints
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Aditya Bhaskara;Ashok Cutkosky;Ravi Kumar;Manish Purohit
中科院分区：
文献类型：
--
作者：
Aditya Bhaskara;Ashok Cutkosky;Ravi Kumar;Manish Purohit
我们考虑在线线性优化问题，在每一步的算法发挥一个点$x_t$的单位球，并遭受损失$\langle c_t，x_t\rangle$的一些成本向量$c_t$，然后透露给算法。最近的研究表明，如果一个算法在执行$x_t$之前收到一个与$c_t$有非平凡相关性的提示$h_t $，那么它可以实现$O（\log T）$的后悔保证，改进了标准设置中的$\Theta（\sqrt{T}）$的界限。在这项工作中，我们研究的问题，是否一个算法真的需要在每一个时间步的提示。有些令人惊讶的是，我们表明，一个算法可以获得$O（\log T）$遗憾在一个自然的查询模型下，只有$O（\sqrt{T}）$提示;相反，我们还表明，$O（\sqrt {T}）$提示不能保证比$\Omega（\sqrt{T}）$遗憾。我们给我们的结果的两个应用程序，以及研究设置乐观的遗憾界和在线学习的问题与克制。
We consider the online linear optimization problem, where at every step the algorithm plays a point $x_t$ in the unit ball, and suffers loss $\langle c_t, x_t\rangle$ for some cost vector $c_t$ that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint $h_t$ that has non-trivial correlation with $c_t$ before it plays $x_t$, then it can achieve a regret guarantee of $O(\log T)$, improving on the bound of $\Theta(\sqrt{T})$ in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain $O(\log T)$ regret with just $O(\sqrt{T})$ hints under a natural query model; in contrast, we also show that $o(\sqrt{T})$ hints cannot guarantee better than $\Omega(\sqrt{T})$ regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.