Budget-Constrained Multi-Consensus Decentralized Gradient Descent
Abstract
We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. As a first step toward the broader communication-computation allocation problem, we consider and analyze a \textit{multi-consensus decentralized gradient descent} (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled consensus-allocation strategy under resource constraints, for which we show that equal allocation of consensus rounds across iterations is optimal under our stepsize rule, up to integer rounding. Numerical experiments corroborate the theoretical findings and demonstrate favorable communication-computation tradeoffs compared with existing multi-consensus decentralized optimization baselines.
Related
- Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective
- Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
- Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks
- Stochastic consensus dynamics for decentralized decision systems
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
BibTeX
@misc{ren2026budgetconstrained,
title = {{Budget-Constrained Multi-Consensus Decentralized Gradient Descent}},
author = {Shuyi Ren and Nicol`o Michelusi and Erik G. Larsson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08508},
eprint = {2610.08508},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08508},
}
RIS
TY - UNPB
TI - Budget-Constrained Multi-Consensus Decentralized Gradient Descent
AU - Shuyi Ren
AU - Nicol`o Michelusi
AU - Erik G. Larsson
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08508
UR - https://arxiv.org/abs/2610.08508
AB - We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. As a first step toward the broader communication-computation allocation problem, we consider and analyze a \textit{multi-consensus decentralized gradient descent} (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled consensus-allocation strategy under resource constraints, for which we show that equal allocation of consensus rounds across iterations is optimal under our stepsize rule, up to integer rounding. Numerical experiments corroborate the theoretical findings and demonstrate favorable communication-computation tradeoffs compared with existing multi-consensus decentralized optimization baselines.
ER -