Decentralized/dynamic stochastic optimization : variance reduction and performative control

Abstract

This thesis investigates innovative approaches to decentralized optimization and control problems for policy-dependent linear dynamical systems. We focus on modeling issues and analyze the convergence of proposed algorithms using mathematical optimization techniques. In the second chapter, we consider minimizing the decentralized finite-sum optimization over a network where each pair of neighboring agents is associated with a nonlinear proximity constraint. Due to the fast convergence and low computational burden, stochastic variance reduction methods have primarily been studied for finite-sum minimization problems. However, these algorithms did not consider the nonlinear constrained optimization problems. The proposed framework, which we call VQ-VR, is particularly well-suited for decentralized stochastic problems involving pairwise constraints that complicate the analysis of convergence rates. By leveraging insights from a novel Lyapunov function, we demonstrate that two specific instantiations of this framework achieve a sublinear convergence rate of O(1/K) in terms of expected cost suboptimality and constraint violations, where K is the number of iterations. Numerical results from two applications validate our theoretical findings and highlight improved computational efficiencies compared to existing methods. The third chapter presents the performative control framework, where the deployed policy influences the control s laystem’s dynamics. In the fourth chapter, the focus shifts to performative model predictive control, handling linear systems with policy-dependent additive disturbances and constraints on the terminal state. These control modes result in a policy-dependent system state data sequence with temporal correlations. We introduce performatively stable solutions for both control frameworks, outlining conditions for unique stable outcomes and examining the impact of system stability on solution existence. The stochastic algorithm that converges to the stable solution for performative control is proposed, with its non-asymptotic convergence rates analyzed and validated through numerical results.

Date of Award	2024
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Xuanyu CAO (Supervisor)