Distributed Optimization with Nesterov Momentum and Finite-Time Quantized Consensus

The gist In this paper, QANM proposes a distributed optimization algorithm that combines Nesterov-accelerated gradient descent with a distributed finite-time quantized consensus protocol to enable accelerated convergence under bandwidth constraints.

Problem Context and Challenges

Distributed optimization is critical for large-scale networked systems where information exchange is governed by a directed communication graph, presenting challenges related to zigzag phenomena caused by differing objective function curvatures and limited bandwidth necessitating compressed (quantized) messages. The paper addresses two key challenges: the zigzag phenomenon caused by the objective functions of individual nodes having significantly different curvature along different directions and that the communication channels among nodes are subject to limited bandwidth, which motivates the use of compressed (quantized) messages. Existing methods often fail because they either impose restrictive assumptions on network topology or do not exhibit communication efficiency among nodes in bandwidth-constrained networks.

Proposed Algorithm QANM

The proposed algorithm, Algorithm 1 (QANM), integrates Nesterov momentum with a finite-time quantized averaging protocol. The iteration process involves several key steps for each node vi:

1. Calculates the look-ahead position as s[k]i = x[k]i + βi(x[k]i − x[k−1]i).

2. Performs one gradient descent step with Nesterov momentum as z[k+1]i = s[k]i − α∇fi(s[k]i).

3. Updates its local estimate variable as x[k+1]i = Algorithm 2q∆(z[k+1]i), D, ∆.

The intuition behind this algorithm is that the quantization level ∆ used in Algorithm 2 (FTQAC) enables quantized communication among nodes, and it determines the desired precision of the solution. Algorithm 2 (FTQAC) runs between two consecutive optimization steps k and k + 1 of Algorithm 1, using a different time index λ.

Convergence Guarantees

Under the assumptions that the local cost function fi of each node vi is closed, proper, µi-strongly convex and Li-smooth, the paper establishes a linear convergence rate for Algorithm 1 (QANM). Specifically, Theorem 1 shows that the sequence of points satisfies∥x[k+1]i − x∗∥ + c∥x[k]i − x∗∥ ≤ d∥x[k]i − x∗∥ + cx[k−1]i − x∗ + O(∆). This implies that Algorithm 1 (QANM) converges R-linearly to a neighborhood of the optimal solution, with the size of this neighborhood determined by the quantization level ∆.

Validation and Application

The proposed algorithm is validated on a distributed sensor fusion application for multi-dimensional target parameter estimation. Simulations across two distinct scenarios confirm the convergence guarantees and demonstrate clear acceleration benefits over nonmomentum baselines. In one scenario, when using a shared matrix P with momentum coefficient greater than zero, Algorithm 1 (QANM) exhibits linear convergence while achieving significantly faster convergence compared to [12, Algorithm 1]. In another scenario involving node-dependent matrices P with momentum coefficient greater than zero, the results remain consistent with those in Fig. 1, and Algorithm 1 (QANM) maintains a significantly faster convergence rate compared to [12, Algorithm 1].

Future Directions

Future work will focus on extending the proposed algorithm to constrained optimization problems, as well as developing improved designs for scenarios where the current method fails to converge. The paper concludes that it has developed an accelerated and communication-efficient algorithm for unconstrained distributed optimization.

How it works

The core mechanism relies on combining two strategies: Nesterov momentum to mitigate zigzag behavior and a finite-time quantized averaging protocol for efficient consensus. The Nesterov momentum is incorporated through the look-ahead position calculation s[k]i = x[k]i + βi(x[k]i − x[k−1]i). This is followed by a gradient descent step z[k+1]i = s[k]i − α∇fi(s[k]i).

The second part involves Algorithm 2 (FTQAC), which operates between optimization steps k and k + 1. In this protocol, nodes maintain two variables representing their current value and an associated integer weight. When the weight exceeds one, the node partitions its value into multiple quantized segments of nearly equal magnitude, retaining the segment with the smallest value locally while transmitting others to neighbors or itself. This process is described as tokens performing random walks over the network, where values are equalized upon meeting at a node.

