BAGEL在分离查询下实现低后悔与约束违规，适合复杂可行集场景。
BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access
- 用分离查询替代投影查询，结合李雅普诺夫加权损失与分块梯度下降。
- 达到$ ilde{ ext{O}}((D/r)^2T^{2β})$次查询，$ ext{O}(T^{1-β})$后悔与$ ext{O}(T^{1-β} ext{log}T)$违规。
- 适用于难以投影但可分离的凸集，对几何结构敏感，适合理论与高维优化研究者。
在对抗性约束在线凸优化（COCO）中，学习者从固定凸集中选择动作，目标是在随时间变化的约束下同时实现低后悔和低累积约束违规（CCV）。本文探讨当动作集通过分离查询（SO）访问，而非精确投影查询（PO）或线性优化查询（LOO）时，能达到何种性能。提出算法BAGEL，结合李雅普诺夫加权代理损失、分块自适应在线梯度下降及基于SO的不可行投影过程。对于凸代价函数及任意$β∈(0,1/2]$，BAGEL实现$ ext{O}(T^{1-β})$后悔与$ ext{O}(T^{1-β} ext{log}T)$累积违规，仅需$ ilde{ ext{O}}((D/r)^2T^{2β})$次分离查询。当$β=1/2$时，获得$ ext{O}( ext{√}T)$后悔与$ ext{O}( ext{√}T ext{log}T)$违规，且查询次数近似线性。该结果为基于查询访问的性能保证，其计算效率依赖于动作集的几何结构及分离查询的实现成本。
原文摘要 · Abstract (English)
In adversarial Constrained Online Convex Optimization (COCO), a learner selects actions from a fixed convex set while seeking both low regret and low cumulative constraint violation (CCV) under time-varying constraints. We ask what performance is achievable when the action set is accessed through a Separation Oracle (SO), rather than an exact Projection Oracle (PO) or a Linear Optimization Oracle (LOO). We introduce $\mathtt{BAGEL}$, which combines a Lyapunov-weighted surrogate loss, blocked adaptive online gradient descent, and an infeasible-projection procedure implemented with an SO. For convex costs and any $β\in(0,1/2]$, $\mathtt{BAGEL}$ achieves $\mathcal{O}(T^{1-β})$ regret and $\mathcal{O}(T^{1-β}\log T)$ cumulative violation using $\widetilde{\mathcal{O}}((D/r)^2T^{2β})$ SO calls. At $β=1/2$, this gives $\mathcal{O}(\sqrt{T})$ regret and $\mathcal{O}(\sqrt{T}\log T)$ violation with a near-linear number of SO calls. The result is an access oracle based guarantee, with computational relevance depends on the geometry of the action set and the cost of implementing its SO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。