Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
Authors: Yossi Arjevani
Michael Field
Venue: NeurIPS 2021 Poster (2021)
Keywords: Neural networks
optimization
symmetry
symmetry breaking
spurious minima
bad local minima
nonconvex
deep learning

Abstract: We study the optimization problem associated with fitting two-layer ReLU neural networks with respect to the squared loss, where labels are generated by a target network. We make use of the rich symmetry structure to develop a novel set of tools for studying families of spurious minima. In contrast to existing approaches which operate in limiting regimes, our technique directly addresses the nonconvex loss landscape for finite number of inputs $d$ and neurons $k$, and provides analytic, rather than heuristic, information. In particular, we derive analytic estimates for the loss at different minima, and prove that, modulo $O(d^{-1/2})$-terms, the Hessian spectrum concentrates near small positive constants, with the exception of $\Theta(d)$ eigenvalues which grow linearly with~$d$. We further show that the Hessian spectrum at global and spurious minima coincide to $O(d^{-1/2})$-order, thus challenging our ability to argue about statistical generalization through local curvature. Lastly, our technique provides the exact \emph{fractional} dimensionality at which families of critical points turn from saddles into spurious minima. This makes possible the study of the creation and the annihilation of spurious minima using powerful tools from equivariant bifurcation theory. 

Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
Yossi Arjevani
Michael Field UC Santa Barbara mikefield0gmail.coomm
The Hebrew University yossi. evani @gmail.com com
Abstract
We study the optimization problem associated with fitting two-layer ReLU neural networks with respect to the squared loss, where labels are generated by a target network. We make use of the rich symmetry structure to develop a novel set of tools for studying families of spurious minima. In contrast existing approaches which operate in limiting regimes, our technique directly addresses the nonconvex loss landscape for finite number of imputs and neurons kt, and provides analytic, rather than heuristic, information. In particular, we derive analytic estimates for the loss at different minima, and prove that modulo (dd-1/2) >teemms the Hessian spectrum concentrates near small positive constants, with the exception of O ((d) cigenvalues which grow linearly with d. We further show that the Hessian spectrum at global and spurious minima coincide to ability argue about statistical generalization through local curvature. Lastly, our technique provides the exact eNactffactiond, dimensionality at which families of critical points turn from saddles into spurious minima. This makes possible the study of the creation and the annihilation of spurious minima using powerful tools from equivariant bifurcation theory.
thus challenging our
One of the outstanding conundrums of deep learning concerns the ability of simple gradient- based methods to successfully train neural networks despite the nonconvexity of the associated optimization problems. Indeed, generic nonconvex optimization landscapes can exhibit wide and flat basins of attraction around poor local minima which may lead complete failure of such methods. The nature by which nonconvex problems associated with neural networks deviate from generic ones is currently well-understood. In particular, much of the dynamics of gradient-based methods follows from the curvature of the loss landscape around local minima. is therefore vital to study the local geometry of spurious (i.e., non-global local) and global minima in order to understand the mysterious mechanism which drives gradient- bassed methods towards minima of high quality. However, already establishing the very existence of spurious minima seems be beyond reach of existing analytic tools; let alone rigorously arguing about their height, curvature and structure- the aim of this work.
In this paper, we focus two-layer ReLU neural networks of the form
aup((w,; W M(k a E R
where (o()) max(0, } is the ReLU activation function acting entry-wise. (M,,, d) denotes the space of k: x d matrices and wn denotes the ith row of W. We are primarily interested in characterizing obstructions for local search method, independently of the expressive power of two-layer ReLU networks. Thus, data is understood to be fully realizable. Concretely, we assume that there are d inputs which are drawn from the standard multivariate Gaussian distribution
various optimization-relan
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and are labeled by planted target network. We consider directly optimizing the expected squared loss, which results in the following highly nonconvex optimization problem:
C(W, = =BoNN( 2
aupp x)) - Σ Buo((or,
(2)
where k denotes the number of hidden neurons, W E M(k, d) and a; E R are the optimization variables, and v; and B3 are fixed parameters. This setting, in which the data distribution is regulated rather than being allowed to admit worst-case behavior, has drawn a considerable amount of interest in recent years [66, 17, 19, 40, 61, 11, 24, 54, 4, 1]. in part due to the growing number of evidences which indicate that any explanation for the empirical success of deep learning (DL) must take into account the intricate interplay between the network architecture, the input distribution and the label distribution (cf. [11, 9, 59] and references therein for hardness results of optimization and learnability under partial sets of assumptions). Moreover, demonstrated later in the paper, in spite of its apparent simplicity, nonconvex problem (2) shares a few important characteristics with full-scale neural networks, such low-dimensional minima and extremely skewed Hessian spectrum.
Learning problem (2) has also been studied in the statistical physics community starting from the 80' [23, 57, 37, 62, 18, 8, 52, 53, 51] under the student-teacher (ST) framework, in which one aims to adjust a studens network so as to fit the output of a teacher network. The ST framework offers clean venue for analyzing optimization-relate physical reductionism. The success of DL models in the past decade has reinitiated a surge of interest in this framework, e.g., [7, 28, 42, 47]. However, despite the long tradition in the statistical physics community and the wide effort put nowadays by the machine learning community, the perplexing geometry of problem (2) still seems to be of reach of existing analytic tools in regimes encountered in practice. In this paper, we present a novel set of symmetry-based tools which allows us, for the first time, analytically characterize important aspects of the associated highly nonconvex landscape for finite number of inputs and neurons.
aspects of neural network models in the spirit of
Our contributions, in order of appearance, be stated as follows:
We demonstrate that, empirically, and in a well-defined sense, minima in two-layer ReLU neural net- works break the symmetry of the target weight matrix. Although ReLU networks have been studied for many years, this phenomenon of symmetry breaking seems to have gone largely unnoticed.
We show that symmetry breaking makes possible to derive analytic expressions for families of spurious minima in the form of fractional power series in terms of d and k. Crucially, in contrast to existing approaches which employ various limiting processes, e.g., [7, 28, 42, 47, 29, 43, 13, 33, 14], our method operates in the natural regime where d and k are finite.
We develop a novel technique which yields an analytic characterization of the Hessian spectrum of minima to O(d-1/2)-order for d 2 k. and determine the exact fractional value of d at which critical points turn from saddles into spurious minima-2 key ingredient in understanding how puee-parameterizzaion annihilates spurious minima.
Based on the unique access to high-dimensional spectral information, we closely examine number of hypotheses in the machine learning literature pertaining to curvature, optimization and generalization. In particular, we prove that the Hessian spectrum minima concentrates near small positive constants, with the exception of ((d) eigenvalues which grow linearly with d. Although this phenomenon of extremely skewed spectrum has been observed many times [10, 38, 55, 56), to our knowledge, this is the first time it has been established rigorously for two-layer ReLU networks. In addition, our analysis shows that the Hessian spectra of spurious and global minima are identical (dd11/2) -teemms, and further implies that the inductive bias of stochastic gradient descent (SGD), provably, can not be exclusively explained in terms of local curvature [32, 36, 34, 63, 64, 12, 16).
The results presented in the paper are threefold: identifying symmetry breaking principle for two-layer ReLU networks, analytically characterizating spurious minima, and computing the Hessian spectrum. The next three sections are organized accordingly, along with literature survey of related work. The last section is devoted for a high-level description of the novel symmetry- based technique used in this work. Proofs, formalities and lengthy technical details are deferred to the appendix.

---

1.6
1.6
Global minmum
#neurons
Spurious minimum (Theorem 2(6))
1.4
#neurons 10
Specturm (Theorem
#ncurons
12
1.0
1.0
Dendtt
0.8
0.8
0.6
0.4
0.2
0.2
0.0
Eigenwaluss NeNuurnss 20)
Eigenwaluss the family critical points 21a), Thearem
Figure 1: (Left) Our symmetry-based technique yields an analytic characterization of the Hessian spectrum (see Theorem 2) to O(d-1/2)-order (in dashed line) which provides good approximation already for small values of inputs and neurons (in solid lines). The analysis further implies that the Hessian spectrum of global and various types of spurious minima agree to within
(Right) the Hessian spectrum is extremely skewed and tends concentrate near small positive constants with the exception of (d) eigenvalues which grow linearly with d. Observe that the family of critical points considered here (see Theorem 1, case 2a) turns from saddles minima when d 2 10. Our analysis shows that the change of stability occurs at d Rs 5.71, and more importantly, indicates that the process can fact reversed, namely, spurious minima can be turned into saddles by wer-parametterzznn (i.e., increasing the number of hidden neurons).
3 into spurious
1 Symmetry breaking in two-layer ReLU neural networks
Optimization problem (2) exhibits a very rich symmetry structure. Indeed, the loss function L is invariant left- and right-multillication of W by permutation matrices (see Section A.1 for formal proof), i.e., L(W, a) C(Pa W P. or) for all (T, E S₃ x Sa. where S,, generally denotes the symmetric group of degree m, and
(Pa)y= = i=
1 10 o.W.
is therefore natural to ask how the critical points of L reflect this symmetry. For example, the identity matrix las one of the global minimizers of L for the in which V Ia. = 1, and A: = d, is invariant under simultaneous left- and right-multiplication by any permutation matrix. Indeed, P. P. global minimizer of L. See [6, Proposition 4. 14.J.) This simple observation is conveniently stated using the concept of the isotropy group. Given a weight matrix W M (k, d), we let
Pa PT
Ta for any E Sa- (Modulo group conjugation, this holds for any
[so(W) = ((TT.)) p) (H, E S& x Sa, P.WP. = -W,
(3)
Thus, we have [so = ASa, where A maps any subgroup H C Sa to its diagonal counterpart AH (hh h) h H} C Sa Sa. Empirically, and somewhat miraculously, spurious minima and saddles of tend to be highly symmetric in the (formal) sense that their isotropy groups are (conjugated to) large subgroups of ASA. the isotropy of the global minima (see Figure 2). Thus, the principle of symmetry breaking can be concisely phrased as follows:
Spurious minima break the symmetry of global minima.
The principle extends to more general target networks; when the isotropy of the target weight matrix V changes, the symmetry of spurious minima belonging to the respective optimization problem. In Section A, we provide a series of experiments which empirically corroborates symmetry breaking for optimization problem (2).
3

---

B
B
B
7
Isotropy AS;
Isotropy AS4 x AS
Isotropy AS3 x AS2
Figure 2: A schematic description of x 5 matrices with isotropy ASs, AS₁ x AS₁ and AS₃ x S2, from left to right (borrowed from [3]). a, B, y, 6, and Ç assumed be 'sufficiently' different.
The principle of symmetry breaking for ReLU networks was first studied in [3, 6], and was later extended to various tensor decomposition problems in [2]. Here, we analyze two-layer ReLU networks where both layers are trainable, an architecture which has received considerable amount of attention in recent years, e.g., [66, 17, 19, 40, 61, 11, 24]. We note in passing that, in its broader sense, the principle of symmetry breaking has been observed many times various scientific fields, e.g., Higgs-Landan theory, equivariant bifurcation theory and replica symmetry-breakinn (see, e.g.. [46, 30, 21, 15]). Two-layer ReLU networks seems to form a rather unexpected instance of this principle.
One intriguing quality of nonconvex landscapes in which the symmetry breaking principle applies is that local minima lie in fixed ow-dimensional spaces (see Section 4). A similar phenomenon of hidden wiwdimeesional structure has been observed in various learning problems DL with real datasets [39, 31]. and is believed by some to be an important factor of learnability in nonconvex settings. the context of this work, the hidden diniiiinnionnaltyy of spurious minima turns out to be a key ingredient to our analytic study, as we now present.
2 Power series representation of families of spurious minima
Although the problem of fitting neural networks under the ST framework have been studied for more than 30 years, the symmetry breaking principle exhibited by optimization problem (2) seems to have gone largely unnoticed. Early studies adopted tools (at times, heuristic, c.g., [45, 44J) from statistical physics to analyze phase transitions and generalization errors [23, 57, 37, 62]. Later work focused on the dynamics of SGD and studied the evolution of the generalization error along the optimization process through set of carefully-derivee ODEs [18, 8, 52, 53, 51]. Following the empirical success of DL in the past decade, this line of work has recently drawn renewed interest, e.g. [7. 28, 47, 29], which puts past analyses on rigorous grounds and addresses a broader class of architectures and activation functions. The methods used in this long line of works operate the thermodynamic lihit-where the number of inputs is taken to infinity. Thus, the formal validity of the results to finite width networks is currently limited.
Other common approaches for analyzing problem (2) are based on: mean-field [43], optimal control [13], NTK [33] and compositional kernels [14]. These approaches offer, in essence, convex surrogates which apply in strict parameter regimes (including algorithmic parameters, such as learning rates). Similarly to the thermodynamic limit approach, the convex surrogates are obtained by limiting processes this time by taking the number of hidden neurons to infinite. A growing number of works has severely limited, if not invalidated, the explanatory power of these approaches for network widths encountered in practice [65, 26).
In sharp contrast to the approaches discussed above, technique directly addresses the associated highly nonconvex optimization landscape in the natural regime where the number of inputs and neu- rons is finite, and provides analytic, rather than heuristic, information. This is obtained by exploiting the presence of symmetry breaking phenomena whereby fractional power series representation for families of spurious minima are derived.
Below, we provide analytic expressions for families of minima of different isotropy (see Definition and Figure 2), along with their respective objective value. For brevity, expressions are given to (dd-3//)-rrder. In the appendix, we list additional O(d 0(d-5/2)-order terms which are required for

---

computing the Hessian spectrum. The invariance properties of optimization problem (2) imply that additional families of minima can be obtained by permuting the rows and the columns of given family. The number of new distinct minima generated using such transformations (i.e., the minima multiplicity) depends on the very structure the family of minima under consideration, and is stated in Theorem 1. Lastly, for any À > O and i E [d], the value of the ReLU network (1) remains fixed under (wn, o:)) r> (Aw,, a./,), This degree-of- ofreeedommf is expressed by using the slack variables X; O, i [d] below.
Theorem 1, Optimization problem (2) with & d, V Ia and B ld possesses the following families of minima for d 2 9:
1. Two families of ASa-minima of multiplicity d! with W(d) Diag(Ai,- Aa) Ad(a, 02) and a(d)= ">r.,...,>? Xxx where X₂ 0,
[11
02
02
01
02
a2
Aa(a1, 02)
E M(d,d),
a1
02
01
Diag(.) maps a given vector to the diagonal entries of a diagonal matrix, and (a) ai = and 02 = 0 (a global minimizer), in which case (dW(d),
0.
(b) 01 = -1= +2 20 02 = a + 100 (d in which case
(d), a(d) + 2
1
+ Od77)
(4)
3T
d
2. Two families of A(Sa-1 81) m-)imim of multiplicity d. d! with
((d) Diag(A),........................ Xa))
Aa-1(a), 02)
03
asI1,d-1
a5
and (d) (A ..... )² where x; > 0 and
(a) 01 1+ 1++00 0 d
02 = 0 03
+
0
04
nd
4
+
+0(dT)
and
05 = +1 72 ++
+ 0 d ) in which case
L(W (d))a((d))))))))))) = 2 7²
+ +0(d7)
(5)
d
(b) 01 = 11 +
02 = 2 ( (
03 = =
a4 =
2-
d
+0(
and
05 = 1 + 8(-++))
+ +0(d2) in which case
r'd
+ 5
+ +0(az)
((W(d). = π
+ 2
3 +
x2
(6)
d
3. Two families of A(Sa-2 x -z)-minima of multiplicity d! (9) with
W(d) (algg(Ai....,...... a2))(0))0))
a3In-2.2 2,2
a412,12
A2(15, 46)
and ad) = (AT1 ...., , 11)
where A; > 0 and
(a) a = =1 0 (d+)
a2 = 0 d
0g 03= 0
04 = nd +o(a))
-1 8. +
+ +0
- and Og
11-12++16+7
+ 0 (1
in which case
x*d(2+T)
L(W(d),
-4+ 7²
x2d + (177)
5

---

(b) a1 -1+ 24
a2 _ + =
03 0
0 0
a1 -
0 d
as = 1 8(115)
0 - and as
16-65-
-0 d
in which case
x2d(2+))
L(W(d),
+ ( +
(8)
3T
One family of A(Sa-3 -aiimia of multiplicity d! (9) with
((d) = Diag( d1 A Ada) Ad Ad-a(a1, 02)
03 03Id-3.3
a313,d-3
A2(05, 06)
and (d) = (AT) ..... Xi where x; > 0 and = 0
02 = 0 0
03 = +
0 ( 04 1 Wd + d 1+ 2 +2+ +0 (d
2
+1++++++20 +1+++11+*000 16+ +
and ag
x x2(
0 (d in which case
6 n² +0(at))
((W(d),a(d)
The idea of the proof of Theorem is given in Section 4.1, and the multiplicity computation, simple application of the orbit-stabilizer theorem, in Section B. We note that the same technique can be used for other choices of target networks, mutatis mutandis. The power series stated in Theorem also represent spurious minima for the under-parameteriied d >> k-case. This obtained by appropriately padding the entries of the weight matrices by zeros (see [6, section 4.3] for details). The derivation of the respective Hessian spectrum is then an immediate application of [4, section E. the spectral analysis given Theorem 2 below (for the case where d = k). By contrast, studying the over over-paramen parameterized regime for which d < k requires qualitatively different tools and is outside the scope of this work.
The analysis above reveals that not all local minima are alike: while the objective value of some minima decays like (1/dd), in other cases the objective value converges to the positive constant 1-1. In particular, except for the global minima case 1a, all minima described above are spurious. The difference between the types of behavior seems lie in the limiting values of the entries of (d)); in the former, the diagonal mainly consists of ones, whereas the latter mainly minus ones. This is consistent with the fact that all the teacher's diagonal entries are ones.
For reasons which are yet to be understood, empirically, the bias induced by Xavier initialization [27] seems to favor the class of minima for which the objective value decays as ((1/d). This is not to say that under Xavier initialization the expected value upon convergence must decrease with d. The objective value decays
different rates (see cases 2a, 3a, 4 above) and depends the probability to converge to a given type of minima. (A possible proxy to the latter is the minima multiplicity stated in Theorem 1.)
3 Analytic study of the Hessian spectrum
Once power series representation has been obtained, it is possible to analytically characterize various important properties of families minima. Here, we use this representation to compute yet another fractional power series eeries-this time, of the Hessian spectrum.
Theorem 2. Assuming all the weights of the second layer of (1) are set to one, the (nonnegative) Hessian spectrum of the families of minima considered in Theorem 1 is

---

Eigenvalue
Multiplicity
O(d-1/3)
d [d- (d
1/ # -0(-21/2
1 1 +0
d -
2 "
0+d-111222
d - 1 d(d-3) 2
+ 25 +0(-1112)
d + 2 1(d-1112
d - 1
+ 25( + +(d-1/22
-4++**
1
10x4844 0(d-1/3
1.
(x(-))
The method we developed for computing the Hessian spectrum builds on [4], but differs in three crucial aspects. First, in our setting the second layer is trainable. The associated so-called isotypic de- composition (a set of 'simple' subspaces compatible with the action of row- and pemunneemuttaioonss formally introduced Section D) must therefore cover the space of x d weight matrices, as well as the d weights of the second layer. Secondly, instead of expressing the Hessian entries in terms of d, W (d) and (xd) and then extracting fractional power series for eigenvalues, we directly express the eigenvalues in these terms. This considerably simplifies computations and facilitates the computation of eigenvalues to potentially any order. Thirdly, and perhaps most importantly, computing the Hessian high accuracy reveals that for small values of the families of minima presented in Theorem I are in fact saddles. Regarding d as a real number, we pinpoint the exact fractiona dimension at which given family of critical points turns from saddles into spurious minima (see also Figure 1). One now led into the dual question: is there mechanism by which spurious minima may be annihilated (that is, turn into saddles)? We have found that the process of the creation of minima can be reversed the over-paramen parameterized regime. This provides a strong evidence for the benefits of increasing the number of student neurons from an optimization point of view adding more neurons turns spurious minima into saddles, thus encouraging gradient-based methods to converge minima of better quality. A rigorous study of this process requires tools from equivariant bifurcation theory, and is deferred to future work (cf. [5]).
Quite remarkably, although families of minima presented in Theorem differ significantly, their Hessian spectra coincide to O(d-1/2)-ordee Another noticeable implication of Theorem is that the Hessian spectrum tends to be extremely skewed. Both phenomena, as well as their consequences for optimization-relate aspects, are discussed in detail below.
Positively-skewed Hessian spectral density. Although first reported nearly 30 years ago [10], to our knowledge, this is the first time that this phenomenon of extremely skewed spectral density has been established rigorously for two trainable ReLU layers of arbitrarily large dimensionality. Early empirical studies of the Hessian spectrum [10] revealed that local minima tend to be extremely ill-conditioned. This intriguing observation was corroborated and further refined in series of works [38, 55, 56] which studied how the spectrum evolves along the training process. was noticed that, upon convergence, the spectral density decomposes into two parts: a bulk of eigenvalues concentrated near small positive constants, and a set of positive outliers located away from zero.
Due to the high computational cost of an exact computation of the Hessian spectrum (cubic in the problem parameters k and d), this phenomenon of extremely skewed spectral densities has only been confirmed for small-scale networks. Other methods for extracting second-order information in large-scale problems roughly fall into two general categories. The first class of methods approximate the Hessian spectral density by employing various numerical estimation techniques, most notably stochastic Lanezos method (e.g., [25,48]). 481). These methods have provided various numerical evidences which indicate that similar skewed spectrum phenomenon also occurs in full-scale modern neural networks. The second class of techniques builds on tools from random matrix theory. The latter approach yields an exact computation of the limiting spectral distribution (where the number of neurons is taken to infinity), assuming the inputs, as well as the model weights are drawn at random [49, 50, 41, 35]. In contrast, method gives an analytic description of the spectral density for
7

---

any number of neurons (granted d 2 9), and at critical points rather than randomly drawn weight matrices.
The flat minima conjecture and implicit bias. has long been debated whether some notion of local curvature can be used to explain the remarkable generalization capabilities of modern neural networks [32, 36, 34, 63, 64, 12, 16]. One intriguing hypothesis argues that minima with wider basins of attraction tend to generalize better. The suggested intuitive explanation is that flatness promotes statistical and numerical stability; together with low empirical loss, these ingredients are widely used achieve good generalization, cf. [58]. However, the analysis presented Theorem 2 shows that Consequently, in setting, local second-order curvature cannot be used to separate global from spurious minima. This rules out any notion of flatness which exclusively relies on the Hessian spectrum. Of course, other metrics of a 'wideness of basins' may well apply.
the spectra of global minima and spurious minima agree O(d-1/2)
4 A symmetry-based analytic framework
In the sequel, we present the main ingredients of the symmetry- technique developed this work. The technique builds on, and significantly extends various components from [4, 3, 6]. To ease exposition, we illustrate with reference to the case where and the weights the second layer are set to one. We let the resulting nonconvex function be denoted by f(W) == L(W, 1).
4.1 Power series representation of minima
The first step in deriving power series representation is to restrict the nonconvex function under consideration to fixed point subspaces (see [20] for more complete account); spaces that consists of weight matrices which remain fixed under row- and column- -eruummmermtttiinnss in certain subgroup of Sa x Sg. For concreteness, consider the space of all matrices which are invariant to permutations in ASa, i...
Wa = ( ((d W P. for all (M, T) E ASa).
(10)
It is easy to verify that Wa is in fact 2-dimensional subspace of the form Wa {(a1, 02) a1 la + [ - 7)}. and that if W Wa, then also Vf(W) E Wa (see [3, Proposition 3J). Thus, one may regard of f on d explicit by defining F R - IR2 (a1, a2 d) + Vf(aala + az [2(1a]] Ia)). Note that although was initially taken be a natural number, in the following explicit expressions of F(a1, 02 d), we regard d as a real variable
a function from R² to R², Next, we make the dependence
ondai (48) (I (-1)
( an (a
where, here and below, (i) (resp. ((e) denotes the angles between the ith row of W and the jth of W (resp. V). Using the implicit function theorem one can establish the existence as well as the uniqueness of a path of critical points (a (d), az()). This gives a formal meaning for examining a given family of minima at fractional dimensionality. Formalities are covered in length in [6].
We are left with the following two issues. First, the implicit function theorem does not yield an explicit form of aj (d) and az) This issue is addressed by using real analytic version of the implicit function theorem, and then computing the coefficients of the power series of aj (d) and ag (2(d) to desired order. Secondly, the implicit function theorem requires initial values for aj and a₂ which solve F(a1, 02 d) 0. To handle this issue, we form power series in 1/d and, loosely speaking, develop them at d co. The advantage of this nonstandard manipulation is that the limiting entries of W (d) have a very simple form, which are then used the initial values required for invoking the implicit function theorem. In fact, due to the dependence of V f on the angels between rows of W and V. the power series of (1 (d) and (z)) are expressed in terms of 1/Vū. Theorem 1 is established by following the recipe described here for various families critical points of different isotropy. The gradient expressions involved in the process are lengthy and therefore relegated to Section E.
8

---

4.2 Computing the Hessian spectrum
Our next goal is derive analytic characterization of the Hessian spectrum. The invariance properties of L imply that although the dimension of the Hessian, k(d + 1) x k(d + 1), depends on and d, the number of distinct eigenvalues remains fixed. This is an immediate consequence of the respective isotypic decomposition (see Section D). A formal introduction of the isotypic decomposition requires some familiarity with group actions, and therefore deferred to Section D.2. Here, we shall focus on one particularly simple case.
The isotypic decomposition associated with AS the isotropy of la implies that for any d,
0
d -
3
3
- d
0
0
0
d
-1 -1
3 - d
0
0
1
1
Da = vec
-1
0
-1
0
0
an eigenvector of f(La), where vec denotes the linear transformation which stacks the rows of given matrix on top one another as a column vector. Thus, the eigenvalue corresponding to Da 3), which takes the following explicit form
equals (V²)([a))
04-1) (+09)
200
2500
where M(() denotes the norm the row of W, and (
(resp. (()) denotes sin arccos
(resp. sin arccos( (3 (B())) To complete the derivation of the eigenvalue Da for families of isotropy AS2, e.g., cases ((a) and 1(b) in Theorem 1, one plugs-in the power series representation of a1 (d(d) and (c)) into the expression above, and forms new power series to get estimate for D). The same procedure used for all families of minima presented in Theorem 1, and is described in detail in Section 4.2.
5 Conclusion
When present, the principle of symmetry breaking forms powerful tool reducing the complexity of nonconvex problems in nonlinear way. This yields unprecedented analytic information for ReLU networks with a finite number of inputs and neurons (rather than limiting models varying qualities). At this stage of the theory, the extent to which the symmetry breaking principle applies is not well-understood. However, it does seem to hold in a broader class of fundamental nonconvex problems, e.g., [2].
An intriguing finding allowed by the principle of symmetry breaking is that various families of spurious and global minima are locally identical to O(d-1/2)-order Since the multiplicity of local minima for k: = d is essentially exponential in d, it is rather unlikely for SGD to be able to escape spurious minima when grows (see [54, Table 1J). Why is then that SGD generally able find good minima for optimization problems associated with fitting ReLU neural networks? Preliminary experiments we conducted indicate that continuously increasing k and leaving d fixed turns families of spurious minima turn into saddles. (The objective value seems to remain constant.) We believe that this phenomenon is instrumental for explaining the effectiveness of gradient- based methods, SGD in particular. A thorough study of this requires tools from equivariant bifurcation theory and is postponed to future work.
Acknowledgements
Part of this work was completed while YA was a postdoctoral researcher NYU. We thank Joan Bruna, Ohad Shamir, Shimon Shpiz and Daniel Soudry for valuable discussions.

---

References
[1] S. Akiyama and Suzuki. On learnability via gradient method for two-layer relu neural networks in teacher-student setting, arXiv preprint arXiv:2106.06251, 2021.
[2] Y. Arjevani, J. Bruna, M. Field, Kileel, M. Trager, and F. Williams. Symmetry breaking in symmetric tensor decomposition. arXiv preprint arXiv:2103.06255 2021.
[3] Y. Arjevani and M. Field. On the principle of least symmetry breaking in shallow relu models. arXiv preprint arxiv: 1912. 1939, 2019.
[4] Y. Arjevani and M. Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12 12, 2020, virtual, 2020.
[5] Y. Arjevani and M. Field. Equivariant bifurcation, quadratic equivariants, and symmetry breaking for the standard representation of s_n. arXiv preprint arXiv:2107.02422, 2021.
[6] Y. Arjevani and M. Field. Symmetry & critical points for model shallow neural network. Physica D: Nonlinear Phenomena, 427:133014, 2021.
[7] B. Aubin, A. Maillard, J. Barbier, F. Krzakala, N. Macris, and L. Zdeborová. The committee machine: Computational to statistical gaps in learning a two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, 2019(12): 2019.
[8] M. Biehl and H. Schwarze. Learning by on-line gradient descent. Journal of Physics A: Mathematical and general, 28(3):643, 1995.
[9] A. I.. Blum and R. L. Rivest. Training a 3-node neural network is np-complete. Neural Networks, 5(1):117-127, 1992.
[10] L. Bottou. Stochastic gradient learning in neural networks. Proceedings of Neuro-Nimes, 91(8):12, 1991.
[11] A. Brutzkus and A. Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages
JMLR. org. 2017.
[12] P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi, C. Borgs, J. Chayes, L. Sagun, and R. Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, (019((1)) 124018,, 2019.
[13] L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. arXiv preprint arXiv:/805.00555,, 2018.
[14] A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. arXiv preprint
2016.
[15] J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 59-68, 2015.
[16] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1019-1028. JMLR. org, 2017.
(17) S. Du, J. D. Lee, Y. Tian, A. Singh, and B. Póczos. Gradient descent learns one-hiddennllyer CNN: don't be afraid of spurious local minima. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässso, Stockholm, Sweden, July 10-15, 2018, pages 1338-1347, 2018
[18] A. Engel and C. Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
10

---

[19] S. Feizi, H. Javadi, J. Zhang, and D. Tse. Porcupine neural networks.(almost) all local optima are global. arXiv preprint 17Xiv1171..0296, 2017.
[20] M. Field. Dynamics and symmetry, volume 3 of ICP Advanced Texts in Mathematics. Imperial College Press, London, 2007.
[21] M. J. Field and R. W. Richardson. Symmetry breaking and the maximal isotropy subgroup conjecture for reflection groups. Archive for Rational Mechanics and Analysis, 105(1);61-94, Mar 1989.
[22] W. Fulton and J. Harris. Representation theory, volume 129 of. Graduate Texts in Mathematics, 1991.
[23] E. Gardner and B. Derrida. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 22(12):1983, 1989.
[24] R. Ge, D. Lee, and T. Ma. Learning llyh neural networks with landscape design. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
[25] B. Ghorbani, S. Krishnan, and Y. Xiao. An investigation into neural net optimization via hessian eigenvalue density. In K. Chaudhuri and Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2241.. PMLR, 2019.
[26] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. When do neural networks outperform kernel methods? arXiv preprint arXiv:2006. 13409,, 2020.
[27] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statisticy, pages 249-256, 2010.
[28] S. Goldt, M. S. Advani, A. M. Saxe, F. Krzakala, and L. Zdeborová. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. arXiv preprint arXiv: 1rX6v 08632, 2019.
[29] S. Goldt, M. S. Advani, A. M. Saxe, F. Krzakala, and L. Zdeborová. Generalisation dynamics of online learning in ever-parameterised neural networks. arXiv preprint arXiv: 2019.
[30] M. Golubitsky. The benard problem, symmetry and the lattice of isotropy subgroups. Bifurcation Theory, Mechanics and Physics. CP Boner et al., eds. (Reidel, Dordrecht, 1983), pages 225-256, 1983.
[31] G. Gur-Ari, D. A. Roberts, and E. Dyer. Gradient descent happens in tiny subspace. arXiv preprint IrXiv:1812.04755 2018
[32] S. Hochreiter and J. Schmidhuber, Flat minima. Neural Computation, 9(1):1-42, 1997.
[33] A. Jacot, Gabriel, and Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint 1xXiv:8806007722 2018.
[34] S. Jastrzkebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey. Three factors influencing minima in sgd. arXiv preprint 1711:00 2017.
[35] R. Karakida, S. Akaho, and S.-i. Amari. Universal statistics of fisher information in deep neural networks: Mean field approach. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1032-1041. PMLR, 2019.
[36] N. Keskar, D. Mudigere, Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch train- ing for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04836 2016.
[37] W. Kinzel and P. Rujan. Improving a network generalization ability by selecting examples. EPL (Europhysics Letters), 13(5):473, 1990.

---

[38] Y. A. LeCun, L. Bottou, G. B. OIT, and K.-R. Müller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9-48. Springer, 2012.
[39] C. Li, H. Farkhoor, R. Liu, and J. Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprini TexXiv::004.00 08838, 2018.
[40] Y. Li and Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pages 597-607, 2017.
[41] C. Louart, Z. Liao, R. Couillet, et al. A random matrix approach to neural networks. The Annals of Applied Probability, 28(2): 10:::1190-12000 1248, 2018.
[42] S. Mannelli, E. Vanden-Eijnden, and L. Zdeborová. Optimization and generalization of shallow neural networks with quadratic activation functions. arXiv preprint arXiv:2006.15459, 2020.
[43] S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, L15(3)):7765--7767,, 2018.
[44] M. Mezard and A. Montanari. Information, physics, and computation. Oxford University Press, 2009.
[45] M. Mézard, G. Parisi, and M. A. Virasoro. Spin glass theory and beyond: An Introduction the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
[46]
L. Michel. Minima of higgs-landau polynomials. Technical report, 1979.
[47] E. Oostwal, M. Straat, and M. Biehl. Hidden unit specialization in layered neural networks: Relu vs. sigmoidal activation. Physica A: Statistical Mechanics and its Applications, 564:125517, 2021.
[48] V. Papyan. The full spectrum of deepnet hessians scale: Dynamics with sgd training and sample size. arXiv preprint arXiv: 1..0002, 2018.
[49] J. Pennington and P. Worah. Nonlinear random matrix theory for deep learning. In Advances in Neural Information Processing Systems, pages 2637-2646, 2017.
[50] J. Pennington and P. Worah. The spectrum of the fisher information matrix of single-hidden- layer neural network. Advances in Neural Information Processing Systems, pages 5410-5419, 2018.
[51] Riegler and M. Biehl. On-line backpropagation in two-layered neural networks. Journal of Physics A: Mathematical and General, 28(20):L507, 1995.
[52] D. Saad and S. A. Solla. Exact solution for on-line learning in multilayer neural networks. Physical Review Letters, 74(21):4337, 1995.
[53] D. Saad and S. A. Solla. On-line learning soft committee machines. Physical Review E. 52(4):4225, 1995.
[54] I. Safran and O. Shamir. Spurious local minima common in two-layer relu neural net- works. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 4430-4438. 2018
[55] L. Sagun, I.. Bottou, and Y. LeCun. Figenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint 161iv:6611.07476 2016.
[56] L. Sagun, U. Evei, U. Guney, Y. Dauphin, and L. Bottou. Empirical analysis of the hessian of over-parametrized neural networks, arXiv preprint arXiv: 17X.v:1706.04444 2017.
[57] H. S. Scung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical review A, 45(8):6056, 1992.
12

---

[58] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(Oct):2635 2670, 2010.
[59] O. Shamir. Distribution-speciii hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):113511163 2018.
[60] C. B. Thomas. Representations of finite and Lie groups. World Scientific, 2004.
[61] Y. Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 3404-3413, JMLR. org, 2017.
[62] L. Watkin, A. Rau, and M. Biehl. The statistical mechanics of learning rule. Reviews of Modern Physics, 65(2))499, 1993.
[63] L. Wu, Z. Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint urXiv: 10239, 2017.
[64] Z. Yao, A. Gholami, Q. Lei, K. Keutzer, and M. Mahoney. bessian-bbsed analysis of large batch training and robustness to adversaries. In Advances Neural Information Processing Systems, pages 1949-4959 2018.
[65] G. Yehudai and O. Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904. 00687, 2019.
[66] Q. Zhang, R. Panigrahy, S. Sachdeva, and A. Rahimi. Electron-proton dynamics in deep learning. arXiv preprint arXiv: / 702.00048, pages 1-31, 2017.
13


Reviews:
[{"review_id": "lbJ-v-S_yMS", "reviewer": "Reviewer_7HVf", "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. \n\nNote: 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nstrengths:\n- the paper studies an important problem in deep learning optimization.\n- 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.\n\nweakness:\n- the theoretical results are not properly motivated and their implications are discussed. More on this below.\n- some of the claims in the paper are misleading or not true. See below.\n\nDetailed review:\n\n- 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?\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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. \n\n- 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.\n\n[1] Sagun, Levent, et al. \"Empirical analysis of the hessian of over-parametrized neural networks.\" arXiv preprint arXiv:1706.04454 (2017).\n\n[2] Dauphin, Yann, et al. \"Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.\" arXiv preprint arXiv:1406.2572 (2014).\n\nBecause of the above concerns, I am giving a score of 6 to the paper. If addressed, I am willing to increase the score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see main review for limitations.\nSocietal impact: N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15 hours"}, "extra_text": {}}, {"review_id": "W9urGLH6lDU", "reviewer": "Reviewer_ceVj", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength\n\nThe non-convex landscape of neural network is an important subject of study in deep learning theory. \nTo 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  \n(i) the similar spectral properties of the Hessian at the global and local minima.  \n(ii) skewed spectrum of the Hessian.   \n(iii) the different decay rates of loss at different local minima.  \n\n## Weakness\n\n1. The theoretical setup is a bit idealized, for the following reasons.\n- 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. \n- The assumptions on the target network in Theorem 1 and 2 (i.e., identity first-layer and all-one second-layer) are quite restrictive. \n- The current study does not cover the $k>d$ case, which is interesting due to the presence of overparameterization.\n- 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. \n\n2. The writing and readability of the manuscript can be improved.\n- 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.\n- 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. \n\n**Additional Comments and Questions**\n\n1. 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?\n\n2. 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? \n\n3. Some relevant papers: \n- 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.   \nAkiyama and Suzuki, ICML 2021. On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting.  \n- The skewed spectrum of the Fisher matrix (related to the Hessian) at initialization has been theoretically investigated in [Karakida et al. 2019].  \nKarakida et al., AISTATS 2019. Universal statistics of fisher information in deep neural networks: Mean field approach.\n\n\n**Post-rebuttal Update**   \nI 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.  \nOne followup comment is that I still do not fully understand what the authors meant by \"spurious minima may turn into\nsaddles, 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours. "}, "extra_text": {}}, {"review_id": "R1enheJGvZ2", "reviewer": "Reviewer_NQUU", "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI 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. \n\nBelow are some (mostly minor) questions in the order of line numbers.\n\n1, 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\". \n\n2, 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?\n\n3, 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.\n\n4, 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?\n\n5, 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)$?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours."}, "extra_text": {}}, {"review_id": "EUbWN6eoKV", "reviewer": "Reviewer_nCPe", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nNevertheless, I do have some questions/concerns about this paper.\n\n1. 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.\n\n2. 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?\n\n3. I'm wondering what the \"break\" of the symmetry of spurious local minima implies. Will it be observed in practice?\n\n4. What if the activation function is not ReLU? Will the analysis be totally different?\n\nWith 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.\n\nUpdate after author response:\n\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations. No direct potential negative societal impact of their work seems to exist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

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)