summaries: 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.  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.  **update after rebuttal** raising my score to 7 The authors study a toy binary classification problem where a certain CNN architecture is trained to detect one of two templates embedded in gaussian noise. The motivation is twofold: the problem is argued to capture relevant structures present in natural image classification tasks where CNNs succeed in practice (i.e., the detection of an object/motif in the image in the presence of a nuisance background), and the theoretical analysis establishes an architectural separation via the rates one gets by analyzing the problem with the neural tangent kernel approach and via the authors' analysis. Concretely, the data model consists of a fixed unknown template embedded in one of $k+1$ consecutive disjoint length-$d$ blocks of a length $d(k+1)$ 1D signal, with the other $k$ blocks containing i.i.d. gaussian noise of a certain variance (the blocks are imagined to be disjoint "image patches", and the template a motif of interest) -- samples from this data model have the patch where the template is contained uniformly randomized and contain independent noise, and the template is given either the positive or negative sign (representing the two classes in the problem). The noise variance is set to be large enough that it is not possible to perform naive matched filtering to recover the template. Accordingly, the CNN that is trained to solve this task contains a custom denoising nonlinearity, the standard soft thresholding function -- this corresponds to a one-layer, two-neuron ReLU network that computes two $d$-strided convolutions with specific weight sharing and output averaging (the shared biases end up corresponding to the soft thresholding function's parameter) -- which is trained using finite samples from the data generating distribution by mini-batch SGD on the logistic loss with gaussian random initialization. The authors show that this procedure yields a classifier for the data whp given polynomial samples and suitable step sizes; in contrast, they show that the network's convolutional NTK is unable to solve the task whp as long as the number of filters satisfies $o(d)$ (the neural network studied corresponds to a two filter network). Experiments involving embedding CIFAR-10 images into random backgrounds (either from ImageNet or having gaussian noise) with varying intensities and comparing neural network performance to their NTK's performance computationally on the classification tasks thus generated verifies the predicted performance gap.   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. 
abstractText: 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 simultaneously 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.
authors.name: Stefani Karp
authors.name: Yuanzhi Li
references.authors: Zeyuan Allen-Zhu Yuanzhi Li
references.title: What Can ResNet Learn Efficiently, Going Beyond Kernels
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Zeyuan Allen-Zhu Yuanzhi Li
references.title: Backward feature correction: How deep learning performs deep learning
references.venue: arXiv preprint arXiv:2001.04413,
references.authors: Zeyuan Allen-Zhu Yuanzhi Li
references.title: Feature purification: How adversarial training performs robust deep learning
references.venue: arXiv preprint arXiv:2005.10190,
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Yingyu Liang
references.title: Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
references.venue: NeurIPS,
references.authors: Sanjeev Arora Simon S. Du Zhiyuan Li Ruslan Salakhutdinov Ruosong Wang Dingli Yu
references.title: Harnessing the power of infinitely wide deep nets on small-data tasks
references.venue: In International Conference on Learning Representations,
references.authors: Ainesh Bakshi Rajesh Jayaram David P Woodruff
references.title: Learning two layer rectified neural networks in polynomial time
references.venue: arXiv preprint arXiv:1811.01885,
references.authors: Digvijay Boob Guanghui Lan
references.title: Theoretical properties of the global optimizer of two layer neural network
references.venue: arXiv preprint arXiv:1710.11241,
references.authors: James Bradbury Roy Frostig Peter Hawkins Matthew James Johnson Chris Leary Dougal Maclaurin George Necula Adam Paszke Jake VanderPlas Skye Wanderman-Milne Qiao Zhang
references.title: JAX: composable transformations of Python+NumPy programs, 2018
references.venue: URL http://github.com/google/jax
references.authors: Alon Brutzkus Amir Globerson
references.title: Globally optimal gradient descent for a convnet with gaussian inputs
references.venue: arXiv preprint arXiv:1702.07966,
references.authors: Minshuo Chen Yu Bai Jason D Lee Tuo Zhao Huan Wang Caiming Xiong Richard Socher
references.title: Towards Understanding Hierarchical Learning: Benefits of Neural Representations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Lénaïc Chizat Edouard Oyallon Francis Bach
references.title: On Lazy Training in Differentiable Programming
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Amit Daniely Eran Malach
references.title: Learning Parities with Neural Networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jia Deng Wei Dong Richard Socher Li-Jia Li Kai Li Li Fei-Fei
references.title: Imagenet: A large-scale hierarchical image database
references.venue: IEEE conference on computer vision and pattern recognition,
references.authors: Carles Domingo-Enrich Alberto Bietti Eric Vanden-Eijnden Joan Bruna
references.title: On Energy-Based Models with Overparametrized Shallow Neural Networks
references.venue: In Proceedings of ICML,
references.authors: Simon S. Du Xiyu Zhai Barnabas Poczos Aarti Singh
references.title: Gradient Descent Provably Optimizes Over-parameterized Neural Networks
references.venue: In International Conference on Learning Representations,
references.authors: Rong Ge Jason D Lee Tengyu Ma
references.title: Learning one-hidden-layer neural networks with landscape design
references.venue: arXiv preprint arXiv:1711.00501,
references.authors: Rong Ge Rohith Kuditipudi Zhize Li Xiang Wang
references.title: Learning two-layer neural networks with symmetric inputs
references.venue: arXiv preprint arXiv:1810.06793,
references.authors: Mario Geiger Stefano Spigler Arthur Jacot Matthieu Wyart
references.title: Disentangling feature and lazy training in deep neural networks
references.venue: Journal of Statistical Mechanics: Theory and Experiment,
references.authors: Behrooz Ghorbani Song Mei Theodor Misiakiewicz Andrea Montanari
references.title: Limitations of Lazy Training of Two-layers Neural Network
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Behrooz Ghorbani Song Mei Theodor Misiakiewicz Andrea Montanari
references.title: When Do Neural Networks Outperform Kernel Methods
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Alexander N. Gorban Ivan Yu. Tyukin
references.title: Blessing of dimensionality: mathematical foundations of the statistical physics of data
references.authors: Rémi Gribonval Gitta Kutyniok Morten Nielsen Felix Voigtlaender
references.title: Approximation spaces of deep neural networks. 2020
references.venue: URL https://arxiv.org/abs/1905.01208
references.authors: Arthur Jacot Franck Gabriel Clement Hongler
references.title: Neural Tangent Kernel: Convergence and Generalization in Neural Networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Pritish Kamath Omar Montasser Nathan Srebro
references.title: Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
references.venue: In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research,
references.authors: Kenji Kawaguchi
references.title: Deep learning without poor local minima
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.authors: Han-Wen Kuo Yenson Lau Yuqian Zhang John Wright
references.title: Geometry and symmetry in short-andsparse deconvolution
references.authors: Yann LeCun Corinna Cortes CJ Burges
references.title: Mnist handwritten digit database
references.venue: ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist,
references.authors: Jaehoon Lee Samuel Schoenholz Jeffrey Pennington Ben Adlam Lechao Xiao Roman Novak Jascha Sohl-Dickstein
references.title: Finite Versus Infinite Neural Networks: an Empirical Study
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Aitor Lewkowycz Guy Gur-Ari
references.title: On the training dynamics of deep networks with l_2 regularization
references.venue: arXiv preprint arXiv:2006.08643,
references.authors: Yuanzhi Li Zehao Dou
references.title: When can wasserstein gans minimize wasserstein distance
references.venue: arXiv preprint arXiv:2003.04033,
references.authors: Yuanzhi Li Yingyu Liang
references.title: Provable alternating gradient descent for non-negative matrix factorization with strong correlations
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Yuanzhi Li Yang Yuan
references.title: Convergence analysis of two-layer neural networks with relu activation
references.venue: In Advances in Neural Information Processing Systems, pages 597–607
references.authors: Yuanzhi Li Yingyu Liang Andrej Risteski
references.title: Recovery guarantee of non-negative matrix factorization via alternating updates
references.venue: In Advances in neural information processing systems,
references.authors: Yuanzhi Li Tengyu Ma Hongyang Zhang
references.title: Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
references.authors: Yuanzhi Li Tengyu Ma Hongyang R Zhang
references.title: Learning over-parametrized two-layer relu neural networks beyond ntk
references.venue: arXiv preprint arXiv:2007.04596,
references.authors: Yuanzhi Li Tengyu Ma Hongyang R. Zhang
references.title: Learning Over-Parametrized Two-Layer Neural Networks beyond NTK
references.venue: In Proceedings of Thirty Third Conference on Learning Theory,
references.authors: Eran Malach Pritish Kamath Emmanuel Abbe Nathan Srebro
references.title: Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
references.venue: In Proceedings of ICML,
references.authors: Edward Moroshko Blake E Woodworth Suriya Gunasekar Jason D Lee Nati Srebro Daniel Soudry
references.title: Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Roman Novak Lechao Xiao Jiri Hron Jaehoon Lee Alexander A. Alemi Jascha Sohl-Dickstein Samuel S. Schoenholz
references.title: Neural tangents: Fast and easy infinite neural networks in python
references.venue: In International Conference on Learning Representations,
references.authors: Ryan O’Donnell Rocco A. Servedio
references.title: New degree bounds for polynomial threshold functions
references.venue: In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing,
references.authors: Samet Oymak Mahdi Soltanolkotabi
references.title: Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
references.venue: arXiv preprint arXiv:1902.04674,
references.authors: Qing Qu Xiao Li Zhihui Zhu
references.title: A nonconvex approach for exact and efficient multichannel sparse blind deconvolution
references.authors: Maria Refinetti Sebastian Goldt Florent Krzakala Lenka Zdeborová
references.title: Classifying highdimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
references.authors: Alexander A. Sherstov Pei Wu
references.title: Near-optimal lower bounds on the threshold degree and sign-rank of ac0
references.venue: In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,
references.authors: Mahdi Soltanolkotabi Adel Javanmard Jason D Lee
references.title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks
references.venue: arXiv preprint arXiv:1707.04926,
references.authors: Daniel Soudry Yair Carmon
references.title: No bad local minima: Data independent training error guarantees for multilayer neural networks
references.venue: arXiv preprint arXiv:1605.08361,
references.authors: Qingyun Sun David Donoho
references.title: Convex sparse blind deconvolution
references.authors: Taiji Suzuki
references.title: Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
references.venue: In International Conference on Learning Representations,
references.authors: Taiji Suzuki Shunta Akiyama
references.title: Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods, 2020
references.venue: URL https://arxiv.org/ abs/2012.03224
references.authors: Taiji Suzuki Atsushi Nitanda
references.title: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. 2019
references.venue: URL https://arxiv.org/abs/1910.12799
references.authors: Terence Tao
references.title: The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
references.authors: Yuandong Tian
references.title: An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis
references.venue: arXiv preprint arXiv:1703.00560,
references.authors: Santosh Vempala John Wilmes
references.title: Polynomial convergence of gradient descent for training onehidden-layer neural networks
references.venue: arXiv preprint arXiv:1805.02677,
references.authors: Xiang Wang Chenwei Wu Jason D Lee Tengyu Ma Rong Ge
references.title: Beyond Lazy Training for Over-parameterized Tensor Decomposition
references.venue: Advances in Neural Information Processing Systems,
references.authors: Colin Wei Jason D Lee Qiang Liu Tengyu Ma
references.title: On the margin theory of feedforward neural networks
references.venue: arXiv preprint arXiv:1810.05369,
references.authors: Blake Woodworth Suriya Gunasekar Jason D. Lee Edward Moroshko Pedro Savarese Itay Golan Daniel Soudry Nathan Srebro
references.title: Kernel and Rich Regimes in Overparametrized Models
references.venue: In Proceedings of Thirty Third Conference on Learning Theory,
references.authors: Bo Xie Yingyu Liang Le Song
references.title: Diversity leads to generalization in neural networks
references.venue: arXiv preprint Arxiv:1611.03131,
references.authors: Gilad Yehudai Ohad Shamir
references.title: On the power and limitations of random features for understanding neural networks
references.venue: arXiv preprint arXiv:1904.00687,
references.authors: Bing Yu Junzhao Zhang Zhanxing Zhu
references.title: On the Learning Dynamics of Two-layer Nonlinear Convolutional
references.venue: Neural Networks. CoRR,
references.authors: Yuqian Zhang Han-Wen Kuo John Wright
references.title: Structured local optima in sparse blind deconvolution
references.authors: Kai Zhong Zhao Song Prateek Jain Peter L Bartlett Inderjit S Dhillon
references.title: Recovery guarantees for one-hidden-layer neural networks
references.venue: arXiv preprint arXiv:1706.03175,
sections.heading: 1 Introduction
sections.text: Recently, deep learning (using multi-layer, non-linear neural networks) has demonstrated superior performance over traditional linear learners in 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, a gradient-descent-trained neural network reduces to a kernel method with a specific architecture- and initialization-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 a variety of perspectives, including the lazy vs. active regime framework [Chizat et al., 2019, Woodworth et al., 2020, Moroshko et al., 2020, Geiger et al., 2020, Wang et al., 2020]. Building on 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 et al., 2021, Kamath et al., 2020, Refinetti et al., 2021, Daniely and Malach, 2020, Chen et al., 2020, Domingo-Enrich et al., 2021].
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  In this work, we extend this theoretical investigation into the superiority of neural networks over linear learners and, inspired by practical settings, propose a new line of reasoning that we refer to as “Local Signal Adaptivity”. In particular, we explore the power of convolutional neural networks (CNNs) in image classification, compared to linear functions over prescribed feature mappings.
  Our setting: We study a simple data distribution that captures one key property of natural image classification tasks: a small set of localized “label-determining” features embedded within a “noisy” background. We formally prove that even when such background occupies a rather large fraction of an image, a 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 a 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 a separation result between our CNN and its CNTK: We formally prove that a small CNN, trained using standard SGD from random initialization, can efficiently learn to find the “signal” and threshold out the noise, whereas the corresponding CNTK requires a comparatively larger model (i.e., with more features) in order to accomplish this.
  Empirical justification: While we pick a simple data distribution in our work to 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 1). Furthermore, in neural networks trained on natural images, it 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 of the denoising/LSA phenomenon studied in this work). For completeness, we have included such an experiment in Figure 2 above, illustrating how the average percentage of active neurons per instance decreases throughout training (details are provided in Appendix C). Finally, to empirically study our theoretical results, we create new 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 of 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” (LSA), is one key component of the superiority of SGD-trained convolutional neural networks over fixed feature mappings.
