Can Non-Convex Optimization Be Robust?

Explore the challenges and possibilities of robust non-convex optimization in this 46-minute lecture by Rong Ge from Duke University. Delve into the reasons behind the perceived ease of non-convex optimization, examine locally optimizable functions, and investigate the consequences of failed assumptions. Learn about robust non-convex optimization techniques using perturbed objectives, and understand the motivation behind comparing empirical risk to population risk. Discover the concept of smoothing and its properties, as well as ideas for establishing lower bounds. Examine matrix completion, semi-random adversaries, and counter-examples. Gain insights into preprocessing techniques and conclude with a summary of key points and open problems in the field of robust and high-dimensional statistics.

Intro
Why is non-convex optimization "easy"?
Locally optimizable functions
What happens when assumptions fail?
Robust non-convex optimization with perturbed objective
Motivation: Empirical Risk vs. Population Risk.
Idea: Smoothing
Properties of Smoothing
Ideas of the Lower Bound
Matrix Completion
Semi-Random Adversary
Counter Examples
Preprocessing
Summary
Open Problems