Annihilation of Spurious Minima in Two-Layer ReLU Networks
Authors: Yossi Arjevani
Michael Field
Venue: NeurIPS 2022 Accept (2022)
Keywords: Neural networks
optimization
symmetry
symmetry breaking
spurious minima
bad local minima
saddles
ReLU
two layers

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. Use is made of the rich symmetry structure to develop a novel set of tools for studying the mechanism by which over-parameterization annihilates spurious minima through. Sharp analytic estimates are obtained for the loss and the Hessian spectrum at different minima, and it is shown that adding neurons can turn symmetric spurious minima into saddles through a local mechanism that does not generate new spurious minima; minima of smaller symmetry require more neurons. Using Cauchy's interlacing theorem, we prove the existence of descent directions in certain subspaces arising from the symmetry structure of the loss function. This analytic approach uses techniques, new to the field, from algebraic geometry, representation theory and symmetry breaking, and confirms rigorously the effectiveness of over-parameterization in making the associated loss landscape accessible to gradient-based methods. For a fixed number of neurons and inputs, the spectral results remain true under symmetry breaking perturbation of the target.

Annihilation of Spurious Minima in Two-Layer ReLU Networks
Yossi Arjevani The Hebrew University yossi. www.eriiiiaaaaall.....mmmmm com
Michael Field UC Santa Barbara Mike field@gmallll..... 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. Use is made of the rich symmetry structure develop a novel set of tools for studying the mechanism by which vvee-paramtterization annihilates spurious minima. Sharp analytic estimates are obtained for the loss and the Hessian spec- trum at different minima, and it is proved that adding neurons can turn symmetric spurious minima into saddles; minima of lesser symmetry require more neurons. Using Cauchy's s interlacing theorem, we prove the existence of descent directions in certain subspaces arising from the symmetry structure of the loss function. This analytic approach uses techniques, new the field, from algebraic geometry, repre- sentation theory and symmetry breaking, and confirms rigorously the effectiveness of partteerrtteiiiioonn in making the associated loss landscape accessible to gradient- methods. For fixed number of neurons and inputs, the spectral results remain true under symmetry breaking perturbation of the target.
Introduction
An outstanding question in deep learning (DL) concerns the ability of simple gradient-based methods to successfully train neural networks despite the nonconvexity of the associated optimization problems. Indeed, nonconvex optimization landscapes may have spurious (i.e., non-global local) minima with large basins of attraction and this can cause a complete failure of these methods. Evidence suggests that this problem can be circumvented by the use of a large number of parameters in DL models. In view of the complexity exhibited by contemporary neural networks and the absence of suitable analytic tools, much recent research has focused on two-layer ReL.U networks as a realistic starting The two-layer networks considered were typically of
point for a theoretical study [1 the form:
5 6, 7
a. = a (WW)), W M(k,d), E R
(1)
where =p(2) = max (0, 2} is the ReLU function acting entrywise and M (K,,, d) denotes the space of d matrices. order to isolate the study of optimization-relate obstructions due nonconvexity from issues pertaining to the expressive power of two-layer networks, data has been often assumed to be fully realizable. This was further motivated by hardness results which indicated strict barrier inherent to the explanatory power of distribution-fia free approaches operating in complete generality g 10 For the squared loss, the resulting. highly nonconvex, expected loss is
L(W, a: = EEDD (fl f(a; V,1)) )²}
1
where denotes probability distribution over the input space, W M d), a E TR* are the optimization variables, and (d, 3 gd are fixed parameters.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The choice of the d-variate normal Gaussian distribution for the input distribution has drawn considerable interest, e.g., [T] 12 14
17. Empirically. it has been observed that as the number of neurons l increases, the loss of models obtained using stochastic gradient descent (SGD) under Xavier initialization [8 decreases (see ( 19 ). The objective of this work is to study the mathematical mechanism behind this fundamental phenomenon. Using ideas based on symmetry breaking (see SeceSeecionn 2). we are able to employ techniques from representation theory and algebraic geometry to study how the loss landscape is transformed when the number of neurons is increased. key feature of our approach is the use of Puiseux series in and path based techniques. For example, we may define the spectrum of the Hessian as Puiseux series for real values of d and so determine the values of d (typically not integers) where eigenvalues change sign. These methods allow the proof of powerful analytic results: in this paper, we derive sharp analytic estimates of the loss and the Hessian spectrum at local minima allowing us to analyze the mechanism whereby spurious minima are annihilated when the number of neurons l is increased. Our contributions can be summarized by
15 16
Theorem (Informal) We describe several infinite families of spurious minima, partly characterized by their symmetry, and prove that:
Adding rather few neurons can transform symmetric spurious minima into saddles.
The Hessian spectrum remains extremely skewed with ( eigenvalues growing linearly with d, and (kkd) eigenvalues being (1)).
Increasing the number of neurons adds ((d) descent directions in ( ddmmeennnsio subspace dictated by the symmetry structure (i.e., the isotypic decomposition) of the loss function.
The loss remains (essentially) unchanged.
The formation of new decent directions allows gradient- mandient-based methods to escape spurious minima that exist in the original loss landscape the subtly of the results given in Theorem I consider a family of spurious minima with symmetry (S x S1) (the type II family described Section 3). Assume k = d. Spurious minima occur for d 2 6. Adding one neuron results in these minima occurring for d 2 8 - not promising. Adding two neurons annihilates all these spurious minima and creates no new spurious minima. The mechanism is finite, cannot be inferred from limiting case, and persists under forced symmetry breaking, and so applies beyond symmetric targets. If instead we consider the unique family of spurious minima with isotropy AS, (see [Section 3), we find that adding just one neuron annihilates these spurious minima. This occurs through the appearance of a multiplicity (d - eiiieennvl associated to the standard representation of Su on Rd-1 (all other eigenvalues remain positive). More precisely, if k: there are 3 strictly positive Hessian eigenvalues associated to the standard representation of Sy, each with d
d), and so detect models of reduced loss. To indicate
multiplicity d - 1. Modulo ( terms, they are 1 3. and 3 + 1. After the addition of one neuron (k- = d + 1), there are 4 Hessian eigenvalues associated to the standard representation of Sa and, modulo O(d 4) terms, these satisfy
111- 2 4 2
1
V5
1
-1-
0
4T
4
4T
This example highlights the special role that the standard representation plays in the annihilation of spurious minima (see Section 5) and the concluding remarks). The sharp estimates of the Hessian spectrum further demonstrate how symmetry breaking enables a complete characterization of the dynamics of gradient-based methods, locally, in the vicinity of symmetric critical points. The dependence of such methods on stability of critical points therefore indicates that attempts for global theory should be preceded by a good description of the mechanism by which spurious minima transform into saddles-the aim of this work.
Next, we relate our results to the existing literature.
Annihilation of spurious minima on account of over-parameeerrizaton. Existing methods for the analysis of optimization problem (2) include: mean- field (4, optimal transport (2) NTK (20 22
and the thermodynamic limit [ [6 23 24). These methods operate by passing to limiting regimes
where the number of inputs or neurons taken to infinity. growing number of works has limited
the explanatory power of such approaches 25 26 Approaches for addressing the loss landscapes in finite parameter regimes exist and include 6 which obtains several generalities on critical points, and [7] which studies conditions under which a single neuron can be added in contrived way to

---

turn given minimum in (d. d) into a saddle in (dd+ 1. d). However, as shown in the present work, families of minima M + d) exist. Indeed, families of minima of lesser symmetry are shown to require at least two additional neurons before turning into saddles.
Symmetry breaking in nonconvex loss landscapes. It has been recently found that the symmetry of spurious minima in optimization problem 22) break the symmetry of global minima (27) (see Section 2 for a formal exposition). A similar phenomenon has been observed for tensor decomposition problems in [28] and later studied [29]. The present work builds on methods developed in a line of work concerning this phenomenon of symmetry breaking. In [30], path based techniques are introduced to construct infinite families of critical points represented by Puiseux series in d In BI], results from the representation theory of the symmetric group are used, together with the Puiseux series result, to obtain precise analytic estimates on the Hessian spectrum. In 32) it is shown that certain families of saddles transform into spurious minima a fractional dimensionality. Moreover, the spectra of these families of spurious minima is shown to be identical to that of global minima to Odd -order. In [3], generic S2 Sæ-equivariant steady-state bifurcation is studied, emphasizing the complex geometry of the exterior square and the standard representations along which the minima studied in this work are created and annihilated.
The results above assume that the number of neurons is less or equal the number of inputs: k S d. The present work concerns the over peraaaaamtteezee case k > d (additional terms used in related contexts are over-specified, e.g.. (34 and over-realized, e.g.. (6). The study of the technically more demanding case of over- parameterization requires new methods and ideas, which we describe below.
We develop a method which allows the expression of eigenvalues in terms of the gradient entries. The approach is used to evaluate eigenvalues of -mulliiyiiylliiity analytically, and reveals hidden algebraic relations between criticality and curvature.
Eigenvalues of mld)lmuuliplicity are computed numerically using estimates of the Puiseux series coefficients. The estimates are obtained through numerical methods used either directly for a system of equations corresponding to different orders of the Puiseux series terms, for a reduced system of equations obtained by exploiting the geometric structure of the problem.
Lastly, Cauchy's interlacing theorem is used to reduce the complexity of the computation of descent directions afforded by over parameterization, and yields a tight characterization of linear subspaces along which spurious minima transform into saddles.
The methods are illustrated for eight families of critical points. Orthogonality of the target matrices is not required by the symmetry- -brekknn framework; other choices of target matrices, distributions, activation functions and architectures have been considered in previous works, and are topic of current research.
Organization of the paper. The proof of Theorem 1 is in four parts: symmetry the loss function, families of symmetric minima, Hessian spectrum, and change of stability under over- parameterization. Proofs and technical details are deferred to the appendix.
2 Symmetry and the loss function
The presentation of our results requires some familiarity with group and representation theory. Key ideas and concepts are introduced as needed.
The symmetric group Sa, d E N, is the group of permutations of [d] {I..... .l.....,), d}. The orthogonal group O(d) is the subgroup of all orthogonal linear maps on Rdd We may identify Sa with the subgroup of ((d) consisting of permutation matrices. Thus Sa acts naturally on [d] (as permutations) and orthogonally on &dd (as permutation matrices).
For k d E N, there are natural actions of St and Sa on the space M d) of k x d matrices: Sa permutes rows, Sa permutes columns. The loss function (2) is invariant under row permutations: L(oW)= L(W), for all E Ss -hhwhatever the choice of V. B. The product action of S2 x Sa on (kk, d) plays a central role in the study of invariance properties of L. If A = [Ay]] E M d), (TT, p) S& x Sa, then
(T, [Ang] = [A, 1(9,0 '6), T E St, E Sa, (i.j) E [K] (d.
(3)
3

---

The action can be defined in terms of permutation matrices. k 2 d, the diagonal subgroup ASa of Sk x Sa is defined by ASaa = ((g.)) 9) g E S2 S Sz}. Clearly, AS, = Sp-
Henceforth assume k: 2 d. Regard M(d, d) as the linear subspace of M d) defined by appending k - zero rows each matrix in (d,, d). Let V M(; d) denote the matrix determined by the identity matrix la E (d, d). By the orthogonal symmetry of the Gaussian distribution, our results will hold for any V determined by matrix in O(d). We shall not consider training processes but rather concrete instances of families of critical points, and so throughout weights are assumed fixed. The weights of the second layer of critical points studied in the present work consists of positive weights and so, by the positive homogeneity of the ReLU activation, there is no loss of generality in assuming that the second layer of weights is set to ones, i.e., a 3 Ix Inj being the i x j j-matrix with all entries equal to 1.
Optimization problem 2 has rich symmetry structure; for our choice of V,, a and B, L Sk Sa- invariant (27). It is natural to ask how the critical points of L reflect this symmetry. Given W E M (k: d). the largest subgroup of Sy Sa fixing W is called the isotropy subgroup of W. The isotropy group quantifies the symmetrr of W. If k d, V has isotropy group ASa and every global minimizer of L lies on the Sa x Są-orbit of V 7 300] Empirically, if k 2 d. non-degenerate (i.e., no zero Hessian eigenvalues) spurious minima of L tend to be highly symmetric in that their isotropy groups are conjugate to large subgroups of A.S. Indeed, we suspect that for our choice of V, the isotropy of non-degenerate spurious minima is always non con-trivial and conjugate to a subgroup of AS
If d, the isotropy of V is not a subgroup of AS, it contains the subgroup la S of row permutations. Perhaps surprisingly, L is more regular at critical points of spurious minima than at points giving the global minimum: if le d, analyticity of L at W V fails. If k: > d, V has row of zeros and L is not differentiable at W = V [ (see also (7]. It may easily be shown that there k- d-dimensional compact connected Sn x Sa-invariant simplicial complex A C M(; d) consisting of all matrices that define the global minimum value of zero (see (see Section A.7). Necessarily, A contains the S₁ Sa orbit of V. At boundary points of A, L is not differentiable. The Hessian, defined on the interior of the simplex, is always singular. Here our focus will always be on families of spurious minima with degeneraeete critical points.
3 Families of minima: structure and basic properties
Families of spurious minima often have characteristic properties. For example, the asymptoties in d of the loss or their chance of being detected by SGD. For a systematic study of the optimization landscape of L. we need to categorize minima and understand their distinctive analytic properties. Both isotropy and the notion of a regular family play an important role. Throughout we assume == d m, for all d 2 do. where m 2 is an integer constant.
If G is subgroup of ASa. let M(k.)) = (W E (k, d) 9W = W, Vig E G} denote the fixed point space for the action of G on ((k Every Sa Sy Sæ-equivariant vector field on M (k. d) is tangent to (k, d)@ and so VL is tangent to M d)c Hence E (k, d) is a critical point of (K, d) iff c is a critical point of L. The inclusion i [d]-[d + 1] induces a natural inclusion id Sa C Sa+1, where (Sa) fixes d + 1. More generally, given a positive integer and do > p, we have a sequence of inclusions id.p : Sa-p x SSp-Sat1-p x Sp. 2 dg Identifying Sa with ASS, a sequence (Ga)dzá, of subgroups of AS is natural if for some positive integer p < dg. (a)
(Ga) C Gdt1, and (b) dim(M(K (k. d)aa) is independent of d 2 do (assume ls 2 d).
Example 1 Set G. = A(Sa-p x Sp) and m be a positive integer. If 0, then Ga = ASa and dim( M (d m, d) 2 d 2 dg 2: if 1, then dim (d m, AS8 1x81)) 5 2m, d 1 3: if 2 2, then (M + m, A(S- = 6 2m, d 2 4.
If (Ga)azd, is natural, we often identify (k; Ga with R d dg. where dim (Kk,d)Ga) = N. We define linear isomorphisms E R² -M d)Ga for the families of Example 1 Let I; I.s - T;, i E N. The matrix E(G). 5 E V. is expressed as block diagonal matrix [Bag]. where each Bi, linear combination in the coordinates of & of the matrices Izj. 1, and 7;. For example, if p 1, m > 1, then N = 5 2m and E(fr,-.. ...) is the (2 + m) x 2-block matrix

---

[Byy] E M(d - m, d) 1x51) defined by
B11 +
B12 E3I8-1.11
B: = -,, B2 = 12i4 I1,1, 2 S 2
Similar expressions hold for the other families. In practice, we restrict the vector field VL to M (k;,d d)G. and then pull back this vector field using = to vector field Fa RN The Jacobian of Fa is then equal to the Hessian of V ((CM d))a). Observe that Fa does not depend on a choice of inner product on RR:; indeed, we take the standard Euclidean inner product on R- (E I -M (k. d)c is not an isometry). Since Fa(E) = E (E((EE we may read off the components of Fc( directly from the corresponding matrix entries of V.. We find that Fa is a continuous family of vector fields on R in the real parameter d. Obviously, no such statement can hold on (K; d) as the dimension of M(k, d) depends on d. Moreover, the vector fields Fa will be real analytic outside of thin (semianalytic) subset of RN,, Indeed, Fa is subanalytic (35] but the real analyticity statement easily proved directly and suffices for our applications. All of this allows us to "connect" the critical points c(d) E M (k, d)ca, d 2 do, by curves in RN and develop a path approach to our problem.
path-based based
Definition 1 (Notation & Assumptions as above.) A family (E(d) = E(((d) d 2 da} of critical points of L with isotropy G. ASa weakly regular if (Ga) natural and for d 2 do
(a) There is continuous curve 7/a [0, 1]-R" of critical points of Fa joining c(d) to c(d + 1).
(b) C is real analytic at E(c(d)) E (k,d).
(c) Fa is real analytic on a neighbourhood of %a((0, 1)) C RN..
(d) The Jacobian of Fa along "ia is non-singular.
If lima-+so c(d) = coo E N exists and is bounded (Euclidean norm on IR-N), ). the family is regular.
Using (c,d), and the real analytic implicit function theorem, 7/d is real analytic. The family defined by c(d) = is not weakly regular as (b) fails even t: = d.
It may be shown, using results on subanalytic sets and the Curve Selection Lemma [6), that every regular family has fractional power series (FPS) representation. That is, with the notation and assumptions of Definition 1, there exist d1 2 do and minimal b E N such that each component ce(d) of ((d) E T.." is given by the convergent power series
c(d); = Σ c ie i, [N]. 1=0
(4)
Under the assumption of weak regularity, there may be Puiseux series representations (30] Exam. 4.13] and co lies in the one point compactification of R. In practice, rather than use the general result, we prove directly that a family has an FPS representation. Verifying regularity for sufficiently large do, is usually straightforward or trivial. We refer to SoeSetion A for examples of construction of FPS representations when d.
The FPS representation for families of critical points is important both theoretically, and computa- tionally and yields Puiseux series representations of the objective value and Hessian spectrum. was shown in (30, Section 8] that for k = d several (regular) families of critical points with isotropy G. ASS x Sp). P E {0, 1}. had FPS representations in d 1 (so b = 2). Each coordinate of foo = lim c(d) E RN was either +1 or zero. For examples of FPS representations with A = d 3). see 332 Explicit construction of the coefficients in these FPS examples is relatively straightforward and algebraic formulae can be given for low order terms. When k d, analysis is harder. is not always possible to give low order coefficients in a simple algebraic form. Moreover, there may be multiple regular families with
and G. = AS x Sp).
the same limiting value coo E N
Let p 2 and take Ga = A(Sa-p x Sp) as Exumple 1 critical points with isotropy (Ga)azd, is of type I (resp. type M) if as do0, the diagonal ele- ments of the (d - p) x (d (1)p-blocc corresponding to the action of ASa converge to - (resp. +1).
Definition
regular family of
5

---

In terms of FPS, a family is of type I (resp. type II) if C1.0 = -1 (resp. +1).
Remark 1 When & d, suspect that the initial coefficients c, of the FPS of a regular family with isotropy (SSapp x Sp). p 2 O, satisfy C,o E {+1,0). However, this is false if k >> d-we give an example later. Moreover if k d, and with a slight extension of the notion of regular family, there is a regular family with G2d = (SS x Sa), d E N, with 61,0 +l, C, =-1 |coefficients corresponding to the diagonal entries of the principal blocks associated to Sa la and La Sa).
Henceforth, we emphasize & > d, and families with isotropy A x Sp), p e {0, 1}. However, the methods are quite general.
Theorem Suppose that C is a regular family of critical points, Assume that initial terms of the asociated FPS do not all vanish and b E {2, 4}. If the isotropy Ga ASa, k {d, + 13, then e of type I; if the isotropy Ga = ASSa11 x Si), k E {d, d 1, 2}, then E is either of type or rype II and there exists at least one family of each rype. If l d there is precisely one type I family and, if p # O. one type Il family.
Remark 2 For k = d. both type I and rype II families are spurious minima [3 32V. However, empirically, type I minima are not detected by SGD when Xavier initialization is used. Since the loss at type II minima decays as ( and the loss at type I is ((1) (independently of the isotropy), it may be lempting loss at rype I minima. However, this turns out to be false: Assume = d. Under Xavier initialization, (1 ) S Ew [[(W)) S (1 ) (see Section A.6
argue that the expected initial loss under Xavier initialization is smaller than the
As increase k- d, the original type and II critical points of spurious minima persist degenerate critical sets and new regular families of critical points of the same type are generated. Thus, if k d 1, and Gd F AS3. two regular families of type I points are generated which are swapped by the permutation of rows d and d+I 1. Similarly for families of type II. When k- d = 2, 3 = |Sg] new regular families of type critical points appear; similarly for type points, which do not originate from the original families and are not spurious minima, may appear. See See(Section A.7 for degenerate critical point sets occurring on account of prrr--aratterrzaioonn
Additional families of critical
Our focus will be on the families of type and II critical points that arise through the above mechanism. For given isotropy G. A(Sa-p Sp), p {0, 1). type X and k 2 d, with k d fixed, let ex denote choice of regular family of critical points (c).m (d) E (K; d)G,) that originates from the unique regular family of critical points of type X that exists when = d. is enough to analyze just one of the type X families when k d as. by equivariance, the choices lie the same Sa x Sororbit and so have similar Hessians. Once the existence of the FPS representation for the families ex has been proved, the next step is estimate the Hessian spectrum, the topic of the next section.
We conclude with examples illustrating the quantitative power of our approach.
Example 2 (1) We investigate how the loss [(c))m) depends k d for the rype II families Cl {0, 2, For
O, the initial coefficients of the FPS are found using Newton-Raphsoo method applied either directly for a system of equations corresponding to different orders of the FPS coefficients Section A.3 or for reduced system of equations obtained through explicit use of the geomelry of the problem Section A.I [(c),.)) = and + O(d- then
We give the asymptotics modulo O(d $) and find that if
2 2 01 2.67254813890 02 2.67193392209
00 2.97357632715 (=
(2) Consider C(c),,m) for type families. We find that C(((, for
m (0, 1) Higher order terms are m- -e-deenndett but can be computed, as they can if 0. For example, if
+ ).
4 + (3) We conclude with an example where the FPS is in powers of d and two components of coo E R
p= = O, m = 1 then [(((,)) = 2/2
3x d + (-1 -
+ 8).
do not lie in 03. If k d + 1, the initial terms of the FPS for a type I family c(d) of critical

---

points of spurious minima are given by
(()i 2d
+ d
+(d
(()2 = 2d Vx 2d + 0(d
(()s = d'' 6+ 3t
d 3 O(d )), ((d) = Vx -2
d + 0ld
4 π
2
+ 3π
c(d)s V -
c(d)s
d + O(d
d 0(d
8 T
6 3m
c(d) = 2
+
d + (dd
8x 8 -
(see Section A.5 for details). The loss [(c),))
4 d
(x-2) d (dd
3
4 Hessian spectrum
The FPS representation makes possible an analytic characterivation the Hessian spectrum using tools from the representation theory of groups Section B for brief review). The main tool used is the isotypic decomposition relating the isotropy of a given point to minimal invariant subspaces of the Hessian. We begin by presenting the isotypic decomposition needed for the over-parameterized case.
Let 2 d. Regard M (ki, d) as an Sa-representation (diagonal action on Md, d) ((, (k),))). By restriction, (K, d) is S Sp-representation,, where 9 = d p. E {0, 1} (the case interest here) the isotypic decomposition uses 4 irreducible representations of Sg. when d 2 4: the trivial representation of degree 1, the standard representation s of S₂ of degree 1, the exterior square representation = A25, of degree (9-1)(9-2) and a representation
9. and S, Sp C Sa. If
2
D, of degree s(y=31 (associated the partition (q 2, 2) 37 decomposition is
For p E {0, 1], the isotypic
M(k, d) (m + 3p + 2)t + (pm 2p + 3)5 Fg + Dg.
Since the representations Fq. Fy contribute eigenvalues, of total multiplicity q² 24 + 1, we have
Lemma k m 2 and p E (0, 1], then of the kd eigenvalues of the Hessian at a point of isotropy A A(Sa-p Sp):
1. (df) are populated by two eigenvalues: the z- and t-reprrssentation eigenvalues,
2. Al most O(k - d) eigenvalues are distinct.
Lemma limplies that the isotropy type of point strictly restricts the number of distinct eigenvalues of the Hessian spectrum. For fixed & - d, the and the n-representation eigenvalues account for kd (dd of the eigenvalues. We show that for all families of critical points considered here, the r- and the p-representation eigenvalues are identical to order Od
Theorem For family of critical points of isotropy A(Sa-p X Sp), E {0,1} and k as in Theorem kd (d)) of the Hessian eigenvalues are populated by the two eigenvalues:
1 11 1 + O(d and 1 + 7 + O(d
4 2m
associated to the y- and the trreeresentation, respectively.
The derivation of Theorem 3 builds on technique used 31 32
and is directed towards the case where k >> d and the coefficients of FPS may not be given in simple algebraic form. Specifically, we rewrite the expression for the Hessian eigenvalues terms of the gradient entries. Since gradient entries vanish at critical points, this allow us to evaluate the eigenvalue expressions. For example, the Puiseux series of the j-eigenvalue of Type A(Sa-1 x -criitica points is
2x + [
Fa,1 c1.2/d Fui
[a ld') Faid [dbb Faidk + +Od (6)
7

---

with Fa. indicating the coefficient of d in Fa.s. Since Fa,s vanish at critical points, X
+ Equation further demonstrates the sensitivity the y-cigenvalue to variations in the FPS coefficients and in different orders of the gradient terms, see see|Section B.I Algebraic relations between criticality and curvature indicate therefore a certain rigidity the loss landscape. Relations of similar nature exist between criticality and the loss a point.
follows from Theorem that all Hessian eigenvalues not associated to the trivial or standard representations are strictly positive for sufficiently large d. Consequently. annihilation of spurious minima a family must be tangent an invariant subspace of the sum of the isotypic components for the trivial and standard representations. Generically, it is to be expected that the subspace will be isomorphic to either the trivial representation or the standard representation.
Over- ever-parameterization
Having computed the r- and the I-eigenvaluus, we now turn describe how the eigenvalues associated to the trivial and the standard representations vary when the number of newrons is increased. We find that while eigenvalues associated to the trivial representation remain strictly positive for all sufficiently large d-some eigenvalues, associated to the standard representation, become negative, indicating transition from minima saddles along the isotypic component of the standard representation. We start with points of isotropy AS
5.1 Critical points of isotropy ASAa
if le E {d, d + 1}. there is one regular family of critical points with isotropy ASa: the type family c,,, i = k d. The representation-thest -therrrtttttttttttiitiii tools used in Section 4 yield a complete characterization of the Hessian spectrum of both familics of critical points (sce the discussion following the statement of Theorem Tin in the introduction for more details).
By Theorem 2
The spectral analysis of the Hessian reveals that:
A. C is family of minima.
B. Adding one neuron turns it into the family J) of non-degenerate saddles where the negative eigenvalue of the Hessian at C) is associated to the standard representation
Since the negative eigenvalue of the Hessian at C) is associated to sas there are exactly descent directions, out of d(d+1 1) possible directions in M (d++ 1, 1.d). lying the 4d 4-dimensional isotypic component 4 spanned by (only nonzero elements are described):
1. The (d - -iddimensional space of (d + 1) x d-matrices [y1z] where for i, E [d] Yij 24 Zj+ for some (= ... 2a) E Rd with Eie[d 2; 0.
(d-1))ddiimme 1--dddmmmniionall space of (d+ 1) d-matrices [Wig] where for i, [d], i + Yig žj 2. The (d-1)
where (.,, 2g)= I with Σie(4 2; O.
3. The (d - 1) dimensional space of (d + 1) x d-matrices whose diagonal elements sum up to zero.
4. The (d - 1) dimeensional space of (d + 1) x d-matrices whose (d + 1) 'th row elements sum up to zero.
No regular families with isotropy AS, exists if two neurons or more are added, i.e., k - d 2 2 (see Section A.7
5.2 Critical points of isotropy A(Sa-1 x S1)
Consider the type II regular families CHI Cll, and C/i corresponding to k d, d + 1 and d + respectively. We show that negative eigenvalues of the Hessian appear when = 2 but not k d = 1. The same result (and proof) hold for the type I family.
For d, h: = d + 1, the eigenvalues associated to the trivial and standard representation s are strictly positive see Table 5.2 By Theorem 3 the and the p-representation eigenvalues are also

---

Isotypic component
Degree
d d+1
Symmetry AS
Symmetry AS
Trivial representation
0.0908
0.0044, 0.0843
0.25
0.2632, 0.3121
mult. 5, if k: d mult. 7, if = d+1
0.1591d -.394d
0.1591d +.755 0.7546
0.25d + 0.25
0.25d + 0.5
0.25d + 0.8471
0.25d + 1.0979
Standard representation S
2-2
0.0908
0.0230, 0.0908
0.0908
0.0936
mult. 5, if k: = d
0.25
0.2693
mult. 6, if l: = d d+1
0.4091
0,5340
0.25d + 0.25
0.25d 0.5
Loss
(l1/d)
(11/d)
Table I: Type II critical points with symmetry ASa-1. The Hessian eigenvalues associated to the
trivial and the standard representation are given four decimal places, modulo Oid O(d-r)-terms. -teems.
strictly positive. Therefore, we have families of spurious minima for k = d, d + 1. For k: = d 2. critical points in the family e) are saddles, with strictly negative eigenvalues associated to 5 To show this, we take different route so as to reduce the complexity of the computation. Consider the 2d x 2d-submatrix H of the Hessian corresponding the last two rows of the weight matrix. By Cauchy's 's interlacing theorem [39]. the smallest cigenvalue the Hessian is bounded from above by the smallest eigenvalue of f. Therefore, it suffices to prove that H has a negative eigenvalue. Since the isotypic decomposition corresponding to H consists of exactly two of the subspaces associated to 9,-1, the problem is reduced to computing the spectrum of 2 x matrix. Using Puiseux series representation, we show that modulo O(d 2 -teems the two eigenvalues of are a = 0.8060 and λ -0.1198... Hence there exists (d - 2) -dimensional eigenspace of descent directions, projecting onto the associated eigenspace for H. Applying Cauchy's interlacing theorem again, there must also exist positive eigenvalues associated to 5.-1-
Theorem 4 (Notation & Assumptions as above.)
ASa-symmetric critical points of type are minima for k: d and non-degenerate saddles for d d 1 with a (d -)-dimensional eigenspace of descent directions.
Critical points of isotropy A(Sa-1 x S1), type or II, define regular families of spurious minima for k d, d + 1, and non-degenerate saddles for k. d + 2, with at least (d (d- 2)-dimensioo space descent directions.
Empirically, when lt d + 1, minima of isotropy A(Sa-1 S1) are not seen for d < 8 (they d and d 2 6) and the probability to detect them using gradient descent is much lower for small values of d > [19] (type minima
not detected under Xavier initialization). Theorem 4 implies that when = + 2 there are no spurious minima of type of symmetry A(S.- x S1) and the descent directions empirical results. The small eigenvalue 0.0230 associated to 5 when A: = d + indicates that we close change of stability (bifurcation) of the critical point for gradient descent. Bifurcation of the trivial solution on 5 1 is special and quite exceptional. In our case, the trivial solution will be sink for gradient descent (i.c., a strict local minimum of the loss function), when
tangent to a copy of s4-1. The last point is erucial for understanding the
+ and source (i.c., strict local maximum of the loss function) when &: = d - 2. The change of stability results from the collision of a large number of saddles of high index with the sink, followed by the emergence of source and large number of saddles with low index. The high index of the saddles converging to the sink, implies that the basin of attraction for the sink shrinks rapidly as the saddles approach the sink. We refer to (33 Sections 1.1, 4] for more on this phenomenon. As we increase d, families ell p > 1, of spurious minima appear which may not be annihilated by adding two neurons. However, such minima were found in [9 when & = d + 2,d < 20 (they were for k = d + 1). The empirical results provide strong support for a change of stability associated to 9 and suggest the unique role this representation may play in understanding
patamerrizaaiiinn

---

Concluding Comments
The rich symmetry structure exhibited by the loss function 2 makes possible an analytic study of the associated nonconvex loss landscape. The approach is twofold. First, the presence of symmetry breaking allows an efficient organization of an otherwise highly complex set of critical points, offering new ways of recognizing, differentiating and understanding local minima (Section aaand Section 3). Second, for a given family of critical points, symmetry grants a parameterization of fixed dimensionality, independent of the ambient space, which permits a new array of analytic and algebraic tools (Section (Section 5).
In this work, the symmetry breaking framework is used for investigating the nature by which over-paramett vve-paramettrrizaionn contributes to making the loss landscape of (2) accessible for gradient-base methods. We find that increasing the number of neurons transforms spurious minima into saddles: decent directions are formed along linear subspaces corresponding the standard representation Sd of Sd, ascent directions along other representations of Sa persist, and the loss remains essentially the same. The process by which spurious minima turn into saddles suggests a powerful mechanism enabling minimization of the loss (rather than the gradient norm [40] 41 42 via computationally efficient local search methods, and further highlights the importance of the intricate interplay between symmetries inherent to data distributions and those displayed by neural network models.
Our spectral results assume the target V has high symmetry but apply also to asymmetric problems. In the cases we discuss, the transition from saddle to minimum, or minimum to saddle, occurs at a non-integer value of d. Hence, integer values of d, critical points are non-degenerate. It follows that for the families p.m we consider, there is an open neighborhood Ul of V = Ia E Md, d), such -egeneeeee critical point close to each
that for all V E ut the loss function L' for V has point of the ((Sa-y x Sp)-orbit of ex p.m with the same number of negative eigenvalues (counting multiplicities). Critical points and eigenvalues depend continuously on V l and the Hessian spectrum remains extremely skewed.
There is the problem of understanding the geometric mechanisms underlying the transition from minimum to saddle. As already indicated, this is closely related to the geometry of the standard representation Su of Sa. For simplicity, assume d 2 + 1 is odd (similar results hold if d is even (33 ). Gradient vector fields on 9, always have a critical point at the origin which is never non-degenerate saddle but is (generically) either a non-degenerate minimum maximum. The transition between minima (sink for the gradient descent, index 26) and maxima (source, index 0) can be achieved locally (that is. as local deformation of the landscape geometry) by 2d non-degenerate saddles of index 2 passing simultancously through the origin and emerging as 2d-1 - 1 non-degenerate saddles of index S l. No new minima or maxima are created. Forced symmetry breaking leads to great complexity near the transition but minimal models of complexity can be given (op. cit., Section 4).
Rather than striving for generalization, our approach in this work has been to focus on an analytically tractable case, one already acknowledged difficult (2 4 5 9 19 20), that helps elucidate some of the key foundational questions. The phenomena described are robust and so already have the power to disprove or support general conjectures in DL [30] 31 (3). The symmetry breaking framework used to study these phenomena generalizes beyond the families of minima considered in the present work [43) and applies to other choices of activation functions and distributions (27 288. In addition, numerical work indicates that minima of the empirical loss are also symmetry breaking, and so allow theoretical investigations of the empirical loss landscape as well as algorithmic biases (see, e.g., 44
within the new analytic framework. The full scope and power of symmetry breaking in DL, and more generally stochastic nonconvex optimization, remain to be discovered.
Acknowledgments and Disclosure of Funding
We thank Noa Aharon, Daniel Soudry and Avi Wigderson for valuable discussions and constructive suggestions. The research was supported by the Israel Science Foundation (grant No. 724/22).
10

---

References
[1] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference machine learning. PMLR, 2017.
[2] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for parameterized models using optimal transport. Advances in neural information processing systems, 2018.
[3] Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee. Theoretical insights into the op- timization landscape of aver-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
[4] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665- E7671, 2018.
[5] Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Generalisation dynamics of online learning in wverpparameterised neural networks. arXiv preprint 1901.0900000003 2019.
[6] Yuandong Tian. Student specialization in deep rectified networks with finite width and input dimension. In International Conference on Machine Learning. PMLR, 2020.
[7] Itay M Safran, Gilad Yehudai, and Ohad Shamir. The effects mild over weer-prraeterization on the optimization landscape of shallow relu neural networks. In Conference Learning Theory. PMLR, 2021.
[8] Avrim Blum and Ronald L Rivest. Training 3-node neural network is np-complete. In Advances neural information processing systems, pages 194-501, 1989.
[9] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In 6th International Conference on Learning Representations, ICLR 2018.
[10] Ohad Shamir. Distributioon-specffi hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):1335-1163 2018.
[11] Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns me-hiiden-laayr cnn: Don't 't be afraid of spurious local minima. In International Conference on Muchine Leurning. PMLR, 2018.
[12] Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit Dhillon. Recovery guarantees for one-hidden-layer neural networks. In International conference machine learning. PMLR, 2017.
[13] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pages 597-607, 2017.
[14] Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In International conference on machine learning. PMLR, 2017.
[15] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning ene-hidden-layee neural networks with landscape design. In 6th International Conference Learning Representations, ICLR 2018.
[16] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps in learning two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, 12:413)) 2019.
[17] Shunta Akiyama and Taiji Suzuki. On learnability via gradient method for two-layer relu neural networks in teacher-student setting. In International Conference on Machine Learning, pages 152-162. PMLR, 2021.

---

[18] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256, 2010.
[19] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. International conference on muchine learning. PMLR, 2018.
[20] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[21] Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. Advances in neural information processing systems, 2016.
[22] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on learning theory. PMLR, 2020.
[23] Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Advances neural information processing systems, 32, 2019.
[24] Elisa Oostwal, Michiel Straat, and Michael Biehl. Hidden unit specialization in layered neural networks: Relu vs. sigmoidal activation. Physica A: Statistical Mechanics and its Applications, 564:125517, 2021.
[25] Gilad Yehudai and Ohad Shamir. standing neural networks. Advances in Neural Information Processing Systems, 32, 2019.
On the power and limitations of random features for under-
[26] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33, 2020.
[27] Yossi Arjevani and Michael Field. On the principle of least symmetry breaking in shallow relu models. arXiv preprint urXiv:/912.1 1939, 2019.
[28] Yossi Arjevani, Joan Bruna, Michael Field, Joe Kileel, Matthew Trager, and Francis Williams. Symmetry breaking in symmetric tensor decomposition. arXiv preprint arXiv:2103.062. 2021.
[29] Yossi Arjevani, Michael Field, and Gal Vinograd. Symmetry & critical points for symmetric tensor decomposition problems. In preparation.
[30] Yossi Arjevani and Michael Field. Symmetry & critical points for a model shallow neural network. Physica D: Nonlinear Phenomena, 427:133014, 2021.
[31] Yossi Arjevani and Michael Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry. Advances in Neural Information Processing Systems, 33, 2020.
[32] Yossi Arjevani and Michael Field. Analytic study of families of spurious minima in two-layer relu neural networks: A tale of symmetry ii. Advances in Neural Information Processing Systems, 34, 2021.
[33] Yossi Arjevani and Michael Field. Equivariant bifurcation, quadratic equivariants, and symmetry breaking for the standard representation of s k. Nonlinearity, 35(6):2809, 2022.
[34] Roi Livni, Shai neural networks. Advances neural information processing systems, 27, 2014.
and Ohad Shamir. On the computational efficiency of training
[35] Edward Bierstone and Pierre Milman. Subanalytic geometry. Model theory, algebra, and geometry (ed. by Haskell, D. et al.), MSRI, 39:151-172, 1998.
[36] John Milnor.
Singular points of complex hypersurfaces. Ann. Math. St, 61:591-648, 1968.
[37] GD James. The representation theory of the symmetric groups Springer, 1978.
12

---

[38] William Fulton and Joe Harris. Representation theory, volume 129 of. Graduate Texts in
Mathematics, 1991.
[39] Charles R Johnson and Roger A Horn. Matrix analysis. Cambridge university press Cambridge, 1985.
[40] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[41] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Progtii Programming, 108(1):177-205, 2006.
[42] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50, 2022.
[43] Yossi Arjevani and Michael Field. Bifurcation, spurious minima and vver-paramerization. In preparation.
[44] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Interaational Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rKPihoqlTHf", "reviewer": "Reviewer_DYe8", "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.", "questions": "Typo:\n\nlines 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?\n\n\nQuestions:\n\nI 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.\n\nWhat will be the main barrier in using these methods for analyzing k-d>2?\n\nFor 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?\n\nRegarding 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?\n\nfor line 200, why it is reasonable for the loss at initialization to be compared to loss in minima?\n\nRegarding 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?\n\nIn section B1, what is an eigenvalue transition matrix?\n\nWhat is the meaning of subscripts 1,2,3 in $\\nabla \\mathcal{L}$ in beginning of page 19?\n\n", "limitations": "I don't see any negative societal impact, except for misuse\\illegal use of Neural networks. ", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.\nfor 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N6Jg8TxcbqH", "reviewer": "Reviewer_WAgA", "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.  \n", "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?\n\nLet $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.\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- This is a strong theoretical paper discussing the spurious local minima of two-layer ReLU networks.\n- 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.\n\nWeakness:\n- 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. \n    -  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. \n    - In Line 152, what does $i_g:\\Delta S_d\\subset \\Delta S_{d+1}$ mean?\n    - 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?\n- 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.\n- 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. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GwXQfc4OBjd", "reviewer": "Reviewer_XqeF", "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. ", "questions": "- Why is it reasonable to study permutations of the input neurons?\n\n- Is it possible to provide specific weight matrices that cover the different symmetry classes?\n\n- 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", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- 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. \n\n- 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.\n\n\nWeaknesses:\n\n- The paper makes a number of assumptions, which questions the applicability of the results to networks in practice:\nThe 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. \n\n- 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.)\n\n- 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.\n\n- 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?\n\n-------\nAdditional Comments:\n\nI 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.)\n\nThe 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.\n\nLine 116  “The loss function is always invariant...“ This only holds if the same permutation as applied to the output weights \n\nLine 120, the meaning of the equality sign is not defined\n\nLine 126: “L is invariant“. I suppose, the authors mean that the teacher network is invariant. \n\nLine 134: what means “fixed“? V was a fixed value to start with. Probably, the authors mean “invariant under“?\n\nLine 138: what exactly is meant by the terminology “nondegenerate“ and “spurious“?\n\nLine 138,139 is missing a reference for the empirical evidence\n\nLine 143, reference is missing to the “recent work“\n\nLine 163, The notation G_c(d) is not defined\n\nLine 185: Def 2 requires more explanation “corresponding to the action of delta S“, \nPossibly it should also be discussed in more detail why the diagonal elements converge to either +1 or -1.\n\nLine 198 “Since the loss at type II minima decays...“ Please provide an explanation or a  reference\n\nLine 267 Typo: Adding one neuron should change the second subscript\n\nLine270: “This isotypic component may be written as...“ Please provide an explanation or a  reference\n\nLine 357: This second part of conclusion is lacking context to understand this part. In particular, please revise or explain the following terminology: \n“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“\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "62F1HRKHbgt", "reviewer": "Reviewer_fCuP", "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).\nFor 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. ", "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). \n\nline125: 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. \n\nTypos/detailed comments:\nline 60-61: adding one neuron results in these minima ... unclear sentence\nline 101: citation needed\ncaption of Table1: I don't understand how lines 4-6 and lines 10-12 are related to the table. \nline 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)?\nline 152: definition of inclusion is unclear to me \nline 289: (typo) so turn minima -> to turn minima \nline 367: what is meant by non-integer values of $d$? \n\n", "limitations": "The paper is written in a neutral way, and the written text reflects the findings in the theorems. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nQuality: 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. \n\nClarity: 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? \n\nSignificance: 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. \n\n\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept