Title: On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization,
Abstract: This paper introduces consensus-based primal-dual methods for distributed
online optimization where the time-varying system objective function
$f_t(\mathbf{x})$ is given as the sum of local agents' objective functions,
i.e., $f_t(\mathbf{x}) = \sum_i f_{i,t}(\mathbf{x}_i)$, and the system
constraint function $\mathbf{g}(\mathbf{x})$ is given as the sum of local
agents' constraint functions, i.e., $\mathbf{g}(\mathbf{x}) = \sum_i
\mathbf{g}_i (\mathbf{x}_i) \preceq \mathbf{0}$. At each stage, each agent
commits to an adaptive decision pertaining only to the past and locally
available information, and incurs a new cost function reflecting the change in
the environment. Our algorithm uses weighted averaging of the iterates for each
agent to keep local estimates of the global constraints and dual variables. We
show that the algorithm achieves a regret of order $O(\sqrt{T})$ with the time
horizon $T$, in scenarios when the underlying communication topology is
time-varying and jointly-connected. The regret is measured in regard to the
cost function value as well as the constraint violation. Numerical results for
online routing in wireless multi-hop networks with uncertain channel rates are
provided to illustrate the performance of the proposed algorithm.