We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as $\textit{consistency}$, while also ensuring worst-case $\textit{robustness}$ even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem's convexity. The first, INTERP, achieves $(\sqrt{2}+\epsilon)$-consistency and $\mathcal{O}(\frac{C}{\epsilon^2})$-robustness for any $\epsilon > 0$, where $C$ is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, BDINTERP, achieves $(1+\epsilon)$-consistency and $\mathcal{O}(\frac{CD}{\epsilon})$-robustness when the problem has bounded diameter $D$. Further, we show that BDINTERP achieves near-optimal consistency-robustness trade-off for the special case where cost functions are $\alpha$-polyhedral.
翻译:我们考虑的是Convex函数以黑箱建议追逐黑箱建议的问题, 在线决策者的目的是在机器学习算法的决定等黑箱建议的帮助下, 最大限度地减少在规范矢量空间中作出和转换决定的总成本。 决策者寻求的成本可以与运行良好时的建议相提并论, 被称为 $\ textit{ 一致性 $, 同时也确保最差的 $\ textit{ robtness} 美元, 即使建议是对立的。 我们首先考虑的是将建议决定和竞争性算法转换为建议决定和竞争性算法之间的通用算法范式, 表明在保持稳健的情况下, 该类的算法不能在3个一致的情况下得到改进。 然后我们提出两种新的算法, 利用问题的一致性, INTEP, 实现美元( sqrtrit{2\\\ eepsil} $( lefral- calal) 美元, 当任何美元 CD- tality $xx 的计算成本时, 。