论文标题
在线和强盗算法超过$ \ ell_p $ norms
Online and Bandit Algorithms Beyond $\ell_p$ Norms
论文作者
论文摘要
向量规范在计算机科学和优化中起着基本作用，因此，持续的努力将现有算法推广到$ \ ell_ \ infty $和$ \ ell_p $ norms以外的设置。我们表明，许多在线和强盗应用程序的一般规范应用程序都承认良好的算法，只要规范可以通过``梯度稳定''的函数近似，即我们引入的概念。大致说，随着我们增加输入向量，该函数的梯度不应在任何组件中（多重）大幅下降。我们证明，包括所有单调对称规范在内的一些规范家庭承认梯度稳定的近似，为我们提供了这些规范家庭的第一个在线和强盗算法。 特别是，我们的梯度稳定性概念给出了$ o \ big（\ log^2（\ text {dimension}）\ big）$ - 竞争性算法，用于在线通用负载平衡和具有背包的匪徒的对称规范概括。我们的技术还扩展到超出对称规范的应用程序，例如在线矢量调度和凸成本的在线概括分配。通过梯度稳定近似所暗示的我们应用程序的一些关键属性是``平稳的游戏不平等''，并且与詹森的不平等相交。
Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond $\ell_\infty$ and $\ell_p$ norms. We show that many online and bandit applications for general norms admit good algorithms as long as the norm can be approximated by a function that is ``gradient-stable'', a notion that we introduce. Roughly it says that the gradient of the function should not drastically decrease (multiplicatively) in any component as we increase the input vector. We prove that several families of norms, including all monotone symmetric norms, admit a gradient-stable approximation, giving us the first online and bandit algorithms for these norm families. In particular, our notion of gradient-stability gives $O\big(\log^2 (\text{dimension})\big)$-competitive algorithms for the symmetric norm generalizations of Online Generalized Load Balancing and Bandits with Knapsacks. Our techniques extend to applications beyond symmetric norms as well, e.g., to Online Vector Scheduling and to Online Generalized Assignment with Convex Costs. Some key properties underlying our applications that are implied by gradient-stable approximations are a ``smooth game inequality'' and an approximate converse to Jensen's inequality.
