What Can ResNet Learn Efficiently, Going Beyond Kernels?

Abstract

How can neural networks such as ResNet efficiently learn CIFAR-10 with test accuracy more than 96%, while other methods, especially kernel methods, fall relatively behind? Can we more provide theoretical justifications for this gap? Recently, there is an influential line of work relating neural networks to kernels in the over-parameterized regime, proving they can learn certain concept class that is also learnable by kernels with similar test error. Yet, can neural networks provably learn some concept class BETTER than kernels? We answer this positively in the distribution-free setting. We prove neural networks can efficiently learn a notable class of functions, including those defined by three-layer residual networks with smooth activations, without any distributional assumption. At the same time, we prove there are simple functions in this class such that with the same number of training examples, the test error obtained by neural networks can be MUCH SMALLER than ANY kernel method, including neural tangent kernels (NTK). The main intuition is that multi-layer neural networks can implicitly perform hierarchical learning using different layers, which reduces the sample complexity comparing to "one-shot" learning algorithms such as kernel methods. In a follow-up work [2], this theory of hierarchical learning is further strengthened to incorporate the "backward feature correction" process when training deep networks. In the end, we also prove a computation complexity advantage of ResNet with respect to other learning methods including linear regression over arbitrary feature mappings.

arXiv commentV2 slightly improves lower bound, V3 strengthens experiments and adds citation to "backward feature correction" which is an even stronger form of hierarchical learning [2]

References in corpus (21)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Do CIFAR-10 Classifiers Generalize to CIFAR-10?
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Convergence Rate of Training Recurrent Neural Networks
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Diverse Neural Network Learns True Target Functions
• Theoretical properties of the global optimizer of two layer neural network
• Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case

Cited by in corpus (37)

• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• When Do Neural Networks Outperform Kernel Methods?
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Towards Understanding the Spectral Bias of Deep Learning
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Neural Thompson Sampling
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Mathematical Models of Overparameterized Neural Networks
• Identification of new classical Be stars from the LAMOST MRS survey
• Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• When Does Preconditioning Help or Hurt Generalization?
• Learning Parities with Neural Networks
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• The Local Elasticity of Neural Networks
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• Global Convergence of SGD On Two Layer Neural Nets
• On the Provable Generalization of Recurrent Neural Networks
• Properties of the After Kernel
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Learning Boolean Circuits with Neural Networks
• Nonparametric Learning of Two-Layer ReLU Residual Units
• The staircase property: How hierarchical structure can guide deep learning
• A class-driven hierarchical ResNet for classification of multispectral remote sensing images
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Neural Optimization Kernel: Towards Robust Deep Learning
• One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks