Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors extend the theory of [6] for mild overparameterization where the student has one or two more neurons than the teacher (ReLU activation function).
For several chosen families of local minima, the authors give an analytic description in terms of the loss at these minima and their Hessians. The neuron additions can turn minima into saddles, "minima of lesser symmetry" needs more neurons for turning them into saddles. 
strengths_and_weaknesses: Originality: The paper extends the theory of [6]. Although the existence of local minima in the asymptotic regime and characterization in [6] is exciting as an example neural network landscape with provable local minima families, I find the contributions of the current paper somehow incomplete, therefore less attractive. 

Quality: The analysis techniques are non-standard. I did not have time to check the proofs, but the results look rigorous. No experiments are presented in the main text, for example, to justify the claim of why type-II minima are more attractive. 

Clarity: Although individual sentences usually can be understood, the technical terms used in this paper are hard to follow. Table I is incomprehensible, the caption refers to the material in the later sections, instead of explaining the table. The spectrum column cannot possibly represent the full Hessian spectrum since there is a scalar value, does it refer to the min. eigenvalue of the Hessian? What are the r and n representations? 

Significance: I think it is an important problem to classify all the critical points of the neural network landscape in the paper. This analysis can pave the way to explaining the difficulties in training mildly overparameterized networks. However, the paper only classifies a few types of local minima points in the asymptotical limit, and it is not even clear whether the dynamics would converge to these points or not. 




questions: Is there any local minima of type $\Delta S_{d-p} \times \Delta S_{p}$ where $p>2$? As far as I see, only $p=\{0,1,2\}$ are discussed (also, some overparameterization). 

line125: I don't think it is trivial at all whether the two-layers setup can be studied in the same way as the one-layer setup studied in the paper. Can the authors please comment on this? As far as I see, also in the reference [6], only the one-layer case is studied. 

Typos/detailed comments:
line 60-61: adding one neuron results in these minima ... unclear sentence
line 101: citation needed
caption of Table1: I don't understand how lines 4-6 and lines 10-12 are related to the table. 
line 116: $\mathcal{L}(\sigma W, \sigma \alpha) = \mathcal{L}(W, \alpha)$ for two-layers networks. However, the authors only study the committee machine setup where the second layer is fixed at $1$. Why not introduce the setup already in this form in page 1 (Eqs~1 and 2)?
line 152: definition of inclusion is unclear to me 
line 289: (typo) so turn minima -> to turn minima 
line 367: what is meant by non-integer values of $d$? 


limitations: The paper is written in a neutral way, and the written text reflects the findings in the theorems.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper concerns about the structure of critical points and how local minima change to saddles in over-parameterized regime in the case of 2 layer ReLU networks, square loss, and labels created by planted model. Using symmetry structure of loss function and considering certain symmetric types of critical points it is shown that adding neurons can turn non-global minima into saddles, addressing over-parameterized models.
strengths_and_weaknesses: Assuming the reader has enough knowledge of existing work and tools being used, the paper is well-written and addresses the effect of over-parameterization on certain symmetry types of minima and their transformation to saddles. The FPS method for defining spectrum of Hessian looks powerful for analyzing the loss and Hessian at local minima, and Theorem 3 is a good example of Hessian spectrum characterization at certain family of critical points. I like the arguments where adding neurons changes the nature of critical points, like in lines 280-284 and 601-603, as well as Theorem 4, and how different families of minima require different number of additional neurons to turn into saddles. I couldn't digest most of the proofs, except for pages 19-21, as I am not familiar with this line of research revolving around representation theory.

The paper also assumes previous knowledge from previous works and is not highly self-readable; However authors try to familiarize readers with existing work in introduction section.
for example, regarding lines 72-76, authors indicate a previous work and pinpoint that considering symmetry type of minima is important.Also following line 77, the symmetry breaking phenomenon observed in previous works is outlined.
questions: Typo:

lines 599 and 686, table 5.2 should be replaced by table 2. line 527, $M(d+2,d)^{\Delta S_{d-1}}$. line 538, $\Omega_1$. line 606, restricted "to" the. line 619, $M(d+2,d)$. line 250, by section A.7 do you mean section B.1 where you prove Theorem 3?


Questions:

I can't understand why the loss function is in invariant by the group of row permutations (line 116). shouldn't the weights of 2nd layer play a role here? why do you just consider $W$? I think I'm convinced by looking at line 124 where you set 2nd layer to be all ones, but this should come before line 116 to avoid confusion.

What will be the main barrier in using these methods for analyzing k-d>2?

For line 198, where do you show that the loss at type II minima decays as $\Theta(\frac{1}{d})$? and is $\Theta(1)$ loss at type I minima characterized by equations in lines 210-211?

