Distributed Constrained Online Nonconvex Optimization with Compressed Communication

Abstract

This paper considers distributed online nonconvex optimization with time-varying inequality constraints over a network of agents. For a time-varying graph, we propose a distributed online primal-dual algorithm with compressed communication to efficiently utilize communication resources. We show that the proposed algorithm establishes an $\mathcal{O}(T^{\max \{1-\hat{I}{¸}_1,\hat{I}{¸}_1\}})$ network regret bound and an $\mathcal{O}(T^{1-\hat{I}{¸}_1/2})$ network cumulative constraint violation bound, where $T$ is the number of iterations and $\hat{I}{¸}_1\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 at all iterations), the network cumulative constraint violation bound is reduced to $\mathcal{O}(T^{1-\hat{I}{¸}_1})$. These bounds are comparable to the state-of-the-art results established by existing distributed online algorithms with perfect communication for distributed online convex optimization with (time-varying) inequality constraints. Finally, a simulation example is presented to validate the theoretical results.

31 pages, 2 figures. arXiv admin note: text overlap with arXiv:2411.11574