Distributed Online Convex Optimization with Adversarial Constraints:
  Reduced Cumulative Constraint Violation Bounds under Slater's Condition
Xinlei Yi Xiuxian Li Tao Yang Lihua Xie Yiguang Hong Tianyou Chai Karl H. Johansson
This paper considers distributed online convex optimization with adversarial
constraints. In this setting, a network of agents makes decisions at each
round, and then only a portion of the loss function and a coordinate block of
the constraint function are privately revealed to each agent. The loss and
constraint functions are convex and can vary arbitrarily across rounds. The
agents collaborate to minimize network regret and cumulative constraint
violation. A novel distributed online algorithm is proposed and it achieves an
$\mathcal{O}(T^{\max\{c,1-c\}})$ network regret bound and an
$\mathcal{O}(T^{1-c/2})$ network cumulative constraint violation bound, where
$T$ is the number of rounds and $c\in(0,1)$ is a user-defined trade-off
parameter. When Slater's condition holds (i.e, there is a point that strictly
satisfies the inequality constraints), the network cumulative constraint
violation bound is reduced to $\mathcal{O}(T^{1-c})$. Moreover, if the loss
functions are strongly convex, then the network regret bound is reduced to
$\mathcal{O}(\log(T))$, and the network cumulative constraint violation bound
is reduced to $\mathcal{O}(\sqrt{\log(T)T})$ and $\mathcal{O}(\log(T))$ without
and with Slater's condition, respectively. To the best of our knowledge, this
paper is the first to achieve reduced (network) cumulative constraint violation
bounds for (distributed) online convex optimization with adversarial
constraints under Slater's condition. Finally, the theoretical results are
verified through numerical simulations.