Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels
Authors: Stefani Karp
Ezra Winston
Yuanzhi Li
Aarti Singh
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep learning theory
neural networks
kernels

Abstract: Neural networks have been shown to outperform kernel methods in practice (including neural tangent kernels). Most theoretical explanations of this performance gap focus on learning a complex hypothesis class; in some cases, it is unclear whether this hypothesis class captures realistic data. In this work, we propose a related, but alternative, explanation for this performance gap in the image classification setting, based on finding a sparse signal in the presence of noise. Specifically, we prove that, for a simple data distribution with sparse signal amidst high-variance noise, a simple convolutional neural network trained using stochastic gradient descent learns to threshold out the noise and find the signal. On the other hand, the corresponding neural tangent kernel, with a fixed set of predetermined features, is unable to adapt to the signal in this manner. We supplement our theoretical results by demonstrating this phenomenon empirically: in CIFAR-10 and MNIST images with various backgrounds, as the background noise increases in intensity, a CNN's performance stays relatively robust, whereas its corresponding neural tangent kernel sees a notable drop in performance. We therefore propose the "local signal adaptivity" (LSA) phenomenon as one explanation for the superiority of neural networks over kernel methods.

Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels
Stefani Karp
Ezra Winston
Carnegie Mellon University and Google Research shkarpocs cmu. edu
Carnegie Mellon University ewinston@cs cmu edu
Yuanzhi
Aarti Singh
Carnegie Mellon University yuanzhi1@cs. cmu. edu
Carnegie Mellon University aarti@cs. cmu edu
Abstract
Neural networks have been shown to outperform kernel methods in practice (includ- ing neural tangent kernels). Most theoretical explanations of this performance gap focus on learning a complex hypothesis class; in some cases, it is unclear whether this hypothesis class captures realistic data. In this work, we propose related, but alternative, explanation for this performance gap in the image classification setting, based on finding sparse signal in the presence of noise. Specifically, we prove that, for a simple data distribution with sparse signal amidst high-variance noise, simple convolutional neural network trained using stochastic gradient descent simultaneously learns to threshold out the noise and find the signal. On the other hand, the corresponding neural tangent kernel, with fixed set of predetermined features, is unable to adapt to the signal in this manner. We supplement our theo- retical results by demonstrating this phenomenon empirically: CIFAR- 10 and MNIST images with various backgrounds, as the background noise increases in intensity, CNN's s performance stays relatively robust, whereas its corresponding neural tangent kernel sees a notable drop in performance. We therefore propose the local signal adaptivity (LSA) phenomenon as one explanation the superiority neural networks over kernel methods.
Introduction
Recently, deep learning (using multi-layer, non-linear neural networks) has demonstrated superior performance over traditional linear learners many machine learning tasks. These achievements have bred much theoretical investigation into whether neural networks are, in fact, superior and why. On the one hand, the Neural Tangent Kernel (NTK) and derivative works show that, under certain (limiting) conditions, gradient-descent-ti trained neural network reduces to kernel method with specific architecture- and initialization initaalzzation-deeemmneed determined kernel [Jacot et al., 2018 Du et al.) 2019). However, this does not seem to be the full story, as it fails to capture the feature learning aspect of neural network training. This distinction between a fixed feature representation and a data-adaptive feature representation has been studied from variety of perspectives. including the lazy vs. active regime framework [Chizat et al., 2019. Woodworth et al. 2020, Moroshko al.) 20200] Geiger et al. 2020, Wang et al.) 2020]. Building these insights, there has been increasing interest in now showing a provable gap between the performance of neural networks and kernel methods in
various settings [Ghorbani et al. 2019 2020 Allen Zhu and Li 2019 2020
Li et al. 2020b Malach
al. 202T] Kamath et al. 2020
Refinetti et 2021 Daniely and Malach 2020 Chen ct al 2020
2021
Domingo-Enrich et al. 2021
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

