Lei Xu

Topic

Distributed Nonconvex Optimization Algorithms with Compressed Communication

Department of Mechanical Engineering

Date & location

• Monday, August 21, 2025

• 4:00 P.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Yang Shi, Department of Mechanical Engineering, University of Victoria (Supervisor)

• Dr. Daniela Constantinescu, Department of Mechanical Engineering, UVic (Member)

• Dr. Jianping Pan, Department of Computer Science, UVic (Outside Member) 

External Examiner

• Dr. Yongqiang Wang, Department of Electrical and Computer Engineering, Clemson University 

Chair of Oral Examination

• Dr. Pablo Restrepo Gautier, School of Languages, Linguistics and Cultures, UVic

   

Abstract

In recent years, distributed optimization has received considerable attention and has been applied in power systems, sensor networks, and machine learning. In distributed optimization, each network agent performs local computations based on its own information exchanged with neighboring agents through a communication net work, with the collective goal of optimizing a global objective. Although various distributed optimization algorithms have been developed, most of them are tailored to distributed convex optimization. However, in many practical applications, the cost function is inherently nonconvex. Moreover, distributed optimization algorithms involve data spread across multiple agents, thereby requiring each agent to communicate with its neighbors. However, one of the main challenges is the communication bottleneck, which can occur owing to limited channel bandwidth or communication power. These challenges motivate the development of distributed nonconvex optimization algorithms with compressed communication. This dissertation addresses three concrete scenarios within this domain and proposes a distinct algorithm for each, supported by rigorous convergence guarantees.

Chapter 1 provides an overview of distributed optimization, covering recent advances under both exact and compressed communication settings, along with a review of the relevant literature. Chapter 2 introduces the notation and reviews key concepts that are used throughout this dissertation. In Chapter 3, we investigate the problem of distributed nonconvex optimization with compressed communication. To solve this problem, we propose three compressed distributed nonconvex optimization algorithm s, each integrating the distributed gradient tracking method with a different type of general compression operator: compressors with bounded relative compression error, compressors with globally bounded absolute compression error, and compressors with locally bounded absolute compression error. We then design several novel Lyapunov functions to establish that the proposed algorithms converge to a stationary point at a rate of O(1 T), where T is the total number of iterations and all local cost functions are assumed to be smooth. Moreover, under the additional assumption that the global cost function satisfies the Polyak-Lojasiewicz (P-L) condition, we prove that the proposed algorithms achieve linear convergence to a global optimum.

Chapter 4 investigates the problem of distributed nonconvex optimization in settings with compressed communication and without access to explicit gradient in formation. To solve this problem, we propose a stochastic zeroth-order compressed gradient tracking algorithm that integrates a random gradient estimator with the compressed gradient tracking algorithm. When the local cost functions are smooth and satisfy a state-dependent gradient variance condition, we establish that the proposed algorithm sublinearly converges to a stationary point at a rate of O(1 T) without the PL condition, and converges to a global optimum at a rate of O(1 T) under the PL condition. Moreover, if the state-dependent gradient variance satis es a relative second-moment bound, the convergence rate can be further improved to O(1 T) without the P-L condition, and to a linear rate under the PL condition.

Chapter 5 investigates the problem of distributed nonconvex optimization over unbalanced directed graphs without access to explicit gradient information. To address this problem, we develop a deterministic zeroth-order compressed push-pull algorithm by integrating a deterministic gradient estimator and compressors with bounded relative compression error into the push-pull method. We establish that the proposed algorithm converges sublinearly to a stationary point at a rate of O(1 T) when the local cost functions are smooth. Moreover, if the global cost function satisfies the PL condition, the algorithm achieves linear convergence to a global optimum. Finally, Chapter 6 presents concluding remarks and outlines potential directions for future research.