Abstract
We study online convex optimization with constraints consisting of multiple functional constraints and a relatively simple constraint set, such as a Euclidean ball. As enforcing the constraints at each time step through projections is computationally challenging in general, we allow decisions to violate the functional constraints but aim to achieve a low regret and cumulative violation of the constraints over a horizon of $T$ time steps. First-order methods achieve an $\mathcal O(\sqrt T)$ regret and an $\mathcal O(1)$ constraint violation, which is the best-known bound, but do not take into account the structural information of the problem. Furthermore, the existing algorithms and analysis are limited to Euclidean space. In this paper, we provide an emphinstance-dependent bound for online convex optimization with complex constraints obtained by a novel online primal-dual mirror-prox algorithm. Our instance-dependent regret is quantified by the total gradient variation $V_*(T)$ in the sequence of loss functions. The proposed algorithm works in emphgeneral non-Euclidean spaces and simultaneously achieves an $\mathcal O(\sqrt{V_*(T)})$ regret and an $\mathcal O(1)$ constraint violation, which is never worse than the best-known $(\mathcal O(\sqrt T), \mathcal O(1) )$ result and improves over previous works that applied mirror-prox-type algorithms for this problem achieving $\mathcal O(T^{2/3})$ regret and constraint violation. Finally, our algorithm is computationally efficient, as it only performs mirror descent steps in each iteration instead of solving a general Lagrangian minimization problem.
Shuang Qiu
Post-doc (2021-)
Mladen Kolar
Associate Professor of Econometrics and Statistics
Mladen Kolar is an Associate Professor of Econometrics and Statistics at the University of Chicago Booth School of Business. His research is focused on high-dimensional statistical methods, graphical models, varying-coefficient models and data mining, driven by the need to uncover interesting and scientifically meaningful structures from observational data.