A well-studied generalization of the standard online convex optimization
(OCO) is constrained online convex optimization (COCO). In COCO, on every
round, a convex cost function and a convex constraint function are revealed to
the learner after the action for that round is chosen. The objective is to
design an online policy that simultaneously achieves a small regret while
ensuring small cumulative constraint violation (CCV) against an adaptive
adversary. A long-standing open question in COCO is whether an online policy
can simultaneously achieve $O(\sqrt{T})$ regret and $O(\sqrt{T})$ CCV without
any restrictive assumptions. For the first time, we answer this in the
affirmative and show that an online policy can simultaneously achieve
$O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV. We establish this result by
effectively combining the adaptive regret bound of the AdaGrad algorithm with
Lyapunov optimization - a classic tool from control theory. Surprisingly, the
analysis is short and elegant.

有关在线凸优化和约束在线凸优化的一篇研究论文，证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规，通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合，达到了这一结果。