Key Theoretical Results

The convergence proof relies on several lemmas and theorems to establish the linear convergence rate. Lemma 1 proves that for each node at time step k ≥ 1, the inequality∥x[k]i − zˆ[k]∥ ≤ 2√d∆ holds. Lemma 2 establishes a bound on the difference between the look-ahead position and the actual position, showing that sˆ[k] − s[k]i ≤ β˜ m[k]i. Theorem 1 ultimately proves that Algorithm 1 (QANM) generates a sequence of points which satisfies∥x[k+1]i − x∗∥ + c∥x[k]i − x∗∥ ≤ dx[k]i − x∗ + cx[k−1]i − x∗ + O(∆).

Application Details

In the application section, the error e[k] is defined as e[k] = vuut 1 n Xn i=1∥x[k]i − x∗∥∥x[0]i − x∗. The simulation used a learning rate α = 0.12, and the dimension of each node’s state as d = 5. The quantization level was tested at two values, namely ∆ ∈ 1e−3, 1e−6. The results consistently show that Algorithm 1 (QANM) maintains a significantly faster convergence rate compared to [12, Algorithm 1] across all quantization levels ∆.

References

[4] M. Doostmohammadian, A. Aghasi, M. Pirani, E. Nekouei, H. Zarrabi, R. Keypour, A. I. Rikos, and K. H. Johansson “Survey of distributed algorithms for resource allocation over multi-agent systems” Annual Reviews in Control vol 59 p 100983 2025<ref:2604.16906#pg5>.

[7] W. Shi, Q. Ling, G. Wu, and W. Yin “Extra: An exact first-order algorithm for decentralized consensus optimization” SIAM Journal on Optimization vol 25 no 2 pp 944–966 2015<ref:2604.16906#pg8>.

[8] P. Neal, C. Eric, P. Borja, and E. Jonathan “Distributed optimization and statistical learning via the alternating direction method of multipliers” Foundations and Trends in Machine learning vol 3 no 1 pp 1–122 2011.

[9] X. Du, K.

1. This algorithm can perform accelerated distributed optimization over bandwidth-limited directed communication networks by integrating Nesterov momentum with a finite-time quantized averaging protocol. This enables faster convergence to a neighborhood of the optimal solution, achieving linear convergence under strong convexity and smoothness assumptions.

2. The system can guarantee finite-time exact agreement on the optimal value (ensuring that all nodes reach identical decision variables within a bounded number of iterations) by employing the Algorithm 2 (FTQAC) which ensures that after every D iterations, the nodes perform a max-min consensus procedure to evaluate a stopping condition.

3. The AI system can operate efficiently under severe communication constraints by utilizing compressed (quantized) messages, as detailed in the paper. This allows for communication-efficient operation where nodes exchange only quantized values over bandwidth-limited channels.

4. The algorithm can mitigate convergence instability caused by objective functions having significantly different curvature along different directions (the zigzag phenomenon) by incorporating Nesterov acceleration, which improves convergence from a standard gradient descent rate of O(1/k) to O(1/k 2).

5. For multi-dimensional target parameter estimation, the system can achieve superior performance compared to non-momentum baselines, as demonstrated by simulations showing clear acceleration benefits over nonmomentum baselines across two simulation scenarios.

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 momentum with a distributed finite-time quantized consensus protocol. Under strong convexity and smoothness assumptions, we show that our proposed algorithm converges linearly to a neighborhood of the optimal solution. Finally, we evaluate QANM on a distributed sensor-fusion problem. With each method's step size tuned separately, QANM exhibits the fastest initial error reduction among the tested methods, including QAGD, Acc-DNGD-SC, and MSDA. Comparisons with QAGD under the same quantized averaging framework illustrate the empirical benefit of momentum, while experiments at two quantization levels demonstrate quantization-dependent error floors.