Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This is a theoretical paper that studies the feature learning properties of neural networks (NN) and the importance of input structure on the advantages of NN's over fixed feature models like linear or random features models. The authors create a setup motivated by real data where they can analytically show that a single hidden layer NNs can achieve good error (Theorem 1), whereas models with fixed features need to be exponentially large (in the number of relevant features) to match (Thm 2). The authors also show that without input structure, polynomial algorithms in the Statistical Query model achieve random guessing error (Thm 3). Some experimental evidence is provided to support some of the claims. 
main_review: Strengths:
- The paper is well motivated and studies a question of great interest to the community (the effects and benefits of NN feature learning), and highlight the importance of input structure, which to my knowledge is often neglected in the literature.
- The paper (to the best of my knowledge) is technically sound.
- I appreciated section 5 which helps to provide some intuition for the results (although also see weaknesses).

Weaknesses:
- Theorem 2 seems slightly weak in that it requires a bounded feature map dimension to work to show that fixed feature models fail, so what about infinite dimensional feature maps like say kernel methods? This is not an issue with other settings to show that fixed feature models fail e.g. https://arxiv.org/abs/2012.09816 (which also should be in the related works, as they also look at input structure, a 'multi-view setting' to show the benefits of NN feature learning over feature selection methods like random features).
- The experimental section is not very convincing to show that your theory is relevant for NNs in practice. It would be good to see Figure 3 for a larger setting, perhaps CIFAR10 with a deeper resnet/cnn. You have a nice simplified story for how NNs learn features from your theory: 1st step extracts rough features, 2nd step refines these, then finally the linear classifier is trained. I'm not convinced that this holds in practice with the provided experiments.
- Likewise the networks for MNIST are very narrow, you have m=9? Perhaps MNIST isn't a very good dataset to depict the importance of NN feature learning, as I believe linear models can already achieve a respectable score.
- I appreciate the efforts of the authors, but I'm still somewhat lacking in the intuition for the setup and how it is relevant to practical settings. For example, the first line of section 3 talks about circles and lines, but you make no further mention of this example. How does your 'structured' data look like in terms of circles and lines, particularly your assumption A1) which is the key assumption I believe, compared to A1')?

Minor points:
- Bottom of page 2: close not closed
- Under lemma 5, should be j \in [A] not j \in [D]?
- The setting of having a changing regularisation strength (in classifier learning stage paragraph just before sec 5.2) is quite strange/not standard. Can you provide a bit more justification for this please?
summary_of_the_review: I'm recommending weak reject, because although I believe the paper is well-motivated and makes some inroads into an important question, I have concerns about some of the theoretical results, the sufficiency of the experimental results to justify the theory, and also some of the intuitive explanations for the theoretical setup.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proves the feature learning ability of a 1-hidden-layer network (Theorem 1), under the assumption that the data is generated from a dictionary learning model. Additional result on the limitation of no feature learning and no input structure is also provided (Theorem 2-3). The proof proceeds by closed-form analysis of gradient dynamics, which is possible thanks to the simplicity of the data-generation mechanism. Authors empirically verified their claim on synthetic and semi-realistic experiments.
main_review: **Strength**:

* A novel analysis of neural learning that connects the learning performance with its ability in adapting to input structure. The analysis is made accessible due to the explicit assumption on data-generation mechanism, which I believe is sufficient given the early-stage of this line of work.
* The theoretical results are empirically verified.

**Weakness**:

This work can greatly benefit from expanding the coverage of the experiments, in terms of data-generation models, sample size and data dimension, etc. Specifically

* Expand the experiment coverage in terms of sample size / data dimension (and optionally other axis such as class imbalance). Since we are stating the main theorems in terms sample size / data-dimension. I wonder if author can expand the first two sections of experiments ( "Simulation: Verification of the Main Results" and "Simulation: Feature Learning in Networks.") to test the robustness of the claim and understand the learning behaviors in a variety of sample size and dimension settings. 

* Evaluation in "Simulation: Feature Learning in Networks.": This section seems to be rather crucial in supporting the theoretical claims. However, most of the results reported are qualitative (Figure 2). Please consider reporting quantitative result (e.g., in terms of certain distance measure between model features and the ground-truth $M$), and examine across different data dimensions,sample size, and optionally with respect to class imbalance, etc.

* Please discuss (in problem setup or in conclusion section) the expressiveness of the function space defined in (1). In particular, what type of data generating function is not yet covered by such model? (e.g., there is a nonlinear corruption process involved in the data-generation mechanism). Correspondingly, in the experiment section (e.g., "Simulation: Verification of the Main Results"), it might be also extend the experiment to more flexible data-generation mechanisms (say y=NN(x) where NN is a 1-layer network) to verify if the result still holds and in what extent.


Minor:

* Clarity: "(A1’) The patterns are independent, and ...". Please clarify, do you mean the patterns in A is independent from the labels?
summary_of_the_review: A novel theoretical analysis that connects neural model's learning behavior to its ability in adapting to input structure. The analysis is done under a simple data-generating model and was relatively accessible. Author empirically verified their claims in simulation experiment. which slightly weakens the quality of this contribution.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The problem of generalization in over-parameterized neural networks is of wide interest to the theoretical machine learning community, and this paper studies this problem from the lens of understanding structures present in feature distributions. The authors present a model for learning neural networks where the decision function can be expressed in terms of a set of correlated features and demonstrate that gradient descent recovers low generalization error under these assumptions. The authors demonstrate that in the absence of structure (i.e., when features are independent of each other), no algorithm can recover low error, which hints at how data-dependent feature learning is necessary for generalization in neural networks.
main_review: Strengths:
- The paper presents an interesting analysis of gradient descent under data-dependent feature distributions and the results appear to be novel.
- The paper is well-written and provides a good summary of related work (esp. in the Appendix).
- The experimental results, albeit limited, are encouraging.