Regarding Definition 2, are there only two types of critical points for all k, d or just the cases you consider? I can see in Theorem 2 you prove there are 1 or 2 family of critical points for specific isotropies. Also for the remarks in lines 337-340, is there any evidence that the 2 families mentioned are representative of other symmetric spurious minima?

for line 200, why it is reasonable for the loss at initialization to be compared to loss in minima?

Regarding line 347, can you point out where in the paper/proofs you assumed V having high symmetry? is it the assumption of $V=I_d$ in line 126?

In section B1, what is an eigenvalue transition matrix?

What is the meaning of subscripts 1,2,3 in $\nabla \mathcal{L}$ in beginning of page 19?


limitations: I don't see any negative societal impact, except for misuse\illegal use of Neural networks.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses the setting of fitting a two-layer networks to a target network with respect to the square loss. They apply novel tools from algebraic geometry to utilize the symmetric structure and characterize how over-parameterization annihilates spurious local minima.  

strengths_and_weaknesses: Strength:
- This is a strong theoretical paper discussing the spurious local minima of two-layer ReLU networks.
- The tools from algebraic geometry and representation theory are novel for the study of local minima in two-layer neural network. The analysis of the families of local minima and Hessian spectrums can bring meaningful results for the theoretical study of two-layer networks.

Weakness:
- The paper should be self-contained. However, the notation is confusing and this imposes difficulty for the reader to understand the contribution of the paper. 
    -  In Line 122, it is said $V=I_d\in M(k,d)$ but here V is a d-by-d matrix and we need to append zero rows to V. It will be better to use another notation. 
    - In Line 152, what does $i_g:\Delta S_d\subset \Delta S_{d+1}$ mean?
    - Some notations are not defined. For instance, what is $\mathcal{L}|M(k,d)^G$ in line 150 and what is $\mathcal{L}|\mathbb{R}^n$ in line 165?
- The optimization variable is conflicted. (W,\alpha) is the pair of optimization variable for the loss $\mathcal{L}$ and a critical point should be in $M(k,d)\times \mathbb{R}^k$. In Line 150, why $c \in M(k,d)$ is a critical point? It seems that the results of the entire paper focuses on optimizing W alone. Please specify what is the optimization variable.
- The paper states that the over-parameterization annihilates spurious local minima but the main theorems (Theorem 2-4) only discuss the cases when $k=d,d+1,d+2$, which is not quite related to the regime of over-parameterization. 
questions: Can the results in the paper be extended to the empirical loss, i.e., the loss function is only evaluated at limited number of data points?

Let $N$ be the number of data points. It is assumed that the labels are generated by a target network with $d$ neurons. Is it possible to generalize the results to a target network with more neurons, say $N+1$? From the Caratheodory’s theorem, an optimal neural network fitting arbitrarily label needs at most $N+1$ neurons. Thus, the results will be more influential if it can be generalized to arbitrary target network.

limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper presents theoretical results on two-layer regression networks with ReLU activations and squared loss. It builds upon a line of work that studies local minima based on symmetries of the loss function (as a function of the weights of the hidden layer). This paper applies and extends previously developed techniques to  the setting where the hidden layer contains more neurons than the input dimension. The new techniques enable the authors to classify local minima in dependence of their symmetry, to provide sharp analytic estimates for the loss at these minima and the spectrum of the loss Hessian, and to thereby understand when local minima of certain symmetries turn into saddles when more neurons are added to the network. 
strengths_and_weaknesses: Strengths:

- The paper applies interesting and novel techniques by combining a variety of mathematical tools.  It builds upon a recent line of work, but applies the approach to a novel setting (where the hidden layer contains more neurons than input dimensions) and thereby requires new ideas and techniques. This results in novel, analytical results that provide sharp estimates on the loss at  certain local minima and the spectrum of the loss Hessian. Interesting results can be then deduced on how minima turn into saddles in dependence of their symmetry class. (Some minima turn into saddles when a single neuron is added, while others require more neurons.) The analytic results do not only provide existence of certain families of local minima, their loss and Hessian, but also their frequency of appearance. 

- While the paper assumes knowledge of the line of papers it builds upon, all theoretical results are proved and detailed calculations are appended in the supplements.


Weaknesses:

- The paper makes a number of assumptions, which questions the applicability of the results to networks in practice:
The authors consider only two-layer regression networks with squared loss in a teacher-student setting, where labels are generated by a target network. The target network is fixed to a weight matrix equal to an identity matrix (stacked with zeros if the hidden layer contains more neurons than input dimensions) and the weights of the output layer equals a vector of ones. (The paper claims that an extension to trainable output layers is possible, but no details or further explanation is given. Similar, the authors write that , while the results assume a target of high symmetry, this would not be necessary, but again without evidence or further discussion.) This restricted setting can be slightly generalized to a hidden weight matrix given by an orthogonal matrix of size input dimension and rest of zeros, but only because of another strong (unrealistic) assumption of a Gaussian input. 

