A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

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 $\epsilon$ – 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 $\mathrm{\Omega }\text{\hspace{0.17em}⁣}({\chi }_{\mathcal{G}}\sqrt{{\kappa }_g}\log \frac{n}{{\chi }_{\mathcal{G}}}\log \frac{1}{\epsilon })$ communication rounds, where ${\chi }_{\mathcal{G}}$ is the condition number of the network Laplacians and ${\kappa }_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.