带压缩通信的分布式约束在线非凸优化
Distributed Constrained Online Nonconvex Optimization with Compressed Communication
摘要 Abstract
本文研究了网络中具有时变不等式约束的分布式在线非凸优化问题。对于时变图,我们提出了一种带压缩通信的分布式在线原对偶算法,以高效利用通信资源。我们证明所提出的算法建立了$\mathcal{O}( {{T^{\max \{ {1 - {\theta_1},{\theta_1}} \}}}} )$的网络后悔界和$\mathcal{O}( {T^{1 - {\theta_1}/2}} )$的网络累积约束违反界,其中$T$为迭代次数,${\theta_1} \in ( {0,1} )$为用户定义的权衡参数。当Slater条件成立(即在所有迭代中存在一个严格满足不等式约束的点)时,网络累积约束违反界可减少至$\mathcal{O}( {T^{1 - {\theta_1}}} )$。这些界与现有针对带有(时变)不等式约束的分布式在线凸优化问题的完美通信状态-of-the-art结果相当。最后,通过仿真示例验证了理论结果。
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 - {\theta_1},{\theta_1}} \}}}} )$ network regret bound and an $\mathcal{O}( {T^{1 - {\theta_1}/2}} )$ network cumulative constraint violation bound, where $T$ is the number of iterations and ${\theta_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 - {\theta_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.