Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies ReLU-activated two-layer neural networks. The main contribution is that unlike traditional deep neural networks (DNNs), this type of polynomial neural network (PNN) also learns high-frequency information quickly. This claim partially verifies why PNNs are suitable for tasks like face recognition, where high-frequency components are crucial for performance. 
main_review: The paper is well written and explains the problem as well as the approach clearly. I appreciate the authors for spending their time polishing the writing, providing clean theorems, and reviewing the literature.

I also think that the problem presented here is meaningful and worth further studying. The fact that PNNs well learn high-frequency signals while general NNs don't indicate that some unique attributes of PNNs enable the model to retain a certain level of signal-to-noise ratio. The existing and current mathematical analyses on this open problem have shone a light on practical applications. Personally 

One of the main concerns is that the paper studies only two-layer PNNs, which is restrictive. The authors stated in the abstract that "we expect our analysis to provide novel insights into designing architectures and learning frameworks..." But it seems to me that two-layer NNs may demonstrate significant behavior compared to DNNs. For example, I am not sure if the fairness of two-layer NNs extends to deeper models. Also, the analysis leverages an infinite-width assumption, far from being practical. 

Another concern is regarding the experiments. The experiments considered the performance of NNs with more than two layers. Though the previous theoretical analysis does not apply to this setting, more layers make the scenarios more practical. But given the scale of the experiments, I think it might be reasonable to consider other supervised learning methods here. Alternatively, as the setting already violates the two-layer assumption, maybe it is appropriate to consider practical applications with high-dimensional and large datasets. 

Finally, I suggest the authors provide a better discussion in the related work section. Currently, it contains only two paragraphs, not delivering sufficient insights. In particular, it would be good to add comparisons (theories & techniques & proofs) between the essential references and the submission, i.e., what makes the paper special?

summary_of_the_review: I like the writing quality and the problem. While it is common to start with simplified models for theoretical analysis, I expect a more profound theorem addressing broader PNN families given the existing work. I appreciate the authors for discussing the prior work and performing experimental comparisons. But I think both aspects are subject to further improvements, i.e., the experiments should emphasize practicality, and the literature review could help differentiate the paper's contributions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a theoretical analysis of the RKHS of the NTK of two-layer polynomial neural networks without bias terms or nonlinear activations. The primary difference between these networks and standard ReLU networks is the presence of (elementwise) multiplicative skip connections, which the authors show (both in the NTK analysis and experiments) improves the convergence rate for higher frequency target functions. 
main_review: Main strengths of the paper
1. Ability to control the spectral bias of neural networks is an important and mostly open question, at least for networks that operate on high-dimensional inputs. This paper offers a valuable step in this direction by showing that multiplicative connections reduce the low-frequency bias of neural networks.
2. The paper is clearly written.

