Characterization of Excess Risk for Locally Strongly Convex Population Risk

Abstract

We establish upper bounds for the expected excess risk of models trained by proper iterative algorithms which approximate the local minima. Unlike the results built upon the strong globally strongly convexity or global growth conditions e.g., PL-inequality, we only require the population risk to be \emph{locally} strongly convex around its local minima. Concretely, our bound under convex problems is of order $\tilde{\cO}(1/n)$. For non-convex problems with $d$ model parameters such that $d/n$ is smaller than a threshold independent of $n$, the order of $\tilde{\cO}(1/n)$ can be maintained if the empirical risk has no spurious local minima with high probability. Moreover, the bound for non-convex problem becomes $\tilde{\cO}(1/\sqrt{n})$ without such assumption. Our results are derived via algorithmic stability and characterization of the empirical risk's landscape. Compared with the existing algorithmic stability based results, our bounds are dimensional insensitive and without restrictions on the algorithm's implementation, learning rate, and the number of iterations. Our bounds underscore that with locally strongly convex population risk, the models trained by any proper iterative algorithm can generalize well, even for non-convex problems, and $d$ is large.

arXiv commentThe first two authors contribute equally to this paper

References in corpus (21)

• Scikit-learn: Machine Learning in Python
• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Information-theoretic analysis of generalization capability of learning algorithms
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Escaping Saddles with Stochastic Gradients
• Theoretical Analysis of Auto Rate-Tuning by Batch Normalization
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Escaping Saddle Points in Constrained Optimization
• On the Local Minima of the Empirical Risk
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Toward Better Generalization Bounds with Locally Elastic Stability