Why some robust estimators are efficiently computable?

Recent advances of computational robust statistics have produced efficient estimators with provable near-optimal statistical guarantees for a variety of problems. These estimators often involve non-convex optimization, and it is not clear why these non-convex problems are efficiently solvable, but many classical non-convex formulations are not. We make an attempt to answer this question, unify the majority of estimators in the literature, extend it to new problems, and obtain better performance guarantees.

It is based on joint work with Banghua Zhu and Jacob Steinhardt.