Main limitations of the paper
1. The theoretical contribution is limited to a very restrictive model: 2 layers, no nonlinear activation function, no bias term, and many more data points than parameters. Further, the analysis is in the NTK regime, which assumes that width tends towards infinity and learning rate tends towards zero.
2. Although the experiments do test violating the 2-layer assumption and the NTK regime assumptions, they remain restricted to very low dimensional problems (1D synthetic functions and 2D images) where, to the best of my knowledge, a neural network would not be the go-to method in real applications.
3. The related work section is very sparse. This should include prior work on spectral bias of ReLU networks (some of which is included in the introduction, but not all--for example, https://arxiv.org/abs/1906.00425 and https://arxiv.org/abs/2003.04560). It should also include other methods that affect spectral bias, for example https://arxiv.org/abs/2006.10739. 

Low-level suggestions
1. Claim 2 could be more specific. Upon a first reading of “standard inverse problems in imaging” I expected some 3D imaging or CT or MRI experiments, but this is actually referring to 2D image denoising.
2. Equation (1) uses the “mode-m vector product”. A quick search showed me the definition of this operation, but it would be easier for the reader if this were defined in the paper (perhaps with examples in the case of vectors and matrices).
3. Equation (2) could be visualized with a simple diagram of the 2-layer pi-net you analyze.
4. It would be helpful for the last sentence of section 3.3 to mention the Schur product theorem as justification.
5. It would be helpful to more clearly delineate the difference between the first and second experiments in section 4.1. As far as I can tell the difference is that the first uses large width and low learning rate and the second uses a smaller width and larger learning rate (to violate NTK assumptions), but these should be stated explicitly.
6. Figure 2 is not very convincing--actually I find Figure 11 in the appendix to be a more compelling comparison, both visually and in terms of the relevance of the comparison.

summary_of_the_review: The paper offers an interesting approach to reduce the spectral bias of neural networks by introducing multiplicative connections, and supports this claim with NTK analysis of shallow networks and experimental evidence on low-dimensional synthetic and real data. Although both the theoretical and experimental contributions are rather restricted, I hope they will serve as useful building blocks for subsequent research on more realistic models and data.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper is dedicated to the study of spectral bias in polynomial neural networks. For feed-forward neural networks with ReLU activation function it is well-known that learning high-frequency terms is made slower (Rahaman et al.). 

Authors claim that polynomial networks are able to learn both low frequency and high-frequency terms almost equally fast. Theory, based on spectral analysis of an integral operator associated with the NTK kernel, is provided.  Theoretical approach was taken from arXiv: 1905.12173, but for NTK kernel of the network with an additional multiplicative interaction layer. 
Then, experiments that support claims are provided. 
It is claimed that multiplicative interactions in the architecture of a NN may be the reason for an ability to learn high frequencies. 

main_review: Note that the network (7) for which NTK kernel was calculated and spectral analysis is made, is not a Π-Net (because it includes ReLU as sigma). So, why can we apply the spectral analysis to Π-Net architecture?

Experiments seem to support the main claim, though fig 5 shows that the difference from standard network is not so sharp. Eventually, it seems that the standard network is also able to learn the high frequency. Also, experimental setups are taken from well-known papers. 


summary_of_the_review: The narrative is well structured and easy to read. The main claim is partially supported. Weak aspects of Π-nets are not discussed. I would assess that it is a borderline paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper gives an analysis of polynomial networks in the NTK regime. They show a theoretical speed-up in learning higher frequencies when using polynomial networks. They also have some experiments that verify these properties. 
main_review: Overall I think this paper is well organized and well written. The proof of this paper seems solid. The main theoretical contributions of this paper are Theorem 1 and 2. Theorem 1 gives the kernel limit of two-layer $\Pi$-net. And Theorem 2 computes the eigenvalues of the linear operator. Given the techniques used in reference [9], the proof of Theorem 1 and 2 are quite strict forward.  The empirical results are quite clear and well supports the main theorem. It's is quite interesting that $\mu_{k} = \Omega(k^{-d/2 -2 })$ rather than $\mu_{k} = \Omega(k^{-d - 1})$.  What will happen if we increase the number of layers or the degree?
summary_of_the_review: This paper is well organized and well written.  The proof is solid, and the empirical results support its claim. However, given the previous paper the, proof techniques are not novel. Therefore, I would only suggest a weak acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers a simplified model of the polynomial neural network, and shows that the eigenvalues of the induced tangent kernel have a slower decay rate, compared with the classical two-layer network. This also means the polynomial neural networks can learn the high-frequency components faster. The empirical evidence supports this tendency.
main_review: Strength: This paper provides an interesting viewpoint to explain why polynomial neural network performs better than feedforward neural networks in some vision tasks. The story is that PNN learns high-frequency components faster, and high-frequency components matter in these specific tasks.

Weakness:
1. Oversimplification: the model this paper analyzes can hardly be seen as a 'polynomial network'. It has two layers, which at best can express a quadratic function. For a two-layer structure, I see no necessity in forcing the $\Pi$-Net formulation. Additionally, the original PNN has no non-linear activations, while the simplified two-layer model has ReLU activations.  While I understand that the spectral analysis in previous works is performed on two-layer nets, the authors should at least explain in the paper why not analyze the full-rank polynomial network and why the ReLU activations. Currently, I feel the theoretical results for the two-layer model cannot really be applied to the PNN in practice. 
2. Technical Novelty: I feel the technical novelty is lacking. The only novel contribution of this paper is to show the decay rate is slower. And to calculate the order of the eigenvalues, most efforts have been done in previous papers, except the arguments from equation (28) to equation (32). The eigenvalues of $\kappa_1$ and $\kappa_2$ are calculated in [7]; and 'larger eigenvalues imply faster learning' is proved in [9].

3. Mathematical Rigor & Presentation: it would be better to reformulate the arguments from (28) to (32), by building up inequalities between the eigenvalue and terms that are calculated. Currently, the proof looks very sloppy. When setting up the mathematical notations, it is better to keep the paper self-contained. For example, the mode-$m$ product is not introduced here. Another drawback is that the main body does not introduce why larger eigenvalues imply faster learning. This may cause a less informed audience at loss.


summary_of_the_review: While the topic and story of this paper are interesting, it has several drawbacks that need to be addressed. The setting is very restricted, and the theoretical results lack novelty.



========Post-rebuttal updates===========

I raise the score from 3 to 5, given that the presentation of the updated version is more rigorous and clear.
review_title: null

Meta-review: *Summary:* Investigate the NTK of PNNs and enhanced bias towards higher frequencies. 

*Strengths:* 
- Spectral bias is a contemporary topic. 
- Some reviewers found the paper well written.

*Weaknesses:* 
- Restricted setting (two-layers / no bias / infinite width), particularly in view of the objective to provide architecture design guidance. Restricted experiments (Introduction indicates learning spherical harmonics). 
- Sparse discussion of related works, particularly on spectral bias. 

*Discussion:* 

During the discussion period authors made efforts to address some of the concerns of the reviewers. A late new experiment prompted KnZp to raise score. TQnp found the paper good but also expected a more profound theorem addressing broader PNN families given the existing work. They found that experiments and discussion of prior work could be improved. The authors added discussion of prior works and provided an explanation for their choices, but left extensions and further analysis for future work. nFMY expressed concerns about applicability of the analysis and evidence in experiments. Author responses addresses this in part. cEcf points out that the main theoretical contributions have straight forward proofs based on previous works and asks about extensions. Authors agree that the paper does not introduce novel techniques and that extending the analysis is an important direction, but leave this for future work. FuRi finds the paper provides an interesting viewpoint and raised score from 3 to 5 following the discussion (improving presentation, rigor, clarity), but considers that the paper has several drawbacks (oversimplification, lack of technical novelty) that need to be addressed. 

*Conclusion:* 

One reviewer found this work marginally below the acceptance threshold, three marginally above, and one good. I find that the paper considers an interesting problem and makes some interesting observations and some valuable advances. I appreciate the authors’ efforts during the reviewing period. Hence I am recommending accept. At the same time, I find that, clarity, technical and experimental contributions still can be improved and encourage the authors to carefully consider the reviewers comments when preparing the final version of the paper.
Decision: Accept (Poster)