A Geometric Approach to Constrained Online Learning

We consider an online learning problem with time-varying adversarial constraints. At each round, a learner selects an action from a bounded convex decision set before observing a loss function and a constraint function, both of which are chosen by an adaptive adversary. The goal of the learner is to obtain the minimax-optimal regret for the loss functions relative to the best fixed action satisfying all constraints in hindsight and to simultaneously minimize the cumulative constraint violation ($\CCV$) corresponding to the constraint functions. Prior to this work, the best-known algorithms achieve $O(\log T)$ $\Regret$ and $O(\sqrt{T\log T})$ $\CCV$ for strongly convex losses and $O(\sqrt{T})$ $\Regret$ and $O(\sqrt{T}\log T)$ $\CCV$ for general convex losses. In this paper, we present an iterated projection-based algorithm \textsf{NP-OGD} that attains $O(\log T)$ $\Regret$ and $O(\log T)$ $\CCV$ for strongly convex losses---reducing the $\CCV$ from polynomial to logarithmic. For general convex losses, our algorithm achieves $O(\sqrt{T})$ $\Regret$ and $O(\sqrt{T})$ $\CCV$, eliminating an extra logarithmic factor from prior bounds. The key to our analysis is a recent geometric result on the path length of self-contracted curves. In particular, we show that when appropriately lifted to a higher-dimensional space, the iterates produced by the nested projected gradient-descent algorithm satisfy a self-contraction property with respect to a non-standard norm. Furthermore, by utilizing a layered sphere-packing construction, we complement our achievability result by establishing an $\Omega\big(\frac{(\log T)^{\frac{d-1}{d+1}}}{\log \log T}\big)$ lower bound for $\CCV$ for strongly convex losses for any online no-regret algorithm. We also establish an $\Omega(T^{\frac{d-1}{2(d+3)}})$ lower bound for the $\CCV$ in the convex-loss setting for any weakly adaptive algorithm achieving $O(\sqrt{T})$ regret.