Algorithmic and Statistical Optimality for High-Dimensional Data

For high-dimensional data, two of the most important questions are the question of algorithmic optimality, which asks for the optimal algorithm within a certain class of computationally feasible procedures, and the question of statistical optimality, which asks for the optimal statistical procedure under a generating model. In this thesis the question of algorithmic optimality is investigated for the class of iterative thresholding algorithms on sparse and low rank structures under the framework of restricted optimality. The question of statistical optimality is investigated for the high-dimensional sparse changepoint detection problem and the contaminated density estimation problem under the minimax framework.