Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
This work addresses statistical guarantees for non-convex optimization in machine learning, though it appears incremental as it builds on existing strict saddle property frameworks.
The paper tackles the sample complexity of empirical risk minimization for non-convex risks with the strict saddle property, showing that efficient algorithms for such problems are statistically stable and generalize well, with fast rates similar to strongly convex settings, as applied to Principal Component Analysis and Independent Component Analysis.
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. We specify our bounds to Principal Component Analysis and Independent Component Analysis. Our results and techniques may pave the way for statistical analyses of additional strict saddle problems.