- It is the latter assumption that seems crucial to the entire theory, while also implying that the setting is quite different to a realistic setting. In particular, local minima are classified into groups of symmetry, defined by being invariant under permutations of hidden and input neurons. In particular, the authors want the target network to be invariant under permutations of the input neurons, which seems to require strong assumptions on the input distribution. (Aside, I would appreciate a clarification from the authors why it would be interesting to consider permutations of the dimensions in the input space at all.)

- A second perceived weakness is the lack of clarification how exhaustive the results are. Are all spurious local minima (possible under the given setting) covered by the theory? It seemed to me that the answer is no, and the paper only considers very specific families of critical points.

- The paper should also be better placed in related work. Existence of spurious local minima in networks have been shown previously (using other techniques) and it remains unclear, how the results of this paper relate to these.  To give a possibly, strongly related example, a classical paper by Fukumizu and Amari („Local minima and plateaus in hierarchical structures of multilayer perceptrons Neural Networks“ 13, 2000) provides specific weight combinations (with a certain symmetry) that lead to local minima. To better place the given submission into the related work, the authors could discuss the specific form of weight matrices that are covered by the symmetry classes. (Since the group actions are very specific, they translate to specific weight configuration, which could be made explicit.) Related to this: If one were to translate the results into statements on specific weight configurations in a network, which certainly seems possible, are the techniques to study the local minima necessary, or can the results be interpreted more easily?

-------
Additional Comments:

I appreciated the detailed calculations in the appendix and detailed arguments in some parts. However, I also found that the paper too often assumes implicit knowledge and is not too precise in its use of terminology. I append a list of some of these points, where the presentation could be improved. Despite strong efforts, I was therefore not able to follow all of the arguments in the paper (I did look into the line of work this submission builds upon, but did not study it in detail.)

The authors call the their setting as “overparameterized“, when the hidden layer has more neurons than the number of input dimensions. This is in conflict with existing works that call a network overparameterized when it has more parameters than input patterns to learn.

Line 116  “The loss function is always invariant...“ This only holds if the same permutation as applied to the output weights 

Line 120, the meaning of the equality sign is not defined

Line 126: “L is invariant“. I suppose, the authors mean that the teacher network is invariant. 

Line 134: what means “fixed“? V was a fixed value to start with. Probably, the authors mean “invariant under“?

Line 138: what exactly is meant by the terminology “nondegenerate“ and “spurious“?

Line 138,139 is missing a reference for the empirical evidence

Line 143, reference is missing to the “recent work“

Line 163, The notation G_c(d) is not defined

Line 185: Def 2 requires more explanation “corresponding to the action of delta S“, 
Possibly it should also be discussed in more detail why the diagonal elements converge to either +1 or -1.

Line 198 “Since the loss at type II minima decays...“ Please provide an explanation or a  reference

Line 267 Typo: Adding one neuron should change the second subscript

Line270: “This isotypic component may be written as...“ Please provide an explanation or a  reference

Line 357: This second part of conclusion is lacking context to understand this part. In particular, please revise or explain the following terminology: 
“sink“, “source“, “index“, “local deformation of the landscape geometry“, “bifurcation theory“, “forced symmetry breaking leads to great complexity near the transition but minimal models of complexity can be given“

questions: - Why is it reasonable to study permutations of the input neurons?

- Is it possible to provide specific weight matrices that cover the different symmetry classes?

- Are all spurious local minima (possible under the given setting) covered by the theory?
limitations: The paper makes strong assumptions. It is unclear whether the local minima can be found in practical neural networks. The necessity of some strong assumptions and their consequences are not discussed in detail
review_title: null

Meta-review: metareview: Thank you for your submission to NeurIPS. 

This paper is on the structure of critical points and local minima in over-parameterized two layer ReLU neural networks.

The reviewers and I, after the author response, are in agreement that there are interesting contributions in this work. However, the reviewers noted significant issues with the presentation (see below). Four knowledgeable reviewers recommend accept/borderline accept, and I concur, in light of the contributions made.

The reviewers also noted several weaknesses in the presentation: In particular, the reviewers noted that 
(1) the technical terms used in this paper and notation are hard to follow, which makes the paper not easily accessible
(2) the paper assumes previous knowledge from previous works and is not highly self-readable 
(3) the theoretical assumptions are strong, 
(4) it is not clear whether the results can give insights on practical neural networks.

Moreover, the analysis techniques are non-standard (to most ML theorist, in my opinion). The reviewers most likely did not check the proofs, but feel confident with the mathematical rigor.

The statement of Theorem 1 looks informal, which should either be made more rigorous or stated that this is an informal version of a formal result that appears later.

Please take into account the updated reviewer comments when preparing the final version to accommodate the requested changes.




confidence: Less certain
Decision: Accept