Talk Less, Work More: Communication-Efficient Decentralized Stochastic Approximation

Decentralized Stochastic Approximation (SA) enables cooperative fixed-point solving over mesh networks without a central server. In these systems, local update is relatively cheap compared with coordination, and frequent information exchange makes communication cost the main bottleneck. To alleviate this issue, we propose a decentralized SA method in which each agent performs $H$ local updates before each communication round. By amortizing communications over multiple local SA updates, the method can substantially reduce communication cost. We also study a multiple mixing scheme based on FastMix, which trades a small amount intra-round communications for a stronger consensus effectiveness on poorly connected graphs. Theoretically, we establish finite-time bounds under general contractive norms and Markovian sampling, by combining contraction, consensus error, and delayed Markovian terms in a round-level Lyapunov recursion. The results show trade-offs among computation, communication and sampling. Numerical experiments on decentralized Q-learning, Markovian SGD and linear SA validate the theory and show substantial communication savings for target accuracy.