Robust estimation via generalized quasi-gradients

Understand

We explore why many recently proposed robust estimation problems are efficiently solvable, even though the underlying optimization problems are non-convex.

• We study the loss landscape of these robust estimation problems, and identify the existence of "generalized quasi-gradients".
• Whenever these quasi-gradients exist, a large family of low-regret algorithms are guaranteed to approximate the global minimum; this includes the commonly-used filtering algorithm.
• For robust mean estimation of distributions under bounded covariance, we show that any first-order stationary point of the associated optimization problem is an {approximate global minimum} if and only if the corruption level $\epsilon < 1/3$.