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 $\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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.12675
curl -X POST /api/v1/records/arxiv/2606.12675/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.12675/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'