On Exact Computation with an Infinitely Wide Neural Net

Abstract

How well does a classic deep net architecture like AlexNet or VGG19 classify on a standard dataset such as CIFAR-10 when its width --- namely, number of channels in convolutional layers, and number of nodes in fully-connected internal layers --- is allowed to increase to infinity? Such questions have come to the forefront in the quest to theoretically understand deep learning and its mysteries about optimization and generalization. They also connect deep learning to notions such as Gaussian processes and kernels. A recent paper [Jacot et al., 2018] introduced the Neural Tangent Kernel (NTK) which captures the behavior of fully-connected deep nets in the infinite width limit trained by gradient descent; this object was implicit in some other recent papers. An attraction of such ideas is that a pure kernel-based method is used to capture the power of a fully-trained deep net of infinite width. The current paper gives the first efficient exact algorithm for computing the extension of NTK to convolutional neural nets, which we call Convolutional NTK (CNTK), as well as an efficient GPU implementation of this algorithm. This results in a significant new benchmark for the performance of a pure kernel-based method on CIFAR-10, being $10\%$ higher than the methods reported in [Novak et al., 2019], and only $6\%$ lower than the performance of the corresponding finite deep net architecture (once batch normalization, etc. are turned off). Theoretically, we also give the first non-asymptotic proof showing that a fully-trained sufficiently wide net is indeed equivalent to the kernel regression predictor using NTK.

In NeurIPS 2019. Code available: https://github.com/ruosongwang/cntk

References in corpus (18)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Neural Networks as Gaussian Processes
• 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
• Convolutional Kernel Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
• To understand deep learning we need to understand kernel learning
• SGD Learns the Conjugate Kernel Class of the Network
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Steps Toward Deep Kernel Methods from Infinite Neural Networks
• A Selective Overview of Deep Learning
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Learning Scalable Deep Kernels with Recurrent Structure
• Deep Gaussian Processes with Convolutional Kernels

Cited by in corpus (172)

• On the eigenvector bias of Fourier feature networks: From regression to solving multi-scale PDEs with physics-informed neural networks
• Machine Learning and Deep Learning -- A review for Ecologists
• Scaling description of generalization with number of parameters in deep learning
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• The Modern Mathematics of Deep Learning
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Automated Reinforcement Learning (AutoRL): A Survey and Open Problems
• Coresets via Bilevel Optimization for Continual Learning and Streaming
• Representation Learning via Quantum Neural Tangent Kernels
• The Global Landscape of Neural Networks: An Overview
• When Do Neural Networks Outperform Kernel Methods?
• Towards Understanding the Spectral Bias of Deep Learning
• Cycle Self-Training for Domain Adaptation
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Explicit Regularisation in Gaussian Noise Injections
• Understanding Self-supervised Learning with Dual Deep Networks
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Bayesian Deep Ensembles via the Neural Tangent Kernel
• Frequency Bias in Neural Networks for Input of Non-Uniform Density
• Multiple Descent: Design Your Own Generalization Curve
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Learning with Density Matrices and Random Features
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• On the training dynamics of deep networks with $L_2$ regularization
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Identification of new classical Be stars from the LAMOST MRS survey
• Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks
• Dataset Distillation with Infinitely Wide Convolutional Networks
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Wide and Deep Neural Networks Achieve Optimality for Classification
• CoinDICE: Off-Policy Confidence Interval Estimation
• Finite size corrections for neural network Gaussian processes
• Tensor Programs III: Neural Matrix Laws
• On Power Laws in Deep Ensembles
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Phase diagram for two-layer ReLU neural networks at infinite-width limit
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• FedLoc: Federated Learning Framework for Data-Driven Cooperative Localization and Location Data Processing
• Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics
• On the infinite width limit of neural networks with a standard parameterization
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• On the Neural Tangent Kernel of Deep Networks with Orthogonal Initialization
• Deep Graph Similarity Learning: A Survey
• Layer-wise Characterization of Latent Information Leakage in Federated Learning
• On the Similarity between the Laplace and Neural Tangent Kernels
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Limitations of Lazy Training of Two-layers Neural Networks
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• Order and Chaos: NTK views on DNN Normalization, Checkerboard and Boundary Artifacts
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Convex Geometry and Duality of Over-parameterized Neural Networks
• The Local Elasticity of Neural Networks
• Learning Deep Graph Representations via Convolutional Neural Networks
• Pathological spectra of the Fisher information metric and its variants in deep neural networks
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• The Normalization Method for Alleviating Pathological Sharpness in Wide Neural Networks
• Deep Active Learning by Leveraging Training Dynamics
• Classification Logit Two-sample Testing by Neural Networks
• Is SGD a Bayesian sampler? Well, almost
• On the Convergence and Calibration of Deep Learning with Differential Privacy
• Towards Understanding the Condensation of Neural Networks at Initial Training
• On Infinite-Width Hypernetworks
• Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics
• Label Noise SGD Provably Prefers Flat Global Minimizers
• Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• Implicit Rugosity Regularization via Data Augmentation
• The Recurrent Neural Tangent Kernel
• Shift Invariance Can Reduce Adversarial Robustness
• Sparse Orthogonal Variational Inference for Gaussian Processes
• Wide Neural Networks with Bottlenecks are Deep Gaussian Processes
• A Mean Field Theory of Quantized Deep Networks: The Quantization-Depth Trade-Off
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Why bigger is not always better: on finite and infinite neural networks
• A global convergence theory for deep ReLU implicit networks via over-parameterization
• Even your Teacher Needs Guidance: Ground-Truth Targets Dampen Regularization Imposed by Self-Distillation
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Deep frequency principle towards understanding why deeper learning is faster
• Increasing Depth Leads to U-Shaped Test Risk in Over-parameterized Convolutional Networks
• Approximation and Learning with Deep Convolutional Models: a Kernel Perspective
• Implicit Gradient Regularization
• Soft Mode in the Dynamics of Over-realizable On-line Learning for Soft Committee Machines
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Wide Neural Networks Forget Less Catastrophically
• Learning with Gradient Descent and Weakly Convex Losses
• Correlated Weights in Infinite Limits of Deep Convolutional Neural Networks
• A Deep Conditioning Treatment of Neural Networks
• On Random Kernels of Residual Architectures
• Is deeper better? It depends on locality of relevant features
• Any Target Function Exists in a Neighborhood of Any Sufficiently Wide Random Network: A Geometrical Perspective
• The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks
• Which Minimizer Does My Neural Network Converge To?
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Exploring the Uncertainty Properties of Neural Networks' Implicit Priors in the Infinite-Width Limit
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• On a Sparse Shortcut Topology of Artificial Neural Networks
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Improved generalization by noise enhancement
• Kernel-Based Smoothness Analysis of Residual Networks
• Learning with convolution and pooling operations in kernel methods
• Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
• Dynamically Stable Infinite-Width Limits of Neural Classifiers
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Analyzing Finite Neural Networks: Can We Trust Neural Tangent Kernel Theory?
• An analytic theory of shallow networks dynamics for hinge loss classification
• Infinite-channel deep stable convolutional neural networks
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• Embedding Principle of Loss Landscape of Deep Neural Networks
• Scaling Neural Tangent Kernels via Sketching and Random Features
• DNN-Based Topology Optimisation: Spatial Invariance and Neural Tangent Kernel
• Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• Are wider nets better given the same number of parameters?
• Pure Exploration in Kernel and Neural Bandits
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Learning curves for Gaussian process regression with power-law priors and targets
• The Bayesian Method of Tensor Networks
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• A priori generalization error for two-layer ReLU neural network through minimum norm solution
• Neural Tangent Kernel Empowered Federated Learning
• Properties of the After Kernel
• Dynamical transition in controllable quantum neural networks with large depth
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Uniform Convergence, Adversarial Spheres and a Simple Remedy
• Fast Adaptation with Linearized Neural Networks
• Quantifying Epistemic Uncertainty in Deep Learning
• Forward Operator Estimation in Generative Models with Kernel Transfer Operators
• Sequentially Aggregated Convolutional Networks
• Joint Text and Label Generation for Spoken Language Understanding
• Avoiding Kernel Fixed Points: Computing with ELU and GELU Infinite Networks
• Neural Optimization Kernel: Towards Robust Deep Learning
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks
• How isotropic kernels perform on simple invariants
• Recent Advances in Large Margin Learning
• Good Classifiers are Abundant in the Interpolating Regime
• Neural Path Features and Neural Path Kernel : Understanding the role of gates in deep learning
• Neural Contextual Bandits without Regret
• A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
• Statistical Mechanical Analysis of Neural Network Pruning
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• An Exploration into why Output Regularization Mitigates Label Noise
• New Insights into Graph Convolutional Networks using Neural Tangent Kernels
• Enhanced Recurrent Neural Tangent Kernels for Non-Time-Series Data
• Graph Neural Network for Large-Scale Network Localization
• Embedding Principle: a hierarchical structure of loss landscape of deep neural networks