50
layer
layer
% active neurons
40
layer
layer
layer
30
20
40
60
80
100
epoch
Figure 1: Examples from the IMAGENET2012 dataset, illustrating background noise in natural image classification tasks.
Figure Sparsity of intermediate WRN layers during training on CIFAR-10.
In this work, we extend this theoretical investigation into the superiority of neural networks over linear learners and, inspired by practical settings. propose new line of reasoning that we refer as "Local Signal Adaptivity". In particular, we explore the power of convolutional neural networks (CNNs) image classification, compared linear functions over prescribed feature mappings.
Our setting: We study a simple data distribution that captures one key property natural image classification tasks: small set of localized label-ddttrmining" features embedded within "noisy" background. We formally prove that even when such background occupies a rather large fraction of an image. CNN can be quite effective at locating the label-determining signal and thus ignoring background information that is mostly irrelevant to the true label, to achieve high accuracy.
Our result: In the formal setting of our simple data distribution (presented in Section 3), we ask whether particular two-layer CNN trained via stochastic gradient descent can provably acquire this "signal-finding ability and how this compares to its associated finite-width convolutional neural tangent kernel (CNTK). We answer with separation result between our CNN and CNTK: formally prove that small CNN, trained using standard SGD from random initialization, efficiently learn to find the "signal" and threshold out the noise, whereas the corresponding CNTK requires comparatively larger model (i.e., with more features) in order to accomplish this.
Empirical justification: While we pick simple data distribution in our work illustrate the main idea and obtain a formal proof, we point out that our setting is very natural in real images: in many image classification tasks, the label-determining feature only occupies a small fraction of the image, and most other parts are background noise (Figure D Furthermore, in neural networks trained on natural images, is generally accepted that activation patterns become increasingly sparse throughout training, effectively zeroing out the activations of low-magnitude noise and locating the true signal (suggestive the denoising/L.SA phenomenon studied in this work). For completeness, we have included such an experiment in Figure above, illustrating how the average percentage of active neurons per instance decreases throughout training (details are provided in Appendix (C). Finally, to empirically study theoretical results, create datasets by embedding CIFAR- 10 and MNIST images within either random Gaussian or IMAGENET backgrounds. Our experiments show that, as the intensity of the background noise grows and thus the "denoising task" becomes harder, the performance the neural network stays relatively stable, while the performance of the corresponding NTK does, in fact, degrade significantly (Section 6 Figure 4).
Based on our theorem and experiments, we therefore believe that this per-instance "signal finding within noisy backgrounds" ability of convolutional neural networks, which we dub "Local Signal Adaptivity" (LSS),, is one key component of the superiority SGD-trained convolutional neural networks over fixed feature mappings.

---

2
Related work
There is a long line of work proving that various concept classes can be learned efficiently by SGD- trained neural networks. Many of the theoretical works taking a "bbyoon-NTK"" perspective and emphasizing the non-linearit of neural networks are only proved under Gaussian inputs [Kawauuchi
2016 Soudry and Carmon, 2016 Xie et al. 2016 Ge et al.
2017. Soltanolkotabi et al. [017 Li and Yuan [017]] Boob and Lan
Tian 2017 |017| Brutzkus and Globerson| [217]] Z et al.) 2017
2017 et al. [2018] Vempala and Wilmes 2018 Ge et al. 2018 8 Bakshi et al. 2018 Oymak and
Soltanolkotahi 2019 Yehudai and Shamir 2019 Li and Yuan 2017] Li and I Liang, 2017 Li et al.
2016 and Doul 2020 Li al. [2000a]. In work, we consider more realistic setting which signal hidden within random background noise. Along these lines, we
there is a highly
recognize various aesthetic similarities sparse blind deconvolution and related areas of the signal processing literature [Zhang et al. 2019 Kuo et al. 2019 Sun and Donoho 202 Qu et al. 2020]. However, there are key structural differences as well e.g., rather than recovering the unknown sparse signal, we simply wish to extract the information relevant to the classification task; thus, further exploring possible connections between LSA and the signal processing literature presents an interesting avenue for future work.
We now give more detailed comparison of our work with prior theoretical results on the separation between neural networks and kemels.
Representation power of neural networks. Many existing works focus on separating the repre- sentation power of neural networks from that of other models [Ghorbani et al.) 2020 Refinetti et al.) 202T Gribonval et al.] 2020, Suzuki 20199] Suzuki and Nitanda 2019]. However, the fact that a function can be represented efficiently by a neural network does not mean that it can be efficiently learned. Only a subset of such works prove efficient Icarnability, including (uzuki and Akiyama [2020] and Daniely and Malach [202)]. In our work, we focus the set of functions that can be efficiently learned by neural networks, in particular learned via stochastic gradient descent over the standard training objective starting from random initialization.
Classification vs. regression. Many existing works only focus on separating the power of neural networks from that of other learners in a regression setting [Ghorbani et al.) 2020] [Suzuki and Akiyama 2020 Allen-Zhu and Lij [020 2019 [i et al.) [2020a] Wei et al. [0188] Yehudai and Shamir 2019]. In this case, both the neural network and the other learning methods are required to fit the exact label. Although Daniely and Malach (2020) presents one of the few results in a classification setting, their final separation result is still in terms of hinge loss instead of 0-1 loss. In our result, we focus on the binary classification setling, where the neural network and (significantly) the linear learner are only required to fit the sign of the label, instead of the exact labeling function. Our final result is therefore more natural in image classification settings than prior works.
Learning a hidden subspace. Many of the existing works showing how neural networks are better than other learners, in particular kernel methods, focus on the case where the concept class is of the form f(x) = ().), where W is rank-deficien matrix [Ghorbani et al. 2020 Wei et al. 2018 Thus, the learning process can be divided into two phases: (1) Identifying the hidden subspace of W: (2) Learning the function & over this hidden subspace. We point out that to the best of our knowledge, all the cited works only shows the superior power of neural networks in (1). This means that, W were known, then neural network would have the same sample/time complexity kernels when performing (2). As we will show, in our work, the underlying concept class does not have a fixed subspace, rather the signal can drift between different patches, and the neural network needs to identify the signal patch while ignoring the noise patches. Our explanation of how neural networks outperform kernels is therefore fundamentally different from the cited works.
Kernel lower bounds. Most of the existing theoretical works demonstrating the power of neural networks focus on showing how neural networks are better than kernel methods or linear functions over prescribed feature mappings. There are two related lines of work: (1) Showing that neural networks are better than any kernel method or any linear learner AAlee-Zhuu and Li 2020 Daniely
and Malach 2020 ; (2) Showing that neural networks are better than a particular set of linear learners, most notably, the NTKs or finite-width NTKs of the corresponding neural network [Yehudai] Wei et al. 2018 Our work belongs to the second line.
and Shamir 2019 Refinetti et al. 2021
3

---

Although result along the first line gives a much stronger separation, we point out that in the classification setting, such separation known to be extremely challenging in computational complexity theory O0 Donnell and Servedio, 2003 Sherstov and Wu 2019
Empirical results in the literature suggest that the anfinite-width NTK generally reaches slightly higher final test accuracy than the winite-width NTK [Allen- -hu and Li Lee et al. 2020). In fact, in certain limited settings, such as low-data regimes, the infinite-widit width NTK has actually demonstrated performance competitive with that of the original neural network Arora et al. 2020]. However, under certain conditions, the computational cost of the nufinite-width NTK can be significant compared to that of the original neural network and its corresponding finite- width NTK [Allen-Zhu and Li, 2020 Lee et al. 2020]. Therefore, due to these computational and NTKs, in our experiments we examine both types of NTK. Our theoretical lower bound, however, is a representational lower bound for the finite-width NTK. This is primarily due to theoretical challenges such those discussed above. Theoretical results such as Allen-Zhu and Li [2020] suggest that it may be possible, in follow-up work, to convert sample complexity lower bound. However, proving a sample complexity gap would likely require tightening sample complexity upper bound as well. We believe, conceptually (and supported by our experiments), that the LSA phenomenon is at play for infinite-width NTKs as well, and it would thus be interesting to extend our theoretical gap to the infinite-width NTK setting as well.
Finite- vs. indinite-width NTK.
2020
accuracy distinctions between the finite- and infinite-
tiith NTK representational lower bound into an infinite-width NTK
3 Problem setup
We now formally state our data distribution and the learning problem in our paper.
Relevant problem parameters. We consider the input X (X1, .x+1) to have k + 1 patches; each patch is associated with vector X; E Rd. We can think of X as either the input image or the output of some intermediate layer of the convolutional neural network. convenient to think of X as a matrix with as polynomial in k, enabling us to simplify certain results by expressing them entirely in terms of k. We consider an unknown signal vector w, E Rd with fn-norm |/wrll2 = =1, which determines how each (image) X is generated (described below). We also set a = log k/ VT. where a determines the intensity of the noise in our problem (described below). In Section [ we will only prove the
rows and columns, i.c., X (+++1)xdd We treat as "large" and d
kernel lower bound in the case where o² = 1/d; extending the result to o = w1/d) might require alternative proof techniques.
Data distribution. We sample each (image, label) pair (X,y) ~ D. The marginal distribution Dy is a uniform distribution over (-1, i.e., both classes occur with equal probability. We first sample y from Dy and then sample X ~ ~Dxig as follows: (a) draw i* from fl...., k+ 1} arbitrarily and put yw. in row i" (we call this the "signal" row); (b) in each of the k remaining rows (we call these the "noise" rows), put an independently-deee denote row i of X, for E {1....,k k + 1}. Formally, we therefore have:
vector e ~ N(0, o² Iaxa). We use X, e Rd to
X, (yw. ifi=;* i*
6 otherwise.
Our data distribution shares many similarities with the distribution studied in Yu et al. (2019). However, perhaps most crucially among the differences. the noise magnitude in our setting is significantly higher; in Yu et al. [2019]. the noise magnitude is low enough to maintain linear separability, which is insufficient to show any separation with linear learners.
We consider the simplest setting where there is only one feature w., though our result trivially extends to the case when there multiple orthogonal features (as many d). For example, the signal patch can contain features of the form Σ; a:w;, where the label is determined by E; a, as in Allen-Zhu and Li 2020
Remark.
How to learn this concept class. In our concept class, one of the rows X; associated with the true signal yw., and all the others are random Gaussian noise. Since this row can appear arbitrarily

---

in one of the l + rows, the most naive way to learn this function is to use convolutional linear classifier: ((X) Σ
*++ _ ( (w., X2). However, we argue that this linear classifier is actually very bad and cannot be used to classify the labels correctly. Note that in our problem setup, the noise rows are sampled according to ON
=i=1
which means that for each noise row i, we have (w).X;) ~ (0,, o²). Hence, the total accumulated noise over & noise rows would be (00 ko²). By our choice of a = log lk, this means that the total noise is much bigger than the signal yy| = 1. Hence, the linear classifier fails to classify the labels correctly with least probability 0.49.
The above argument suggests that, to learn the concept class, the model cannot naively sum up (W..X;) Rather, the model has to identify the signal row and ignore the noise rows. In other words, the model needs to distinguish between the case when (w.X)) is large (y) or small (O, o²)). As we will show, this can be efficiently learned by neural network with ReLU activations, trained using standard stochastic gradient descent from random initialization.
Convolutional neural network (CNN) architecture. Our goal is to learn the optimal parameters W E R2d b E Th of the following simple CNN:
k+1
k+1
fw,((x)= = Σ Φol(w. X())
Σ
ReLU((W, + ReLU(-(w,,X)) - b)]
This CNN can be understood from either of two equivalent perspectives:
(1) A single convolutional filter E R with stride d is applied to the image. Then the soft- thresholding activation function (x) = ReLU(( + b) - ReL.U(- + b) is applied pointwise over the resulting (k + 1) --dimensional vector. Finally, the second con-trainable) layer of the CNN simply sums up the k + 1 entries (i.e., the second layer is fully-connected layer mapping from R4+1 to R, with non-traine trainabllb weights all equal to 1).
(2) Two convolutional filters, each with stride d, are applied to the image. One filter is w E I2 and the other is -w IRd. After each filter is applied, the activation function (p)()) ReLU + b) is applied pointwise to all 2k + 2 pre-activation values (i.e., a k +1 "vector" with 2 channels). A non-trainable fully-connected layer then applied, mapping 22 to IR; in this layer, each of the k+1 1 weights applied to the the first channel (i.c., from filter w) are all 1, and each of the weights applied to the second channel (i.e., from filter w) are all -.
The key in both perspectives is how the two ReLU activation functions work together to implement a soft-thresholding function, which enables denoising. Throughout, we refer to our CNN having one filter, since only has d + 1 trainable parameters, regardless of which perspective is taken.
Training algorithm. We initialize b deterministically at O. We initialize w randomly by drawing from A (0, or laxa:: where ag is 1/poly(k:). We train the above CNN using mini-batch stochastic gradient descent (SGD) with the logistic loss, where the logistic loss é is defined as E( ((fw,b(X), == log( +e e=WSs..(X)).
Specifically, each iteration of SGD, argue that, at each iteration, the empirical gradient is very close to the true population loss gradient.
poly(k) fresh samples from D. This will allow to
To simply the proof, we use slightly smaller learning rate for b (denoted 7h) than for w (denoted lww). Specifically, we adopt a 1/poly(k) learning rate for w, and we set 7/6 7/w = 1/k. With bit more technical care, our proofs can be extended to cover the setting where 77 7/ but we use this simpler version to illustrate the main idea of the learning process, as we will state in the next section.
To avoid any ambiguity, we define this procedure explicitly as Algorithm 1
Algorithm 1 Mini-batch SGD
Initialization and learning rate (0)) + 0: (0) + -N(0, oālaxu); 17 + ni/k: ?w + 7
for t + 1...2 T do
Sample mini-batch of examples of size poly(k): 2 D Compute the stochastic gradient: gb - E2ez Vol(z), fw E Vul(z)
Update using stochastic gradient descent: ((t) + (t-1) Mb9., w!!)) t wil--) nw
return (TT) (T)
5

---

Additional notation. We will occasionally use the shorthand fe(-) to denote fwi .00 (00 (-), the network at iteration t. We use the standard big-O notation and its variants: (-), o()), (-), (2()) w-))., where & is the problem parameter that becomes large. Occasionallyy use the symbol (-)) (and analogously with the other four variants) to hide log & factors.
Our results will hold with high probability over the random initialization of w and the randomness of the mini-hatches, where "high probability" here means a failure probability super-polynomially small in k. Unless specified otherwise, w...p. can be taken to mean: with probability at least 1 e -3lllg k).
4 Neural network results
We now present and briefly describe our main result on the provably efficient learning of the CNN described in Section
Theorem (Main result). There exists an absolute constant ko such thut, for every k 2 kg using poly(k) samples from D. learning rate 1j = (/))ly(kk) and T poly(k) iterations, w.h.p. over the randomness of the initialization and the samples, we have (((x.))-D(sign(ffr the final network fr returned by Algorithm
# y) S 0.01,
Therefore, in contrast its corresponding Neural Tangent Kernel (Section 5 our CNN trained via SGD provably achieves high accuracy efficiently. This stands in contrast to some of the prior works discussed in Section 2 many of which do not prove efficient learnability.
We defer our detailed proofs to Appendix A and summarize the key ideas here.
Empirical vs. population gradients. Our general proof technique involves analyzing the gradient of the population loss at each iteration (we call this the true gradient): (x).(x.))=((((f..ll v)] and VxlE(x.))~<D(((
(X), (x),,,), w)]. Then, with (k) samples per mini-batch, we argue that w.h.p. the empirical gradient concentrates around the true gradient, and over = poly(k) steps, the
accumulated error is fairly small. This argument is made rigorous in Appendix A Therefore, in the remainder of this section, to illustrate the key idea of the proof, we limit our discussion to the true gradient just defined (and use the term gradient derivative without further qualification).
Learning the signal direction. As training progresses, W W. grows from its small-man magnniude initialization to a relatively large, but still O(),, positive value. Specifically, at each iteration, the gradient with respect to w has component parallel to w., with two opposing forces determining the sign/magnitude of this component: expectation over (X,y) D,
1. the k "noise" rows of X push w. to shrink and 2. the "signal" row pushes w, grow.
The "signal" row's contribution has magnitude of ((1), and the k "noise" rows have total contribution of magnitude at most O (Iw (/w.ww/-... - k log k- o²) = O ([w w.l log k). Therefore, long as |w w.| o(1/ log k),, the "signal" row's contribution overpowers the "noise" rows' contribution, causing w w. to grow. This means that, within ( log" k)- poly(k) iterations, w.w, rises from its small-magnitude initialization (11 //ol'g" k). After w, rises O(1/ log" k). we longer track its dynamics explicitly, throughout the rest of training, and this turns out to be sufficient for the remainder of the argument. The main lemma we prove in Appendix A regarding the growth of w w, is slightly more formal version of the following:
must stay somewhere between (2(1/ log" k) and (())
Lemma (Sketched). For any < T, (((()))))))) w.l = ( then V. V. w. (11).
10
Bounded growth along non-signal directions. As training progresses, we also track ||w -ww[d (w w,)w=ll2, the magnitude of w's projection onto the orthogonal complement of span(w.], Although the projection's direction can change, we show that its norm remains very small, allowing w w, to dominate.

---

Specifically, letting WT denote w (w w.Jw. at the start of iteration t, we show that (. y)] span(w,. W Further, (x y)] w /l/walll mirrors the "noise" contribution above: it has magnitude at most (l|w 1 klog k. x²) = O (Il [[wwlll wwlll log k) and pushes ||w ||2 to shrink. Thus, if we were actually using the true gradient, w would maintain its direction, and its norm would shrink. The effect of the stochastic gradient is that WT can change direction slightly, and its norm can grow bounded amount per iteration; however, as long as the mini-batch size is large enough (poly(k) suffices), its norm stays small enough throughout training. The main lemma we prove Appendix regarding [|w w ll2 is therefore a slightly more formal version of the following:
Lemma 2 (Sketched). For any t S T, let of denote VwB(((((())))) w W0/lw/ ll2 Then 01
(0) 0 and (()) O (Iw(") 1911 log R).
Learning to threshold out the noise. The derivative with respect to b similarly has two opposing forces determining its sign/magnitude: in expectation over (X, y) D,
1. the k "noise" rows of X push to decrease and
2. the "signal" row pushes 6 to increase.
The "signal" row's contribution has magnitude of (1)). Thus, we can only guarantee that is decreasing if the "noise" rows' total contribution is (1). Roughly, the "noise" rows' contribution is determined by (i) the scalar projection of each noise vector e, onto w and (ii) (when b < 0) how much of these scalar projections survive "thresholding". As |wll grows throughout training (primarily due to the growth of w W., discussed above), (i) becomes larger. However,
decreases (i.e. |6| grows, for b < 0), (ii) becomes smaller (i.e., much of the noise does not survive "thresholding"). Therefore, the crux of the proof to show that, as long as the probability of misclassification is still > 0.01, despite b already "thresholding out"" fair amount of the noise, the "noise" rows' total contribution will remain (1) and thus cause to further decrease. The main lemma we prove in Appendix A regarding b is therefore a slightly more formal version of the following:
Lemma 3 (Sketched). For any t S T, if w w. = w(1/k//8), then VaB]e(fe(XX, y) = 2(1).
We note that the requirement w(t) w. = (1/k3/5) is satisfied by the S211 log k) lower bound presented above, thus connecting the two phases of training.
Comment on actual dynamics. The elegance of this approach is that it largely allows us to ignore b's behavior prior to w w. reaching the S2(1/ log" k) regime. In reality, there is a short phase the beginning of training during which b grows (i.e., becomes increasingly positive); this occurs because, even though none of the noise is being "thresholded out" this point, ||w||2 is not yet large enough for the "noise" rows' contribution to dominate the "signal" row's 's (11) contribution (which itself does not scale with l[w]))). Then, at some point prior to w w. reaching 2/1/ log* k). 6 begins to decrease rather than increase and, as we prove, eventually continues to decrease throughout the rest of training. However, for our performance guarantee, it does not matter exactly when this transition from increasing to decreasing actually occurs. The T/. T/w 1/k ratio ensures that |b///w . w.l never exceeds (1/k) while b > O, which means that b = ((1/k) throughout its positive phase.
Provable efficiency. We argue that if pr(X,g)) [sign( (Xx( # y) 2 0.01, then we must have |W- w.| (1). This, along with the rest of the argument, is made fully rigorous in Appendix A We sum up the total number of iterations as follows. First, there are O(( log' 4 k)-1) iterations before begins to decrease. Then, because [w w. = (1), V,E[e(f. (X). v)] = (11. and the classification accuracy is controlled by the ratio [b]/ w.], we conclude that there are poly(k) iterations before {b] becomes large enough to yield Pr(x.))~Dl (sign)((())))((( # y) & 0.01. Thus, T = (k)y and with poly(k) samples per mini-batch. we have total sample complexity poly(k).
Illustration of training dynamics with synthetic data. Figure 3 illustrates these training dynam- ics on synthetic data (with à: 1000, = 10, a 1, Th: = 0.1, 7/h 0.1/1000). As can be seen in the figure, as training progresses, w w, increases and b decreases (i.e., b < 0, with increasing mag- nitude). Furthermore, as the ratio [b// /ww w.| grows (and thus more and more noise is "thresholded out"), the test accuracy increases as well, tightly aligning with the theory.
7

---

80
param. values
0.4
% test accuraiy
70
(ur
0.3
0.0
0.2
5000
10000
5000
10000
5000
10000
steps
SGD stops
SGD stops
Figure 3: Training our model on synthetic data. Left: Values of b and w Center: Ratio
[b/((w w.). Right: Test accuracy.
5 Kernel results
In this section, we compare the function learned by our simple convolution neural network to its corresponding finite-width CNTK [Allen-Zhu al. 2019). We define the finite-width CNTK as:
Niw (X)
Σ Σ iE[ki jE[m]
(w,, X,)1 (w])) x,)|+b,20'
which is a linear function over the gradient of (X) at initialization. We show that this NTK is unable to classify the target function correctly, unless the total number of channels m is large.
We prove this for the case where o² = 1/d. Extending the result to o² = w(1/d) might require alternative proof techniques.
Theorem 2. As long (0) where each w; i.i.d. N/0, (0,,0ā1) I) have that for every set of weights and for every set of biases {by jj(m)
(1), w.p. at least 0.999 over the random initialization {w; (0)
jje[m]
Pr [sign(kw (X)) # v) 0.1.
X.y<D
Compared to our convolutional neural network, which only requires m = neurons and can learn the target function correctly, the corresponding finite- width CNTK needs w(1) neurons order to even
represent the target function. This is due to the fact that the features w
(0) are prescribed at random
initialization, instead of trained. Thus, even with arbitrary tuned bias bj. the neural tangent kernel still fails adapt the local signal and perform denoising.
Experiments
We now provide concrete empirical evidence that the LSA phenomenon does explain the performance gap between CNNs and kernels in real-world datasets. We first construct several variants of CIFAR-10 (Krizhevsky 2009] with various forms of structured noise and compare how the scale of the noise affects CNNs and their corresponding
mhite-width NTKs. Next, we perform similar experiments using smaller CNN on MNIST [LeCun et al. 2010]; in this setting we can efficiently compute the infinite-widde NTK, as well as vary the width of the finite-width NTK, and observe whether the performance gap persists. CNN architecture and training details are given in Appendix C
CIFAR with structured noise. We construct several CIFAR-10 variants with structured noise, which capture key property real-world image classification tasks, that the signal localized to patch amidst a large amount of background noise. Although real-world images also exhibit this property (as in Figure []]. we wanted the ability to easily vary the intensity of the background noise, while leaving the signal intact. On each dataset, compare the performance of a 10-layer WideResNet (with widening factor 10) to that of its finite-width NTK [Zagoruyko and Komodakis
'Code for experiments available at
adaptiiity

---

CIFAR-10 (moise=ImageNet)
CIFAR-Vchicles
100
%/6 test accuracy
WRN
NTK
WRN NTK
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
noise pixel intensity
noise pixel intensity
CIFAR-2 (mageNe)))
CIFAR-2 (noise-Gaussian)
100
%6 test accuacy
80
WRN
WRN NTK
Figure 5: Examples from CIFAR-VEHICLAS VEHICLES (top) and CIFAR-10 10 with IMAGENET noise (bottom), both for back- ground noise pixel intensity scaled to 0.75.
NTK
1.00
noise pixel intensity
noise stdev, IT
Figure 4: WRN and NTK test accuracy over range of noise levels.
2016]. We vary the intensity of the noise and observe the resulting degradation in WideResNet (WRN) and NTK performance.
Each dataset is constructed by scaling a CIFAR image to 16x16 pixels and placing it onto a 32x32 noise background. In some instances described below, used IMAGENET backgrounds (Deng et al. 2009]. Here we highlight experiments on four such datasets:
CIFAR-10, IMAGENET noise. CIFAR-18 10 images are placed at a random location onto random background image chosen from the IMAGENET Plants synset. The Plants synset was chosen for its visual similarity to backgrounds in real images. In our experiments, we scale the background pixel intensity in a range between zero (black background) and one (original IMAGENET background). An example is shown in Figure (bottom).
CIFA R-2, IMAGENET noise. Same as above, except the CIFAR- 10 classes are grouped into animals and vehicles and the classification task is now binary. In contrast CIFAR-10 on CIFAR-2 the NTK performs nearly as well as the CNN in the zero-noise setting.
C-FAR-2, Gaussian noise. Also using the CIFAR-2 2 task, but with standard Gaussian noise in the background, for range of standard deviations a.
CIFAR-VEHICH VEICCLSS.. The task is to classify between the four vehicle classes from CIFAR- 10. The vehicle appears in random corner of the image, and the other three corners filled with random images from the four CIFAR- 10 animal classes. See Figure 5 (top). Unlike the relatively uniform IMAGENET plants backgrounds, this dataset is designed to capture a common type of background noise which consists of "distractor" signals which are not predictive of the true image class. For example, irrelevant people, bicycles, and birds could all occur in the background of a real-world vehicle-classification task.
For more natural setting, we conduct an additional experiment on CIFAR-2 with IMAGENET noise, but maintaining the full pixel intensity and varying the size of the background noise. This detailed in Appendix [D] along with additional experiment variants such different image placements, all of which display similar behavior to the experiments described here. While these datasets capture key attributes of real images, their synthetic construction does limit how realistic the images can be. We construct the datasets in this way in order to allow tunable noise levels, thus providing the r-axis of the plots in Figure 4 One could imagine alternative, more realistic ways of creating tunable noise levels, such as increasing the diversity of distractor images; these are viable avenues for future experimentation.
Observations. As seen Figure as the scale of the noise increases, NTK performance decreases significantly while WRN performance is relatively unaffected. Table [ gives the percent of test

---

MNIST-20k (noise-Gausian)
MNIST (noise-Gaussian)
100
60
25
40
woise stdov.
Figure 6: Comparison of CNN, finite-width, and infinite-width NTKs on a 20k MNIST sample (left), and various finite-width NTKs on full MNIST (right).
accuracy retained by each model as noise intensity increases from (or from o o in the Gaussian-nove noise case); that is, the percentage 100 lest at max nosse level The WRN always retains over 96% of its zero-noise performance, while the NTK in one case degrades below 70%.
Table I: Percentage of zero-noise test accuracy retained at maximum noise level.
CIEAR-I0, ImNet noise CIFAR-Vehicles CIFAR-2, ImNet noise CIEAR-2, Gauss. noise
WRN
98.97
97.25
99.79
96,83
NTK
69.75
76.37
92.81
85.54
Effect of NTK width (MNIST). We place MNIST images of size 28x28 onto 42x42 Gaussian- noise backgrounds. We use a small CNN with two convolutions with 8 and 16 channels, and compare to finite-width NTKs where the width has been increased by factor of between 50 and 100. On subset of 20k MNIST images, we also compare the same CNN and finite-width NTK (width factor=1) to the wndth NTK.
The results (Figure 6) indicate that the degradation of NTK performance persists for both infinite- and finite-width NTKs (regardless of finite NTK width). Results for intermediate NTK widths are shown in Appendix D Another desirable feature which we observe in the MNIST setting is that the NTK and CNN perform on-par in the presence of zero noise.
7 Conclusion
We have considered a simple, noisy data distribution that captures some the key structure seen in natural images. We have (1) provably shown that particular two-layer CNN trained via SGD can efficiently (in time and sample complexity) achieve high accuracy and (2) that its corresponding linear model (the finite-width NTK) requires larger network size (i.e., more features). Overall, our results shed light on a new mechanism through which neural networks are provably better than their corresponding kernels: in particular, when there is signal hidden within background noise, neural network is able to simultaneously adapt to the local signal and perform "denoising". We provide empirical justification showing that theoretical framework does coincide with the superior power of neural networks over linear learners in practice.
One avenue for future work involves extending the noise distribution: increasing a beyond log t/V which can provide an even stronger separation with linear learners, and extending to other noise models beyond Gaussian. Another possible extension is to drop the restriction that the same filter is used in both parts of the activation function and study whether this noft-thresholding behavior is recovered automatically upon training the final-layer weights. We could also consider more general models in which the signal "patch" and the CNN filter are not perfectly aligned. Another possibility is to develop a limitation result for all kernel methods instead of the CNTK corresponding to our CNN; however, as discussed in Section 2 this would likely be regression result instead of classification result, which is weaker in other ways. Finally, it would be interesting to extend this theoretical analysis to deeper networks and thus more practical CNNs (perhaps "hierarchical denoising").
[Ethics statement] Our work primarily theoretical in nature and analyzes existing methods; thus, to the best of our knowledge, it does not have any negative societal impact.
10

---

Acknowledgments & Funding Disclosure
The authors thank Zico Kolter for conversations about the experiments and Jachoon Lee and Ben Adlam for their help in navigating the neural-tangents API. The authors also thank the anonymous NeurlPS reviewers for their thoughtful, helpful feedback. YL acknowledges support from NSF RI 2007517.
References
Zeyuan Allen-Zhu and Yuanzhi Li. What Can ResNet Learn Efficiently, Going Beyond Kernels? In Advances in Neural Information Processing Systems, volume 32, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint 2011022001.04413, 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. /0/90, 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. In NeurIPS, 2019. Full version available at
http://arxiv.om org/ abs/ 049118
Sanjeev Arora, Simon S. Du Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2020. URL
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. arXiv preprint arXiv: 1.01885, 2018.
Digvijay Boob and Guanghui Lan. Theoretical properties of the global optimizer of two layer neural 2017.
network. arXiv preprint
James Bradbury. Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Mill and Qiao Zhang. JAX: composable transformations of Python+NumPP programs, 2018. URL
sttt:://githut cww coom/googee/jax
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint arXiv:1702.07960 2017.
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards Understanding Hierarchical Learning: Benefits of Neural Representations. In Advances in Neural Information Processing Systems, volume 33, pages 22 1413-21455555 2020.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems, volume 32, 2019.
Amit Daniely and Eran Malach. Learning Parities with Neural Networks. In Advances in Neural Information Processing Systems, volume 33, pages 20356-2000 20365, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pages 248-255. leee, 2009.
Carles Domingo-Enrich, Alberto Bietti, Eric Vanden-Eijnden, and Joan Bruna. On Energy-Based Models with Overparametrized Shallow Neural Networks. In Proceedings of ICML, 2021.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. In International Conference on Learning Representations, 2019. /RRLnttts///opeeeeeieee htt.://www.....tt.ooooooceeeeaaa
Rong Ge, Jason Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. arXiv preprint arXiv:1711.00501, 2017.

---

Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric imputs. arXiv preprint arXiv:1810.0679) 2018.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020 (11), 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of Lazy Training of Two-layers Neural Network. In Advances in Neural Information Processing Systems, volume 32, 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewiez, and Andrea Montanari. When Do Neural Networks Outperform Kernel Methods? In Advances in Neural Information Processing Systems, volume 33, pages 14820-14830, 2020.
Alexander N. Gorban and Ivan Yu. Tyukin. Blessing of dimensionality; mathematical foundations of the statistical physics of data. 2018.
03421
Rémi Gribonval, Gitta Kutyniok, Morten Nielsen, and Felix Voigtlaender. Approximation spaces of deep neural networks. 2020. https://t//// www.aaawwwwwo..aaaaaaaaaaaaaaaee 1900.01208.....
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernl:: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2236-2262, 2020.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pages 586-594, 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Han-Wen Kuo, Yenson Lau, Yuqian Zhang, and John Wright. Geometry and symmetry in short-and- sparse deconvolution. 2019.
Steven P. Lalley. Concentration inequalities (lecture notes). URL httpp::///galtoo httt::///aaloon.ucciaapo edu/ haalley/correee/////ccceettttttt .df.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online].
Available: http://yann.lecmn www.unnn.eeeccc.. www.:llllwww..ceeee.. wwtpw/////x//iiis.....mm 2, 2010.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite Versus Infinite Neural Networks: an Empirical Study. In Advances in Neural Information Processing Systems, volume 33, pages 15156-15172, 2020.
Aitor Lewkowycz and Guy Gur-Ari. On the training dynamics of deep networks with 1_2 regulariza- tion. arXiv preprint arXiv:2006. 00643, 2020. URI http:httt:::/ttttaie
www.google//aeeooooooooooooeeeee autol2
Yuanzhi Li and Zehao Dou. When can wasserstein gans minimize wasserstein distance? arXiv preprint arXiv:2003. 04000003.0333,.. 2020.
Yuanzhi Li and Yingyu Liang. Provable alternating gradient descent for non-negative matrix factor- ization with strong correlations. In Proceedings of the 34th International Conference on Machine Learning- Sharning-Volume 70, pages 2062-2070. JMLR. org, 2017.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances Neural Information Processing Systems, pages 597-607. wttpa//wwii..oa/aa////.........
2017.
Yuanzhi Li, Yingyu Liang, and Andrej Risteski. Recovery guarantee of non-negative matrix fac- torization via alternating updates. In Advances in neural information processing systems, pages 4987-4995, 2016.
12

---

Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over wer-paaraetteizzed matrix sensing and neural networks with quadratic activations. In COLT, 2018.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer relu neural networks beyond ntk. arXiv preprint arXiv:2007.04596 2020a.
Yuanzhi Li, Tengyu Ma, and Hongyang R. Zhang. Learning Over- PaeamParrmetrized Two--Layer Neural Networks beyond NTK. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2613-2682. PMLR, 2020b.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels. In Proceedings of ICMI,, 2021.
Edward Moroshko, Blake E Woodworth, Suriya Gunasekar, Jason D Lee, Nati Srebro, and Daniel Soudry. Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy. In Advances in Neural Information Processing Systems, volume 33, pages 22182 22192,293, 2020.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein. and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference Learning Representations, 2020. URL URLhttps:: httts: com/ google/ http:/euuualaaaaaaaa
Ryan O' Donnell and Rocco A. Servedio. New degree bounds for polynomial threshold functions. In Proceedings of the Thirty-Fifth Anmual ACM Symposiun on Theory of Computing, STOC '03, page 325-334, New York, NY, USA, 2003, Association for Computing Machinery. ISBN 1581136749, doi: 00.11457780522.780522. httpstcss:///ai.oor 10. 1145/780542 780592
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterrizatoo:: global con- vergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674 2019.
Qing Qu, Xiao Li, and Zhihui Zhu. A nonconvex approach for exact and efficient multichannel sparse blind deconvolution, 2020.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed. 2021.
URL httpt:tttaxxii.....tt wwwp:/iwiv.ooo/bbbbaae httggabb/2102.11////
Alexander A. Sherstov and Pei Wu. Near-optimal lower bounds on the threshold degree and sign-rank of acO. In Proceedings of the 5 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 401 -122, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 978 450367059. doi: 10.1 10.1145/3313276.331 6408.
URL https::/ org. /00000011 1145/
6313276.3366408
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of pereparameterized shallow neural networks. arXiv preprint arXiv: /70.00467, 2017.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint 1XXi::66050086// 2016.
Qingyun Sun and David Donoho. Convex sparse blind deconvolution. 2021.
Taiji Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2019. URI httttps:://penneeveeee httpiiiwwwwweeeeeeee http:/formmmmddidlellbeae
Taiji Suzuki and Shunta Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods, 2020. URL htttttttt///xiiii org/ abs/2012. 03224
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. 2019. URL
Terence Tao. The Litlleood--Offord problem in high dimensions and conjecture of Frankl and Füredi. 2010. htLLstts::// httt:tttst//rryyttttet httpeerryyytao.woorrresss.s wttpp//sssooootteeeeeeeeeeeeeee hatpa///ssaalllalllaaaaaaaaaeale balbbbbbiiyllrr..abiiii
13

---

Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. arXiv preprint arXiv:1733.0056)) 2017.
Santosh Vempala and John Wilmes. Polynomial convergence of gradient descent for training one- hidden-layer neural networks. arXiv preprint arXiv: 1805.02677, 2018.
Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond Lazy Training for Over-parrmeterrized Tensor Decomposition. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Advances in Neural Information Processing Systems, volume 33, pages 21934-21944, 2020.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. arXiv preprint arXiv: 1810.0536,, 2018.
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and Rich Regimes in Overparametrized Models. In Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 3635-3673, 2020.
Bo Xie, Yingyu Liang, and Le Song. Diversity leads to generalization neural networks. arXiv 2016.
preprint
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint 1904v 006677 2019.
Bing Yu, Junzhao Zhang, and Zhanxing Zhu. On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks. CoRR, abs/1905.10157,, 2019. URL htl.Lttt:///axx...r///aaas 1195510157
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, abs/ 0oos/160500716, 2016. URL http://arxiv. wtgg.bs//605.0000
Yuqian Zhang, Han- Wen Kuo, and John Wright. Structured local optima in sparse blind deconvolution. 2019.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. arXiv preprint arXiv:/706.03: 2017.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section T
(b) Did you describe the limitations of your work? [Yes] Sections 6 aannd 7 and a bit in
Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Sections
and P
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Sections
A
(b) Did you include complete proofs of all theoretical results? [Yes] In Section A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're rou're using/curating? [Yes]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "uADgQpdEn-4", "reviewer": "Reviewer_X9Jj", "summary": "This paper tackles the question of whether neural networks can be provable better than their induce neural tangent kernel for some problem setting. This question is answered in the context of a binary classification problem, in which the signal is shift invariant and embedded in a background of noise. The authors show that for this problem, a two layer neural network with relu activations and logistic loss efficiently learns (in sample and time complexity) this problem class with constant number of neurons, whereas its neural tangent kernel counterpart requires at least order d - the dimension of the (local) inputs. The authors then illustrate this basic problem in image classification settings where the problem setting is conceptually present, with results that align with their results in the toy-like distribution.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper was a pleasure to read. To the best of my knowledge, the results presented here are significant, as they illustrate a simple and clear setting in which the ability to learn the filters in a neural network model enables the problem to be learned efficiently, whereas building a kernel with their not-trained version does not. \n\nI have only a few minor questions and comments:\n\n1. The degree of difficulty in the problem is given, in a nutshell, buy the signal to noise ratio. The authors address the simple case where the classifier vector appears only once in the input matrix, but presumably the SNR could be improved by repeating the true vector in several patches. Is this correct?\n\n2. It is clear that the data distribution is a strong simplification of the distribution of images for image classification. One difference between them is that, in real settings, the background patches are not really independent of the image class (determined by the foreground object). Examples of this are sky backgrounds for planes, water background for boats, etc. Could the authors comment on whether such correlations could be taken into account in their model? Presumably, one could decompose the \"background\" patches into a 'signal' component (e.g. only weakly correlated with the signal) and a random component? \n\n3. Could the authors comment briefly on multi-class extensions of their analysis? Would it be the case that gradients will decompose into a 'true class' versus 'all other classes' components?\n\n4. Finally, I believe that a more natural way to evaluate this problem in practice would have been to implant cifar10 images in backgrounds of different sizes, as opposed to controlling the energy of the background. This is also mentioned by authors, and unfortunately left as future work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "oWYb9iStI8u", "reviewer": "Reviewer_cikC", "summary": "The paper provides a theoretical analysis comparing the training dynamics and performance of a specific 1 hidden-layer convolutional neural network with those of its corresponding finite width CNTK on a simple data distribution. This analysis is used to support their claim that the gap between neural networks and kernel methods may lie in the ````''Local Signal Adaptivity'', in the sense that neural networks outperform kernel methods in distinguishing localized influential features from noisy background. Furthermore, they empirically identify a performance gap between the CNN and finite width CNTK on noise extended variants of the CIFAR-10 dataset, which emphasizes the influence of the ``''Local Signal Adaptivity''. The authors conclude that this setting degrades the performance of kernels in a more pronounced way than it affects neural networks.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives: \n\n(1) Regarding the originality of the paper, it builds on a simple dataset similar to the one studied on a previous paper, as they explain in line 135. However, to the best of my knowledge, it is the first analysis of the gap between neural networks and kernels focusing on a locally informative image embedded in noise. Related work seems adequately cited.\n\n(2) The main claims are supported by theoretical analysis for a simple network and dataset.  \n\n(3) The paper is well organized to my opinion and the theoretical results are well explained.\n\n###################################\n\nLimitations: \n\n(1) Regarding the claims that neural networks have been shown to significantly outperform kernel methods in practice - I'm not sure this is precise.  There is evidence that the infinite width NTK and CNTK can outperform corresponding finite width neural networks and several other standard machine learning methods (e.g. see https://arxiv.org/abs/1910.01663 and https://arxiv.org/abs/2007.15801).  I think the authors should try to clarify their statements in the abstract and introduction to make clear that the gap studied in this work is between the finite width NTK/CNTK and the corresponding finite width network.  \n\n(2) I also have a few concerns about the conclusion drawn from the experimental results.  The authors claim that the experiments provide concrete empirical evidence that local signal adaptivity explains the performance gap between the finite width NTK and training finite width networks.  This experiment is performed using a WideResNet for 4 different settings.  Since the model used is widely different from the one considered in theoretical analysis, I feel the authors need to demonstrate that additional simpler models (maybe 1 to 3 hidden layer convolutional nets) also show a similar gap.  \n\n(3) Regarding the conclusions drawn about this gap between the finite width NTK and neural networks, I'm also a bit unsure whether this gap would disappear as width increases.   The authors already claim that the NTK requires many more features in order to identify the signal and threshold noise.  The main benefit of the NTK is that a closed form is readily computed for infinite width.  It seems entirely plausible that this performance gap decreases when increasing width.  Would the authors be able to run experiments to demonstrate that this is not the case?  \n\n(4) Lastly, I think the authors should also present the training accuracy for the finite width NTK and the finite width neural network to ensure that these are are trained to 100% training accuracy (and similar training losses).  This is important since the results could be a side-effect of underparameterization for the finite width NTK.  Please let me know if this is not the case. \n\nI am happy to consider raising the score provided that some of these limitations are addressed.  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, the authors have correctly addressed the potential negative societal impact of their work. However, their work has several limitations that have not been addressed in the paper (explained above along with suggestions for improvement).\n", "review_text": "", "extra_scores": {"ethical_concerns": "None at this point. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "n9y0Tyunjrf", "reviewer": "Reviewer_5cbb", "summary": "This paper introduces the notion of local signal adaptivity (LSA), which the authors claim is a new perspective on the benefits of feature learning in NNs over kernel methods like the NTK. LSA denotes the ability of non-linear NNs to find a sparse signal in the presence of large noise, and the authors theoretically show that in a particular data distribution setting with a sparse signal, a single filter CNN is able to train with GD to learn the signal. On the other hand, they show that for an underparameterised linear NN (linearised at initialisation in parameter space) the model is unable to learn the signal. Experimental results are provided comparing the degradation of non-linear and linear NNs under increasing noise, demonstrating that non-linear NNs are indeed more robust to noise in line with the theory.\n\n**update after rebuttal** raising my score to 7", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*originality* This paper offers a new take on the benefit of feature learning in NNs using the proposed LSA property, which as far as I am aware hasn't been studied before. Intuitively, sparse signals in the presence of noise are well fit description of image data, hence the relevance for CNNs and the image classification setting.\n\n*quality* I believe the paper is technically sound (although I didn't check all the details). I find some of the results, like the main contribution Theorem 1, to be interesting, and also appreciate the authors' efforts in page 6+7 to clearly describe a sketch of the proof, which seems sensible. \n\n*clarity* The paper is well written and organized, especially section 4 as mentioned. \n\n*signficance* I think this seems like a solid, if unspectacular, contribution. The question of the benefits of feature learning compared to kernel methods in *overparameterised* NNs is an popular area which would be of general interest to the NeurIPS community, though as the authors mention there are many similar papers in this area. I have some gripes as to the relevance of this paper though for that area too (see limitations). I think the idea of LSA is interesting in and of itself, though also have some questions about assumptions which make the data setting seemingly far from standard (see limitations).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- I find theorem 2 unsurprising, as in this setting we just don't have a rich enough hypothesis class (finite-channel hence underparameterised CNN NTK features at init) in order to fit the target class. The vast majority of interest in this area is to do with overparameterised NNs (which is also the settings used empirically in practice) and the benefits of feature learning vs kernel learning , so I don't really see the connection/importance of theorem 2 here. Given that the idea of 'LSA as a new angle on feature learning' is one of the key messages of the paper, I find this quite unsatisfactory. It would be more interesting if you could show e.g. sample complexity of nonlinear NNs is better relative to overparameterised linear NNs, or just develop the LSA idea more (perhaps going into some of the extensions you mention in the conclusion).\n- I find the assumption of d changing polynomially with k to be a bit strange. So k is the number of patches, but then the patch sizes is also increasing as the number of patches changes? Is this assumed elsewhere in the literature? Likewise, the assumption that you have enough data such that the empirical gradient and the population loss gradient are close throughout training with mini-batches seems quite strong.\n- The empirical results are not very convincing to me. In particular, because the linear WRN is already much worse than the non-linear WRN with 0 noise, it seems like there could be other effects going on to explain the degradation of the linear NN? It would make more sense to me to consider a case where we know that the finite-width linear NN and non-linear NN have similar performance without noise, before adding background noise. Does MNIST work (I know there is not much difference between infinite width NTK and non-linear NN)? Given that this is mainly a theoretical paper, I would find a more thorough smaller scale setting more convincing.\n\nIf the authors can address my concerns I would be happy to raise my score.", "review_text": "", "extra_scores": {"ethical_concerns": "N/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Xqjty5X_78y", "reviewer": "Reviewer_MLtr", "summary": "The authors study a toy binary classification problem where a certain CNN\narchitecture is trained to detect one of two templates embedded in gaussian\nnoise. The motivation is twofold: the problem is argued to capture relevant\nstructures present in natural image classification tasks where CNNs succeed in\npractice (i.e., the detection of an object/motif in the image in the presence\nof a nuisance background), and the theoretical analysis establishes an\narchitectural separation via the rates one gets by analyzing the problem with\nthe neural tangent kernel approach and via the authors' analysis. Concretely,\nthe data model consists of a fixed unknown template embedded in one of $k+1$\nconsecutive disjoint length-$d$ blocks of a length $d(k+1)$ 1D signal, with the\nother $k$ blocks containing i.i.d. gaussian noise of a certain variance (the\nblocks are imagined to be disjoint \"image patches\", and the template a motif of\ninterest) -- samples from this data model have the patch where the template is\ncontained uniformly randomized and contain independent noise, and the template\nis given either the positive or negative sign (representing the two classes in\nthe problem). The noise variance is set to be large enough that it is not\npossible to perform naive matched filtering to recover the template.\nAccordingly, the CNN that is trained to solve this task contains a custom\ndenoising nonlinearity, the standard soft thresholding function -- this\ncorresponds to a one-layer, two-neuron ReLU network that computes two\n$d$-strided convolutions with specific weight sharing and output averaging (the\nshared biases end up corresponding to the soft thresholding function's\nparameter) -- which is trained using finite samples from the data generating\ndistribution by mini-batch SGD on the logistic loss with gaussian random\ninitialization. The authors show that this procedure yields a classifier for\nthe data whp given polynomial samples and suitable step sizes; in contrast,\nthey show that the network's convolutional NTK is unable to solve the task whp\nas long as the number of filters satisfies $o(d)$ (the neural network studied\ncorresponds to a two filter network). Experiments involving embedding CIFAR-10\nimages into random backgrounds (either from ImageNet or having gaussian noise)\nwith varying intensities and comparing neural network performance to their\nNTK's performance computationally on the classification tasks thus generated\nverifies the predicted performance gap.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I thank the authors for their stimulating and interesting submission. I would\nlike to highlight what I perceive as a few strengths of the paper:\n- The theoretical task, while fundamentally simple and idealized (as the\n  authors acknowledge throughout the paper), has a strong motivation in the\n  understanding of aspects of neural network training problems that match the\n  settings where they are successful in practice, here specifically in the\n  context of image classification. This has the potential to spur further\n  impactful research.\n- In a similar vein, one major implication of the results is that kernel\n  approaches to analyzing the neural network training problem cannot capture\n  the same guarantees as in the authors' analysis without using additional\n  network resources. A number of works of this type have appeared in the\n  literature; the authors' has the advantage of pertaining to an algorithmic\n  learning scenario with a practically-motivated data model, which sets it\n  apart and will hopefully influence future works in this line.\n- In addition to being well-motivated, the paper is well-written, specifically\n  in its technical aspects. The sketch of the argument in section 4 is\n  particularly lucid.\n\nI will discuss what I perceive as some weaknesses/points where clarification\nwould be helpful below. I do not think these negatively outweigh the paper's\nstrengths. I hope the authors will correct any misconceptions I make in my\ndiscussion in the rebuttal.\n\n\n### Toy-ness of the task\n\n- I am onboard with the idea that the task is simple in order to act as a minimal\n  demonstration of a separation between kernel tools and direct methods for\n  analyzing neural network training that may have broader implications in the\n  future, and that it is therein essential to consider a CNN training scenario\n  with the given data model. However, it seems notable that the classification\n  task studied is algorithmically trivial: given that the class of CNN\n  architectures we search over with gradient descent is essentially\n  hand-designed to perform the denoising we need in the task, it is not\n  surprising that a simple algorithm solves this problem (it seems: given one\n  labeled sample from $\\mathcal{D}$, use this as a template to perform\n  filtering with new samples: cross-correlate over blocks on new samples and soft\n  threshold the output (if the noise distribution is not known, the threshold\n  level could be learned from a training set using classical detection\n  methods), then use the label from before to determine the class of the\n  result). A dual view here is that a \"data driven initialization\" approach\n  trivializes the problem. As before, I understand that the purpose of the\n  paper is to use this simple task as a way to study some interesting\n  properties of CNN training, but the task's algorithmic simplicity seems to\n  point to a need to include more challenging aspects in the problem\n  (overlapping blocks; templates obscured in noise; non-antipodal classes;\n  correlated models for the background noise) in order to obtain an analysis\n  that can truly offer insights into the features relevant to practical image\n  classification tasks.\n- In a similar vein, the CNN architecture used here feels ad-hoc designed to\n  perform well on the task, and some possibly unrealistic prior knowledge is\n  assumed in the non-overlapping blocks and the incorporation of $d$ as the\n  stride (along with all samples being \"canonized\" in the same block\n  alignment). This is reminiscent of other separations in the literature\n  between neural networks and kernel methods, which are often established on\n  tasks where the target function is per force well-specified by some neural\n  network architecture by construction of the task (notwithstanding the good\n  practical motivation here). Specifically in the context of some of the other\n  motivation in the \"Learning a hidden subspace\" paragraph, it seems like the\n  current task, rather than being one of learning a target $f(x) = \\phi(Wx)$ as\n  in related works, is one of learning a target $f(x) = \\phi(W_i x)$, where the\n  $W_i$s vary randomly over some finite set and one obtains different\n  observations of this form. In this connection, I would find it interesting to\n  know if there is any connection to be made with the analysis of [1] here.\n\n### Connections to signal processing literature?\n\n- Given that the task studied here is essentially a simple denoising task in\n  the language/formalism of CNN training, it would seem appropriate to mention\n  any relevant prior art in theory for neural networks and denoising (e.g. [2]\n  and much related work). I understand that the specific motivations and\n  focuses of the current work may be different from those in this literature\n  (here, the simple task is a vehicle to illustrate a point about neural\n  network training; there the tasks are more general and theoretical results\n  may be directly relevant to applications) and that this may make these\n  works not directly relevant; however, the focus on denoising and image data\n  makes it seem likely to me that there should be nontrivial overlap.\n- One area of this literature I do feel may likely be relevant in terms of\n  technical prior art is the literature on theory for sparse blind\n  deconvolution (e.g. [3-6] below), given that the authors' analysis here is an\n  analysis of the gradient descent trajectory. Natural optimization\n  formulations for these tasks collapse into the minimization of a loss like\n  the authors' $\\ell( f_{w, b}(X), y)$ in the non-overlapping-data setting the\n  authors study here, but the loss will be different from the logistic loss \n  (e.g. something like the Huber penalty function, which involves\n  soft-thresholding of large magnitude components at a scale commensurate with\n  the regularization threshold, which corresponds to $b < 0$ here). In the\n  multi-template classification setting with multiple observations, as\n  considered here, the areas of convolutional dictionary learning [7] and\n  multi-channel sparse blind deconvolution [8], respectively, may have the\n  relevant connections (given the functional similarities) -- although in the\n  context of the authors' simple data model the additional generality inherent\n  in these frameworks may not add anything relative to the authors' CNN\n  training framework. I would be interested to hear if the authors detect any\n  technical overlap between their work and this area of the literature -- I\n  suppose works on noisy SBD will be most relevant to the authors' work, and of\n  course the results and models considered in these works apply to more general\n  problem scenarios than the present setting where the motif locations do not\n  overlap. I also believe there may be some interesting messages with regards\n  to this literature from the authors' work here -- the fact that the parameter\n  $b$ is learned in the current work may be of interest in SBD settings where\n  one would like to adaptively set the regularization parameter, and I am not\n  aware of theoretical analyses that proceed in this way.\n\n### References mentioned above\n\n[1] http://arxiv.org/abs/2102.13219\n\n[2] https://ieeexplore.ieee.org/document/8398588/\n\n[3] https://arxiv.org/abs/1806.00338\n\n[4] https://arxiv.org/abs/1901.00256v2\n\n[5] https://arxiv.org/abs/2007.06753\n\n[6] https://arxiv.org/abs/2106.07053\n\n[7] https://arxiv.org/abs/1709.02893\n\n[8] https://arxiv.org/abs/1908.10776\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues. In this connection, I would like to thank the authors for their\nhonest remarks in section D.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is motivated by the need for mathematical understanding of mechanisms of feature learning in neural networks, and for understanding the limitations of kernel models (i.e., neural tangent kernel NTK) for learning in randomly initialized networks. The paper studies a very simple model problem, in which the goal is to determine whether a given input contains a noisy copy of a certain motif, or simply noise. In positive samples, the location of the motif is chosen uniformly at random. 

This simple model problem provides a separation between kernel methods, and methods which learn features: the paper considers single-layer nonlinear networks, and shows that (i) this problem can be solved by a network which only two neurons [which essentially implements a soft thresholding denoiser], which can be learned by randomly initialized  stochastic gradient descent, and (ii) the corresponding neural tangent kernel is only capable of achieving nontrivial performance when the number of neurons exceeds the length, d, of the motif. 

The paper complements these observations with experiments on both Gaussian backgrounds and “visual clutter”, involving more complex architectures, and showing a performance gap between the trained network and the corresponding kernel model, when the background is prominent. 

Initial reviews appreciated the paper’s clarity, and its contribution to the discussion on gaps between kernels and feature learning. Reviewers also noted several limitations — the “handcrafted” nature of the neural network and the simplicity of this model problem — and raised questions about comparisons to finite vs infinity width neural tangent kernels. 

After discussion of the above points, the reviewers converged to a decision to accept the paper. The AC concurs with this evaluation. There are some obvious limitations to the analysis. At the same time, the strength of the paper is that it provides rigorous results on feature learning and separations vis kernel methods in the practically relevant setting of detecting a motif (feature) in background clutter. The experiments suggest that these phenomena also obtain for more realistic networks and backgrounds. The paper is clearly written, and seems likely to stimulate future work. 

Decision: Accept (Poster)