Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper theoretically study a one hidden layer neural network with ReLU activation trained using Gaussian data, and analytically derive the values of the different classes of local minima of this objective, and the spectrum of the Hessian at these local minima. The results show that as the degree of over-parameterization is increased, the local minima transform into saddle points in the loss landscape, and further find the exact fractional dimension at which this transition occurs. 

Note: I am not familiar with the mathematical tools used in this paper. So my comments pertain to the utility of the findings and claims made in the paper.
main_review: Introduction and section 1 describe the problem setup. In section 2, the various class of local minima are derived analytically and the difference in the decay of their Hessian spectrum is discussed. Section 3 reveals the spectrum of Hessian of the families of local minima discovered in theorem 1, and shows that the bulk of eigenvalues are small positive values while a small subset of eigenvalues grow linearly with d (the dimensionality of the hidden layer of the target network). In section 4, the authors develop a symmetry-based framework as a way to analytically derive the power series representation of minima and the Hessian spectrum.

strengths:
- the paper studies an important problem in deep learning optimization.
- the paper provides a currently less mainstream approach to study 2 layer ReLU network with the goal of deriving the form of local minima and spectrum of the Hessian at these minima.

weakness:
- the theoretical results are not properly motivated and their implications are discussed. More on this below.
- some of the claims in the paper are misleading or not true. See below.

Detailed review:

- It is not explicitly mentioned anywhere but the dimensionality d of the input vector x is assumed to be the same as the dimensionality d of beta (number of neurons in the hidden layer) in the target network (Eq 2). What is the reasoning behind this and what are the implications of this assumption on the outcome of the analysis?

- It would be nice to establish a connection between dimensionality d and the number of classes C in a classification task (at least intuitively). This would be particularly helpful because it has been shown in [1] that the eigenvalues of the Hessian tend to have C large eigenvalues while the others are nearly zeros. So the dependence on d in the submitted paper should clearly have some connection with C.

- the main statement of section 1: "Spurious minima break the symmetry of global minima" and figure 2, are not very clear. Perhaps a more intuitive explanation of this statement and describing the physical significance of this claim would help.

- On line 117-120, the authors cite [48,49] while claiming that (specifically) local minima lie in fixed low-dimensional subspaces of the parameter space. However, the cited papers do not mention the minima found were local. In fact fig. 1 in [48] suggests the minimum is global.

- section 2 derives the analytical form of the various classes of local minima and the difference in the decay of their Hessian spectrum is discussed. While this is a strong result, it would be informative to also discuss how these differences can impact gradient descent based optimization (e.g. in terms of the likelihood of discovering these minima) or other physical significance of this result. 

- One of the claims in the paper (e.g. line 323-329) is around the exposition of how the proposed theory explains why local minima are not major limitation in over-parameterized deep networks since over-parameterization turns local minima into saddle points. However, this claim is not novel and has been known at least since [2] if not before.

[1] Sagun, Levent, et al. "Empirical analysis of the hessian of over-parametrized neural networks." arXiv preprint arXiv:1706.04454 (2017).

[2] Dauphin, Yann, et al. "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization." arXiv preprint arXiv:1406.2572 (2014).

Because of the above concerns, I am giving a score of 6 to the paper. If addressed, I am willing to increase the score.
limitations_and_societal_impact: see main review for limitations.
Societal impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Under a student-teacher setup with unit Gaussian input, this submission studies the Hessian of a finite-width two-layer ReLU network at critical points of the (population) MSE loss, and characterizes the spectrum and loss at different minima. The starting observation is a symmetry-breaking property based on which a power series description of the minima can be derived, which then leads to an analytic description of the Hessian (up to a dimension-dependent residual). The analysis reveals interesting non-asymptotic properties of the landscape of two-layer network.
main_review: ## Strength

The non-convex landscape of neural network is an important subject of study in deep learning theory. 
To my knowledge, most prior works studying the spectrum of Hessian (or the Fisher / NTK) considered the model at random initialization, for which exact description is possible in certain asymptotic limits (e.g., proportional scaling of the network width and input size). In contrast, this submission derived an analytic description of the Hessian for finite-width models at critical points (up to $d^{-1/2}$ terms). This setting leads to a number of interesting findings, including  
(i) the similar spectral properties of the Hessian at the global and local minima.  
(ii) skewed spectrum of the Hessian.   
(iii) the different decay rates of loss at different local minima.  

## Weakness

1. The theoretical setup is a bit idealized, for the following reasons.
- The analysis only deals with the population loss (with unit Gaussian data); hence it is unclear if these findings can be translated to the more common setting of empirical risk minimization. 
- The assumptions on the target network in Theorem 1 and 2 (i.e., identity first-layer and all-one second-layer) are quite restrictive. 
- The current study does not cover the $k>d$ case, which is interesting due to the presence of overparameterization.
- The analysis does not take optimization into account. As the authors noted, gradient descent starting from standard initialization favors certain minima over others, so a more practically relevant object to study would be the Hessian of a trained neural network. 

2. The writing and readability of the manuscript can be improved.
- The main theorem is lengthy and not easy to parse. It would be nice to add some more interpretation of the result (especially the structure of $W(d)$), or defer the complete statement to the appendix.
- What is the setting of Figure 1 (right)? Is it still the case that $k=d$, and both are growing? If yes, then this is probably not the typical notion of overparameterization (which corresponds to fixing $d$ and increasing $k$); if not, then this setting does not align with Theorem 1. 

**Additional Comments and Questions**

1. It is mentioned that the same analysis can be applied to other choices of target network. Can the authors comment on the difference and similarity we should expect under a more general setting?

