How to keep constraints satisfied while learning online

Online learning algorithms must make decisions before seeing their cost, while respecting adversarial constraints. This work improves the tradeoff between regret (performing nearly as well as the best feasible point) and constraint violation (how much rules are broken). For strongly convex losses, the method achieves logarithmic constraint violations—an exponential improvement over prior work—using a geometric insight about self-contracted curves.