Statistics Meets Nonconvex Optimization: Computational Efficiency and Uncertainty Quantification

Cong Ma – Princeton University


In recent years, there has been an explosion of interest in designing fast nonconvex optimization algorithms to solve statistical estimation and learning problems. However, in contrast to convex optimization that has become a real pillar of modern engineering, the theoretical foundations of nonconvex optimization are far from satisfactory, especially in terms of its computational and inferential properties. This talk will present two recent stories that advance our understanding of nonconvex statistical estimation. The first story is concerned with uncertainty quantification for nonconvex low-rank matrix completion. We develop a de-biased estimator — on the basis of a nonconvex estimator — that enables optimal construction of confidence intervals for the missing entries of the unknown matrix. The second story focuses on computational efficiency in solving the phase retrieval problem. Despite the nonconvexity of the natural least-squares formulation, gradient descent with random initialization finds its global solution within a logarithmic number of iterations. All of this is achieved via an integrated view of statistics and optimization.