Nonconvex Statistical Optimization

Abstract

Complex statistical models, combined with scalable computing architectures, are beginning to shed lights on the analysis of large, intricate, and noisy datasets. To glue these three components --- big data, big models, and big architectures --- we need a seamless integration of high-dimensional statistics and large-scale optimization. In this context, the high-level goal of this thesis is to develop a new generation of {\it statistical optimization} method and theory to address emerging challenges in data science and artificial intelligence.

In particular, {\it nonconvex} formulations of machine learning problems bring superior computational efficiency, statistical accuracy, and modeling flexibility. However, a gap separates theory from practice. On the one hand, nonconvex optimization heuristics often exhibit good empirical performance in practice. On the other hand, classical theory only characterizes the statistical accuracy of a hypothetical global optimum, which is computationally intractable to attain in the worst case. Such a gap between theory and practice prohibits us from designing efficient algorithms in a principled way. This thesis aims to answer the question: How should we develop nonconvex statistical optimization algorithms with provable guarantees?

In this thesis, we develop a new unified algorithmic framework that integrates the {\it global exploration} and {\it local exploitation} of the {\it latent convexity} induced by the randomness of data. Under such a framework, we propose two global exploration schemes, namely, {\it homotopy path following} and {\it tightening after relaxation}, in the two parts of this thesis, respectively. Combining the two global exploration schemes with model-specific local exploitation methods, we establish globally convergent and statistically optimal nonconvex statistical optimization algorithms correspondingly for two problems, namely, nonconvex $M$-estimation and sparse principal component analysis.