Discretized Distributed Optimization Over Dynamic Digraphs

Introduction

Distributed optimization is a cornerstone of modern multi-agent systems, where a collective of agents—such as robot swarms, sensor networks, or distributed servers—collaborates to minimize a global cost function. This global objective is typically the sum of individual local functions known only to each agent. To achieve a common goal, agents must exchange information over a communication network.

A significant hurdle in existing distributed algorithms is the reliance on bi-stochastic weight matrices. In such systems, the weights of incoming and outgoing links for every node must sum to exactly one. While manageable in static, wired environments, this requirement is impractical for dynamic digraphs (directed graphs). In mobile or volatile networks, a single dropped packet or a robot moving out of range breaks the bi-stochastic condition, often necessitating a computationally expensive "weight-redesign" phase that halts optimization. This paper proposes a new discrete-time algorithm designed to maintain convergence in these challenging, time-varying environments.

Methodology

The researchers introduce a discretized version of a continuous-time gradient-tracking model. The algorithm maintains two primary variables for each agent $i$:

1. $x_i$: The local estimate of the optimal state.
2. $y_i$: An auxiliary variable for gradient tracking, which allows agents to estimate the global gradient using only local data and neighbor communications.

Key Technical Innovations

• Weight-Balanced Relaxation: The proposed method relaxes the strict bi-stochastic requirement to a "weight-balanced" condition, where the sum of in-weights equals the sum of out-weights. This condition is significantly easier to maintain in dynamic settings; for instance, in symmetric undirected networks, losing a link naturally preserves this balance.
• Stability via Matrix Perturbation: Using matrix perturbation theory, the authors prove that the optimization dynamics can be viewed as perturbations of a standard consensus network. By bounding these perturbations, they ensure global stability.
• Euler Forward Discretization: The continuous-time model is translated into a practical discrete-time algorithm (Algorithm 1), making it suitable for implementation on low-cost microprocessors.

Experimental Evaluation: Distributed SVM

The algorithm's performance was evaluated using a Distributed Support Vector Machine (D-SVM) simulation. The task involved binary classification of 50 random data points in a 3D space, distributed across a 5-node network. Each node had access to only 80% of the training data.

To test robustness, the researchers simulated a "link failure" scenario. Mid-optimization, a bidirectional connection between two nodes was removed to determine if the algorithm could recover without a weight-redesign phase.

Expand

Source, p. 7

Results and Discussion

The simulation results confirmed that the proposed method is highly resilient to network changes. Unlike traditional bi-stochastic algorithms that would fail or require a restart, this method successfully reached the global optimum—matching the results of a centralized SVM—despite the link failure.

Expand

Source, p. 8

The paper provides explicit mathematical bounds (Equations 24 and 31) for the step-sizes. As long as the parameters stay within these bounds, the agents are guaranteed to reach a consensus on the optimal solution.

Key Insights

• Resilience to Packet Drops: The "weight-balanced" property allows optimization to continue seamlessly even when links are lost, a common occurrence in robotic swarms.
• Single Time-Scale Operation: The method avoids the "inner loop" of multiple consensus rounds per optimization step, leading to higher efficiency for real-time applications.
• Stability Trade-offs: There is a mathematical relationship between the gradient-tracking step-size ($\alpha$) and the sampling time-step ($\eta$). Aggressive gradient tracking requires more frequent network sampling to maintain stability.

Conclusion and Future Work

This research demonstrates that "weight-balanced" is a sufficient and more practical condition for distributed learning in mobile robotic swarms than stricter traditional conditions. While the paper proves convergence, deriving explicit bounds on the convergence rate remains a challenge for future work due to the complexity of the perturbation analysis. Additionally, future research will explore the impact of communication noise, quantization, and time-delays on the algorithm's performance.

@inproceedings{doostmohammadian2023discretized,
  author = {Mohammadreza Doostmohammadian and Wei Jiang and Muwahida Liaquat and Alireza Aghasi and Houman Zarrabi},
  title = {{Discretized Distributed Optimization Over Dynamic Digraphs}},
  booktitle = {IEEE Trans Autom. Sci. Eng},
  year = {2023},
}