When Are Solutions Connected in Deep Networks?
Authors: Quynh Nguyen
Pierre Bréchet
Marco Mondelli
Venue: NeurIPS 2021 Poster (2021)
Keywords: Theory of deep learning
mode connectivity

Abstract: The question of how and why the phenomenon of mode connectivity occurs in training deep neural networks has gained remarkable attention in the research community. From a theoretical perspective, two possible explanations have been proposed: (i) the loss function has connected sublevel sets, and (ii) the solutions found by stochastic gradient descent are dropout stable. While these explanations provide insights into the phenomenon, their assumptions are not always satisfied in practice. In particular, the first approach requires the network to have one layer with order of $N$ neurons ($N$ being the number of training samples), while the second one requires the loss to be almost invariant after removing half of the neurons at each layer (up to some rescaling of the remaining ones). In this work, we improve both conditions by exploiting the quality of the features at every intermediate layer together with a milder over-parameterization requirement. More specifically, we show that: (i) under generic assumptions on the features of intermediate layers, it suffices that the last two hidden layers have order of $\sqrt{N}$ neurons, and (ii) if subsets of features at each layer are linearly separable, then almost no over-parameterization is needed to show the connectivity. Our experiments confirm that the proposed condition ensures the connectivity of solutions found by stochastic gradient descent, even in settings where the previous requirements do not hold.

