提出新算法,同时优化在线学习的累积代价与约束违反程度。
Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
- 用代理代价函数将约束问题转化为标准在线凸优化
- 首个在无共同可行点时仍能实现最优动态后悔上界的方法
- 无需投影的算法在快速变化环境中表现更优,适合实时系统
我们研究了具有对抗性在线约束的广义在线凸优化(OCO)框架。在线学习者在多轮交互中逐轮选择动作,每轮开始时从凸决策集选行动,随后对手揭示凸代价函数和凸约束函数。目标是同时最小化累积代价并尽可能满足约束。本文提出两种结构简洁的高效算法,首次实现了通用动态后悔与累积约束违反的统一界,优于现有最优结果。第一种算法虽需投影到约束集但达到最优后悔界;第二种为无投影算法,在约束快速变化环境下获得更优的违反界。理论成立条件极为宽松:代价与约束函数可任意选择,且约束函数无需存在固定公共可行点。核心思想是构建特殊代理代价函数,将约束学习问题转化为标准OCO问题。
原文摘要 · Abstract (English)
We consider a generalization of the celebrated Online Convex Optimization (OCO) framework with adversarial online constraints. In this problem, an online learner interacts with an adversary sequentially over multiple rounds. At the beginning of each round, the learner chooses an action from a convex decision set. After that, the adversary reveals a convex cost function and a convex constraint function. The goal of the learner is to minimize the cumulative cost while satisfying the constraints as tightly as possible. We present two efficient algorithms with simple modular structures that give universal dynamic regret and cumulative constraint violation bounds, improving upon state-of-the-art results. While the first algorithm, which achieves the optimal regret bound, involves projection onto the constraint sets, the second algorithm is projection-free and achieves better violation bounds in rapidly varying environments. Our results hold in the most general case when both the cost and constraint functions are chosen arbitrarily, and the constraint functions need not contain any fixed common feasible point. We establish these results by introducing a general framework that reduces the constrained learning problem to an instance of the standard OCO problem with specially constructed surrogate cost functions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。