Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
Year: 2022

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 a 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 Θ(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 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. 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 to a complete failure of such methods. The nature by which nonconvex problems associated with neural networks deviate from generic ones is currently not well-understood. In particular, much of the dynamics of gradient-based methods follows from the curvature of the loss landscape around local minima. It 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-based methods towards minima of high quality. However, already establishing the very existence of spurious minima seems to 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 on two-layer ReLU neural networks of the form

text: 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 to a complete failure of such methods. The nature by which nonconvex problems associated with neural networks deviate from generic ones is currently not well-understood. In particular, much of the dynamics of gradient-based methods follows from the curvature of the loss landscape around local minima. It 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-based methods towards minima of high quality. However, already establishing the very existence of spurious minima seems to 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 on two-layer ReLU neural networks of the form
k∑
i=1
αiϕ(〈wi,x〉), W ∈M(k, d), α ∈ Rk, (1)
where ϕ(z) = max{0, z} is the ReLU activation function acting entry-wise, M(k, d) denotes the space of k×dmatrices andwi denotes the ith row ofW . We are primarily interested in characterizing various optimization-related 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
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and are labeled by a planted target network. We consider directly optimizing the expected squared loss, which results in the following highly nonconvex optimization problem:
L(W,α) := 1 2 Ex∼N (0,Id)
[( k∑
i=1
αiϕ(〈wi,x〉)− d∑
i=1
βiϕ(〈vi,x〉) )2 ] , (2)
where k denotes the number of hidden neurons, W ∈ M(k, d) and αi ∈ Rk are the optimization variables, and vi and βi 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, as 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 as 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 student network so as to fit the output of a teacher network. The ST framework offers a clean venue for analyzing optimization-related aspects of neural network models in the spirit of 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 out 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, to analytically characterize important aspects of the associated highly nonconvex landscape for a finite number of inputs and neurons.
Our contributions, in order of appearance, can be stated as follows:
• We demonstrate that, empirically, and in a well-defined sense, minima in two-layer ReLU neural networks 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 it 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 ≥ k, and determine the exact fractional value of d at which critical points turn from saddles into spurious minima—a key ingredient in understanding how over-parameterization annihilates spurious minima.
• Based on the unique access to high-dimensional spectral information, we closely examine a number of hypotheses in the machine learning literature pertaining to curvature, optimization and generalization. In particular, we prove that the Hessian spectrum at 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 to O(d−1/2)-terms, 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 a 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 a 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.

heading: 1 Symmetry breaking in two-layer ReLU neural networks
text: Optimization problem (2) exhibits a very rich symmetry structure. Indeed, the loss function L is invariant to left- and right-multiplication of W by permutation matrices (see Section A.1 for a formal proof), i.e., L(W,α) = L(PπWP>ρ ,α) for all (π, ρ) ∈ Sk × Sd, where Sm generally denotes the symmetric group of degree m, and
(Pπ)ij =
{ 1 i = π(j),
0 o.w. .
It is therefore natural to ask how the critical points of L reflect this symmetry. For example, the identity matrix Id, one of the global minimizers of L for the case in which V = Id, α = β = 1d and k = d, is invariant under simultaneous left- and right-multiplication by any permutation matrix. Indeed, PπIdP>π = PπP > π = Id for any π ∈ Sd. (Modulo group conjugation, this holds for any global minimizer of L. See [6, Proposition 4.14.].) This simple observation is conveniently stated using the concept of the isotropy group. Given a weight matrix W ∈M(k, d), we let
Iso(W ) := {(π, ρ) | (π, ρ) ∈ Sk × Sd, PπWP>ρ = W}, (3) Thus, we have Iso(Id) = ∆Sd, where ∆ maps any subgroup H ⊆ Sd to its diagonal counterpart ∆H := {(h, h) | h ∈ H} ⊆ Sd × Sd. Empirically, and somewhat miraculously, spurious minima and saddles of L tend to be highly symmetric in the (formal) sense that their isotropy groups are (conjugated to) large subgroups of ∆Sd, 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).
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 a 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 in various scientific fields, e.g., Higgs-Landau theory, equivariant bifurcation theory and replica symmetry-breaking (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 low-dimensional spaces (see Section 4). A similar phenomenon of hidden low-dimensional structure has been observed in various learning problems in DL with real datasets [39, 31], and is believed by some to be an important factor of learnability in nonconvex settings. In the context of this work, the hidden low-dimensionality of spurious minima turns out to be a key ingredient to our analytic study, as we now present.

heading: 2 Power series representation of families of spurious minima
text: 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, e.g., [45, 44]) 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 a set of carefully-derived ODEs [18, 8, 52, 53, 51]. Following the empirical success of DL in the past decade, this line of work has recently drawn a 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 in the thermodynamic limit—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, our technique directly addresses the associated highly nonconvex optimization landscape in the natural regime where the number of inputs and neurons 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 3 and Figure 2), along with their respective objective value. For brevity, expressions are given to O(d−3/2)-order. In the appendix, we list additional O(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 a given family. The number of new distinct minima generated using such transformations (i.e., the minima multiplicity) depends on the very structure of the family of minima under consideration, and is stated in Theorem 1. Lastly, for any λ > 0 and i ∈ [d], the value of the ReLU network (1) remains fixed under (wi, αi) 7→ (λwi, αi/λ). This degree-of-freedom is expressed by using the slack variables λi > 0, i ∈ [d] below. Theorem 1. Optimization problem (2) with k = d, V = Id and β = 1d possesses the following families of minima for d ≥ 9:
1. Two families of ∆Sd-minima of multiplicity d! with W (d) = Diag(λ1, . . . , λd)Ad(a1, a2) and α(d) = (λ−11 , . . . , λ −1 d ), where λi > 0,
Ad(a1, a2) :=   a1 a2 . . . a2 a2 a1 a2 . . . a2
... ...
a2 . . . a2 a1
  ∈M(d, d),
Diag(·) maps a given vector to the diagonal entries of a diagonal matrix, and (a) a1 = 1 and a2 = 0 (a global minimizer), in which case
L(W (d), α(d)) = 0.
(b) a1 = −1 + 2d +O ( d −3 2 ) , a2 = 2 d +O ( d −3 2 ) , in which case
L(W (d), α(d)) = − 1 π + 1 2 − 4 3π √ d
+ − 12 − 2π2 + 3π
d +O
( d −3 2 ) . (4)
2. Two families of ∆(Sd−1 × S1)-minima of multiplicity d · d! with
W (d) = Diag(λ1, . . . , λd) ( Ad−1(a1, a2) a3Id−1,1 a4I1,d−1 a5 ) ,
and α(d) = (λ−11 , . . . , λ −1 d ), where λi > 0 and
(a) a1 = 1 + O ( d −3 2 ) , a2 = O ( d −3 2 ) , a3 = 2 d + O ( d −3 2 ) , a4 = 4 πd + O ( d −3 2 ) and
a5 = −1 + 8 π2 +2+ 8π d +O
( d −3 2 ) , in which case
L(W (d), α(d)) = 1 2 − 2π2 d +O ( d −3 2 ) . (5)
(b) a1 = −1 + 2d +O ( d −3 2 ) , a2 = 2 d +O ( d −3 2 ) , a3 = O ( d −3 2 ) , a4 = 2− 4π d +O ( d −3 2 ) and
a5 = 1 + 8(−1+π) π2d +O
( d −3 2 ) , in which case
L(W (d), α(d)) = − 1 π + 1 2 − 4 3π √ d
+ −1− 4π2 + 5π
d +O
( d −3 2 ) . (6)
3. Two families of ∆(Sd−2 × S2)-minima of multiplicity d! ( d 2 ) with
W (d) = Diag(λ1, . . . , λd) ( Ad−2(a1, a2) a3Id−2,2 a4I2,d−2 A2(a5, a6) ) ,
and α(d) = (λ−11 , . . . , λ −1 d ), where λi > 0 and
(a) a1 = 1 +O ( d −3 2 ) , a2 = 0 +O ( d −3 2 ) , a3 = 2 d +O ( d −3 2 ) , a4 = 4 πd +O ( d −3 2 ) , a5 =
−1 + 8 π2 +2+ 8π d +O
( d −3 2 ) and a6 = 2(−12π+16+π3+4π2) π2d(2+π) +O ( d −3 2 ) , in which case
L(W (d), α(d)) = −4 + π 2
π2d +O
( d −3 2 ) . (7)
(b) a1 = −1 + 2d + O ( d −3 2 ) , a2 = 2 d + O ( d −3 2 ) , a3 = 0 + O ( d −3 2 ) , a4 = 2− 4π d +
O ( d −3 2 ) , a5 = 1 + 8(−1+π) π2d +O ( d −3 2 ) and a6 = 4(−π2−8+6π) π2d(2+π) +O ( d −3 2 ) , in which case
L(W (d), α(d)) = − 1 π + 1 2 − 4 3π √ d
+ − 32 − 6π2 + 7π
d +O
( d −3 2 ) . (8)
4. One family of ∆(Sd−3 × S3)-minima of multiplicity d! ( d 3 ) with
W (d) = Diag(λ1, . . . , λd) ( Ad−3(a1, a2) a3Id−3,3 a4I3,d−3 A2(a5, a6) ) ,
and α(d) = (λ−11 , . . . , λ −1 d ), where λi > 0 and a1 = 1 + O
( d −3 2 ) , a2 = O ( d −3 2 ) , a3 = 2 d +
O ( d −3 2 ) , a4 = 4 πd+O ( d −3 2 ) , a5 = −1+ 8 π2 +2+ 8π d +O ( d −3 2 ) and a6 = 2(−12π+16+π3+4π2) π2d(2+π) + O ( d −3 2 ) , in which case
L(W (d), α(d)) = 3 2 − 6π2 d +O ( d −3 2 ) . (9)
The idea of the proof of Theorem 1 is given in Section 4.1, and the multiplicity computation, a 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 1 also represent spurious minima for the under-parameterized d > k-case. This is 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.1] to the spectral analysis given in Theorem 2 below (for the case where d = k). By contrast, studying the over-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/d), in other cases the objective value converges to the positive constant 1 2 − 1π . In particular, except for the global minima case 1a, all minima described above are spurious. The difference between the two types of behavior seems to lie in the limiting values of the entries of W (d); in the former, the diagonal mainly consists of ones, whereas in 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 to zero at different rates (see cases 2a, 3a, 4 above) and depends on the probability to converge to a given type of minima. (A possible proxy to the latter is the minima multiplicity stated in Theorem 1.)

