Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.


main_review: I thank the authors for their stimulating and interesting submission. I would
like to highlight what I perceive as a few strengths of the paper:
- The theoretical task, while fundamentally simple and idealized (as the
  authors acknowledge throughout the paper), has a strong motivation in the
  understanding of aspects of neural network training problems that match the
  settings where they are successful in practice, here specifically in the
  context of image classification. This has the potential to spur further
  impactful research.
- In a similar vein, one major implication of the results is that kernel
  approaches to analyzing the neural network training problem cannot capture
  the same guarantees as in the authors' analysis without using additional
  network resources. A number of works of this type have appeared in the
  literature; the authors' has the advantage of pertaining to an algorithmic
  learning scenario with a practically-motivated data model, which sets it
  apart and will hopefully influence future works in this line.
- In addition to being well-motivated, the paper is well-written, specifically
  in its technical aspects. The sketch of the argument in section 4 is
  particularly lucid.

I will discuss what I perceive as some weaknesses/points where clarification
would be helpful below. I do not think these negatively outweigh the paper's
strengths. I hope the authors will correct any misconceptions I make in my
discussion in the rebuttal.


### Toy-ness of the task

- I am onboard with the idea that the task is simple in order to act as a minimal
  demonstration of a separation between kernel tools and direct methods for
  analyzing neural network training that may have broader implications in the
  future, and that it is therein essential to consider a CNN training scenario
  with the given data model. However, it seems notable that the classification
  task studied is algorithmically trivial: given that the class of CNN
  architectures we search over with gradient descent is essentially
  hand-designed to perform the denoising we need in the task, it is not
  surprising that a simple algorithm solves this problem (it seems: given one
  labeled sample from $\mathcal{D}$, use this as a template to perform
  filtering with new samples: cross-correlate over blocks on new samples and soft
  threshold the output (if the noise distribution is not known, the threshold
  level could be learned from a training set using classical detection
  methods), then use the label from before to determine the class of the
  result). A dual view here is that a "data driven initialization" approach
  trivializes the problem. As before, I understand that the purpose of the
  paper is to use this simple task as a way to study some interesting
  properties of CNN training, but the task's algorithmic simplicity seems to
  point to a need to include more challenging aspects in the problem
  (overlapping blocks; templates obscured in noise; non-antipodal classes;
  correlated models for the background noise) in order to obtain an analysis
  that can truly offer insights into the features relevant to practical image
  classification tasks.
- In a similar vein, the CNN architecture used here feels ad-hoc designed to
  perform well on the task, and some possibly unrealistic prior knowledge is
  assumed in the non-overlapping blocks and the incorporation of $d$ as the
  stride (along with all samples being "canonized" in the same block
  alignment). This is reminiscent of other separations in the literature
  between neural networks and kernel methods, which are often established on
  tasks where the target function is per force well-specified by some neural
  network architecture by construction of the task (notwithstanding the good
  practical motivation here). Specifically in the context of some of the other
  motivation in the "Learning a hidden subspace" paragraph, it seems like the
  current task, rather than being one of learning a target $f(x) = \phi(Wx)$ as
  in related works, is one of learning a target $f(x) = \phi(W_i x)$, where the
  $W_i$s vary randomly over some finite set and one obtains different
  observations of this form. In this connection, I would find it interesting to
  know if there is any connection to be made with the analysis of [1] here.

### Connections to signal processing literature?

- Given that the task studied here is essentially a simple denoising task in
  the language/formalism of CNN training, it would seem appropriate to mention
  any relevant prior art in theory for neural networks and denoising (e.g. [2]
  and much related work). I understand that the specific motivations and
  focuses of the current work may be different from those in this literature
  (here, the simple task is a vehicle to illustrate a point about neural
  network training; there the tasks are more general and theoretical results
  may be directly relevant to applications) and that this may make these
  works not directly relevant; however, the focus on denoising and image data
  makes it seem likely to me that there should be nontrivial overlap.
- One area of this literature I do feel may likely be relevant in terms of
  technical prior art is the literature on theory for sparse blind
  deconvolution (e.g. [3-6] below), given that the authors' analysis here is an
  analysis of the gradient descent trajectory. Natural optimization
  formulations for these tasks collapse into the minimization of a loss like
  the authors' $\ell( f_{w, b}(X), y)$ in the non-overlapping-data setting the
  authors study here, but the loss will be different from the logistic loss 
  (e.g. something like the Huber penalty function, which involves
  soft-thresholding of large magnitude components at a scale commensurate with
  the regularization threshold, which corresponds to $b < 0$ here). In the
  multi-template classification setting with multiple observations, as
  considered here, the areas of convolutional dictionary learning [7] and
  multi-channel sparse blind deconvolution [8], respectively, may have the
  relevant connections (given the functional similarities) -- although in the
  context of the authors' simple data model the additional generality inherent
  in these frameworks may not add anything relative to the authors' CNN
  training framework. I would be interested to hear if the authors detect any
  technical overlap between their work and this area of the literature -- I
  suppose works on noisy SBD will be most relevant to the authors' work, and of
  course the results and models considered in these works apply to more general
  problem scenarios than the present setting where the motif locations do not
  overlap. I also believe there may be some interesting messages with regards
  to this literature from the authors' work here -- the fact that the parameter
  $b$ is learned in the current work may be of interest in SBD settings where
  one would like to adaptively set the regularization parameter, and I am not
  aware of theoretical analyses that proceed in this way.

### References mentioned above

[1] http://arxiv.org/abs/2102.13219

[2] https://ieeexplore.ieee.org/document/8398588/

[3] https://arxiv.org/abs/1806.00338

[4] https://arxiv.org/abs/1901.00256v2

[5] https://arxiv.org/abs/2007.06753

[6] https://arxiv.org/abs/2106.07053

[7] https://arxiv.org/abs/1709.02893

[8] https://arxiv.org/abs/1908.10776

limitations_and_societal_impact: No issues. In this connection, I would like to thank the authors for their
honest remarks in section D.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

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. 

I have only a few minor questions and comments:

1. 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?

2. 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? 

3. 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?

4. 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.
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

main_review: Positives: 

(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.

(2) The main claims are supported by theoretical analysis for a simple network and dataset.  

(3) The paper is well organized to my opinion and the theoretical results are well explained.

###################################

Limitations: 

(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.  

(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.  

(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?  

(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. 

I am happy to consider raising the score provided that some of these limitations are addressed.  


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).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

**update after rebuttal** raising my score to 7
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.

*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. 

*clarity* The paper is well written and organized, especially section 4 as mentioned. 

*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).
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).
- 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.
- 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.

If the authors can address my concerns I would be happy to raise my score.
review_title: null

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)