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, 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} non-Euclidean 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的时间步骤范围内实现对限制的低遗憾和累积违反。 第一阶方法可以实现一个全新的在线初等镜像算法的复杂限制 。 在损失函数序列中, 我们依赖实例的遗憾通过总变色变异 $V}(T} 美元) 来量化, 但不考虑问题的结构信息。 此外, 现有的算法和分析仅限于 Eucliidean 空间 。 在本文件中, 我们提供的 emph\ imphr\ imetx 步数将连接到在线的精度优化, 新的线性镜像算算算法 。 在损失函数中, 我们依赖实例的遗憾通过总变异度变 $ (T) (T) 硬度 来量化 。