heading: 3 Analytic study of the Hessian spectrum
text: Once a power series representation has been obtained, it is possible to analytically characterize various important properties of families of minima. Here, we use this representation to compute yet another fractional power series—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/2) d 1 4 − 12π +O(d−1/2) (d−1)(d−2) 2 1 2 − 1π +O(d−1/2) d− 1 1 4 +O(d
−1/2) d− 1 1 4 + 1 2π +O(d
−1/2) d(d−3)2 d 4 + 1 2 +O(d
−1/2) d− 1 d 4 + −4+π+π2 2π(−4+π) +O(d −1/2) 1
d π + −10π+8+π2 2π(−4+π) +O(d −1/2) 1.
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 decomposition (a set of ‘simple’ subspaces compatible with the action of row- and column-permutations formally introduced in Section D) must therefore cover the space of d× 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 α(d) 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 to high accuracy reveals that for small values of d the families of minima presented in Theorem 1 are in fact saddles. Regarding d as a real number, we pinpoint the exact fractional dimension at which a given family of critical points turns from saddles into spurious minima (see also Figure 1). One is now led into the dual question: is there a 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 in the over-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 to 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 1 differ significantly, their Hessian spectra coincide to O(d−1/2)-order. Another noticeable implication of Theorem 2 is that the Hessian spectrum tends to be extremely skewed. Both phenomena, as well as their consequences for optimization-related 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 a series of works [38, 55, 56] which studied how the spectrum evolves along the training process. It 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 Lanczos method (e.g., [25, 48]). These methods have provided various numerical evidences which indicate that a 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, our method gives an analytic description of the spectral density for
any number of neurons (granted d ≥ 9), and at critical points rather than randomly drawn weight matrices.
The flat minima conjecture and implicit bias. It 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 to achieve good generalization, cf. [58]. However, the analysis presented in Theorem 2 shows that the spectra of global minima and spurious minima agree to O(d−1/2)-order. Consequently, in our 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.

