Decentralized Optimization With Multiple Local Updates and Network-Independent Stepsizes

Efficient communication is crucial for decentralized optimization and learning to scale effectively in large-scale engineered systems. Although performing multiple local updates per communication round significantly enhances communication efficiency in server-assisted distributed learning (i.e., federated learning), extending this strategy to fully decentralized settings remains a fundamental challenge. In fact, to incorporate multiple local updates, existing decentralized methods often rely on small/diminishing stepsizes, sacrifice consensus guarantees, or incur high communication overhead due to auxiliary variable exchanges. In this paper, we propose MIND, a fully decentralized algorithm that overcomes these limitations and is applicable to both exact and stochastic gradient scenarios. MIND introduces a novel update mechanism that guarantees convergence without auxiliary variables, exchanging only a single vector between two interacting agents per communication round. This reduces communication costs by at least half compared to existing methods, which require sharing both the optimization and auxiliary variables. Additionally, MIND achieves accurate convergence with a network-independent stepsize, unlike most existing decentralized optimization methods where each agent must access global network information to determine the stepsize. Extensive experiments demonstrate that MIND outperforms existing methods in both convergence speed and communication efficiency.