ONLINE LEARNING, UNIFORM CONVERGENCE, AND A THEORY OF INTERPRETABILITY

This doctoral thesis covers various aspects of theoretical machine learning relative to two of its most fundamental paradigms: batch learning and online learning. In particular, we address the role of feedback models for multiple online learning problems, the sample complexity for uniform convergence, and a learning-theoretic approach to interpretable machine learning. First, we focus on online learning and investigate variants of the multi-armed bandit problem, including settings with feedback graphs, expert advice, and delayed feedback. We improve bounds on the minimax regret for undirected, strongly observable feedback graphs and develop nearly optimal algorithms for directed, stochastic feedback graphs without prior information on the distribution of the graphs. Additionally, we derive improved regret bounds for bandits with expert advice and explore the impact of intermediate observations in the delayed feedback setting, designing a meta-algorithm to achieve near-optimal regret which shows a reduced effect of the total delay. Second, we study the uniform convergence property of real-valued function classes with finite fat-shattering dimension. We provide an improved bound on the sample complexity of uniform convergence, closing the gap with existing lower bounds. Finally, regarding interpretability, we establish a taxonomy for approximating complex binary concepts with interpretable models such as shallow decision trees. Leveraging uniform convergence for Vapnik-Chervonenkis classes and von Neumann's minimax theorem, we achieve a surprising trichotomy for interpretable concepts while revealing connections between interpretable approximations and boosting.