CMI Seminar: Mateo Diaz

Though nonconvex optimization problems are NP-hard in general, simple iterative methods, e.g., subgradient descent, are broadly used and often highly successful in high-dimensional statistical estimation and machine learning problems. This talk describes a few settings where simple algorithms are provably convergent. In the first part of the talk, we discuss rapid local convergence guarantees for nonconvex formulations of low-rank matrix recovery problems, a problem family that includes phase retrieval, blind deconvolution, matrix completion, and robust PCA. Standard approaches for solving these problems use smooth penalty functions and often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension.

In contrast, we show that natural nonsmooth penalty formulations have two clear advantages: (1) they do not suffer from the same type of ill-conditioning, and (2) they are robust against noise and gross outliers. Consequently, we prove that off-the-shelf algorithms for nonsmooth optimization converge at a rapid dimension-independent rate when initialized close to the solution, even when the measurements are corrupted. In the second part of the talk, we turn to the question of global convergence to local minimizers of nonsmooth functions. Recent work has shown that stochastically perturbed gradient methods can efficiently find local minimizers of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms can find approximate local minimizers of the Moreau envelope at a controlled rate.