Data-Exchange-Efficient Decentralized Optimization and Learning with High Probability Convergence over Multi-Agent Systems

Decentralized optimization and learning (DOL) have emerged as powerful approaches for large-scale systems, with successful applications in diverse domains such as natural language processing, smart grids, and wireless networks. Unlike centralized methods, DOL enables agents to collaboratively optimize a global objective function using only their local data while exchanging information with neighboring agents. This decentralized framework offers several key advantages, including improved robustness, enhanced data privacy, and strong scalability.Data exchange among agents is critical to guarantee convergence in DOL. However, existing methods face two fundamental challenges: (1) excessively high data-exchange frequency, where agents exchange data at every iteration; and (2) large data-exchange volume, often due to the transmission of multiple complete high-dimensional variables. These issues create significant data-exchange overhead, limiting the scalability and practical deployment of DOL in bandwidth-constrained or resource-limited environments. This proposal aims to address these challenges by developing a unified framework for data-exchange-efficient DOL based on two complementary strategies:- Reducing data-exchange frequency;- Reducing data-exchange volume.The proposed approach supports heterogeneity in the number of local updates across agents and an increasing number of local updates over communication rounds, combined with appropriately designed step-size schemes, to reduce data-exchange frequency. It further introduces stochastic quantization methods and single-variable communication protocols to reduce data-exchange volume. The convergence behavior of the proposed methods will be rigorously analyzed to ensure robust performance across a range of decentralized scenarios.Furthermore, this proposal aims to establish new theoretical foundations and algorithms that offer strong convergence guarantees, with a particular focus on high probability convergence analysis. High probability guarantees provide stronger reliability by ensuring that algorithms perform well with overwhelming likelihood, rather than merely on average. Such guarantees are essential in safety-critical domains and practical scenarios with limited algorithm runtime, where expectation-based guarantees are often insufficient. The research outcomes will enhance the robustness, efficiency, and scalability of decentralized optimization and learning, providing a solid theoretical foundation for practical multi-agent systems.