静5青年讲座 | Operationalizing Stein's Method for Online Linear Optimization

Stein's method is a classical "descriptive" framework in probability theory for proving quantitative versions of the central limit theorem (CLT). This talk introduces an algorithmic application of this framework in adversarial online linear optimization (OLO). Focusing on the special case of one-dimensional fixed-time OLO on a bounded domain, we present an algorithm based on Stein's method which is capable of achieving various "additively sharp" performance guarantees, surpassing the conventional big-O-optimal worst-case regret bounds. Furthermore, instantiations of this algorithm improve upon the total loss upper bounds of classical baselines, including online gradient descent (OGD) and multiplicative weight update (MWU). Conceptually, our algorithm can be viewed as a continuous refinement of a seminal dynamic programming algorithm of T. Cover (1966), while technically, our construction is inspired by the remarkably clean proof of a quantitative Wasserstein martingale CLT due to A. Röllin (2018). These results suggest an intriguing algorithmic relation between adversarial online learning and probabilistic limit theorems, whose applicability might be extended further. This is a joint work with Aaditya Ramdas at CMU.

Zhiyu Zhang is an assistant professor at the College of Control Science and Engineering at Zhejiang University. Previously he obtained his PhD from Boston University, and then did PostDoc at Harvard University and Carnegie Mellon University. His research focuses on algorithmic problems at the intersection of optimization, statistics and game theory, as well as downstream applications in GenAI and robotics.