Constrained Online Convex Optimization with Polyak Feasibility Steps

Spencer Hutchinson, Mahnoosh Alizadeh

In this work, we study online convex optimization with a fixed constraint function $g:{\mathbb{R}}^d\to \mathbb{R}$. Prior work on this problem has shown $O(\sqrt{T})$ reg…