Questions and Concerns:
- Can the authors elaborate on the relationship between network depth and the "emergence" of good features under the model considered herein?
- Can the authors provide explicit details on the improvements / differences with comparison to the results in Daniely and Malach (2020), specifically the lower bound?
- Can the authors provide some formulations for capturing class-dependent feature distributions in real-world problems? The definition assumes such a distribution exists, however one can think of several counterexamples (e.g., occlusion in visual domains) where "class-dependent" nature of features is not apparent.
summary_of_the_review: Overall I like the paper, and I think there are certain interesting results that are demonstrated, however, I believe the authors should elaborate more on the nature of the feature correlations considered: currently their model assumes two types of features, i.e., ones that are correlated with labels, and the ones that aren't. It perhaps would be interesting to examine whether this assumption can be weakened to something that holds stochastically over the data distribution, as such precise models for data generating processes are hardly available in practice (and are usually substituted by generative models).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper delves deep into learning dynamics of a one-layer neural networks and presents a class of functions and input distributions on which one layer neural networks trained with gradient descent learn well while no data-independent embedding map of the input to a polynomial number of dimensions can learn these function/distribution combinations without using weights which are exponentially large.
The main message seems similar in spirit to the paper titled “Learning Parities with Neural Networks” by Daniely and Malach, but as opposed to the artificially created problem of parities, the current paper presents a function/input distribution combination which is closer to distributions seen in practice. An additional result they show is that in the absence of any input structure the learning problem becomes hard under the statistical query model.
Finally the paper concludes by showing some experiments to support their claim that input structure is necessary to explain the good learning capabilities of neural networks.

main_review: The primary results of the paper are theoretical. It is well-written and clearly presented. An extensive discussion of the related work together with a clean crisp and highly relevant message on the role of input structure in explaining the learning capabilities of neural networks are some of the strengths of the paper. The experiments are also interesting although not very comprehensive (which is fine as the paper’s primary contributions are theoretical).
The only aspect where the paper lacks is perhaps that the main results and the techniques used seem very similar in spirit to those of Daniely and Malach (2020). Firstly, the lower bound to show that in the absence of any input structure learning can’t happen follows almost directly from a similar lower bound in Daniely and Malach (2020).
Given this, the main contribution of the paper is in showing the power of neural nets over data-independent kernel methods. Here, the paper does go into greater detail (in the Appendix) to contrast the contributions of current work to those of Daniely and Malach (2020) but it is not clear how technically novel the current analysis is. The phrase “Input structure” is a bit vague as one can argue that Daniely and Malach (2020)’s result also shows the importance of “input structure” (since their result shows that parities are learnable only under a certain input distribution). A key technical difference seems to be that the current setup requires a second gradient step to find the right patterns to focus on. This indicates that the current setup is more challenging to learn that the parity problem Daniely and Malach (2020) focus on.

Questions and suggestions:
1.	It would help to explicitly mention that the set A is fixed across inputs when describing the setup.
2.	Condition (A1) seems to not hold for the parity example (Example 2 in page 4)? Can you elaborate on how this condition is satisfied in the case of parities?

Minor typos and comments:
1.	Page 9: “chaning” -> “changing”
2.	In Theorem 1, k is Omega(log^2(m)) and m itself is Omega(k^12). This seems like a circular dependency. Can write this more clearly perhaps by using Theta instead of Omega in the appropriate place?

summary_of_the_review: The paper studies a very central problem in developing an understanding of deep learning today. It builds on a line of literature which theoretically capture settings where neural networks trained with gradient descent are provably more powerful than data-independent kernel methods. Moreover, they authors clearly outline the mechanism by which neural nets derive their additional power. Albeit a limited novelty (due to similarity to prior work), I believe the paper’s contributions are quite significant thereby I believe it clears the bar for acceptance at ICLR.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper gives results for learning a simple classification task by training a 2-layer NN with truncated ReLU activations. They also prove some lower bounds suggesting the necessity of the some of the model assumptions. From these results they try to infer that (a) their algorithm goes beyond the kernel/NTK regime and (b) the features learned are data/input specific and the task cannot be accomplished with oblivious features (such as random features).
main_review: +  a simple model
+ a positive learning result analyzing GD
+ a relevant lower bound

- the model is very specific with many assumptions ensuring that the GD analysis works out (e.g., irrelevant attribute effects are balanced out)
- all the interesting action in the upper bound happens in the first two rounds of GD, which suggests that this particular problem can also be solved by simple combinatorial methods
- the claimed SQ lower bound simply consists of showing that the parity function fits the model (i.e., no new lower bound insight here)
- it is not clear that kernel based learning cannot solve this problem; the text suggests this but I could not find any proof/evidence in the paper
summary_of_the_review: The contributions of this paper, in my view, are a simple model that seems to require learning input-specific features, and a careful detailed analysis of the first two steps of GD applied to a 2-layer network with truncated ReLU activations. I think these are interesting, but might not be sufficient to justify acceptance.
review_title: null

Meta-review: The authors theoretically analyze learning of two-layer neural
networks by gradient descent with respect to a data distribution that
exposes how useful features are learned during training.

Overall, the reviewers felt that the analysis yielded useful insight,
and was original.

During the discussion period, a reviewer recommended that the authors
look at papers providing lower bounds on statistical query learning of two-layer networks,
and consider comparing the lower-bound technique of this paper with that earlier work.
Decision: Accept (Poster)