论文标题
懒惰的在线梯度下降是多面体的通用
Lazy Online Gradient Descent is Universal on Polytopes
论文作者
论文摘要
我们证明熟悉的懒惰在线渐变下降算法是多层域上通用的。这意味着它会得到$ O（1）$ pseudo-regret对I.I.D对手，同时获得了众所周知的$ O（\ sqrt n）$最差的遗憾。为了进行比较，大部分文献都集中在单纯形上的树篱（指数重量）算法的变体上。这些原则上可以将其提升为一般的多面体。但是，对于许多重要的类别，这些过程在计算上是不可行的，在这些类别中，顶点数量随维度迅速增长。提升过程还忽略了成本向量上的任何欧几里得界限，并且可以在伪重新结合中创建额外的维度因素。梯度下降比文献中多型的少数专用算法更简单，并且在更广泛的环境中起作用。在特别的现有算法中，假设优化器是唯一的，而我们的界限则允许几个最佳顶点。
We prove the familiar Lazy Online Gradient Descent algorithm is universal on polytope domains. That means it gets $O(1)$ pseudo-regret against i.i.d opponents, while simultaneously achieving the well-known $O(\sqrt N)$ worst-case regret bound. For comparison the bulk of the literature focuses on variants of the Hedge (exponential weights) algorithm on the simplex. These can in principle be lifted to general polytopes; however the process is computationally unfeasible for many important classes where the number of vertices grows quickly with the dimension. The lifting procedure also ignores any Euclidean bounds on the cost vectors, and can create extra factors of dimension in the pseudo-regret bound. Gradient Descent is simpler than the handful of purpose-built algorithms for polytopes in the literature, and works in a broader setting. In particular existing algorithms assume the optimiser is unique, while our bound allows for several optimal vertices.
