Distributed Optimization of Clique-Wise Coupled Problems Via Three-Operator Splitting

This study explores distributed optimization problems with clique- wise coupling via operator splitting and how we can utilize this framework for performance analysis and enhancement. This framework extends beyond conventional pairwise coupled problems (e.g., consensus optimization) and is applicable to broader examples. To this end, we first introduce a new distributed algorithm by leveraging a clique-based matrix and the Davis-Yin splitting (DYS), a three-operator splitting method. We then demonstrate that this approach sheds new light on conventional algorithms in the following way: (i) Existing methods (NIDS, Exact diffusion, diffusion, and our previous work [1]) can be derived from our proposed method; (ii) We present a new mixing matrix through our analysis for the NIDS. We prove its preferable eigenvalue distribution enabling fast consensus; (iii) These observations yield a new linear convergence rate for the NIDS with non-smooth objective functions. Remarkably a linear rate is first established for the general DYS with a projection for a subspace. This case is not covered by any prior results, to our knowledge. Finally, numerical results showcase the efficacy of our approach.