Carnegie Mellon University
Browse

Modern Martingale Methods: Theory and Applications

Download (2.47 MB)
thesis
posted on 2025-03-18, 21:07 authored by Justin WhitehouseJustin Whitehouse

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-11

Degree Type

  • Dissertation

Department

  • Computer Science

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Aaditya Ramdas Zhiwei Steven Wu

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC