Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks

Abstract

Recent theoretical work has established connections between over-parametrized neural networks and linearized models governed by he Neural Tangent Kernels (NTKs). NTK theory leads to concrete convergence and generalization results, yet the empirical performance of neural networks are observed to exceed their linearized models, suggesting insufficiency of this theory. Towards closing this gap, we investigate the training of over-parametrized neural networks that are beyond the NTK regime yet still governed by the Taylor expansion of the network. We bring forward the idea of \emph{randomizing} the neural networks, which allows them to escape their NTK and couple with quadratic models. We show that the optimization landscape of randomized two-layer networks are nice and amenable to escaping-saddle algorithms. We prove concrete generalization and expressivity results on these randomized networks, which lead to sample complexity bounds (of learning certain simple functions) that match the NTK and can in addition be better by a dimension factor when mild distributional assumptions are present. We demonstrate that our randomization technique can be generalized systematically beyond the quadratic case, by using it to find networks that are coupled with higher-order terms in their Taylor series.

arXiv commentPublished at ICLR 2020

References in corpus (24)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• 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
• Characterizing Implicit Bias in Terms of Optimization Geometry
• The loss surface of deep and wide neural networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Stronger generalization bounds for deep nets via a compression approach
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Limitations of Lazy Training of Two-layers Neural Networks

Cited by in corpus (10)

• A Theoretical Analysis of Deep Q-Learning
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• How Important is the Train-Validation Split in Meta-Learning?
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Dynamically Stable Infinite-Width Limits of Neural Classifiers
• Provable Regret Bounds for Deep Online Learning and Control
• Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
• Towards a General Theory of Infinite-Width Limits of Neural Classifiers
• Understanding Deflation Process in Over-parametrized Tensor Decomposition