首次实现约束在线优化中后悔与约束违规的最优√T界
Optimal Bounds for Adversarial Constrained Online Convex Optimization
- 设计新代理损失函数，强制约束惩罚最小化
- 首次达到后悔和累积约束违规均为O(√T)的最优界
- 适用于对抗性环境下的在线学习算法设计
约束在线凸优化（COCO）可视为标准在线凸优化（OCO）的推广。每轮中，学习者先选择动作，随后揭示代价函数和约束函数。目标是同时最小化对自适应对手的后悔值和累积约束违规（CCV）。本文首次证明，在不增加额外假设的前提下，可同时实现后悔和CCV的最优 $O(ar{\sqrt{T}})$ 界，优于此前已知的 $O(ar{\sqrt{T}})$ 与 $\tilde{O}(ar{\sqrt{T}})$。基于一种新的代理损失函数，该函数对约束函数施加最小惩罚，我们证明了跟随正则化领导者（FTRL）和在线梯度下降（OGD）均能达到最优边界。
原文摘要 · Abstract (English)
Constrained Online Convex Optimization (COCO) can be seen as a generalization of the standard Online Convex Optimization (OCO) framework. At each round, a cost function and constraint function are revealed after a learner chooses an action. The goal is to minimize both the regret and cumulative constraint violation (CCV) against an adaptive adversary. We show for the first time that is possible to obtain the optimal $O(\sqrt{T})$ bound on both regret and CCV, improving the best known bounds of $O \left( \sqrt{T} \right)$ and $\tilde{O} \left( \sqrt{T} \right)$ for the regret and CCV, respectively. Based on a new surrogate loss function enforcing a minimum penalty on the constraint function, we demonstrate that both the Follow-the-Regularized-Leader and the Online Gradient Descent achieve the optimal bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。