无需斯莱特条件，实现在线凸优化的高效约束控制。
Constrained Online Convex Optimization without Slater's Condition
- 设计自适应正则化的原对偶框架，稳定双变量更新过程。
- 随机约束下，期望误差和约束违反均达 $O(\ oot{2}{T})$ 级别。
- 适用于强凸损失与对抗性约束，适合需高可靠性的系统设计。
研究对抗性损失下带随机或对抗性约束的在线凸优化问题。现有算法在随机约束情形常依赖斯莱特条件等正则性假设以获得近优的遗憾与约束违反界；而对抗性约束算法虽避免此类假设，却需使用严格逐轮可行的比较器。本文提出一种即用型原对偶框架，通过在对偶更新中引入自适应正则项，使对偶过程稳定，不再依赖斯莱特条件带来的负漂移。对于凸损失与随机约束，该算法实现 $O(\sqrt{T})$ 期望遗憾与 $O(\sqrt{T}\log T)$ 期望累计约束违反。进一步证明其在高概率意义下也具有相同阶的保证。当损失为强凸时，遗憾降至 $O(\log T)$，约束违反仍保持同阶。经小幅修改，该框架亦可处理对抗性约束，并提供硬约束违反的保证。
原文摘要 · Abstract (English)
We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to $O(\log T)$ with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。