Abstract

I introduce novel concentration-of-measure bounds for the supremum deviation, several variance concepts, and a family of game-theoretic welfare functions. I then apply these bounds to analyze machine learning and data science problems, with deep theoretical consequences and impactful practical ramifications. Parts I and II assume an independently and identically distributed (i.i.d.) setting, where we observe many statistically independent occurrences, and part III extends some of my methods and themes to study non-i.i.d. mean estimation problems. Naturally, some conclusions are weaker in these relaxed settings, but I find that many of the same data-dependent and variance-sensitivity themes apply, and give efficient algorithms for real-world problems where the i.i.d. assumption is prohibitive.

This thesis is split into three parts, each representing a significant advancement in its respective field; the first in statistical learning theory, with an emphasis on algorithms and generalization guarantees making efficient use of training data; the second in the axiomatic underpinnings, practice, and statistical elements of fair machine learning; and the third in showing that themes and bounds from sampling problems in standard i.i.d. settings translate well into non-i.i.d. settings. Special attention is paid to keep each part independently readable, however the reader will better appreciate thematic connections, applications, and technical synergy when they are considered as a whole.

Concretely, I note that the methods of parts I and III are not mutually incompatible, opening the door to strong uniform convergence bounds in non-i.i.d. settings, and furthermore, the fair learning setting of part II benefits from the statistical bounds of part I, and similar analysis is possible in non-i.i.d. settings. Indeed, in a connected and interdependent world, it may be the case that practical fair systems need to consider the intricacies of non-i.i.d. learning. Ultimately, the importance of philosophically grounded and statistically rigorous fair-learning systems, operating on real-world data with all the messy dependence structures that may entail, seems to be not only of immense academic interest, but also a necessary step in joining the theory and practice of machine learning and its societal impact.

Three Parts of a Whole

• Part I: Concentration of Measure and Uniform Convergence in Machine Learning
• Chapter 1: Sharp Uniform Convergence Bounds through Empirical Centralization
• Chapter 2: Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees
• Part II: Fairness with Population Means: Malfare, Welfare, and Fair PAC Learning
• Chapters 3 & 5: An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
• Part III: Sample-Efficient Mean-Estimation with Dependent Sequential Data
• Chapter 7: Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE

• My dissertation was awarded the 2021 Joukowsky Outstanding Dissertation Prize in the physical sciences.
• On March 25, 2021, I successfully defended my thesis.
• On November 6, 2020, I passed my thesis proposal presentation.