We study online convex optimization with constraints consisting of multiple functional constraints and a relatively simple constraint set, such as a Euclidean ball. As enforcing the constraints at each time step through projections is computationally challenging in general, we allow decisions to violate the functional constraints but aim to achieve a low regret and cumulative violation of the constraints over a horizon of $T$ time steps. First-order methods achieve an $\mathcal{O}(\sqrt{T})$ regret and an $\mathcal{O}(1)$ constraint violation, which is the best-known bound under the Slater's condition, but do not take into account the structural information of the problem. Furthermore, the existing algorithms and analysis are limited to Euclidean space. In this paper, we provide an \emph{instance-dependent} bound for online convex optimization with complex constraints obtained by a novel online primal-dual mirror-prox algorithm. Our instance-dependent regret is quantified by the total gradient variation $V_*(T)$ in the sequence of loss functions. The proposed algorithm works in \emph{general} normed spaces and simultaneously achieves an $\mathcal{O}(\sqrt{V_*(T)})$ regret and an $\mathcal{O}(1)$ constraint violation, which is never worse than the best-known $( \mathcal{O}(\sqrt{T}), \mathcal{O}(1) )$ result and improves over previous works that applied mirror-prox-type algorithms for this problem achieving $\mathcal{O}(T^{2/3})$ regret and constraint violation. Finally, our algorithm is computationally efficient, as it only performs mirror descent steps in each iteration instead of solving a general Lagrangian minimization problem.
翻译:我们用多种功能限制和相对简单的限制设置来研究在线 convex优化, 包括多重功能限制和相对简单的限制设置, 如 Euclidean 球。 当通过预测执行每个时间步骤的限制限制在总体上具有计算上的挑战性时, 我们允许做出违反功能限制的决定, 但目的是在$T的时间步骤范围内实现对限制的低遗憾和累积违反。 在本文中, 第一阶方法可以实现一个$\ mathcal{O} 的最小端点优化, 由新的线上线上镜面算法获得的复杂限制。 在损失函数序列中, 最著名的限制是 $V} 美元, 但没有考虑到问题的结构信息。 此外, 现有的算法和分析仅限于 Euclidean 空间。 在本文中, 最糟糕的算法是, 最糟糕的阶值 。