精选理由
约束在线优化是机器学习中的核心问题，这篇论文用简洁的投影算法大幅降低了累积约束违反，做在线学习或凸优化理论的研究者值得关注，其自收缩性技巧可能启发更多改进。
本文针对对抗性约束下的在线凸优化（COCO）问题，提出了一种基于投影的简单算法。对于强凸损失，该算法同时实现了 O(log T) 的遗憾和 O(log T) 的累积约束违反（CCV），相比此前最优的 O(√T log T) CCV 实现了指数级改进。对于凸损失，算法将 CCV 从 O(√T log T) 降至 O(√T)，同时保持最优 O(√T) 遗憾。关键创新在于利用自收缩曲线的几何结果，该技术可能具有独立研究价值。
AI 翻译 · 中文
本文针对对抗性约束下的在线凸优化（COCO）问题，提出了一种基于投影的简单算法。对于强凸损失，该算法同时实现了 O(log T) 的遗憾和 O(log T) 的累积约束违反（CCV），相比此前最优的 O(√T log T) CCV 实现了指数级改进。对于凸损失，算法将 CCV 从 O(√T log T) 降至 O(√T)，同时保持最优 O(√T) 遗憾。关键创新在于利用自收缩曲线的几何结果，该技术可能具有独立研究价值。
We consider Constrained Online Convex Optimization (COCO) with adversarially chosen constraints. At each round, the learner chooses an action before observing the loss and constraint function for that round. The goal is …