Distributed Optimization with Imperfect Communication

Abstract

Distributed optimization over multi-agent systems has recently been a hot research topic. In distributed optimization, each agent only has access to its local cost function, and they cooperatively minimize the global cost function, which is the sum of all agents' local cost functions. There is no central coordination in distributed optimization; cooperation depends on information transmission among neighboring agents. Each agent does local computation based on the received information from its neighbors to seek the optimal value of the global function. Compared with centralized optimization, distributed optimization has many advantages, such as robustness, modularity, and scalability.

The information transmission over multi-agent systems is essential to realize the cooperation in distributed optimization methods. Most of the research literature proposes distributed optimization algorithms with a critical assumption that each agent can receive accurate information from its neighbors without transmission errors. However, the communication channels are imperfect and have different kinds of limitations in real-world applications. Technical limitations such as limited bit rates, communication noises, and communication delays should not be ignorable. Moreover, accurate information transmission requires massive communication burdens and high transmission expenses in a realistic scenario. Due to the technical limitations and the economic cost, it is reasonable to assume that each agent can only receive information with transmission errors from its neighbors. How to guarantee the convergence of distributed optimization algorithms with imperfect communication should be investigated for practical applications.

In this thesis, we consider limited bit rates, communication noises, time-triggered schemes, and communication delays in the information transmission process of distributed optimization. The main contributions of this thesis are summarized as follows:

The distributed mirror descent algorithm with adaptive quantization is proposed for distributed optimization over time-varying networks with limited communication capacity. The adaptive quantization method is based on the traditional uniform quantization, and only a finite number of bits will be transmitted among agents. The quantization mid-value and quantization interval size are updated adaptively at each iteration to satisfy the non-saturated property of the quantizer. The proposed adaptive quantization method helps to alleviate the quantized error asymptotically. Then, the convergence of the distributed mirror descent algorithm can be guaranteed.

The periodic dynamic quantization method is proposed for the distributed mirror descent algorithm. Unlike the adaptive quantizer, the proposed dynamic quantizer is constructed from the uniform quantizer by periodically updating the quantization mid-value and quantization interval size. Thus, the periodic dynamic quantization method requires less frequency of updating quantization parameters, reducing the expenses of designing the quantizer. Since the parameters of the quantizer are updated periodically, a control parameter is defined as a decreasing sequence to reduce the information loss caused by the quantizer. The parameters of the periodic dynamic quantizer are designed appropriately based on the control parameter and the step size for the non-saturated property of the quantizer. Moreover, sufficient conditions of the step size and the control parameter are provided to guarantee the convergence of the distributed mirror descent algorithm.

The distributed dual averaging algorithm with the two-time-scale approach is constructed for distributed optimization over time-varying networks with stochastic communication noises. In the proposed algorithm, one time-scale is used as the step size of the algorithm, while the other is used to eliminate the effect of communication noises. After comprehensive convergence analysis, the algorithm's expected and high probability convergence rates can be derived under a general condition on noises and appropriate choices of the two-time-scale approach.

The time-triggered scheme is developed for the distributed mirror descent algorithm with the two-time-scale approach (DMDA-TTS) to reduce the number of information transmission among agents. In the proposed time-triggered schemes, each agent periodically sends/receives information to/from its neighboring agents instead of at each iteration. Each agent will utilize the outdated information received at the last transmission time to update parameters if no information is received from its neighbors at some iteration. Unlike the traditional periodic transmission, the information transmission period can be designed as a non-decreasing sequence in the DMDA-TTS of this thesis. Besides the step size, the control parameter is proposed as the decreasing sequence to eliminate the effect of outdated information. The sufficient conditions of the step size, the control parameter, and the transmission period are provided to guarantee the convergence of DMDA-TTS. Then, the corresponding convergence rates are given for DMDA-TTS with different parameters. The economic cost of information transmission can be significantly lowered due to the reduced number of information transmission.

Many existing distributed optimization algorithms (DOAs) cannot be directly utilized to solve distributed optimization problems over the time-varying network with communication delays. A generic algorithm framework is constructed for DOAs to address this issue in this thesis. A set of slack parameters of each agent is designed to update adaptively to predict its future state. Then, slack parameters will be transmitted among agents to solve distributed optimization problems with communication delays. The proposed generic algorithm framework is expressed via pseudocode and can be used for many DOAs, such as the subgradient descent, mirror descent, and dual averaging algorithms. Moreover, the generic algorithm framework is extended for seeking Nash equilibrium of non-cooperative games with delays.

Date of Award	23 Jul 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wing Cheong Daniel HO (Supervisor)