The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks
Authors: Rahim Entezari
Hanie Sedghi
Olga Saukh
Behnam Neyshabur
Venue: ICLR 2022 Poster (2022)
Keywords: Permutation
Invariance
Mode Connectivity
Energy Barrier
Loss landscape
Deep Learning

Abstract: In this paper, we conjecture that if the permutation invariance of neural networks is taken into account, SGD solutions will likely have no barrier in the linear interpolation between them. Although it is a bold conjecture, we show how extensive empirical attempts fall short of refuting it. We further provide a preliminary theoretical result to support our conjecture. Our conjecture has implications for the lottery ticket hypothesis, distributed training, and ensemble methods. The source code is available at \url{https://github.com/rahimentezari/PermutationInvariance}.

Published as a conference paper at ICLR 2022
The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks
Rahim Entezari', Hanie Seghi", Olga Saukh', and Behnam Neyshabur
'TU Graz CSH Vienna, Google Research, Brain Team, GGoolee Research, Blueshift Team ABSTRACT
In this paper, we conjecture that if the permutation invariance of neural networks is taken into account, SGD solutions will likely have no barrier in the linear inter- polation between them. Although it is a bold conjecture, we show how extensive empirical attempts fall short of refuting it. We further provide a preliminary theo- retical result to support our conjecture. Our conjecture has implications for lottery ticket hypothesis, distributed training and ensemble methods. The source code available at ptttps:/ggitee com/ http////iiiiieeeeeeeee////aaaaaa
INTRODUCTION
Understanding the loss landscape of deep neural networks has been the subject of many studies due
to its close connections to optimization and generalization (Li et al. 2017 Mei et al. 2018 Geiger
al. 2019 Ng gguyen al.] 2018: Fort al. 2019 Baldassi et al. 2020)) Empirical observations
suggest that loss landscape of deep networks has many minima (Keskar et al. 2017 Draxler et al.
2018 Zhang al., 2017). One reason behind the abundance of minima over- over-paramenn parametrization.
Over--aramente parametrized networks have enough capacity to present different functions that behave similarly on the training data but vastly different on other inputs (Neyshabur et al. 2017 Nguyen et al. 2018) [i al. 2018, Liu et al. 2020). Another contributing factor is the existence of scale and permutation invariances which allows the same function to be represented with many different parameter values of
the same network and imposes counter- inntter-nttuitve geometry the loss landscape (Neyshabur et al.)
2013 Brea et al. 2019a).
Previous work study the relationship between different minima found by SGD and establish that they are connected by a path of con-increasing loss; however, they are not connected by a linear path (Freeman & Bruna 2016: Draxler et al.) 2018 Garipov et al., 2018). This phenomenon is often referred to as mode connectivity (Garipov et al. 2018) and the loss increase on the path between two solutions is often referred to (energy) barrier (Draxler et al. 2018). Understanding linear mode connectivity (LMC) is highly motivated by several direct conceptual and practical implications from pruning and sparse training distributed optimization and ensemble methods.
The relationship between LMC and pruning was established by Frankle et al. 2020) where they showed the correspondence between LMC and the well-known lottery ticket hypothesis (LTH) (Fran- kle & Carbin 2019). In short, LTH conjectures that neural networks contain sparse subnetworks that can be trained in isolation, from initialization, or early in training to achieve comparable test accuracy. |Frankle et al. (2020) showed that solutions that are linearly connected with no barrier have the same lottery ticket. They further discuss how coneecivnnet is associated with stability of SGD. This view suggests that SGD solutions that are linearly connected with no barrier can be thought of as being in the same basin of the loss landscape and once SGD converges to a basin, shows a stable behavior inside the basin"] Because of the direct correspondence between LMC and LTH, any understanding of LMC, has implications for LTH, stability of SGD and pruning techniques.
Linear mode connectivity has also direct implications for ensemble methods and distributed training. Ensemble methods highly depend on an understanding of the loss landscape and being able to sample from solutions. Better understanding of mode connectivity has been shown to be essential in devising better ensemble methods (Garipov et al. 2018). Linear mode connectivity between solutions or checkpoints also allows for weight averaging techniques for distributed optimization to be used as effectively in deep learning as convex optimization (Scaman et al. 2019).
'This notion of basin also consistent with the definition proposed by Neyshabur al. 2020

---