sections.heading: 2 Related work
sections.text: There is a long line of work proving that various concept classes can be learned efficiently by SGDtrained neural networks. Many of the theoretical works taking a “beyond-NTK” perspective and emphasizing the non-linearity of neural networks are only proved under Gaussian inputs [Kawaguchi, 2016, Soudry and Carmon, 2016, Xie et al., 2016, Ge et al., 2017, Soltanolkotabi et al., 2017, Tian, 2017, Brutzkus and Globerson, 2017, Zhong et al., 2017, Li and Yuan, 2017, Boob and Lan, 2017, Li et al., 2018, Vempala and Wilmes, 2018, Ge et al., 2018, Bakshi et al., 2018, Oymak and Soltanolkotabi, 2019, Yehudai and Shamir, 2019, Li and Yuan, 2017, Li and Liang, 2017, Li et al., 2016, Li and Dou, 2020, Li et al., 2020a]. In our work, we consider a more realistic setting in which there is a highly-structured signal hidden within random background noise. Along these lines, we recognize various aesthetic similarities to sparse blind deconvolution and related areas of the signal processing literature [Zhang et al., 2019, Kuo et al., 2019, Sun and Donoho, 2021, 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 a more detailed comparison of our work with prior theoretical results on the separation between neural networks and kernels.
  Representation power of neural networks. Many existing works focus on separating the representation power of neural networks from that of other models [Ghorbani et al., 2020, Refinetti et al., 2021, Gribonval et al., 2020, Suzuki, 2019, 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 learnability, including Suzuki and Akiyama [2020] and Daniely and Malach [2020]. In our work, we focus on 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 Li, 2020, 2019, Li et al., 2020a, Wei et al., 2018, 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 setting, 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) = φ(Wx), where W is a rank-deficient 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, if W were known, then a neural network would have the same sample/time complexity as 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 [Allen-Zhu 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 and Shamir, 2019, Refinetti et al., 2021, Wei et al., 2018]. Our work belongs to the second line.
  Although a result along the first line gives a much stronger separation, we point out that in the classification setting, such a separation is known to be extremely challenging in computational complexity theory [O’Donnell and Servedio, 2003, Sherstov and Wu, 2019].
  Finite- vs. infinite-width NTK. Empirical results in the literature suggest that the infinite-width NTK generally reaches slightly higher final test accuracy than the finite-width NTK [Allen-Zhu and Li, 2020, Lee et al., 2020]. In fact, in certain limited settings, such as low-data regimes, the infinite-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 infinite-width NTK can be significant compared to that of the original neural network and its corresponding finitewidth NTK [Allen-Zhu and Li, 2020, Lee et al., 2020]. Therefore, due to these computational and accuracy distinctions between the finite- and infinite-width 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 as those discussed above. Theoretical results such as Allen-Zhu and Li [2020] suggest that it may be possible, in follow-up work, to convert our finite-width NTK representational lower bound into an infinite-width NTK sample complexity lower bound. However, proving a sample complexity gap would likely require tightening our 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.
sections.heading: 3 Problem setup
sections.text: We now formally state our data distribution and the learning problem in our paper.
  Relevant problem parameters. We consider the input X = (X1, · · · , Xk+1) to have k + 1 patches; each patch is associated with a vector Xi ∈ Rd. We can think of X as either the input image or the output of some intermediate layer of the convolutional neural network. It is convenient to think of X as a matrix with k + 1 rows and d columns, i.e., X ∈ R(k+1)×d. We treat k as “large” and d 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? ∈ Rd with `2-norm ‖w?‖2 = 1, which determines how each (image) X is generated (described below). We also set σ = log k/ √ k, where σ determines the intensity of the noise in our problem (described below). In Section 5, we will only prove the kernel lower bound in the case where σ2 = 1/d; extending the result to σ2 = ω(1/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, 1}, i.e., both classes occur with equal probability. We first sample y fromDy and then sample X ∼ DX|y as follows: (a) draw i? from {1, . . . , 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-drawn vector i ∼ N (0, σ2Id×d). We use Xi ∈ Rd to denote row i of X , for i ∈ {1, . . . , k + 1}. Formally, we therefore have:
  Xi =
  { yw? if i = i?
  i 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.
  Remark. We consider the simplest setting where there is only one feature w?, though our result trivially extends to the case when there are multiple orthogonal features (as many as d). For example, the signal patch can contain features of the form ∑ i αiw ? i , where the label is determined by ∑ i αi, as in Allen-Zhu and Li [2020].
  How to learn this concept class. In our concept class, one of the rows Xi is associated with the true signal yw?, and all the others are random Gaussian noise. Since this row can appear arbitrarily
  in one of the k + 1 rows, the most naive way to learn this function is to use a convolutional linear classifier: l(X) = ∑k+1 i=1 〈w?, Xi〉. 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 N (0, σ2Id×d), which means that for each noise row i, we have 〈w?, Xi〉 ∼ N (0, σ2). Hence, the total accumulated noise over k noise rows would be N (0, kσ2). By our choice of σ = log k/ √ k, this means that the total noise is much bigger than the signal |y| = 1. Hence, the linear classifier fails to classify the labels correctly with at least probability 0.49.
  The above argument suggests that, to learn the concept class, the model cannot naively sum up 〈w?, Xi〉. 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?, Xi〉 is large (y) or small (N (0, σ2)). As we will show, this can be efficiently learned by a 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 ∈ Rd, b ∈ R of the following simple CNN:
  fw,b(x) = k+1∑ i=1 φb(〈w, Xi〉) = k+1∑ i=1 [ ReLU(〈w, Xi〉+ b)− ReLU(−〈w, Xi〉+ b) ] .
  This CNN can be understood from either of two equivalent perspectives:
  (1) A single convolutional filter w ∈ Rd with stride d is applied to the image. Then the softthresholding activation function φb(x) = ReLU(x+ b)− ReLU(−x+ b) is applied pointwise over the resulting (k+ 1)-dimensional vector. Finally, the second (non-trainable) layer of the CNN simply sums up the k + 1 entries (i.e., the second layer is a fully-connected layer mapping from Rk+1 to R, with non-trainable weights all equal to 1).
  (2) Two convolutional filters, each with stride d, are applied to the image. One filter is w ∈ Rd and the other is −w ∈ Rd. After each filter is applied, the activation function ϕb(x) = ReLU(x + 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 is then applied, mapping R2k+2 to R; in this layer, each of the k + 1 weights applied to the the first channel (i.e., from filter w) are all 1, and each of the weights applied to the second channel (i.e., from filter −w) are all −1. 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 as having one filter, since it only has d+ 1 trainable parameters, regardless of which perspective is taken.
  Training algorithm. We initialize b deterministically at 0. We initialize w randomly by drawing from N ( 0, σ20Id×d ) , where σ0 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 `(fw,b(X), y) := log ( 1 + e−yfw,b(X) ) .
  Specifically, at each iteration of SGD, we use poly(k) fresh samples from D. This will allow us to argue that, at each iteration, the empirical gradient is very close to the true population loss gradient.
  To simply the proof, we use a slightly smaller learning rate for b (denoted ηb) than for w (denoted ηw). Specifically, we adopt a 1/poly(k) learning rate for w, and we set ηb/ηw = 1/k. With a bit more technical care, our proofs can be extended to cover the setting where ηb = ηw 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 b(0) ← 0; w(0) ← N (0, σ20Id×d); ηb ← η/k; ηw ← η for t← 1 . . . T do
  Sample a mini-batch of examples of size n = poly(k): Z ← Dn Compute the stochastic gradient: gb = 1n ∑ z∈Z ∇b`(z), gw = 1 n ∑ z∈Z ∇w`(z)
  Update using stochastic gradient descent: b(t) ← b(t−1) − ηbgb, w(t) ← w(t−1) − ηwgw return b(T ),w(T )
  Additional notation. We will occasionally use the shorthand ft(·) to denote fw(t),b(t)(·), the network at iteration t. We use the standard big-O notation and its variants: O(·), o(·),Θ(·),Ω(·), ω(·), where k is the problem parameter that becomes large. Occasionally, we use the symbol Õ(·) (and analogously with the other four variants) to hide log k factors.
  Our results will hold with high probability over the random initialization of w and the randomness of the mini-batches, where “high probability” here means a failure probability super-polynomially small in k. Unless specified otherwise, w.h.p. can be taken to mean: with probability at least 1−e−Ω(log2 k).
sections.heading: 4 Neural network results
sections.text: We now present and briefly describe our main result on the provably efficient learning of the CNN described in Section 3.
  Theorem 1 (Main result). There exists an absolute constant k0 such that, for every k ≥ k0, using poly(k) samples from D, learning rate η = 1/poly(k), and T = poly(k) iterations, w.h.p. over the randomness of the initialization and the samples, we have Pr(X,y)∼D[sign(fT (X)) 6= y] ≤ 0.01, for the final network fT returned by Algorithm 1.
  Therefore, in contrast to 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): ∇wE(X,y)∼D[`(fw,b(X), y)] and ∇bE(X,y)∼D[`(fw,b(X), y)]. Then, with poly(k) samples per mini-batch, we argue that w.h.p. the empirical gradient concentrates around the true gradient, and over T = 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 as just defined (and use the term gradient or derivative without further qualification).
  Learning the signal direction. As training progresses, w ·w? grows from its small-magnitude initialization to a relatively large, but still O(1), positive value. Specifically, at each iteration, the gradient with respect to w has a component parallel to w?, with two opposing forces determining the sign/magnitude of this component: in expectation over (X, y) ∼ D,
  1. the k “noise” rows of X push w ·w? to shrink and 2. the “signal” row pushes w ·w? to grow.
  The “signal” row’s contribution has a magnitude of Θ(1), and the k “noise” rows have a total contribution of magnitude at most O ( |w ·w?| · k log k · σ2 ) = O ( |w ·w?| · log3 k ) . Therefore, as long as |w · w?| = o(1/ log3 k), the “signal” row’s contribution overpowers the “noise” rows’ contribution, causing w ·w? to grow. This means that, within Θ((ηw log4 k)−1) = poly(k) iterations, w·w? rises from its small-magnitude initialization to Θ(1/ log4 k). After w·w? rises to Θ(1/ log4 k), we no longer track its dynamics explicitly, as it must stay somewhere between Ω(1/ log4 k) andO(1) 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 a slightly more formal version of the following:
  Lemma 1 (Sketched). For any t ≤ T , if |w(t) ·w?| = o ( 1 log3 k ) , then ∇wE[`(ft(X), y)] ·w? = −Θ(1).
  Bounded growth along non-signal directions. As training progresses, we also track ‖w − (w · w?)w?‖2, 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 w⊥ denote w − (w · w?)w? at the start of iteration t, we show that ∇wE[`(ft(X), y)] ∈ span{w?,w⊥}. Further, ∇wE[`(ft(X), y)] ·w⊥/‖w⊥‖2 mirrors the “noise” contribution above: it has magnitude at most O ( ‖w⊥‖2 · k log k · σ2 ) = O ( ‖w⊥‖2 · log3 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 w⊥ can change direction slightly, and its norm can grow a 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 in Appendix A regarding ‖w⊥‖2 is therefore a slightly more formal version of the following:
  Lemma 2 (Sketched). For any t ≤ T , let g(t)⊥ denote ∇wE[`(ft(X), y)] · w (t) ⊥ /‖w (t) ⊥ ‖2. Then g (t) ⊥ ≥ 0 and g (t) ⊥ = O ( ‖w(t)⊥ ‖2 · log 3 k ) .
  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 b to decrease and 2. the “signal” row pushes b to increase.
  The “signal” row’s contribution has a magnitude of Θ(1). Thus, we can only guarantee that b 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 i onto w and (ii) (when b < 0) how much of these scalar projections survive “thresholding”. As ‖w‖2 grows throughout training (primarily due to the growth of w ·w?, discussed above), (i) becomes larger. However, as b decreases (i.e, |b| grows, for b < 0), (ii) becomes smaller (i.e., much of the noise does not survive “thresholding”). Therefore, the crux of the proof is to show that, as long as the probability of misclassification is still > 0.01, despite b already “thresholding out” a fair amount of the noise, the “noise” rows’ total contribution will remain ω(1) and thus cause b 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 ≤ T , if w(t) ·w? = ω(1/k1/8), then∇bE[`(ft(X), y)] = Ω(1).
  We note that the requirement w(t) ·w? = ω(1/k1/8) is satisfied by the Ω(1/ log4 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 Ω(1/ log4 k) regime. In reality, there is a short phase at 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” at this point, ‖w‖2 is not yet large enough for the “noise” rows’ contribution to dominate the “signal” row’s Θ(1) contribution (which itself does not scale with ‖w‖2). Then, at some point prior to w ·w? reaching Ω(1/ log4 k), b 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 ηb/ηw = 1/k ratio ensures that |b|/|w ·w?| never exceeds Θ(1/k) while b > 0, which means that b = O(1/k) throughout its positive phase.
  Provable efficiency. We argue that if Pr(X,y)∼D[sign(fT (X)) 6= y] ≥ 0.01, then we must have |w ·w?| = O(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((ηw log4 k)−1) iterations before b begins to decrease. Then, because |w · w?| = O(1), ∇bE[`(ft(X), y)] = Ω(1), and the classification accuracy is controlled by the ratio |b|/|w · w?|, we conclude that there are poly(k) iterations before |b| becomes large enough to yield Pr(X,y)∼D[sign(fT (X)) 6= y] ≤ 0.01. Thus, T = poly(k), 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 dynamics on synthetic data (with k = 1000, d = 10, σ = 1, ηw = 0.1, ηb = 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 magnitude). Furthermore, as the ratio |b|/|w ·w?| grows (and thus more and more noise is “thresholded out”), the test accuracy increases as well, tightly aligning with the theory.
