Fast Rates for Empirical Risk Minimization of Strict Saddle Problems

Understand

We derive bounds on the sample complexity of empirical risk minimization (ERM) in the context of minimizing non-convex risks that admit the strict saddle property.

• Recent progress in non-convex optimization has yielded efficient algorithms for minimizing such functions.
• Our results imply that these efficient algorithms are statistically stable and also generalize well.
• In particular, we derive fast rates which resemble the bounds that are often attained in the strongly convex setting.