On Exact Computation with an Infinitely Wide Neural Net
By Sanjeev Arora, Simon Shaolei Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang. 2019
1,059 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Large Language Models, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Ruslan Salakhutdinov
- Tengyu Ma
- Percy Liang
- Sergey Levine
- Quoc V. Le
- Mohit Bansal
- Yuanzhi Li
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Jitendra Malik
- Xiaogang Wang
- Andrew Zisserman
- Andrea Vedaldi
In Large Language Models
- Yuanzhi Li
- Greg Yang
- Zeyuan Allen-Zhu
- Lechao Xiao
- Yingyu Liang
- Simon Shaolei Du
- Aaron C. Courville
- Yoshua Bengio
In Scaling & Learning Theory
- Greg Yang
- Yuanzhi Li
- Zeyuan Allen-Zhu
- Jason D. Lee
- Simon Shaolei Du
- Tengyu Ma
- Quanquan Gu
- Lechao Xiao
Citations in the corpus
- Scaling description of generalization with number of parameters in deep learning (2019, background): “In particular, recent works on the over-parametrized regime of DNNs [20, 21, 22, 23] have shown that the landscape around a typical initialization point becomes essentially convex, allowing for convergence to a global minimum during training.”
- The large learning rate phase of deep learning: the catapult mechanism (2020, background): “Prior work has focused on comparisons between various infinitewidth kernels associated with deep networks and their finite-width, SGD-trained counterparts (Lee et al., 2018; Novak et al., 2019; Arora et al., 2019).”
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “Another line of work has identified that deep linear networks gradually increase the rank during training [Arora et al., 2019a, Saxe et al., 2014, Lampinen and Ganguli, 2018, Gidel et al., 2019].”
- When do neural networks outperform kernel methods? (2020, background): “RKHS behave well on certain image classification tasks [4, 21, 24], and this seems to contradict the previous point.”
- What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, methodology): “For example, ResNet achieves 96% test accuracy on the CIFAR-10 data set, but NTKs achieve 77% [6] and random feature kernels achieve 85% [29].”
- Wide Neural Networks Forget Less Catastrophically (2021, background): “, 2020), we study how the width of the network affects the continual learning performance – aligned with the recent research on infinite width networks and Neural Tangent Kernel (NTK) regime (Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019; Chizat et al., 2019).”
- A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix (2020, methodology): “[2017], memory-based and projection methods [Chaudhry et al., 2018, Lopez-Paz and Ranzato, 2017, Farajtabar et al., 2020] or parameters isolations [Mallya and Lazebnik, 2018, Rosenfeld and Tsotsos, 2018]. In Pan et al. [2020], the authors propose a method to identify memorable example from the past ”
- Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, methodology): “We solve the coreset selection for KRR using the RBF kernel with γ = 10 − 5 (found by validation), and CNTK proposed in [3] with 6 layers and global average pooling, with normalization.”
- On Lazy Training in Differentiable Programming (2018, background): “Note that [3] reports a test accuracy of 77.”
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, methodology): “” There is also a line of work studying the relationship between neural networks and NTKs (neural tangent kernels) [3, 4, 7, 27, 31, 51].”
- Neural Tangents: Fast and Easy Infinite Neural Networks in Python (2019, background): “…kernels (Garriga-Alonso et al., 2019; Novak et al., 2019; Arora et al., 2019a), and by their ability to match or exceed the performance of finite width networks in some situations, especially for fully-and locally-connected model families (Lee et al., 2018; Novak et al., 2019; Arora et al., 2019b).”
- Enhanced Convolutional Neural Tangent Kernels (2019, methodology): “• Finally, for CNTK, when c = 0 (no pooling layer) and c = 32 (GAP) our reported test accuracies are close to those in Arora et al. (2019) on CIFAR-10. For CNN-GP, when c = 0 (no pooling layer) our reported test accuracies are close to those in Novak et al. (2019) on CIFAR-10 and Fashion-MNIST.”
- FedLoc: Federated Learning Framework for Data-Driven Cooperative Localization and Location Data Processing (2020, methodology): “Lately, the arc-cosine kernel [58], the neural tangent kernel (NTK) [67], and the convolutional neural tangent kernel (CNTK) [68] were developed to mimic a DNN with infinite width.”
- Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “2 With huge non-convexity obstacles, existing theoretical works, to the best of our knowledge, have only been able to demonstrate that multi-layer neural networks can efficiently perform learning tasks that are already known solvable by non-hierarchical methods, such as kernel methods [3, 6, 7, 9, 1”
- Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “For this same setting, Daniely [17], Du et al. [22, 21], Jacot et al. [31], Arora et al. [6, 5] make this connection explicit by establishing that the prediction function found by gradient descent is in the span of the training data in a reproducing kernel Hilbert space (RKHS) induced by the Neural…”
- Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks (2019, methodology): “Theoretically, a line of work study the optimization and generalization behavior of ultra-wide NNs (Allen-Zhu et al., 2018b,a; Arora et al., 2019b; Du et al., 2018b,a; Li & Liang, 2018; Zou et al., 2018; Yang, 2019; Cao & Gu, 2019a,b).”