Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods

Abstract

Establishing a theoretical analysis that explains why deep learning can outperform shallow learning such as kernel methods is one of the biggest issues in the deep learning literature. Towards answering this question, we evaluate excess risk of a deep learning estimator trained by a noisy gradient descent with ridge regularization on a mildly overparameterized neural network, and discuss its superiority to a class of linear estimators that includes neural tangent kernel approach, random feature model, other kernel methods, $k$-NN estimator and so on. We consider a teacher-student regression model, and eventually show that any linear estimator can be outperformed by deep learning in a sense of the minimax optimal rate especially for a high dimension setting. The obtained excess bounds are so-called fast learning rate which is faster than $O(1/\sqrt{n})$ that is obtained by usual Rademacher complexity analysis. This discrepancy is induced by the non-convex geometry of the model and the noisy gradient descent used for neural network training provably reaches a near global optimal solution even though the loss landscape is highly non-convex. Although the noisy gradient descent does not employ any explicit or implicit sparsity inducing regularization, it shows a preferable generalization performance that dominates linear estimators.

arXiv comment21 pages

References in corpus (6)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Concentration inequalities and asymptotic results for ratio type empirical processes
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• When Do Neural Networks Outperform Kernel Methods?
• Duality in refined Sobolev-Malliavin spaces and weak approximations of SPDE

Cited by in corpus (3)

• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
• When Does Preconditioning Help or Hurt Generalization?