[Paper] A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

Source: arXiv - 2606.12675v1

Overview

We study the communication complexity of convex decentralized optimization over time-varying networks, where $n$ nodes hold private functions and must agree on the global minimizer using only synchronous exchanges with neighbors. The cost is the number of communication rounds to reach accuracy $\varepsilon$ — a measure akin to round complexity in the LOCAL model, but constrained by nodes sharing only oracle responses. We prove a new lower bound of $Ω!\left(χ_{\mathcal G} \sqrt{κ_g},\log\frac{n}{χ_{\mathcal G}}\log\frac1\varepsilon\right)$ communication rounds, where $χ_{\mathcal G}$ is the condition number of the network Laplacians and $κ_g$ that of the global objective, showing the round complexity attainable under uniform regularity cannot be matched in the nonuniform regime. The construction rests on spectral graph theory: we embed time-rotating star gadgets into the edges of an expander and patch them to preserve spectral connectivity.

Key Contributions

This paper presents research in the following areas:

• math.OC
• cs.DC

Methodology

Please refer to the full paper for detailed methodology.

Practical Implications

This research contributes to the advancement of math.OC.

Authors

• Demyan Yarmoshik
• Maxim Klimenko

Paper Information

• arXiv ID: 2606.12675v1
• Categories: math.OC, cs.DC
• Published: June 10, 2026
• PDF: Download PDF