Spurious Local Minima Provably Exist for Deep Convolutional Neural Networks
Authors: Bo Liu
Keyi Fu
Tongtong Yuan
Venue: Submitted to ICLR 2023 (2023)
Keywords: theoretical issues in deep learning

Abstract: In this paper, we prove that a general family of spurious local minima exist in the loss landscape of deep convolutional neural networks with squared loss or cross-entropy loss.  For this purpose, we develop some new techniques to solve the challenges introduced by convolutional layers. We solve a combinatorial problem which considers the limited receptive fields of hidden neurons, and possible distinct activation status for different samples and different locations in feature maps, to show that a differentiation of data samples is always possible somewhere in feature maps. Training loss is then decreased by perturbation of network parameters that can affect different samples in different ways. Despite filters and biases are tied in each feature map, we give a construction in which this perturbation only affects the output of a single ReLU neuron and keeps the outputs at other locations unchanged. Finally, we give an example of nontrivial spurious local minimum in which different activation patterns of samples are explicitly constructed. Experimental results verify our theoretical findings. 

Under review as a conference paper at ICLR 2023
SPURIOUS LOCAL MINIMA PROVABLY EXIST FOR DEEP CONVOLUTIONAL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we prove that a general family of infinitely many spurious local minima exist in the loss landscape of deep convolutional neural networks with squared loss or cross-entropy loss. Our construction of spurious local minima is general and applies to practical dataset and CNNs containing two consecutive convolutional layers. We develop some new techniques to solve the challenges in construction caused by convolutional layers. We solve a combinatorial problem to show that differentiation of data samples is always possible somewhere in feature maps Empirical risk is then decreased by perturbation of network parameters that can affect different samples in different ways. Despite filters and biases are tied in each feature map, in our construction this perturbation only affects the output of single ReLU neuron. We also give example of nontrivial spurious local minimum in which different activation patterns of samples are explicitly constructed. Experimental results verify our theoretical findings.
INTRODUCTION
Convolutional neural networks (CNNs) (e.g. Lecun al. (1998); Krizhevsky et al. (2012); (Smonyyn & Zisseerman (2015;; Szegedy et al. 2015); He et al. (2016); Huang et al. (2017) ). one of the most important models in deep learning, have been successfully applied many domains. Spurious local minima, whose losses are greater than that of global minimum, play an important role in the training of deep CNNs and understanding of deep learning models. is widely believed that spurious local minima exist in the loss landscape of CNNs which is thought to be highly non-convex, as evidenced by some experimental studies (e.g. Dauphin et al. (2014); Goodfellow et al. (2015); [iao & Poggio
(2017); Freeman & Bruna (2017); Draxler et al. (2018): Garipov et al. (2018); Li et al. (2018);
Mchmeti- Goppll et al. (2021) l). However, the existence of spurious local minima for deep CNNs
caused by convolutions has never been proved mathematically before.
In this paper, we prove that infinite spurious local minima exist in the loss landscape of deep CNNs with squared loss cross- cross-entropy loss. This is in contrast to the "no spurious local minima" property of deep linear networks. The construction of spurious local minima in this paper is general and applies to practical dataset and CNNs containing two consecutive convolutional layers, which is satisfied by popular CNN architectures.
The idea is to construct local minimum 0 at first, and then construct another point 6' in parameter space which has the same empirical risk as 0 and there exist regions around 0' with less empirical risks. However, the construction of spurious local minima for CNNs faces some technical challenges, and the construction for fully connected deep networks cannot be directly extended to CNNs. Our main contribution in this paper
tackle these technical challenges. In the construction of spurious local minima for fully connected deep ReLU networks (He et al. [2200)] Ding et al.) (2019); (Glddblum jet al. 2020 Liu al. (2021)) ). in order to construct 6' and perturb around it, data samples are split into some groups according to the inputs of a specific ReLU neuron such that each group will behave differently under the perturbation of network parameters so as to produce a lower risk. This technique relies on data split and parameter perturbation, and cannot be directly applied to CNNs due to the following difficulties. Every neuron in CNN feature maps has limited receptive field that covers partial pixels in an input image (take image as example), and hence the inputs to ReLU neuron can be identical even for distinct samples, making them hard to distinguish. This data split issue is further complicated by the nonlinear ReL.U activations that truncate negative inputs, and the

---

Under review as a conference paper at ICLR 2023
activation status vary from place to place and from sample sample. Moreover, the filters and biases of CNNs are shared by all neurons in the same feature map, and thus adjusting the output of a ReLU neuron by perturbing these tied parameters will also affect other neurons in the same feature map.
We solve these challenges by developing some new techniques in this paper. By taking limited receptive fields and possible distinct activation status for different locations and samples into account, we solve a combinatorial problem to show that split of data samples is always possible somewhere in feature maps. We then present a construction of CNN parameters (0") that can be perturbed to achieve lower losses for general local minima 9. Despite the parameters are tied, our construction can perturb the outputs of samples at single neuron in feature maps without affecting other locations. We also give a concrete example of spurious local minima for CNNs. To our best knowledge, this the first work showing existence of spurious local minima in deep CNNs introduced by convolutional layers.
This paper is organized as follows. Section 1.1 is related work. Section 2 describes convolutional neural networks, and gives some notations used this paper. In section 3 our general results on spurious local minima are given with some discussions. In section we present an example of nontrivial spurious local minima for CNNs. 3 experimental results to verify our theoretical findings. Finally, conclusions are provided. More lemmas, experimental details and all proofs are given in appendices.
1.1
RELATED WORK
For some neural networks and learning models, it has been shown that there exist no spurious local minima. These models include deep linear networks (Baldi & Hornik 1989); Kawaguchi (2016);
Lu & Kawaguchi (2017); Laurent & von Brecht (2018); Yun al. (2018); Nouiched & Razaviyayn
(2018); Zhang 2019)), ), matrix completion and tensor decomposition (c.g.. Ge et al. (2016)), one-
hidden-layed networks with quadratic activation (Soltanolkotabi et al. (2019); Du & Lee (2018))
deep linear residual networks (Hardt & (2017) and deep quadratic networks (Kazemipour et al.
(2200).
Existence of spurious local minima for one-hidden-layer ReLU networks has been demonstrated, by constructing examples of networks and data samples, in Safran & Shamir (2018); [Swirs777 et al.
(2016); Zhou & Liang| (2018); Yun et al. (2019): Ding et al. (2019), Sharifnasaa et al. (2020) He
ct al. (020);; Goldblum et al. (2020)
etc.
2020); Ding al. (2019): Goldblum et al. 2020); Liu et al. (202T) showed that spurious local minima exist for fully connected deep neural networks with some general loss functions. For these spurious local minima, all ReLU neurons are active and deep neural networks are reduced to linear predictors. Spurious local minima for CNNs are not treated in these works. In comparison, we deal with spurious local minima for CNNs in this work, and the constructed spurious local minima can be nontrivial in which nonlinear predictors are generated and some ReL.U neurons are inactive.
For deep ReLU networks, He et al.
Du et al. 2018); Zhou et al. 2019); Brutzkus & Globerson (017) showed the existence of spurious local minima for one-hidden- layer CNNs with a single non-overlapping filter, Gaussian input and squared loss. In contrast, we discuss practical deep CNNs with multiple filters of overlapping receptive fields and arbitrary input, for both squared and cross-entropy loss. Given non-overlapping filter and Gaussian input, the population risk with squared loss function can be formulated analytically
with respect the single filter w, which facilitates the analysis of loss landscape. Thus, the techniques used in Du et al.) (2018) Zhou et al.) (2019): Brutzkus & Globerson (2017) cannot be extended to the general case of empirical risk with arbitrary input samples discussed this paper. Nguyen & Hein (2018) showed that sufficiently wide CNN (include a wide layer which has more neurons than the number of training samples followed by a fully connected layer) has a well-behaved loss surface with almost no bad local minima. Liu (2022) explored spurious local minima for CNNs introduced by fully connected layers. Du et al. (2119): Zhu et al.] (2019) explored the local convergence of gradient descent for sufficiently over-parameterized deep networks including CNNs.
2

---