Published as a conference paper at ICLR 2022
Real World
Our Model
A
parmutation
B
Barner (Our Model)
0.8
D'
1000
permutiion
0.6
0.4
500
0.0
Final parameters
Random Init.
Random Perm.
0.0 0.2 0.4 0.6 0.8 1.0
Barrier (Real World)
Figure 1: Linear mode connectivity when using permutation invariance. Left: Schematic picture of four minima A, B, C, in different basins with an energy barrier between each pair. However, our conjecture suggests that permuting hidden units of B, C' and D would result in B3, C" and D) which present the exact same function as before permutation while having no barrier on their linear interpolation with A. Middle: Our model for barriers real world SGD solutions. In real world train networks running SGD with different random seeds starting from different initializations. In our model, different final networks are achieved by applying random permutations to the same SGD solution (or equivalently, applying random permutations to the same initialization and then running SGD with the same seed on them). Right: Aggregation of our extensive empirical evidence (more than 3000 trained networks) in one density plot comparing barriers in real world against model across different choices of architecture family, dataset, width, depth, and random seed. Points in the lower left mostly correspond to lowest barrier found after searching in the space valid permutations using a Simulated Annealing (SA). For a detailed view on architectures and datasets see Figure 10 in Appendix A.3
In this paper, we conjecture that by taking permutation invariance into account, the loss landscape can be simplified significantly resulting in linear mode connectivity between SGD solutions. We investigate this conjecture both theoretically and empirically through extensive experiments. We show how attempts fall short of refuting this hypothesis and end up supporting evidence for it (see Figure [ We believe our conjecture sheds light into the structure of loss landscape and could lead to practical implications for the aforementioned areas.
Contributions. This paper makes the following contributions:
We study linear mode connectivity (LMC) between solutions trained from different initial- izations and investigate how it is affected by choices such as width, depth and task difficulty for fully connected and convolutional networks (Section]
We introduce our main conjecture in Section 3 If invariances are taken into account, there will likely be barrier on the linear interpolation of SGD solutions (see the left panel of Figure]] I.
By investigating the conjecture theoretically, we prove that it holds for wide enough fully-connected network with one hidden layer at random initialization Seetion 3).
In Section 4 we provide strong empirical evidence in support of our conjecture. To overcome the computational challenge of directly evaluating the hypothesis empirically, which requires searching in the space of all possible permutations, we propose an alternative approach. We consider set of solutions corresponding solution (our model) and show several empirical evidences suggesting our model is good approximation for all SGD solutions(real world) with different random seeds (see the middle and right panel of Figure
random permutations of a single fixed SGD
Further related work. Permutation symmetry of neurons in every layer results in multiple equivalent minima connected via saddle points. Few studies investigate the role of these symmetries in the context of connectivity of different basins. Given a network with L layers of minimal widths ri...., rī_ that reaches zero-loss minima rjl....,TLL1 isolated points (permutations of one another), [Simçe et al. (202T) showed that adding one extra neuron to each layer is sufficient to connect all these previously discrete minima into single manifold. Fukumizu Amari (2000) prove that a point corresponding to the global minimum of smaller model can be local minimum or saddle point of the larger model. Brea et al. (019b) find smooth paths between equivalent global minima that lead through permutation point, i.e., where the input and output weight vectors of two neurons in the same hidden layer interchange. They describe a method to permute all neuron indices in the same layer at the same cost. (Singh & Jaggi (2020) proposed layer-wise model fusion algorithm for making ensembles. Their method utilizes optimal transport for aligning neurons across the models trained from different initializations. Tatro et al. (2020) showed that aligning the neurons
2

---

Published as a conference paper at ICLR 2022
in two different neural networks makes it easier to find second order curves between them in the loss landscape where barriers are absent.
2 LOSS BARRIERS
In this section, we first give formal definition for linear mode connectivity and study how it affected by different factors such as network width, depth, and task difficulty for a variety of architectures.
2.1 DEFINITIONS
Let fo(-) be function presented by a neural network with parameter vector 0 that includes all parameters and ((0) be the any given loss (e-g.. train or test error) of f.(.). Let (0), 02) C(a0) + (1 a))2), for
[0, 1] be the loss of the network created by linearly interpolating between parameters of two networks fa, (-) and Sa,(,), (.). The loss barrier , 02) along the linear
path between 0 and fg is defined as the highest difference between the loss occurred when linearly
connecting two points 01, Bg and linear interpolation of the loss values at each of them:
B(01,82 = supl[[((aa) + - a)))) - (a[(()) + +1 (1- (1-a)
(1)
The above definition differs from what was proposed by Frankle et al. (2020) in that they used 0.5 + (.g instead of ((() ((())=+ + (1 ((2) in our definition. These definitions are the same [(0)) = C(22). But if C(01). ((2)) are different, we find our definition to be more appropriate because it assigns We say that two networks 0, and 0g are linear mode connected if the barrier between them along a linear path is (Frankle al. 20200.. It has been observed in the literature that any two minimizers of a deep network can be connected via non-linear low-loss path (Garipov et al. 2018 Draxler ct al. 2018 Fort & Jastrzebski 2019). This work examines linear mode connectivity (LMC) between minima. Next, we empirically investigate the effect of task difficulty and choices such as architecture family, width and depth on LMC of SGD solutions.
barrier value to a loss that is changing linearly between 0 and 02.
2.2 EMPIRICAL INVESTIGATION: BARRIERS
In this section, we look into barriers between different SGD solutions on all combinations of four architecture families (MLP (Rosenblatt) 1961) Shallow CNN (Neyshabur 2020), ResNet (He et al. 2015) and VGG (Simonyan Zisserman 2015 and four datasets (MNIST (LeCun & Cortes] 2010 SVHN (etter et al.) (011), CIFAR- (Krizhessky et al. 2009) and CIFAR- T00 (Krizhevsky et al. 2009)). The main motivation to use Shallow CNN is to move from fully connected layers (MLP) to convolutions. The main difference between Shallow CNN and VGG16 is depth and the main difference between ResNet18 and VGG16 is existence of residual connections. We empirically investigate how different factors such as architecture family, width, depth and task difficulty impact the barrier S We refer to training loss barrier as barrier. For loss barriers on a test set see E.4 For train and test errors A.2
We evaluate the impact of width on the barrier size in Figure 2 values of width the barrier becomes small. This effect starts at lower width for simpler datasets such as MNIST and SVHN compared CIFAR datasets. A closer look reveals that the barrier increases with width up to a point and beyond that increasing width leads to lower barrier size. This effect is reminiscent of the double descent phenomena (Belkin al. 2019 Nakkiran al.) 2019). Checking the test error (Figure g) indicates that in our experiments the barrir peak happens at the same size that needed fit the training data. This phenomena observed for both fully-connected
Width:
We note that for large
In all plots the harrier is evaluated using training loss across 5 different random pairs (10 random SGD solutions). For casier comparison between all figures, report the train accuracy barrier in all barrier plots. In our experiments, we observed that evaluating the barrier at a 1 a reasonable surrogate for taking the supremum over a (the difference is less than 10 11. Therefore, to save computation, report the barrier value
3

---

Published as a conference paper at ICLR 2022
1.0
MIP
1.0
Shallow CNN
1.0
VGG16
1.0
RecNar18
MART De
MShT
0.6
0.6
0.4
0.4
04
0.4
0.2
0.2
02
0.2
CEARDS
0.0
2
21
2
2'
0.0
Width
Width
Winth
Math
Figure 2: Effect of width on barrier size. From left to right: one-layer MLP, two-layer Shallow CNN, VGG-16 and ResNet- 18 architectures on MNIST, CIFAR-10, SVHN, CIFAR- 100 datasets. For large width sizes the barrier becomes small. This effect starts at lower width for simpler datasets such as MNIST and SVHN compared to CIFAR datasets. closer look reveals similar trend to that of double-descent phenomena. MLP architectures hit their peak a lower width compared to CNNs and a decreasing trend starts earlier. For ResNet. the barrier size is saturated at a high value and does not change due to the effect of depth as discussed in Figure 3
MLP
Shallow
1.0
VGG
Restett
Baries
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
SAH
0.2
5MH
0.2
CHO222
0.0
11
13
18 19 3B
34
50
Depth
Desth
Depth
Death
Figure 3: Effeet of depth on barrier size. From left to right MLP, Shallow CNN, VGG 13,1,119),, 19), and ResNee((18.34 architectures on MNIST, CIFAR-10, SVHN, CIFAR-100 datasets. For MI. and Shallow CNN. we fix the layer width at 2 while adding identical layers shown along the x-axis. Similar behavior is observed for connecco and CNN family, i.e., low barrier when number of layers are low while observe a fast and significant barrier increase as more layers are added. Increasing depth leads to higher barrier values until it saturates (as seen for VGG and ResNet).
and convolutional architectures. MLP architectures hit their peak at a lower width compared CNNs and decreasing trend starts earlier. For ResNets the barrier size is saturated at a high value and does not change. The barrier value for VGG architecture on different datasets is also saturated at a high value and does not change by increasing the width. Such similar behavior observed for both ResNets and VGG architectures is due to the effect of depth as discussed in the next paragraph.
Depth: We vary network depth in Figure to to evaluate its impact on the barrier between optimal solutions obtained from different initializations. For MLPs, we fix the layer width at 2 while adding identical layers as shown along the x-axis. We observe a fast and significant barrier increase as more layers are added. For VGG architecture family we observe significant barriers. This might be due to the effect of convolution or depth. order to shed light on this observation, we use Shallow CNN (Neyshabur 2020) with only two convolutional layers. As can be seen in Figure 3 when Shallow CNN has two layers the barrier size is low, while keeping the layer width fixed at 20 and adding more layers increases the barrier size. For residual networks we also consider three ResNet architectures with 18, 34 and 50 layers and observe the same barrier sizes as VGG for all these depth values. The main overall observation from depth experiments is that for both fully-connected and convolutional architectures, increasing depth increases the barrier size significantly so the effect of depth is not similar to width. This can also be attributed the observations that deeper networks usually have a less smooth landscape (Li et al. 2017).
Task difficulty and architecture choice: In Figure 4 we look into the impact of the task difficulty provided by the dataset choice (MNIST, SVHN, CIFAR-IO, CIFAR-100, and ImageNet (Deng et al. 2009)) and the architecture type (one-layer MLP with 210 neurons, Shallow CNN with two convolutional layer and width of 210 VGG-16 with batch nonnchoommaization, ResNet18 and ResNet50). Each row in Figure 4a and Figure shows the effect of task difficulty, e.g., fixing the task to SVHN and moving from MLP to Shallow CNN gives lower test error hence lower barrier size. Each column also represents the effect of architecture on a specific dataset, e.g., fixing the architecture to Shallow CNN and moving from CIFARIO to CIFARI00 presents an increase in test error, hence increase in the barrier size. Although deep architectures like VGG16 and ResNet18 present low test error, the discussed effect of depth saturates their barrier at a high level. Figure 4c aggregates the correlation between test error and size of the barrier. For MLP and Shallow CNN observe high positive correlation between test error and barrier size across different datasets. Deeper networks (VGGs, ResNets) form cluster in the top-left, with low test error and high barrier size.
4

---

Published as a conference paper at ICLR 2022
MNIST
SVHN
CI
CIFAR100
HNIST
SVHN SVHN
CIFAR10
CIFAR100
1.0
1.0
MLP 241144
0.005
0.995
1.0081
0.3483
2.7280
Barrier Size (Train)
0.8
0.8
0.8
0.6
Shallou CNN
8.0161
0.1003
0.3102
0.48
0.6
0.0115
0.1197
0.3190
0:8346
0.6
J0J.3 1591
Sarfic
VGG16
0:8975
0.4
0.0698
0.4
2hih
0.2
CRARLESD
0.2
0.2
invoyste
ResNet18 8
5.8551
0.8011
0.8066
0.0077
0.0598
0.1694
0.4261
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.0
Test Error
(a) Barrier for different architcctures and task difficulty
(b) Achieved error
(c) Lower test error results in lower barrier for shallow networks
Figure 4: Effect of architecture choice and task difficulty barrier size. Each row in Figure 4a and FigureFBbshows shows the effect of task difficulty while each column represents the effect of architecture dataset. Figure notes that pair of (architecture, task) has lower barrier if the test error is lower. Therefore. any changes in the architecture or the task that improves the test error, also improves the loss barrier. Effect of depth is stronger than (architecture, task) which leads to high barrier values for ResNets on MNIST, SVHN, CIFARIO, CIFARIOO, and ImageNet.
specific
ROLE OF INVARIANCE IN LOSS BARRIERS
Understanding the loss landscape of deep networks has proven to be very challenging. One of the main challenges in studying the loss landscape without taking the optimization algorithm into account that there exist many minima with different generalization properties. Most of such minima are reachable by SGD and we only know about their existence through artificially-made optimization algorithms and training regimes (Neyshabur et al. 2017). To cireumvent this issue, we focus on parts of the landscape that are reachable by SGD. Given dataset and an architecture, one could define probability distribution over all solutions reachable by SGD and focus on the subset where SGD more likely to converge to.
3.1 INVARIANCES IN NEURAL NETWORK FUNCTION CLASS
We say that a network is invariant with respect to a transformation if and only the network resulting from the transformation represents the same function the original network. There are two well-known invariances: one is the unit-rescaling due to positive homogeneity of ReLU activations (Neyshabur et al. 2015) and the other is permutation of hidden units. Unit-rescaling has been well-studied and empirical evidence suggests that implicit bias of SGD would make the solution converge to a stage where the weights are more balanced (Neyshabur et al. 2015 Wu et al., 2019). Since we are interested in the loss landscape through the lens of SGD and SGD is much more likely to converge to particular rescaling, consideration of this type of invariance does not seem useful. However, in the case of permutations, all permutations are equally likely for SGD and therefore, is important to understand their role in the geometric properties of the landscape and its basins of attraction. Here consider invariances that are in form of permutations of hidden units in each layer of the network, i.e., each layer i with parameters W; is replaced with P.W.P.- where P; is permutation matrix and Pt P, is the identity matrix. Note that results only hold for permutation matrices since only permutation commutes with nonlinearity. We use P to refer to the of valid permutations for neural network and
refer valid permutation.
3.2 OUR CONJECTURE
As mentioned above, SGD's implicit regularization balances weight norms and, therefore, scale invariance does not seem to play an important role in understanding symmetries of solutions found by SGD. Consequently, here we focus on permutation invariance and conjecture that taking it into account allows us have a much simpler view SGD solutions. We first state our conjecture informally:
Most SGD solutions belong to a set S whose elements can be permuted in such a way that there is no barrier on the linear interpolation beiween any two permuted elements in S.
The above conjecture suggests that most SGD solutions end up in the same basin in the loss landscape after proper permutation (see Figure left panel). We acknowledge that the above conjecture is bold.
5

---

Published as a conference paper at ICLR 2022
Nonetheless, argue that coming up with strong conjectures and attempting disprove them is an effective method for scientific progress. Note, our conjecture also has great practical implications for average models that are in the same basin in the loss
model ensembling and parallelism since landscape. The conjecture can be formalized as follows:
Let f(0) be the function representing a feedforward network with parameters E IR P be the set of all valid permutations for the network. P: ER x x - R be the function that applies a given permutation to parameters and returns the permuted version, and B(.,)) be the function that returns barrier value between two solutions as defined in Equation [ Then, there exists width h >> O such that for any network f(0) of width at least h the following holds: There exist set of solutions S C R and a function Q S + such for any 01, O2 E S.
Conjecture 1.
Q(0:)), 02) ss 0 and
with high probability over an SGD solution 0, we have E S.
Next, we approach Conjecture from both theoretical and empirical aspects and provide some evidence to support it.
3.3 THEORETICAL RESULT
In this section we provide elementary theoretical results in support of our conjecture. Although the theoretical result is provided for a very limited setting, we believe it helps us understand the mechanism that could give rise to conjecture. Bellow, theoretically show that Conjecture| [ holds for a fully-connected network with a single hidden layer at initialization. Proof is given in Appendix D
Theorem 3.1. Let fx, oUxx be a fully-connected network with h hidden units where a is ReLU activation, E R²' and U E Rixd are the parameters and x E IR is the input. If each element of U and U' is sampled uniformly from [-1/ 1 1/ and each element of and v' is sampled uniformly from [-1/vh, 1/Vh,, then for any E Rd such that ||x||| vd, with probability 1 - 8 over U, v,v', there exist a permutation such that
fav+(I- (1-="" (0 (x) - -fv.u(xv) (1 at)-)ffv..xx)) = =0 -(h-2--) 25)
where v" and U" permuted versions v' and U².
Theorem 3.1 states that for wide enough fully-connected networks with single hidden layer, one can find a permutation that leads to having no barrier at random initialization. Although, our prove only covers random initialization, we believe with more involved proof, it might be possible to extend it to NTK regime (Jacot al. 2018). We leave this for future work.
3.4 DIRECT EMPIRICAL EVALUATION OF CONJECTURE
Another possible approach is to use brute-force (BF) search mechanism and find the function Q for elements of S. The factorial growth of the number of permutations with the size of hidden units in each layer hinders exhaustive search for winning permutation и to linear mode connect P(O,, T and 02. Even for MLPs with just one hidden layer brute-force works in reasonable time up to 24 neurons only, forcing the search to examine 2 R 10 permuted networks. BF not feasible even for modest size deep networks. For small networks, between different models (see E.3). However, small size networks are not the focus of this paper and Conjecture I specifically mentions that.
use BF to find permutations
Given the size search space, using a more advanced search algorithm can be useful. The issue with this approach is that since it relies on the strength of search algorithm, if the search algorithm fails in finding the permutation, one cannot be sure about the source of failure being the search algorithm or nonexistence of permutation that leads to barrier.
3.5 OUR MODEL VS REAL WORLD: AN ALTERNATIVE APPROACH
We propose the following approach to circumvent the above obstacles. We create competing set (our model) as proxy for set S (real world). Given an SGD solution 6 E S, we define S' = (P(0,, V) E P). We know that set S' satisfies the conjecture. For set 8', all points

---

Published as a conference paper at ICLR 2022
1.0 MLP
1.0
Shallow CNN
1.0
MLP
1.0
Shall OV-CNN
0.8
0.8
0.6
0.5
0.2
0.0
0.0
0.0
0.0
Dopth
Figure 5: Similar loss barrier between real world and our model BEFORE applying permutation. From left to right: one-layer MLP, two-layer Shallow CNN, MLP and Shallow CNN with layer width of 2 Increasing width first increases and then decreases the barrier, while adding more layers significantly increases the barrier size. We observe that S' and S hchave similarly in terms of barrier as we change diffcrent architecture parameters such as width, depth across various datascts.
known permutations 0j. Therefore, one can permute all points remove their barriers with 0j, i.c. for all 02 P(0,, T) one can use ((2) = -- to remove the barrier between 01 and 0z. Our goal therefore to show that similar to S' terms of barrier behavior.
Equivalence of S' and S in terms of barriers, means that if we choose an element @ in S, one should be able to find permutations for each of other elements of the S that the permuted elements have no barrier with 0 and hence are in the same basin as 0. The consequence of the equivalence of our model real world is that Conjecture hhlld.. The conjecture effectively means that different basins exist because of the permutation invariance and if permutation invariance is taken into account (by permuting solutions to remove the barriers between them), there is only one basin, i.c., all solutions reside in the same basin in the loss landscape. We actually want to show S is similar to S' in terms of optimizing over all permutations but that is not possible so we show S is similar to S' in terms of barrier without search when we search over smaller set of permutations using search algorithm. In the next section, we investigate our conjecture using this approach.
4 EMPIRICAL INVESTIGATION
In this section we show that S and S' have similar loss barrier along different factors such as width, depth, architecture, dataset and other model parameters (with and without searching for permutation that reduces the barrier), hence supporting our conjecture. As discussed in Section / the barrier for both VGG and ResNet architectures is saturated high value hinting that the loss landscape might be more complex for these architecture families. In our experiments we observed that S and S' have similar high barriers for both of these architectures (see Appendix E.2). Moreover, we observed that for both S and S' the employed algorithms (Section 4.2) were unable to find a permutation to reduce the barrier and hence our model shows similar behavior to real world Given that the width and depth do not influence the barrier behavior in VGG and ResNet architectures, here we only focus on the effect of width and depth on barrier sizes for MLPs and Shallow CNNs.
4.1 SIMILARITY OF AND
Figure 5 compares ccmmpress model to the real world and shows that S' and S have strikingly similar barriers as we change different architecture parameters such as width and depth across various architecture families and datasets. This surprising level of similarity between our model and real world variety of settings provide strong evidence for the conjecture. Even if the conjecture is not precisely correct as stated, the empirical results suggest that the structural similarities between our model and real world makes our model a useful simplification of the real world for studying the loss landscape. For example, the effect of width and depth on the barrier almost identical our model and the real world which suggests that permutations are perhaps playing the main role in such behaviors.
4.2 SEARCH ALGORITHMS FOR FINDING A WINNING PERMUTATION
The problem of finding a winning permutation π E P is a variant of the Travelling Salesman Problem where neurons are mapped to citics visited by salesman. The problem belongs to the class of NP-hard optimization problems and simulated annealing (SA) is often used to find a solution for such a combinatorial search problem. SA's performance however highly depends on the parameter
All the experiments are included in the aggregated results reported in Figure
7

---

Published as a conference paper at ICLR 2022
Algorithm 1 Simulated Annealing (SA) for Permutation Search
1: procedure SA((0,), ), I..n, 2) Tj = To. Vi 1.,n
Goal: minimize the barrier between n solutions
2:
3:
for k 0: k < kmaxi +++ do k+1)
4:
T 4- temperature( Eeaae
5:
Pick random candidate permutations { Vi 1..n if (Pos,, ft)) < <V((O,, then
6:
D Mr: barrier objective function
7:
T4 4x
return {
1.0
MLP
1.0
Shallow CNN
1.0
MLP
1.0
Shallow CNN
BErOnE
0.8
0.5
0.5
0.5
2AR
0.6 2
0.5
0.6
0.6-
21
2' 2
2'
Figure 6: Performance Simulated Annealing (SA). Two Left: SA2 where average the weights of permuted models first and & is defined as the train error of the resulting average model. Two Right: Search space is reduced i... we take two SGD solutions 0₃ and 82, permute 8 and report the barrier between permuted 01 and 02 found by SA with 2. When search space reduced, SA is able to find better permutations.
choices, including the minimum and maximum temperatures, the cooling schedule and the number of optimization steps. The pseudocode of SA is shown in Algorithm [ SA takes a set of solutions { = I..n, n 2 2 input (we use 5) and searches for the barriers between all permuted (?) solution pairs. To find the best {T² , in each step of SA the current candidate permutations } 1..n are evaluated to minimize the objective function V. We use two versions of simulated annealing that vary in their definition of v to evaluate the conjecture.
of permutations {T²} that reduce
Simulated Annealing 1 (SA1). In the first version SA,, V is defined as the average pairwise barrier between candidate permutations ((P m.), P(0,, m,)), j.
Simulated Annealing 2 (8A2). In the second version SA2, we average the weights of permuted models PO,, TT.) first and defined v as the train error of the resulting average model. The simplest form of SA2 happens if and is discussed in Section A.3
The rationale behind these two versions is that the solutions reside in one basin, there is no barrier between them. Therefore averaging solutions in one basin yields another solution inside their convex hull. Although each version of SA has a different definition the objective function V to find the best permutation, for all SA versions Our empirical results suggest that SA, and SA2 yield very similar performance. However, SA2 significantly less computationally expensive, which makes more suitable for exploring larger models. In the following sections we present the results obtained with SA2 only and refer to this version as SA. For more details on SA implementation see Appendix A.4 The left two plots in Figure 6Jsoww that SA₂ is not able to find permutations that improve pair-wise barrier significantly. We know that SA does not guarantee finding solution and known to lose its effectiveness on TSP benchmarks beyond 1'000 cities (Zhan et al. 2016). The effectiveness of SA is also reduced here as we can only evaluate the cost of full route (divide and conquer is not possible). One way to increase this efffcctiveness is reduce the search space which will discuss next.
report the average barrier between all pairs in the plots.
Search space reduction. In order to reduce the search space, here we only take two SGD solutions 0, and 02. permute 0, and report the barrier between permuted 0, and O2 as found by SA with n = 2. The right two plots in Figure shoows this intervention helps SA to find better permutations. In particular, the barrier improves significantly for MNIST and SVHN datasets for both MLP and Shallow CNN across different width. However, similar to Section 2, we did not observe significant improvements when increasing depth (see Figure 12
8

---

Published as a conference paper at ICLR 2022
MLP
Shallew CNN
MLPP
Shallow CNN
0.8
02
0.2
0.6
0.6
0.6
0.6
0.4
04
0.4
RVET
CRANUE
0.0
0.0
Wiith
Width
Depth
Depthh
Figure 7: Similar loss barrier between real world and model AFTER applying permutation, when search space reduced. We observe that reducing the scarch space makes SA more successful in finding the permutation to remove the barriers. Specifically, SA could indeed find permutations that when applied to d result in zero barrier e.g., MLP for MNIST where depth is (across all width), 2 and 4 (where width is 2 200)
4.3
SIMILARITY OF AND S' AFTER SEARCH
Figure 7 shows the surprising similarity of the barrier between S and S' even after applying permutation found by a search algorithm (when search space is reduced). We also observe that reducing the search space makes SA more successful in finding the permutation (x) } to remove the barriers. Specifically, in some cases SA could indeed find permutations that when applied to 0 result in zero barrier. However, the fact that SA's success shows a similar pattern for S, S' provides another evidence in support of the conjecture. For example, SA successfully reduces the barrier for both S, on MNIST and SVHN datasets. Figure (right) summarizes our extensive empirical evidence (more than 3000 trained networks) in one density plot, supporting similarity of barriers in real world and our model across different choices architecture family, dataset, width, depth, and random seed. Putting together, all our empirical results support our main conjecture.
5 DISCUSSIONS AND CONCLUSION
We investigated the loss landscape of ReLU networks, proposed and probed the conjecture that the barriers in the loss landscape between different solutions of a neural network optimization problem are an artifact of ignoring the permutation invariance of the funetion class. In nutshell, this conjecture suggests that if one considers permutation invariance, there is essentially no loss barrier between different solutions and they all exist in the same basin in the loss landscape. Our analysis has direct implication on initialization schemes for neural networks. Essentially it postulates that randomness in terms of permutation does not impact the quality of the final result. It is interesting to explore whether it is possible to come up with an initialization that does not have permutation invariance and only acts like a perturbation to the same permutation. If all basins the loss landscape are basically the same function, there will be no need to search all of them. One can explore the same basin while looking for diverse solutions and this makes search much easier and would lead to substantially more efficient search algorithms.
Another area where our analysis is of importance is for ensembles and distributed training. Related works (Frankle et al. 2020 Fort et al., 2019) show that simply averaging two SGD solutions would fail. If these models lie at the periphery of a wide and flat low loss region then ensembling them in their weight space (averaging), creates a model tending the center of the region, which leads to performance improvement (Izmailov et al.) 2019 Wen et al.] 2020).. we can track the optimal permutation (that brings all solutions one basin), it is possible to use it to do weight averaging and build ensembles more efficiently. Moreover, we are interested in answering the question whether there a one-to-one mapping between lottery tickets and permutations. Frankle al. (020) requires stability to find lottery tickets. They define stability as the point in training trajectory where, if we branch at this point and train two copies with different seeds, the trained solutions are linearly mode connected. We conjecture that all the SGD trained solutions are linearly mode connected if the permutation considered (satisfying the necessary condition for Lottery Ticket Hypothesis). We believe our analysis laid the ground for investigating these important questions and testing the usefulness of our conjecture in ensemble methods and pruning, which is the subject of future studies.
The biggest limiting factor of our study is the size of the search space and hence we need strong search algorithm, specially for deep models where the size and complexity of the search space was prohibitive in terms of computation for the existing search methods. We hope improvements of search algorithms can help us to extend these results. Lastly, our analysis focuses on image recognition task and extending the results natural language tasks is of interest for future work.

---

Published as a conference paper at ICLR 2022
REFERENCES
Carlo Baldassi, Fabrizio Pittorino, and Riccardo Zecchina. Shaping the learning landscape in neural networks around wide flat minima. Proceedings of the National Academy of Sciences, 117(1): 161-170, 2020.
Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnin practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, (1663))15844--15888 2019.
Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape. arXiv preprint arXiv:1907.02911 2019a.
Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape, 2019b.
Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International conference on machine learning, pp. 1309-1318. PMLR, 2018.
Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes, 2019.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape perspec- tive. arXiv preprint arXiv: 1912.02757, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. ICML, volume 119, pp. 3259-3269. PMLR, 2020.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: 1.01540, 2016.
Kenji Fukumizu and Shun Amari. Local minima and plateaus in hierarchical structures of multilayer perceptrons. Neural Networks, 13:317-327, 05 2000.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson.
Loss surfaces, mode connectivity, and fast ensembling of DNNs, 2018.
Mario Geiger, Stefano Spigler, Stéphane d' Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthicu Wyart. Jamming transition as paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(1):012115, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Xiaoxi He, Zimu Zhou, and Lothar Thiele. Multi-task zipping via layer-wise neuron sharing. arXiv preprint arXiv: 09791, 2018
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:/806.075// 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On batch-batch training for deep learning: Generalization gap and sharp minima, 2017.
10

---

Published as a conference paper at ICLR 2022
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 100 and cifar-10 (canadian institute for advanced research), 2009. httphhttp//w..ccr wwwssttooott.ccom arrront..duu/kii///ffarrr. html MIT License.
Yann LeCun and Corinna Cortes. http://yann,eeau http://ann.ecu..coo/eeteee Creative Commons AttributionSSarr Alike 3.0.
MNIST handwritte digit database.
2010.
URL http://yann. wwwp::ewww....././////eocoo...te wwtp/xob////ssstttcc
Dawei Li, Tian Ding, and Ruoyu Sun. ever-parameterized deep neural networks have no strict local minima for any continuous activations. arXiv preprint 1XX.:1112..10339 2018.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. arXiv preprint arXiv: 171200991, 2017.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- over-varameee parameterized non-linear systems and neural networks. arXiv preprint wxiv:2003.00307. 2020.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115633) 2018.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and Ilya Sutskever, Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.0229; 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading dig- its in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learming and Unsupervised Feature Learning 2011, 2011. URL http://ufld,, Ldl. stanford. edu/housenumbers License: CCO: Public Domain.
Behnam Neyshabur. Towards learning convolutions from scratch. Advances in Neural Information Processing Systems, 2020.
Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro. Path-SGD: Path-normalized opti- mization in deep neural networks. arXiv preprint 1vXiv:556600261 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring gen- cralization in deep learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 5949-59999999 5958, 2017.
Behnam Neyshabur, Hanie Sedghi, and Chiyuan Zhang. What being transferred transfer learning? In NeurlPS, 2020.
Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. On the loss landscape of class of deep neural networks with no bad local valleys. arXiv preprint arXiv:1809.10744 2018.
2018.
Sam Ritchie, Ambrose Slone, and Vinay Ramasesh. Caliban: Docker-based job manager for reproducible workflows. Journal of Open Source Software, 5(53):2403, 2020.
Frank Rosenblatt. Principles of neurodynamics. perceptrons and the theory of brain mechanisms. Technical report, Cornell Acronautical Lab Inc Buffalo NY, 1961.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, and Laurent Massoulié. Optimal con- vergence rates for convex distributed optimization networks. Journal of Machine Learning Research, 20:1-31, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of the International Conference Learning Representations, 2015.
Berfin Şimşek, François Ged, Arthur Jacot, Francesco Spadaro, Clément Hongler, Wulfram Ger- stner, and Johanni Brea. Geometry of the loss landscape in overparameterized neural networks: Symmetries and invariances. arXiv preprint wrXiv:2105.1222.. 2021.
Sidak Pal Singh and Martin Jaggi. Model fusion via optimal transport. Advances in Neural Information Processing Systems, 33:22045-22055. 2020.
11

---

Published as a conference paper at ICLR 2022
N Joseph Tatro, Pin- Yu Chen, Payel Das, Igor Melnyk, Prasanna Sattigeri, and Rongjie Lai. Optimiz- ing mode connectivity via neuron alignment. arXiv preprint arXivv2009.02439, 2020.
Yeming Wen, Dustin Tran, and Jimmy Ba. Batchensemble: an alternative approach to efficient ensemble and lifelong learning. arXiv preprint arXiv:2002.06715. 2020.
Mitchell Wortsman, Maxwell Horton, Carlos Guestrin, Ali Farhadi, and Mohammad Rastegari. Learning neural network subspaces. arXiv preprint arXiv:2 10472, 2021.
Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren, Shanshan Wu, Zhiyuan Li, Suriya Gumasckar, Rachel Ward, and Qiang Liu. Implicit regularization and convergence for weight normalization. arXiv preprint arXiv: /9/ .7996,99666 2019.
Shi-hua Zhan, Juan Lin, Ze-jun Zhang, and Yi-wen Zhong. List-based simulated annealing algorithm for traveling salesman problem. Intell. Neuroscience, 2016:8, March 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the International Conference on Learning Representutions, 2017.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
A IMPLEMENTATION DETAILS
We used Caliban (Ritchie al. 2020) to manage all experiments in reproducible environment in Google Cloud's AT Platform. Each point in plots show the mean value taken over 10 different runs (20 trained networks).
A.1 TRAINING HYPER-PARE PARAMETERS
Table summarizes the set used hyper-parametee for training different networks.
Plyper-parameter
MLP
Shallow CNN
VGG
ResNet
Learning Rate
Fixed 0.01', Fixed 0.0012
Cosine 0.02
Cosine 0.02
Cosine 0.02
Batch Size
64
256
256
256
Epochs
3000
1000
1000
1000
Momentum
0.9
0.9
0.9
0.9
Weight Decay
Data Augmentation
Normalization
Normalization
Normalization
Normalization
MNIST
SVHN, CIFARIO, CIFAR100
Table 1: Training Hyper-parameten
A.2 PERFORMANCE EVALUATION TRAINED MODELS: ERROR AND LOSS
Figure g demonstrate Train and Test error/loss for experiments on the effect of width. Here for MLP we have one hidden layer, for Shallow CNN two convolutional layer, ResNet is fixed to ResNet18. and VGG16 selected from VGG family. Figure also demonstrates Train and Test error/loss for different depth. We set MIP have 1024 hidden units in each layer, Shallow CNN, VGG and ResNest to have 1024, 64, channels in each convolutional layer, respectively.
Taan
M447
0.6
0.6
0.5
0.5
0.4
0.4
0.4
0.4
272
2722"
2-2
272
2-120
Shollow-CNN
VGG16
15a
13F
130
10-
10-7
10ad
10
27.27 22222222--22 22
27
Wi.th
W1.thh
Vildth
Welthh
Figure& 8: Train and Test Error/Loss for Width. Solid and dotted lines correspond to train and test respectively. All models are trained for 1000 epochs except MLP networks that trained for 3000 epochs. The stopping criteria either Cross Entropy Loss reaching 0.01 number epochs reaching maximum epochs.
13

---

Published as a conference paper at ICLR 2022
1.0
MLP
1.0
Shallow-CNN
1.0
VGG
1.0
ResNet
0.8
0.8
0.5
0.8
0.6
0.6
0.6
0.2
0.2
0.0
0.0
0.0
0.0
Depth
Dapth
Depth
Depti
MLP
Shallow-CNN
VGG
ResNitt
101
100
100
1025
10a
10a4
10
10
18
Figure Train Test Error/Loss for Depth. Solid dotted correspond to train test respectively. All models are trained for 1000 epachs except MLP networks that are trained for 3000 epochs. The stopping criteria is either Cross Entropy Loss reaching 0.01 or number of epochs reaching maximum epochs.
A.3 SIMILARITY OF S AND S': DETAILED
Aggregated empirical results. Figure shows the aggregation of our extensive empirical evidence (more than 3000 trained networks) in one plot comparing barriers in real world against our model across different choices of architecture family, dataset, width, depth, and random seed. Points with solid edges correspond to lowest barrier found after searching in the space of valid permutations using Simulated Annealing (SA). SA shows better performance for shallow networks pushing more solid edge points to the lower left corner.
1.0
MNIST
Barrier [Our Model)
0.8
CIFAR1O
CIFAR100
0.6
0.4
MBF
0.2
VCG18
0.0
0.2
0.4
0.6
0.8
1.0
Barrier (Real World)
Figure 10: Aggregation of empirical evidence similarity of Real World and Our Model. aggregation of extensive empirical evidence (more than 3000 trained networks) one plot comparing barriers in real world against our model across different choices of architecture family, dataset, width, depth, and random seed.
Simulated Annealing performance. In this Section, we show that S and S' have similar loss barriers we change different architecture parameters such as as width, depth across various datasets. Here we consider the mean over all pair-wise barriers as barrier size. Figure showss the similarity of and before permutation. each plot, barrier size for S is similar to S Such similarity is also observed in Figure TT. where the barrier after permutation using SA.
14

---

Published as a conference paper at ICLR 2022
1.0
MLP
Shallow CNN
1.0
MLP
1.0
Shallow CNN
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
CIM03
0.2
0.2
40 Terezatie
0.2
0.2
Port widaia
0.0
1
Depth
Depth
Depth
Depth
Figure 12: Performance of Simulated Annealing (SA). Left: SA₂ where we average the weights of permuted models first and t is defined as the train error of the resulting average model. Right: Scarch space is reduced Le., we take two SGD solutions A and 92, permute 0i and report the barrier between permuted I1 and 02 as found by SA with n When search space reduced, SA able to find better permutations.
1.0
HLP
1.0
Shallow CNN
1.0
MLP
1.0
Shall ov. CNN
0.8
0.5
0.5
0.8
0.6
0.5
0.5
0.5
0.4
0.4
Were
0.2
5Am
21
27
21
2'
27
2'
Witth
Width
Depth
Depth
Figure 11: Similar loss barrier between real world and our model after applying permutation. Effects of width and depth also holds in this setting. Compared to Figure 5 observe slight harrier reduction. Reducing search space helps SA to find better solutions (see section
Search space reduction. In order reduce the search space, here we only take two SGD solutions 81 and fg permute 81 and report the barrier between permuted 0₃ and 6g as found by SA with n 2. Figure 13 and Figure show the effect of width and depth on barrier similarity between S and S' before and after permutation. Comparing Figure 13 and Figure 7 shows that SA succeeds in barrier removal. SA performance on and S' yields similar results for both before and after permutation scenarios. Such similar performance is observed along wide range of width and depth for both MIP and Shallow-CNN over different datasets (MNIST, SVHN CIFARIO. CIFAR100). We look into effects of changing model size in terms of width and depth in carlier sections, and note that similar trends hold for before and after permuting solution 0 Comparing Figure 13 and Figure shows that reducing the search space makes SA more successful in finding the permutation { } to remove the barriers. Specifically, SA can indeed find permutations across different networks and datasets that result in zero barrier when applied to 0,. SA can also find permutations that reduce the barrier for both MLP and Shallow-CNi across different width, depth and datasets. For example, such cases include MLP for MNIST. SVHN, CIFARIO, and CIFARI00 where depth is I and width is 2 and 24. MLP for MNIST where depth is 2 and width is 2dh Shallow-CN CNN for MNIST, SVHN, CIFARIO. CIFAR where depth is and width is 2 and for Shallow-CNN for MNIST where depth 2 and width is 26
Shallow
Shallow-CMM
0.8
0.0
0.8
0.5
0.5
0.6
0.5
0.5
Mode
0.4
G718393
0.0
0.5
Figure 13: Effect width and depth on barrier similarity between real world and our model before permutation. Search space is reduced here i.e., we take two SGD solutions 0; and 02, permute 0; and report the barrier between permuted 0 and 6g as found by SA with n = 2. Similarity of loss barrier between real world and our model is preserved across model type and dataset choices width and depth of the models increased.
15

---

Published as a conference paper at ICLR 2022
A.4 SIMULATED ANNEALING
We use Simannea python module for simulated annealing. The process involves:
Randomly move alter the state (generate a permutation)
Assess the energy of the new state (permuted model) using the objective function (Linear Mode Connectivity based on Equation
Compare the energy to the previous state and decide whether accept the new solution or reject it based on the current temperature.
For to be accepted, it must meet of two requirements:
The move causes decrease in state energy (i.e. an improvement the objective function)
The move increases the state energy (i.e. slightly worse solution) but is within the bounds of the temperature.
Temperature. In each step, the generated permutation is chosen with the probability of P gemparature, where cost is the barrier at a 1. In the first steps, as the temperature is high, there is high probability that the worse neighbor is also selected. The neighbor is another permutation that applied, differs slightly in the order the neurons/channels. As we move forward the temperature
-cost
decreases with T
Tmmnxatop and stick permutations that improve the barrier.
Scaling the computation for SA. In an experiment, we scale number of steps in simulated annealing investigate the effect of this hyper- parem-paramtter. If the barrier continues decrease the amount of computation increases and does not plateau, then this would suggest that with enough computation, the barrier found by simulated annealing could eventually go zero. Figure [4 shows that increasing number of steps exponentially, helps SA to find better solutions. Table 3 shows that as the number of steps increases (10x), A moves towards 2 i.e., 50% reduction in barrier (A means barrier does not plateau). Running SA for 50K steps takes 10K seconds on an nl at-annnd GCP machine (8 vCPU, 30 GB RAM) with 100 GPU. Due limited computational resources, we number of the steps to 50K.
MLP-MNIST
0.5
steps=10 10
0.4
steps= 100
steps=1K
0.3
steps=10K
steps=50K
0.2
0.1
0.0
23
25
27
29 Width
2 11
2
13
255
Figure 14: Scaling cost for Simulated Annealing, Increasing number of steps exponentially, helps SA to find better solutions. As the amount of computation increases the barrier continues to decrease.
16

---

Published as a conference paper at ICLR 2022
width=16
width=32
width=64
steps
barrier
barrier
steps
barrier
A barrier
steps
barrier
barrier
10
0,470
10
0,430
10
0.271
100
0.331
1.42x
100
0.302
1.43x
100
0.202
1.35x
1K
0.190
1.73
1K
0.175
1.71x
1K
0.121
1.41x
10K
0.105
1.80
10K
0.995
1.75x
10K
0.085
1.71x
50K
0.055
1.90
50K
0.055
1.80x
50K
0.048
1.77x
0.470
1.42
0.331
Table 2: Scaling cost for Simulated Annealing As the amount of computation increases the barrier continues to decrease. As the number of steps increases, increases toward and does not plateau.
The following code runs simulated annealing find the best permutation in Section 4.1
// Simulated innealing
from simanneal import Annealer
def barrier_SA(archs model, sd1, sd2, w2, init_state, tmax, tmin, steps, train_inputs, train_targets, train_avg_org har__aaa__rrr_modeeeee nchannels, nclasses, nunits): class patrriirraccclaaatooooooeeeeann
"*"annealer with a travelling salesman problem. def -sln, state):
super uuprr(BBrrieerlcccaiioooo..... self)._.iii___ (staestttte) impor
def move(self):
"""Swaps two cities in the route."" """
initial_energy self.energy() for j r5nge(5):
for i in self. self.state[]][i]
random. rondint len(x)
random. randint len(x)
[tlf.state[j](][a), self state[][[i][bbb]] self. stlf.st,te(j](()(bb,,
self self.state(j]lii[aa
return self self.energy() initial_energy
def energy(self)):
"""Calculates the cost for proposed permutation. -.. permuted_models []
for i in range
permuted_moded copeesss.ppennppeeuuttarrrrr model, self. state(i),, sd2[i], w2[i],
nchannels, nclasses, nunits))
**н# form one model which is the average of 5 permuted models permuted_avg copy. (mode))y(model)) new_params OrderedDict() for key sd2[o].keys()
param =
for i in
param param + permuted_models[ [
new_params(key] param [en modeeess__o
permuted_avg. load_stadee stautstttee__e sttesttttettttteeteeeeeettttettt dict(nea_paaams) eval_train evaluate_mooie sooeeee_oodellleeee (permuted_avg, train_inputs, train_targets) top1
cost eval_train return cost
bcp = Barriieraacuuaiiooooommiiiitttt
bcp_auto = ('tmax': tmax, 'tmin'; tmin, 'steps'; steps, 'updates': 1003
bcp. rete_scheuuleebcp_attce winning_state, bcp. an)eal() return winning_state
17

---

Published as a conference paper at ICLR 2022
B IMPROVE SEARCH ALGORITHM
In the main text we use simulated annealing (SA) to find the winning permutation л. Figure 6 shows that SA is only able to reduce the barrier, and reducing search space (n = 2) helps in finding better permutations. However, a critical question still remains: Is there an algorithm that finds better permutations?
He et al. 2018) proposed an algorithms that merges correlated, pre-trained deep neural networks for cross-model compression. Their objective is to zip two neural networks, optimized for two different tasks, into one network. The ultimate network does both tasks without losing too much accuracy on each task. Their algorithm is based on layer-wise neuron sharing, which uses f(weights, post activations) to find which neurons could be zipped together. They define the similarity (or equivalently difference) of two neurons as below (Eq. 12 in the original paper):
2 (w/ - ((H + (H "-- -w w(s))
(2)
We also used their "functional difference" as a measure for neuron matching between two randomly initialized trained networks. They used post activation as approximation for Hessian matrices.
Calculating the difference between each pair of neurons based on Equation [ gives an m X m matrix (m is width of the network). In the second step, neurons with minimum distance are matched together in greedy way ie., if 04,A and ngB8 have the minimum distance, row i and column j is removed from the distance matrix. Figure 15 shows that using functional difference, the barrier could be improved.
MLP
1.0
FD
MNIST
SA
SVHN
0.8
CIFAR1O
CIFAR100
Barrier
0.6
0.4
0.2
0.0
23
2
27
29
11
2
25
Width
Performance of Functional Difference compared Simulated Annealing. Functional Differ- ence could indeed find better permutations, improving the barrier size between two solutions.
Figure 15:
C MAKING ENSEMBLES
As stated before, our conjecture has implications for ensemble methods. If two solutions lie the periphery of a wide and flat low loss region (a basin where models are linearly connected to each other), then ensembling them in their weight space (averaging), creates a model tending to the center of the region, which leads to performance improvement. However, Simulated Annealing could not find the optimal permutations for all cases. Section B shows that using matching algorithms like functional difference could help to find better permutations. Motivated to create ensembles, WWotsman ctt al. (02II) start with two (or more) random initializations and learn a subspace (a line or simplex) connecting them. Throughout training they sample one (or more) points on this line and add the loss at this point to the loss of training. In order to enforce diversity in function space, they also add regularization term cosine similarity of two endpoints of the line. However they enforce two models to be in a line, the functional diversity of the final ensemble limited compare to our methods. Here we combine their method with functional difference make best of both worlds.
18

---

Published as a conference paper at ICLR 2022
In this experiment, train two randomly initialized networks separately, and then use functional difference to decrease the barrier between final solutions. Then we use learning subspace method to make them in one basin. Our results on MLP with one hidden layer and width of 1024 neurons MNIST and CIFAR 10 shows that this method outperforms the others.
Architecture
Width
Dataset
FD
SL²
FD + SL
MLP
1024
MNIST
96.85
97.63
98.22
MLP
1024
CIFARIO
52.95
57.89
58.94
Functional Difference (He al. 2018)
2 Subspace Learning (Worssman et al. 2021
Table 3: Performance comparison of ensemble methods. While functional difference (He et al. 2018) gives
better permutations compared simulated annealing, Subspace Leamning (Wortsman al. [022]] enforces solutions into one basin from scratch. We combine the best of two worlds FD SL. guarantce functional diversity of learned solutions and also make them in one basin.
D PROOF OF THEOREM 3.1
We first recap Theorem 3.1 below for convenience and then provide the proof
Theorem D.1 (.J). Let h be the number of hidden units, be the input size. Let the function fv,u(x) = vvl o (x) where o--) is ReLU activation, v E IR"h and U E Rgxx are parameters and x E Rd is the input. We show that if each element of U and U' is sampled uniformly from I1//Vd,1 1/v/ and each element of v and v' is sampled uniformly from [-1/Vh, 1/Vhi, then for any E Re such that |x|2 = dd, with probability 1 8 over U, U', v,v', there exist permutation such that
Sav+(I-o)y" J (x+
(x),
(1-a))v,, Ö(1==t)
where v" and U" are permuted versions v' and U
Proof. For any given E >> 0, we consider the set S5 (-1//
which has size <va For any Sç. let (U) be the set of indices of rows of U that are closest in Euclidean distance to s than any other element in Sg:
yds
C.(U)- {ils
arg min u, s' b1 s'ES
(3)
where for simplicity assume that arg min returns single element. We next the function C, to specify a permutation that allows each row in U' to be close to its corresponding row in U. For every s Se, consider random matching of elements in CU( and C.(U") and when the sizes don't match, add the extra items in U and U' to the sets and I' accordingly to deal with them later.
Since each element of U and U' is sampled uniformly from [-1/Vd, 1/Vdj, for each row in U and U'. the probability of being assigned to each s E Se is a multinomial distribution with equal probability for each Given any s E Sç. we can use Hoeffding's inequality to bound the size of (U)) with high probability. For any t 2 0:
P (ICC.U)) (h/1SED) 2t) < -2expp(-2f")
(4)
By union bound over all rows U and U" with probability 1 1-5, -5/3, we have that for every s Sg.
h
h
s (CC [8g
+
V/2 log(12) Scl/5)
(5)
For simplicity, we assume that is chosen that / d is multiple of
19

---

Published as a conference paper at ICLR 2022
Consider and I' which are the sets of indices that we throw out during the index assignment because of the size mismatch. Then, based on above inequality, we have that with probability 1 - 6/3,
I -= = E -C. s Sely log (1g(1 SESt
(6)
We next randomly match the indices in and 1. Let U" be the matrix after applying the permutation
to U' that corresponds to above matching of rows of U' to their corresponding row in U. Note that for any E [h] I, we have that u; u We next upper bound the left hand side of the inequality the theorem statement:
2 and for E I, we have//ur u ll" s 2/vd.
(art0--alw:.00000))uu afv.uxx)= (1 o))
(av + (1-a)"")) a)U*)x) av o(xx) (1- a)v" x(Ux
av
o(Ux)] +1- =(la))""a(uU++ (11- oUU"))]
$ av aoTio((aUt+ + x)) - o(Ux)]
a)1- [o((aU xx) o('
Since each element of v is sampled uniformly from 1-1/Vh, 1/Vh), for any R² we have that E|v r] = 0 and by Hoeffding's s inequality.
hht
P v I 22)
[
2eep
(8)
2/
Using the above argument, with probability - 5/33, we can bound the right hand side of inequality as follows:
av 110(aa+(111))")>>> - (UX))
+ +111 (1-a)v" [o((UU
(210g(12/0)
+ -1 (1--))0))x - o(Ux)112
(9)
h
2 212(/2 V)v
+ +1 (V-
|o((aU + a)U))x) o (U'x))l1
2 2log(12/0)
(aU (1-1)00)> Ux|12
(10)
h
2 2lg((12/0)
+ (1 V
|| (1 a)U')x - U"xl|2
2 2log(1200)
a)) U*) + (1 aav 2 212((12/8)
=o
|Ia(U (O)U-U")l]]
h
(12(12/0)
|| - U
(11)
2h
where the inequality i0 is due to Lipschitz property of ReLU activations. Now, all we need to do U"
to bound [|
J z Note that for any (i.j) [h] [d]. ui uli is an independent random
variable with mean zero and bounded magnitude(2/ if E and 2 otherwise). Therefore, we can again the Hoffding's inequality similar to inequality (8) for each row and after taking union
20

---

Published as a conference paper at ICLR 2022
bound, we have the following inequality with probability - -8/3.
Σ V 1e1
iu
u x
Σ
(u: )
kE(N]V
4 1oog (
||ا||| /
+ -h (1g(1/00))))
d
2 1og(122/8)) (11) +
Where the last inequality is using ||x|| - Vd. Substituting the above inequality into the right hand side of the inequality (TT), gives us the following upper bound on the left hand side of the inequality in the theorem statement:
/ew.t0-alwr/UU400a////6 afv.u(x)) - (1 a).vv
log(12/0)
[ U
(12)
2h
(17) + fdd
2 (12
(13)
Setting & =e
e/v /4d (og(110// log (2h/6),
gives the following bound on h:
1log(12/6) 12g(2//0011
h <
4log (12/8) log S2h/ log
22
Therefore, we have;
2
4
h <
4 4log (log(12/5) log(11/1)))))
d+2
(log(12/6) + dlog((/c))
2²
Using the above inequality, we have Ö(h - =ddts)
E ADDITIONAL PLOTS
E. BARRIER BEHAVIOR UNDER NOISY LABELS
Related works /hhan et al. 2017) show that neural nets can memorize random labels. In this section want to whether the barrier changes if one starts to inject random labels into the training dataset. Our results over different runs show that the barrier size behavior does not change, however including higher level of noise in labels lead small increase in barrier size.
21

---

Published as a conference paper at ICLR 2022
MLP-CIFARIO
MLP-CIFAR10
MLP-CIFAR1O
0.8
10a
0.6
109
0.6
Barrier
0.4
0.4
10-2
Nosy lab
0.2
0.2
No
Both Nowy labels
10
0.0
0.0
6085 No lobis
2'2'2'2'2"
2
2
27
2
2
2
2
Width
Width
dthh
Figure 16: Effect of label noise barrier size. Left: Train and Test Loss under different label noise. Middle: Train and Test Error under differentt label noise. Right: Train barrier (accuracy) under different label noise. Our results over 5 different noise labels lead to small increase in barrier size.
show that the barrier size hehavior does not change, however including higher level
E.2 BARRIER: VGG AND RESNET
Figure 17 shows the barrier similarity for VGG and ResNet families between real world and our model. The left two panels shows the effect of width, while the right two panels illustrate the depth. As discussed in section 2 the barrier for VGGs and ResNets, for both real world and our model, is saturated at a high value and does not change.
1.0
VEG16
ResNet18
1.0
VGG
1.0
ResNet
0.8
0.3
0.2
0.8
0.6
0.6
MM67
M1ST
MMET
RVGT
0.2
Dur Riik
0.2
Mv3-
0.0
0.0
2
2
0.0
13
Word
0.0
Paal Wodd
CHARCE
Whdth
Width
Depth
Depth
Figure 17: Effect of width and depth on barrier similarity between real world and our model before permutation: VGG and ResNet families. The left two panels shows the effect of width, while the right two panels illustrate the depth. As discussed in section the barrier for VGGs and ResNets, for both real world and our model, is saturated at a high value and does not change.
E.3 SMALL NETWORKS
We consider MLPs with the same architecture starting from 100 different initializations and trained on the MNIST dataset. For each pair of the networks we calculate their loss barrier and plot the histogram the values. Next for each pair of the networks, we find the permutation that minimizes the barrier between them and plot the histogram for all the pairs. We do this investigation for different network sizes. The results are shown in Figure [ top row. Note that since we consider all possible pairs, the observed barrier values are not i.i.d. If instead we randomly divide the 100 trained networks into two sets and choose pairs that are made by picking one network from each set, we will have an i.i.d sampling strategy. We investigate the pairs of networks trained on MNIST and measure the value of the direct and indirect barriers between them. Indirect barrier between two networks A, is minimum over all possible intermediate points B of maximum of barrier between A, B and barrier between B, C, i.e.,
min BI=A
max ((A,, 0B), B(0g, Oc)).
The reason we look into this value is that if maximum between two barriers is small, it means that both barriers are small and therefore there exist an indirect path between and
E.4 Loss BARRIERS ON THE TEST SET
Width. We evaluate the impact of width on the test barrier size in Figure 19 In comparison to
Figure the the magnitude of test barriers are shifted lower values as the test accuracy is lower than
22

---

Published as a conference paper at ICLR 2022
3
4 hidden units
4 hidden units
probability
0.03
hidden units
8 hidden units
probability
hidden units
16 hidden units
0.02
32 hidden units
64 hidden units
0.01
0.00
20
40 barrier
60
80
10
20 barrier
30
x=y
x=y
indirect barrier
60
indirect barrier
4 hidden units
10
4 hidden units
hidden units
8 hidden units
40
20
0
0
0
20
40
60
80
0
10
20
30
direct barrier
direct barrier
Figure 18: Histogram of barrier values between pairs of 100 networks with the same architecture trained on MNIST starting from different initializations. We find permutation for each pair that minimizes the barrier. This is done for two layer MI.Ps and repeated for networks different sizes. Bottom row: Indirect barrier between two networks A,C is minmimum over all possible intermediate points B of maximum of harrier between A, B and barrier between B, C. Left: before the permutation; Right: after the permutation.
train accuracy. This effect is intensified for harder tasks such CIFAR100, The double descent phenomena is also observed here, especially for simpler tasks, egg. MNIST and SVHN.
1.0
MLP
Shallow CNN
VGG16
1.0
ResNet18
MNET
MIGT
0.8
tumu
0.4
0.1
0.2
0.2
02
CRANIO
0.2
Sysh
2
2
2'
2
21
2
20
2
21
2"
21 Width
2
2
0.0
wilth
Width
Witth
Figure 19: Effect of width on barrier size (Test). From left to right: one-layer MLP, two-layer Shallow- CNN, NGG-16, and ResNet-18 architectures and MNIST. CIFAR-10 10, SVHN, CIFAR- 100 datasets. When the task hard (CIFARIO, CIFAR100) the barrier shrinks. For simpler tasks and large width sizes also the barrier becomes small.
Depth. We evaluate the impact of depth on the test barrier size in Figure 20 For MLPs, we fixed the layer width 20 while adding identical layers shown along the x-axis. Similar to Figure 3 we observe a fast and significant barrier increase as more layers are added. In comparison to Figure the magnitude of test barriers shifted to lower values the test accuracy is lower than train accuracy.
E.5 SIMILARITY OF S AND S' ON THE TEST SET
We note SA success on test barrier removal by comparing Figure 21 and Figure 22 SA performance on S and S' yields similar results for both before and after permutation scenarios. Such similar performance is observed along wide range of width and depth for both MLP and Shallow-CN CCNN over different datasets(MNIST) SVHN, CIFAR1O, CIFAR100). We look into effects of changing
23

---

Published as a conference paper at ICLR 2022
1.0
MLP
Shallow CNN
VGG
1.0
ResNet
0.5
crasis
0.3
02
0.5
0.6
0.6
0.2-
0.2
(EA122
0.0
Desth 0.0 Depth 0.0
0.0
Depth
Dipth
Figure 20: Effecct of depth on barrier size (Test). From left right MLP, Shallow-CNN, VGG(LL,13.16.18)) and (es,ee((18,4,,00) architectures and MNIST, CIFAR-IO, SVHN, CIFAR- datasets. For MLP and Shallow- CNN, we fixed the layer width at 2 while adding identical layers as shown along the x- axis. Similar behavior is observed for fully-conman collected and CNN family, i.e. low barrier when number of layers are low while we observe fast and significant barrier increase more layers added. Increasing depth leads higher barrier values until it saturates (as seen for ResNet).
model size in terms of width and depth as in earlier Sections, and note that similar trends hold for before and after permuting solution 01.
Shallow
CNN
Out Pacel
MIST
Car Mode
MI5T
Oar PP-P
Our PEBi
C9NN10 CENIUB
0.6
0.6
0.5
0.5
0.4
0.4
0.4
0.4
0.2
0.2
C718230
OPAN330
Depth
Dosto
Figure 21: Effect of width and depth on barrier consistency between real world and our model before permutation (Test). Search space is reduced here i.e., we take two SGD solutions 01 and 02. permute 01 and report the harrier between permuted 01 and o2 found by SA with n = 2. Similarity of loss barrier between real world and our model preserved across model type and dataset choices as width and depth of the models are increased.
3.0
MLP
1.6
Shallow CNN
1.0
MLP
1.0
Shallow CNN
Our
Mode Mark
MEST
0.8
Real Dand
0.8
2041
Morks
Ward
0PN1120
076/041
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
5MN
0.2
5/H
0.0
0.0
2
2'
21
2
2
Width
Depth
Depth
Figure 22: Effeet of width and depth on barrier consistency between real world and our model after permutation (Test). We observe that reducing the search space makes SA more successful in finding the permutation (π) to remove the barriers. Specifically, SA could indeed find permutations across different networks and datasets that when applied where depth is I and width is larger than 2 MLP for MNIST where depth is and 4, and width is 2 Shallow- CNN for MNIST where depth is 2, Shallow-CNN for SVHN where depth is 2 and width is 2
result in almost zero test barrier e.g. MLP across MNIST dataset
24


Reviews:
[{"review_id": "_Cqbf71XPB", "reviewer": "Reviewer_D6tW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper makes a rigorous empirical study of their main claim across several datasets and many architectures. The barrier predictions of their model using SA are convincing. \n\nOne concern remains on the novelty of the conjecture. How do the authors compare their conjecture to the Theorem 4.2 of Simsek et. al., 2021 (https://arxiv.org/pdf/2105.12221.pdf)? It looks like this theorem has already proven the conjecture for two-layers networks for a special activation function and in an infinite data regime. ", "summary_of_the_paper": "The authors empirically study the linear mode connectivity property for four model types, their scalings, and four datasets. Their main contribution is a conjecture: 'all solutions can be linearly connected by permuting the hidden neurons of one of the solutions.'", "summary_of_the_review": "The authors study the effect of width, depth, skip connections on the barriers (via lines, i.e., LMC) after having rotating one of the solutions with a suitable permutation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VprnQ37AFMJ", "reviewer": "Reviewer_iy5q", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength\n\n- Understanding properties about the optimization landscape of neural networks is a central problem in deep learning. While there has been lots of theoretical studies, they typically apply only to particular styles of data models or rely on particular assumptions on the initialization. This paper instead directly studies properties of the optimization landscape through large-scale experiments. The findings are both interesting and novel.\n\n- The authors have stated a Conjecture that could potentially inspire future studies. This Conjecture is in line with existing results in the literature. A preliminary result in the large-width limit is provided to support the Conjecture.\n\n- The scale of the experiments is on a large range of datasets and models, with over 3,000 runs, giving validity to the supporting arguments.\n\n## Weakness\n\n- Based on Conjecture 1, one would expect the barrier to go to zero, provided with sufficient computation to find the “right” permutation to apply to the weight matrices. Figure 6 goes into supporting this Conjecture, by showing that Simulated Annealing helps reduce the barrier. However, the reduction in the barrier is marginal at best. Thus, I am not entirely convinced by the result of this experiment.\n    - Could the authors show a scaling cost as for whether the barrier would continue to decrease, provided more computation? For example, suppose the barrier continues to decrease as the amount of computation increases and does not plateau, then this would suggest that with enough computation, the barrier could eventually go to zero. The current result shown in Figure 6 looks marginally supportive at best.\n- Based on the nature of this paper, I think the discussions should be stated more concretely.\n    - For example, the authors state “Another area where our analysis is of importance is for ensembles and distributed training.” It’s unclear what this refers to.\n    - It’s also unclear when the authors state “whether there is a one-to-one mapping between lottery tickets and permutations. We believe our analysis laid the ground for investigating these important questions…”\n\n**Questions**\n- From the paper by Zhang et al. (ICLR’17), we know that neural nets can memorize random labels and regularization methods can help mitigate such memorization (Figure 2a) though not entirely. Would Conjecture 1 still be true if one takes into account the effect of regularization? For example, while the permutation invariance property holds for regularization methods such as weight decay, it does not hold for $\\ell_1$ penalty or data augmentation.\n- Additionally, it would be interesting to see whether the barrier changes if one starts to inject random labels into the training dataset, similar to Zhang et al.’s experiments.\n- I was also curious what the prediction performance of the linearly-interpolated model is. For example, it would be interesting to see a figure similar to Figure 2 but with the y-axis being the prediction accuracy.\n\n**References**\n- Understanding Deep Learning Requires Rethinking Generalization. Zhang, Bengio, Hardt, Recht, and Vinyals. ICLR’17.\n\n**Typos**\n- Extra space on page 2: “In Section 4”\n- Missing white space on page 8: “$\\Psi$ to”", "summary_of_the_paper": "This paper studies the optimization landscape of neural networks. In particular, this paper touches on the question of whether two local minima of the optimization landscape are connected by a “line” of linearly-interpolated neural networks. To probe this question, this paper evaluates the loss gap (so called “barrier”) between two local minima and their linear interpolation. The finding is that this barrier is non-zero. Next, the authors conjecture that if one takes into account permutation invariance of a local minimum, the barrier should be reduced to zero. To support this conjecture, the authors considered a simulated annealing algorithm to search for permutations of the weight matrices, to show that the barrier reduces after applying the simulated annealing algorithm", "summary_of_the_review": "This paper presents several interesting and novel ideas regarding the linear mode connectivity of the optimization landscape of neural networks. The findings are supported by extensive experiments. An interesting Conjecture is stated, which could be interesting for future studies. On the other hand, I think the writing of this paper could still be improved.\n\n**Update after rebuttal:** The rebuttal addressed my main concerns mentioned under the Main Review section; thus, I increased my score. I particularly appreciated the empirical strength and the insights of this paper.\n\nOn the other hand, I agree with other reviewers that the authors need to clearly state the version of the conjecture that is already proved in prior works.\n\nMy other remaining concern is about the loss function used in the proposed conjecture. As in the current form, the conjecture is stated for the minimizers of generic loss landscapes of neural networks. However, it doesn't explicitly clarify whether there are any regularization penalties (e.g., $\\ell_2$ or $\\ell_1$ loss of weight matrices) in the loss function, which I believe is used in the experiments (e.g., weight decay). I think this aspect needs to be stated more carefully.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "AiDwjEKlbHo", "reviewer": "Reviewer_vZXp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Strengths:\n- The experiments are fairly extensive covering several network architectures over MNIST, Cifar10, SVHN and Cifar100.\n- Though the computational burden of checking such a conjecture exhaustively is intractable, the authors use innovative approximations that might still be describing the real behavior.\n- Linear Mode Connectivity is currently of great interest to the community due to the Lottery ticket hypothesis and may hold key insights into the learning dynamics of SGD on overparameterized DNNs.\n\nConcerns/Comments:\n-  In Sec 2.2, and for most of the main paper, the authors restrict their attention to training loss barrier as the \"barrier to linear interpolation\". I understand that this is something that can be computed at train time, but isn't the claim of linear interpolation to do with the \"true\" landscape of the loss function? If so, I feel understanding the test loss barrier is more interesting. I'm happy to see that it has been discussed in the appendix, but I would like to see a more thorough treatment for it.\n- All the plots have a maximum barrier of $1.0$ even though I don't see any normalization in the computation of the barrier function. Is this just an artifact of the specifics of the problem? If there is no normalization, I find it hard to understand what value of barrier is large enough to be considered a refutation of linear interpolation.\n- The authors note that VGG and ResNet architectures have a high barrier at all widths. Is there any explanation for why this might hold? Does it imply that SGD somehow has different dynamics on feedforward networks when compared to ResNets? And if so, how does linear mode connectivity now interact with generalization? I understand that these are very hard questions, but I thought I'd ask more out of curiosity than a criticism of the work.\n- In footnote 2, it is mentioned that the experiments are conducted over $5$ pairs of solutions and that the barrier is reported at $\\alpha=1/2$. Is it ensured anywhere that the solutions in those $5$ pairs are reasonably far away from each other? Reporting the barrier at $\\alpha=1/2$ makes sense if the solutions were actually linearly connected, but would be unrepresentative if they were not. Something like a weighted average over the interval might make more sense to be sure of the findings.\n- In section 3.1, it is stated that \"In the case of permutations, all permutations are equally likely for SGD\". Is there a reference for this claim?\n- Section 3.3 has a typo \"Bellow => Below\"\n- I am a little unsatisfied with the theoretical result since it has nothing to do with SGD which is the main topic of study. Moreover, the fact that it holds for all $x \\in \\mathbb{R}^d$ shows that this is more to do with the concentration we get from the random initialization than the network. However, I appreciate that the authors sufficiently state the limitations of this result.\n- Sec 3.5 defines the \"Our model\" approach where the authors consider the set of all permutations as a proxy for the brute force search. While this is creative, I'm a little bit confused as to how to interpret the results. If the barriers were all non-existent up to permutations, then shouldn't the experiments on $S'$ show a lower barrier than the other experiments? I was under the impression that experiments in Figures 2 and 3 do not involve permutations.\n- The footnote 3 in Section 4 seems to be missing.", "summary_of_the_paper": "The paper makes a bold conjecture that all the solutions that SGD reaches on deep feedforward networks are linearly interpolatable if they are permuted correctly, and if the network is wide enough. They conduct fairly extensive experiments that are unable to refute this conjecture, but do not prove it with certainty. They prove a theorem that shows that such a result holds at random initialization for a fully connected 1-hidden layer ReLU.", "summary_of_the_review": "I think the paper is a fairly thorough empirical evaluation and makes some valuable findings. However, I find it lacking for (what even the authors consider) a \"bold\" conjecture. I am a little confused as to the exact message of some of the experiments, and therefore am on the fence when it comes to recommending acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9cdQKJ8WJ4", "reviewer": "Reviewer_EfdQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "If true, this conjecture would have significant implications for both our theoretical understanding of neural networks and our use of them in practice (e.g. ensembling). The challenge of course is finding evidence for it, given that optimizing permutations between large neural networks is computationally infeasible. I think the authors take a meaningful first step in showing that a simple simulated annealing algorithm is largely unsuccessful in finding winning permutations. However I wish they had explored this direction a little further - perhaps by using other heuristics to preliminarily sort the neurons (e.g. weight norms or activations on a set of test images), and then further refining the permutation from this starting point.\n\nAs a second idea, since the function implemented by a neural network is invariant to permutation of its hidden neurons, if the authors' conjecture is correct then for two SGD solutions NN1 and NN2 there exists a solution NN2' (a permutation of NN2) which implements the same function as NN2 but lies in the same basin as NN1. Rather than finding NN2' by identifying a winning permutation, could NN2' be found by fine-tuning NN1 to implement the same function as NN2? without leaving the low-loss basin?\n\nThe authors' approach of comparing the loss barriers between different SGD solutions to the loss barriers between permutations of the same solution is interesting, and the close match is certainly intriguing. But it is only a small step towards demonstrating that their conjecture holds. I was left wondering whether there are other measurable properties of pairs of neural networks (beyond loss barriers) which could provide further evidence for (or against) their claim. For instance, some recent works [1] have shown that ensembling networks which lie in different loss basins yields significantly better performance (diverse predictions etc) than ensembling networks which lie in the same loss basin. Could a property like this be used to distinguish the real-world setting $S$ from the authors' model $S'$?\n\nThe paper is well written and clearly organized. Experiments are well-motivated and carefully described. And I think the investigations of width, depth, task and architecture on loss barrier size are independently interesting.\n\n\n[1] Fort, Stanislav, Huiyi Hu, and Balaji Lakshminarayanan. \"Deep ensembles: A loss landscape perspective.\" arXiv preprint arXiv:1912.02757 (2019).\n", "summary_of_the_paper": "The authors present a bold and thought-provoking conjecture: neural networks trained with SGD converge to the same low-loss basin, up to permutations of their hidden neurons. They go on to provide some limited but intriguing evidence in support of this conjecture. First, they prove that it holds for sufficiently wide one-hidden-layer neural networks at random initialization. Second, they empirically show that the loss barriers between different SGD solutions are similar in magnitude to the loss barriers between different permutations of a single SGD solution, across a range of models, tasks, and hyperparameters (e.g. width, depth). The paper also includes a number of experiments investigating the effects of width, depth, task, and architecture on loss barrier size.", "summary_of_the_review": "Overall, I think the conjecture presented by the authors is highly interesting and it is the first time I have seen it in writing. While the authors' empirical and theoretical results fall far short of verifying their conjecture in realistic settings, I think they are sufficient to recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the linear mode connectivity of the loss landscape of neural networks, i.e. whether a convex combination of two parameters of local optima on the SGD paths has low loss values (i.e. low barrier) up to some permutations. To probe this question, this paper empirically studies the loss gap, named as “barrier”, between two local minima and their convex combinations or linear interpolation. Before permutations, such barriers are typically non-zero; yet, after taking into account of permutation invariance of models, such barriers could be reduced along to zero with the width increasing, a main conjecture formulated in the paper. To support this conjecture, the authors proposed a simulated annealing algorithm to search for such permutations, demonstrating that the barrier reduces after such permutations.

The reviewers unanimously accept the paper, if the authors make the proposed improvement in the final version. In particular, a reader points out a paper by Singh and Jaggi, 'Model Fusion via Optimal Transport', NeurIPS 2020, that supports the same conjecture with a constructive algorithm to find optimal permutations or matching using optimal transport. This should be included in the final version as the authors replied.
Decision: Accept (Poster)