A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and Finite Constraint Violations for Online Convex Optimization with Long Term Constraints
A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and Finite Constraint Violations for Online Convex Optimization with Long Term Constraints
复制标题
DOI：
--
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Hao Yu;M. Neely
中科院分区：
文献类型：
--
作者：
Hao Yu;M. Neely
本文研究了复杂约束集上的在线凸优化问题，该问题通常由多个功能约束和一个集合约束组成。传统的在线投影算法（Zinkevich, 2003）由于投影操作潜在的高计算复杂度而难以实现。在本文中，我们放宽了功能约束，允许它们在每一轮被违反，但仍然要求它们在长期内得到满足。Mahdavi等人（2012）首先考虑了这种类型的宽松在线凸优化（具有长期约束）。先前的工作提出了一种算法来实现一般问题的$O(\sqrt{T})$遗憾和$O(T^{3/4})$约束违反，以及另一种算法来实现约束集可以由有限数量的线性约束描述时的遗憾和约束违反的$O(T^{2/3})$界。最近在\citet{Jenatton16ICML}中的扩展可以实现$O(T^{\max\{\theta,1-\theta\}})$遗憾和$O(T^{1-\theta/2})$约束违反，其中$\theta\in (0,1)$。本文提出了一种新的简单算法，与以前的工作相比，它的性能得到了提高。新算法实现了$O(1)$约束违规的$O(\sqrt{T})$后悔绑定。
This paper considers online convex optimization over a complicated constraint set, which typically consists of multiple functional constraints and a set constraint. The conventional online projection algorithm (Zinkevich, 2003) can be difficult to implement due to the potentially high computation complexity of the projection operation. In this paper, we relax the functional constraints by allowing them to be violated at each round but still requiring them to be satisfied in the long term. This type of relaxed online convex optimization (with long term constraints) was first considered in Mahdavi et al. (2012). That prior work proposes an algorithm to achieve $O(\sqrt{T})$ regret and $O(T^{3/4})$ constraint violations for general problems and another algorithm to achieve an $O(T^{2/3})$ bound for both regret and constraint violations when the constraint set can be described by a finite number of linear constraints. A recent extension in \citet{Jenatton16ICML} can achieve $O(T^{\max\{\theta,1-\theta\}})$ regret and $O(T^{1-\theta/2})$ constraint violations where $\theta\in (0,1)$. The current paper proposes a new simple algorithm that yields improved performance in comparison to prior works. The new algorithm achieves an $O(\sqrt{T})$ regret bound with $O(1)$ constraint violations.