A Unified Framework for Understanding Distributed Optimization Algorithms: System Design and its Applications

Abstract

More than ever before, technology advances across the spectrum have meant that we have individualized and decentralized access to data, resources, and human capital. The capability to utilize massively and distributedly generated data (e.g., personal shopping records) and distributed computation (e.g., fast smartphone processors) has simplified our lives, facilitated optimal resource allocation, and unlocked innovation across industries. Distributed algorithms play a central role in the optimal operation of distributed systems in many applications, such as machine learning, signal processing, and control. Significant research efforts have been devoted to developing and analyzing new algorithms for various applications. However, existing methods are still facing difficulties in using computational resources and distributed data safely and efficiently. The three major challenges in state-of-the-art distributed systems are 1) finding appropriate models to describe the resources and problems in the system, 2) developing a general approach to solving problems efficiently, and 3) ensuring participants' privacy. My thesis research focuses on building an algorithmic framework to resolve these fundamental and practical challenges. This thesis provides a fresh perspective to understand, analyze, and design distributed optimization algorithms. Through the lens of multi-rate feedback control, this thesis theoretically proves that a wide class of distributed algorithms, including popular decentralized and federated schemes, can be viewed as discretizing a certain continuous-time feedback control system, possibly with multiple sampling rates, while preserving the same convergence behavior. Further, the proposed system unifies the stochasticities in a wide range of distributed optimization algorithms as several types of noises injected into the control system, and provides a uniform convergence analysis to a class of distributed stochastic optimization algorithms. The control-based framework is applied to designing new algorithms in decentralized optimization and federated learning to meet different system requirements including achieving convergence, optimal performance, or meeting privacy concerns. In summary, this thesis establishes a control-based framework to understand, analyze, and design distributed optimization algorithms, with applications in decentralized optimization and federated learning algorithm design.