Distributed Optimization with Nesterov Momentum and Finite-Time Quantized Averaging over Directed Networks: Extended Version

Abstract

In modern large-scale networked systems, rapidly solving optimization problems while utilizing communication resources efficiently is critical for addressing complex tasks. However, distributed optimization over bandwidth-limited networks must cope with two obstacles: limited-bandwidth communication, and slow convergence when the objective is ill-conditioned. In this paper, we consider unconstrained distributed optimization over strongly connected directed networks, where nodes exchange quantized (i.e., compressed) messages. We propose QANM (Quantized Averaged Nesterov Momentum), an algorithm that combines Nesterov momentum with a finite-time quantized averaging protocol. At every iteration, QANM enables all nodes to reach exact agreement, without requiring doubly stochastic weight matrices or undirected communication. For strongly convex and smooth objectives, we show that the objective gap of QANM decays at the accelerated rate $1-{\kappa }^{-1/2}$ (where $\kappa$ is the condition number), up to a residual of order ${\Delta }^2$ determined by the quantization level $\Delta$. This improves the condition-number dependence of the transient iteration complexity from $\kappa$ to $\sqrt{\kappa }$ compared with gradient descent that utilizes the same quantized averaging mechanism. Finally, we evaluate QANM on a distributed sensor fusion problem, showing that our algorithm exhibits the fastest initial error reduction compared with other methods from current literature.