heading: 4 A symmetry-based analytic framework
text: In the sequel, we present the main ingredients of the symmetry-based technique developed in 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 k = d and the weights of the second layer are set to one. We let the resulting nonconvex function be denoted by f(W ) := L(W,1).

heading: 4.1 Power series representation of minima
text: The first step in deriving a power series representation is to restrict the nonconvex function under consideration to fixed point subspaces (see [20] for a more complete account); spaces that consists of weight matrices which remain fixed under row- and column-permutations in a certain subgroup of Sd × Sd. For concreteness, consider the space of all matrices which are invariant to permutations in ∆Sd, i.e.,
Wd := {W ∈M(d, d) |W = PπWP>π for all (π, π) ∈ ∆Sd}. (10)
It is easy to verify that Wd is in fact a 2-dimensional subspace of the form Wd = {(a1, a2) | a1Id + a2(1d1>d − I)}, and that if W ∈ Wd, then also ∇f(W ) ∈ Wd (see [3, Proposition 3]). Thus, one may regard f as a function from R2 to R2. Next, we make the dependence of f on d explicit by defining F : R3 → R2 : (a1, a2, d) 7→ ∇f(a1Id + a2(1d1>d − Id)). Note that although d was initially taken to be a natural number, in the following explicit expressions of F (a1, a2, d), we regard d as a real variable   a1d 2 − a1d sin ( β (1) (1) ) 2πν(1) + a1(d2−d) sin ( α (2) (1) ) 2π − a1(d2−d) sin ( β (2) (1) ) 2πν(1) − a2α (2) (1)(d 2−d) 2π + a2(d2−d) 2 + β (1) (1) d
2π − d2 −a1α (2) (1)(d 2−d)
2π + a1(d2−d) 2 − a2α
(2) (1)(d 3−3d2+2d) 2π +
a2(d3−2d2+d) sin ( α (2)
(1)
)
2π + a2(d3−2d2+d) 2 − a2(d2−d) sin
( β (1)
(1)
)
2πν(1) − a2(d
3−2d2+d) sin ( β (2)
(1)
)
2πν(1) +
β (2) (1)(d 2−d)
2π − d 2 2 + d 2
 
