**Speaker:** Yuxin Chen, Princeton University

**Title:** Random initialization and
implicit regularization in nonconvex statistical estimation

**Abstract:** Recent
years have seen a flurry of activities in designing provably efficient nonconvex procedures
for solving statistical estimation / learning problems. Due to the highly nonconvex nature
of the empirical loss, state-of-the-art procedures often require suitable initialization and
proper regularization (e.g. trimming, regularized cost, projection) in order to
guarantee fast convergence. For vanilla procedures such as gradient descent,
however, prior theory is often either far from optimal or completely
lacks theoretical guarantees.

This talk is concerned
with a striking phenomenon arising in two nonconvex problems (i.e.
phase retrieval and matrix completion): even in the absence of
careful initialization, proper saddle escaping, and/or explicit
regularization, gradient descent converges to the optimal solution within a
logarithmic number of iterations, thus achieving near-optimal statistical and
computational guarantees at once. All of this is achieved by exploiting the
statistical models in analyzing optimization algorithms, via a leave-one-out
approach that enables the decoupling of certain statistical dependency between
the gradient descent iterates and the data. As a byproduct, for noisy matrix
completion, we demonstrate that gradient descent achieves near-optimal entrywise error control.