提出新算法，实现√T级静态后悔与依赖实例的约束违反
$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
- 利用约束集几何特性设计算法，动态调整约束处理方式
- 静态后悔达O(√T)，约束违反最高为O(√T log T)且可更低
- 适用于约束集变化缓慢或结构规则的场景，如固定边界问题
考虑标准在线凸优化（OCO）的约束版本（COCO），每轮在学习者选择动作后才揭示凸代价函数和凸约束函数。目标是同时最小化静态后悔和累积约束违反（CCV）。本文提出一种算法，保证静态后悔为O(√T)，CCV为min{𝒱, O(√T log T)}，其中𝒱取决于连续约束集间的距离、约束集形状、动作空间维度及动作空间直径。对于特殊约束集情形，𝒱=O(1)。相比现有最优结果（静态后悔O(√T)，CCV O(√T log T)）的通用性，新结果的约束违反为实例相关，通过挖掘约束集几何性质实现。
原文摘要 · Abstract (English)
The constrained version of the standard online convex optimization (OCO) framework, called COCO is considered, where on every round, a convex cost function and a convex constraint function are revealed to the learner after it chooses the action for that round. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV). An algorithm is proposed that guarantees a static regret of $O(\sqrt{T})$ and a CCV of $\min\{\cV, O(\sqrt{T}\log T) \}$, where $\cV$ depends on the distance between the consecutively revealed constraint sets, the shape of constraint sets, dimension of action space and the diameter of the action space. For special cases of constraint sets, $\cV=O(1)$. Compared to the state of the art results, static regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T}\log T)$, that were universal, the new result on CCV is instance dependent, which is derived by exploiting the geometric properties of the constraint sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。