where, here and below, α(j)(i) (resp. β (j) (i) ) 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 (a1(d), a2(d)). This gives a formal meaning for examining a given family of minima at a 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 a1(d) and a2(d). This issue is addressed by using a real analytic version of the implicit function theorem, and then computing the coefficients of the power series of a1(d) and a2(d) to a desired order. Secondly, the implicit function theorem requires initial values for a1 and a2 which solve F (a1, a2, d) = 0. To handle this issue, we form power series in 1/d and, loosely speaking, develop them at d =∞. The advantage of this nonstandard manipulation is that the limiting entries of W (d) have a very simple form, which are then used as the initial values required for invoking the implicit function theorem. In fact, due to the dependence of ∇f on the angels between rows of W and V , the power series of a1(d) and a2(d) are expressed in terms of 1/ √ d. Theorem 1 is established by following the recipe described here for various families of critical points of different isotropy. The gradient expressions involved in the process are lengthy and are therefore relegated to Section E.

heading: 4.2 Computing the Hessian spectrum
text: Our next goal is to derive an analytic characterization of the Hessian spectrum. The invariance properties of L imply that although the dimension of the Hessian, k(d + 1) × k(d + 1), depends on k 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 is therefore deferred to Section D.2. Here, we shall focus on one particularly simple case.
The isotypic decomposition associated with ∆Sd, the isotropy of Id, implies that for any d,
Yd := vec     0 d− 3 3− d · · · 0 0 0 d− 3 0 0 · · · −1 −1 −1 3− d 0 0 · · · 1 1 1
0 −1 1 · · · 0 0 0 · · · · · · · · · · · · · · · · · · 0 −1 1 · · · 0 0 0 0 −1 1 · · · 0 0 0
    ,
is an eigenvector of∇2f(Id), where vec denotes the linear transformation which stacks the rows of a given matrix on top of one another as a column vector. Thus, the eigenvalue corresponding to Yd equals (∇2f(Id)Yd)2/(d− 3), which takes the following explicit form
a21 2πν2
(1) ν (2) (1)
+ a21 sin
( α (2)
(1)
)
2πν2 (1)
( ν (2)
(1)
)2 − a1a2 πν2
(1) ν (2) (1)
− a1a2 sin ( α (2) (1) )
πν2 (1)
( ν (2)
(1)
)2 + a22
2πν2 (1) ν (2) (1)
+ a22 sin
( α (2)
(1)
)
2πν2 (1)
( ν (2)
(1)
)2 + α
(2) (1) 2π + (d−1) sin
( α (2)
(1)
)
2π − (d−1) sin
( β (2)
(1)
)
2πν(1) − sin
( β (1)
(1)
)
2πν(1) − sin
( β (2)
(1)
)
2π ( µ (2)
(1)
)2 ν(1) ,
where ν(i) denotes the norm of the ith row of W , and ν (j) (i) (resp. µ (j) (i) ) denotes sin arccos(α (j) (i) )
(resp. sin arccos(β(j)(i) )). To complete the derivation of the eigenvalue Yd for families of isotropy ∆Sd, e.g., cases 1(a) and 1(b) in Theorem 1, one plugs-in the power series representation of a1(d) and a2(d) into the expression above, and forms a new power series to get an estimate for Yd. The same procedure is used for all families of minima presented in Theorem 1, and is described in detail in Section 4.2.

heading: 5 Conclusion
text: When present, the principle of symmetry breaking forms a powerful tool of reducing the complexity of nonconvex problems in a nonlinear way. This yields unprecedented analytic information for ReLU networks with a finite number of inputs and neurons (rather than limiting models of 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 d grows (see [54, Table 1]). Why is it then that SGD is generally able to 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.

heading: Acknowledgements
text: Part of this work was completed while YA was a postdoctoral researcher at NYU. We thank Joan Bruna, Ohad Shamir, Shimon Shpiz and Daniel Soudry for valuable discussions.

Review summaries:
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.

The paper theoretically study a one hidden layer neural network with ReLU activation trained using Gaussian data, and analytically derive the values of the different classes of local minima of this objective, and the spectrum of the Hessian at these local minima. The results show that as the degree of over-parameterization is increased, the local minima transform into saddle points in the loss landscape, and further find the exact fractional dimension at which this transition occurs.   Note: I am not familiar with the mathematical tools used in this paper. So my comments pertain to the utility of the findings and claims made in the paper.

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.