Justin Alexander Whitehouse

Modern Martingale Methods: Theory and Applications Degree Type: CS
Advisor(s): Zhiwei Steven Wu, Aaditya Ramdas
Graduated: December 2024

Abstract:

Martingale concentration is at the heart of sequential statistical inference. Due to their time-uniform concentration of measure properties, martingales allow researchers to perform inference on highly correlated data as it is adaptively collected over time. Many state-of-the-art results in areas such as differential privacy, multi-armed bandit optimization, causal inference, and online learning boil down to (a) finding an appropriate, problem-dependent martingale and (b) carefully bounding its growth. Despite the important roles martingales and time-uniform concentration of measure play in modern statistical tasks, applications of martingale concentration is typically ad-hoc. Often, poorly chosen martingale concentration inequalities are applied, which results in suboptimal, even vacuous rates in sequential estimation problems.

The focus of this thesis is twofold. In the first part of this thesis, we provide simple yet powerful frameworks for constructing time-uniform martingale concentration inequalities in univariate, multivariate, and even sometimes infinite-dimensional settings. The inequalities contained herein can be applied to processes with both light-tailed and heavy-tailed increments, and follow from simple geometric arguments. The second part of this thesis is focused on applying martingale methods and time-uniform martingale concentration to practically relevant data science tasks. In particular, we show that, by appropriately applying martingale concentration, one can obtain salient improvements over the state-of-the-art in both differentially private machine learning and kernel bandit optimization tasks. In sum, the hope is to give a reader a start to finish view of how to derive and apply time-uniform martingale concentration in modern statistical research.

Thesis Committee:
Zhiwei Steven Wu (Co-chair)
Aaditya Ramdas (Co-chair)
Weina Wang
Aarti Singh
Csaba Szepesvári (University of Alberta)
Emilie Kaufmann (Université de Lille)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Applied Probability, Machine Learning, Martingale Methods, Sequential Inference, Online Learning, Differential Privacy