Abstract: 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 extend much further.

This is a joint work with Aaditya Ramdas at CMU. Link to paper: https://arxiv.org/abs/2602.06545