Nesterov Accelerated Distributed Optimization with Efficient Quantized Communication
For practitioners of distributed optimization in networked systems, this work provides a method that simultaneously handles ill-conditioned objectives and communication constraints, though the improvement is incremental over existing techniques.
The paper tackles distributed optimization with directed communication graphs, addressing the zigzag phenomenon from ill-conditioned objectives and limited bandwidth via quantized messages. The proposed QANM algorithm achieves linear convergence to a neighborhood of the optimal solution, validated on a sensor fusion task with clear acceleration over non-momentum baselines.
In modern large-scale networked systems, rapidly solving optimization problems while utilizing communication resources efficiently is critical for addressing complex tasks. In this paper, we consider an unconstrained distributed optimization problem in which information exchange among nodes is governed by a directed communication graph. In our setup we focus on two key challenges. The first is the zigzag phenomenon caused by the objective functions of individual nodes having significantly different curvature along different directions. The second is that the communication channels among nodes are subject to limited bandwidth, which motivates the use of compressed (quantized) messages. To address both challenges simultaneously, we propose QANM, a distributed optimization algorithm that combines Nesterov-accelerated gradient descent with a distributed finite-time quantized consensus protocol, enabling accelerated convergence. Under strong convexity and smoothness assumptions, we show that our proposed algorithm converges linearly to a neighborhood of the optimal solution. Finally, we validate our algorithm on a distributed sensor fusion application for multi-dimensional target parameter estimation, where simulations across two distinct scenarios confirm the convergence guarantees and demonstrate clear acceleration benefits over non-momentum baselines.