What Can ResNet Learn Efficiently, Going Beyond Kernels?

By Zeyuan Allen-Zhu, Yuanzhi Li. 2019

200 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures, Statistical 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

In Computer Vision and Pattern Recognition

In Model Architectures

In Statistical Learning Theory

Citations in the corpus

LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “In theory literature, it is known that neural networks outperform other classical learning methods, including the corresponding (finite-width) neural tangent kernels [5, 22] when the underlying concept class has certain low-rank structure [2, 3, 11].”
When do neural networks outperform kernel methods? (2020, background): “target functions f∗ that can be represented and possibly efficiently learnt using neural networks, but not in the corresponding RKHS [32, 6, 17, 16, 1, 2].”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, methodology): “This also prevents [2] from going beyond L = 3 layers; our result in this paper holds for every L ≥ 3, demonstrating that going deeper in the hierarchy can actually have consistent advantage.”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “Suzuki (2018); Allen-Zhu and Li (2019); Yehudai and Shamir (2019) demonstrated that neural network outperforms linear estimators (including kernel methods) in learning various target functions.”
Towards Understanding the Spectral Bias of Deep Learning (2019, result): “Therefore, our results share certain common limitations of NTK-type results discussed in (Chizat et al., 2019; Allen-Zhu and Li, 2019).”
Neural Contextual Bandits with UCB-based Exploration (2019, methodology): “This suggests that using deep neural networks to predict the reward function is better than using a ﬁxed feature mapping associated with the Neural Tangent Kernel, which mirrors similar ﬁndings in supervised learning (Allen-Zhu & Li, 2019).”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, background): “Finally, Li et al. (2019) showed how a combination of large learning rate and injected noise ampliﬁes the regularization from the noise and outperforms the NTK of the corresponding architecture.”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “The recent advance in deep learning [5, 6] that extends the study of two-layer neural networks [44, 68, 73, 35, 67, 70, 25, 79, 53, 24, 50, 72, 22, 78, 47, 49] might make this direction a not-so-remote goal.”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “(2.2) Correspondingly, the population loss of fP(x) is given as L∞(P) =c0 ∥ ∥ ∥ ∥ ∥ E w∼P ‖w‖2 − d ∑ i ai ∥ ∥ ∥ ∥ ∥ 2 F + c1 ∥ ∥ ∥ ∥ E w∼P w‖w‖2 ∥ ∥ ∥ ∥ 2 F + c2 ∥ ∥ ∥ ∥ ∥ E w∼P w⊗2 − d ∑ i=1 aieie ⊤ i ∥ ∥ ∥ ∥ ∥ 2 F + ∑ j≥2 c2j ∥ ∥ ∥ ∥ ∥ E w∼P w⊗2 ⊗ w̄⊗(2j−2) − d ∑ i=1 aie ⊗2j i ∥ ∥ ∥ ∥ ∥ 2 F .”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, background): “…nearest neighbor search is very standard in literature (Arya & Mount, 1993; Indyk & Motwani, 1998a; Datar et al., 2004; Andoni et al., 2014; 2015; Andoni & Razenshteyn, 2015; Indyk & Wagner, 2018; Andoni et al., 2017; 2018; Dong et al., 2019; Chen et al., 2020b; Li & Li, 2022; Li et al., 2019).”