Fast Rates for Empirical Risk Minimization of Strict Saddle Problems

Abstract

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.

References in corpus (1)

• The Power of Normalization: Faster Evasion of Saddle Points

Cited by in corpus (13)

• Generalization in Deep Learning
• Understanding Generalization through Visualizations
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Stability and Generalization of Learning Algorithms that Converge to Global Optima
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• The Landscape of Deep Learning Algorithms
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Understanding Generalization in Deep Learning via Tensor Methods
• SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
• Learning in Non-convex Games with an Optimization Oracle
• Smooth Sensitivity Based Approach for Differentially Private Principal Component Analysis
• Algorithmic Instabilities of Accelerated Gradient Descent
• Characterization of Excess Risk for Locally Strongly Convex Population Risk