Abhishek Sinha - Optimal Algorithms for Online Convex Optimization with Adversarial Constraints

Instructor : Abhishek Sinha
Affiliation : TIFR, Mumbai
Abstract : Constrained Online Convex Optimization (COCO) is a well-studied extension of the standard Online Convex Optimization framework, where at each round the learner selects an action before observing both a convex loss function and a convex constraint function. The goal is to design an online policy that achieves both low regret and low cumulative constraint violation (CCV) against an adaptive adversary over a horizon of length T. A fundamental open question in this area has been whether it is possible to simultaneously obtain O(√T) regret and Õ(√T) CCV without imposing any structural assumptions on the problem.

In this talk, I will present the first affirmative resolution of this question. We show that a simple first-order algorithm attains these bounds simultaneously. I will further discuss extensions of this result under strong convexity and smoothness conditions, an anytime version of the policy, and generalizations to long-term budget constraints and bandit feedback.

Joint work with Rahul Vaze (TIFR), Dhruv Sarkar (IIT Kharagpur), Subhamon Supantha (IIT Bombay), and Samrat Mukhopadhyay (IIT Dhanbad)