Topics in the Statistical and Computational Complexities of Modern Machine Learning

Abstract

Modern machine learning methods feature a combination of complex statistical models and algorithms, scalable computing architectures, huge amounts of training data and computational resources. In particular, such a requirement of huge data and computational resources can be prohibitive in applications where data acquisition is costly or computation budget is limited. Thus, to democratize machine learning technology, it is pivotal to gain deeper insights into questions about data and computation. In this thesis, we aim to (a) delineate the fundamental limits involving statistical accuracy and computationally efficiency in heterogeneous statistical models, and (b) characterize the statistical and computational performances of reinforcement learning algorithms with neural network models. In Chapter 2, we study the fundamental tradeoffs between statistical accuracy and computational tractability in the analysis of high dimensional heterogeneous models including sparse Gaussian mixture model and mixture of sparse linear regressions. We exploit an oracle-based computational model to establish conjecture-free computationally feasible minimax lower bounds, which show that there exist significant gaps between computationally feasible minimax risks and classical ones. These gaps quantify the statistical price we must pay to achieve computational tractability in the presence of data heterogeneity. Furthermore, in Chapter 3, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN.