Andrea Montanari: The landscape of some statistical problems

Abstract:  Most high-dimensional estimation and prediction methods propose to minimize a cost function
(empirical risk) that is written as a sum of losses associated to each data point (each example).
Studying the landscape of the empirical risk is useful to understand the computational complexity
of these statistical problems. I will discuss some generic features that can be used to prove that the
global minimizer can be computed efficiently even if the loss in non-convex.

A different mechanism arises in some rank-constrained semidefinite programming problems. In this case,
optimization algorithms can only be guaranteed to produce an (approximate) local optimum, but all local
optima are close in value to the global optimum.

Finally I will contrast these with problems in which the effects of non-convexity are more dramatic.

[Based on joint work with Yu Bai, Song Mei, Theodor Misiakiewicz and Roberto Oliveira]