Skip navigation
Please use this identifier to cite or link to this item:
Title: Topics in the Statistical and Computational Complexities of Modern Machine Learning
Authors: Yang, Zhuoran
Advisors: FanLiu, JianqingHan
Contributors: Operations Research and Financial Engineering Department
Keywords: Deep Q-Learning
Gaussian Mixture Models
Markov Game
Reinforcement Learning
Statistical-Computational Tradeoff
Subjects: Statistics
Issue Date: 2022
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Yang_princeton_0181D_14037.pdf1.86 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.