2. The finding that minima with almost identical Hessian spectra can have distinct loss is interesting. Is there an intuitive explanation of why these different loss solutions all have similar Hessian spectrum? 

3. Some relevant papers: 
- In the overparameterized case, it has been shown in [Akiyama and Suzuki 2021] that gradient descent on the empirical loss can identify the parameters of a target ReLU network with high probability.   
Akiyama and Suzuki, ICML 2021. On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting.  
- The skewed spectrum of the Fisher matrix (related to the Hessian) at initialization has been theoretically investigated in [Karakida et al. 2019].  
Karakida et al., AISTATS 2019. Universal statistics of fisher information in deep neural networks: Mean field approach.


**Post-rebuttal Update**   
I have read the author's response and the other reviews. The authors addressed some of my concerns; hence I decided to keep my original score of borderline accept.  
One followup comment is that I still do not fully understand what the authors meant by "spurious minima may turn into
saddles, by using over-parameterization." The normal notion of overparameterization corresponds to increasing the width $k$ under fixed input dimensionality $d$. Where exactly is this setting investigated in the main text?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the property of spurious local minima in two-layer ReLU neural networks. In particular, it provides analytic expressions as well as the corresponding Hessians of some families of local minima, and by analyzing the Hessian spectrum it provides justification for some empirical observation.
main_review: The direct analysis of the loss and the Hessian spectrum of local minima is an interesting direction to pursue. The calculated Hessian spectrum of the spurious local minima matches the empirical observation that most eigenvalues concentrate near zero, which may be a good justification for practice. The symmetry of the families of spectrum of local minima also seems interesting, and the mechanism behind this is definitely worth further exploration.

Nevertheless, I do have some questions/concerns about this paper.

1. If I didn't miss something, the rigorous proof of the theorems seems to be missing. It is possible that the proof applies from other works, but if that is the case please explicitly remark on this. Currently I am not fully sure about the correctness of the proof.

2. Theorem 1 discusses some families of the local minima. Are these all the local minima contained in the network? If not, how to analyze other local minima, and will they possess the same property as claimed in this paper?

3. I'm wondering what the "break" of the symmetry of spurious local minima implies. Will it be observed in practice?

4. What if the activation function is not ReLU? Will the analysis be totally different?

With the questions above, I think the paper needs to address some of the issues before being accepted (at least adding a complete proof). It definitely has the potential of being a good paper, but perhaps not the current version.

Update after author response:

After reading the author's response, I'm convinced of the rigorousness of the proof. Therefore I'm happy to raise my score to 6. I still recommend the authors to include the formal details from [41] in this paper (possibly in the appendix) to make it more self-complete.
limitations_and_societal_impact: The authors addressed the limitations. No direct potential negative societal impact of their work seems to exist.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper presents theory for spurious minima in the classic two-layer ReLU network with squared error loss under the student-teacher framework. The paper establishes analytic expressions for families of minima, including global and local minimizers, according to different isotropy. Then, the paper presents analytic expressions for the Hessian spectrum, i.e. the eigenvalues and their multiplicity. The results support prior findings on skewed spectrum of Hessians in this setting, and further indicate that spurious and global minima can hardly be distinguished by the spectrums. 
main_review: Theoretical understanding of spurious minima in ReLU networks is very significant as it informs why and when training these networks can be successful. This is also a hard area because of large amount of parameters, non-linearity, non-convexity, and stochasticity. The analytic results in this paper is original and significant for the community to understand what may occur in a specific, shallow setting. The theoretical tools used in this paper, as well as the insights and conclusions, are very meaningful although the optimization problem is largely simplified. The paper is well written and easy to read with heavy math being well organized. 

I enjoyed reading the paper and learned a lot. The symmetry breaking framework and results are elegant. The theortical findings (on spectrum of the Hessian) are consistent with prior empirical findings and informative. The similarity between spurious and global minima in the sense of Hessian spectrum is especially interesting. I think this paper provides an important piece of understanding to the community of ReLU neural network theory. 

Below are some (mostly minor) questions in the order of line numbers.

1, Line 2: because the teacher network outputs real values, it is not accurate to call them "labels". Instead, it is better to call them "target values" or "target outputs". 

2, Regarding Theorem 1, are those families of minima the only ones? If not, is there any characterization for the rest families? Are the rest families analytic / intractable / very few?

3, Line 183-184: "this is obtained by ... by zeroes" is a little confusing. Which of $W$ or $V$ (or both) do you pad with zeroes? If you pad $V$, then $d$ becomes even larger. If you pad $W$, since the weights are learned instead of assigned, how do you deal with this? This sentence is important for the readers to understand why the $d=k$ results can be extended to the $d>k$ case, so I suggest the authors to explain more here.

4, In Theorem 2, by saying "normalized to one", do you mean setting each $\alpha_i$ to be $\pm1$ by rescaling between each $\alpha_i$ and $w_i$ *after* the optimization process?

5, A general question on the problem formulation: does your theory naturally extend to the empirical average version of eq (2), that is, $\frac1n\sum_{j=1}^n Loss(x_j)$ instead of $\mathbb{E}_x Loss(x)$, where $x_j\sim\mathcal{N}(0,I_d)$?

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper gives a detailed characterization of spurious local minima for 2-layer ReLU networks, which was a model that received substantial theoretical interest. The paper was able to do this using a powerful technique of symmetry-breaking, and the results explained some of the observations in previous works. Overall the paper is a very solid contribution to the understanding of optimization landscape of neural networks and the symmetry-breaking technique might be useful in more general settings.
Decision: Accept (Poster)