When Are Solutions Connected in Deep Networks?
Quynh Nguyen MPI-MIS, Germany quynh. mpg.anii..pp............. de
Pierre Bréchet
MPI-MIS, Germany
pierre brechetticc mpg
Marco Mondelli
IST Austria
mar www.mmoeeeeeii......mmmmmm
Abstract
The question of how and why the phenomenon of mode connectivity occurs in training deep neural networks has gained remarkable attention in the research community. From a theoretical perspective, two possible explanations have been proposed: (i) the loss function has connected sublevel sets, and (ii) the solutions found by stochastic gradient descent dropout stable. While these explanations provide insights into the phenomenon, their assumptions are not always satisfied practice. In partieular, the first approach requires the network have one layer with order of N neurons (N being the number of training samples), while the second requires the loss to be almost invariant after removing half of the neurons each layer (up to some rescaling of the remaining ones). In this work, we improve both conditions by exploiting the quality of the features every intermediate layer together with a milder over-paramin pverpparameteiizationn requirement. More specifically, we show that: (i) under generic assumptions on the features of intermediate layers, it suffices that the last hidden layers have order of /N neurons, and (ii) if subsets of features at each layer are linearly separable, then almost no over- parameterization is needed to show the connectivity. Our experiments confirm that the proposed condition ensures the connectivity of solutions found by stochastic gradient descent, even in settings where the previous requirements do not hold.
Introduction
The aim of this work to provide further theoretical insights into the mode connectivity phenomenon which has recently attracted some considerable attention from the research community (i.e. training a neural network via stochastic gradient descent (SGD) from different random initializations often leads to solutions that could be connected by a path of low loss) 2 I 15). Existing theoretical insights from optimization landscape analysis suggest that, for over parameterized networks, the loss function has connected sublevel sets, and hence the solutions found by SGD are also connected 332 37 43). However, in order for such a result to hold, the network needs to have one wide layer with least N neurons (N being the number of training samples) 33 This bound is also known to be tight for 2-layer networks. Here, we would like to understand the above phenomenon for deep and mildly prer-parameterized networks (i.e. we aim to prove weaker guarantees under milder conditions). The idea is that, even when the sublevel sets are disconnected, SGD may only concentrate in (large) region with connected minima, see e.g. Figure This leads the question that whether one can characterize the properties of the solutions found by SGD which capture the mode connectivity phenomenon, for mildly werrpaaameterized networks. Along this line, a recent work (24) proposed the so-called "dropout stability" condition, that is, removing half the neurons from every hidden layer leads to almost no change in the value of the loss. As shown in the prior
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Figure 1: A function with disconnected sublevel sets and two connected sets of minima.
works (also in our experiments in Section 6). this condition holds for very wide networks or when dropout is used as a regularizer during training, but it does not hold under other practical settings.
The aim of this work is to provide new characterization of SGD solutions which capture their connectivity property, and to improve the previous assumptions (width ((V). and dropout stability) for networks of practical sizes, learned without the support of dropout training. As remark, although our work is motivated by the original phenomenon concerning mainly the solutions found by SGD, all the theoretical results are still valid for other pairs of solutions in parameter space.
Main contributions. Our main Theorem 4. provides an upper bound of the loss along a path connecting two given solutions in parameter space. This bound is characterized by the loss of L. optimized and sparse subnetworks, I. being the network depth. These I. subnetworks connect subsets of at least half the neurons at each layer to the output (see Figure 2). and their weights can be optimized independently of the weights of the original network, which leads to a significant reduction of the loss. This is the key difference to the previously proposed dropout stability property [24]. Next, we specialize our theorem to different settings to demonstrate the improvement over prior works:
shows that our condition is provably milder than dropout stability [24). In fact, dropout stability implies that the loss does not change much when we remove least half of the neurons at each layer and rescale the remaining ones. Here, we allow to optimize again all the weights of the subnetworks connecting the subsets of features to the output.
Corollary 4.2
As the weights of the subnetworks can be optimized, we establish formal connection between mode connectivity and memorization capacity of neural nets. In particular, Corol- lary 4.3 proves that, if the last two hidden layers have ((vN) neurons, then under some additional mild conditions the features of intermediate layers, any two given solutions can be connected by a path of low loss. This improves the width condition of prior works from ((N) to (((N) at the cost of ensuring a weaker guarantee (i.e. the connectivity of sublevel sets proved in prior works implies the connectivity of any two pairs of solutions, but in this paper we only show the connectivity for certain pairs).
32 33
Corollary proves that, for a classification task, if subsets of features at each layer are linearly separable, then no over- parameterization is required to prove the connectivity.
The message of this paper is that, in order to ensure the connectivity, a smooth trade-off between feature quality and over- pwraperraettiizzaaionn suffices. The two extremes this trade-off are captured by Corollary 4.3 and 4.4 mentioned above. More generally, at each layer containing at least half the neurons. If the features indexed by Ij are good enough, in the sense that there exists small subnetwork & achieving small loss when trained on these features inputs, then all layers & > in the original network do not need to be larger than twice the widths of the subnet &,- Hence, the better the features at lower layers, the less over-parameterized the higher layers need to be.
pick subset I
Finally, our numerical results show that, if the learning task is sufficiently simple (c.g. MNIST) and the network is sufficiently over-paramenn wer-parameterized, then dropout stability holds and the SGD solutions can be connected as in [24] However, when the learning task is more difficult (e.g. CIFAR- 10), or for networks of moderate sizes, dropout stability does not hold and the path of 24 exhibits high loss. In this challenging setting, we are still able to find low-loss paths connecting the SGD solutions.
Proof techniques. We remark that, while previous work 32 33, 43 focused on the connectivity of all the sublevel sets (i.e. a property of the global landscape), here we are only interested in the connectivity of a particular subset of solutions, especially those that are discovered by SGD. This leads to several differences in the proofs. First, previous analysis relies on the fact that the first hidden layer has at least N + 1 neurons [33. and thus the training inputs can essentially be mapped to

---

00
0000
0
0000
0 0
0
O
(a) Original net 8'
(b) Subnet Eo
(c) Subnet Ç1
(d) Subnet &2
Figure 2: An illustration of the sub-networks appearing in our main Theorem 4.1 correspond to the subset Z in the theorem, and its cardinality sub-network & receives as inputs the blue neurons from layer I, and pass it through the red ones at the higher layers, all the way the output of the network. All the weights of the sub-networks (in green) can be re-optimized to minimize the upper bound in the theorem. This is shown via the infimum taken over & on the RHS of Equation
The blue neurons least half the layer width. Each
feature space where they become linearly independent. This property allows the network to realize arbitrary outputs at each layer, which leads to the connectivity of sublevel sets. This property is longer true for the networks considered here, where the layer widths are allowed to sublinear in N. Second, the analysis of sublevel sets often do not take into account the bias of SGD, whereas here we focus more on understanding the properties of these solutions which lead to their connectivity. More closely related is the work by (24), with which we provide detailed discussion in Section 4
2 Further Related Work
Theoretical research on the loss surface of neural networks can be divided into two main categories:
that studies the global optimality of local minima, e.g. 7 13 14 17
18 T9 22 25 27
28 29 30 34, 38 42 45 46
47 48 50 [1], and the other that studies landscape connectivity. This work falls into the latter category. Specifically, the works of I12 37 suggest that the loss function a two-layer network becomes more and more connected as the number of neurons increases. In 43 and [2], it is proved that networks with one sufficiently wide layer have no spurious valleys and connected sublevel sets, respectively. All these works require networks with at least one layer of
order N neurons, whereas Corollary 4.3 requires widths of order /N neurons. In [5], the authors study the connectivity of equivalent minima (i.e. representing the same network function) which arise by permuting neurons from the same layer. A similar property is investigated in (20 for all local minima lying a cell or activation region (i.e. those sharing the same activation patterns across all the hidden neurons and training samples). In contrast, here we consider more general setting: Theorem provides upper bounds on the loss when connecting two arbitrary points parameter space. In particular, these points need not be local minima, nor share the same activation patterns, or even represent the same function. This allows us to study the mode connectivity phenomenon of SGD solutions [24], which typically not captured by the previous assumptions. Other works discuss lower bounds on over-varanne pate-aaattttrizationnn to ensure the existence descent paths in shallow nets [39], the satisfiability of the dropout stability condition in the mean field regime 440.
Memorization capacity is an old and well-studied topic 4 Networks with ((N) parameters are known to memorize N arbitrary samples, and this type of results has been studied for variety of settings, see
44 44]. Nevertheless, how memorization capacity related the mode connectivity phenomenon remains unclear, especially in the absence of layer of width Q(N). Our work draws a formal connection between the two, which opens up new directions for future works.
3 6
16 31
Preliminaries
Given two nonnegative integers i.j. let [i.]] = fi....,) and [1] (1,2...., Given a set I, we denote by [Z] its cardinality, We consider an L-llaee neural network with weight matrices Wi R=-11xa for E [T... and bias vectors by E TR" for / E [T.-]]. Here, no is the input dimension, nz the output dimension, and Ø1,..., M1-1 the widths of all the hidden layers. Let be the set of all
the network parameters. Given an input I80,, the feature vector fi E 1. at layer is defined as

---

I; o(W? fi-1(0,0)) + bi), W7.
= 0, LE [L - 1|,
f)
(I)
= L,
where a : R + R is some activation function. Let Ω be the parameter space of the network. For a data distribution (ar, y) ~ DD the population loss T 92 + TR. is defined as
(0))
ED V (0z ()).)
(2)
where (.. y) is assumed to be convex with respect to the first argument. Typical examples of yp which satisfy this assumption include the standard square loss and cross-entropy loss. By letting D be the uniform distribution over a fixed set of N samples, the loss & reduces to the empirical loss.
In the following, we frequently encounter situations where we are given layer / [0, L 11. and we want to study a subnetwork from layer to the output layer L. The widths and the inputs to this subnet are defined as follows. Let Ip S [Pp) be subset of neurons at layer p. for p E [1, T. 1]. By convention, let Io- [no] Let fp.Z, R Pzpl be obtained from fp by taking the neurons indexed by
Ip. The layer widths of this subnet (associated to 1) are given by mi (1) [Zi], m -p Ipp for
p E [1 + 1, L - 1), and m = nLg. The associated weight matrices and bias vectors are {UA 1 1pttt1 and {up (1) 1 where U//) 12m"2 xm and Up (1) =R=!" Let & ((V)")/ ) (vp) )
see Figure 2 for an illustration. Given an input Rm, this subnetwork, the corresponding
output, denoted by h2(E,, 2) E I is recursively defined for p E [7, L] as
2, a hhp + 11p
p
2)(
(1)
[ + T. 1].
(3)
(U (E,,),
p= L.
4 Main Result: Statement and Discussion
We now state our main result, which is proved in Section 5
Theorem 4.1 Fix any 0g 01 Ω and any e 0. Then, there exists a continuous piecewise linear
(PWL) path 0: [0, 1] + Ω such that ((0) = 0o 0(1) = =0, and the following holds:
max (((()) max max (000), (E|U,1] ('E
min
max inf [ (h1 (Ei, JU., (0)=))))))))++++
1 m1 It- Sin
s.t. 12 " 11 "
where hr, (Er, fI.T, (0', x)) is the output of the subnetwork from layer to layer L as defined in (3) fed with input Ji,Z, (0', σ)), and & contains the parameters of this subnetwork.
We remark that the second maximum on the RHS of 4 is intended to be taken between the two components in the open bracket (i.e., ((6') and the min maxinf).
An illustration of the subnets & s appearing in the theorem can be found in Figure 2 In words, for layer/ 7 E [T. - 1.. we pick subset Z, containing at least half the hidden neurons in that layer. Then, the loss over the PWL path upper bounded by the loss at I. points that are formed by connecting the subset of features (indexed by IT) at layer to the output via the subnetwork defined in ( The key idea is that we can construct low-loss paths connecting these sparse points, and the subnetworks guarantee sufficient amount of sparsity: they have Zj| neurons at layer I, and np Ipp neurons at layer E [1++ + 1, - 1]. The additive factor e the RHS of 44) serves to deal with the case in which the inf is not attained (as for the cross-entropy loss). We note that Theorem 4.1 also holds for deep nets without biases, which can be proved by following the same argument as in Section 5
Equivalent formulation. Before discussing the implications of Theorem 4.1 we provide an equiva- lent way to write the "min max inf" on the RHS of (4). This characterization will be useful when evaluating numerically our bound in Section 6 First, note that the subnetwork & in (4) is fully
determined by I and the cardinalities of I[+1, , Ir To this end, let Ki = [T], / E [ - 1]. and
Q inf Ep (hL (Ct, Zi.z, (0', (x)) w)l,
LE [0,L- L - 1).
(5)

---

Then, clearly Qi is fully determined by the variables {0', It. Ki41...., 1 and thus it does not depend on the actual content of I for * L. Based on this observation, one can easily argue that
min 21 IL- 11 s.t. 1Z
max Qt = 16
min - SKa-iSnn- LE
max
min
Qt-
SKK
(6)
TT TT|-Ki
To see why (6) holds, we first write the minimum over the sets (Zihett- on the LHS as a minimum
over their cardinalities he followed by a minimum over all the possible choices of subsets with fixed cardinalities. From the above discussion, once Ki+1..... K are fixed, the quantity Q entirely independent of Za for all k + l. Thus, one can swap the maximum over I E [0, L 1J with
the minimum over the sets, and the result readily follows.
A condition milder than dropout stability. Theorem of [24] can be deduced as corollary of Theorem 4.1 stated for networks without biases. Let us first recall the definition of e-dropout stability from [24] We say that some point 0 1 is e-dropout stable if, for all / [T. - 1], there exists a subset of at most np/2] hidden neurons in each of the layers p E [t, T. - 1] with the following property: after rescaling the outputs of these hidden units by some factor and setting the outputs of
the remaining units to zero, we obtain a parameter or. such that ((0r,a) I (0) + e. The proof of the following corollary is postponed to Appendix AA.1
Corollary 4.2
Fix any og. 01 E Ω and any > 0. Assume that 0g and 01 are s-dropout stable. Then, there exists continuous PWLppath @: [0, 1] - Z such that 8(0) = 0, (1) 01, and it holds:
max & (0()) S max ($(0.), ((0))) + + [E|0,1]
We highlight that requiring dropout stability to ensure the connectivity of solutions is a much stronger assumption than what is needed in Theorem 4.1 In fact, in order have that the loss along the path connecting &o and 0₁ is s-close to the loss at the extremes, Theorem I of (24) requires that Og and 0 are s-dropout stable. On the contrary, our main result requires that, for O' (0o, 01).
inf Ep M (he (Ei, fu.z, (6', xx)), .y) E1
(8)
is no bigger than (8)). The key difference with respect 24 is that in 8 not restricted to rescaling the weights of the original network (as in the dropout stability assumption), but we are allowed to optimize the weights of the subnetwork. This makes significant difference in practical settings. In Section we provide examples of networks trained on MNIST and CIFAR- 10 such that dropout stability is not satisfied, but mild condition still holds. Thus, even if the path provided by 24 leads to a large loss, we are still able to connect the SGD solutions via low-loss path.
Connections with memorization capacity. The fact that we can choose arbitrary weights to ap- proach the inf (8) provides a link between the connectivity capacity of neural nets. Consider setting in which there are N data samples {(rr) y2)} Je[vv] and we wish to minimize the empirical training loss, i.c. D is the uniform distribution over these samples. By exploiting recent progress the finite-sample expressivity of neural networks 16 49), one deduces the corollary below, whose proof is deferred to Appendix A.2 We recall that a set of points {ax (di)se(M]
solutions and the memorization
in Idd is said be in generic position if any hyperplane in TRd contains at most d points.
Corollary 4.3 Fix any og 01 E Q and any > O, and let a be RELU, Let { Ys) ISEN be data samples, where Uj E 1-1,1 for j E [N] and the vectors { are distinct. Let D be the uniform distribution over these samples. For i E {0, 13, assume that there exist subsets of neurons (I, JEE[e-1] such that the following holds:
(AI) |2 BL and 4
nz-2
NN.
4n
(AI-b) For some E 2 0,
inf
Ed ED(W(W"
1,11 (0,, s ((.)) +E.
(9)
WEB
Xuz
(A2) [11)] = [[T PPL-21 and the feature vectors {f ff (0,, (0.. 2,)}sE[N] are in generic position.
2
5

---

(A3) For all I E [I. -33: 3) |//00 ny 1, and the feature vectors { U1,2, (0.: JEN are distinct.
Then, there exists a continuous PWL path 0: [0, 1] + S.t. 8(0) = 0b, (11 = 81, and it holds:
max +(((t)) - max (I(66), Φ(01)) + + te(0.1]
(10)
This result should be regarded as a proof of concept. Improved bounds on memorization capacity would immediately lead to stronger results about connectivity. Let us now discuss in more detail the assumptions needed in Corollary 4.3 Assumption (A2) ensures sufficient "diversity" among the features at the second last hidden layer: the vectors { (0,,4y))eEM need to be in
generic position, which is rather standard in the literature about the memorization capacity of neural networks, e.g. 44_ Assumption (A3) requires a minimal condition that the feature vectors (f,z0000 x2) [5)]) are distinct for 1 E [L- - 3]. Assumption (A1-b) involves the quality of the
neurons and picking suitable new outcoming weights for the remaining ones, we do not increase the loss by more than e. Assumption (A1) involves the over- neer-paramttrizationn of the last two hidden layers of the network:
features at the last hidden layer: it requires that, by removing 7 - -Z
it requires that n assume that n, is a constant independent of N. Then, assumption (A1-b) holds if the loss remains stable after removing a d-fraction of the neurons, and assumption (A1) holds if 7 = (2NN). We remark that there is no requirement on the widths of the remaining layers.
1 |} is at least roughly 8NN... Pick 1/ = (1 - d)nL-1 and
is shown in 33 that, for deep nets, if the first hidden layer has N + neurons then one gets connected sublevel sets. This bound is tight sublevel sets. Here, we use properties of the features of the solutions we wish to connect in order to relax the requirement on the over-paramettrizzaion.. In particular, if the features the last two hidden layers are good enough (i.e. removing a s small number of neurons at layer I, - does not increase the loss much, and a subset of features at layer L - 2 are in generic position), then ((VN) neurons in each of these two layers are sufficient to ensure the connectivity. More generally, the fact that we are free to choose the sizes of the sets ..,..., It.-1 in the RHS of 4 quality of the features at a given layer and the amount of vee-parameterrzation in the layers above it.
2-layer network of width N can have disconnected
allows one to trade-off between the
Linearly separable features. One extreme example of this trade-off is when the features are linearly separable (i.e. the features are highly representative of the labels). More formally, consider classification task where one is given the labels yJ E {0, 1 ) and the data samples are linearly separable. Recall that, a set of data samples ((r yj) je(r]] is called "linearly separable" if there exist nz hyperplanes, each separating the samples of one class from the other classes perfectly. Pick two points such that, by removing n, neurons per layer, their features remain linearly separable each layer. Then, these points can be connected by low-loss path (without any extra over-parameetrization requirement). This formalized in the following corollary, whose proof appears in Appendix A.3
Corollary 4.4 Fix any 0o, E Q and any > Assume that ni 2 2n for I E [L 1] and that there exists an interval [or s.t. is strictly monotonic on (o, Let N linearly separable data samples, where y3 E (0,1)at for j E [N]. Let 'D be the uniform distribution over these samples, and let y be the standard cross-entropy loss. Assume that, for i. E {0,1), there exists subsets )E] such that ni
be
2 I <I S 14 nn and the set of features { (f1220000, xz); ys JEIN is linearly separable, for all l [0, L0 1]. Then, there exists a continuous
PWL path 0 [0, 1] + Ω such that ((0)- 0o ((1) O2, and the following holds:
max 4 ((((t) < max ( (o))), (00))) +E. (E
(11)
We remark that the result of Corollary for any loss function whose infimum is when the input is linearly separable. Furthermore, the assumption on the activation function being monotonic in interval is very mild, and it serves to avoid degenerate cases (e.g. constant activation function).
4.4 is not restricted to the cross-entropy loss, but it holds
'E.g.. less parameters in the interpolating network less assumptions on the input data.

---

5 Proof of Theorem 4.1
In the following, the "incoming weights" of a neuron refer both the incoming weight vector and the bias of that neuron, and the "outcoming weights" of a neuron simply refer to its outcoming weight vector. We call neuron "inactive" if its incoming weights are zero, and we call neuron "pure zero" if both its incoming and outcoming weights are zero. Clearly, pure zero neuron is inactive. Whenever we say "set some parameter w from a to 6", we simply mean to change the current value of w from a to b by following a direct line segment: w(A) = (1 - A)a + Xb, where À E [0, 1]. First, we state and prove a useful claim. Then, we present the proof of Theorem 4.1
Claim 5.1 Consider two distinct hidden neurons and on the same layer, and assume that is pure zero neuron. Then, one can swap p and q by a continuous PWL path along which the network oulput is invariant.
Proof of Claim 5.1; Let Pm and Pour denote the incoming resp. outcoming weights of p. Similarly,
we denote by Gin and Jont the incoming and outcoming weights of q. We change p and continuously
by applying the following paths sequentially (after each step, we reset the value of p and q to the
ending point of the path): (i) (A) = (1 A)pmm + Agn. (ii) [Poul A), Jom (A)] = [Agous (1 g) and (ii)) Gin (A) = (1 2) For all these paths, goes from to 1. Note that path (i) does not change the network output, since the outcoming weights of p zero. At the end of the first path, p and q have the same incoming weights (i.e. they are identical neurons). Furthermore, path (ii) does not change the network output, since the total contribution of and to the next layer is constant along the path. Finally, also path (iii) does not change the network output, since the outcoming weights of q are at the end of path (ii). After performing these three steps, p and q are swapped, ie. q becomes pure zero while p has the original weights of q.
Fix the subsets (Z) HE(L-1j where Ii S [mi], [ 2 m²/2, and let Iạ be the complement of ZT We show that there is a continuous PWL path from Oo to some other point for which all the neurons in {Ii {Tr) are pure zero, and the loss along the path is at most
Proof of Theorem 4.1
max (o((0)) max 1E &
inf LVD (hr. (Et, JU.z (fo. x)) v)] +
(12)
To prove the claim, we start from Og and apply a sparsification procedure that makes the neurons in ... Ii become pure zero, one layer at time from layer L 1 down to layer 1. First, we construct path that makes the outcoming weights of the neurons in Iz-1 become zero by changing only the weights in the last layer. Note that & is convex in the weights of the last layer, hence 4 is also convex those weights. Therefore, the loss along this path is at most
max ((0o), inf ED(y (hr. (51-1, i (Oo, x)) w)] ) fL-1
Once the outcoming weights of a neuron are all zero, the incoming weights can also be set to zero without changing the loss. Thus, the neurons in Σz-1 can be made pure zero.
pure zero, and we want to make the neurons in Iı pure zero. It suffices to make all the connecionss between Z and 11+1 become zero, because the connections between I, and Z are already zero due to the inactivity of I4+1- To do this, one first observes that the pure-zero state of the neurons in [I ) separates the original network from layer I + 1 to layer L into two parallel subnetworks: one with neurons in {Ip) 1-11 and the other with pure zero neurons. Now, set the
Now, we assume via induction that we have already made all the neurons in
incoming weights of the neurons in (II.I...,, II-1) to the corresponding values given by the subnetwork E., where ç. satisfies the following
ED|y (hL (E., fi.I,(O,, x)) v)] < inf Ep / (fL (Ei, fi.z, (Co, x)) .v)l +
(13)
&
Note that subnetwork & which satisfies [13 always exists: if the infimum on the RHS of (13 is actually a minimum, then we can pick ç. to be one of the minimizers. Otherwise, there exists a E. whose loss approaches the infimum with arbitrarily small error. In the above step, only the incoming weights that are relevant to the subnetwork &. are reset, while the other ones are kept unchanged. In particular, this step does not affect the outputs of the neurons in the other subsets (I+1,..., II-II) } as well as the output of the network. Next, let set all the outcoming weights
7

---

in IL-1 to the corresponding value given by f.. and all the outcoming weights in Iy-1 1 to zero (in one step). By the convexity of v w.r.t. the output weights, we have that the loss along this path is upper bounded by the loss at the extremes of the path, which is in turn upper bounded by (12) Now, since the outcoming weights of 1 are zero, follows that the parallel subnetwork associated to (T++1....,Zz _ } does not contribute to the network output. Thus, we can change the incoming weights of all the neurons in this subnetwork to any arbitrary values without affecting the loss. Hence, we turn all these neurons into inactive and then pure zero, without changing the loss. As a result, all the inter-connections between Z and I will become zero, as wanted from above. At this point, note that the weights of the neurons in [I++1.... ................................ IL-1} are those of &. Thus, in order to finish the induction proof, we need to make them become pure zero again. This can be done by swapping, at Tpl. each layer p 11+1, L 1]. one pure zero neuron in Ip with one neuron in Ip. As Ipl oe this is always possible, and the network output is invariant by Claim
The sparsification procedure described above can be performed for any subsets {Ttheel--1 s.t. [Za] 2 21 for [ [L- Thus, we can take the minimum in (12) over such subsets. Let {Ii hel--1 be the optimal subsets for 0g- Let us apply the same sparsification procedure to 01. We can assume w.l.o.g. that the optimal subsets for 01 and fg are the same. In fact, if this is not the case, we use Claim and swap the pure zero neurons with other ones on the same layer in order to satisfy this property. At this point, both On and 0, have been sparsified, and they have the same set of pure zero neurons at each layer, indexed by {Ii |EE[--1)
Finally, we connect the sparsified versions of 6g and 0j. Let A be the subnetwork consisting of all the hidden neurons in {Ii leerr--j. and B the subnetwork consisting of all the remaining neurons. Both A and B share the same input and output layers as the original network. Note also that the hidden layers of B have larger widths than the corresponding layers of A. Since A and B are decoupled, one can turn one on and the other off by setting the appropriate output weights to zero, and then update the incoming weights of the other subnetwork to any desired value without affecting the loss. In this way, one can make all the incoming weights (restricted to each parallel subnetwork) of 8g equal to the corresponding values of 0, Finally, one uses the convexity of the loss Vi again equalize the output weights of both 0g and 0,. Hence, the loss incurred to connect the sparsified versions of Oo and 0, is no bigger than
maXg (%o.01) inf Ep M (h (Eo. fo(6', (f)) v)] +c.
&o
By taking the maximum of the loss along the paths considered in this proof, we get the bound (4
6 Numerical Experiments
We compare the losses along the path of Theorem 4. and the one in 24 which our theoretical analysis has improved upon. Implementation details and link to the code are given in Appendix C
Datasets and architectures. We consider MNIST (26 and CIFAR- 23 datasets. As a pre- processing stage, we perform scaling into [-1, 1] for MNIST, and data whitening for CIFAR-10. For MNIST, we consider a fully connected network (FCN) with 10 hidden layers (T. = 11), each of width 245. For CIFAR-10, of width 500, and (ii) the VGG-11 network [4]] All architectures have ReLU activations. We train each network by standard SGD with cross-entropy loss, batch size 100 and no explicit regularizers. All the networks are trained beyond the point where the dataset is perfectly separated, and no early stopping mechanism is used. For each trained network, we perform the following two experiments.
consider architectures: (i) FCN with 5 hidden layers (L = 6), each
Experiment (A): we evaluate the RHS of 4.. with Ø' being the trained model, by using the equivalent characterization 6 First, we fix the integers Ki [n//2]- Then, for each E [0, T. 1], we compute the quantity Qt, defined as:
Q min Qi
min inf Ep /V (he (Ei, fU. (6', x)) xx)x)))))) .v)].
(14)
md
Clm T-|-K
I.
Kr
We upper bound the inf in 14 by running an independent SGD routine, and upper bound the min there by sampling the subsets L uniformly at random for Ta 20 times and by picking the best training loss resulting from the inf. The resulting bounds on Q) are shown by the blue curves in
8

---

2.0
1.5
1.5
1.5
1.0
1.5
1.0
ref.
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0 4.5 5 6
9.
1
2
3
4
0 2 3 4 5 6 9:20
(0.00
15. 0)
130,
01
layer index
layer index
layer index
points
(a) FCN MNIST
(b) FCN CIFAR-10
(c) VGG CIFAR-I0
(d) Training loss on path
Figure 3: (a) (c)(c) Training loss for Experiments (A) and (B). The dotted green line is the originally
trained model 8', used as a reference. Mean and 95% confidence interval are shown for 10 different
trained networks in (a) (b) and for different #' in [c) The plot (d) shows the loss along the paths of Experiments (A) and (B) between a fixed pair of solutions for the FCN trained on CIFAR-10.
Figure Note that by taking the maximum of these values for ( E 0, L 11. one obtains upper bound on (6). which is exactly the min max inf term in Theorem 4.1 As Theorem 4.. requires at least two different points 0' to connect, in Figure 3 we run our experiments multiple times (i.e. by training multiple network 6' above), and we report the mean together with the 95% confidence interval. The performance of these original models 0 is shown by the horizontal dotted green line in Figure (used as a reference). As one can sec, the blue curve is always close to the reference curve, which means that our upper bound as given in Theorem 4.1 for connecting these 0' solutions is always close to their original training losses, and thus all these solutions are approximately connected.
Experiment (B): we test the dropout stability of the trained model as defined in (24] For each I E [L- I], we proceed as follows: (i) randomly remove half of the neurons at all layers p E [1, L I]. and (ii) optimize the scaling factor of the output of the remaining network by minimizing the training loss. This last optimization is performed in our experiments via the Scipy method minimize_ sccalaraaarreeeeeeeeeeeeeeerrlee
For each E [L- - 1]. this procedure (i.e. do (i), and then (ii)) is repeated TB = 200 times, and we pick the best result based on the training loss. We have chosen the value TB 200 by observing that, if we increase TB from 100 to 200, the change in the minimum loss is negligible. The results here are shown by the orange curves in Figure 3 One observes that dropout stability tends to be satisfied the layers near the output of the network, while dropping the neurons from the first few layers increases the loss significantly. This is consistent with the findings of [24), where it is reported that dropout stability does not hold for the first few layers of the VGG-11 architecture without dropout training. If one instead uses dropout during training, (44 show that the trained model satisfies the dropout stability property. In Experiment (A), we have shown that, even when dropout is not used as an explicit regularizer during training (and consequently dropout stability may not hold), we can still ensure the existence of low-loss connecting paths. This is because our bound in Theorem 4.1 allows the optimization of the weights of the subnetwork &,.
Figure 3(d) illustrates the paths between two SGD solutions obtained from Experiment (A) and (B) for the FCN with --=6 6 trained on CIFAR-10. While the path (A) constructed via Theorem 4.1 has loss close to zero (and close the loss of the reference model), the path of 24] experiences large loss. Additional results in Appendix [ show similar patterns for the test error (see Figure (6) and for
different dropout ratios (see Figures 7 8) Furthermore, the log-scale plot in Figure/5o0 Appendix B
allows one to zoom into the detailed difference between our bound and the reference.
In Figure 4 we perform Experiments (A)-(B) for an FCN with 2 hidden layers of equal width, trained on MNIST and CIFAR-10. Here, we vary the width, and report the maximum of the bounds over all the layers. As expected, the loss gets smaller width increases. However, the bound provided by Theorem 4.1 is close to already for networks of moderate sizes: about 200 neurons for MNIST, and 500 for CIFAR-10. These networks widths roughly correspond to vN, as predicted by Corollary 4.3 On the contrary, much larger widths are necessary for dropout stability to hold: 2000 neurons for MNIST, and for CIFAR- 10, networks with 3000 neurons are still quite far from being dropout stable.
Taking all these experimental results together, we have demonstrated that, for simple datasets (e.g. MNIST) and for large enough widths, dropout stability holds. However, for more difficult learning tasks (e.g. CIFAR-10), and for networks of moderate widths or larger depths, there is strong

---

1.5
ref.
0.15
1.0
1.5
1.0
0.5
0.5
0.5
0.0
100
200
300
1000 2000
3000
200
400
600
1000 2000
3000
width
width
wisth
width
(a) MNIST
(b) CIFAR-10
Figure 4: Training loss (maximum over all layers) for Experiments (A) and (B) for an FCN with two hidden layers of equal albeit varying widths. The dotted line is the originally trained model. Mean and 95% confidence interval are shown for 3 different solutions
evidence that dropout stability is not satisfied. Yet, our main theorem provides connecting paths with low loss, even when the over-parameterization of the trained networks moderate.
Concluding Remarks
We provide new characterization for SGD solutions (or generally, for any two points in parameter space) to be connected by low-loss paths. Numerical experiments demonstrate that the proposed sufficient condition is satisfied by trained networks, also in settings where the requirements of the previous works do not hold. Our results and analysis lead directly to the following open question: Is having (more than two) hidden layers with ((vN) neurons in general sufficient to guarantee the connectivity all the sublevel sets? Although width N is both necessary and sufficient for two-layer nets [33], our Corollary [4.3 hope that this bound may be not tight for deeper nets, and sublinear widths there might suffice. Answering this question would help better understand the role of depth on shaping the geometry of neural net loss function. It is also interesting to study: (i) Why does SGD converge solutions fulfilling the trade-off we describe here between feature quality and paeaaeterettriioionn? (ii) Does SGD provably converge to global optimum for such networks? This last question was studied, e.g.
IO 35 36 52 for regression tasks, but the current results still require at least one layer with ((N) neurons. The analysis here suggests that SGD may explore a hell-behaved region of the loss landscape even for networks with sublinear layer widths.
Acknowledgements
MM partially supported by the 2019 Lopez-Loreta Prize. QN and PB acknowledge support from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement no 757983).
References
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterizatio.. In International Conference on Machine Learning (ICML), pages 2019.
[2] Ivan Anokhin and Dmitry Yarotsky. Low-loss connection of weight vectors: distribution-base approaches. In International Conference Machine Learning (ICML), pages 335-344, 2020.
[3] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research (JMLR), 20(63): 2019.
[4] Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 4, 1988.
[5] Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise permutation saddles, connected by equal-loss valleys across the loss landscape, 2019. arXiv: 1907. 02911.
10

---

[6] Sébastien Bubeck. Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
[7] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 192-204, 2015.
[8] Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, (3):326-333) 1965.
[9] Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International Conference on Machine Learning (ICML), pages 1309-1388, 2018.
[10] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), pages 1675-1685, 2019.
[1]]
Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes. In Neural Information Processing Systems (NeurIPS), 2019.
[12] C. Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimiza- tion. In International Conference on Learning Representations (ICLR), 2017.
[13] Kenji Fukumizu and Shun-ichi Amari. Local minima and plateaus in hierarchical structures of multilayer perceptrons. Neural Networks, pages 317-327, 2000.
[14] Kenji Fukumizu, Shoichiro Yamaguchi, Yoh ichi Mototake, and Mirai Tanaka. Semi-flat minima and saddle points by embedding neural networks to overparameterization. In Neural Information Processing Systems (NeurIPS), 2019.
[15] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. In Neural Information Processing Systems (NeurIPS), pages 8789-8798, 2018.
[16] Rong Ge, Runzhe Wang, and Haoyu Zhao. Mildly overparametrized neural nets can memorize training data efficiently, 2019, arXiv: 11837.
[17] Micah Goldblum, Jonas Geiping, Avi Schwarzschild, Michael Moeller, and Tom Goldstein. Truth or backpropaganda? An empirical investigation of deep learning theory. In International Conference Learning Representations (ICLR), 2020.
[18] Benjamin Haeffele and Rene Vidal. Global optimality in neural network training. In Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[19] Moris Hardt and Tengyu Ma. Identity matters deep learning. In International Conference on Learning Representations (ICLR), 2017.
[20] Fengxiang He, Bohan Wang, and Dacheng Tao. Piecewise linear activations substantially shape the loss surfaces neural networks. In International Conference on Learning Representations (ICLR), 2020.
[21] Kenji Kawaguchi. Deep learning without poor local minima. In Neural Information Processing Systems (NIPS), 2016.
[22] Kenji Kawaguchi and Yoshua Bengio. Depth with nonlinearity creates no bad local minima in resnets. Neural Networks, pages 167-174, 2019.
[23] Alex Krizhevsky, Learning Multiple Layers of Features from Tiny Images. page 60.
[24] Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. In Neural Information Processing Systems (NeurIPS), pages 14601-14610, 2019.
11

---

[25] Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning (ICML), pages 2902-2907, 2018.
[26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Bradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 01-22277-2324 1998.
[27] Dawei Li, Tian Ding, and Ruoyu Sun. aver-parameterized deep neural networks have no strict local minima for any continuous activations, 2018. arXiv: 18039.109..
[28] Shiyu Liang, Ruoyu Sun, Jason D Lee, and Rayadurgam Srikant. Adding neuron can eliminate all bad local minima. In Neural Information Processing Systems (NeurIPS), pages 4350-43600 4360, 2018.
[29] Shiyu Liang, Ruoyu Sun, Yixuan Li, and Rayadurgam Srikant. Understanding the loss surface of neural networks for binary classification. In International Conference on Machine Learning (ICML), pages 2840-28440 2849, 2018.
[30] Haihao Lu and Kenji Kawaguchi. arXiv:1702.c 08580.
Depth
creates no bad local minima, 2017.
[31] Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. 2020. arXiv:2007.. 12826.
[32] Quynh Nguyen. On connected sublevel sets in deep learning. In International Conference Machine Learning (ICML). pages 4790 4790-4799, 2019.
[33] Quynh Nguyen. A note on connectivity of sublevel sets in deep learning, 2021. arXiv:2101 08576.
[34] Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In International Conference Machine Learning (ICML), pages 2603-2612, 2017.
[35] Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Neural Information Processing Systems (NeurIPS), 2020.
[36] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizztion. global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
[37] Itay Safran and Ohad Shamir. On the quality of the initial basin in overspecified neural networks. In International Conference on Machine Learning (ICML), pages 774-782, 2016.
[38] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer ReLU neural networks. In International Conference on Machine Learning (ICML), pages 4430-4438, 2018.
[39] Arsalan Sharifnassab, Saber Salehkaleybar, and S. Jamaloddin Golestani. Bounds on over- parameterization for guaranteed existence of descent paths in shallow relu networks. In Interna- tional Conference on Learning Representations (ICLR), 2019.
[40] Alexander Shevchenko and Marco Mondelli. Landscape connectivity and dropout stability of sgd solutions for over-parameterized neural networks. International Conference on Machine Learning (ICML), pages
2020.
[41] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations (ICLR), 2015.
[42] Daniel Soudry and Elad Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks, 2018. arXiv: 1i0i::170..0577
[43] Luca Venturi, Afonso Bandeira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1-34) 2019.
[44] Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal Mathematics of Data Science, 2(4):1004-1033, 2020.
12

---

[45] Chenwei Wu, Jiajun Luo, and Jason D. Lee. No spurious local minima in two hidden unit relu network. In International Conference on Learning Representations (ICLR) Workshop. 2018.
[46] Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1216-1224, 2017.
[47] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. International Conference on Learning Representations (ICLR), 2018.
[48] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference Learning Representations (ICLR), 2019.
[49] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks are powerful memorizers: tight analysis of memorization capacity. In Neural Information Processing Systems (NeurIPS), 2019.
[50] Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi- branch architectures areintrinsically less non-convex. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[51] Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and landscape properties. In International Conference on Learning Representations (ICLR), 2018.
[52] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes parameterized deep relu networks. Machine Learning, 109(3):467-492, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the open problems in Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not see direct paths to applications with negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All the assumptions are clearly stated in the statements of the various results.
(b) Did you include complete proofs of all theoretical results? [Yes] The proof of the main result (Theorem 4.1 provided in Section 5 The proofs of Corollary 4.3 and
are contained in Appendix A.1 A.2 and respectively.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] See the url in Appendix(C
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] Mean and 95% confidence intervals are shown for 10 different solutions 0' in Figures 3(a) 3(b) for 5 solutions in Figure 3(c) and for 3
solutions in Figure 4
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix C
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "nAWnxF_tZV", "reviewer": "Reviewer_Yt3T", "summary": "The paper introduces an upgrade of the existing research on the existence of low-loss paths connecting minima (or random points) on the loss surface of a neural network. The main idea is to bound the loss of the points along the path by the loss of the sparse subnetworks of the original network. The technique is demonstrated to be more widely applicable as compared to the existing dropout-stability technique. Moreover, the connection to memorization ability is shown with smaller requirements to the width of the layers, which is also demonstrated in the experiments (by the price of considering only SGD solutions and not the full parameter space). The theory gives an insight on the trade-off between quality of features and overparametrization of the layers.\nThe empirical evaluation demonstrates that the proposed approach can find connection path on each level and with significantly better approximation than the dropout stability technique. Also it requires less overparametrization for precise estimations.", "questions": "", "limitations": "", "rating": 7, "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 is clearly written and provides the proofs for all the presented results. Empirical evaluation demonstrates the validity of the proposed technique also showing the advantages compared to the current state-of-the-art.\n\nSome minor points can improve the understanding of the interesting details:\n- Clearer discussion on memorization, including the notion of memorization used and how it is connecting to the low-loss-paths\n- Clearer discussion on why only SGD solutions should be considered in the theory and what are the possible problems with it (will the parameter configurations built for the low-loss-path always an SGD solution for example?)\n\nPossibly there is a typo in eq.4 (second max in RHS)\n\nOverall, the theory is clear and well explained, the empirical results are good, so my suggestion would be to accept the paper for the conference.\n\n---\nI am satisfied with the rebuttal discussion and not changing my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors included a detailed discussion of limitations, all of which seem to be viable.\n\nAs a theoretical paper it does not have any direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "m1721dAByVC", "reviewer": "Reviewer_5bCi", "summary": "This paper studies the connectivity of two parameters such as two SGD solutions of the deep neural networks. The general result subsumes several conditions including dropout stability, memorization capacity, and linear separable features. In particular, the theory shows that the connectivity occurs when the last two layers have $\\Omega(\\sqrt{N})$ neuron. The theory is validated by numerical experiments. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Overall, I think the main message is interesting, and the presentation is clear. Since the main contribution claimed in this paper is on the milder overparametrization, the assumption (A1-b) on the feature quality deems further justifications. This assumption possibly implicitly put stringent requirements on the level of overparametrization of previous layers. The discussion might also help understand the difference between deep nets and two-layer nets where $\\Omega(N)$ neurons are necessary. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the paper. The potential negative societal impacts are not available, as this paper focuses on the mathematical theory for the solutions of deep networks. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "EMNkpRLYqq", "reviewer": "Reviewer_4Z11", "summary": "1. The authors prove a mild condition for mode connectivity for deep nets. The proof is a natural generalization of (Kuditipudi et al., 2019) and the condition required in this paper is provably weaker than the dropout stability. The authors also demonstrate in experiments that their condition can still hold when dropout stability fails.\n\n2. The author provides a nice conceptual connection between their results and the memorization capacity of neural nets. In detail, they show if the product of widths of the last two layers is $\\Omega(N)$, then solutions are connected via a low-loss path with minimal assumptions.", "questions": "", "limitations": "", "rating": 7, "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": "This paper made a nice observation that the proof technique in (Kuditipudi et al., 2019) could be generalized in the following sense: for a fixed subset of the neurons per layer, to find a low-loss path, one doesn't have to rescale the original weights. Instead, it's possible to optimize weights in all further layers, thus further reducing the loss. Despite the simplicity of the idea, this new construction actually gives paths of much lower cost, as demonstrated in Figure 2 and 3.\n\nThis paper is clearly written and I enjoyed reading this paper. The setting of the experiments is clearly stated and I checked the proof of the main theorem and it sounds correct to me. The topic of mode-connectivity in deep learning is closely related to the interest of Neurips community. As the authors remarked, the mystery of mode-connectivity is still unsolved because we don't know why SGD find networks satisfying the assumption or if this is in general true for deep nets. However, I think this paper makes a solid step towards understanding mode-connectivity. Thus I suggest accepting this paper.\n\nOther comments:\nI really appreciate the authors' effort in making Figure 1, which helps readers to understand the notation of subnetwork used in this paper. Similarly, I think the paper will benefit from making several graphical demonstrations for the proof sketch, e.g., the operations you take to move from the right to the right subfigure in Figure 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, in Sec 7.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0E04SqfJvbh", "reviewer": "Reviewer_S8SJ", "summary": "The authors propose a theoretical explanation to the mode connectivity phenomena observed in neural networks. Specifically, it is shown that any two points in parameter space may be connected by a piece-wise linear path of low loss.  Technically this is done by assuming that there exists a tradeoff between feature quality and over parameterization at every layer. The authors note that this tradeoff assumption is milder than the dropout stability assumption made in previous work. Given this assumption, the authors improve upon the conditions for the existence of level set connectivity by requiring that the last two hidden layers only contain O(\\sqrt{N}) neurons, instead of O(N).", "questions": "", "limitations": "", "rating": 6, "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": "I am mainly concerned with the actual significance of the results, and with the writing/presentation in general. \nAs with the results themselves, i am a bit unsure as to how significant the results really are, given the strong assumption on the quality/over parameterization tradeoff. Concretely, Theorem 4.1 is proven by constructing sub networks connecting a set of neurons from each layer, to the output. The bound in Theorem 4.1 therefore depends on the error that these subnetworks can achieve (Eq 8), which crucially depend on the quality of the set of features chosen. It is not clear to me how significant this bound is given this assumption. (this is also true for the dropout stability assumption in prior work).   It appears to me that the main novelty of the paper is by formalizing a stronger assumption (which is eq 8 needs to be small) than dropout stability (the validity of both is not clear), and using it to get stronger results. \n\nIn addition, i find it hard to judge the impact of this paper due to the lack of discussion on why the subject matter is of any relevance. Besides it being intellectually intriguing to some, what is the significance of the findings in this paper, practically or otherwise?  To be clear, i feel this is more of a presentation issue than anything, and could be cleared out by the authors with some additional discussion.\n\nSome additional comments:\n\n- The authors mention that \"This improvement comes at the cost of ensuring a weaker guarantee (connectivity of SGD solutions, as opposed to connectivity of all sublevel sets)\". Can the authors expand on this further, how are the results in the paper specifically relevant for solutions found by SGD? Is the intention that the connecting path is found by SGD? This is not clear from the draft.\n\n- While i appreciate figure 1 and the Proof techniques section, i feel that the readability of the proof of Theorem 4.1 could and should be improved. This is especially true since it is part of the main draft. For instance, i find it hard to parse the sentence \". Now, set the\nincoming weights of the neurons ....  to the corresponding values given by....\" right before Eq 13. This could be made much clearer by some additional figures similar to fig 1.\n\n----------Post Rebuttal\n\nThe authors have addressed my concerns to an adequate degree, hence i have updated my score accordingly and recommend acceptance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are addressed ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The primary contribution of this work is in proving results similar to existing ones (connectedness of solutions in neural network training landscapes), but under milder assumptions.  Reviewers generally agreed that while the work is incremental by nature, it is technically sound and of interest to the community.  The AC sides with this view and recommends acceptance.
Decision: Accept (Poster)