AI & Fundamentals

Stochastic Approximation Algorithms with Decision-Dependent Data: The Case of Performative Prediction - Hoi-To Wai, Assistant Professor, CUHK

Abstract:

Stochastic approximation (SA) forms the foundation of numerous online decision-making algorithms under uncertainty. In recent years, it has garnered renewed interest in the dynamic environment setting where streaming data is not independent and identically distributed (i.i.d.), but rather correlated and/or decision-dependent. This resurgence of interest stems from its widespread application in contemporary domains, such as reinforcement learning, performative prediction, and fine-tuning of large language models (LLMs). This presentation focuses on SA algorithms applied to stochastic optimization problems with decision-dependent distributions, commonly referred to as the performative prediction problem(s). We will commence by motivating the problem through an illustrative example of strategic classification and demonstrate that a natural implementation of the “stochastic gradient” algorithm with “greedy deployment” yields an SA scheme that deviates from the stochastic gradient updates. Subsequently, we will present recent results on the convergence of such an algorithm under both convex and non-convex settings, as well as in stateful and non-stateful agent environments. Finally, we will illustrate several intriguing extensions of the model to encompass multi-agent learning, non-cooperative network games, and fine-tuning of LLMs.

Bio

Hoi-To Wai received his PhD degree from Arizona State University (ASU) in Electrical Engineering in Fall 2017, B. Eng. (with First Class Honor) and M. Phil. degrees in Electronic Engineering from The Chinese University of Hong Kong (CUHK) in 2010 and 2012, respectively. He is an Assistant Professor in the Department of Systems Engineering & Engineering Management at CUHK. He is also an Associate Editor for the IEEE Transactions on Signal and Information Processing over Networks, IEEE Transactions on Signal Processing, Elsevier’s Signal Processing. He has held research positions at ASU, UC Davis, Telecom ParisTech, Ecole Polytechnique, MIT. Hoi-To’s research interests are in the broad area of signal processing, machine learning and stochastic optimization. His dissertation has received the 2017’s Dean’s Dissertation Award from the Ira A. Fulton Schools of Engineering of ASU and he is a recipient of Best Student Paper Awards at ICASSP 2018, SAM 2024 (as a co-author).