{"id":"arxiv/2606.12675","url":"https://arxiv.org/abs/2606.12675","tags":["math.OC","cs.DC"],"score":0,"title":"A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization","domain":"math.OC","source":"arxiv","authors":["Demyan Yarmoshik","Maxim Klimenko"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}