{'fraction_non_alphanumeric': 0.04040782355389097, 'fraction_numerical': 0.014044943820224719, 'mean_word_length': 3.832193846772572, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets

Mode connectivity is a surprising phenomenon in the loss landscape of deep nets. Optima -- at least those discovered by gradient-based optimization -- turn out to be connected by simple paths on which the loss function is almost constant. Often, these paths can be chosen to be piece-wise linear, with as few as two segments. We give mathematical explanations for this phenomenon, assuming generic properties (such as dropout stability and noise stability) of well-trained deep nets, which have previously been identified as part of understanding the generalization properties of deep nets. Our explanation holds for realistic multilayer nets, and experiments are presented to verify the theory.


Introduction
Efforts to understand how and why deep learning works have led to a focus on the optimization landscape of the training loss. Since optimization to near-zero training loss occurs for many choices of random initialization, it is clear that the landscape contains many global optima (or near-optima). However, the loss can become quite high when interpolating between found optima, suggesting that these optima occur at the bottom of "valleys" surrounded on all sides by high walls. Therefore the phenomenon of mode connectivity (Garipov et al., 2018;Draxler et al., 2018) came as a surprise: optima (at least the ones discovered by gradient-based optimization) are connected by simple paths in the parameter space, on which the loss function is almost constant. In other words, the optima are not walled off in separate valleys as hitherto believed. More surprisingly, the paths connecting discovered optima can be piece-wise linear with as few as two segments.
Mode connectivity begs for theoretical explanation. One paper (Freeman and Bruna, 2016) attempted such an explanation for 2-layer nets, even before the discovery of the phenomenon in multilayer nets. However, they require the width of the net to be exponential in some relevant parameters. Others (Venturi et al., 2018;Liang et al., 2018;Nguyen et al., 2018;Nguyen, 2019) require special structure in their networks where the number of neurons needs to be greater than the number of training data points. Thus it remains an open problem to explain mode connectivity even in the 2-layer case with realistic parameter settings, let alone for standard multilayer architectures.
At first sight, finding a mathematical explanation of the mode connectivity phenomenon for multilayer nets-e.g., for a 50-layer ResNet on ImageNet-appears very challenging. However, the glimmer of hope is that since the phenomenon exists for a variety of architectures and datasets, it must arise from some generic property of trained nets. The fact that the connecting paths between optima can have as few as two linear segments further bolsters this hope.
Strictly speaking, empirical findings such as in (Garipov et al., 2018;Draxler et al., 2018) do not show connectivity between all optima, but only for typical optima discovered by gradient-based optimization.
It seems an open question whether connectivity holds for all optima in overparametrized nets. Section 5 answers this question, via a simple example of an overparametrized two-layer net, not all of whose optima are connected via low-cost paths.
Thus to explain mode connectivity one must seek generic properties that hold for optima obtained via gradient-based optimization on realistic data. A body of work that could be a potential source of such generic properties is the ongoing effort to understand the generalization puzzle of over-parametrized nets-specifically, to understand the "true model capacity". For example, Morcos et al. (2018) note that networks that generalize are insensitive to linear restrictions in the parameter space. Arora et al. (2018) define a noise stability property of deep nets, whereby adding Gaussian noise to the output of a layer is found to have minimal effect on the vector computed at subsequent layers. Such properties seem to arise in a variety of architectures purely from gradient-based optimization, without any explicit noise-injection during training-though of course using small-batch gradient estimates is an implicit source of noise-injection. (Sometimes training also explicitly injects noise, e.g. dropout or batch-normalization, but that is not needed for noise stability to emerge.) Since resilience to perturbations arises in a variety of architectures, such resilience counts as a "generic" property for which it is natural to prove mode connectivity as a consequence. We carry this out in the current paper. Note that our goal here is not to explain every known detail of mode connectivity, but rather to give a plausible first-cut explanation.
First, in Section 3 we explain mode connectivity by assuming the network is trained via dropout. In fact, the desired property is weaker: so long as there exists even a single dropout pattern that keeps the training loss close to optimal on the two solutions, our proof constructs a piece-wise linear path between them. The number of linear segments grows linearly with the depth of the net.
Then, in Section 4 we make a stronger assumption of noise stability along the lines of Arora et al. (2018) and show that it implies mode connectivity using paths with 10 linear segments. While this assumption is strong, it appears to be close to what is satisfied in practice. (Of course, one could explicitly train deep nets to satisfy the needed noise stability assumption, and the theory applies directly to them.)

Related work
The landscape of the loss function for training neural networks has received a lot of attention. Dauphin et al. (2014); Choromanska et al. (2015) conjectured that local minima of multi-layer neural networks have similar loss function values, and proved the result in idealized settings. For linear networks, it is known (Kawaguchi, 2016) that all local minima are also globally optimal.
Several theoretical works have explored whether a neural network has spurious valleys (non-global minima that are surrounded by other points with higher loss). Freeman and Bruna (2016) showed that for a two-layer net, if it is sufficiently overparametrized then all the local minimizers are (approximately) connected. However, in order to guarantee a small loss along the path they need the number of neurons to be exponential in the number of input dimensions. Venturi et al. (2018) proved that if the number of neurons is larger than either the number of training samples or the intrinsic dimension (infinite for standard architectures), then the neural network cannot have spurious valleys. Liang et al. (2018) proved similar results for the binary classification setting. Nguyen et al. (2018); Nguyen (2019) relaxed the requirement on overparametrization, but still require the output layer to have more direct connections than the number of training samples.
Some other papers have studied the existence of spurious local minima. Yun et al. (2018) showed that in most cases neural networks have spurious local minima. Note that a local minimum need only have loss no larger than the points in its neighborhood, so a local minimum is not necessarily a spurious valley. Safran and Shamir (2018) found spurious local minima for simple two-layer neural networks under a Gaussian input distribution. These spurious local minima are indeed spurious valleys as they have positive definite Hessian.

Preliminaries
Notations For a vector v, we use v to denote its 2 norm. For a matrix A, we use A to denote its operator norm, and A F to denote its Frobenius norm. We use [n] to denote the set {1, 2, . . . , n}. We use I n to denote the identity matrix in R n×n . We use O(·), Ω(·) to hide constants and use O(·), Ω(·) to hide poly-logarithmic factors.
Neural network In most of the paper, we consider fully connected neural networks with ReLU activations. Note however that our results can also be extended to convolutional neural networks (in particular, see Remark 1 and the experiments in Section 6).
Suppose the network has d layers. Let the vector before activation at layer i be , where x d is just the output. For convenience, we also denote the input x as x 0 . Let A i be the weight matrix at i-th layer, so that we have let the width of the layer be h i . We use [A i ] j to denote the j-th column of A i . Let the maximum width of the hidden layers be h max := max{h 1 , h 2 , . . . , h d−1 } and the minimum width of the hidden layers be h min := min{h 1 , h 2 , . . . , h d−1 }.
We use Θ to denote the set of parameters of neural network, and in our specific model, Throughout the paper, we use f θ , θ ∈ Θ to denote the function that is computed by the neural network. For a data set (x, y) ∼ D, the loss is defined as where l is a loss function. The loss function l(y,ŷ) is convex in the second parameter. We omit the distribution D when it is clear from the context.
Mode connectivity and spurious valleys Fixing a neural network architecture, a data set D and a loss function, we say two sets of parameters/solutions θ A and θ B are -connected if there is a path π(t) : R → Θ that is continuous with respect to t and satisfies: 1. π(0) = θ A ; 2. π(1) = θ B and 3. for any t ∈ [0, 1], L(f π(t) ) ≤ max{L(f θ A ), L(f θ B )} + . If = 0, we omit and just say they are connected.
If all local minimizers are connected, then we say that the loss function has the mode connectivity property. However, as we later show in Section 5, this property is very strong and is not true even for overparametrized two-layer nets. Therefore we restrict our attention to classes of low-cost solutions that can be found by the gradient-based algorithms (in particular in Section 3 we focus on solutions that are dropout stable, and in Section 4 we focus on solutions that are noise stable). We say the loss function has -mode connectivity property with respect to a class of low-cost solutions C, if any two minimizers in C are -connected.
Mode connectivity is closely related to the notion of spurious valleys and connected sublevel sets (Venturi et al., 2018). If a loss function has all its sublevel sets ({θ : L(f θ ) ≤ λ}) connected, then it has the mode connectivity property. When the network only has the mode connectivity property with respect to a class of solutions C, as long as the class C contains a global minimizer, we know there are no spurious valleys in C.
However, we emphasize that neither mode connectivity or lack of spurious valleys implies any local search algorithm can efficiently find the global minimizer. These notions only suggest that it is unlikely for local search algorithms to get completely stuck.

Connectivity of dropout-stable optima
In this section we show that dropout stable solutions are connected. More concretely, we define a solution θ to be -dropout stable if we can remove a subset of half its neurons in each layer such that the loss remains steady.
Definition 1. (Dropout Stability) A solution θ is -dropout stable if for all i such that 1 ≤ i < d, there exists a subset of at most h j /2 hidden units in each of the layers j from i through d − 1 such that after rescaling the outputs of these hidden units (or equivalently, the corresponding rows and/or columns of the relevant weight matrices) by some factor r 1 and setting the outputs of the remaining units to zero, we obtain a parameter θ i such that L(f θi ) ≤ L(f θ ) + .
Intuitively, if a solution is -dropout stable then it is essentially only using half of the network's capacity. We show that such solutions are connected: Theorem 1. Let θ A and θ B be two -dropout stable solutions. Then there exists a path in parameter space π : [0, 1] → Θ between θ A and θ B such that L(f π(t) ) ≤ max{L(f θ A ), L(f θ B )} + for 0 ≤ t ≤ 1. In other words, letting C be the set of solutions that are -dropout stable, a ReLU network has the -mode connectivity property with respect to C.
Our path construction in Theorem 1 consists of two key steps. First we show that we can rescale at least half the hidden units in both θ A and θ B to zero via continuous paths of low loss, thus obtaining two parameters θ A 1 and θ B 1 satisfying the criteria in Definition 1.
Lemma 1. Let θ be an -dropout stable solution and let θ i be specified as in Definition 1 for 1 ≤ i < d.
Though naïvely one might expect to be able to directly connect the weights of θ and θ 1 via interpolation, such a path may incur high loss as the loss function is not convex over Θ. In our proof of Lemma 1, we rely on a much more careful construction. The construction uses two types of steps: (a) interpolate between two weights in the top layer (the loss is convex in the top layer weights); (b) if a set of neurons already have their output weights set to zero, then we can change their input weights arbitrarily. See Figure 1 for an example path for a 3-layer network. Here we have separated the weight matrices into equally sized blocks: The path consists of 6 steps alternating between type (a) and type (b). Note that for all the type (a) steps, we only update the top layer weights; for all the type (b) steps, we only change rows of a weight matrix (inputs to neurons) if the corresponding columns in the previous matrix (outputs of neurons) are already 0. In Section A we show how such a path can be generalized to any number of layers. We then show that we can permute the hidden units of θ A 1 such that its non-zero units do not intersect with those of θ B 1 , thus allowing us two interpolate between these two parameters. This is formalized in the following lemma and the proof is deferred to supplementary material.
Lemma 2. Let θ and θ be two solutions such that at least h i /2 of the units in the i th hidden layer have been set to zero in both. Then there exists a path in parameter space π : [0, 1] → Θ between θ and θ with 8 line segments such that L(f π(t) ) ≤ max{L(f θ ), L(f θ )}.
Theorem 1 follows immediately from Lemma 1 and Lemma 2, as one can first connect θ A to its dropout version θ A 1 using Lemma 1, then connect θ A 1 to dropout version θ B 1 of θ B using Lemma 2, and finally connect θ B 1 to θ B using Lemma 1 again. Finally, our results can be generalized to convolutional networks if we do channel-wise dropout (Tompson et al., 2015;Keshari et al., 2018).
Remark 1. For convolutional networks, a channel-wise dropout will randomly set entire channels to 0 and rescale the remaining channels using an appropriate factor. Theorem 1 can be extended to work with channel-wise dropout on convolutional networks. 1 Note our results will also work if r is allowed to vary for each layer. Figure 1: Example path, 6 line segments from a 3-layer network to its dropout version. Red denotes weights that have changed between steps while green denotes the zeroed weights that allow us to make these changes without affecting our output.

Connectivity via noise stability
In this section, we relate mode connectivity to another notion of robustness for neural networks-noise stability. It has been observed (Morcos et al., 2018) that neural networks often perform as well even if a small amount of noise is injected into the hidden layers. This was formalized in (Arora et al., 2018), where the authors showed that noise stable networks tend to generalize well. In this section we use a very similar notion of noise stability, and show that all noise stable solutions can be connected as long as the network is sufficiently overparametrized. We begin in Section 4.1 by restating the definitions of noise stability in (Arora et al., 2018) and also highlighting the key differences in our definitions. In Section 6 we verify these assumptions in practice. In Section 4.2, we first prove that noise stability implies dropout stability (meaning Theorem 1 applies) and then show that it is in fact possible to connect noise stable neural networks via even simpler paths than mere dropout stable networks.

Noise stability
First we introduce some additional notations and assumptions. In this section, we consider a finite and fixed training set S. For a network parameter θ, the empirical loss function is Here the loss function l(y,ŷ) is assumed to be β-Lipschitz inŷ: for anyŷ,ŷ ∈ R h d and any y ∈ R h d , we have |l(y,ŷ) − l(y,ŷ )| ≤ β ŷ −ŷ . Note that the standard cross entropy loss over the softmax function is √ 2-Lipschitz. For any two layers i ≤ j, let M i,j be the operator for the composition of these layers, such that Arora et al. (2018) used several quantities to define noise stability. We state the definitions of these quantities below.
Definition 2 (Noise Stability Quantities). Given a sample set S, the layer cushion of layer i is defined as Furthermore, for any layer i the minimal interlayer cushion is defined as 2 µ i→ = min i≤j≤d µ i,j .
The activation contraction c is defined as c = max x∈S, 1≤i≤d−1 Intuitively, these quantities measures the stability of the network's output to noise for both a single layer and across multiple layers. Note that the definition of the interlayer cushion is slightly different from the original definition in (Arora et al., 2018). Specifically, in the denominator of our definition of interlayer cushion, we replace the Frobenius norm of J i,j x i by its spectral norm. In the original definition, the interlayer With this new definition, the interlayer cushion need not depend on the layer width h i .
The final quantity of interest is interlayer smoothness, which measures how close the network's behavior is to its linear approximation under noise. Our focus here is on the noise generated by the dropout procedure (Algorithm 1). Let θ = {A 1 , A 2 , ..., A d } be weights of the original network, and let . . , A d } be the result of applying Algorithm 1 to weight matrices from layer 2 to layer i. 3 For any input x, letx i i (t) andx i i−1 (t) be the vector before activation at layer i using parameters Definition 3 (Interlayer Smoothness). Given the scenario above, define interlayer smoothness ρ to be the largest number such that with probability at least 1/2 over the randomness in Algorithm 1 for any two layers i, j satisfying for every 2 If the network is smooth (has Lipschitz gradient), then interlayer smoothness holds as long as Essentially the assumption here is that the network behaves smoothly in the random directions generated by randomly dropping out columns of the matrices.
Similar to (Arora et al., 2018), we have defined multiple quantities measuring the noise stability of a network. These quantities are in practice small constants as we verify experimentally in Section 6. Finally, we combine all these quantities to define a single overall measure of the noise stability of a network.
Definition 4 (Noise Stability). For a network θ with layer cushion µ i , minimal interlayer cushion µ i→ , activation contraction c and interlayer smoothness ρ, if the minimum width layer h min is at least Ω(1) wide, .
The smaller , the more robust the network. Note that the quantity is small as long as the hidden layer width h min is large compared to the noise stable parameters. Intuitively, we can think of as a single parameter that captures the noise stability of the network.

Noise stability implies dropout stability
We now show that noise stable local minimizers must also be dropout stable, from which it follows that noise stable local minimizers are connected. We first define the dropout procedure we will be using in Algorithm 1.
Bernoulli random variable which takes the value 0 with probability p and takes the value 1 1−p with probability (1 − p).
The main theorem that we prove in this section is: Theorem 2. Let θ A and θ B be two fully connected networks that are both -noise stable, there exists a path with 10 line segments in parameter space π : To prove the theorem, we will first show that the networks θ A and θ B are O( )-dropout stable. This is captured in the following main lemma: Lemma 3. Let θ be an -noise stable network, and let θ 1 be the network with weight matrices from layer 2 to layer d dropped out by Algorithm 1 with dropout probability For any 0 ≤ t ≤ 1, define the network on the segment from θ to θ 1 as θ t := θ + t(θ 1 − θ). Then, with probability at least 1/4 over the weights generated by Algorithm 1, The main difference between Lemma 3 and Lemma 1 is that we can now directly interpolate between the original network and its dropout version, which reduces the number of segments required. This is mainly because in the noise stable setting, we can prove that after dropping out the neurons, not only does the output remains stable but moreover every intermediate layer also remains stable.
From Lemma 3, the proof of Theorem 2 is very similar to the proof of Theorem 1. The detailed proof is given in Section B.
The additional power of Lemma 3 also allows us to consider a smaller dropout probability. The theorem below allows us to trade the dropout fraction with the energy barrier that we can prove-if the network is highly overparametrized, one can choose a small dropout probability p which allow the energy barrier to be smaller.
Theorem 3. Suppose there exists a network θ * with layer width h * i for each layer i that achieves loss L(f θ * ), and minimum hidden layer width h * min = Ω(1). Let θ A and θ B be two -noise stable networks. For any dropout probability 1.
then there exists a path with 13 line segments in parameter space π : [0, 1] → Θ between θ A and θ B such that Intuitively, we prove this theorem by connecting θ A and θ B via the neural network θ * with narrow hidden layers. The detailed proof is given in Section B.

Disconnected modes in two-layer nets
The mode connectivity property is not true for every neural network. Freeman and Bruna (2016)  to the overparametrized setting. In this section, we show that even if a neural network is overparametrized-in the sense that there exists a network of smaller width that can achieve optimal loss-there can still be two global minimizers that are not connected.
In particular, suppose we are training a two-layer ReLU student network with h hidden units to fit a dataset generated by a ground truth two-layer ReLU teacher network with h t hidden units such that the samples in the dataset are drawn from some input distribution and the labels computed via forward passes through the teacher network. The following theorem demonstrates that regardless of the degree to which the student network is overparametrized, we can always construct such a dataset for which global minima are not connected.
Theorem 4. For any width h and and convex loss function l : R × R → R such that l(y,ŷ) is minimized when y =ŷ, there exists a dataset generated by ground-truth teacher network with two hidden units (i.e. h t = 2) and one output unit such that global minimizers are not connected for a student network with h hidden units.
Our proof is based on an explicit construction. The detailed construction is given in Section C.

Experiments
We now demonstrate that our assumptions and theoretical findings accurately characterize mode connectivity in practical settings. In particular, we empirically validate our claims using standard convolutional architecturesfor which we treat individual filters as the hidden units and apply channel-wise dropout (see Remark 1)-trained on datasets such as CIFAR-10 and MNIST.
Training with dropout is not necessary for a network to be either dropout-stable or noise-stable. Recall that our definition of dropout-stability merely requires the existence of a particular sub-network with half the width of the original that achieves low loss. Moreover, as Theorem 3 suggests, if there exists a narrow network that achieves low loss, then we need only be able to drop out a number of filters equal to the width of the narrow network to connect local minima. First, we demonstrate in the left plot in Figure 2 on MNIST that 3-layer convolutional nets (not counting the output layer) with 32 3 × 3 filters in each layer tend to be fairly dropout stable-both in the original sense of Definition 1 and especially if we relax the definition to allow for wider subnetworks-despite the fact that no dropout was applied in training. For each trial, we randomly sampled 20 dropout networks with exactly 32(1 − p) non-zero filters in each layer and report the performance of the best one. In the center plot, we verify for p = 0.2 we can construct a linear path π(t) : R → Θ from our convolutional net to a dropout version of itself. Similar results were observed when varying p. Finally, in the right plot we demonstrate the existence of 3-layer convolutional nets just a few filters wide that are able to achieve low loss on MNIST. Taken together, these results indicate that our path construction in Theorem 3 performs well in practical settings. In particular, we can connect two convolutional nets trained on MNIST by way of first interpolating between the original nets and their dropped out versions with p = 0.2, and then connecting the dropped out versions by way of a narrow subnetwork with at most 32p non-zero filters. We also demonstrate that the VGG-11 (Simonyan and Zisserman, 2014) architecture trained with channelwise dropout (Tompson et al., 2015;Keshari et al., 2018) with p = 0.25 at the first three layers 5 and p = 0.5 at the others on CIFAR-10 converges to a noise stable minima-as measured by layer cushion, interlayer cushion, activation contraction and interlayer smoothness. The network under investigation achieves 95% training and 91% test accuracy with channel-wise dropout activated, in comparison to 99% training and 92% test accuracy with dropout turned off. Figure 3 plots the distribution of the noise stability parameters over different data points in the training set, from which we can see they behave nicely. Interestingly, we also discovered that networks trained without channel-wise dropout exhibit similarly nice behavior on all but the first few layers. Finally, in Figure 3, we demonstrate that the training loss and accuracy obtained via the path construction in Theorem 3 between two noise stable VGG-11 networks θ A and θ B remain fairly low and high respectively-particularly in comparison to directly interpolating between the two networks, which incurs loss as high as 2.34 and accuracy as low as 10%, as shown in Section D.

A Proofs for connectivity of dropout-stable optima
Proof of Lemma 1. Without loss of generality, suppose for each θ i that the subset of h i /2 non-zero hidden units in each layer are all indexed between 1 and h i /2 . For 1 < i < d, we can partition A i into quadrants such that A i = L i C i D i R i . (Here, L i ∈ R hi/2 × hi/2 . If h i is odd, when we write L i in the other quadrants we implicitly pad it with zeros in a consistent manner.) Similarly, we can partition A 1 such We will sometimes use the notation A i to refer to the value of A i at a given point on our path, while A θ i will always refer to the value of A i at θ. We now proceed to prove via induction the existence of a path from θ to θ i for all i whose loss is bounded by L(f θ ) + , from which the main result immediately follows.
Base case: from θ to θ d−1 As a base case of the induction, we need to construct a path from θ to θ d−1 , such that the loss is bounded by L(f θ ) + . First, note that setting a particular subset of columns (e.g. the right half of columns) in A i to zero is equivalent to setting the corresponding rows (e.g. the bottom half of rows) of A i−1 to zero. So from the fact that L(f θ d−1 ) ≤ L(f θ ) + it follows that we can equivalently replace A θ d with rL θ d 0 without increasing our loss by more than . In fact, because our loss function is convex over A d we can actually interpolate A d between A θ d and rL θ d 0 while keeping our loss below L(f θ ) + at every point along this subpath. Then, because R d = 0 we can modify both D d−1 and R d−1 any way we'd like without affecting the output of our network. In particular, we can interpolate A d−1 between A θ d−1 and From θ k to θ k−1 Suppose we have found a path from θ to θ k such that (1) , and (4) A θ k i = A θ i for i < k, such that the loss along the path is at most L(f θ ) + . Note that θ d−1 satisfies all these assumptions, including in particular (2) as there are of course no A i between A d−1 and A d . Now let us extend this path to θ k−1 .
First, because the rightmost columns of A i are zero for k < i ≤ d, we can modify the bottom rows of A i for k ≤ i < d without affecting the output of our network. In particular, we can set A k to L θ k C θ k rL θ k 0 , as well as A i to rL θ i 0 0 rL θ i for k < i < d. From the fact that the loss is convex over A d and that L(f θ k−1 ) < L(f θ ) + , it then follows that we can set A d to 0 rL θ d via interpolation while keeping our loss below L(f θ ) + . In particular, note that because the off-diagonal blocks of A i are zero for k < i < d, interpolating between the leftmost columns of A d being non-zero and the rightmost columns of A d being non-zero simply amounts to interpolating between the outputs of the two subnetworks comprised respectively of the first h i /2 and last h i /2 rows of A i for k ≤ i < d.
Once we have the leftmost columns of A d set to zero and A i in block-diagonal form for k < i < d, we can proceed to modify the top rows of A k however we'd like without affecting the output of our network.

Specifically, let us set
. We can then reset A d to rL θ d 0 via interpolation-this time without affecting our loss since the weights of our two subnetworks are equivalent-and afterwards set D k to zero and R i to zero for k ≤ i < d-again without affecting our loss since the rightmost columns of A d are now zero, meaning that the bottom rows of A i have no affect on our network's output.
Following these steps, we will have A i = rL θ i 0 0 0 for k ≤ i < d and A d = rL θ d 0 . And so we are now free to set the bottom rows of A k−1 to zero without affecting our loss, thus arriving at θ k−1 .
Lemma 4. Let θ be a parameter such that at least h i /2 of the units in each hidden layer have been set to zero. Then we can achieve an arbitrary permutation of the non-zero hidden units of θ via a path consisting of just 5 line segments such that our loss is constant along this path. Proof.
Note that when we refer to a unit j as "set to zero", we mean that both row j of A i and column j of A i+1 have been set to zero.
To permute the units of layer i, we can first simultaneously copy the non-zero rows of A i into a subset of the rows that have been set to zero. Specifically, for j ∈ [ h i /2 ] we can copy row j of A i into row π (j) via interpolation and without affecting our loss, due to the fact that column π (j) in A i+1 is set to zero. We can then set column j of A i+1 to zero while copying its value to column π (j), again via interpolation and without affecting our loss since rows j and π (j) of A i are now equivalent.
Following these first two steps, the first h i /2 columns of A i+1 will have been set to zero. Thus, for all j ∈ [ h i /2 ] such that π(j) ∈ [h i /2] we can copy row π (j) of A i into row π(j) without affecting our loss. We can then set column π (j) of A i+1 to zero while copying its value into column π(j) via interpolation and without affecting our loss since rows π (j) and π(j) of A i are now equivalent. Setting row π (j) to zero-again for all j ∈ [ h i /2 ] such that π(j) ∈ [h i /2]-completes the permutation for layer i.
Note that because we leave the output of layer i unchanged throughout the course of permuting the units of layer i, it follows that we can perform all swaps across all layers simultaneously. And so from the fact that permuting each layer can be done in 5 steps-each of which consists of a single line segment in parameter space-the main result immediately follows.
Proof of Lemma 2. Without loss of generality, suppose for θ that the subset of h i /2 non-zero hidden units in each layer i are all indexed between 0 and h i /2 . Note that when we refer to a unit as "set to zero", we mean that both the corresponding row of A i and column of A i+1 have been set to zero. Adopting our notation in Lemma 1, we can construct a path from θ to θ as follows.
First, from the fact that the second half of units in each hidden layer i have been set to zero in θ we have Similarly, half the rows of A θ 1 are zero, half the rows and columns of A θ i are zero for 1 < i < d, and half the columns of A θ d are zero. Note that the indices of the non-zero units in θ may intersect with those of the non-zero units in θ. For 1 ≤ i ≤ d, let B i denote the submatrix of A i corresponding to the non-zero rows and columns of A θ i . Because A θ i are block-diagonal for 1 < i < d and the rightmost columns of A θ d are zero, starting from θ we can modify the bottom rows of A i for 1 ≤ i < d any way we'd like without affecting our loss-as done in our path construction for Lemma 1. In particular, let us set Then, from the fact that our loss function is convex over A d it follows that we can set A d to 0 B θ d via interpolation while keeping our loss below max{L(f θ ), L(f θ )}. Finally, from the fact that the leftmost columns of A d are now zero and A i are still block-diagonal for 1 < i < d, it follows that we can set L i to zero for 1 ≤ i < d without affecting our loss-thus making A i equal to To complete our path from θ to θ we now simply need to permute the units of each hidden layer so as to return the elements of B θ i to their original positions in A i for each i. From Lemma 4 it follows that we can accomplish this permutation via 5 line segments in parameter space without affecting our loss. Combined with the previous steps above, we have constructed path from θ to θ consisting of a total of 8 line segments whose loss is bounded by max{L(f θ ), L(f θ )}. Proof of Theorem 1. First, from Lemma 1 we know we can construct paths from both θ A to θ A 1 and θ B to θ B 1 while keeping our loss below L(f θ A ) + and L(f θ B ) + respectively. From Lemma 2 we know that we can construct a path from θ A 1 to θ B 1 such that the loss along the path is bounded by max{L(f θ A 1 ), L(f θ B 1 )}. The main result then follows from the fact that L(f θ A 1 ) ≤ L(f θ A ) + and L(f θ B 1 ) ≤ L(f θ B ) + due to θ A and θ B both being -dropout stable.

B Proofs for connectivity via noise stability
In this section, we give detailed proofs showing that noise stability implies connectivity. In the following lemma, we first show that the network output is stable if we randomly dropout columns in a single layer using Algorithm 1.

Lemma 5. For any layer
, with probability at least 1 − δ, we have for any (U, x) ∈ G that Further assuming h min = Ω log(1/δ) p , we know with probability at least 1 − δ, no less than 2 3 p fraction of columns inÂ i are zero vectors. Intuitively, this lemma upper-bounds the change in the network output after dropping out a single layer.
In the lemma, we should think of x as the input to the current layer, A i as the layer matrix and U as the Jacobian of the network output with respect to the layer output. If the activation pattern does not change after the dropping out, UÂ i x is exactly the output of the dropped out network and U (Â i − A i )x is the change in the network output. Proof of Lemma 5. Fixing 2 ≤ i ≤ d and one pair (U, x) ∈ G, we show with probability at least 1 − δ m , Let U k be the k-th column of U . Then by definition ofÂ i in the algorithm, we know where δ j is an i.i.d. Bernoulli random variable which takes the value 0 with probability p and takes the value 1 1−p with probability (1 − p). Let [A i ] j be the j-th column of A i . Because p ≤ 3 4 , 1 1−p = O(1) (any p bounded away from 1 will work). Hence the norm for each individual term can be bounded as follows.
where (*) uses the assumption that at least 1/2. Taking another union, we know with probability at least 1/2 − δ, interlayer smoothness holds and inequality (1) holds for every 2 ≤ i ≤ d. Next, conditioning on the success of these two events, we will inductively prove for any 1 ≤ i ≤ d, for any i ≤ j ≤ d, For the base case i = 1, since we are not dropping out any weight matrix, the inequality is trivial. For any we prove the induction hypothesis holds for layer i.
For any i ≤ j ≤ d we have By the induction hypothesis, we know the second term can be bounded by (i − 1) x j /d. Therefore, in order to complete the induction step, it suffices to show that the first term is bounded by We can decompose the error into two terms: The first term of (2) can be bounded as follows: The second term of (2) can be bounded as: Both terms of (4) can be bounded using the interlayer smoothness condition. For the second term of (4), notice that A i φ(x i−1 ) =x i i−1 . Thus by the induction hypothesis, we know Now, by interlayer smoothness, where in (*) we use (5) and the assumption ρ ≥ 3d. For the first term of (4), we knowÂ i φ(x i−1 ) = x i i−1 + ∆ i φ(x i−1 ). Therefore by the induction hypothesis and (3) for i = j, Together, (7) and (6) show that (4) is ≤ 2 3d x j . Together with (3) we obtain from 2 that , completing the induction step. Conditioning on the success of interlayer smoothness and inequality (1), we've shown, for any i ≤ j ≤ d. Recall that with probability at least 1/2 − δ, interlayer smoothness holds and inequality (1) , we know with probability at least 1/2 − δ, Bounding f θ (x) − f θt (x) for any fixed t: The proof for a fixed network on the path is almost the same as the proof for the end point. Instead of consideringx j i , now we considerx j i (t), which is the vector before activation at layer j if the weights A 2 , . . . , A i are replaced by We can still use Lemma 5 to bound the noise produced by replacing the weight matrix at a single layer because Thus, we can still use the above induction proof to show that for any fixed 0 ≤ t ≤ 1, let = O Bounding f θ (x)−f θt (x) for every t: Finally, we show that f θ (x)−f θt (x) is bounded for every point on the path via an -net argument. Similar to previous steps, letting = O , we know that with probability at least 1/2 − δ, Next, we show that on the path, the network output is smooth in terms of the parameters. According to Algorithm 1, we know for any 2 For any t, t and any 2 ≤ i ≤ d, let θ i t,t be θ t with the weight matrix at every layer 2 ≤ j ≤ i replaced by (A j + t (Â j − A j )). For convenience, we also denote θ t as θ 1 t,t . Given τ < 1/2, for any τ ≤ t ≤ 1 − τ and for any −τ ≤ κ ≤ τ, we can bound f θt+κ (x) − f θt (x) as follows: The output of layer i − 1 is the same for the two networks, of norm ≤ x i−1 j=1 A j,t+κ . Hence the output of layer i differs by at most κ x Â i − A i i−1 j=1 A j,t+κ and the output differs by κ Aj , we know for any τ ≤ t ≤ 1 − τ and for any −τ ≤ α ≤ τ, There exists a set Q = {θ t } with size O(1/τ ) such that for any network on the path, the distance to the closest network in Q is no more than τ. If we can prove for any θ t ∈ Q, f θ (x) − f θt (x) ≤ /2, we immediately know for any network θ t on the path f θ (x) − f θ t (x) ≤ by inequality (8).

By a union bound over
, we know with probability for any θ t ∈ Q. Setting δ = 1/4, we know there exists such that with probability at least 1/4, for any x ∈ S and any 0 ≤ t ≤ 1. Since the loss function is β-Lipschitz, we further know that for any 0 ≤ t ≤ 1: Now, we are ready to prove the main theorem.
Theorem 2. Let θ A and θ B be two fully connected networks that are both -noise stable, there exists a path with 10 line segments in parameter space π : [0, 1] → Θ between θ A and θ B such that Proof of Theorem 2. Setting dropout probability p = 3/4, by Lemma 5 and Lemma 3, if h min = Ω (1), we know there exist θ A 1 and θ B 1 such that 1. in both networks, each weight matrix from layer 2 to layer d has at least half of columns as zero vectors; Since the dropout fraction in both θ A 1 and θ B 1 is at least half, we can connect θ A 1 and θ B 1 as we did in Lemma 2, while ensuring the loss doesn't exceed max{L(f θ A ), L(f θ B )} + O( ). Connecting θ A to θ A 1 and connecting θ B to θ B 1 each take one line segment. By the construction in Lemma 2, connecting two dropped-out networks θ A 1 and θ B 1 takes 8 line segments. Thus, overall the path between θ A and θ B contains 10 line segments.
Next, we show that if there exists a "narrow" neural network achiving small loss, we can get a lower energy barrier using a smaller dropout probability.
Theorem 3. Suppose there exists a network θ * with layer width h * i for each layer i that achieves loss L(f θ * ), and minimum hidden layer width h * min = Ω(1). Let θ A and θ B be two -noise stable networks. For any dropout probability 1.
then there exists a path with 13 line segments in parameter space π : [0, 1] → Θ between θ A and θ B such that By Lemma 5 and Lemma 3, there exist θ A 1 and θ B 1 such that 1. in both networks, each weight matrix from layer 2 to layer d has at least h * i columns set to zero; . From the fact that at least h * i units in layer i of both θ A 1 and θ B 1 have been set to zero for 1 ≤ i < dmeaning that the corresponding rows of A i and columns of A i+1 are zero-it follows from Lemma 2 that we can connect θ A 1 to an arbitrary permutation of θ * using 8 segments while keeping the loss on the path no more than max{L(f θ A 1 ), L(f θ * )}. By choosing this permutation so that the non-zero units of θ * do not intersect with those of θ B 1 , we can then connect θ * to θ B 1 using just 3 segments as done in the first step of our path construction in Lemma 2 seeing as there is no need to permute θ * a second time. Combining these paths together with the paths that interpolate between the original parameters θ A and θ B and their dropout versions θ A 1 and θ B 1 , we obtain a path in parameter space π : [0, 1] → Θ between θ A and θ B with 13 line segments such that L(f π(t) ) ≤ max{L(

C Proofs for disconnected modes in two-layer nets
Proof of Theorem 4. Define our loss over parameter space such that L(f θ ) = 1 n l(y i , f θ (x i )), where x i ∈ R h+2 is our i th data sample, y i ∈ R the associated label, and f θ (x i ) = w T φ(Ax i ) for θ = (w, A) ∈ R (h+2)×h × R h . We can represent the data samples as rows in a matrix X ∈ R n×(h+2) -with f i denoting the i th "feature" (i.e. column) of X-and the labels as elements of y ∈ R n×1 , as illustrated in Figure 4.
Choose k, l, m, n such that k < l < m < n where k > h, l − k > h, m − l > 2 and n − m > h. When i ≤ l, let When l < i ≤ m, let When i > m, let Finally, let y i = 1 when i ≤ l and 0 otherwise.    From the fact that φ(f 1 ) − φ(f 2 ) = h+2 j=3 φ(f j ) = y it follows that there exist networks with both two active hidden units and h active hidden units that achieve minimal loss, with the former corresponding to the ground truth teacher network which generated our dataset.
Note in particular that the output layer weight corresponding to φ(f 2 ) in the network with two active hidden units is negative, whereas in the network with h active hidden units the output layer weights are all positive. Thus, any path between the two networks must pass through a point in parameter space where at least one output layer weight is zero while the other h − 1 are positive. However, as shown in Lemma 6, there does not exist such a point in parameter space that achieves minimal loss. It follows that there exists a barrier in the loss landscape separating the original networks, both of which are global minima. Moreover, by adjusting k, l, and m we can somewhat arbitrarily raise or lower this barrier.
Lemma 6. There does not exist a set of h − 1 positive weights w i and vectors h i ∈ span X such that Proof. We can think of each h i as the output a particular hidden unit over all n samples in our dataset and w i as the output layer weight associated to this hidden unit. We then have h i = a i,j f j , where the coefficients a i,j are elements of A.
First, if there did exist w i and h i such that h−1 i=1 w i φ(h i ) = y, then it must be the case for all i that h i = a i,j f j where a i,j ≥ 0 for all j. Otherwise, there would be non-zero elements in some h i between indexes l + 1 and n that would be impossible to eliminate in Second, any linear combination of f 1 and f 2 with positive coefficients would result in a vector whose first l elements are positive and increasing. In contrast, the first l elements of Y are constant. And so from the fact that there does not exist a i,j > 0 such that the first l elements of a i,j f j are decreasing-in particular because the first k elements and next l − k elements of h+2 j=3 a ij x j are periodic with length h-it follows that a i,1 , a i,2 = 0 for all h i .
Thus, we need only consider linear combinations of f 3 through f h+2 with positive coefficients as candidates for h i . To this end, note that if a particular f j has zero coefficient in all of h 1 through h h−1 , then will have zeros in every index congruent to j mod h and therefore cannot equal y. Hence by the pigeonhole principle, in order to have j=3 a i,j f j with at least two coefficients being non-zero. However, in any linear combination h+2 j=3 a i,j f j where a i,j , a i,j > 0 for at least two distinct j, j , the elements in indexes k + 1 to l will be greater than the elements in indexes 1 to k that are congruent to j mod h and j mod h. In contrast, the first l elements of y are constant. Hence, similar to the case of f 1 and f 2 , there cannot exist h i = h+2 j=3 a i,j f j and positive coefficients w i such that

D.1 Experimental details and hyperparameters
For all experiments on MNIST, we used a convolutional architecture consisting of 3 convolutional layers followed by a fully-connected output layer. Each convolutional layer consisted of 32 3 × 3 filters and used sufficient padding so as to keep the layer's output the same shape as its input. All networks were trained on an NVIDIA Tesla K20c GPU for 5000 iterations with a batch size of 64 using stochastic gradient descent with an initial learning rate of 0.1 and a decay rate of 1E −6 . No significant hyperparameter tuning was applied. Images were normalized.
For the left and right plots in Figure 2, we report results averaged over 5 random trials and error bars corresponding to the standard deviation over these trials. For the center plot we simply computed the loss and accuracy over a linear path between a particular convolutional net and a single dropout version of itself. Specific to Figure 2, in applying dropout with probability p we randomly sample a subset of 32(1 − p) units and rescale these units by 1/(1 − p) while setting the remaining units to zero. In the left plot, each trial consisted of sampling 20 such dropout networks and reporting the performance of the network achieving the lowest loss. Losses and accuracies in all plots were computed on a random batch of 4096 training images.
On CIFAR-10, we trained VGG-11 networks on an NVIDIA Titan X GPU for 300 epochs with SGD with a batch size of 128, with weight decay 5e-4, momentum 0.9, and an initial learning rate of 0.05 which is decayed by factor of 2 every 30 epochs. We used channel-wise dropout at all convolutional layers. The dropout rates are p = 0.25 at the first three layers and are p = 0.5 at the others. Ordinary dropout with p = 0.5 is used at every fully-connected layers except for the last one (the softmax layer).

D.2 Straight interpolation between two models
As demonstrated in Figure 5, a straight line interpolation between two noise stable model may incur large losses and poor accuracies. The models are the same as used in Figure 3.

E Tools
We use matrix concentration bounds to bound the noise produced by dropping out one single layer (Lemma 5).
As a corollary, we have: Lemma 8 (Bernstein Inequality: Vector Case). Consider a finite sequence {v k } of independent, random vectors with dimension d. Assume that each random vector satisfies v k − E[v k ] ≤ R almost surely. Define Then, for all t ≥ 0, Pr k (v k − E[v k ]) ≥ t ≤ (d + 1) · exp −t 2 /2 σ 2 + Rt/3 .