CLASP算法在线优化中同时控制损失与约束违规，强凸问题下实现对数级性能保证。
CLASP: An online learning algorithm for Convex Losses And Squared Penalties
- 基于凸投影的非扩张性，设计新在线学习算法
- 强凸场景下累积损失与惩罚均达O(log T)界
- 适合需要严格约束控制的在线决策任务
我们研究约束型在线凸优化（COCO），学习者迭代选择动作，观测未预见的凸损失和凸约束，累积损失并因违反约束而受罚。本文提出CLASP（凸损失与平方惩罚）算法，旨在最小化累积损失及平方约束违规项。分析突破以往方法，充分利用凸投影的严格非扩张性，这一证明策略此前未在该场景使用。对于凸损失，CLASP在任意β∈(0,1)下达到后悔值O(T^{max{β,1−β}})和累积平方惩罚O(T^{1−β})。更重要的是，在强凸情形下，首次实现对数级后悔与累积平方惩罚上界：两者均被控制在O(log T)内。
原文摘要 · Abstract (English)
We study Constrained Online Convex Optimization (COCO), where a learner chooses actions iteratively, observes both unanticipated convex loss and convex constraint, and accumulates loss while incurring penalties for constraint violations. We introduce CLASP (Convex Losses And Squared Penalties), an algorithm that minimizes cumulative loss together with squared constraint violations. Our analysis departs from prior work by fully leveraging the firm non-expansiveness of convex projectors, a proof strategy not previously applied in this setting. For convex losses, CLASP achieves regret $O\left(T^{\max\{β,1-β\}}\right)$ and cumulative squared penalty $O\left(T^{1-β}\right)$ for any $β\in (0,1)$. Most importantly, for strongly convex problems, CLASP provides the first logarithmic guarantees on both regret and cumulative squared penalty. In the strongly convex case, the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。