Tata Institute of Fundamental Research
Constrained Online Convex Optimization: A Simple Algorithm and Slater-Slack Reductions
Project Presentation
Speaker:
Aakash Ghosh (TIFR)
Organiser:
Abhishek Sinha
Date:
Thursday, 11 Jun 2026, 16:30 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Online convex optimization with adversarial, online-revealed constraints (COCO) is a natural model for safe sequential decision-making. However, adversarial constraints rule out simultaneous sublinear regret and per-round feasibility, so one instead controls aggregate violation. Two main approaches handle this: the Neely and Yu drift-plus-penalty method attains O(1) violation under a Slater condition but requires solving a convex program every round, while the recent work of Sinha and Vaze attains O(√T) regret and Õ(√T) strict cumulative violation requiring only a single projected-gradient step. After surveying this landscape, I ask a safe-learning question: if the learner additionally holds a baseline action that is strictly feasible by a margin, what benefits does this provide? I present a black-box reduction that wraps any base algorithm carrying a regret and violation certificate. I treat three regimes: a known point and margin, a known point with an unknown margin, and an unknown point with known margin lower bounds, concluding with a discussion of the tradeoffs involved.
| Speaker: | Aakash Ghosh (TIFR) |
| Organiser: | Abhishek Sinha |
| Date: | Thursday, 11 Jun 2026, 16:30 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Online convex optimization with adversarial, online-revealed constraints (COCO) is a natural model for safe sequential decision-making. However, adversarial constraints rule out simultaneous sublinear regret and per-round feasibility, so one instead controls aggregate violation. Two main approaches handle this: the Neely and Yu drift-plus-penalty method attains O(1) violation under a Slater condition but requires solving a convex program every round, while the recent work of Sinha and Vaze attains O(√T) regret and Õ(√T) strict cumulative violation requiring only a single projected-gradient step. After surveying this landscape, I ask a safe-learning question: if the learner additionally holds a baseline action that is strictly feasible by a margin, what benefits does this provide? I present a black-box reduction that wraps any base algorithm carrying a regret and violation certificate. I treat three regimes: a known point and margin, a known point with an unknown margin, and an unknown point with known margin lower bounds, concluding with a discussion of the tradeoffs involved.