sections.heading: 5 Kernel results
sections.text: In this section, we compare the function learned by our simple convolution neural network to its corresponding finite-width CNTK [Allen-Zhu et al., 2019]. We define the finite-width CNTK as:
  kw(X) = ∑ i∈[k] ∑ j∈[m] 〈wj , Xi〉1|〈w(0)j ,Xi〉|+bj≥0,
  which is a linear function over the gradient of fw,b(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 σ2 = 1/d. Extending the result to σ2 = ω(1/d) might require alternative proof techniques.
  Theorem 2. As long as m = O(1), w.p. at least 0.999 over the random initialization {w(0)j }j∈[m] where each w(0)j i.i.d. ∼ N (0, σ20I), we have that for every set of weights w and for every set of biases {bj}j∈[m],
  Pr X,y∼D
  [sign(kw(X)) 6= y] ≥ 0.1.
  Compared to our convolutional neural network, which only requires m = 1 neurons and can learn the target function correctly, the corresponding finite-width CNTK needs ω(1) neurons in order to even represent the target function. This is due to the fact that the features w(0)j are prescribed at random initialization, instead of trained. Thus, even with arbitrary tuned bias bj , the neural tangent kernel still fails to adapt to the local signal and perform denoising.
sections.heading: 6 Experiments
sections.text: 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 finite-width NTKs. Next, we perform similar experiments using a smaller CNN on MNIST [LeCun et al., 2010]; in this setting we can efficiently compute the infinite-width 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.1
  CIFAR with structured noise. We construct several CIFAR-10 variants with structured noise, which capture a key property of real-world image classification tasks, that the signal is localized to patch amidst a large amount of background noise. Although real-world images also exhibit this property (as in Figure 1), we wanted the ability to easily vary the intensity of the background noise, while leaving the signal intact. On each dataset, we compare the performance of a 10-layer WideResNet (with widening factor of 10) to that of its finite-width NTK [Zagoruyko and Komodakis,
  1Code for experiments is available at https://github.com/skarp/local-signal-adaptivity.
  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, we used IMAGENET backgrounds [Deng et al., 2009]. Here we highlight experiments on four such datasets:
  • CIFAR-10, IMAGENET noise. CIFAR-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 5 (bottom).
  • CIFAR-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 to CIFAR-10, on CIFAR-2 the NTK performs nearly as well as the CNN in the zero-noise setting.
  • CIFAR-2, Gaussian noise. Also using the CIFAR-2 task, but with standard Gaussian noise in the background, for a range of standard deviations σ.
  • CIFAR-VEHICLES. The task is to classify between the four vehicle classes from CIFAR10. The vehicle appears in a random corner of the image, and the other three corners are 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 a 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 is detailed in Appendix D, along with additional experiment variants such as 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 x-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 in Figure 4, as the scale of the noise increases, NTK performance decreases significantly while WRN performance is relatively unaffected. Table 1 gives the percent of test
  accuracy retained by each model as noise intensity increases from 0 to 1 (or from σ = 0 to σ = 2 in the Gaussian-noise case); that is, the percentage 100 · test acc. at max noise leveltest acc. at zero noise . The WRN always retains over 96% of its zero-noise performance, while the NTK in one case degrades below 70%.
  Effect of NTK width (MNIST). We place MNIST images of size 28x28 onto 42x42 Gaussiannoise 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 a factor of between 50 and 100. On a subset of 20k MNIST images, we also compare the same CNN and finite-width NTK (width factor=1) to the infinite-width NTK.
  The results (Figure 6) indicate that the degradation of NTK performance persists for both infiniteand 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.
sections.heading: 7 Conclusion
sections.text: We have considered a simple, noisy data distribution that captures some of the key structure seen in natural images. We have (1) provably shown that a 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 a 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 a signal hidden within background noise, a neural network is able to simultaneously adapt to the local signal and perform “denoising”. We provide empirical justification showing that our 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 σ beyond log k/ √ k, 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 soft-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 a regression result instead of a 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 is primarily theoretical in nature and analyzes existing methods; thus, to the best of our knowledge, it does not have any negative societal impact.
  Acknowledgments & Funding Disclosure
  The authors thank Zico Kolter for conversations about the experiments and Jaehoon Lee and Ben Adlam for their help in navigating the neural-tangents API. The authors also thank the anonymous NeurIPS reviewers for their thoughtful, helpful feedback. YL acknowledges support from NSF RI 2007517.
title: Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels