标题： 在线凸优化的自适应算法与长期约束 显示英文标题

标题： Adaptive Algorithms for Online Convex Optimization with Long-term Constraints

摘要： 我们提出了一种自适应在线梯度下降算法，以解决具有长期约束的在线凸优化问题，这些约束需要在有限轮数T内累积满足，但在中间轮次中可以被违反。 对于某些用户定义的权衡参数$\beta$ $\in$ (0, 1)，所提出的算法分别在损失和约束违反方面实现了累计遗憾界的O(T^max{$\beta$,1--$\beta$})和O(T^(1--$\beta$/2))。 我们的结果适用于凸损失，并且可以在不需要预先知道轮数的情况下处理任意凸约束。 我们的贡献改进了Mahdavi等人(2012)的最佳已知累计遗憾界，分别为一般凸域的O(T^1/2)和O(T^3/4)，以及在进一步限制到多面体域时的O(T^2/3)和O(T^2/3)。 我们通过实验补充了分析，验证了我们的算法在实际中的性能。 显示英文摘要

摘要： We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints , which are constraints that need to be satisfied when accumulated over a finite number of rounds T , but can be violated in intermediate rounds. For some user-defined trade-off parameter $\beta$ $\in$ (0, 1), the proposed algorithm achieves cumulative regret bounds of O(T^max{$\beta$,1--$\beta$}) and O(T^(1--$\beta$/2)) for the loss and the constraint violations respectively. Our results hold for convex losses and can handle arbitrary convex constraints without requiring knowledge of the number of rounds in advance. Our contributions improve over the best known cumulative regret bounds by Mahdavi, et al. (2012) that are respectively O(T^1/2) and O(T^3/4) for general convex domains, and respectively O(T^2/3) and O(T^2/3) when further restricting to polyhedral domains. We supplement the analysis with experiments validating the performance of our algorithm in practice.