Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the implications of various architectural choices on the performance of neural networks, and how they may break the curse of dimensionality. The authors consider fully-connected, locally-connected, locally-connected + weight sharing, and locally connected + global average pooling architectures. They then show, both theoretically and experimentally, how symmetries in the data may affect these architectures differently, at infinite width or finite width (where weight sharing can play a bigger role) under standard initializations. The authors also observe how the learning rates / slopes of learning curves may improve when the amount of data is large enough, particularly for finite networks. Finally, the authors provide spherical harmonic decompositions of the kernels that arise from infinite-width networks with different architectures -- fully-connected, locally connected, or locally connected with global pooling --, observing that local connectivity provides exponential (in the dimension) reductions in the size of eigen spaces, while pooling provides an additional improvement factor of the number of patches.
main_review: The question of what allows deep learning to learn efficiently by breaking the curse of dimensionality is important for understanding its success, and the paper provides an interesting and comprehensive study of this with both theoretical and empirical findings. Thus, I think the quality and significance of the paper are quite clear, and it is well written, thus I recommend acceptance.

Below are a few minor comments:
- When comparing LCN to VEC, the phrase "the opposite is also true" is a bit confusing, since this actually requires more parameters
- The setting of Figure 1 was a bit difficult to grasp and could be better explained (in the text or caption). If I understand correctly, the same spurious transformation is applied to each example? Also, the y axis lacks a label.
- For DIDE, do you have an idea/conjecture of what additional "priors" are being learnt by the networks at large data regimes for improving these slopes?
- It would be helpful to add a paragraph after Theorem 4.1 explaining how the improvements in dimensionality/spectral gaps may improve learning efficiency (instead of simply pointing to the appendix)
- Note that similar questions regarding benefits of locality and/or pooling in kernel regimes have been studied in a few recent papers, e.g., [here](https://arxiv.org/abs/2102.13219), [here](https://arxiv.org/abs/2102.10032), [here](https://arxiv.org/abs/2106.08619). It would be good to provide comparisons at least in the final version of the paper.
- typos: L74 "even" -> "even when"?; L163 "Kernelss"; L277 "unrorated"; L305 "harmonic" -> "harmonics"


-------- update after rebuttal ----------
Thanks for your response. The discussion raised some concerns regarding clarity, and I hope the authors can address these (see comments by reviewer XBfK). Nevertheless, I think these are minor issues which can be addressed for a final version, and the authors' last response to reviewer XBfK makes me confident that they will be properly addressed, thus I decided to raise my score.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposed an viewpoint to analyze deep learning methods as an integrated system of data (D), models (M), and inference algorithms (I) by studying the symmetric of the triplet (D, M, I) (in terms of transformations) on specific network models for vision including fully/locally connected networks (F/LCN), convolutional network w/o pooling(VEC/GAP). The key result in symmetry is that when networks are initialized with i.i.d. standard Gaussian distribution, then the considered neural networks are invariant against orthogonal group on the flatten input space when networks are over-parameterized.  
main_review: 1. In the DIDE experiments for $VEC_n$, the authors claim that in Figure 3, the learning curve is dramatically speedup in the larger data set regime (# of samples $> 2^{12}$). However, the orange curve does not seem to have dramatic speedup from $2^{11}$ to $2^{15}$ comparing to the rest of the learning models. The authors then claim that it is because the model prior is too large (since $GAP_n \subseteq VEC_n \subseteq LCN_n \subseteq VEC_{dn}$ in (4)). I am not sure if Theorem 2.1 is able to interpret this empirical results. A more thorough discussion is needed.

2. The explanations on the experiment results in Figure 4 (middle) are not clear to me. Do you mean when the images are rotated, it is harder to learn but when as the number of the training samples increases, its become easier to learn (due to DIDE)? Why the red dots are not aligned with the orange dashed line then? How do you make sure the transition of the red dots is entirely due to DIDE? An ablation study is needed. It is possible to understand the benefit of DIDE in a more theoretical manner?

3. The explanation on Theorem 4.1 is also not clear to me. Why there are drops of eigenvalues in Figure 5? Can these drop be explained by Theorem 4? How does the proposed analysis on pooling connect to some existing works on analysis of pooling, e.g., [1]?

[1] Lee, C.Y., Gallagher, P.W. and Tu, Z., 2016, May. Generalizing pooling functions in convolutional neural networks: Mixed, gated, and tree. In Artificial intelligence and statistics (pp. 464-472). PMLR.
limitations_and_societal_impact: No potential negative societal impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper tries to understand why a convolutional neural network and its variants with a proper training algorithm can learn to recognize images with only limited training data. Theoretically, by considering the data, model, and inference algorithm as a system, the authors study the symmetries of several different systems, and compute and analyze the eigendecomposition of their corresponding one-hidden-layer infinite-width kernels on spherical input space. The authors also did experiments to study how the symmetries affect the performance of different models on different data and validate their theoretical results on eigendecomposition.
main_review: Originality: It is interesting to study the data, model, and training algorithm as an entire system and analyze its symmetries, which differs from previous research. The related works appear to be adequately cited.

Quality: The theoretical results in this paper seem to be correct, and they are supported by the experimental results.

Significance:

- The justification for analyzing the symmetry of the data-model-algorithm system seems unclear. This is my major concern about this paper. The authors theoretically showed that different systems have different basic symmetries, and empirically demonstrated that changing the symmetries can affect the performances of the trained models. However, the reason why this change of symmetry is the cause for the change in performances is unclear. The authors did not seem to provide strong theoretical evidence or insights explaining the relationship between symmetry and performance. Besides, in the experiments, changing the symmetries implicitly changes a lot of other factors. For instance, an image with each pixel "rotated" on the channel space is no longer a valid image. It might be better if the authors could provide more theoretical insights about the relationship between symmetry and performance so the experimental results can be better justified.

- Studying the data-model-algorithm system as a whole seems to make the analysis in this paper more complicated than directly analyzing the model structure or the data. The symmetry in this paper is defined on the entire system, but this property mainly comes from the symmetries in the model. It also depends on the distribution used for initialization and the training algorithm, but these are almost fixed in reality. Besides, when doing experiments, the authors are also changing one variable at a time. Therefore, it seems unclear why the authors want to analyze the entire system, which is a more complicated object than individual components.

- The authors computed the eigendecomposition of different models' one-hidden-layer infinite-width kernels on a particular input space and validated their results by experiments, but this setting might be too specific, making the results somewhat restricted.

Clarity:

- This paper might contain too many claims, and there seems to be a lack of focus. It seems from the abstract and the conclusion section that the authors want to emphasize the important role of locality in helping neural networks escape the curse of dimensionality. However, in the introduction section, especially the contribution part, the authors are making a lot of claims and listing many results, which may confuse the reader. It might be better to shorten the introduction and perhaps re-organize these parts to focus more on the main claim of the paper. Besides, at the end of section 3 where the title is about symmetries, the authors are talking about DIDE, which may be only related to the training data. Moving this part out as a separate section may improve the flow of this paper.

- Some of the experimental details, e.g., the hyperparameter settings, are not mentioned in this paper, which makes their experimental results not convincing enough.

- There are some other parts of the paper that may need minor improvements, and the details will be provided in the "Minor Comments" section below.

Minor Comments:

- In line 85, the authors claimed that "we prove the opposite is true". What they actually prove is that the function class of $LCN_n$ is a subset of that of $VEC_{dn}$, but the direct opposite seems to be $LCN_n$ versus $VEC_n$. Therefore, this claim may seem a bit misleading.

- For section 2.1, the authors provide many formulas for different network models, and it might be better to also have some figures for the network models so the readers can better understand them.

- In line 190, the notation "$=^d$" is not defined.

- In Figure 1, the y-axis is not defined, and the second subfigure has no legend.

- In the experiments in Figure 1 and Figure 3, the authors did not mention the stopping criteria for the training process and it is unclear whether they run each experiment multiple times. They also did not mention why they choose the experimental settings NN/NN+/NN++. These may make their empirical results less convincing.

- Section 4 ends with a theorem and the implications of this theorem are in the appendix. It might be better to summarize the implications in the main text to improve the flow of this paper.

Typos:

- Equation 2: "$\sum_{j=1}^{n^l}$" -> "$\sum_{i=1}^{n^l}$"
- Equation 3: "$\sum_{\alpha\in[d]}$" -> "$\sum_{\alpha\in[d],i\in[n]}$"
- Line 167: "where is the infinite width limit of $\Theta$" -> "where $\Theta$ is the infinite width limit of $\hat{\Theta}$"
- Line 262, 271, 279: "Fig. S2" -> "Fig. 4"
- Line 270: "which" -> "which is"
- Line 274: "the dataset grows, ...... as that of" -> "as the dataset grows, ...... that of"

---------------------Update--------------------------

I have read all the other reviews and the authors' responses, and I have decided to increase my score by 1, i.e., I think it's on the borderline and slightly leaning towards rejection. The detailed reasons for this are provided below:

- After reading the authors' response, the justification for analyzing the symmetries of the data-model-algorithm system becomes more clear to me. Thank the authors for providing examples explaining the role of symmetries in the system, and I agree with the authors that understanding these symmetries is an important step towards understanding the empirical success of convolutional neural networks. It might also be better if the authors could explain more about this in their paper to help the readers better understand the importance of this topic. 

- My current major concern is the clarity of this paper, which is the main reason why I am still tending to reject this paper. On the one hand, this paper seems to have a lack of focus. The authors included a lot of content in this paper, but the structure and organization of these contents might need some improvements so that the readers can better understand the core idea of this paper. As I suggested in my original review, a more concise and clear introduction might help a lot. On the other hand, as also suggested by the other reviewers, there are many things that need further clarifications, e.g., the insights and consequences of Theorem 4.1, the "Conjecture/Ideas of DIDE", more detailed experimental settings and explanations, and comparisons to some prior works. These modifications may require a major revision of this paper. Therefore, the current form of this paper is perhaps not ready for publication.
limitations_and_societal_impact: The authors briefly discussed the limitations of their work at the end of this paper, and it may be better to talk more about them. I do not see any immediate negative societal impacts of this paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the symmetries of the the system (Arch, Data, Algorithm) and provides extensive empirical results. the paperis well-written and flows nicely.
main_review: 
Advantages:

- Understanding symmetry in Deep Learning is still a major open question. This paper introduces a new framework to characterize this symmetry by considering intergated (arch, data, alg) systems. 

- The empirical results support the claimed symmetries although (the symmetries) they're not very accurate in some scenarios.

- The paper is well-written


Weaknesses:

- The bulk of the analysis relies on the NTK and NTK parameterization. It is now well known that the NTK regimes does not capture what happens in deep neural networks (see, e.g. Yang et al. Feature Learning in Infinite-Width Neural Networks). Does the analysis extend to the standard parameterization (i.e. without the 1/sqrt{n})?
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper studies how symmetries and biases associated to various architectural choices may alleviate the curse of dimensionality. The reviewers found the methodology employed by the authors interesting, and generally appreciated the various observations and experiments provided in the paper. That said, the reviewers raised several critical concerns pertaining to presentation (experimental details, in particular), clarity, and focus. Despite the considerable discussion this paper has generated among the reviewers, opinions remained divided whether a substantial revision is needed before the paper can be considered for publication.
Decision: Reject