论文标题
追逐凸功能的无维度界限
Dimension-Free Bounds on Chasing Convex Functions
论文作者
论文摘要
我们考虑追逐凸功能的问题，其中功能会随着时间的推移到达而到达。玩家看到功能后采取行动，目标是为这些动作实现较小的功能成本，以及在动作之间移动的小成本。虽然一般问题需要对维度的多项式依赖性，但我们展示了如何获得良好的函数的尺寸依赖性界限。特别是，我们考虑了凸函数为$κ$的条件的情况，并给出了一种实现$ o（\sqrtκ）$ - 竞争力的算法。此外，当在$ k $维仿期子空间上支持该功能时，当功能是某些仿射子空间的指示器时，我们获取$ o（\ min（k，\ sqrt {k \ log t}}）$ - 竞争算法的竞争算法，用于$ t Lengvent $ t $ $ t $的竞争算法。我们还显示了一些下限，条件良好的功能需要$ω（κ^{1/3}）$ - 竞争力，$ k $ - 维功能需要$ω（\ sqrt {k}）$ - 竞争力。
We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small function cost for these actions, as well as a small cost for moving between actions. While the general problem requires a polynomial dependence on the dimension, we show how to get dimension-independent bounds for well-behaved functions. In particular, we consider the case where the convex functions are $κ$-well-conditioned, and give an algorithm that achieves an $O(\sqrt κ)$-competitiveness. Moreover, when the functions are supported on $k$-dimensional affine subspaces--e.g., when the function are the indicators of some affine subspaces--we get $O(\min(k, \sqrt{k \log T}))$-competitive algorithms for request sequences of length $T$. We also show some lower bounds, that well-conditioned functions require $Ω(κ^{1/3})$-competitiveness, and $k$-dimensional functions require $Ω(\sqrt{k})$-competitiveness.