Under review as a conference paper at ICLR 2023
2 PRELIMINARIES
2.1 NOTATIONS
We use M.. and (i.-) -) denote the ith row of matrix M, and use M and (-, i) denote the ith column of M. Mii and Mij are the (i.j) entry of M. The ith component of a vector is denoted as ot vf or v()). [N] is equivalent to {1, 2, ... .N. i j means i, + 1, :...-- v(i end) stands for the components of vector from the ith one the last one. In denotes vector of size whose components are all 1s.
2.2 CONVOLUTIONAL NEURAL NETWORKS
typical CNN includes some convolutional layers. pooling layers and fully connected layers. Because spurious local minima caused by fully connected layers in CNNs can be treated in the same way as in fully connected networks, we will focus on spurious local minima caused by convolutional layers.
Convolutional layers can take advantage of the translational invariance inherent in data, and are defined as follows. Suppose the /th layer is a convolutional layer, neighboring neurons at layer (1 - 1) grouped into patches for the convolution operation. Let Pt and st be, respectively, the number of patches and the size each patch in the Ith layer, and denote by Ti the number of convolutional filters (or the number of feature maps) in the /th layer. Denote {o} ............................... ,op,
RR as the set of patches in the lth layer. If there are multiple feature maps in layer (1 - 1). a patch will include corresponding neighboring ncurons from every feature map. The number of neurons in each feature map in the Ith layer is Pt-1- The number of neurons in the Ith layer is then nę T, P Given the pth (p (Pt-1) patch of o and the tth (t E (Ti)) filter w E R the output of corresponding neuron in layer 7 is given follows,
o' (h) a (w of-1 b)),
where h = 1)P-11 p. (x)) maz(0, x is the ReLU activation function. There is a single bias by for each feature map.
For ease of presentation, input feature maps are zero padded such that for each convolutional layer, the sizes of input and output feature maps are equal. The convolution operation can then be reformulated as matrix- vector product. We explain this by considering the following one-dimensional example. Given a one mne-dimensionll input o' (a, b, d, e) and filter W1 (wi wf. wi) "f""" the input becomes (0, a. b, d, e, 0)" after padding with zeros. Here, Ti = 1, S1-1 = 3. P1-1 = 5 after vero-padding, n4 TiP 1 5. The convolution operation equivalent
will assume that the strides for convolutions are equal to and the
?
w
w
w
wa
o' = σ
0
wi
w
w
dd
w
w1
One can set [w] 0, w 1, uf in 2 forward o'-1 unchanged (before adding bias and
ReL.U activation). This is equivalent to setting the weight matrix as a identity one. For the case of two-dimensional input, the input can be converted into vector and the convolution operation be reformulated as a matrix-vecti product using similar idea.
We will use matrix-ved vector product represent convolution operations. Denote the weight matrix and bias vector of the /th layer as Wi and b', respectively, with W E R and b' E R", then the output of the /th layer is o' aWWoo' + b'). This matrix-vector product formulation can also be used to represent fully connected layers.
We only consider average pooling layers. If layer / average pooling layer, each patch used in the pooling operation will include only the neighboring neurons within a single feature map in layer (I (1-1). 1). Let P/-1 be the number of patches in single feature map of the (1 1)th layer, and hence the size of each feature map in layer 1 is P1-1. For average pooling, the output of the pth neuron of (p) each feature map of layer is computed by
(p) mean (o, (1), ...
oop 1-1 ( p (P-1))
(3)
3

---

Under review as a conference paper at ICLR 2023
where (i) is the ith element in the pth patch of layer (1 1) within feature map. The average pooling operation is a linear operation and thus can can be represented by a matrix-vector product. The exact forms of parameter matrices for average pooling and fully connected operations will be given Appendix A in detail.
Consider a training set ((11))) y1), (x2, V2) ..... (XN, [XN.NN]] yN)),
where x; E R yy: E Rd (i E [N]) are, respectively, the input and target output. Let L be the number of layers in a CNN, and let a be the output of for the ith data sample (denote 0 : x;). The output vector of a CNN is
(N)
0 == o Who + b², i [N].
We introduce diagonal matrix 1 RR for each sample and each ReLU layer to represent the activation status of ReLU neurons, whose diagonal entries are 1 if - )o' + b/. and k otherwise. Consequently, the output of a convolutional layer can be written as . = 1 ow' 1. + b'). The CNN output can be written as
W 1y11 (w ... (W) x, + b') + + b 1'
(4)
The empirical risk (training loss) is defined as
N Σ (o),
R(W b', ... WT b²)
= N
(5)
1=1
where is the loss function, such as the widely used cross-entropy loss for classification problems. Our main goal in this paper is to construct spurious local minima for the empirical risk function of deep CNNs given in (5)
3 SPURIOUS LOCAL MINIMA
In this section, we first construct general local minimum with parameters := (W", b') Then, we present another point I' in parameter space which has an equal empirical risk with We further perturb 0' and show that empirical risk can be decreased. Therefore, 0 is spurious local minimum in parameter space.
Our construction is general and can be applied to CNNs with two consecutive convolutional layers, which is easily satisfied by most practical CNN models, such as AlexNet (Krizhevsky et al. (0012) 2012h)
VGG (Simonyan & Zisserman 2015 and GoogleNet (Szegedy et al. (2015).
3.1 CONSTRUCTION OF LOCAL MINIMA
We first give a general construction of nontrivial local minima. Given a local minimum for a subnetwork of CNN, show that it will induce local minimum of the whole CNN if the subnetwork is embedded into the CNN appropriately. Local minima for subnetworks of a CNN can be constructed using any method. Our construction of spurious local minima is general and does not rely on the concrete form of local minima for subnetworks. In section 4 construction of exemplar nontrivial local minima for subnetworks.
we will give an explicit
Our construction of spurious local minima is general and will utilize two consecutive convolutional layers, whereever there in the CNN. For ease of presentation, first we will assume that the last two hidden layers before the output layer (the Lth layer, which is fully connected) are two consecutive convolutional layers. The general case of having two consecutive convolutional layers in other places will be discussed in section 3
When layers L. - and I. - are two consecutive convolutional layers, we will fix the parameters of the last two convolutional layers in way such that the output L-33, is passed through layers I - 2 and L 1 unchanged. Two feature maps in layers L - 2 and the perturbation described later. Without loss of generality, let them be the first and second feature maps in these two layers, respectively. Fig T some associated parameters. Note that the size of a single output feature map in the /th layer is PI-1, and Pt.-2 = Pt-3 = Pt.-4 after padding. We have the following lemma to informally descibe the construction of local minima 0, and its formal version is given Lemma 6 in Appendix
1, respectively, are reserved for
()) shows the top layers of the CNN architeture with
4

---

Under review as a conference paper at ICLR 2023
(a) Top layers for local min- ima /
(b) Top layers for 0' (n z -b--3)
(c) Top layers for 0' (n <
-bf -l--
Figure 1: The top layers and associated parameters for constructing local minima and spurious local minima. In general, our construction can be applied to CNNs with two consecutive convolutional layers, like layers I. and I, this figure.
Lemma 1. (informal). Given CNN whose numbers of filters in the last two convolutional layers satisfy T 2 3, Ti-2 Z 3, the parameters W (-, 2Pr.2), W and WL-2 b of the last three layers are set to propagate o -.-3, unchanged to the output neurons, and the first and second feature maps in both layer L and layer
have no contributions to the final output.
The remaining parameters, including (- - 1 end), bf and (W*,b') I.-3 constitute subnetwork, and if they locally minimize the training loss when fixing other parameters, then point
b')
0 = (W',b') is a local minimum in parameter space.
In this lemma, 4 (-, 1: 2Pr-2) means the weights of connections from output neurons to the first two feature maps in layer 1 The identity forward propagations in layers L and L (see Fa)) can be implemented by setting corresponding submatrices in W and W L-2 to identity ones, which is equivalent to setting corresponding filters to the form (0, ...
0)² with single nonzero entry in the middle) as explained in section 2.2 and setting biases b b to
zeros.
The embedding scheme construct local minima or saddle points has also been used for fully connected networks by Fukumizu et al. (2019); Fukumizu & Amari (2000); ; He et al. (2020); Liu et al. 2021); p Zhang al. (2022). However, embedding for CNNs needs to tackle the problems of limited receptive fields, arbitrary activation status at different locations, and tied weights and biases.
3.2 CONSTRUCTION OF SPURIOUS LOCAL MINIMA
Our construction of spurious local minima relies the following assumption.
Assumption 1. At local minimum 0, the inputs to the final fully connected layer are distinct for different samples, i.e., Vi,j [N] and / j, ---11 o-11.j
For practical CNNs and datasets with rich contents, the number of neurons n41 input to the final fully connected layer is big and the chance of o (note that o--1,6 + 0 since 14-1,4 o 0 by the nondegenerate requirement in Lemma 6 the formal version of Lemma TT being identical for different samples is very small, thus Assumption I is reasonable and enforces very mild restriction on local minimum 0. This assumption is used to prevent distinct samples from becoming indistinguishable when passing through ReLU layers and being truncated by them. For fully connected deep neural networks, (He et al. (220)) Liu et al. (202T) assumed that all data points are distinct, ie.. Vi,j E [N] and J j, x; * Xj. Under this condition, we show in Lemma 7 in Appendix C that for practical datasets and CNNs there always exists local minimum 0 for which Assumption holds. An exception is the neural collapse phenomenon that during the terminal phase of training, the features of the final hidden layer tend to collapse to class feature means. As result, our construction of spurious local minima does not include those that may arise during the ending training phase when the loss is driving towards zero
5

---

Under review as a conference paper at ICLR 2023
3.2.1 DATA SPLIT
In the following, we will show that given Assumption I, there must exist least one location in feature maps where the outputs of all samples can be split into two parts using a threshold such that the two parts will behave differently under perturbations. This is not a easy task due to the following difficulties introduced by convolutional layers. Firstly, the receptive field of each neuron in a convolutional layer smaller than the input image, thus at each location in feature maps, the effective inputs (pixels in the receptive field) from distinct samples can be identical and indistinguishable. Secondly, the activation status of hidden ReLUU neurons can vary from place to place and from sample to sample. Assumption I will help us to distinguish different samples. Thirdly, the filters and biases are shared by all locations in a feature map, and one cannot perturb these parameters at a location without affecting other places.
We assume that training loss at satisfies R(0)= > O. By Lemma 8 given in Appendix C for training data that cannot be fit by linear models (also assumed by [He et al. (2020) Liu et al. (2021) and
popular CNN architectures, there always exists point 0 such that both Assumption 1 and 72(0) > 0
hold. Moreover, by Lemma [1 in Appendix EL for squared and cross-entropy loss function 1,
(((())))..) cannot equal to zero for all samples R(O) > O, where o (x,) is the output function of do input x; given by 4 Without loss of generality, assume u;
hxx().))x.) + 0 for some i E [NV] do(1)
where o11) is the first component of output vector o. By optimality of 0 = (W1, b') we have aR 86
N Σ
a(((x)))).)
1 Σ un 0.
Do(1) N
We will split the outputs of all samples at layer L- Given CNN parameters 0 = (W in and
data samples {x1, (x1,X,," X2,
xx). we consider the outputs و4-3,6 (j) (i E [N] E [M] in feature
maps of layer T--3. 3, where M is the number of neurons (locations) in all feature maps of layer T. - 3
used in Lemma For all j E [M]] e [N]. we denote
uf = w f-3 (i (i.)) 6,
w = W (1,2P1-++))
(6)
of is the output at layer 3 before adding bias and ReLU activation. Thus, at each location j E [M], there is a list (vf, u2y ... ). Let x be the vector composed of pixels of x, in the receptive field of the jth location. x can be identical for distinct samples, resulting in identical u/s. Identical u/s can also be resulted from ReLU activations that remove the difference between input samples.
In general, at each location j in the feature maps, (o/, vg. .... (xx) are organized in groups according to their magnitudes. Assume there are 9j groups in the list (u), "e. ug.... ... ,xx) Without loss of generality, we can re-index the samples in descending order of of and write the ordered list as of = ur = =... vd > u
....)))))))
#1++1= = ........ v > Um -1
Vma UN-
Li=1 U, = 0. In the following lemma, we show that there is at least one location where the split of data samples exists. This a combinatorial problem which needs to deal with multiple locations and multiple ordered groups at each location, and the groupings of samples can be arbitrary at each location.
Let u-u = (n,, U2, " and note that u + 0 and >
Lemma Assume that training loss R[(W', b))(2) > 0 for squared or cross-entropy loss. Under Assumption 1, there exist some locations j [M] where the ordered list of = ug = v 11+
...ut, 1 = ....unng
omn, = r'y can be splitted into two parts
{ 19, v2. , m/ and { (ubT vyy } by threshold n such that
1 ". ... wig > n, wet 2+2
UU 7. Σ u. + 0.
There may be more than one location where such data split exists, and we choose the one with the biggest threshold 17 for later usage. Let h be the location with the biggest split threshold, and without loss of generality, assume it is located in the first feature map of layer L - (that is why we put a special emphasis on the first and second feature maps in layers I, - 2 and L 1 in Lemma T and

---

Under review as a conference paper at ICLR 2023
Since 7 for the hth location is the biggest threshold among all locations j [M], by Σx=1 U4 7 0 are not satisfied at locations whose thresholds are less than 77, thus we have
Lemma 4
[M] j j h, Vj
Σ
U 0.
1E(1,2-,,
An Auxiliary Lemma At each location j E [M], samples are organized into groups according to of (i [N]). u/'s in each group are equal. Let 1/ be the set of indices of samples in the qth group of the jth location. We have the following lemma to show that Eiera 04 cannot equal to zero for all groups and all locations.
Lemma 3. Under Assumption 1. for CNNs with squared or cross-entrops loss, if R(((,, b))(=)
O, then there must exist some j E [M] and E [g;] such that Eier Us #
Lemma 3 will be used by Lemma to find data split that satisfies 7p. We will prove Lemma by induction. The number of groups 9j at each location and the value of u for each group can be arbitrary. We will prove that if SammaBholld for m samples, then for all possible configurations of current groups and all ways of adding new sample, it also holds for m + samples.
3.2.2 CONSTRUCTION OF
Given the CNN parameters 0 = (W b specified in Lemma 6 and the threshold vi in Lemma
2 we will give the point 0' : (W" b²) 1= in parameter space and show that training loss at 0' is equal to that at 0. We only change the parameters that are related with the first and second feature maps in layers L - 2 and L- 1, respectively, to obtain 0', and remaining parameters are fixed. The purpose of these parameter setting is to make R(Ø') R(Ø) and enable different behaviors under perturbation of parameters for different parts of samples. Different settings are designed depending illustrated in Fig b). and the setting for 1 < - is shown in Fig D c). The following lemma informally describe the parameter settings and its formal version is given in Lemma 9 in Appendix C
on whether 77 2 -b or not. The setting for the case of 17 2 -bf-3
Lemma 4. (informal). Given the CNN parameters 0 == (W b') specified in Lemma ! (formally Lemma Gin Appendix C.. let 6 == ==
(W", b²) 1-11 and set W " W and W 2,b
in way such that the value w (ov + +b--3)+ " bf (the original output of the first output neuron, contributed by location j in the first feature map of layer L- 3) is not changed for every location and each sample i E [N), no matter how big vi is relative to 1) and b/-3. There are three possible paths through which value aio + +b6--) can propagate, i.e., the paths that connect the first, second, and third feature maps, respectively, in layers L 2 and L - (see Fig If 2 -b4-3 a positive value of (v + bf-3) will pass through either the first or the second path. If < -b(-3, a positive value of (v + +b4-5) will pass through all three paths and the oulputs from the first and second paths counteract. The differentiation of paths will make it possible for different parts of samples to behave differently under perturbation of parameters. Remaining parameters in O keep fixed. Then, R(0') R(0).
3.2.3 PERTURBATION OF 8'
Next, we will show that by perturbing 0', we can decrease the training loss. We demand that only the final output contributed by location h in the first feature map of layer L 3, where vi, 122 ... , > 7) and Σ us * 0 happens, will be affected by the perturbation so as to decrease the training loss. The perturbation is then designed such that single bias in the path each of (with of > 7) passes through is perturbed. The final output is not affected by locations other than h even with of > 1 due to Ex U; = O. The following lemma informally describe our parameter perturbation scheme and its formal version is given in Lemma i0 Appendix C.
Lemma 5. (informal). If 2 -bf-3, perturb - If -b(-3, perturb byT--2 Remaining parameters in 6' keep fixed. Then under Assumption 1, a training loss lower than R(0") is obtained under this perturbation.
7

---

Under review as a conference paper at ICLR 2023
3.3 MAIN RESULTS AND DISCUSSION
Combining Lemma | Lemma 4 and Lemma 5 we have the following theorem.
Theorem 1. Under Assumption 1, the local minima 0 == (') given in Lemma 1 are spurious
if R(() > O for squared or cross-entropy loss. Due to nonnegative homogeneity of ReLU activation, infinitely many spurious local minima exist by scaling the parameters of different layers
In the general case when the two consecutive convolutional layers we utilized are not located at the top and there are some convolutional, average pooling, fully connected layers between them and the output layer, we can still construct spurious local minima using similar idea. The only difference is the setting of parameters for layers above the consecutive convolutional layers, and we set them such that the output of the two consecutive convolutional layers are propagated unchanged (except pooling operations in possible subsequent pooling layers) to the first fully connected layer, which plays the role of layer L in Lemmas I and + and then the output of the first fully connected layer forwarded unchanged to the output neurons. For such constructed and 0', we can show that 0 is still local minimum, there is still R(O") R(0) and the empirical risk can be decreased by perturbing 0', The details will be given in Appendix D The requirement of having two consecutive convolutional layers may be further relaxed, and we leave it to our future work.
Remark 1: Our construction of spurious local minima shows that for practical datasets and CNNs each local minimum of the subnetwork is associated with spurious local minimum. Since the output of a CNN with ReLU activations is a piece-wise linear function, and from the perspective of fitting data samples with piece-wise linear output (Liu 2022 ). the local minima of subnetworks of a CNN (and consequently the spurious local minima of the CNN) may be common due to the abundance of different fitting patterns. Furthermore, suggested by Xiong et al. (2220), CNNs have more expressivity than fully connected NNs per parameter in terms of the number of linear regions produced. The ability of producing more linear regions implies more fitting patterns, thus we conjecture that CNNs are more likely to produce spurious local minima than fully connected NNs of the same size. We leave the exploration of these ideas our future work.
4 AN EXAMPLE OF NONTRIVIAL SPURIOUS LOCAL MINIMA
In this section, we will construct an example of nontrivial local minimum in which some neurons are inactive, which can serve as the subnetwork in Lemma [ By Theorem [ the associated local minimum for the CNN that contains this subnetwork is spurious. In comparison, in He et al. (2020); Ding et al. (2019;; Goldblum et al. (2020); Liu al. (202T) for deep ReLU networks. spurious local minima are trivial since all ReLU neurons are active and deep neural networks are reduced to linear predictors.
The idea is to split data samples into two groups using a hyperplane that is perpendicular to an axis, and then fit each group of samples using different predictors. We design a CNN architecture with appropriate parameters to generate these two predictors, and show that perturbing parameters will increase or at least maintain the loss.
we use hyperplane with normal p to split the data samples. Choose any index & [du], we set p = (0, 0. ..... 1, .,., where only the kth component of is 1. Without loss of generality, assume the kth component of input x is in located in its first channel. Let I = {i] keth component. Choose one element i in set I, and denote by j the index of any sample with the largest x among n, (n E [N). & 7). then we set
Given data samples (xi, "x, , .NN.
maxje[N] 2 j.e.. is the set of indices of samples having the largest
(a + ax.))
cp
For any point x on the positive side of hyperplane P. we have
1 2 (af + 0.
opp x + c,) = olz - ( + x3.)) = v
(10)
We fit the two groups of samples in different ways using two subnetworks. Concatenating the two subnetworks, we obtain a full CNN. The following theorem gives an informal description of its architecture and parameters. The formal description will be given in Appendix B
8

---

Under review as a conference paper at ICLR 2023
730
433
(a) level sets around 0 in Lemma
(b) level sets around 0' in Lemma
(c) level sets around 0N in Theorem 2
Figure 2: The visualization of level sets of empirical loss around specific locations in parameter space. (a) and (b) demonstrate that is spurious local minimum since R(6") R(0). (c) shows that 01 constructed in Theorem 2 is a local minimum.
Theorem 2. (informal). Given a CNN with two subnetworks, its parameters 01 (W', b') set as follows. The parameters of the first subnetwork are set such that the kth component of sample x; (i E T) is forward propagated the final fully connected layer, and that of sample x; (i T) is blocked. The parameters of the second subnetwork are optimized to minimize the empirical loss for samples {xyli E [N]. j 1). Then, the point 01 local minimum in parameter space.
For this local minimum, the ReLU units in the first subnetwork that correspond the kth component of input are only activated by samples Xj (j I) and are inactive for remaining samples. Thus,
the local minimum (W b)) is nontrivial for which different activation patterns exist and the resulting predictor is nonlinear. When using the local minimum 0 constructed in Theorem
the subnetwork of in Lemmal 1 in order to further construct 8' shown in Lemma 4 we need to make
sure that Assumption and R(0) hold. With the same ideas as dicussed in section 3.2.1 1
can construct the second subnetwork such that there always exists point 0₁ (and consequently 8) for which both Assumption and R(0)= hold for popular datasets and CNN architectures.
5 EXPERIMENTAL RESULTS
We conduct experiments CIFAR-10 image set to verify the correctness of Theorem 1 and Theorem We use two approaches to show the existence of spurious local minima. The first one is to visualize the loss landscape around local minima 0 using the technique given in Li et al. (2018). Given two random directions 8 and we compute the empirical losses R(O + aò + 3r)) at grid points in the two-dimensional plane specified by 8 and r), where (a, B) are the coodinates of each grid point. Then, the level sets of empirical loss are depicted using empirical losses at these grid points. The second approach is to compute the empirical losses around 0 along many random directions and see whether losses lower than R(O) exist. Experimental details are given in Appendix
Fig 2 shows the results of the level set visualization approach. Fig 2(a and Fig [[b) demonstrate that the local minimum 0 constructed in Lemma 6 is spurious since R(0') R()) and local minimum
with loss lower than R(0') exists. Fig shows that the point 0 constructed in Theorem is local minimum. 3 shows the results of random direction approach and will be given in Appendix
CONCLUSION
We have proved that convolutional layers can introduce infinite spurious local minima in the loss landscape of deep convolutional neural networks with squared loss or cross-entropy loss. To show this, we developed new techniques to solve the challenges introduced by convolutional layers. We solved a combinatorial problem to demonstrate that a split of outputs data samples is always possible somewhere in feature maps. In this combinatorial problem, we overcame the difficulty of arbitrary groupings of outputs of data samples caused by limited receptive fields and arbitrary activation status of hidden neurons. We also solved the tied parameters problem, giving perturbations of filters and biases to decrease the training loss that affect only the output a single neuron the feature map.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning. 2019.
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58, 1989.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International Conference on Machine Learning, 2017.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in Neural Information Processing Systems, 2014.
Tian Ding, Dawei Li, and Ruoyu Sun. Spurious local minima exist for almost all wee-ppaametterized neural networks. Optimization online, 2019.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A. Hamprecht. Essentially barriers in neural network energy landscape. In International Conference on Machine Learning, 2018.
Simon S. Du and Jason D. Lee. On the power of over- paramttriitiiooonn in neural networks with quadratic activation. In International Conference on Machine Learning, 2018.
Simon S. Du, Jason D. Lee, Yuandong Tian, Barnabás Póczos, and Aarti Singh. Gradient descent
learns seee-hidennllayee cnn: Don't be afraid of spurious local minima. International Conference Machine Learning, 2018.
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 Machine Learning, 2019.
C Daniel Freeman and Joan Bruna. Topology and geometry half-rectified network optimization. In International Conference on Learning Representations, 2017.
K. Fukumizu and S. Amari. Local minima and plateaus hierarchical structures of multilayer perceptrons. Neural Networks, 13:317-327, 2000.
Kenji Fukumizu, Shoichiro Yamaguchi, Yoh ichi Mototake, and Mirai Tanaka. Semi-flat minima and saddle points by embedding neural networks to overparameterrizaton. In Advances in Neural Information Processing Systems, 2019.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances Neural Information Processing Systems, 2018.
R. Ge, J. Lee, and Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems, 2016.
M. Goldblum, J. Geiping. A. Schwarzschild, M. Moeller, and Goldstein. Truth or backpropaganda? an empirical investigation of deep learning theory. In International Conference on Learning Representations, 2020.
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. In International Conference on Learning Representations, 2015.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2017.
Fengxiang He, Bohan Wang, and Dacheng Tao. Piecewise linear activations substantially shape the loss surfaces of neural networks. In International Conference Learning Representations, 2020.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Patlern Recognition, 2016.
10

---

Under review as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. 2015 IEEE International Conference on Computer Vision (ICCV), pp. 1026-1034, 2015.
Gao Huang, Zhuang Liu, and Laurens van der Maaten. Densely connected convolutional networks. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, 2016.
Abbas Kazemipour, Brett Larsen, and Shaul Druckmann. No spurious local minima in deep quadratic networks. arXiv preprint arXiv:2001.00098 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, 2012.
Thomas I Laurent and James H. von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, 2018.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11): 1998.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, 2018.
Qianli Liao and Tomaso Poggio. Theory of deep learning ii: Landscape of the empirical risk in deep learning, arXiv preprint arXiv: 09830, 2017.
Bo Liu. Spurious local minima common for deep neural networks with piecewise linear activations. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-13, 2022. doi: 10. 109/ TNNLS 2022.320419..
Bo Liu, Zhaoying Liu, Ting Zhang, and Tongtong Yuan. Non-differentiabbee saddle points and sub-optimal local minima exist for deep relu networks. Neural Networks, 144:75-89, 2021.
Haihao Lu and Kenji Kawaguchi. Depth creates bad local minima. arXiv: 777208858.. 2017.
arXiv preprint
Christian H.X. Ali Mehmeti Goppll. David Hartmann, and Michael Wand. Ringing relus: Harmonic
distortion analysis of nonlinear feedforward networks. International Conference on Learning Representations, 2021.
Q Nguyen and M. Hein. Optimization landscape and expressivity of deep cnns. In International Conference on Machine Learning, 2018.
Maher Nouiehed and Meisam Razaviyayn. Learning deep models: Critical points and local openness. arXiv preprint arXiv: 1803.02968, 2018.
I. Safran and O. Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference Machine Learning. 2018.
Arsalan Sharifnassab, Saber Salehkaleybar, and S. Jamaloddin Golestani. Bounds on over- parameterization for guaranteed existence of descent paths in shallow relu networks. In In- ternational Conference on Learning Representations, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
M. Soltanolkotabi, Javanmard, and J. D. Lee. Theoretical insights into the optimization landscape of overparameterizee shallow neural networks. IEEE Transactions on Information Theory, 65(2): 742-769, 2019.
Grzegorz Swirszez, Wojeiech Marian Czarnecki, and Razvan Pascanu, Local minima in training of deep networks. arXiv preprint 161 10, 2016.

---

Under review as a conference paper at ICLR 2023
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In IEEE Conference Computer Vision and Pattern Recognition, 2015.
Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. In International Conference on Machine Learning, 2020.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. In International Conference on Learning Representations, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaic. Small nonlincarities in activation functions create bad local minima in neural networks. In International Conference Learning Representations, 2019.
Li Zhang. Depth creates more spurious local minima. arXiv preprint arXiv:1901.099: 00990000..99...00. 2019.
Yaoyu Zhang, Yuqing Li, Zhongwang Zhang, Tao Luo, and Zhi- Qin John Xu. Embedding principle: A hierarchical structure of loss landscape of deep neural networks. Journal of Machine Learning. 1:60-113, 2022.
Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference Machine Learning. 2019.
Yi Zhou and Yingbin Liang. Critical points of neural networks: Analytical forms and landscape properties. In International Conference on Learning Representations, 2018.
12

---

Under review as a conference paper at ICLR 2023
A PARAMETER MATRICES FOR AVERAGE POOLING AND FULLY CONNECTED OPERATIONS
We give one-dimensional example show how formulate the average pooling operation matrix-vector product. Given a one-dimensional input o' (a, b, c, d) suppose the patches for pooling are con-overlapping, which is usually the case, and the patch size is 2. The output is then of = (5 a + 6), { + d))", which is equivalent to the following matrix-vector product
1 20011
(11)
Thus, W 1 6 1
01000
1109
9) Parameter matrix for average pooling operation in two-dimensional
case can be obtained using similar idea by converting the feature maps in input layer into vector, and the nonzero entries each row of W are not all adjacent.
For fully connected layers, there are no constraints on the entries of parameter matrix W E RR 1,
B AN EXAMPLE OF NONTRIVIAL LOCAL MINIMA FOR CNNS
We fit the two groups of samples separated by the hyperplane with normal p different ways. For samples (xylj E [ & J, we use subnetwork with parameter matrix W2 to fit them, i.e., the output of this subnetwork
W28j, Vj E [N].j & T,
(12)
where & is the input augmented with scalar (at the same time weight matrices are augmented to include biases (denoted as Wi make notations simple).
We use a subnetwork with parameter matrix W1 to fit data samples {xyli E [}, and W1 is given by
Wili, )22 (2 )), + (p
(TTxx Xj + cp), j I i [dy]-
(13)
Then, the output is
0j = WiX = W2 + (p x, + cp) A2,,
JEI.
(14)
()r, i [d,]} are constants determined as follows. there is only one sample x,- in set with target output y,. and the loss function is the squared loss, there must exist y;-- such that 1 v,.) = 0. Let
O,- y,., then we have T-- (j) = W2(j, ))+;- + Xj (p X;- cp), Vj E [dy,], which leads to
A y (j) Wa(i.)
Vj [dy].
(15)
x/ + Cp
If there are multiple elements in set or the loss function is the cross-entropy loss, the parameters {Ag,5 e [dy]} are determined by
El 1i(w>x + (xt + cp) 42, ... ² .8.). (16)
(Ag, j E [dy]] argmin (py, JEid,
NEl
Concatenating the subnetworks, obtain full CNN. The following theorem gives its architec- ture and parameters (w', presentation, we ignore pooling layers first.
( b²)(_ and shows that 01 = (Wl, b is a local minimum. For ease of
Theorem 3. (formal version of Theorem D. Given a CNN, assume the number of filters in each convolutional layer satisfies Ti 2 (I -- 1-1), and the size of each convolutional layer satisfies n4 Pt-1 2 dy E [L 1]). Its parameters are given follows. The weight matrix of the first filter in the first convolutional layer is
W Po, 1: Po) TT
(17)
13

---

Under review as a conference paper at ICLR 2023
where Idrgxr, is the identity matrix of size Po Po. Po is the number of patches in the input used for convolution. The corresponding bias is
8 =
(18)
The filters and biases of higher convolution layers
(1 PL-1 Pt-1) Idp, 0,, 1E 12.3. , 1}
(19)
forward propagate the first feature map of a (x;) unchanged.
The subnetwork with parameter matrix W₂ is formed by the part of CNN that removes the first filter and all activation units in each layer, and its output is given as follows. For all j E [N] and j I,
o, = W22,; :: Pr.-2 ny [W 1i:.:w11100 (PP.- + n1, PT-3 + :.r.22)
(W (Po + 1 m. ), + bb +
+1 11:m) + +... b--1 (Pr + 1 nz 1) + b
(20)
W2 is optimized to minimize Eiin, (W28.,3)).
The final fully connected layer is set as
Wh. (i, (0, .., ,0, E [dy].
(21)
where only the kth component connecting to the first subnetwork is nonzero and equals to X Sufficiently large positive constants с₁ (1 =
are added to the biases of each convolutional layer in the second subnetwork such that the involved ReLU units are all activated. The biases of top fully connected layer by: (i E [dy]) are then substituted by by Ao where (1 recursively computed as
(1) cI, iE [Po +1:
Ad'(i) Σ
('(,,) (J) + (P-1+ 1: m)) LE 1 1),
Ao'(i)= Σ
Wh - ie [dy].
Je(Pr-attmmmn)
(22)
All remaining parameters to zeros. Then, the point 0₃ (W [ specified above is local minimum in parameter space.
If pooling layers are used in CNNs, we can adjust the parameters in Theorem to reflect the effects of parameter matrices of pooing layers. However, the adjusted (W b)) is still a local minimum.
The condition for the number of filters is used to contain two subnetworks. The condition for the size of each convolutional layers is used to make sure 8, presented in Theorem meets the full rank requirement. Because the size of each convolutional layer satisfies nę P 2 dy (1 E [L- - 1]). the matrix W2 E Rdd, xd, for the second predictor is full rank around 0 (see the proof of Theorem in Appendix G.9p. These conditions are easily satisfied by most CNNs used practice.
C LEMMAS FOR CONSTRUCTION OF SPURIOUS LOCAL MINIMA
The following Lemma 6 descibe the construction local minima 0, and it is the formal version of Lemma in section 3.1
Lemma 6. Given CNN whose numbers of filters in the last two convolutional layers satisfy
Tr-1 2 3, Ti.-2 2 3, the parameters of its last three layers are set as follows to propagate 1.-3 3x)
to the output layer. The first and second feature maps in both layer I 2 and layer L. have
14

---

Under review as a conference paper at ICLR 2023
contributions the final output.
1h (,1:2PL-2) 0,
W/ (i, = 1, [min
Wh-1 (i.j) = =0, i 1 (i,-) 0, 0, i [2PL-s]; 2 +, = i, [min (
W 2
= i i i mmin (nI.2 2P, 2Pr.,,,11.33]]
b b²~2=0
(23)
The remaining parameters, including (' (..2PP22 end). bd. and (Wi, b constitute subnetwork, and they locally minimize the following training loss when fixing those parameters in
23
R((W', (((W",')
L-3 wT (.,2 :: :edd), b²)
1 N
(24)
Σ (W (W
(Wi-1... ... (W'x x; + bb) + .....bbb1) b²-1) + b²,
Assume that i's for all 1 E 11 and E [N]. Then, the point 0 = (W b)) obtained above is a local minimum in parameter space.
The requirement in Lemma o that Î * 0 for all / E [L- and E [M] is used to prevent degenerate cases in which all ReLU neurons in a layer are deactivated for some samples. The nondegenerate cases always exist since we can fix sufficiently big biases such that all ReLU neurons are turned on and then train the subnetwork.
The following Lemma Z that for practical datasets and popular CNN architectures, there always exists point parameter space where Assumption holds.
Lemma 7. For CNNs whose number of feature maps in each convolutional and average pooling layer is greater than or equals to the number of input channels Te and width of each fully connected layer is bigger than or equals to that of output layer, and datasets in which all data points are distinct, i.e. Vi,j E [N] and i + j, X; + X3, if the distinctness of samples is preserved after each pooling operation of CNNs when directly applied to the input, then there always exists point 0 for which Assumption 1 holds.
For popular CNN architectures, such AlexNet and VGG used in CIFAR10 and ImageNet image classifiction tasks, the number of feature maps in each layer is greater than the number of input channels, and the output layer is indeed narrower than hidden fully connected layers. For practical datasets, the distinctness of samples is usually preserved after several pooling operations. Thus, the conditions in Lemma are reasonable in practice.
Proof. We consider the general case in which the two consecutive convolutional layers we utilized are not located at the top, and there are some convolutional, pooling, or fully connected layers between them and the final output layer. For CNNs whose number of feature maps in each convolutional and average pooling layer is greater than equals to the number of input channels, we can set the
parameters (W", b') such that each convolutional layer forward propagates its input unchanged using the first n feature maps and the remaining feature maps are set to zeros using zero filters and biases. Also, since the width of each fully connected layer is bigger than or equals to that of output layer, we use the first dy neurons in the first fully connected layer to perform the fully connection operation, and subsequent fully connected layers forward propagate their inputs unchanged to the final output neurons. Sufficiently large biases are used in the first convolutional layer and the first fully connected layer such that all ReLU neurons in the first n feature maps of convolutional and pooling layers and the first d, ReLU neurons in hidden fully connected layers are turned on, and their effects can be cancelled at the final output layer (as done for the second subnetwork in 22 in Theorem
15

---

Under review as a conference paper at ICLR 2023
By doing so, the training loss of the CNN can be expressed as R(0) 2/ EE= I (W x,, y:). where W/Poo is a constant matrix that characterizes the average pooling operations from input the first fully connected layer, and W characterizes the computation in the first fully connected layer. The CNN has been reduced to linear classifier and the corresponding point 0 in parameter space becomes a local minimum when minimizing NV Σi=1 1 2 (W// x,, y;) with respect to W/e.
The only operation that can affect the distinctness of o T. (i E [M] at layer L-1 (or more generally, the two consecutive convolutional layers used in the construction of spurious local minima) is then the pooling operation. If the distinctness of samples x; (i E [N]] is preserved after each pooling operation of the CNN when directly applied x; (i.e., WPoo! x;), then Vi, [M] and o j. o o 04-15, hence Assumption I holds for 0.
The following Lemma 8 shows that for training data that cannot be fit by linear models and popular CNN architectures, point in parameter space with training loss R(0) > O always exists.
Lemma 8. For training data that cannot be fi by linear models, and CNNs whose number of feature maps in each convolutional and average pooling layer is greater than or equals to the number of input channels n and width of each fully connected layer is bigger than or equals to that of outpul layer, there always exists a point 0 = ((W,,'). in parameter space such that training loss R(0) > O.
The point 0 (W b)) in Lemma 8 can be the same as that in Lemma Therefore, combining the two lemmas, there exists point 0 where both Assumption I and R(0) hold.
Most practical datasets, such as CIFARIO and ImageNet, are complex and cannot be fit by linear models. Thus, the conditions in Lemma x are reasonable in practice.
Proof. Let W* E Rd, is a local minimizer of t EN / (Wx,,,). where / is the loss func- tion. For training data that cannot be fit by linear models, have N E / (W*x;,y 0. We use the same parameter settings as in the proof of Lemma 7 and then the training loss of CNN is expressed as R(0) N EEM? (W
Since SE yW*x,
endyyy 3/2 D ( x,, y:) > O, we have R(0)= > O.
The following Lemma 9 descibe the construction the point 0', and is the formal version of Lemma
il section 3.2.2
Lemma 9. Given the CNN parameters 0 = W'), specified in Lemma 6 let 0' =
(W", b'))
1. 1-1 Ifn 2 bb - set
(L.2P---+ 3PPL2)
W (1,1: (1:2-- 1 + +1: :P3PP-) O".
4 d2, = 0,
W (i,i) = -1, i E [Pt-a]]
W =1, iE {Pr +1 :1
- + 64-3,
1/-11 1
(25)
2 (i, = 11, i E (Pr.-4);
W (Pt. + i, +1, i (Pr.4),
81T 3 - sE[M] P
min
8/.-2 = + b 3
P P
61--2 2 77 b/--3
oft bf
Σ ==1
w (n+ b9
16

---

Under review as a conference paper at ICLR 2023
nn < -b(--3 set set
W (1,1: :L-2) = (1,2PL-2+1:3PPP
W 11: = -W (1,22)-2+1:3PPP- 1 (2: dy, 1: :P =
whh = (, i [P
W = (1, iE [PL-3 + 11:PP
(1, i [2PL-3 1:3PL-3)
(1, = i [PL-al;
W 2 (PL-3 = 1, i [PL-1l,
8/-3 = min
v//
114-3 -1 - 1/-33
1/2
-11 - 1/--3
VE[N),J[[PA 4)
6 = -1 b/ 611-1 0,
b =0 0, 6/- 17 + b b/-3
6/2h 6,² i E [dy]. (26)
Remaining parameters in keep fixed. Then, R(f") R(0))
The purpose of introducing b4--3 to make (v + 8/ b/L-3) z for all i E [M, j E [PL-4].
Next, we show that by perturbing 0', we can decrease the training loss. We use different perturbation schemes for different cases of yy. The following Lemma T0 descibe the perturbation scheme, and the formal version of Lemma in section 332.3
Lemma 10. If 2 - perturb 1/--2 -1
11 1/ as
1 -> 1/1-2
+ 5b - 1/L-3 + 8b.
(27)
In < -b perturb 81T-2 = -17 b1 - as
b b1 1 + =
-1
b1 - + 86.
(28)
Remaining parameters in 6 keep fixe.. Then under Assumption 1, a training loss lower than R(0') is obtained under this perturbation with proper sign of 5b.
D CONSTRUCTION OF SPURIOUS LOCAL MINIMA: THE GENERAL CASE
When the two consecutive convolutional layers we utilized are not located at the top, and there are some convolutional, pooling, fully connected layers between the two consecutive convolutional layers used our construction and the final output layer, we can still construct spurious local minima using settings similar to Lemmas 6 9 and 10 We let the first fully connected layer play the role of layer L in Lemmas and S and set the parameters of layers above the two consecutive convolutional
layers such that the output of the two consecutive convolutional layers are propagated unchanged (except the pooling operations in subsequent pooling layers) to the first fully connected layer, whose output is then forwarded invariantly the final output neurons. Similar the proof of Lemma this is always possible by utilizing the minimal widths among subsequent convolutional layers and fully connected layers, respectively.
Then, by reserving the first two feature maps in layers starting from the two consecutive convolutional layers and minimizing the loss of the remaining subnetwork, we can obtain local minimum By setting the parameters connected to the two consecutive convolutional layers as in Lemma 9 we can obtain 0'_ The positive value of (u + - may pass through different paths as before for different location j. If there are average pooling layers above the two consecutive convolutional layers, since average pooling operation is linear, the average poolings in feature maps of different paths are finally aggregated in the first fully connected layer, producing an output equal to that of 9. Therefore, there is still R(O')= R()). The perturbation scheme is the same in Lemma 10 and the perturbation will persist after passing through the linear average pooling operations, thus the empirical risk can be decreased by perturbing 0' as before.
17

---

Under review as a conference paper at ICLR 2023
E MORE AUXILIARY LEMMAS
Denote u, ;= (l( and o; == (l)((1) شزو w'o ( + +b, + bf, where b4, 3 is the do(1)
bias associated with the feature map in which location resides. We have the following lemma for squared and cross-entropy loss.
Lemma 11.
For convolutional neural networks with squared loss or cross-entrop: loss, the follow- ings can be achieved through perturbing (1,) under Assumplion where of and us denote, respectively, and after perturbation.
1. o * of ifo, oo (i.j E [N], i 5).
# =0 (i [N]).
u4 * 1l or + u * 0 if u, = u or u, + u = 0, respectively, (i.j E [N], i # j).
4. = (u1, 02 ,Nn)² T #f E ((o. 0.
5. Nonzero gaps between dis or u can still exist after subsequent perturbations.
The maintenance of nonzero gaps between dis or u/s guarantees that of # oo or uf + uz etc. still hold after subsequent perturbations.
In the following. we absorb biases into weights and the CNN output is written as o, W- T'.'''' Here, we omit the hat augmented variables for notational simplic- ity, and the exact meaning of involved symbols is clear from context. The following two lemmas will be used to prove ut + u/, ui + ul₃ & (i,j E [N], i + f) in Lemma 11 for cross-entropy loss.
Lemma 12. For cross-entropy loss, if us -L-1. -.',, al--l.wtt-... p.... (a + 0, 1), then under Assumption 2/ # vly can be achieved through perturbing W (1,.).
Uy for two samples x,,X, (i * j) and
Lemma 13. For cross-entropy loss, if u: + Uj = for two samples xs, X, (i + j) and -6-1.1 W = aI--1.J plitix, (a & 0, + 1), then under Assumption u/ + u²y + can be achieved through perturbing (1.....
F EXPERIMENTAL DETAILS
We use CIFAR-10 image set to train CNNs, which consists of 10 classes and 50000 training images of size 32 32. The CNN used our experiments has convolutional layers, with the number of channels being 64, 64, 128, 128, 256, 256, 256, respectively, and no pooling layers are used. The convolution filters are all 3 3. Each convolutional layer followed by ReLU layer. The subnetwork in Lemma is trained by Adam optimizer with 150 epochs, with learning rate of 0.001 and weight decay of 0.0005. The subnetwork W2 in Theorem 3 is trained by Adam optimizer with 500 epochs, with a learning rate of 0.0001 and weight decay of 0.0005. Both subnetworks use the Kaiming initialization (He et al. 2015)). The biggest threshold r7 in Lemma 2 is found to be 6.8915.
Fig 3 shows the results of random direction approach.
G MISSING PROOFS
For the proofs in the following sections, we assume that the perturbation of network parameters for differentiable local minimum # (W', b'),., is very small such that the activation patterns
7 (1 [T. 11 i [N)) will keep constant.
18

---

Under review as a conference paper at ICLR 2023
(a) variation of empirical loss in random directions around in Lemma
(b) variation of empirical loss in random directions around 0' Lemma 3
(c) variation of empirical loss in random directions around 0n in Theorem
The variation of empirical loss in 200 random directions around specific locations in parameter space. In (b), some directions have losses lower than R(0') R(0). (a) and (b) together demonstrate that 0 is a spurious local minimum. (c) shows that 01 constructed in Theorem 2 is local minimum.
Figure 3:
G.1 PROOF OF LEMMA
Proof. When parameters are perturbed (W b¹) (Wi tWw, + =ob') the output after perturbation is as follows,
o' (xi) :=) (w2 + +ow+) j4-1,8 (1i4-1+ +oVi2-1) j4-22... ... (wi + +ow+) &: (29)
( -i. 8F; Vi [N],
where 8F 8 11 1i + 1 W +
3W OW
The training loss after perturbation is
R((W' B((W'+&W' +ow b' +ob')
(0' (x))
N
W 81 xx.
(30)
Since for every sample the output of each layer nondegenerate, when minimizing R((WW, b)) 1.-3 w 2P
end), b²)
N DM!! (Wrift-L, explored by f R((W' + - b' + 5b )b)) cannot be lower than ( b') despite the perturbation in 8. and (W b is thus local minimum in parameter space.
...... W & in 24 the space of o (x;) has been fully
W in the neighborhood during minimization. Therefore,
G.2 PROOF OF LEMMA 2
== min (n 2PL-2, nL-2 - 2P n)),),, if there exist some groups in the ordered list of of (i E (N]) such that Eiery * 0. and suppose G1 1mm+1: 1m,42: uy j is
Proof. At
location j
[M] (more specifically,
the first such group in the ordered list, we can set 1 m + w/ " which is the midpoint of the gap between group G1 and the next group, and set n -g+1l We then have ΣL 4; = Emn u4 + Eieg, i: = EiEc, u, * O. The requirements have found split for data samples.
are satisfied and we
for every group E [gy] at location j. there is Eiery u; = O, we have to explore other locations in feature maps to whether there exist such splits. According to Lemma 3 Ever 4, 0
19

---

Under review as a conference paper at ICLR 2023
cannot happen for every group q and every location j, and there must exist some locations where Eier; U + O for some groups. As a result, we can split data samples as before at these locations.
There may be more than one location where such data split exists, and we choose the one with the biggest threshold 7) and use it in the perturbation of training loss. Let h be the location having the biggest split threshold, we then have
Vj E [M], + h,
Σ
u, = O.
(31)
EE 1E (11,,,,,,,1 MN1/20}
G.3 PROOF OF LEMMA 9
Proof. There are two possible cases for 1) 17 2 -b1-3 or 17 < -b4-3, which will be treated differently in the following.
In order to compare the training losses at 0 and 0', we need to compute the output of (x:) 2 obtained by 0'. We will give the computation of its first component oj (xx) in detail. We only need to compute those terms in 0f (x:) that are affected by the parameter settings in (25) and (26). and denote by o' (x,) the sum of such terms.
In 2 -bi only the first and the second feature maps in layers L - 1 and L - 2 are involved. Let 1 ). where 1r.-4 is the vector of size Pt-4 whose components are all Is. o'6-3,i is the output of the first feature map at layer L 3 using the new bias 114-3, Since WL-3 ( + b/--3 2 0 for all E [N], j E [Pr.4], there is 0'L-3,3- = WL-3 (1: P1:4,,,,000 04-44 + 1f1-31p Then, the output o' (x:) is
0LL-3,1- == OWL-3 (1: P2-4. -) +
o' (xx) =W (1.1:
o (W (1: Pt.22, 1: PP.3))
a (W 20 211: Pr.3, 1: Pt.-4) 4) o 31.33, + 1 Pp-s) + +b bb 10--Ipm_- Pp-2)) +
:hth (1, : 2)))22
(W (PL-2 + : P1
o 2 (P P1- 1b-3,, + 6 1 2 + 112--11
11h-11 1144-11p__0 1p22)) + bbt
(32)
For notational simplicity, denote / (1, 2) (i (P2-2)) as w². and note that of
WL-3 (f..)oz 04-4,3, E [Pr_ Using 25). we have
Ph-2
o' (xx) = Σ Iwo σ (-o ( (1o 87 + +7 81th B/u-3) + + + b//33)
5=1
w¹o (0 (0g B/4-3) - 14633) + + + wy (17 + 14-391 + of (33)
Pr
= Σ w 22/ + b
Ø=1
where
2/ = (oo (-v -b(l-3 + + +1 ((t1-1 + + 64-3) +
(34)
o
b/--3) 11 -b(L-3 + + b(-3) - (17 + b6--)
We also denote
2j ==== o + 1/-3))
(35)
and thus the partial output obtained from 0 is
Pr--
o(x))
Σ
w
Zz + bf
(36)
j=l
20

---

Under review as a conference paper at ICLR 2023
There are three possible cases for the value of oz. Note that we already have 17 b/-3 2 if
" 2 14-3
1) o) n..
In this case, we have oy - 2 and i. + b/-3 2 up - 17 2 0, then
z/ (nn + bf- + ( + - (1 + of-
(37)
= up + b/ وj >0, 0, Vje E Pr--2|
2) 16--3 < 1/ <1.
We have -1g + 11 > 0. By (34) and of + 1/-3 2 0, we then have
oj (- (-o +n) + 0 + (17 09- (11 -1
(38)
= (v + b1 3 = 2j 2 0, Vj E [P2-2].
3) o! <b--
In this case, have of < 1/ oa bb b < then
2/ = 0 b/ 17 + + by 0)
+ a (1+ b1-3) (n+
(39)
a ot + b 0 Bjz vj [PL-2])
In all three possible cases, we have obtained = = 2g, Vj [PL-2]- Therefore, o' (x.) = :x)==Ef+ w 2 + bft o (x:). Vi [N]. We can obtain (x,)) 0 (x,) (Ai E [N], Vk E [dy], * 1) for remaining output components since W (2 dy, 1: 22) The outputs are thus not changed, so does the training loss.
We now discuss the case of 1 < <bf-33 Denote w² := -WL (1,2P--2+ Vi E [PL-2]. The output o' (x,) that is affected by the parameter setting in 26 as follows.
(xx) =w" (1, PL-2)
o (W (1: P2-2, PL-3)
o (W (1: PT,-,, 1 41, 0 - -b(--2pp pp +
w' (1, 11, 22(-2)
o OWW'i-1 1
o -WWLL22 (P Pt P1
-331 + b2 1---21 1 + + (pmn)) +
1 (1,2P, (1,2Pr-2+1:3PP.
a (W'L-1 (1
a (W ::
b/2 11-2211 1p + +b4 1
1p
+ bit (40)
Using 26 we have
PL-2
(x,) = Σ
w 0 0 1/ + k - 6² 3)(
j=1
1 bf--3 17 - 8)
(41)
15 + 8if 11 1443) + n + bf- + i.
+o
Pi--3
Σ
w +
21

---

Under review as a conference paper at ICLR 2023
where
of
1/ + b/--3 3 -17 -
1/ + bL - 11 1 b16-3)
(42)
1 + 81t 1 b1 1ソ + + bf-3)
+o
There are also three possible cases for the value of uf. Note that we already have 1) + 64-3 < 0 when
< -113- 1) 2-
In this case, using uf - 11 > 0, of + +bf-3 2 and (42 we have
zン} ug! 77) (n) ")
+ (f
(43)
up + by -3 2j 2 0, bj E [p1--)].
2) S v.. < -b--3
Using vi 11 2 0, vg + 1/-3 < 0, we have
zンj o - -n) - {n] -1)
(d} + b/
(44)
0 2j. Vj E [PL-2]-
3) of <n Using v/ - 1] < 0, vl + 1/-3 < 0, we have
2 = a (n + : = 2 = a (vf (b Vj [p2-2].
(45)
Therefore, in all possible cases of 1) and vi: the output of (x,) = or (ix) E [N]. We have (x.) of (x:) (Vi E [N], Vk [dyl, k + 1) for remaining output components. As result, the training loss satisfies R (0) R (0)).
G.4 PROOF OF LEMMA IO
Proof. We will show that by perturbing 0', the training loss can be decreased. We use different perturbation schemes to show this for different cases of v).
If 2 61-3, we only perturb fff--2 - 17 6/ bff.-3
8 b/ 5b 7)
61T - + 8b.
(46)
Under this perturbation, the output of each sample is perturbed as follows according to different cases of e
1) 2 n.
In this case, after perturbation, by modifying 34 we have
zy= (o (a(0) - + +
Since v is at the midpoint of gap between adjacent v/s (as indicated in the proof of Lemma
2) there
is vi > 17, hence for sufficiently small perturbation 8b, of 17 + 5b > 0 and of + 1/-3 5b 0 hold. Therefore.
2/3 of + t + 86 2, + 86, Vj E PPi-2l.
(47)
2) -18-3 3 < < 17- Since of 17 + 6b < 0, the perturbation åb does not pass through the ReLU activation,
2/ nrf + + وjo Vj (Pr-2])
(48)
22

---

Under review as a conference paper at ICLR 2023
3) od -bp-3. In this case, vf - + 86 then
= 2js Vj E [Pt-2].
(49)
Combining the above three cases, found that the output of (x;) perturbed only if ug > Correspondingly, the perturbation of output is
P7 Σ
601 (xx) 50 (x:)
w 5b (1 (2)))).
(50)
where I () is the indicator function. Other components of output do not change under this perturbation since W (2 dy, 1 2PL-2) = 0. The training loss is perturbed as
Øl (o' (x)) -80 (x:)
1 N Ol (x:) -50 (x:)
8R' = 500) R(0")
do1
001
here o = (x;) is used to get
(()o'))))))))
M(o(k)). doi
Therefore, we have
do:
Pi-2
8K'
1
Ui
Σ j=1
w 86 (1) ({/11) >n).
(51)
For all samples x; with u/ > (Vj E (P2-2]). by Lemma 2 only at the /th neuron in the first feature map of layer L - 3, Σ W & and ma (Vi E [n]) both hold. At other locations in this feature map, because 7 is the biggest split threshold among locations, even if of > v) holds, there is Eie (1,2," M|/t>) = 0 (see (8) ). We then have
Pa-z
8R'
1
5b
Σ
W
Σ
5b w
(52)
N
N
ie (1,1,2 Mo!
Setting Sgn (Bb) = Sgnn (n D us) if whth + 0, where Sgn() is the sign function, we obtain
8R' <.
(53)
Therefore, the training loss is decreased by the perturbation, resulting in
(0)= > R (0' + 80').
(54)
Thus, 0 is spurious local minimum.
h 0, we perturb well by n + Sw, then
8R'
8b dw
W;
(55)
Setting Sgn( = Sgn (fw Σi= u,) can still decrease the training loss, and thus the conclusion that 0 is a spurious local minimum still holds.
If n < - we only pertur b/2-2 2 = 17 8 3 as
1 - 11--2 2 + = -n 1/--3 + 8b.
(56)
With this perturbation, the output of each sample is perturbed in three different cases according to the value of u/-
1) oa 2 -
In this case, by modifying
42) we have
m 17 + 8b) (o/ nn) to (o) + +//
(57)
= + 8b, Vj E [Pt-2]
23

---

Under review as a conference paper at ICLR 2023
2) n o/ < <b/--3
In this case, since gap exists between 77 and oa when splitting samples with 7 in Lemma 2 7 < of and consequently uz -1 + 8b > 0 for sufficiently small ōb. Therefore,
we have
= ug - + 8b) { n) = 5b = 2j + 8b, Vj E (P
(58)
3) o <1). 1/-
Using of - 1j + ôb < O, we have
= o (n
= =0 =j 2j, Aj E [Pz-2]- -0=
(59)
The perturbation 8b has been blocked by ReLU units.
Only the first and second eases, the output of (x:) affected by the perturbation db. Thus, we have The output is perturbed as
R 23 + ōb, if vf > T, vi [M). [Pz-2]-
(60)
Pr.-2
PL-2
d01 (x:)
Σ
w 821
Σ
w
8b
I (1} n))
(61)
j=1
Remaining output components keep unchanged. The training loss is perturbed as follows,
PL-2
8R'
u, (x;)
1
Σ
w
Σ
(62)
N
ie (12.
Because 7j the biggest split threshold among all locations, only for the hth location, there is Eiel1, (N///))) ui # O. We then have
8R'
5b w
Wi
which is the same as (2). By setting òb with appropriate sign, we can obtain dR' < and conclude that 0 is spurious local minimum.
a perturbation of (1,-) -) is required to split data samples as shown in Lemma II the training
loss at 0 is perturbed as
R 60) = (0) + OR(O) (L.)
(64)
OWL(1,.)
due to the optimality condition an(()
aw-(1.-) O since is a local minimum. The perturbation 50
only modifies -1, and does not change other parameters. Therefore, by starting from + 59 and setting the parameters of the last three layers as in Lemma 9
we can obtain a point 6" with R (0 + 50) = R (0"). Thus we have R (0) = R (0"). We then perturb the biases of 0" as Lemma 10 to obtain a loss lower than R (0), which shows that 0 is spurious local minimum.
G.5 PROOF OF LEMMA 3
Proof. We prove by induction. We will often perturb the network parameters tune o; or u; (t [N]), which does not change empirical loss, as shown in 64).
Let us first consider some special cases.
24

---

Under review as a conference paper at ICLR 2023
G.5.1 SPECIAL CASES: N = OR M
If there is only one data sample, i.e., N = 1, there will be only one group at each location. Then, by Lemma we have u (wi) # 0, thus Lemma holds.
We then consider the case of only one location: M = 1. If there are some groups with Eigrg * O,
Lemma already holds. there exists group consisting of a single sample with u, 0, according to Lemma 11 we can perturb network parameters to get u/ * 0 and thus Lemma 3 holds. Otherwise, all groups have multiple samples and there are Σierh u, for all groups, and by R(0)= > 0 and
consequently # there must exist some group such that there exists E 1 and u, * 0. All samples in group k have identical outputs, and by Lemma I1 we can separate this sample with u4 o from other samples in this group by perturbation, i.e., 0 o of (Vj E T # i). By doing so, we can obtain a isolated sample with ut o O, and thus Lemma 3 satisfied.
G.5.2 INDUCTION HYPOTHESIS
Now we discuss the cases for 2 2 and M > 1, and use induction to prove.
In order give our induction hypothesis, we first give some definitions. For multiple locations (M 1), there are usually a number of groups at each location. Recall that I denotes the set of indices of samples in the ęth group of the jth location. We can select one group with Σier, ui (the sum of u,s in this group) from each location j and form a sequence Eiery Ues EiEry Ui U EIEIN u₁ TM
If elements this sequence are equal and nonzero, i.e., Σier, " Eiery, ",
EiEry U * 0, we call it a complete and identical sequence of groups (CI sequence). If all AM
elements in sequence are nonzero but not equal, partial elements in this sequence equal to zero, we call it a non-CI sequence.
Given CI sequence, after adding a sample ug into the group qj at each location j. if Σ iE = Exemm = the sequence becomes ΣiEry, = 0, Eierg U4 = RM
EiEra us 0,.,, EiEi = 0 (now the set T4 (j E [M] contains the new sample index k:). Therefore, if for all groups and all locations, there exists only one CI sequence, and there are Σier, = 0 for all groups not in this CI sequence, then it is possible that for all j E [M] and E 1971. Σier " = 0 after adding new sample that can annihilate this CI sequence, thus Lemmal 3 is violated.
In order to prove Lemma 3 suffices to prove that for every possible group configuration groups with Eier u, # 0 exist after removing CI sequences. Sometimes only CI sequences exist, like (u:) - (w:) -...- (u.) (i E [N]), and when adding new samples, there is risk of annihilating such CI sequences. We can avoid such situations using perturbations of network parameters (this will be explained in sections G.3.3 and G.3.4). Consequently, we give the following induction hypothesis.
For multiple locations, either non-CI sequences exist after removing each CI sequence (setting each element Dierd, uy in it to zero), or the removal of CI sequences can be prevented.
By this induction hypothesis, after adding a new sample X into one existing group at each location, groups with Eiert, u, * 0 still exist, and Lemma 3 hhllds accordingly.
As base cases, we will prove that this induction hypothesis holds for N = 2. We then prove that if it holds for N = m (m 2 2), will also hold when adding new sample X 1, as induction step.
G.5.3 BASE CASES: N =
M 2. First, we discuss the cases two locations. When = 2, all possible group configurations discussed in the following and we will prove that induction hypothesis holds for each case.
25

---

Under review as a conference paper at ICLR 2023
CASE 1. Suppose the groups two locations
location 1: (u1 u2)
(65)
location 2 (W1, U2)
If U1 U2 * 0, then the sequence (u1, u2) - (M1, U2) (the first element in the sequence is (u1, U2) from location 1, and the second one is (W1, u2) from location 2) a CI sequence. However, this CI sequence cannot be vanished by adding new sample since we can use perturbation of network parameters to prevent it from happening, described later in the induction step.
If #1 U2 0, by Lemma 11 we can perturb network parameters to obtain w/ ul2 = 0 at first.
CASE 2. Suppose the groups at two locations are
location 1 (ui, (2); location 2 (u,), (u2),
(66)
where groups on the left have bigger u/s than those on the right at each location.
By Lemma 11 we can perturb network parameters to obtain un * 0 and un * 0 for squared loss
and cross-entropy loss, then the sequences (w/, u/)) - (u4) and (u', uh) (ul) are both non-CI sequences, thus the induction hypothesis holds. If (u1, u2) in location is separated as (u() (ub)
after perturbation, then it can be treated by the following case
CASE 3. Suppose the groups at two locations are
location 1: (ur), (u2)
(67)
location 2: (w1) (u2)
or
location : (wi). ) (u2)
(68)
location 2 (u2). (u1).
For these cases, by Lemma 11 uj = U2, we can perturb the parameters to obtain o' + uly for squared loss and cross-entropy loss, then the sequences (w²) (ul) and (u²) - (u²) are both non-CI sequences.
The sequences (u1) - (u1) and (uz) (w2) are CI sequences. Again, by appropriate perturbations when adding new samples in the induction step, such CI sequences will not be removed and thus hoolds......
select two locations subset, which must belong to one of the above three possible cases. The full sequences of locations contain those sequences in this two-location subset as sub-sequences, and consequently groups with Eisri, u4 # still exist in full sequences. Therefore, induction hypothesis holds for M 2 3.
M 3. 3. If there more than two locations,
G.5.4 INDUCTION STEP
At last, prove that if the induction hypothesis holds for N samples, then it holds for N = m + samples. Suppose sample Xm++1 is to be added given current arrangement of groups.
Note that have um+1 * according to Lemma [1] There are the following three possible situations.
1) Xm++ added as a new group at every location.
This is equivalent adding CI sequence. CI and non-CI sequences formed by previous groups still exist, thus induction hypothesis holds.
2) X x is inserted into an existing group at every location. More specifically, this can divided into the following four cases.
26

---

Under review as a conference paper at ICLR 2023
A) Xm++1 is inserted into existing group satisfying Zier U4 every location.
This is equivalent adding new CI sequence into existing groups. Since CI non-CI sequences still exist, the induction hypothesis holds.
B) + is inserted into existing CI or non-CI sequences.
inserting x into an existing CI sequence, it will either be a new CI sequence, or annihilated by this addition. By induction hypothesis, non-CI sequences may still exist, hence induction hypothesis holds again after inserting Xm+1. Another possible situation is that CI sequences exist, such as (u,) (u,)
(u,) (i E [M]. and when adding new samples, there is risk of annihilating such CI sequences, and if no remaining non-CI sequences exist, then no groups with Σier, 144 * 0
exist. We perturb the outputs of samples avoid such situation using perturbation of network parameters. For example, un + 0g = 0, then adding u3 into the sequence (u1) - (w1) - _... (21) will cause its disappearance. We will have 0₁ 03 since sample and sample 3 always appear in the same group at every location after the addition. After perturbation that tunes 0₁ and 03 differently to get of * dg. as shown Lemma 11 sample and sample 3 then cannot appear in the same group every location. The annihilation of sequence (ui) (u1) - -... (u1) is thus avoided and induction hypothesis holds.
If inserting Xm+1 into an existing non-CI CI-C sequence, it will still be non- CI sequence by definition. Therefore, induction hypothesis holds.
C) Xm+1 is inserted into an existing CI sequence at some locations and into an existing non-CI sequence at remaining locations.
The involved CI sequence becomes non-CI one, and the involved non-CI sequence may become non-CI sequence, a CI sequence or a zero sequence. Anyway, non-CI sequences still exist and cannot be removed by adding sample, and thus induction hypothesis holds.
D) X 1 is inserted into an existing CI or non-CI sequence at some locations and into groups with ExEr U2 = 0 at remaining locations.
In this case, non-CI sequences will exist after inserting Xm+11, thus induction hypothesis holds.
3) Xm+1 is inserted into existing groups at some locations j E J1, and added as new groups at remaining locations J2. Equivalently, we can regard new groups in J2 (before adding Xm++ as existing groups with Eier u4 = 0, thus the above case D) can be applied directly, and induction hypothesis is maintained.
G.5.5 INDUCTION CONCLUSION
We have proved that if the induction hypothesis holds for N = samples, then it holds for N m+1 samples. By induction hypothesis, there exists j E [M] . E [a,], Eier u4 A O, and consequently a split of data samples somewhere feature maps is always possible.
G.6 PROOF OF LEMMA 12
Proof. For cross-entropy loss, the training loss for a sample (x) is
dy
((((x)) =- - Vio log
Σ
05.5
(69)
Σk=1 00,6
27

---

Under review as a conference paper at ICLR 2023
where oz is the jth component of o,. Its derivative is
al (o(x)),
04
00,,1
Ek=1 e
- 11
(70)
%1.1 Let p;
2 e " we have
04 P: V-.1
(71)
Denote w = (1, o: 01,1- Under the perturbation ow, by Taylor expansion we have
du. [ fl 5w
u1 = ui +
do
(72)
[11--1.
pl 5w] 2 + O(16w())
12.
+ 2 do?
Note that for - to the parameter setting in Lemma 6, thus perturbation 5w(1 2P has no effect in 72 For cross-entropy loss, the first and second order derivatives of u, are
p'''''x,, pe:
have 1,6 - 2P).-2) (Vi E [N]) due
Ou: Pt -P/;
(73)
0o
84u
Su, öp:
Ous
= (1 - -2ps))
(74)
802
Dodp: do
0o
respectively.
Let Q' = --- 1..W we now prove that if Q'x, = aQ'x, (a + 0, + 1). then by setting 5w appropriately, since p: * and p: * for finite inputs. Also note the requirement Q'x, such that (Q'x;) dw + 0 and 6. we have Q'x; + 0, i E [N]. We can set dw '
always make u/ * u/y- Note that du; do Ps p + 11-18 # in Lemma
(Q'x,) 6w * O, where is sufficiently small positive number. By (72 if du. 8o * 0ug then
Bu: (Q'x:) ow + dug (Q'x;) ) 8w, hence we have u/ + u'y up to the first-order Taylor expansion. Do
do
Bus 1 Ou, Q'x; = aQ'x; and do a Do we need to consider the second-order term in 72 and
Bu,
0o a² + 0o we have u/ + u/ up to the second-order Taylor approximation. Otherwise, we have
8uy
Bu: do do 0ot
1 Bus
wy which result in and ou, a² = aot
(p: - pa)a P
(75)
and
(1 - 2p:ja = =1- 1-2p;-
(76)
respectively.
We next show that 75 and (76) cannot both hold for each case of yr,1 {0, 1}. and thus we have 24 + v/z up to either the first-order or the second-orde Taylor approximation.
If u, = Pt, u = Pj or u, = P:- 1, u, =P; 1, then u, uj implies p; = Py. From (75) and * 1, contradiction is resulted and hence u. * v/y. If samples x; and x, have distinct labels, say
without loss of generality, u; = p: 1, Uj = Py. then u, = uj leads to Pj = p. 1. Substituting
into 775) and (76). we obtain
(p. 1-pp)aa-- (p: p2 + 2(p; - 1)
(77)
and
(1 2p:)a (1 2p:) + 2,
(78)
respectively.
and (88) can be transformed into
P. p.)a (1 (p: 2)
(79)
28

---

Under review as a conference paper at ICLR 2023
and
(1 - p.) -
(80)
respectively, By 1 Pi + 0, (99 results in
P: = Pi -
(81)
Solving 80 and we obtain a -1, However, pt 1 is impossible for finite inputs. therefore, we have # u/ after the perturbation.
G.7 PROOF LEMMA 13
Proof. We now prove that if My + új 0 and Q'x; = aQ'x; (a # 0, # 1), then by setting dw appropriately, one can always obtain ut + n'j o
By 72 if du. # Bu, then du. (Q'x,) dw first-order Taylor expansion.
Bu
(Q'x²) 8w, hence if u/ + up the do
If Q'x, =Q'xx and 8u = 1 Bu, 8 u. a² # 80
80 we need to consider the second-order term in (72), and if we have ui n'y $ 0 up to the second-order Taylor approximation. Otherwise,
do
ug
00
au; Ou, and @h a² - _ which result in
have
80
0od
-(p pp)a a = Pj p3
(82)
and
(1 22-pppaaa + (1 - (1-2p,) = O.
(83)
respectively.
We next show that 82 and 83 cannot both hold for every case of yt, E {0,
If u4 Pts U = Pj. then i4 U, 0 implies Pj -p:. Substituting it into (82 and 83 and with simple calculations, we can obtain
P,a Ps
(84)
and
2paa + 2p; =a
(85)
The solution is 1, 0, which contradict L,,; 0.
u, P: 1, = Pj 1, then u; + U, = 0 implies p, 2 - p;- In this case, the solution to 82
and 83 is 1, P: again contradiction is resulted.
samples x, and x, have distinct labels, say without loss of generality, u; = - 1, 1 P,. then u, + U, 0 leads to pj p.
p.. The solution to (82) and implies Q'x; -Q Q' x'x,. Due to 1 have for all i [N]] that all components of Q' x; are nonnegative and some components of it must be positive, and thus Q'x; = - Q' x, leads to contradiction. Therefore, a - impossible.
83 will be -1 and pa can be arbitrary. by the requirement in Lemma 6
However,
In summary, for various cases of U4,1 E {0, 1}, we all have uf n/j + 0.
G.8 PROOF OF LEMMA
Proof.
1. Proof of of # of (i,j E [N], i i) for squared loss and cross-entropy loss.
We perturb (1,.) make of # of. Under this perturbation, we have
o, o; 111-1 ... ". 1 x.) 8w o; + (Q'x;) 8w.
(86)
Since ---1, + 1 by Assumption 1, have Q'x; + Q'xy. Then, if o, og. we have of - of = (Q'x; Q'x;) åw. Let ow =(Q'x, Q'x;), where sufficiently small positive number, there is of of =||@'xx Q'xy11 # 0. Thus, of # o/.
29

---

Under review as a conference paper at ICLR 2023
2. Proof of u² + 0 (i [N]).
For squared loss, we perturb W (1, -) to make u/ # Of u, = 0. With this perturbation, we have
au
u = u, +
[ [1--1.1
7',' W x;) 5w]
(87)
do
We have 14 = 0; - V for squared loss ((o, = 2 llo; - yell -yell then
u (Q'x;) 8w.
(88)
Setting dw = e(('x:) x,) results in = Q0'x; 12= By Q'x; + 0 due the requirement /--1,6 + in Lemma 6 we have ut + O.
For cross entsopy loss function, the derivative u, is given in 70 For finite inputs and yı, E {0, 1}.
we have c- Eizle "LE + 0 and Σ PL, f 1, thus u, o
3. Proof of u² + u/j or ut + u²j + 0 (1,j E [N], 5).
For squared loss, we perturb W (1,,,.) to make u³ # u/j or ut + u/j # Under this perturbation, u, = Ug. by we have us u/z = (Q'x, x; - Q'x,) 8w. Let 8w = c(Q'x; Q'xy), there is 2/ -uy- = ==||Q'x+ Q'x, 1| * 0. Therefore, 2\ # ul (t,j E [N], j).
If u, + uj = 0, we have ut + u/ (Q'x: + Q'x,)) dw. Note that Q'x; # -Q'x, due to |1- # 0 and _ 1_ ij # 0 by the requirement in Lemma 6 Let dw <(Q'xx x; + Q'x;), we then
have vn + u || + Q'x,) 1| / O. Therefore, u/ + un o 0 (7,j E [N]. i + j)-
For cross-entropy loss function, recall that w" (1,) and Q' 16-1, W I Under perturbation ów, by the first-order Taylor expansion in 72). using (73) we have
Ou, [ 1.i.w- /'''' x;) dw] u. (p: pt) [(''x,) 5w]
4/- = u; 80
(89)
Note that Q'x; + 0, Q'x, + 0, and pi - 12 + 0 since p: * 0 and pt + 1. If Q'x: is not parallel
to Q'x,, then (p. - (Q'x,) = (p, p3 (Q'x))
+ O. Therefore, we have uf # uty or un + ulj +
0 (i,j E [N], i * j). respectively.
obtain of F ul or n/ u/, + 0 (i.j e [M], i # j) by Lemma 12 or Lemma 13 respectively. 1 is not allowed by Assumption 1.
If Q'x; is parallel Q'x₁, i.e., Q'x; aQ'x, (a # 0)),
4. u = (u), U2, uN) 10 + 0 if R = N Em 1(o,, y:) > O.
For squared loss, ii 0: V4. If y; 0 for every sample x; (i E [N]), then the empirical N Σ y,),,,) = IN E |lo, -1ll² = O, contradicting the assumption R > 0. Therefore, there must be some nonzero components in vector (o. y,) for some i [N.. Without loss of generality, let some components in (01 1/111, O2
loss R = +
y2.1, ... ON YN.1) be nonzero, hence
/ O.
For cross-entropy loss, according to 70 u; * 0 (Vi E [N]) for finite inputs, thus u =
(ui, u2,..., uN)
+ O.
5. Nonzero gaps between ois or u/s can still exist after subsequent perturbations, for squared loss and cross-entropy loss.
We discuss the gaps between o/s in detail. Given some samples with identical outputs, say without loss of generality, 01 02 T := (1. to obtain of # oz.. thus gap exists between of and oz. Without loss of generality, suppose after the first perturbation, the outputs of samples are ordered as of > dz > ..... dntm 0' o
Os, by Lemma IT we can use perturbation of parameters
of = op41
of.- We now want perturb the outputs of samples
again to avoid o', = dn41 using dw
Under the second perturbation Sw', the output of each sample is o" (w' + +ww): Q'x, = of + dw'. Q'x,. The gaps between samples are changed of oft of -441 + 8w' (Q'x,
30

---

Under review as a conference paper at ICLR 2023
Q x++1) (i Is 1]). We set 8w' small enough follows to make sure the nonzero gaps in of 01 (2 (s 1]) do not disappear.
For the gap of -o- we have of - 1+1 2 - -041 --1- 11ów ||'xx - x (i E [s
1]).
We already have of d++1 > 0 for nonzero gaps, and if dw are small enough such that
Vi [s 11, of d++1 - 11ww'l ||xxx; Q' x 0,
(90)
or equivalently
0 0++1
Vi Is 1], |lów'/1 < (iE(s-1), of 0641 20)
min
(91)
|Q'x: - Qi+1x++11
then we will have vi - of - O. Note that ||'xx - xi+1x++11 o The nonzero gaps between neighboring samples still exist.
Additional perturbations can be treated in the same spirit. For dataset with N samples, at most N perturbations are needed. The total perturbation is obtained by adding the perturbations in all steps, i.c. dw ów'
The gaps between u/s can be treated similarly using small enough perturbations.
G.9 PROOF OF THEOREM 3
Proof. The parameter matrix (1 Po. : of the first convolutional layer can be implemented by a filter like w = (0, 0, 0) (for so = 5). With the parameter setting in Theorem 3 the output
of the kth neuron in the first convolution layer
o = o (z + tp).. ViE [N]
(92)
Then, we have
of. (x:) (.. -
ViEl
(93)
due to (T). The outputs of remaining neurons the first feature map of the first convolutional layer do not matter since they will be annihilated later by W Given x + Cp < 0 (vi & 7), we have
of (x: i [N] i
(94)
The filters and biases of higher convolutional layers (1 {2, .... L 1}) for the first predictor propagate d'(1 Pt-1) (the outputs in the first feature map of each layer) forward without changing them.
Sufficiently large positive constants a E [L - 1]) are added to the biases of each layer such that all activated and their outputs
the ReLU units in the second subnetwork first convolutional layer will be added ei to each of its output neuron, and the change of outputs of higher convolutional layers can be recursively computed as
truncated. The
(1)(1) = CI2 i [Po + 1:ni].
Ao'(i) Σ
(((--)) ta iE (Pi 1: m)) LE (2,3, 1),
jelR-aatam-i
Ao"(1)=
Σ
W "'(i T- (1), ie [dy]-
JElPi-2timm-il
(95)
The effect of introducing (I [L 1]) is cancelled at the output layer by subtracting Ao from (i) (i [dyl). This is equivalent subtracting Ao (i) from 6f.
By the parameter setting, the output of each sample
(x:) Wzx; + (x) cp) (A1; ,,,,), Vi [N),
(96)
31

---

Under review as a conference paper at ICLR 2023
where the expression of Wzx; is given in 20 This implies
(x+) W2 (a cp) (21,)2,"" Ad,)) i
(97)
and
(x,) = y:, ((o (x:) ..,) = 0, iEi
(98)
if there is a single index in 1, where y; defined section 4 If there are multiple elements in set 1,
[((0(x),
Σ (Wok, + (x. + cp) 22.-..... .. .da,) .3.)
(99)
iES
is minimized.
For samples (x,, i & /]. we have
o xx = W2 Vi E [N] i i
(100)
We now show that for the CNN given in Theorem 3 be seen by perturbing the parameters and showing the non-eeeresssness of loss. The training loss is
01 (w b)) is a local minimum. This can
N
1
R =
(o (x.))))))
N
(101)
1
Σ KET
(W2x, + (-. + cp) (22, ... ,Ad,)" .31)
Σ ((W2x,)))
=
N
+ N
(C(N). sFT
Under perturbation (SW1, 8b")² 1-1 since there is a gap between xf (i E [M] and the threshold (a + =²j.), the ReLU unit in 92) keeps its activation status for every sample when the perturbation of bj cp is sufficiently small. Therefore, the output of each sample is still in the form of 96) Accordingly, if there are multiple elements in set I,
L
R'
1 ( (x;) + (x:)
N
(W28: + (z) + cp) (21, + 000 (xi) .Y:)
N
iE!
Σ
IW22; + 50 (x:)
N
kE(N] ig!
where d0 (x:) (i E I) and do (x:) (i E 1) are caused by the perturbations of parameters both Wi and W2. However, since (21,)2, ,,, minimize
Ad,)
Eier 1 (W2x + (a) + (p) (A1, A2, ... >a,) T .y). and the space of o (x;) has been fully explored by (21,)2, )d during minimization, we have
Σ ie7
(W28 (a) + cp)
(,a))" 60 (x.)..)
(102)
Σ iEl
[22x + (x. + cp) (Ai, ".,,), Ad,)) .81)
On the other hand, since the size of each convolutional layer satisfies 14 P- 2 dy (1E 1)).
the matrix W.,, PL-2 + 1: (P +1: nL-1, P1-3 + + nL-2) (. 1:
.) E xd is full rank and can generate the full space of dy de matrices around thus Eicin, 1 (W,,;, y.) is minimized by W2 in (20). Therefore, TEl
Σ (W 80 (x.
Σ (Wa
(103)
SEIN]
KE(N)
32

---

Under review as a conference paper at ICLR 2023
Using
102
and (03).
R¹ 2
W22 + (x + cp) (A1,)2, ,7a,)) .8:) + N
Σ ((222)))))
N NEI
EIN xgr
(104)
N xx) R. N
Σ
For the case of single element in set 1, R' 2 R can shown easily due to 98 Therefore, 81 (W b') L. is local minimum.
33


Reviews:
[{"review_id": "rnqTOx2svkf", "reviewer": "Reviewer_JdM7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper constructs bad local minima for convolutional neural networks (CNN) with ReLU activation. Specifically, the paper establishes the following results:\n\n1) If a neural network (termed \"subnetwork\") has a local minimum, then a network concatenating the subnetwork and 2 convolutional layers has a local minimum.\n2) There exists another point with a smaller training loss than the above local minimum. Thus, the above local minimum is not a global minimum.\n3) Construct a concrete example of the subnetwork, so as to validate the existence of a bad local minimum.\n\nThis is the first paper that addresses the existence of bad local minima for CNN with ReLU activation.", "summary_of_the_review": "Extend an existing technique to construct a spurious local minimum for CNN, which is the first attempt in this field. However, the construction of the local minimum is not sufficiently justified to be a CNN point.", "strength_and_weaknesses": "Studying the loss landscape, especially the existence of bad local minima is important for understanding neural network training. Most existing results are limited to fully-connected networks, hence an attempt to expand our understanding to CNN is valuable.\n\nThe proof of this paper consists of two major steps: 1) the construction of a local minimum, and 2) proof of the constructed local minimum to be spurious. However, in the first step (Lemma 1), the authors seem to intrinsically consider a fully-connected network. Below are detailed comments.\n\n- The authors study the matrix-vector product formulation (2) for CNN. Due to weight sharing, some entries in matrix W and bias b represent the same network weights. That is, during the optimization, some entries in W and b should be kept identical. \n\n- However, in the construction of Lemma 1, entries of $W$ and $b$ seem to be freely designed. If this is the case, it reduces to the fully-connected networks, bypassing the most challenging issue of CNN. Otherwise, the authors should justify how the shared weight constraints are satisfied. For example, the form of W in (2) does not allow assigning nonzero values to all diagonal entries. Then, how is the construction of $W^{L-1}$ in Lemma 1 possible? \n\nLemma 1 (construction of local minimum) serves as a foundation of this paper. If the problem of Lemma 1 can not be addressed properly, the paper has not really proven the existence of spurious local minima for CNN.\n\nOther comments:\n\n- Lemma 1 requires the matrix product $W^L I^{L-1,i} W^{L-1}\\cdots W^1$ to be full-rank. This may not be possible since some of the rows in $W^{L-2}$ (and some of the columns in $W^{L}$) are set to 0. Are there any dimension constraints (on $n_{L-1}, n_{L-2}, n_{L-3}$) missing in Lemma 1?\n\n- In the last sentence of page 3, $i^*_p$ may not be able to keep constant in its neighborhood if two or more features are equal.\n\n- Assumption 1 needs further justification. If neural collapse happens, the inputs to the final layer may be identical for different samples in the same class.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YOIRp2IKXc", "reviewer": "Reviewer_wvat", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper theoretically proved the existence of spurious local minima in deep convolutional neural networks by construction. Specifically, for a convolutional neural network whose last three layers before the final fully-connected layer are all convolutional layers, the authors constructed a spurious local minimum for square loss or cross-entropy loss under some non-degeneracy assumptions for the input data and model weights. The construction and proof in this paper mainly follow the framework in (He et al., 2020) which deals with fully-connected layers, and the authors solved two main technical challenges (limited receptive field, and parameter sharing) to extend their proof to the convolutional case. Experiments of a 7-conv-layer CNN on CIFAR-10 are also provided to validate the theoretical results.", "summary_of_the_review": "I tend to lean towards rejecting this paper. Although this paper introduces new techniques to construct spurious local minima for convolutional neural networks, these techniques might not be easily generalized to other settings, and the main message of the results might be somewhat unclear. Besides, the clarity of this paper also needs improvement.", "strength_and_weaknesses": "-Strengths:\n\n1. This paper showed the existence of spurious local minima in deep convolutional neural networks, and this existence is mainly due to the use of convolutional layers. This indicates that convolutional layers can introduce spurious local minima themselves when equipped in a fully-connected neural network.\n\n2. The network structure used for the theoretical proof is realistic and the ReLU activation pattern of the spurious local minima is non-trivial. The model structure can include fully-connected layers, convolutional layers, and max/average-pooling layers, which match the main ingredients of the convolutional neural networks used in practice.\n\n3. This paper introduces new techniques to extend the framework in (He et al., 2020) to convolutional neural networks. Specifically, Lemma 2/Lemma 5 extends the output split to the convolutional case by solving a combinatorial problem, and Lemma 3/Lemma 4 uses a different way (3 consecutive convolutional layers) to perform local perturbation.\n\n-Weaknesses:\n\n1. The new proof techniques used in this paper seem to be specific about the setting in this paper and could not be easily generalized to solve other problems. The framework for constructing local minima mainly follows that of (He et al., 2020), and the additional technical lemmas seem to only work for the specific setting of convolutional layers. This might limit the technical significance of this paper.\n\n2. It appears somewhat unclear what is the main message from the main theorems in this paper. Since the construction of spurious local minima of convolutional layers seems harder than fully-connected ones, does that mean convolutional layers are less likely to introduce spurious local minima? It would be better if the authors could include more implications and discussions of their theoretical results in this paper.\n\n3. The notation in this paper is heavy and somewhat hard to follow, and it might be better if the authors could use more intuitive explanations/figures and fewer formulas to improve the understanding of the readers. Moreover, the organization of the formulas and lemmas can be further improved. For example, The margin around equations (9) and (10) seems too large. Section 3.2 could also be re-arranged to a place closer to Lemma 2 to help with the proof sketch.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "XuGBrgGKSX", "reviewer": "Reviewer_L56V", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "\nThe authors study the loss landscape of multilayer convolutional neural\nnetworks, and in particular consider the construction of spurious minimizers of\nnetworks trained on regression/classification tasks. They consider networks\nwith fully connected, convolutional, max-pooling, and average pooling layers,\nas well as ReLU nonlinearities. Their main results (1) construct spurious\nminimizers in a network assuming that a subnetwork construction is satisfied\nand a certain nondegeneracy assumption holds at the local minimizer obtained\nfrom this subnetwork construction; (2) show in a specific setting (slightly\nnonstandard architecture) that a subnetwork can explicitly be constructed to\ngive a local minimizer. \n", "summary_of_the_review": "\nThe strength of the assumptions made in the theory seems to significantly limit\nits scope. As a result, although the work is technically impressive, it does\nnot seem to shed much novel light on when and why spurious minimizers exist in\nconvolutional neural networks trained on various practical tasks. The notation\nand writing could do with additional polishing.\n", "strength_and_weaknesses": "## Strengths\n\nThe authors argue that their approach to constructing local minima is modular,\nin that the task is reduced to studying a local minimum of a subnetwork (which\ncan then be embedded into larger networks). This may be useful for obtaining\ngeneral conclusions. They mention on page 5 that this is new in the context of\nCNNs (standard for feedforward nets).\n\nThe analysis seems highly technical and intricate, involving detailed\nindex-level manipulations of the filters in the network. (This also makes it\nchallenging to verify). The result considers fairly general CNN architectures\nand various loss functions, including regression and classification losses. \n\n## Weaknesses\n\nThe claims of novelty in the introduction (end of first paragraph, end of third\nparagraph) are not correct: the related work section even discusses a work of\nDu et al. on one-layer CNNs that shows spurious minima (and see similar works\nnot cited, such as https://arxiv.org/abs/1909.03172). This is not hard to fix:\nyou can claim the first result on spurious minimizers in deep CNNs / CNNs with\nseveral channels, etc. I would also recommend an additional literature search\nfor possible related references in this context, since the one I mention here\nwas missed.\n\nClaim about argmax at bottom of page 3 and top of page 4: I do not think this\nis correct in general -- consider the case where there are two distinct indices\n$i$ which achieve the argmax corresponding to different filters, and suppose\nthe coordinates $o_p^{l-1}(i)$ are open mappings (is there any reason for them\nnot to be?). Then every neighborhood of the parameters $W, b$ contains points\nat which the argmax is taken uniquely on a distinct coordinate involved in the\ntie; it implies that there is no locally-valid way to define a *constant* matrix\nthat selects the right element of the max-pooling operation. The assumption that the \ncoordinate maps are open is only sufficient; it should be possible to construct\ncounterexamples under more general conditions specific to the definition of the\nfeature maps.\n\nThe result relies on a technical assumption (Assumption 1) that seems to\nsignificantly limit the scope of the theory (or even make it vacuous).\nAssumption 1 is a nondegeneracy assumption on the network features at a local\nminimizer (this is used to prove that the minimizer is spurious). As a result\nof the dependence on this assumption, it does not seem that the theory makes\nany predictions about the existence or non-existence of spurious minimizers in\nany actual network architectures. Based on the way Section 4 and Theorem 2-3\nare written, I understand that even in the authors' construction of a concrete\nlocal minimum, it is still necessary to make assumption 1 in order to conclude\nthat the local minimum is spurious. In the rebuttal, I would appreciate if the\nauthors could enlighten me on whether assumptions like this are standard in\nother works that study spurious minimizers in neural networks (say, in the\nwell-studied feedforward setting). From my perspective, I would find it hard to\nunderstand why the natural extension from the results mentioned in the related\nwork section by Du et al. and the one I mentioned above for concrete spurious\nminimizers non-overlapping-receptive-field and one-layer Convnets would not be\nsomething for single-layer and overlapping receptive field networks, or\nmulti-layer and non-overlapping receptive field networks, rather than the\nextremely general setting the authors consider here (given that there are no\nconcrete conclusions in this setting in the presented work). \n\n## Minor / Questions\n\nBottom of page 1 and elsewhere: \"perturbated\" -> \"perturbed\" (\"perturbate\" does\nnot sound correct)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9FfdIEQOwU", "reviewer": "Reviewer_h5wB", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper theoretically investigates spurious local minima (i.e., local minima that are not globally optimal) that arise in the empirical risk of deep convolutional neural networks.\n\n- By embedding a local minimum of a subnetwork to a larger network, the paper constructs a local minimum $\\theta$ of the larger network (Lemma 1). Then, it is shown that a different point $\\theta'$ can be perturbed in a way that the empirical risk at $\\theta'$ is strictly smaller than $\\theta$ (Lemmas 2, 3, and 4). This proves that the local minimum $\\theta$ is spurious (Theorem 1).\n\n- Theorem 1 relies on the existence of a local minimum of a subnetwork. Theorem 2 provides a construction of a local minimum that is \"nontrivial\"---in the sense that different ReLU activation patterns exist for different data points, unlike existing results.\n", "summary_of_the_review": "This paper develops some novel techniques to show the existence of bad local minima in the empirical risk of CNNs. If fully correct, this looks like a good contribution to the literature. However, some issues (mostly with proof and notation) are raised and I set the recommendation to weak reject for now. If the authors clarify these issues through the rebuttal period, I would be happy to raise my score.\n", "strength_and_weaknesses": "- Existence/absence of bad local minima is an important topic in the literature, and it is true that the investigation has mostly focused on fully-connected networks. This paper is one of the first attempts to characterize spurious local minima that arise from convolutional networks, and the authors seem to have overcome several technical barriers that arise in CNNs.\n\n- However, while I got the main idea, reading the paper left me with some questions, mostly related to Theorem 1 and its proof. If all the issues are clarified I would be happy to raise my score.\n\n- I'm confused about the relationship between the number of neurons $n_l = T_l P_{l-1}$ and the number of patches $P_l$. As one can see in Eq (1) and (2), the output $o^l \\in \\mathbb R^{n_l}$ is plugged in as the input for the next layer. Considering that we apply zero-padding and stride is equal to 1, it seems to me that the number of patches at layer $l$ would be the same as $P_l = n_l$. However, it seems that the paper is assuming $P_l = P_{l-1}$ by zero-padding (e.g., see $P_{L-2} = P_{L-3} = P_{L-4}$ right above Lemma 1). To me this looks like a contradiction unless we have $T_l = 1$. Can you clarify?\n\n- In Lemma 1, we make portions of $W^{L-1}$ and $W^{L-2}$ equal to \"identity\" matrices by filling in the diagonal entries with 1. However, I wonder whether this is always possible? For example, if we look at Eq (2), there are certain entries that are *forced to be zero* by the structure of the weight matrix that arises from convolution. Also, it is mentioned that the conclusion of Lemma 1 still holds if the top layers are pooling layers. How? Take average pooling for example. One does not have the freedom to choose $W^{L-1}$ and $W^{L-2}$ arbitrarily; the matrices are just fixed, based on the number of patches and filter length.\n\n- Lemma 1 requires that $\\hat W^L \\hat I^{L-1,i} \\cdots \\hat W^1$ is full-rank for all $i$. While this may look reasonable for networks of general size, for certain cases I think this condition can become a big restriction. For example, consider the case where all $\\hat W^l$ are square matrices. Then necessarily all the diagonal matrices $\\hat I^{l,i}$ must set their diagonal entry to one in order to satisfy the full-rank condition. This means that all ReLUs must be turned on for all datasets, which boils down to a linear model.\n\n- For the local minimum $\\theta$ constructed by Lemma 1, the rest of the proof assumes that the local minimum has $R (\\theta) > 0$. How can you safely assume that? The conclusion that the local minimum $\\theta$ is spurious becomes vacuous if this assumption $R (\\theta) > 0$ actually does not hold for any local minimum. In other words, the theorem does not *disprove* the possibility that all the local minima are globally optimal because it relies on this assumption. Would there be a way to show the existence of $\\theta$ that always satisfies $R (\\theta) > 0$? Maybe by using the construction idea from Theorem 2?\n\n- Why should Eq (10) necessarily hold? If $\\eta$ is chosen based on $h$ with the biggest split threshold, why should the sum in Eq (10) suddenly become zero for all $j \\neq h$?\n\n- In Theorem 2, it is assumed that for any target $y_{i^*}$ there exists $\\tilde y_{i^*}$ such that the loss $l(\\tilde y_{i^*}, y_{i^*}) = 0$. What happens for losses for which such $\\tilde y_{i^*}$ does not exist, e.g., cross-entropy loss? Also, in Theorem 2, is $R (\\theta) > 0$ always satisfied?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject