PRiML Seminar: “Nonconvex Optimization Meets Statistics: A Few Recent Stories”

Recent years have seen a flurry of activity in solving statistical estimation and learning problems via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. This talk presents two recent stories about nonconvex statistical estimation, which highlight the important role of statistical models in enabling efficient nonconvex optimization. The first story is about randomly initialized nonconvex methods for a phase retrieval problem: even without careful initialization, simple algorithms like gradient descent provably find the global solution within a logarithmic number of iterations. The second story is concerned with uncertainty quantification for nonconvex low-rank matrix completion. We develop a de-biased estimator — on the basis of a nonconvex estimate — that enables optimal construction of confidence intervals for the missing entries of the unknown matrix. All of this is achieved via a leave-one-out statistical analysis framework, which is very powerful in handling and decoupling complicated statistical dependency.