Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a communication complexity lower bound for decentralized convex optimization in time-varying networks, focusing on the number of rounds required for nodes to reach an agreement on the global minimizer. The authors derive a lower bound of \(Ω\left(χ_{\mathcal G} \sqrt{κ_g}\,\log\frac{n}{χ_{\mathcal G}}\log\frac1\varepsilon\right)\), demonstrating that the achievable round complexity under uniform conditions cannot be replicated in nonuniform scenarios. Their approach leverages spectral graph theory, utilizing time-rotating star gadgets to maintain spectral connectivity in the network's communication structure.
Nonuniform networks require significantly more communication rounds for consensus than previously understood, with a new lower bound that challenges existing assumptions about optimization efficiency.
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.