Modern Martingale Methods: Theory and Applications
Martingale concentration is at the heart of sequential statistical inference. Due to their time-uniform concentration of measure properties, martingales allow re searchers 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 set tings. 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.
Funding
Optimal Scheduling of Parallelizable Jobs in Cloud Computing Environments
Directorate for Engineering
Find out more...CAREER: Online Multiple Hypothesis Testing: A Comprehensive Treatment
Directorate for Mathematical & Physical Sciences
Find out more...FAI: Advancing Fairness in AI with Human-Algorithm Collaborations
Directorate for Computer & Information Science & Engineering
Find out more...Collaborative Research: SaTC: CORE: Small: Foundations for the Next Generation of Private Learning Systems
Directorate for Computer & Information Science & Engineering
Find out more...AI Institute for Societal Decision Making (AI-SDM)
Directorate for Computer & Information Science & Engineering
Find out more...CAREER: New Frontiers of Private Learning and Synthetic Data
Directorate for Computer & Information Science & Engineering
Find out more...Graduate Research Fellowship Program (GRFP)
Directorate for Education & Human Resources
Find out more...Graduate Research Fellowship Program (GRFP)
Directorate for Education & Human Resources
Find out more...History
Date
2024-12-11Degree Type
- Dissertation
Department
- Computer Science
Degree Name
- Doctor of Philosophy (PhD)