Weight-space symmetry in neural network loss landscapes revisited
Authors: Berfin Simsek
Johanni Brea
Bernd Illing
Wulfram Gerstner
Venue:  (2020)
Keywords: Weight-space symmetry
neural network landscapes

Abstract: Neural network training depends on the structure of the underlying loss landscape, i.e. local minima, saddle points, flat plateaus, and loss barriers. In relation to the structure of the landscape, we study the permutation symmetry of neurons in each layer of a deep neural network, which gives rise not only to multiple equivalent global minima of the loss function but also to critical points in between partner minima. In a network of $d-1$ hidden layers with $n_k$ neurons in layers $k = 1, \ldots, d$, we construct continuous paths between equivalent global minima that lead through a `permutation point' where the input and output weight vectors of two neurons in the same hidden layer $k$ collide and interchange. We show that such permutation points are critical points which lie inside high-dimensional subspaces of equal loss, contributing to the global flatness of the landscape. We also find that a permutation point for the exchange of neurons $i$ and $j$ transits into a flat high-dimensional plateau that enables all $n_k!$ permutations of neurons in a given layer $k$ at the same loss value. Moreover, we introduce higher-order permutation points by exploiting the hierarchical structure in the loss landscapes of neural networks, and find that the number of $K$-th order permutation points is much larger than the (already huge) number of equivalent global minima -- at least by a polynomial factor of order $K$. In two tasks, we demonstrate numerically with our path finding method that continuous paths between partner minima exist: first, in a toy network with a single hidden layer on a function approximation task and, second, in a multilayer network on the MNIST task. Our geometric approach yields a lower bound on the number of critical points generated by weight-space symmetries and provides a simple intuitive link between previous theoretical results and numerical observations.

Under review as a conference paper at ICLR 2020
WEIGHT-SPACE SYMMETRY IN NEURAL NETWORK LOSS LANDSCAPES REVISITED
Anonymous authors Paper under double-bling review
ABSTRACT
Neural network training depends the structure of the underlying loss landscape, i.e. local minima, saddle points, flat plateaus, and loss barriers. In relation to the structure of the landscape, layer of a deep neural network, which gives rise not only to multiple equivalent global minima of the loss function but also to critical points in between partner minima. In network of d hidden layers with nt neurons in layers k: = 1....,d d, we construct continuous paths between equivalent global minima that lead through a 'permutation point' where the input and output weight vectors of two neurons in the same hidden layer it collide and interchange. We show that such permutation points are critical points which lie inside dimenssinn subspaces of equal loss, contributing to the global flatness the landscape. We also find that a permutation point for the exchange of neurons i and transits into flat high-dimensional plateau that enables all n2! permutations of neurons a given layer at the same loss value. Moreover, the hicrarchical structure in the loss landscapes of neural networks, and find that the number of K-th order permutation points much larger than the (already huge) number of equivalent global minima at least by a polynomial factor of order K. In two tasks, demonstrate numerically with our path finding method that continuous paths between partner minima exist: first, in toy network with a single hidden layer on a function approximation task and, second, on the MNIST task. Our geometric approach yields a lower bound on the number of critical points generated by weight-space symmetries and provides a simple intuitive link between previous theoretical results and numerical observations.
study the permutation symmetry of neurons in each
introduce higher-order permutation points by exploiting
multilayer network
INTRODUCTION
The structure of the loss landscape plays important role in the optimization of neural network parameters. A large number numerical (Dauphin et al., 2014; Goodfellow et al., 2014; Li et al., 2018; Sagun al., 2014; 2016; Ballard al., 2017; Garipov al., 2018; Draxler et al., 2018; Sagun et al., 2017; Baity-Jesi et al., 2018) and theoretical (Choromanska et al., 2015; Rasmussen, 2003; Freeman and Bruna, 2016; Soudry and Carmon, 2016; Nguyen and Hein, 2017) studies have explored the properties of the loss landscape. In particular, in a multilayer network of d - 1 hidden layers with n neurons each, there are (n!)d=1 equivalent configurations corresponding to the permutation of neuron indices in each layer of the network (Goodfellow et al., 2016; Bishop, 1995). The permutation symmetries give rise to a loss landscape where any given global minimum in the weight space must have (n!)d-I completely equivalent partner minima. This property of neural network landscapes called weight-space symmetry.
Several (Saad and Solla, 1995; Amari et al., 2006; Wei et al., 2008) works explored the implications of weight-space symmetry for training dynamics in two-layer networks and found that training dynamics slow down near the singular regions caused by weight-space symmetry. Dauphin al. (2014); Orhan and Pitkow (2017) argue that optimization paths may get close to the singular regions induced by weight-space symmetry and this, in turn, slows down training for deep neural networks. Exploiting weight-space symmetries, we give insights into and partial explanations of three observations on neural network landscapes.

---

Under review as a conference paper at ICLR 2020
Observation 1. Training dynamics are slow near singular regions caused by weight-space symmetry and stochastic gradient descent might travel near these regions throughout training (Saad and Solla, 1995; Wei et al., 2008; Amari al., 2006; Dauphin et al., 2014; Orhan and Pitkow, 2017).
Observation 2. training. thus the landscape is flat in many directions (Sagun al., 2017; Papyan, 2018; Ghorbani et al., 2019).
The Hessian of the loss function has numerous almost-zero cigenvalues throughout
Related observation 1 and 2, we prove the existence of numerous connected high-ddmnnnsional plateaus extending across the landscape due to weight-space s symmelries.
Observation 3. The number of saddles can grow exponentially in neural network landscapes (Auer et al., 1996; Dauphin et al., 2014; Choromanska et al., 2015).
Related observation global minima due to weight-space symmetries in neural networks, without any further assumplions.
prove that there are least polynomially many more saddles than the
In addition, we propose novel low-loss path finding algorithm to find barriers between partner minima. We start from the known permutation symmetries and consider continuous low-loss paths that connect two equivalent global minima by merging the weight vectors of two neurons specific way. At a so-called permutation point, where the distance between the input and output weight vectors of the two neurons vanishes, the indices of the two neurons can be interchanged at no extra cost. After the change, the system returns on the 'mirrored' path back to the original configuration eexeept for the permutation of one pair of indices.
Surprisingly, we find that we can permute all neuron indices in the same layer at the same cost as the loss a permutation point reached by moving along the path that merges a single pair of neurons. These constant-loss permutations are possible because each permutation point lies in high-dimensional plateau of critical points. Our theory can be extended to higher-order saddles and provides explicit lower bounds for the number of first- and higher-order permutation points. Numerically, we confirm the existence of first-order permutation saddles.
In particular, the specific contributions of our work are:
A simple low-loss path-finding algorithm linking partner global minima via permutation point, implemented by minimization under single scalar constraint (distance of weight vectors).
The theoretical characterization of permutation points, for cxample that these critical points and several permutation points are connected via paths at equal loss.
A lower bound for the number of first- and higher-order permutation points and their corresponding plateaus.
Numerical demonstrations of the path finding method in multilayer neural networks trained on MNIST.
1.1 RELATED WORK
Structure of the landscape. For linear networks, it was shown that all the critical points - except for the global minimum are saddles in the case of two-layer (Baldi and Hornik, 1989) multilayer networks (Freeman and Bruna, 2016; Kawaguchi, 2016; Lu and Kawaguchi. 2017). Interestingly, deep linear networks are reported to exhibit sharp transitions the edges of extended plateaus (Saxe et al., 2013), similar to the plateaus observed in deep nonlinear networks (Goodfellow et al., 201 4). For nonlinear multilayer networks, Choromanska et al. (2015) argue that all local minima lie below certain loss value by drawing connections to the spherical spin-glass model. Improving upon this result, Soudry and Carmon (2016); Nguyen and Hein (2017) prove that almost all local minima are global minima for multilayer networks under mild over-parann peeeraaamtttiztioonn assumptions.
Bottom of the landscape. Another line of research studies the bottom of the landscape containing global minima and low-loss barriers between them. Freeman and Bruna (2016) prove the existence of low-loss paths connecting global minima for wide two-layer networks by upper- bounding the loss along the path with a parameter that depends on the number of parameters and data smoothness. Draxler et al. (2018) use Nudged Elastic Band method introduced in Jónsson et al. (1998) to connect independent minima and numerically find that the barrier vanishes consistently for increasing
2

---

Under review as a conference paper at ICLR 2020
width and depth in DenseNet, ConvNet and ResNet architectures trained on CIFAR datasets. In simultaneous work, Garipov et al. (2018) confirm that there is no significant barrier by connecting independent minima with polygonal chains.
Training dynamics in the landscape. For general loss functions, Lee et al. (2016) show that gradient descent with sufficiently small step-size converges to local minima if all the saddles have least one negative eigenvalue. For overparametrized neural networks, gradient descent converges to global minima without moving far from initialization (Jacot et al., 2018; Du al., 2018a;b), thus suggesting convex-like behavior around random initialization. For the finite size networks, how training dynamics converge to a minima and in particular how fast they converge remain an open question. For soft-committee machines, it turns out that the initial learning dynamics are slowed down by correlation of hidden neurons (Saad and Solla, 1995; Engel and Van den Broeck, 2001; Inoue et al., 2003). Amari et al. (2006); Wei et al. (2008) show that training dynamics slow down near singular regions due to weight-space symmetry. Dauphin et al. (2014) empirically argue that the large number of saddle points in the landscape makes training slow. Orhan and Pitkow (2017) numerically find that stochastic gradient descent may slow down near plateaus due to weight-space symmetry for deep (30 layers) feedforward networks trained CIFAR100.
In this paper we show that there is an impressively large number of permutation points. Each permutation point is a critical point (either local minimum saddle) with large number of flat directions, potentially linked to the empirically observed plateaus. In contrast to an earlier study by Fukumizu and Amari (2000) with a scalar output for two-layered networks where line of critical points around the permutation point was reported, we study deep network with d' - 1 hidden layers and find multi-diiensional equal-loss plateaus. Moreover, we give a novel lower bound on the number of permutation points and construct sample paths between global minima using an algorithm that is different from previously used methods (Garipov et al., 2018; Draxler et al., 2018), since exploits the symmetries at the permutation point.
1.2 PRELIMINARIES
We study multilayer neural networks f(x; 0) with input x E ["", d layers of ni,... nn neurons per layer, parameters 0 = (w(k) E RR and (k) E IR : k E {l....,d] d}} e θ and n.-dimensional output
f(x: 0) = w(1) (..(0o..((()))) (w (w(' +b(2)) 6
where g is a nonlinear activation function that operates component-wise on any vector.
Definition 1 & 2. (Parameter vector) We define the parameter vector ((x) of neuron m in layer as the incoming weights a neuron m in layer k concatenated with its bias term: (K)
a(k) m = [w-(]] m. m.ng 1: [())] (Output weight vector) We define the output weight vec-
tor of neuron m in layer k as its outgoing weights from neuron m in layer k to the next layer:
W 1.m ..... (A-1)
(k-1)
Since can permute the neurons within each layer without changing the network function f(x; 0). any point A induces a 'permutation set'. Definition 3. (Permutation set)
P(0) 10' θ (kk
(6)))),(tt-)))) = w (k) ig and 6 (k)
6,th (k) K (L,,,...
(2)
())
of points O' with f(x; 0) f(æ; 0'), where (A) are permutations of the neuron indices {1, (1..... 3
in (hidden) layer A where (0)) and (d)) are fixed trivial permutations, since we want to permute neither the indices of the input nor that of the output. We will use the notation 0' (A) (0) to
indicate a point e' that differs from only by swapping neurons and in layer k.
Note that the cardinality of permutation set is maximal with [P(O) = 11 ny! only if all parameter vectors 0(hh) + (k) are distinct for every 1 + m and layer & E (1...., - 1). In the following, will assume that, at global minima, all parameter vectors distinct at every layer k.
Definition 4. (Permutation point) Consider a minimum of a multilayer network with (N....., ny 1...., R22) neurons per layer. We map this minimum to configuration in the landscape of
3

---

Under review as a conference paper at ICLR 2020
multilayer network with (Mi,.... ....... Rd)) neurons per layer by duplicating neuron fI...., ni - 1} in layer as follows: (i) substitute the parameter vector of the new neuron with copy of the parameter vector (hhh of neuron m, (ii) replace the output weight vector of the new neuron and the duplicated neuron m with the initial output weight of neuron m rescaled by 1 and 2 (iii) keep all the other parameters the same. This new configuration where the parameter vectors and the output weight vectors of the new neuron and the duplicated neuron m are the same will called
permutation point, denoted by lcom: i.e. ( Olesm (0) (0(=m))
For training data = {(z", ,y") f2 fl..... T}} with targets y" E V. we define a loss function L(O; D) = + وnz (vy, ff(==;(())") 0)), where y x m + R some single-sample loss function. To simplify notation we will usually omit the explicit mentioning of the data in the loss function, i.e. L(0) L(0: D).
A
B
8000 g00)
((k)
9
X
(d)
d < (10
(d)
d >
d(k)
8 (d)
((k)
d(k)
(())
(k) 1.
7m
/
(4))
((k
Figure 1: A. Configuration of two parameter vectors 0.e and ((k) (black) minimum and potential path (green) towards permutation point 0% 0/e) (x). The path is parametrized by the distance d. Along the path the distance (blue dashed lines) decreases continuously starting at d_ (0). Note that the path can lead a permutation point far away from the initial configuration, outside the linear subspace spanned by the parameter vectors (*)) and (k)) m the distance along the path increases.
B. We exclude hypothetical paths where
2
MAIN RESULTS
In this section, we will first present novel method find low-loss path between partner minima. Our method ensures that this path passes through 'permutation point'. We study the properties of permutation points. Furthermore, will introduce higher-order permutation points and provide lower-bound on their number.
2.1 A NOVEL METHOD TO CONSTRUCT LOW-LOSS PATHS BETWEEN PARTNER MINIMA
One natural question regarding the geometry of the bottom of the landscape is the following: possible to find continous low-loss path that connects two minima? In this work, we are interested in finding the barriers between partner global minima. In particular, we want to find a continuous low-loss path [0, 1] + θ connecting two partner minima by first merging two parameter vectors and output weight vectors ('permutation point') ) and then completing the path using symmetry. We will first introduce some concepts to introduce this low-loss path between partner minima formally.
Definition 5. (Distance function) d(Aa) θ - R+ a distance function that takes configuration and returns the squared Euclidean distance between the parameter vectors of neuron and m at layer k:
= [1/0(k)
(k) 12
(3)
1.m
4

---

Under review as a conference paper at ICLR 2020
Our idea is to find low-barrier path Y arg y: i| max [] (tr(t) under the following constraints for the initial (t = 0) and quarter-way (t configurations: 7x(0) 0, where the parameter configuration the minimum, and ( (7+ (7)) = Furthermore, the distance between parameter vectors ( and (1th) m layer & is decreasing, i.c. df (T) 1.m (t)())) for all
>> l' E [0, 1)" (see Fig. and pseudocode in Appendix).
The quarter-way configuration guarantees that the parameter vectors are identical m/ puts no constraints on the output weights of neurons m and in layer k. We can continously move from the quarter-way configuration (t = }) to a configuration at t = 1 where the outputs weights of the related neurons are equal, without making any changes to the network output or the loss as follows: we will increase all output weights W of neuron and decrease the corresponding output weights W of neuron y by the same amount continuously so to keep their sum fixed n.m
O but
m
until W W wk+1 for every neuron n E {L...... 1 J at layer & + (see Appendix Fig. 4). n,m
D2
Lemma 1. The configuration at & is one of the permutation points.
Once we have reached / 2. we interchange the neuron indices of the 'merged' neurons and continue on 'mirror' path that results from walking the first half of the path backwards with interchanged
neuron indices, until we arrive at the partner minimum at t = i.e. r(2 + r) =0 Iesm (7( 7)) for [0, --1
(k)
To find such paths algorithmically, we reparametrize @ (t) = (k) (t) + d(t)e(t) where d(t) is a positive scalar and e(I) unit-length vector. start with d(0) = d (0) and initialize e in direction of the difference ((k) 0ft (((h) the global minimum i.e., the initial parameter configuration. Next, decrease d infinitesimally and perform gradient descent for fixed d on the loss L until convergence. Note that all parameters can change, including ((()) and e during gradient descent. This procedure is repeated until d value without changing the network function (see Appendix Fig. 4).
/ = 1. Finally we shift the respective output weights to the same
Since the path connects two partner minima, there must be at least one saddle point on the path rtt,, E [0, 1]. potentially but not necessarily, the permutation point. Moreover, there is no guarantee that the highest saddle should be located at the permutation point (see Appendix Fig, 5).
2.2 CHARACTERIZATION OF PERMUTATION POINTS
In earlier work, Fukumizu and Amari (2000) studied a specific set of critical points induced by the hierarchical structure in the neural network landscapes in two-layer neural networks. Let L (f) be the loss function ('landscape') and single output. They showed that any critical point in the landscape of (!I-1) induces a line of critical points in the landscape of I, (H). We study permutation points in the general setup for the neural networks with multiple outputs and multiple layers.
two-layer neural network with H neurons the hidden layer
Theorem 1. (Fukumizu and Amari, 2000) By duplicating one parameter vector of any critical point in 1I1 and keeping the sum of the two output weights corresponding to the duplicated parameter vectors fixed at the value of the original output weight, one obtains line of critical points in I (H),
Proposition 1. (i) Permutation points 0 (eem are critical points of the original loss function.
(ii) Any permutation point lies inside dime--imnnio equal-loss subspace of critical points.
(iii) All other permutations of neuron indices in layer k can be performed by continuous equal-loss transformations starting from permutation points (k) of neurons and m, i.c. there a continuous
Note that the parametrization t including the exact t values for the mentioned configurations are arbitrary and only used for conceptualizing the path. The relevant parametrization of the path will be the distance d. easily verified by setting derivatives all parameters to zero (2f (critical point) and observing that the derivatives of the corresponding configuration in T, (() will be zero under the mapping stated in the theorem.
*Theorem
5

---

Under review as a conference paper at ICLR 2020
2.
B
2 5
3
3&4
31
-10
.10
-10
8
3
2
1
0
10 10-2
10 10 4 10
100
10-4 44
10
100
d
d
Figure 2: Paths to the same different permutation points. Top row. Configuration of the weight vectors (!!))
s.: () of the first layer at the global minimum (blue) and at a permutation point (red) reached after merging the parameter vectors of neurons. Note that the global minimum (i.e., the starting configuration) is the same for (A), (B) and (C) but the loss at the permutation point can be the same - (A) and (B) - or different (A) and (C) depending on the pair of neurons chosen for merging. Numbers indicate neurons. Bottom row. Quadratic loss L as a function of the distance between the neurons to be merged. The distance was decreased in 200 logarithmically spaced steps from d = d (0") was performed until convergence. Training data was generated by sampling 103 two-dimensional input points x from a standard normal distribution and computing labels y = f(x"; (0)) using a teacher network (shown in blue, equivalent the configuration the global minima). The teacher had a single layer of five hidden neurons with rectified-linear activation function g and one linear output layer.
) to 1/10* of the initial value. For each d, full batch gradient descent on the loss
path p [0, 1] - such that p(0) = ((() and p(1) o and L(p(t)) = L(p(0)) for all I E [0, 1] and all i E [1,...,,k]] ). (Proofs: see appendix).
Therefore, each of the m=(m--1) different permutation points of layer k corresponds to plateau of 1 dimensions. This plateau enables the exchange of indices in layer k. Note that there can be multiple plateaus different loss levels that correspond to different local minima of the smaller networks where one of the neurons is dropped at permutation point. For example in Fig. one exchange all indices in the hidden layer through the configuration in A and B through the configuration points embedded in different plateaus, could for example search for the one with the lowest cost and this lowest-cost permutation would then also connect all global minima caused by arbitrary permutations neurons in layer k.
that has another loss level. Note that, amongst all these permutation
Definition 6. (Higher-order permutation point) Consider a minimum of multilayer network with (n....., n4. K...., ... nag) neurons per layer. We can map this minimum to a configuration in the landscape of a multilayer network with (M..... .g..... na.) neurons per layer by replicating some neurons m, (1,..., ny K} in layer l: to fill out the parameters of new neurons as follows: (i) substitute the parameter vectors of the new neurons with one of the parameter vectors of the initial minimum, (ii) replace the output weight vectors of the new neurons and the output weight of the corresponding parameter vector my with the initial output weight of the replicated neuron m, normalized so that the mentioned output weight vectors sum up to the original output weight vectors, and (iii) keep all the other parameters the same. This new configuration where the parameter vectors and the output weight vectors of the new neurons and the replicated neuron m, for several, j in layer k are the same will be called K-th order permutation point.

---

Under review as a conference paper at ICLR 2020
This natural generalization the 1-st order permutation points to higher-orders enables generalizing Proposition 1(i) and (ii) to the K-th order permutation points.
Proposition 2. (i) A K- k-th order permutation point is critical point of the original landscape. (ii) Any K-th order permutation point at layer & lies K -dimensional subspace of equal loss parameter configurations. (Proofs: see appendix).
2.3 COUNTING HIGHER- ORDER PERMUTATION POINTS
configuration in the landscape of -H-) can be mapped to an equivalent configuration in T, with the procedure described in Definition 6. We can then count the number of permutation points that reduce to the same configuration in L (H) combinatorially (see Appendix Fig. 6 for the explanation of combinatorial counting). For counting, we consider the cardinality of the permutation set of a permutation point. Since some parameter vectors replicated, have to consider permutations of sometimes identical neurons. This enables finding a lower bound on the number of critical points that have higher loss values than the global minima in general.
Proposition 3. neural network with (nı,.... ne) neurons per layer, let T(K, ng)) denote the ratio of the number of K o"h-order permutations points at layer & to the number of global minima for k = 1, d - 1 and K 2 1.
(i) For K 2, and nh 2 2K, find T(K, nz) be:
T(K 1, mx) ("
T(K 2, n4) = - (me-2)
33 +
(n-22)
2
T(K = 3, 3,nz) = ( ("(T")
+ (-x--) 2
3
(ii) For general K S <x/22, we find the bound T(K, m4.)
("*=* 2σ. (Proof': see appendix)
Considering all the layers, we note that the number of permutation points order K is at least
(8 K) times more than the global minima for 2K S mming n4- 2x
K
Lemma 2. For finite K z and ng co, T(K, cgn k since şK ("*=*) ckn.
When one layer has large number of neurons (i.e. n oo) then the ratio T(K, my) grows with n
Every permutation point lies inside a high-dimensional subspace of equal loss (Proposition 2(i)), Appendix Fig. 7 for illustration). Importantly, every permutation point lies inside a distinct but connected subspace. Therefore the count for permutation points holds for the corresponding high-dimensional equal-loss subspaces of critical points.
Lemma 3. In a neural network with (MI,..., na) neurons per layer, there are (at least) Σ1=1 T(K, [[ ng. many Kn -dimensional equal-loss subspaces of critical points the loss of K-th order permutation point for 2K < min; Rk.-
We could start at an arbitrary configuration in consider the landscape of ( and the corre- sponding equal-loss high-dimensional subspaces in (,) where each configuration in the subspace computes the same function as the initial configuration. This procedure again would yield the same number of high-dimm -ineediimnnio equal-loss subspaces. Therefore due weight-space symmetry, neural network landscapes do not only exhibit numerous high- nigh-dimmessioal plateaus of critical points but also numerous high- -igheninnnio plateaus (of usually non-critical points) at various loss values.
EMPIRICAL RESULTS
Using similar procedure in the toy example (see Fig. 2), we constructed paths between global minima a fully connected three-layer network with vi = n2 = H and ni3 = 10 neurons (see Fig. 3). In order to study global minima we used student-teacher setting?: the teacher network was
Paths between local minima could be constructed by starting with a pre-trained network on MNIST and applying our path finding method with standard gradient descent training on MNIST. We expect to find similar results.
7

---

Under review as a conference paper at ICLR 2020
pre-trained on the MNIST data set using negative log- logllikelihood loss and its parameters 0 were kept fixed thereafter. We initialized the student with the parameters 0 of the teacher and decreased the distance d between the parameter vectors of two selected neurons and in layer k 2 in 100 logarithmically spaced steps from (,,)(")) to 1/10* of the original value. For every value of d, the student was trained on a regression task with a mean- error loss L between teacher and student output using full batch gradient descent until convergence. With y = f(x 0²) R being the output the last layer before the softmax operation, we chose L + En= 11y0 f(x" 0)1 (wv,") as the mean squared error loss between teacher and student, where (.) denotes the mean over patterns and dimensions and 1, ..... 7 enumerates the samples of the data set. Apart from a few cases, where the trajectory towards the permutation point passed through a saddle on the way, in most cases the loss increased monotonically until the permutation point. This indicates that the permutation point is a saddle, and not a minimum. As expected from theoretical results (Freeman and Bruna, 2016) and empirically observed by (Draxler et al., 2018), the barrier height (loss at saddle) decreased with the number H of hidden neurons per layer.
A
10-2
10
training accuracy
15
0.98
25
0.5
0.96
0
0.94
10
10 2
100
10 -4
10-2
10
100
Figure 3: A low-loss permutation path the loss landscape of a multi-layer network using a student-teacher setup trained MNIST. We merged the parameter vectors of two neurons with high cosine-similarity in the second hidden layer of a three-layer student network. The corresponding teacher network with H 10, 15, 20 25 was trained on MNIST. For each hidden layer size trained 6 teacher networks with different random seeds and display one curve per hidden layer size and seed. A. In most cases, the mean squared loss L between teacher and student output increases monotonically along our constructed paths from a global minimum until the permutation point. In these cases the latter corresponds to the loss barrier along the path. Note that the barrier height (loss at saddle) decreases with H. B. The MNIST classification accuracy on the training set decreases only marginally when moving to permutation point.
4 DISCUSSION
The surprising training performance of neural networks despite their highly non-convex nature has been drawing attention the structure of the loss landscape. In this paper, we explored how weight-space symmetry induces saddles and plateaus in the neural network loss landscape. We found that special critical points, so-called permutation points, are embedded in high- high-dimensional flat plateaus. We proved that all permutation points in given layer are connected with equal-loss paths, suggesting new perspectives on loss landscape topology. We provided novel lower bound for the number of first- and higher-order permutation points and proposed a low-loss path finding method to connect equivalent minima. The empirical validation of our path finding algorithm in multilayer network trained on MNIST showed that permutation points could indeed be reached in practice. Additionally, we observed that the loss at the permutation point (barrier) decreased with network size and thus confirmed Freeman and Bruna (2016)'s 's findings for loss barriers between global minima. High- High-dimensional flat regions around permutation points could be one of the causes of the empirically observed slow phases in training.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in Neural Information Processing Systems, pages 2933-2941, 2014.
J. Goodfellow, O. Vinyals, and M. Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint arXiv: 1 2014.
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems 31, pages 6389 6399. Curran Associates, Inc., 2018.
L. Sagun, V. U. Guney, G. B. Arous, and Y. LeCun. Explorations on high dimensional landscapes. arXiv preprint arXiv: 142..661,, 2014.
L. Sagun, L. Bottou, and Y. LeCun. Eigenvalues of the Hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476 2016.
A. Ballard, R. Das, S. Martiniani, D. Mehta, L. Sagun, J. Stevenson, and D. Wales. Energy landscapes for machine learning. Physical Chemistry Chemical Physics, 19(20):15555-2260) 2017.
T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. In Advances in Neural Information Processing Systems, pages 8789-8798, 2018.
Draxler, K. Veschgini, M. Salmhofer, and F. A. Hamprecht, Essentially no barriers in neural network energy landscape. arXiv preprint / 1803.000300855 2018.
L. Sagun, U. Evei, V. U. Guney, Y. Dauphin, and L. Bottou. Empirical analysis of the Hessian of over-parametrized neural networks. arXiv preprint 1rXiv:1706.0044
2017.
M. Baity-Jesi, L. Sagun, M. Geiger, S. Spigler, G. B. Arous, C. Cammarota, Y. LeCun, M. Wyart, and G. Biroli. Comparing dynamics: Deep neural networks versus glassy systems. arXiv preprint arXiv:1803.06965 2018.
A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and LeCun. The loss surfaces multilayer networks. In Artificial Intelligence and Statistics, pages 192 192-204, 2015.
C. Rasmussen. Gaussian processes machine learning. In Summer School on Machine Learning, pages 63-71. Springer, 2003.
C. D. Freeman and J. Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv:1611.005: 2016.
D. Soudry and Y. Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint 1rX1v1160..0866,, 2016.
Q. Nguyen and M. Hein. The loss surface of deep and wide neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volus Volume 70, pages 2603-2612 2.12. JMLR. org, 2017.
I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. 2016.
C. M. Bishop. Neural Networks for Pattern Recognition. Clarendon Press, 1995.
D. Saad and S. A. Solla. On-line learning soft committee machines. Physical Review E, 52(4): 4225, 1995.
S. Amari, H. Park, and T. Ozeki. Singularitics affect dynamics of learning in neuromanifolds. Neural computation, 1007 2006.

---

Under review as a conference paper at ICLR 2020
H. Wei, J. Zhang, F. Cousseau, T. Ozeki, and S.-i. Amari. Dynamics of learning near singularities in layered networks. Neural computation, 20(3):813 8133333,3 2008.
A. E. Orhan and X. Pitkow. Skip connections eliminate singularities. arXiv preprint 1xXx::1001.0975: 2017.
V. Papyan. The full spectrum of deep net Hessians at scale: Dynamics with sample size. arXiv preprint
2018.
B. Ghorbani. S. Krishman, and Y. Xiao. An investigation into neural net optimization via Hessian cigenvalue density. arXiv preprint arXiv:1901.10159, 2019.
P. Auer, M. Herbster, and M. K. Warmuth. Exponentially many local minima for single neurons. In Advances in neural information processing systems, pages 316-322, 1996.
Baldi and K. Homik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1))53-58, 1989.
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pages 586-594, 2016.
H. Lu and K. Kawaguchi. Depth creates no bad local minima. arXiv preprint arXiv: 1oXiv:/7022. 1702.08580, 2017.
A. M. Saxe, McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6122 2013.
H. Jónsson, G. Mills, and K. W. Jacobsen. Nudged elastic band method for finding minimum energy paths of transitions. Classical and Quantum Dynamics Condensed Phase Simulations, pages 385-404, 1998.
J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent converges to minimizers. arXiv preprini arXiv: 1602.0996 2016.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pages 8571 6571-855 15710, 2018
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes wer-parameterized neural networks. arXiv preprint arXiv.1810.02054. 2018a
S. S. Du, J. D. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1ate:1/111000000 1.03804, 2018b.
A. Engel and C. Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
M. Inoue, H. Park, and M. Okada, On-line learning theory soft committee machines with correlated hidden units steepest gradient descent and natural gradient descent. Journal of the Physical Society of Japan, 72(4):805-810, 2003.
K. Fukumizu and S. Amari. Local minima and plateaus in hierarchical structures of multilayer perceptrons, Neural Networks, 13(3):317-333 327,, 2000.
10

---

Under review as a conference paper at ICLR 2020
A
SUPPLEMENTARY FIGURES
B
L
W
W (R+1) mm
W (R-1)
with) W
Layer:
W Wo
(((++1) ((+++1)
k+1
W
Wilh
W (k+1) n.m
k
Wel)
(prik)
i
k-1
W (K) m.i
W (R))
Figure 4: A. The loss landscape (schematic) as a function of two parameters: the difference W-(R) w:(k) between the weights from neuron i to neurons m and layer and the weight (((++1) from neuron m to neuron n in the next layer (see for network graph). The red curve indicates the path from one of the global minima (red triangle) to half-way configuration where the difference
m.a
between the input weight vectors of neurons m and layer vanishes (Wr(k) ( red m.,
square). Along the axis (((h) m, w:(h) = O, we can change the output weight w=(k+1) at constant
loss (dashed horizontal line), as long as the sum w + ngl
w>(k++1) remains constant. The point
w=(++1) = w where the two output weights are identical (and assuming the same matching n.r
condition for the other output weights) defines the permutation point (k) (red *) where we can swap the indices of neurons m and in layer le at equal loss and continuously parameter space.
we then shift (dashed green line) all output weights of neuron m. in layer le to zero (W(++1)
n.m. = 0 for free change the weight (x(k) constant loss (green arrows) as
all n. green filled circle), perform further permutations of neurons in layer kt

---

Under review as a conference paper at ICLR 2020
A
B
Ct
S
do d
d
d
Figure 5: Loss L (vertical axis) on the permutation path as function of the distance d between the two parameter vectors to be permuted (schematic). A. In the teacher network the two parameter vectors have a distance dp. Along the path, the distance is reduced to zero. At the permutation point (+), the loss reaches a maximum which corresponds to saddle point of the total loss function. B. On the path towards the permutation point (+) an intermediate saddle point (S) may occur. C. The permutation point (+) could be minimum along the path.
12

---

Under review as a conference paper at ICLR 2020
(0.1.3)
(1.0.3
4.0
3.5
10.4,
0.4, 2.5)
125, 0.4, 2.5)
3.0
2,, 2.5, 2:5)
2.0
(3,0,1)
15
30,3.11
(2.5, D:4, 0.4)
1.0
2.54 0.4)
0.5
(3,1,0)
0.0
(1,3,0)
(2:5, 2.5, 0.41
0.5
1.0
1.5
0.0
0.5
2.0
1.0
1.5
2.0
3.0
W5
3.0
3.5
4.0
4.0
3.5
Figure 6: Visualizing how permutation points arise in between global minima for (hypothetical) network function with scalar inputs and one hidden layer with three neurons. Here we do not consider biases for simplicity. Blue dots: many equivalent global minima. A red *: One permutation point (of first order at layer k = 1) represented by its weights in the first layer, i.e. (2.5, 2.5, 0.4). All red *: One permutation set where the weight value 2.5 is duplicated. All green *: The other permutation set where the weight value 0.4 is duplicated. Note that overall, we have 6 permutation points that give rise to the same network function as the weight configuration with two hidden neurons with (2.5, 0.4). Indeed, T(K 1, n1 = 3) = (a-1) = confirms why the number permutation points corresponding to this particular weight configuration with two hidden neurons is equal to the number of global minima. Note that the weight values are assigned randomly for visualization purposes.
13

---

Under review as a conference paper at ICLR 2020
A
02.5, 25)
3.0
15
2,5
10.5. 0.5.
19.
0.5
3
10
0,5.0.
0.5
0.0
-10
GPPL
0.5
0.0
-10 0.5
860
1.0
3.0
Figure Zooming in permutations points of one the permutation sets (red Fig. 6). B. Visualizing how permutation points (at layer k = see A) lie inside equal-loss lines in the weight space of the layer k
2. Only two out of three lines are shown for simplicity. We observe that the number of such equal-loss lines (hyperplanes) is equal to the number of permutation points, i.e. each permutation point lies inside one distinct line.
14

---

Under review as a conference paper at ICLR 2020
B PATH FINDING ALGORITHM
Algorithm 1 Finding Low-Loss Paths through Permutation Points
Require: parameters 0, indices k, m, SCHEDULE of decreasing distances
1: dg f (8) (0)
2: Re-parametrize A 0 (10, e.) s.t. 0.0 = -.0) !!hh =0²²² + de/llel|
3: d +- do. e f 0(h) 0(h))
4: for d' SCHEEDLLE(g) do
5: d d'
6:
7(d") + (d") as found by gradient descent on L( {d])
7:
end for
8: return
C PROOFS
C.I HALF-WAY CONHIGURATIONS ARE PERMUTATION POINTS
Proof of Lemma 1. Since the parameter vectors and output vectors of the two neurons are identical at t t= 1. we can merge the two neurons into single one (by appropriately rescaling the corresponding output weights) so that the number of neurons fı in layer & is reduced by one. Since our path- auth-finding method minimizes the gradient, the configuration t 1 is local minimum of the smaller network, hence permutation point.
2
Alternatively, we will reformalize the auth-finding problem with Lagrange multipliers: minimize L(O) + Ad (0) for increasing values of X, starting with À = and increasing (potentially) until - cc. The goal here is to decrease the distance down to zero while keeping the loss minimal. For every A, will obtain minimizer 0. This sequence of 0 configurations will be an approximate discretization of the ideal path With the Lagrangian formulation, we can easily show that the half way configuration is critical point: it is minimizer of L(Ø) + Add (0) (0) 0. Note that the partial derivatives of dr,m with respect the parameter vectors of neuron and in layer are odft)
when d(bb) (0) for big enough
A. Therefore, VL(O) + AV (
0 2(0 9(k)
ad(t) 80
((()) and both are equal to zero at the half way o 1 0. All other partial derivatives with respect other parameter
(k) (()(
m
configuration since ||0((()
vectors are 0 since df
does not depend on them. Therefore d i.m (0) = 0. Consequently, VL(0) 0. We note that the Lagrangian formulation is an approximation the ideal path "
C.2 PROPERTIES OF (FIRST-ORDER) PERMUTATION POINTS
Proof of Proposition 1. (i) Let us assume we merged the neurons and m in layer and scaled the output weight vectors of these neurons with In that case, the output vector in layer it + 1 remains the same. The derivative with respect an output in the layer k + 1 will be the same, i.c. ØL for do5 E [M4+1] will not change under this mapping. The derivatives with respect to the output weights (say : for i E [mι] of layer is Σn 8L t+1 ZrT ow. These derivatives would be the same as the corresponding derivatives before the mapping performed. The derivatives with respect to the parameter vectors of layer is aL a
remains the same up scaling in the output weight value. Ba 00t
All the other derivatives remain the same (up to scalar constant) as the corresponding derivatives before the mapping is performed. Therefore, a critical point in the landscape of the neural network with (n....., 72 1,..., na) neurons per layer will map another critical point in the landscape of the neural network with (n....., ny..... Ra)) neurons per layer under the function preserving mapping described in the definition of permutation point. This proposition is straightforward
15

---

Under review as a conference paper at ICLR 2020
extension to the Theorem 1 in (Fukumizu and Amari, 2000) for multiple output and multiple-layer neural networks.
(ii) Once the parameter vectors of neurons and | in layer is are identical, they implement the same function. Any change of an output weight l preserves the network function, and criticality n.m
(see Proposition 1-(i) above), as long the output weight wrl++ is coadapted so to keep the sum W w n.
(k+1) constant. The sum-constraint W + w((+) c for each n in layer k + 1 defines an ri++1 1ie+--dimesional hyperplane of critical points. In particular, each point in the hyperplane, we have + directions of the Hessian with zero Higenvalues if the activation function g is wwice-differentiabl..
a.l
(iii) We make the following sequence of continuous transformations that are all possible at fixed loss. First, we decrease the output weights of neuron m zero while increasing those of by the same
amount, keeping the sum of weights w=(k+1) w((h-)) constant for each j in layer + Second, we a.
ju
change smoothly the input parameter vector neuron m to match those an arbitrary other neuron i in the same layer k. Third, increase the output weights of neuron while decreasing those of neuron until all output weights of neuron i are zero, keeping the sum of weights W( ( constant for each j in layer k + 1. Fourth, we reduce the input parameter vector of neuron i zero. Fifth, we increase the input parameter vector of neuron i to match that of neuron 1 at the permutation point. Finally, we equally share output weights between neurons and so that has the same weights as previously neuron at the permutation point.
j.m
j.a
Effectively, this procedure enables us to exchange an arbitrary neuron with neuron m, but the procedure can be repeated for further permutations. The permutations constructed in the proof of property (ii) start at permutation points where the parameter vectors of neurons and m merge. Therefore the loss associated with all the permutations constructed in the proof is T.(0)e te ). the one of this permutation point. However, we could also begin with two other weight vectors and j and
construct the path leading to another (Aa) that has, in general, a different loss.
jezy
C.3 PROPERTIES OF HIGHER-ORDER PERMUTATION POINTS
Proof of Proposition 2. (i) We take minimum in the landscape of neural network with (ni,--.. Fi neurons per layer. Using Proposition I-(i,, we map to a critical point in the landscape of neural network with (n....., ni K + 1,.... nad) neurons per layer where one parameter vector in layer A is duplicated and the corresponding output weights are rescaled with 4. Repeating the same mapping starting the latter critical point, we map to another critical point in the landscape of neural network with (n...... we end up a K-th order permutation point (up to changes in the output weights of the replicated neurons as long as the network function is preserved) and this is a critical point in the landscape of neural network with (MI,..., ...,,..,,. ,., neurons per layer by induction.
naa) K....,
..... K + ...... ..)) neurons per layer. Repeating this mapping for K times,
(ii) We will denote the parameter vectors of a neural network with (n1...., ni: K.... na)
neurons per layer with (0(()) (/ ...... ((4) and that of f(n
neurons with ..... [k)] J. Let's consider unordered partition of ng 81 + $2 +... + s with -0 {o((A)
8m 2 for m = 1....,l. Without loss of generality, let's assume that the first $1 parameter vectors of layer k are the same, then the next 82 and on. Equivalently, for all
1,...,4, we have
(((e) = ((k) for = 8m-1 1- + 8m....,mm111 + 8m where 8y =
m
The only free variables are the outgoing weights of the replicated neurons- except for the constraint that the summation of these weights is fixed. These constraints correspond to Ejmnttim W W
(k+1) for all neurons at layer 1+ Overall, there are (E'm=1 Sm Rm++1 = 7 free variables im
constrained by (n&+1 equations. One equation defines 74 1 dimensional hyperplane in the dimensional equal-loss hyperplane.
7 space. Intersecting In of these hyperplanes, we end up having a (n4 - l)n4+1 = Kn
16

---

Under review as a conference paper at ICLR 2020
C.4 COUNTING NIGHER-ORDER PERMUTATION POINTS
We simulate smaller neural network with the big network of (71...... ........ nl.)
neurons
the d layers. We assume that a minimum of the small neural network has ni - K distinct parameter vectors layer k and n, distinct parameter vectors at other layers j + k. A K-th order permutation point (at layer k) of the big network implements all the (mI....,, n K...., ma)) parameter vectors of the small network and only these. Since the big networks has ni neurons in layer k and the small network only ni K, the big network must reuse some of these parameter vectors of the smaller network several times. Therefore we count the number of permutations of indices calculate T(K, ng). We will start with K =
Proof of Proposition 3.
(1) The case K = 1:
At first-order permutation point in layer k we have / ni distinct parameter vectors {0(*) (0(h) ..... ())) for a total of ny neurons. Therefore two of the n& neurons must have the same parameter vector. More formally, there is only one way partition ng into n 1 positive in- tegers without respecting order and this unordered partition can be represented as ne = =+1+...++
(k) The duplicated parameter vector could be the first one, (0({A) ), or the second one, or the last one, (0(k)). Therefore there are ("x=1) choices. For each of these choices (say, double the third parameter vector), we have ni!! 2! permutations of indices of neurons in layer k. If we include the permutations that are possible all other layers, we have (" I[= ny! first-order permutation points (see Fig. 6). Since the cardinality of the permutation induced by global minimum is [P(0) = II I nyl. we arrive ratio T(K n4.) )
(2) The case K 2:
There are two ways to have 2 distinct vectors out of ng. corresponding to two unordered partitions of ny: (i) n 3 1 .... 1, and (ii) n& 2
(i) n4 = +1
For this case, we have n permutations given by permuting the neuron indices of layer k instead of the usual n4. permutations since we should eliminate the equivalent permutations corresponding to the permutations among the replicated parameter vectors with division by 3!. Therefore, this 2-nd order permutation point induces permutation set with cardinality |P(0)] [[- nz!!
Now should consider other 2-nd order permutation points (at layer k) giving rise the same network function and corresponding to the same unordered partition, which we did not count in this permutation set. If we had chosen another parameter vector replicate three times, this 2-nd order permutation point would induce another permutation set. Note that we can choose the parameter
vector to replicate out of n& - 2 in 2 ways and there are 1 d-1 ny! many points in each
3! 11; d-
one of the permutation sets. Therefore, we end up having ("+-²) [-=1 ny! many 2-nd order permutation points (at layer k) corresponding to this unordered partition.
(ii) n& = For this case, we have 212 permutations given by permuting the neuron indices of layer k instead of the usual ng!! permutations since we should eliminate the equivalent permutations corresponding to the permutations among the two pairs of duplicated parameter vectors with a division by 2!a. Therefore,
this 2-nd order permutation point induces a permutation set with cardinality [P()) = ュ 1 n,J.
Again, we should consider other 2-nd order permutation points (at layer k) giving rise to the same network function and corresponding to the same unordered partition. Note that parameter vectors to duplicate out n (m4-2) ways and there are 2í2
choose two [d-] nyl many points
in each one of the permutation sets. Therefore, we end up having (n=-2) 2T ji=1 ny! many 2-nd
d-1
17

---

Under review as a conference paper at ICLR 2020
order permutation points (at layer k) corresponding this unordered partition. Overall, have (nE 3
II ny!+ ("x 2) I[-=1 ny! many 2-nd order permutation points at layer
(3) The case K 3:
There are three ways to have ni 3 distinct vectors out of vks, corresponding to three unordered parti- tions of ng: (i) ng 4+ +++..... + +1, (ii) ny 3+2+ ..... . 1, and (iii) ny -++++++1++
(i) Th 44+1+ For this case, we have ny! permutations given by permuting the neuron indices of layer k. Therefore, this 3-rd order permutation point induces a permutation set with cardinality |(()) = 11 nyl.
As usual, we should consider other 3-rd order permutation points (at layer k) giving rise to the same network function and corresponding to the same unordered partition. If we had chosen another parameter vector to replicate four times, this 3-rd order permutation point would induce another permutation set. Note that we can choose the parameter vector replicate of nt 3 in ("T
ways and there are d j=1 ny! many points in each one of the permutation sets. Therefore, we end
up having ("11- 1 [1==1 j=1 ny! many 3-rd order permutation points (at layer k) corresponding to this unordered partition.
(ii) ny = 3+ For this case, we have
312! permutations given by permuting the neuron indices of layer k. Therefore. this 3-rd order permutation point induces permutation set with cardinality IP(0)] 3 II d-1 ny!.
As usual, we should consider other 3-rd order permutation points (at layer k) giving rise to the same network function and corresponding to the same unordered partition. If we had chosen two other parameter vector to replicate, say (((hk) and (²(k), this 3-rd order permutation point would induce another permutation set. Note that can choose two parameter vectors to replicate out of nig in 2! ("==3) ways. We have extra 2! factor here since have different
permutation sets if replicate 0((Aa) twice and (((k) three times, vice versa. Yet, there ny! many points each one of the permutation sets. Therefore, we end up having mK 2 3121 1 ny! ("x-3) 31 [ ny! many 3rd.rrder permutation points (at layer k)
32
21
corresponding to this unordered partition.
(iii) ni -2+2+2+1+..-
For this case, we have ny. 2 permutations given by permuting the neuron indices of layer k. Therefore, this 3-rd order permutation point induces a permutation set with cardinality IP(0) = / I1 nty..
As always, we should consider the other 3-rd order permutation points layer giving rise the same network function and corresponding to the same unordered partition. Note that we can choose
II ny! many points in each one of the permutation sets. Therefore, we end up having ("==²) 27 1 ny! many 3-rd order permutation points (at layer k) corresponding to this unordered partition. Overall, we
three parameter vectors to duplicate out of ng 3 in ("u-3) ways and there 23
have (n=-3) I ny! + (me-3) I ny! + (" 1 I ny! many 3-rd order permutation points at layer k.
21
(4) A note the general closed form formula for T(K, m.):
For general integer K there is no closed-form formula for the number partitions, although is easy have closed-form formula for the number of permutation points for one given unordered partition following the counting arguments. Thus, we believe that there is no way to find a closed-form formula for T(K, n&) function of K. However, the lower bound for T T(K, n4) is also the dom-
18

---

Under review as a conference paper at ICLR 2020
inating term for large nk, since every other summand would be polynomial of at most (K1)-th order.
(5) A lower bound for general K:
For general K, we have | ni distinct parameter vectors in the small network. There are many ways to partition ny into I positive integers without respecting order. Since are interested in lower bound, we only consider the following unordered partition: 72 = = = + + 1 +.... 1, Le. we have K duplicated parameter vectors and ng 2K parameter vectors that appear once. For this unordered partition, have ("*=*) K) ways choose the duplicated parameter vectors. For each one of these choices, we can permute the neuron indices in nxl different ways. Including the K)
permutations in other layers j * k, end up with ("*=K) 2 IT ny! points in the permutation set. The number is a lower bound of [K, nk). because other unordered partitions of ng give rise to other K -oderr permutation points at layer k.
C.5 PROOF OF LEMMA 2
We can approximate the factorial an integer n using Stirling's 's formula
71
n!
2
as m -> 0o
(4)
We note that this approximation leads to accurate results even for small n. As - xo, both K + x and n 2K + Do for finite K. Therefore, we can apply Stirling's formula both for n K and n 2K:
n K
1
(n K)!
(5)
2
K
2!K (n- 2K)!K!
n-K
2 K)
n-K
(n K)!
21K
(n
2K)!K!
21K
as n2
00
(6)
2n(nn 2
n-2K
K!
1
K
(n K)n mmn-k
1
as > 00
2!K
n1 2K
(n 2K) In n-2K 2K e K!
1
(K 1)ah 1m K
1
n K KK
2) 2K K-
as - 00
(8)
2!K
n
2 (x
ek K!
2!K
K
e K!
K
2 c
KT 11
CK"
as n 00
(9)
C.6 PROOF OF LEMMA 3
We already know the number of equilavent K order permutation points (the ones that reduce the same configuration in the landscape of the neural network with (nz...., 74 K.... nn2)) is at least E T(K, nx) I ng.! (Proposition 3-(i)). We can easily that see that every permutation point gives rise to a distinct high-dimensional subspace of critical points by observing that their parameter vectors in layer k would be in distinct positions when projected
the parameters of the layer since we never repeat the same set of parameters in layer k. If two such subspaces were the same, their projection on lower dimensional space (parameters of the layer k) would be same necessarily, Therefore, the subspaces mentioned are distinct and the number of them is equivalent to the number of related permutation po
19


Reviews:
[{"review_id": "HklMZ14z5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a special type of weight symmetry in neural networks. I think studying the geometry of neural-nets is an interesting and important direction for understanding neural-nets, and along this direction, weight-space symmetry is an important subject. However, it seems to me this paper does not make enough contributions. Details are given below.\n \nList of contributions of the paper:\n \n1.\tPropose an algorithm to find a (low-loss) path connecting arbitrary two partner local minima and passing through a permutation point, where a permutation point is defined as a weight setting where a pair of neurons (in the same layer) have the same fan-in and fan-out weights. \n\n2.\tTheoretically prove that some permutation points are connected via paths with equal loss. (Proposition 1 and 2)\n\n3.\tProvide a lower bound for the number of permutation points and high-order permutation points (Proposition 3).\n\nCons: \n\n1.\tThe theory of this paper is a bit weak. There are three propositions.  Proposition 1 and Proposition 2 are about the equal-loss surface and theoretical existence of an equal-value path. They are kind of straightforward to prove. Prop. 3 is about counting the number of permutation points. It is a rather simple combinatorial problem, and the lower bound of the expression (an exponential bound) seems standard. \n\n2.\tSimple proofs can sometimes provide nice insight, but it is not clear how the study of partner global minima can help improve the understanding of DNN. \n    --First, partner global minima are just a special case of critical points created by \"neuron splitting\", which has been comprehensively studied in  [FA2000] (Fukumizu and Amari, 2000). Note that Theorem 1 of this paper is also directly borrowed from [FA2000]. To me, this paper does not provide much additional theoretical insight on neuron splitting. \n    --Second, what is the significance of the simulation results? Prior works have shown the existence of low-cost path; this paper shows the existence of a low-cost path containing a permutation point. The major difference is that the new low-cost path is more special. Why is this finding interesting and useful? (noting that the proof of the existence of such a path seems to be much easier than proving the existence of such a path for two general global minima).\n    \n\n3.\tIt is not clear how the path-finding algorithm helps in practice.\na)\tThe algorithm is computationally expensive. It is a double-loop algorithm: in the outer loop, d is reduced by a tiny amount at each time; in the inner loop, for a fixed d, gradient descent is run for the entire DNN (with only one parameter excluded) until convergence. The total time is (# of d) * (original running time). Here, # of d’s depends on the grid: if the initial d is 10 and the grid size is 0.1, then (# of d) = 100. \n     Compared to the path-finding algorithm in Garipov et al., which only runs GD for one time, this algorithm is much more expensive, yet the benefit is unclear. \nb)\tThe motivation of the algorithm is not clear. Why choose to monotonically decrease the difference between the fan-in weights (of the chosen pair of neurons), but let all other weights freely optimized during the pathfinding algorithm? The paper does not provide a detailed explanation of this. \n\n4.\tMinor issues\n  -- The weight parameters created by Algorithm 1 may not be a critical point of the loss function, and thus not necessarily a saddle point. I think the claim “since the path connects two partner minima, there must be at least one saddle point on the path” is incorrect without extra assumptions. \n  --The paper mentioned \"global minima\" in the introduction; but in practical training, one does not always find global minima. Is \"global minima\" crucial for the theory and for the algorithm? ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkluC-v3FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presented a method for studying the landscape of the loss function w.r.t. parameters in a neural network from the perspective of weight-space symmetry. The detailed method includes constructing/optimising a low-loss path in between two parameter vectors (incoming connections from the previous layer) of two neurons respectively, and then set the output weight vectors (outgoing connections to the next layer) to be the same without changing the output of the current layer. \n\nThe empirical results show that the proposed optimisation scheme for finding the path is indeed low-loss, which implies that there exists numerous critical points in between two equivalent local minima (which are global minima in over-parametrised models).\n\nMy major concern is that scope of the study is very limited, since only permutation is considered here. I am not an expert in this field, however, I could come up with examples which could easily generalise the method of study to rotations since rotation matrices include permutation matrices. \n\nWe can look into the loss landscape of 2D matrix factorisation in this form UV^T=W, and it is obvious that any rotation of U on the RHS of it is an optimal solution as long as the same rotation is applied to V. The perspective from this optimisation problem is that it gives us a continuous plateau and it includes permutation of the dimensions. \n\nFor neural networks with only one hidden layer. For example, consider a neural network in this form y=Uf(Vx) where U and V are parameter matrices and f() is a monotonic squashing function. It is easy to show that, when U is timed with a matrix R, where RR^T= I, as in U'= UR, there exist a V' and \\alpha that gives R^Tf(Vx) = \\alpha f(V'x) so that Uf(Vx) = URR^Tf(Vx) = U'f(V'x) for the hyperbolic tangent function. In the case where ReLU activation function is used as f(), then as long as the rotation doesn't produce negative entries, V' exists. In addition, when f is ReLU, isotropic scaling of the outputs from the first layer also gives rise to equivalent optima.  \n\nCompared to the proposed study, the aforementioned way of studying the neural networks naturally gives continuous plateaus w.r.t. U in the loss landscape, and, by studying the discontinuity of the landscape w.r.t. V, more understanding could be unveiled. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJxkDMC6YS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the permutation symmetry of deep neural networks. It was known that by reordering neurons and their connections in each layer, the input -> output map the neural network represents can be preserved. This corresponded to a set of unconnected equivalent points in the weight space. The authors study the weight-space connectivity of these points through midpoints they call “permutation points”. They demonstrate that such points are members of high-dimensional manifolds of equivalent points. After that, they look at empirical experiments and explicitly construct a path between two equivalent weight-space points on a toy task and MNIST.\n\nI generally like the paper and its geometrical lens on the problem. I find the figures very helpful in understanding what is going on. However, there are a few points that I wasn’t entirely clear on. I will detail them below.\n\n-- Point 1 --\nConnecting equivalent minima vs connecting SGD-found minima. \n\nIf I understood the paper correctly, the derivation connects two weight space points A and B whose weights and biases, once loaded to the neural network, would have the exact same answers on all inputs X i.e. f_A(X) == f_B(X), i.e. they are a pair of equivalent points. I understand that those are the ones we obtain by using the permutation symmetries.\n\nHowever, some of the papers cited look at the low-loss paths between pairs of optima found by training with SGD from independent initializations, which in turn represent different functions. I.e. for two such optima C and D, the predictions on the val/test set are (sometimes) different, showing that the functions are not the same. I found the initial evidence in:\n\nLarge Scale Structure of Neural Network Loss Landscapes. Stanislav Fort and Stanislaw Jastrzebski. NeurIPS 2019. (https://arxiv.org/abs/1906.04724)\n\nAnd also in much more detail in another OpenReview submission:\n\nDeep Ensembles: A Loss Landscape Perspective. (https://openreview.net/forum?id=r1xZAkrFPr)\n\nI found your results very compelling, however, the two problems seem to be quite different -- on one hand you are connecting a pair of minima that are in fact *identical* by construction. On the other hand the empirical work in literature (especially in the two papers I provided above) deals with pairs of minima that in fact do differ on the test set (at least).\n\nWould you mind commenting on how the two approaches relate to each other? \n\n-- Point 2 --\nHigher order connectivity\n\nIn Large Scale Structure of Neural Network Loss Landscapes. Stanislav Fort and Stanislaw Jastrzebski. NeurIPS 2019. (https://arxiv.org/abs/1906.04724), the authors look at higher-order connectivity between SGD-found optima (e.g. connecting 3 optima on a 2-manifold, 4 optima on a 3-manifold etc.). They also have a particularly simple path-finding algorithm. This seems relevant to the approach you are presenting, although the points in Point 1 still stand.\n\n-- Point 3 --\nPrevious work on connecting two optima using layer-wise weight merging\n\nExplaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets. Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Sanjeev Arora, Rong Ge. (https://arxiv.org/abs/1906.06247)\n\nThey prove that a low-loss path between 2 optima exists provided you can apply a p_keep = 0.5 dropout on each of the optima without incurring a significant loss punishment for it. This paper seems very related to your approach. Would you mind commenting on the differences?\n\n-- Conclusion -- \nI like the paper and the idea in general. I appreciate the geometrical lens the authors took. My main point of confusion relates to the connection between this work and the low-loss connectivity between inequivalent optima found in literature, which (at least to me) seems to be the more interesting of the two connectivities.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After communicating with each reviewer about the rebuttal, there seems to be a consensus that the paper contains a number of interesting ideas, but the motivation for the paper and the relationship to the literature needs to be expanded.  The reviewers have not changed their scores, and so there is not currently enough support to accept this paper.
Decision: Reject