Statistical Learning and Optimal Decision Making under Uncertainty

Abstract

Recent years have witnessed an explosion of interest in designing statistical and decision making algorithms that are computationally efficient and statistically accurate, along with quantitative measures of uncertainty or risk. In this thesis, we make contribution towards this end for several widely encountered problems in statistics, machine learning, and data science. • Starting with estimation algorithms, we show that a principled convex program achieves near-optimal statistical accuracy for robust PCA (i.e., low-rank matrix estimation in the presence of noise, missing data and outliers). We also design an efficient gradient descent algorithm for computing the nonparametric MLE of Gaussian mixture models with provable convergence guarantees. • In terms of uncertainty quantification for estimation algorithms, under a spiked covariance model, we propose a novel approach for performing valid statistical inference for PCA, which enables computation of both confidence regions for the principal subspace and entrywise confidence intervals for the covariance matrix. • Finally, for decision making problems, we develop two efficient offline reinforcement learning algorithms, which cover both the single- and multi-agent case respectively, that achieves optimal sample complexity in finding optimal policy or Nash equilibrium. In addition, we also design an Isotonic Mechanism to enhance peer review in machine learning and artificial intelligence conferences. All of this is enabled by an integrated consideration of statistics, optimization, and decision theory, and requires bringing together tools from a broad spectrum of foundational areas including random matrix theory, high-dimensional probability, PDE, Riemannian geometry, stochastic process, and game theory.