T HE LOSS SURFACE AND EXPRESSIVITY OF
DEEP CONVOLUTIONAL NEURAL NETWORKS
Quynh Nguyen and Matthias Hein
Department of Mathematics and Computer Science
Saarland Informatics Campus, Saarland University, Germany

arXiv:1710.10928v1 [cs.LG] 30 Oct 2017

A BSTRACT
We analyze the expressiveness and loss surface of practical deep convolutional
neural networks (CNNs) with shared weights and max pooling layers. We show
that such CNNs produce linearly independent features at a “wide” layer which
has more neurons than the number of training samples. This condition holds e.g.
for the VGG network. Furthermore, we provide for such wide CNNs necessary
and sufficient conditions for global minima with zero training error. For the case
where the wide layer is followed by a fully connected layer we show that almost
every critical point of the empirical loss is a global minimum with zero training
error. Our analysis suggests that both depth and width are very important in deep
learning. While depth brings more representational power and allows the network
to learn high level features, width smoothes the optimization landscape of the
loss function in the sense that a sufficiently wide network has a well-behaved loss
surface with potentially no bad local minima.

1

I NTRODUCTION

It is well known that the optimization problem for training neural networks can have exponentially
many local minima (Auer et al., 1996; Safran & Shamir, 2016) and NP-hardness has been shown in
many cases (Blum & Rivest., 1989; Sima, 2002; Livni et al., 2014; Shamir, 2017; Shalev-Shwartz
et al., 2017). However, it has been empirically observed (Dauphin et al., 2014; Goodfellow et al.,
2015) that the training of state-of-the-art deep CNNs (LeCun et al., 1990; Krizhevsky et al., 2012),
which are often overparameterized, is not hampered by suboptimal local minima.
In order to explain the apparent gap between hardness results and practical performance, many interesting theoretical results have been recently developed (Andoni et al., 2014; Sedghi & Anandkumar,
2015; Janzamin et al., 2016; Haeffele & Vidal, 2015; Gautier et al., 2016; Brutzkus & Globerson,
2017; Soltanolkotabi, 2017; Soudry & Hoffer, 2017; Goel & Klivans, 2017; Du et al., 2017; Zhong
et al., 2017; Tian, 2017; Li & Yuan, 2017) in order to identify conditions under which one can guarantee that local search algorithms like gradient descent converge to the globally optimal solution.
However, it turns out that these approaches are either not practical as they require e.g. knowledge
about the data generating measure, or a modification of network structure and objective, or they
are for quite restricted network structures, mostly one hidden layer networks, and thus are not able
to explain the success of deep networks in general. For deep linear networks one has achieved a
quite complete picture of the loss surface as it has been shown that every local minimum is a global
minimum (Baldi & Hornik, 1988; Kawaguchi, 2016; Freeman & Bruna, 2017; Hardt & Ma, 2017;
Yun et al., 2017). By randomizing the nonlinear part of a feedforward network with ReLU activation function and making some additional simplifying assumptions, Choromanska et al. (2015a) can
relate the loss surface of neural networks to a certain spin glass model. In this model the objective of
local minima is close to the global optimum and the number of bad local minima decreases quickly
with the distance to the global optimum. This is a very interesting result but is based on a number of unrealistic assumptions (Choromanska et al., 2015b). More recently, Nguyen & Hein (2017)
have analyzed deep fully connected networks with general activation functions and could show that
almost every critical point is a global minimum if one layer has more neurons than the number
of training points. While this result holds for networks in practice, it requires a quite extensively
overparameterized network.
1

In this paper we overcome the restriction of previous work in several ways. This paper is one of
the first ones, which studies deep CNNs. CNNs are of high practical interest as they learn very
useful representations (Zeiler & Fergus, 2014; Mahendran & Vedaldi, 2015; Yosinski et al., 2015)
with a small number of parameters. We are only aware of Cohen & Shashua (2016) who study
the expressiveness of CNNs with max-pooling layer and ReLU activation but with rather unrealistic
filters (just 1 × 1) and no shared weights. In our setting we allow as well max pooling and general
activation functions. Moreover, we can have an arbitrary number of filters and we study general
convolutions as the filters need not be applied to regular structures like 3 × 3 but can be patch-based
where the only condition is that all the patches have the size of the filter. Convolutional layers,
fully connected layers and max-pooling layers can be combined in almost arbitrary order. We study
in this paper the expressiveness and loss surface of such a CNN where one layer is wide, in the
sense that it has more neurons than the number of training points. While this assumption sounds at
first quite strong, we want to emphasize that the VGG network (Simonyan & Zisserman, 2015) and
other CNNs, see Table 1, fulfills this condition. We show that such wide CNNs produce linearly
independent feature representations at the wide layer and thus are able to fit the training data exactly
(universal finite sample expressivity). This is even true if the bottom layers (from input to the wide
layer) are chosen randomly with probability one. We think that this explains partially the results
of Zhang et al. (2017) where they show experimentally for several CNNs that they are able to fit
random labels. Moreover, we provide necessary and sufficient conditions for global minima with
zero squared loss and show for a particular class of CNNs that almost all critical points are globally
optimal, which to some extent explains why such wide CNNs can be optimized so efficiently.

2

D EEP C ONVOLUTIONAL N EURAL N ETWORKS

We first introduce our notation and definition of CNNs. Let N be the number of training samples
and denote by X = [x1 , . . . , xN ]T ∈ RN ×d , Y = [y1 , . . . , yN ]T ∈ RN ×m the input resp. output
matrix for the training data (xi , yi )N
i=1 , where d is the input dimension and m the number of classes.
Let L be the number of layers of the network, where each layer is either a convolutional, maxpooling or fully connected layer. The layers are indexed from k = 0, 1, . . . , L which corresponds to
input layer, 1st hidden layer, . . ., and output layer. Let nk be the width of layer k and fk : Rd → Rnk
the function that computes for every input its feature vector at layer k.
The convolutional layer consists of a set of patches of equal length where every patch is a subset of
neurons from the same layer. Throughout this paper, we assume that the patches of every layer cover
the whole layer, i.e. every neuron belongs to at least one of the patches, and that there are no patches
that contain exactly the same subset of neurons. This means that if one patch covers the whole layer
then it must be the only patch of the layer. Let Pk and lk be the number of 
patches resp. the size
of each patch at layer k for every 0 ≤ k <nL. For every input o
x ∈ Rd , let x1 , . . . , xP0 ∈ Rl0
denote the set of patches at input layer and fk1 (x), . . . , fkPk (x) ∈ Rlk the set of patches at layer
k. We denote by Tk the number of convolutional filters and by Wk = [wk1 , . . . , wkTk ] ∈ Rlk−1 ×Tk
the corresponding parameter matrix of the convolutional layer k for every 1 ≤ k < L. Each column
of Wk corresponds to one filter whose size is equal to the patch size of previous layer, that is, lk−1 .
Furthermore, bk ∈ Rnk denotes the bias vector and σk : R → R the activation function for each
layer. Note that one can use the same activation function for all layers but we use the general form
to highlight the role of different layers. In this paper, all functions are applied componentwise, and
we denote by [a] the set of integers {1, 2, . . . , a} and by [a, b] the set of integers from a to b.
Definition 2.1 (Convolutional layer) A layer k is called a convolutional layer if its output fk (x) ∈
Rnk is defined for every x ∈ Rd as


p
fk (x)h = σk wkt , fk−1
(x) + (bk )h
(1)
for every p ∈ [Pk−1 ], t ∈ [Tk ], h := (p − 1)Tk + t.
The value of each neuron at layer k is computed by first taking the inner product between a filter
of layer k and a patch at layer k − 1, adding the bias and then applying the activation function.
The number of neurons at layer k is thus nk = Tk Pk−1 , which we denote as the width of layer k.
2

Our definition of a convolutional layer is quite general as every patch can be an arbitrary subset of
neurons of the same layer and thus covers most of existing variants in practice.
Definition 2.1 includes the fully connected layer as a special case by using Pk−1 = 1, lk−1 =
1
nk−1 , fk−1
(x) = fk−1 (x) ∈ Rnk−1 , Tk = nk , Wk ∈ Rnk−1 ×nk , bk ∈ Rnk . Thus we have only one
patch which is the whole feature vector at this layer.
Definition 2.2 (Fully connected layer) A layer k is called a fully connected layer if its output
fk (x) ∈ Rnk is defined for every x ∈ Rd as


fk (x) = σk WkT fk−1 (x) + bk .
(2)
For some results we also allow max-pooling layers.
Definition 2.3 (Max-pooling layer) A layer k is called a max-pooling layer if its output fk (x) ∈
Rnk is defined for every x ∈ Rd and p ∈ [Pk−1 ] as


p
p
fk (x)p = max (fk−1
(x))1 , . . . , (fk−1
(x))l
.
(3)
k−1

A max-pooling layer just computes the maximum element of every patch from the previous layer.
Since there are Pk−1 patches at layer k − 1, the number of output neurons at layer k is nk = Pk−1 .
Reformulation of Convolutional Layers: For each convolutional or fully connected layer, we
denote by Mk : Rlk−1 ×Tk → Rnk−1 ×nk the linear map that returns for every parameter matrix
Wk ∈ Rlk−1 ×Tk the corresponding full weight matrix Uk = Mk (Wk ) ∈ Rnk−1 ×nk . For convolutional layers, Uk can be seen as the counterpart of the weight matrix Wk in fully connected layers.
We define Uk = Mk (Wk ) = Wk if layer k is fully connected. Note that the mapping Mk depends on the patch structure of each convolutional layer k. For example, suppose that layer k has
"
#
a d
1
2
two filters of length 3, that is, Wk = [wk , wk ] = b e , and nk−1 = 5 and patches given by
c f


a b c 0 0
d e f 0 0 


0 a b c 0 
T
T
a 1D-convolution with stride 1 and no padding then: Uk = Mk (Wk ) = 
,
0 d e f 0 
0 0 a b c 
0 0 d e f
The above ordering of the rows of UkT of a convolutional layer is determined by Equation (1), in
particular, the row index h of UkT is calculated as h = (p − 1)Tk + t, which means for every given
patch p one has to loop over all the filters t and compute the corresponding value of the output unit
by taking the inner product of the h-th row of UkT with the whole feature vector of the previous layer.
We assume throughout this paper that that there is no non-linearity at the output layer. By ignoring
max-pooling layers for the moment, the feature maps fk : Rd → Rnk can be written as

f0 (x) = x,
fk (x) = σk gk (x) , where gk (x) = UkT fk−1 (x) + bk , ∀ 1 ≤ k ≤ L − 1
fL (x) = gL (x) = ULT fL−1 (x) + bL ,
where gk : Rd → Rnk is the pre-activation output at layer k. By stacking the feature vectors of layer
k of all training samples, before and after applying the activation function, into a matrix, we define:
Fk = [fk (x1 ), . . . , fk (xN )]T ∈ RN ×nk ,

and

Gk = [gk (x1 ), . . . , gk (xN )]T ∈ RN ×nk .

In this paper, we refer to Fk as the output matrix at layer k. It follows from above that
F0 = X,

Fk = σk (Gk ), where Gk = Fk−1 Uk + 1N bTk ,

FL = GL = FL−1 UL +

1N bTL .

∀1 ≤ k ≤ L − 1

(4)
(5)

In this paper, we assume the following general condition on the structure of convolutional layers.
3

Assumption 2.4 (Convolutional Structure) For every convolutional layer k, there exists at least
one parameter matrix Wk ∈ Rlk−1 ×Tk for which the corresponding weight matrix Uk =
Mk (Wk ) ∈ Rnk−1 ×nk has full rank.
It is straightforward to see that Assumption 2.4 is satisfied if every neuron of a convolutional layer
belongs to at least one patch and there are no identical patches.
Lemma 2.5 If Assumption 2.4 holds, then for every convolutional layer k, the set of Wk ∈ Rlk−1 ×Tk
for which Uk = Mk (Wk ) ∈ Rnk−1 ×nk does not have full rank has Lebesgue measure zero.
Proof: Since Uk = Mk (Wk ) ∈ Rnk−1 ×nk and Mk is a linear map, every entry of Uk is a linear
function of the entries of Wk . Let m = min(nk−1 , nk ), then the set of low rank matrices Uk

k−1 ,nk )
is characterized by a system of equations where the max(nm
determinants of all m × m
sub-matrices of Uk are zero. As the determinant is a polynomial in the entries of the matrix and thus
a real analytic function, and the composition of analytic functions is again analytic, we get that each
determinant is a real analytic function of Wk . By Assumption 2.4, there exists at least one Wk such
that one of these determinants is non-zero. Thus by Lemma A.2, the set of Wk where this determinant is zero has Lebesgue measure zero. As all the sub-matrices need to have low rank in order
that Uk has low rank, we get that the set of Wk where Uk has low rank has Lebesgue measure zero. 

3

W IDE CNN S CAN LEARN LINEARLY INDEPENDENT FEATURES

In this section, we show that a class of standard CNN architectures with convolutional layers, fully
connected layers and max-pooling layers plus standard activation functions like ReLU, sigmoid,
softplus, etc are able to learn linearly independent features at any hidden layer if that layer has more
neurons than the number of training samples. Our assumption on training data is the following.
Assumption 3.1 (Training data) The patches of different training samples are non-identical, that
is, xpi 6= xqj for every p, q ∈ [P0 ], i, j ∈ [N ], i 6= j.
Assumption 3.1 is quite weak, especially if the size of the input patches is larger. If the assumption
does not hold, one can add a small perturbation to the training samples: {x1 + 1 , . . . , xN + N } .
N
The set of {i }i=1 where Assumption 3.1 is not fulfilled for the new dataset has Lebesgue measure
N
zero. Moreover, {i }i=1 can be chosen arbitrarily small so that the influence of the perturbation is
negligible. Our main assumptions on the activation function of the hidden layers is the following.
Assumption 3.2 (Activation function) The activation function σ is continuous, non-constant, and
satisfies one of the following conditions:
• ∃µ+ , µ− ∈ R s.t. lim σk (t) = µ− and lim σk (t) = µ+ and µ+ µ− = 0
t→−∞

t→∞

• ∃ρ1 , ρ2 , ρ3 , ρ4 ∈ R+ s.t. |σ(t)| ≤ ρ1 eρ2 t for t < 0 and |σ(t)| ≤ ρ3 t + ρ4 for t ≥ 0
Assumption 3.2 covers several standard activation functions.
Lemma 3.3 The following activation functions satisfy Assumption 3.2:
ReLU: σ(t) = max(0, t), Sigmoid: σ(t) =

1
1
, Softplus: σα (t) = ln(1 + eαt ) for α > 0.
1 + e−t
α

The softplus function is a smooth approximation of ReLU. It holds:
1
ln(1 + eαt ) = max(0, t).
α
The first main result of this paper is the following.
lim σα (t) = lim

α→∞

α→∞

(6)

Theorem 3.4 (Linearly Independent Features) Let Assumption 3.1 hold for the training sample.
Consider a deep CNN architecture for which there exists some layer 1 ≤ k ≤ L − 1 such that
4

1. Layer 1 and layer k are convolutional or fully connected while all the other layers can be
convolutional, fully connected or max-pooling
2. The width of layer k is larger than the number of training samples, nk = Tk Pk−1 ≥ N
3. (σ1 , . . . , σk ) satisfy Assumption 3.2
Then there exist a set of parameters of the first k layers (Wl , bl )kl=1 such that the set of feature
vectors {fk (x1 ), . . . , fk (xN )} are linearly independent. Moreover, (Wl , bl )kl=1 can be chosen in
such a way that all the weight matrices Ul = Ml (Wl ) have full rank for every 1 ≤ l ≤ k.
Theorem 3.4 implies that a large class of CNNs employed in practice with convolutional, fully
connected and max-pooling layers and standard activation functions like ReLU, sigmoid or softplus
can produce linearly independent features at any hidden layer if its width is larger than the number
of training samples. Figure 1 shows an example of a CNN architecture that satisfies the conditions
of Theorem 3.4 at the first convolutional layer (i.e. k = 1). Note that if a set of vectors are linearly
independent then they are also linearly separable. In this sense, Theorem 3.4 suggests that deep and
wide CNNs can produce linearly separable features at every wide hidden layer.
Linear separability in neural networks has been recently studied by An et al. (2015), where the
authors show that a two-hidden-layer fully connected network with ReLU activation function can
transform any training set to be linearly separable while approximately preserving the distances of
the training data at the output layer. Compared to An et al. (2015) our Theorem 3.4 is derived for
CNNs with a wider range of activation functions. Moreover, our result shows even linear independence of features which is stronger than linear separability. Recently, Nguyen & Hein (2017) have
shown a similar result for deep fully connected networks and analytic activation functions.
We note that, in contrast to fully connected networks, for CNNs the condition nk ≥ N of Theorem
3.4 does not necessarily imply that the network has a huge number of parameters as the layers k and
k + 1 can be chosen to be convolutional. In particular, the condition nk = Tk Pk−1 ≥ N can be
fulfilled by increasing the number of filters Tk or by using a large number of patches Pk−1 (however
Pk−1 is upper bounded by nk ), which is however only possible if lk−1 is small as otherwise our
condition on the patches cannot be fulfilled. Interestingly, such a architecture has been used in the
VGG-Net (Simonyan & Zisserman, 2015), where they use small 3 × 3 filters and minimal stride 1 in
the first layer and thus they fulfill the condition nk ≥ N for k = 1, see Table 1, for ImageNet. Also
note that other state-of-the-art-networks fulfill the condition in Table 1. Overall, Theorem 3.4 can be
seen as a theoretical support for the usage of small filters and strides in practical CNN architectures
as it increases the chance of achieving linear separability at early hidden layers in the network and
also reduces the total number of training parameters. The reason why linear separability helps will
be discussed in Section 4 when we analyze the loss surface of the CNNs. Note also that the condition
nk ≥ N is a sufficient condition but not necessary to prove our results. In particular, we conjecture
that linear separability might hold with far less number of neurons in practical applications.
One might ask now how difficult it is to find such parameters which generate linearly independent
features at a hidden layer? Our next result shows that once analytic activation functions 1 , e.g.
sigmoid or softplus, are used at the first k hidden layers of the network, the linear independence of
features at layer k holds with probability 1 even if one draws the parameters of the first k layers
(Wl , bl )k randomly for any distribution which is absolutely continuous w.r.t. the Lebesgue measure.
Theorem 3.5 Let Assumption 3.1 hold for the training samples. Consider a deep CNN for which
there exists some layer 1 ≤ k ≤ L − 1 such that
1. Every layer from 1 to k is convolutional or fully connected
2. The width of layer k is larger than number of training samples, that is, nk = Tk Pk−1 ≥ N
3. (σ1 , . . . , σk ) are real analytic functions and satisfy Assumption 3.2.
Then the set of parameters of the first k layers (Wl , bl )kl=1 for which the set of feature vectors
{fk (x1 ), . . . , fk (xN )} of layer k are not linearly independent has Lebesgue measure zero.
1
A function σ : R → R is real analytic if its Taylor series about x0 converges to σ(x0 ) on some neighborhood of x0 for every x0 ∈ R (Krantz & Parks, 2002).

5

Note that Theorem 3.5 is a much stronger statement than Theorem 3.4, as it shows that for almost
all weight configurations one gets linearly independent features at the wide layer. While Theorem
3.5 does not hold for the ReLU activation function as it is not an analytic function, we want to note
again that one can approximate the ReLU function arbitrarily well using the softplus function (see
Equation 6), which is an analytic function for any α > 0 and thus Theorem 3.5 applies. It is an open
question if the result holds also for the ReLU activation function itself.
It is very interesting to note that Theorem 3.5 explains previous empirical observations. In particular,
Czarnecki et al. (2017) have shown empirically that linear separability is often obtained already in
the first few hidden layers of the trained networks. This is done by attaching a linear classifier probe
(Alain & Bengio, 2016) to every hidden layer in the network after training the whole network with
backpropagation. The fact that Theorem 3.5 holds even if the parameters of the bottom layers up
to the wide layer k are chosen randomly is also in line with recent empirical observations for CNN
architectures that one has little loss in performance if the weights of the initial layers are chosen
randomly without training (Jarrett et al., 2009; Saxe et al., 2011; Yosinski et al., 2014).
An application of Theorem 3.4 yields the following universal finite sample expressivity for CNNs.
In particular, a deep CNN architecture with scalar output can perfectly express the values of any
scalar-valued function over a finite number of inputs as long as the width of the last hidden layer is
larger than the number of training samples.
Corollary 3.6 (Finite Sample Expressivity) Let Assumption 3.1 hold for the training samples.
Consider a standard CNN with scalar output which satisfies the conditions of Theorem 3.4 at the
last hidden layer k = L − 1. Let fL : Rd → R be the output of the network given as
fL (x) =

m
X

λj f(L−1)j (x) ∀x ∈ Rd

j=1

where λ ∈ RnL−1 is the weight vector of the last layer. Then for every target output y ∈ RN , there
always exist λ, (Wl , bl )L−1
so that it holds fL (xi ) = yi for every i ∈ [N ].
l=1
Proof: Since the network satisfies the conditions of Theorem 3.4 for k = L − 1, there exist a set of
T
N
parameters (Wl , bl )L−1
l=1 such that rank(FL−1 ) = N. Let FL = [fL (x1 ), . . . , fL (xN )] ∈ R then
−1
T
T
it follows that FL = FL−1 λ. Pick λ = FL−1 (FL−1 FL−1 ) y then it holds FL = FL−1 λ = y. 
The expressivity of neural networks have been well-studied in the literature, in particular in the
universal approximation theorems for one hidden layer networks (Cybenko, 1989; Hornik et al.,
1989). Recently, many results have be shown why deep networks are superior to shallow networks
in terms of expressiveness (Delalleau & Bengio, 2011; Telgarsky, 2016; 2015; Eldan & Shamir,
2016; Safran & Shamir, 2017; Yarotsky, 2016; Poggio et al., 2016; Liang & Srikant, 2017; Mhaskar
& Poggio, 2016; Montufar et al., 2014; Pascanu et al., 2014; Raghu et al., 2017). While most of
these results are derived for fully connected networks, it seems that Cohen & Shashua (2016) are the
first ones who study expressivity of CNNs. In particular, they show that CNNs with max-pooling
and ReLU units are universal in the sense that they can approximate any given function if the size
of the networks is unlimited. However, the number of convolutional filters in this result has to grow
exponentially with the number of patches and they do not allow shared weights in their result, which
is a standard feature of CNNs. Our Corollary 3.6 shows universal finite sample expressivity, instead
of universal function approximation, even for L = 2 and k = 1, that is a single convolutional layer
network can perfectly fit the training data as long as the number of hidden units is not smaller than
the number of samples. To the best of our knowledge, this is the first result on universal finite sample
expressivity for a large class of practical CNNs.
For fully connected networks, universal finite sample expressivity has been studied by Zhang et al.
(2017); Nguyen & Hein (2017); Hardt & Ma (2017). They show that a network with a single hidden
layer with N hidden units can express any training set of size N . While the number of training
parameters of a single hidden layer CNN with N hidden units and scalar output is just T1 l0 + 2N ,
where T1 is the number of convolutional filters and l0 is the length of each filter, it is N d + 2N for
fully connected networks. If we set the width of the hidden layer of the CNN as n1 = T1 P0 = N
in order to fulfill the condition of Corollary 3.6, then the number of training parameters of the CNN
becomes 2N + N l0 /P0 , which is less than 3N if l0 ≤ P0 compared to (d + 2)N for the fully
connected case. In practice one almost always has l0 ≤ P0 as l0 is typically a small integer and P0
6

Figure 1: An example of CNN for a given training set of size N ≤ 100 × 26 × 26 = 67600.
The width of each layer is d = n0 = 784, n1 = 67600, n2 = 16900, n3 = 2880, n4 = 720, n5 =
100, n6 = m = 10. One can see that n1 ≥ N and the network has pyramidal structure from layer 2
till the output layer, that is, n2 ≥ . . . ≥ n6 .
Table 1: The width of the first convolutional layer (n1 ) and the maximum width of all the hidden layers (max1≤k≤L−1 nk ) of state-of-the-art CNN architectures in comparison with the size of
ImageNet (N ≈ 1200K). All numbers are lower bounds on the true width.
CNN Architecture
VGG(A-E) (Simonyan & Zisserman, 2015)
InceptionV3 (Szegedy et al., 2015b)
InceptionV4 (Szegedy et al., 2016)
SqueezeNet (Iandola et al., 2016)
Enet (Paszke et al., 2016)
GoogLeNet (Szegedy et al., 2015a)
ResNet (He et al., 2016)
Xception (Chollet, 2016)

n1
3000K
700K
700K
1180K
1000K
800K
800K
700K

maxk nk
3000K
1300K
1300K
1180K
1000K
800K
800K
700K

is on the order of the dimension of the input. Thus, the number of parameters of the CNN to achieve
universal finite sample expressivity is significantly smaller than that of fully connected networks.
Obviously, in practice it is more important that the network generalizes rather than just fitting the
training data. By using shared weights and sparsity structure, CNNs seem to implicitly regularize
the model class in order to achieve good generalization performance. Thus even though they can
fit also random labels or noise (Zhang et al., 2017) due to the universal finite sample expressivity
shown in Corollary 3.6, they seem still to be able to generalize well (Zhang et al., 2017).

4

T HE L OSS S URFACE OF C ONVOLUTIONAL N EURAL N ETWORKS

In this section, we restrict our analysis to the use of least squares loss. However, as we show later
that the network can produce exactly the target output (i.e. FL = Y ) for some choice of parameters,
all our results can also be extended to any other loss function where the global minimum is attained
at FL = Y , for instance the squared Hinge-loss analyzed in Nguyen & Hein (2017). Let P denote
the space of all parameters of the network. The final training objective Φ : P → R is given as

 1
2
kFL − Y kF
(7)
Φ (Wl , bl )L
l=1 =
2
where FL is defined as in (5), which is also the same as
FL = σL−1 (. . . σ1 (XU1 + b1 ) . . .)UL + bL ,
where Ul = Ml (Wl ) for every 1 ≤ l ≤ L.
Our assumptions on the architecture of CNNs is given below.
Assumption 4.1 (CNN Architecture) Every layer in the network is a convolutional layer or fully
connected layer and the output layer is fully connected. Moreover, there exists some hidden layer
1 ≤ k ≤ L − 1 such that the following holds:
7

• The width of layer k is larger than number of training samples, that is, nk = Tk Pk−1 ≥ N
• All the activation functions of the hidden layers (σ1 , . . . , σL−1 ) satisfy Assumption 3.2
• (σk+1 , . . . , σL−1 ) are strictly increasing or strictly decreasing, and differentiable
• The network is pyramidal from layer k + 1 till the output layer, that is, nk+1 ≥ . . . ≥ nL
A typical example that satisfies Assumption 4.1 is the following (see Figure 1 for an illustration):
•
•
•
•
•

The first layer is a convolutional layer with n1 = T1 P0 ≥ N
Every layer from layer 2 till the output layer is convolutional or fully connected
(σ1 , . . . , σk ) can be ReLU, sigmoid or softplus
(σk+1 , . . . , σL−1 ) can be sigmoid or softplus
n2 ≥ n3 ≥ . . . ≥ nL

One can easily check that the above example satisfies Assumption 4.1 for k = 1.
In the following, let us define for every 1 ≤ k ≤ L − 1 the subset Sk ⊆ P such that

Sk := (Wl , bl )L
rank(Fk ) = N and Ul has full rank for every l ∈ [k + 2, L] .
l=1
The set Sk is the set of parameters where the feature vectors at layer k are linearly independent and
all the weight matrices from layer k + 2 till the output layer have full rank. In the following, we
examine conditions for global optimality in Sk . It is important to note that Sk covers almost the
whole parameter space under an additional mild condition on the activation function.
Lemma 4.2 Let Assumption 3.1 hold for the training sample and let the CNN architecture satisfy
Assumption 4.1 for some layer 1 ≤ k ≤ L − 1. We assume further that the activation functions of
the first k layers (σ1 , . . . , σk ) are real analytic. Then the set P \ Sk has Lebesgue measure zero.
Proof: One can see that

P \ Sk ⊆ (Wl , bl )L
l=1


rank(Fk ) < N ∪ (Wl , bl )L
Ul has low rank for some layer l .
l=1

By Theorem 3.5, it holds that the set (Wl , bl )L
l=1 rank(Fk ) < N has Lebesgue measure zero.
Moreover, it follows from Lemma 2.5 that the set (Wl , bl )L
Ul has low rank for some layer l
l=1
also has measure zero. Thus, P \ Sk has Lebesgue measure zero.

In the next key lemma, we bound the objective function in terms of its gradient magnitude w.r.t. the
weight matrix of layer k for which nk ≥ N. For every matrix A ∈qRm×n , let σmin (A) and σmax (A)
P
2
denote the smallest and largest singular value of A. Let kAkF =
i,j Aij , kAkmin := min |Aij |
i,j

and kAkmax := max |Aij |. From Equations (4), (5) and (7), it follows that Φ can be seen as a function
i,j

of (Ul , bl )L
l=1 , and thus we can use ∇Uk Φ. If layer k is fully connected then Uk = Mk (Wk ) = Wk
and thus ∇Uk Φ = ∇Wk Φ. Otherwise, if layer k is convolutional then we note that ∇Uk Φ is “not”
the true gradient of the training objective because Uk is not the true optimization parameter but
Wk . In this case, the true gradient of Φ w.r.t. to the true parameter matrix Wk which consists of
convolutional filters can be computed via chain rule as
X ∂Φ ∂(Uk )ij
∂Φ
=
∂(Wk )rs
∂(Uk )ij ∂(Wk )rs
i,j
Please note that even though we write the partial derivatives with respect to the matrix elements,
∇Wk Φ resp. ∇Uk Φ are the matrices of the same dimension as Wk resp. Uk in the following.
Lemma 4.3 Consider a standard deep CNN which satisfies Assumption 4.1 for some hidden layer
1 ≤ k ≤ L − 1. Then it holds
∇Uk+1 Φ

F

≥ σmin (Fk )

 L−1
Y


σmin (Ul+1 ) kσl0 (Gl )kmin kFL − Y kF

l=k+1

8

and
∇Uk+1 Φ

F

 L−1

Y
≤ σmax (Fk )
σmax (Ul+1 ) kσl0 (Gl )kmax kFL − Y kF .
l=k+1

Our next main result is motivated by the fact that empirically when training over-parameterized
neural networks with shared weights and sparsity structure like CNNs, there seem to be no problems
with sub-optimal local minima. In many cases, even when training labels are completely random,
local search algorithms like stochastic gradient descent can converge to a solution with almost zero
training error (Zhang et al., 2017). To understand better this phenomenon, we first characterize in
the following Theorem 4.4 the set of points in parameter space with zero loss, and then analyze in
Theorem 4.5 the loss surface for a special case of the network. We emphasize that our results hold
for standard deep CNNs with convolutional layers with shared weights and fully connected layers.
Theorem 4.4 (Necessary and Sufficient Condition for Zero Training Error) Let
Assumption
3.1 hold for the training sample and suppose that the CNN architecture satisfies Assumption 4.1
for some hidden layer 1 ≤ k ≤ L −1. Let Φ : 
P → R be defined as in (7). Given any point
L
L
(Wl , bl )l=1 ∈ Sk . Then it holds that Φ (Wl , bl )l=1 = 0 if and only if ∇Uk+1 Φ
= 0.
L
(Wl ,bl )l=1



Proof: If Φ (Wl , bl )L
l=1 = 0 then it follows from the upper bound of Lemma 4.3 that ∇Uk+1 Φ =
0. Now, we suppose that ∇Uk+1 Φ = 0. Since (Wl , bl )L
l=1 ∈ Sk it holds rank(Fk ) = N and Ul
has full rank for every l ∈ [k + 2, L]. Thus it holds σmin (Fk ) > 0 and σmin (Ul ) > 0 for every
l ∈ [k + 2, L]. Moreover, (σk+1 , . . . , σL−1 ) have non-zero derivative by Assumption 4.1 and thus
kσl0 (Gl )kmin > 0 for every l ∈ [k + 
1, L − 1]. This
 combined with the lower bound in Lemma 4.3
leads to kFL − Y kF = 0 and thus Φ Wl , bl )L
l=1 = 0.



Lemma 4.2 shows that the set of points which are not covered by Theorem 4.4 has just measure zero
under a mild condition. The necessary and sufficient condition of Theorem 4.4 is rather intuitive as
it requires the gradient of the training objective to vanish w.r.t. the full weight matrix of layer k + 1
regardless of the architecture of this layer. It turns out that if layer k + 1 is fully connected, then this
condition is always satisfied at a critical point, in which case we obtain that every critical point in Sk
is a global minimum with exact zero training error. This is shown in the next Theorem 4.5, where
we consider a classification task with m classes. Z ∈ Rm×m is the full rank class encoding matrix
e.g. the identity matrix and (X, Y ) the training sample such that Yi: = Zj: whenever xi belongs to
class j for every i ∈ [N ], j ∈ [m].
Theorem 4.5 (Loss Surface of CNNs) Let (X, Y, Z) be a training set for which Assumption 3.1
holds, the CNN architecture satisfies Assumption 4.1 for some hidden layer 1 ≤ k ≤ L − 1, and
layer k + 1 is fully connected. Let Φ : P → R be defined as in (7). Then


L
• Every critical point (Wl , bl )L
∈
S
is
a
global
minimum
with
Φ
(W
,
b
)
k
l
l
l=1
l=1 = 0


L
• There exist infinitely many global minima (Wl , bl )L
l=1 ∈ Sk with Φ (Wl , bl )l=1 = 0
Theorem 4.5 indicates that the loss surface for this type of CNNs has a rather simple structure in
the sense that almost every critical point is a global minimum with zero training error. It remains
an interesting open problem if this result can be transferred to the case where layer k + 1 is also
convolutional. In any case whether layer k + 1 is fully connected or not, one might still assume that
a solution with zero training error still exists. However, note that Theorem 4.4 shows that at those
points where the loss is zero, the gradient of Φ w.r.t. Uk+1 must be zero as well. An interesting
special case of Theorem 4.5 is when the network is fully connected, in which case all the results of
Theorem 4.5 hold without any modifications.
Corollary 4.6 (Loss Surface of Fully Connected Nets) Let (X, Y, Z) be a training set with nonidentical training samples, i.e. xi 6= xj for every i 6= j and the fully connected network satisfies
Assumption 4.1 for some layer 1 ≤ k ≤ L − 1. Let Φ : P → R be defined as in (7). Then the
following holds
9



L
• Every critical point (Wl , bl )L
∈
S
is
a
global
minimum
with
Φ
(W
,
b
)
k
l
l
l=1
l=1 = 0


L
• There exist infinitely many global minima (Wl , bl )L
l=1 ∈ Sk with Φ (Wl , bl )l=1 = 0
Corollary 4.6 can be seen as a formal proof for the implicit assumption used in the recent work
(Nguyen & Hein, 2017) that there exists a global minimum with zero training error for the class of
fully connected, deep and wide networks.

5

C ONCLUSION

We have analyzed the expressiveness and loss surface of CNNs in realistic and practically relevant
settings. As state-of-the-art networks fulfill exactly or approximately the condition to have a sufficiently wide convolutional layer, we think that our results help to understand why current CNNs can
be trained so effectively. It would be interesting to discuss the loss surface for cross-entropy loss,
which currently does not fit into our analysis as the global minimum does not exist when the data is
linearly separable.

R EFERENCES
G. Alain and Y. Bengio. Understanding intermediate layers using linear classifier probes. In ICLR
Workshop, 2016.
S. An, F. Boussaid, and M. Bennamoun. How can deep rectifier networks achieve linear separability
and preserve distances? In ICML, 2015.
A. Andoni, R. Panigrahy, G. Valiant, and L. Zhang. Learning polynomials with neural networks. In
ICML, 2014.
P. Auer, M. Herbster, and M. K. Warmuth. Exponentially many local minima for single neurons. In
NIPS, 1996.
P. Baldi and K. Hornik. Neural networks and principle component analysis: Learning from examples
without local minima. Neural Networks, 2:53–58, 1988.
A. Blum and R. L Rivest. Training a 3-node neural network is np-complete. In NIPS, 1989.
A. Brutzkus and A. Globerson. Globally optimal gradient descent for a convnet with gaussian inputs,
2017. arXiv:1702.07966.
F. Chollet.
Xception:
arXiv:1610.02357.

Deep learning with depthwise separable convolutions, 2016.

A. Choromanska, M. Hena, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer
networks. In AISTATS, 2015a.
A. Choromanska, Y. LeCun, and G. B. Arous. Open problem: The landscape of the loss surfaces of
multilayer networks. COLT, 2015b.
N. Cohen and A. Shashua. Convolutional rectifier networks as generalized tensor decompositions.
In ICML, 2016.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control,
Signals, and Systems, 2:303–314, 1989.
W. M. Czarnecki, G. Swirszcz, M. Jaderberg, S. Osindero, O. Vinyals, and K. Kavukcuoglu. Understanding synthetic gradients and decoupled neural interfaces. In ICML, 2017.
Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking
the saddle point problem in high-dimensional non-convex optimization. In NIPS, 2014.
O. Delalleau and Y. Bengio. Shallow vs. deep sum-product networks. In NIPS, 2011.
10

S. S. Du, J. D. Lee, and Y. Tian.
arXiv:1709.06129.

When is a convolutional filter easy to learn?, 2017.

R. Eldan and O. Shamir. The power of depth for feedforward neural networks. In COLT, 2016.
C. D. Freeman and J. Bruna. Topology and geometry of half-rectified network optimization. In
ICLR, 2017.
A. Gautier, Q. Nguyen, and M. Hein. Globally optimal training of generalized polynomial neural
networks with nonlinear spectral methods. In NIPS, 2016.
S. Goel and A. Klivans.
arXiv:1709.06010.

Learning depth-three neural networks in polynomial time, 2017.

I. J. Goodfellow, O. Vinyals, and A. M. Saxe. Qualitatively characterizing neural network optimization problems. In ICLR, 2015.
B. D. Haeffele and R. Vidal. Global optimality in tensor factorization, deep learning, and beyond,
2015. arXiv:1506.07540v1.
M. Hardt and T. Ma. Identity matters in deep learning. In ICLR, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2:359–366, 1989.
F. N. Iandola, S. Han, M. W. Moskewicz, K. Ashraf, W. J. Dally, and K. Keutzer.
Squeezenet: Alexnet-level accuracy with 50x fewer parameters and < 0.5mb model size, 2016.
arXiv:1602.07360.
M. Janzamin, H. Sedghi, and A. Anandkumar. Beating the perils of non-convexity: Guaranteed
training of neural networks using tensor methods. arXiv:1506.08473, 2016.
K. Jarrett, K. Kavukcuoglu, and Y. LeCun. What is the best multi-stage architecture for object
recognition? In CVPR, 2009.
K. Kawaguchi. Deep learning without poor local minima. In NIPS, 2016.
S. G. Krantz and H. R. Parks. A Primer of Real Analytic Functions. Birkhäuser, Boston, second
edition, 2002.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional
neural networks. In NIPS, 2012.
Y. LeCun, B. Boser, J.S. Denker, D. Henderson, R.E. Howard, W. Hubbard, and L.D. Jackel. Handwritten digit recognition with a back-propagation network. In NIPS, 1990.
Y. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation, 2017.
arXiv:1705.09886.
S. Liang and R. Srikant. Why deep neural networks for function approximation? In ICLR, 2017.
R. Livni, S. Shalev-Shwartz, and O. Shamir. On the computational efficiency of training neural
networks. In NIPS, 2014.
A. Mahendran and A. Vedaldi. Understanding deep image representations by inverting them. In
CVPR, 2015.
H. Mhaskar and T. Poggio. Deep vs. shallow networks : An approximation theory perspective, 2016.
arXiv:1608.03287.
B. Mityagin. The zero set of a real analytic function, 2015. arXiv:1512.07276.
G. Montufar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural
networks. In NIPS, 2014.
11

Q. Nguyen and M. Hein. The loss surface of deep and wide neural networks. In ICML, 2017.
V. D. Nguyen. Complex powers of analytic functions and meromorphic renormalization in qft, 2015.
arXiv:1503.00995.
R. Pascanu, G. Montufar, and Y. Bengio. On the number of response regions of deep feedforward
networks with piecewise linear activations. In ICLR, 2014.
A. Paszke, A. Chaurasia, S. Kim, and E. Culurciello. Enet: A deep neural network architecture for
real-time semantic segmentation, 2016. arXiv:1606.02147.
T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda, and Q. Liao. Why and when can deep – but not
shallow – networks avoid the curse of dimensionality: a review, 2016. arXiv:1611.00740.
M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, and J. Sohl-Dickstein. On the expressive power of
deep neural networks. In ICML, 2017.
I. Safran and O. Shamir. On the quality of the initial basin in overspecified networks. In ICML,
2016.
I. Safran and O. Shamir. Depth-width tradeoffs in approximating natural functions with neural
networks. In ICML, 2017.
A. Saxe, P. W. Koh, Z. Chen, M. Bhand, B. Suresh, and A. Y. Ng. On random weights and unsupervised feature learning. In ICML, 2011.
H. Sedghi and A. Anandkumar. Provable methods for training neural networks with sparse connectivity. In ICLR Workshop, 2015.
S. Shalev-Shwartz, O. Shamir, and S. Shammah. Failures of gradient-based deep learning. In ICML,
2017.
O. Shamir. Distribution-specific hardness of learning neural networks, 2017. arXiv:1609.01037.
J. Sima. Training a single sigmoidal neuron is hard. Neural Computation, 14:2709–2728, 2002.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
M. Soltanolkotabi. Learning relus via gradient descent, 2017. arXiv:1705.04591.
D. Soudry and E. Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural
networks, 2017. arXiv:1702.05777.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In CVPR, 2015a.
C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture
for computer vision, 2015b. arXiv:1512.00567.
C. Szegedy, S. Ioffe, V. Vanhoucke, and A. Alemi. Inception-v4, inception-resnet and the impact of
residual connections on learning, 2016. arXiv:1602.07261.
M. Telgarsky. Representation benefits of deep feedforward networks, 2015. arXiv:1509.08101v2.
M. Telgarsky. Benefits of depth in neural networks. In COLT, 2016.
Y. Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In ICML, 2017.
D. Yarotsky. Error bounds for approximations with deep relu networks, 2016. arXiv:1610.01145.
J. Yosinski, J. Clune, Y. Bengio, and H. Lipson. How transferable are features in deep neural
networks? In NIPS, 2014.
12

J. Yosinski, J. Clune, A. Nguyen, T. Fuchs, and H. Lipson. Understanding neural networks through
deep visualization. In ICML, 2015.
C. Yun, S. Sra, and A. Jadbabaie. Global optimality conditions for deep neural networks, 2017.
arXiv:1707.02444.
M. D. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. In ECCV, 2014.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and Oriol Vinyals. Understanding deep learning requires
re-thinking generalization. In ICLR, 2017.
K. Zhong, Z. Song, P. Jain, P. Bartlett, and I. Dhillon. Recovery guarantees for one-hidden-layer
neural networks. In ICML, 2017.

A
A.1

M ISSING P ROOFS OF S ECTION 3
P ROOF OF L EMMA 3.3
• ReLU: It holds for every t < 0 that σ(t) = max(0, t) = 0 < et , and for t ≥ 0 that
σ(t) = t < t + 1. Thus ReLU satisfies the second condition of Assumption 3.2.
• Sigmoid: It holds that
lim

t→−∞

1
= 0,
1 + e−t

lim

t→∞

1
= 1.
1 + e−t

Thus σ satisfies the first condition of Assumption 3.2.
• Softplus: Since 1 + eαt ≤ 2eαt for every t ≥ 0, it holds for every t ≥ 0 that
0 ≤ σα (t) =

1
log(2)
1
log(1 + eαt ) ≤ log(2eαt ) =
+ t.
α
α
α

Moreover, since log(1 + t) ≤ t for t > 0, it holds log(1 + eαt ) ≤ eαt for every t ∈ R. Thus
αt
it holds that 0 ≤ σα (t) ≤ eα for every t < 0. Therefore σα satisfies the second condition
of Assumption 3.2 for ρ1 = 1/α, ρ2 = α, ρ3 = 1, ρ4 = log(2)/α.
A.2

P ROOF OF T HEOREM 3.4

To prove Theorem 3.4, we first show that Assumption 3.1 can be transported from the input to the
output layer.
Lemma A.1 Let Assumption 3.1 hold for the training sample. Consider a standard deep CNN
architecture which satisfies the following
1. The first layer is either convolutional or fully connected while all the other layers can be
convolutional, fully connected or max-pooling
2. (σ1 , . . . , σL ) are continuous and non-constant activation functions
Then for every layer 1 ≤ k ≤ L, there exist a set of parameters of the first k layers (Wl , bl )kl=1 such
that it holds fkp (xi ) 6= fkq (xj ) for every p, q ∈ [Pk ], i, j ∈ [N ], i 6= j. Moreover, (Wl , bl )kl=1 can
be chosen in such a way that, except for max-pooling layers, all the weight matrices Ul = Ml (Wl )
have full rank for every 1 ≤ l ≤ k.
Proof: Since Assumption 3.1 holds for the training inputs, one can first pick (W1 , b1 ) such that
Assumption 3.1 holds at the first layer. Then given that Assumption 3.1 is satisfied at the first layer,
the selection of the parameters of the higher layers can be done similarly.
Since our definition of a convolutional layer includes fully connected layer as a special case, it
is sufficient to prove the result for the general convolutional structure. Since the first layer is a
convolutional layer by our assumption, we denote by Q = [a1 , . . . , aT1 ] ∈ Rl0 ×T1 a matrix that
13

contains the set of convolutional filters of the first layer. Note here that there are T1 filters, namely

a1 , . . . , aT1 , where each filter at ∈ Rl0 for every t ∈ [T1 ]. Let us define the set
D 0
E
o
[ n

at , xpi − at , xqj = 0 .
Q ∈ Rl0 ×T1
S := Q ∈ Rl0 ×T1 M1 (Q) has low rank ∪
i6=j
p,q∈[P0 ]
t,t0 ∈[T1 ]

Basically, S is the set of “true” parameter matrices of the first layer where the corresponding weight
matrix M1 (Q) has low rank or there exists two patches of two different training samples that have
the same inner product with some corresponding two filters. By Assumption 3.1 it holds that xpi 6=
xqj for every p, q ∈ [P0 ], i 6= j, and thus the right hand side in the above formula of S is just the
union of a finite number of hyperplanes which has Lebesgue measure zero. For the left hand side,
it follows from Lemma 2.5 that the set of Q for which M1 (Q) does not have full rank has measure
zero. Thus the left hand side of S is a set of measure zero. Since S is the union of two measure zero
sets, it has also measure zero, and thus the complementary set Rl0 ×T1 \ S must be non-empty and
we choose W1 ∈ Rl0 ×T1 \ S.
Since σ1 is a continuous and non-constant function, there exists an interval (µ1 , µ2 ) such that σ1 is
bijective on (µ1 , µ2 ). We select and fix some matrix Q = [a1 , . . . , aT1 ] ∈ Rl0 ×T1 \ S and select
some β ∈ (µ1 , µ2 ). Let α > 0 be a free variable and W1 = [w11 , . . . , w1T1 ] where w1t denotes the
t-th filter of the first layer. Let us pick
w1t = αQ:t = αat ,

(b1 )h = β,

∀t ∈ [T1 ], h ∈ [n1 ].

It follows that W1 = αQ and thus M1 (W1 ) = M1 (αQ) = αM1 (Q) as M1 is a linear map by our
definition. Since Q ∈
/ S by construction, it holds that M1 (W1 ) has full rank for every α 6= 0. By
Definition 2.1, it holds for every i ∈ [N ], p ∈ [P0 ], t ∈ [T1 ], h = (p − 1)T1 + t that
f1 (xi )h = σ1 ( w1t , xpi + (b1 )h ) = σ1 (α at , xpi + β).
Since β ∈ (µ1 , µ2 ), one can choose a sufficiently small positive α such that it holds α ha, xpi i + β ∈
(µ1 , µ2 ) for every i ∈ [N ], p ∈ [P0 ], t ∈ [T1 ]. Under this construction, we will show that every entry
of f1 (xi ) must be different from every entry of f1 (xj ) for i 6= j. Indeed, let us compare f1 (xi )h
and f1 (xj )v for some h = (p − 1)T1 + t, v = (q − 1)T1 + t0 and i 6= j. It holds for sufficient small
α > 0 that
 D 0
E


f1 (xi )h − f1 (xj )v = σ1 α at , xpi + β − σ1 α at , xqj + β 6= 0
(8)
D 0
E
where the last inequality follows from three facts. First, it holds hat , xpi i =
6
at , xqj since Q ∈
/ S.
Second, for the chosen α the values of the arguments of the activation function σ1 lie within (µ1 , µ2 ).
Third, since σ1 is bijective on (µ1 , µ2 ), it maps different inputs to different outputs.
Now, since the entries of f1 (xi ) and that of f1 (xj ) are already pairwise different from each other,
their corresponding patches must be also different from each other no matter how the patches are
organized in the architecture, that is,
f1p (xi ) 6= f1q (xj ) ∀p, q ∈ [P1 ], i, j ∈ [N ], i 6= j.
Now, if the network has only one layer, i.e. L = 1, then we are done. Otherwise, we will prove via
induction that this property can be translated to any higher layer. In particular, suppose that one has
already constructed (Wl , bl )kl=1 so that it holds
fk (xi )h − fk (xj )v 6= 0 ∀h, v ∈ [nk ], i, j ∈ [N ], i 6= j.

(9)

This is true for k = 1 due to (8). We will show below that (9) can also hold at layer k + 1.
1. Case 1: Layer k + 1 is convolutional or fully connected.
Since (9) holds for k by our induction assumption, it must hold that
fkp (xi ) 6= fkq (xj ) ∀p, q ∈ [Pk ], i, j ∈ [N ], i 6= j.
which means Assumption 3.1 also holds for the set of features at layer k. Thus one can
follows the similar construction as done for layer 1 above by considering the output of
layer k as input to layer k + 1. Then one obtains that there exist (Wk+1 , bk+1 ) where
Uk+1 = Mk+1 (Wk+1 ) has full rank so that the similar inequality (8) now holds for layer
k + 1, which thus implies (9) holds for k + 1.
14

2. Case 2: layer k + 1 is max-pooling
By Definition 2.3, it holds nk+1 = Pk and one has for every p ∈ [Pk ]


fk+1 (x)p = max (fkp (x))1 , . . . , (fkp (x))lk .
Since (9) holds at layer k by our induction assumption, every entry of every patch of fk (xi )
must be different from every entry of every patch of fk (xj ) for every i 6= j, that is,
(fkp (xi ))r 6= (fkq (xj ))s for every r, s ∈ [lk ], p, q ∈ [Pk ], i 6= j. Therefore, their maximum elements cannot be the same, that is,
fk+1 (xi )p 6= fk+1 (xj )q

∀p, q ∈ [nk+1 ], i, j ∈ [N ], i 6= j.

which proves (9) for layer k + 1.
So far, we have proved that (9) holds for every 1 ≤ k ≤ L. Thus it follows that for every
layer k, there exists a set of parameters of the first k layers for which the patches at layer k of
different training samples are pairwise different from each other, that is, fkp (xi ) 6= fkq (xj ) for every
p, q ∈ [Pk ], i 6= j. Moreover, except for max-pooling layers, all the weight matrices up to layer k
have been chosen to have full rank.


Proof of Theorem 3.4 Let A = Fk = [fk (x1 )T , . . . , fk (xN )T ] ∈ RN ×nk . Since our definition
of a convolutional layer includes fully connected layer as a special case, it is sufficient to prove the
result for convolutional structure. By Theorem’s assumption, layer k is convolutional and thus it
holds by Definition 2.1 that


p
(xi ) + (bk )j
Aij = fk (xi )j = σ wkt , fk−1
for every i ∈ [N ], t ∈ [Tk ], p ∈ [Pk−1 ] and j = (p, t) := (p − 1)Tk + t ∈ [nk ].
In the following, we show that there exists a set of parameters of the network such that rank(A) = N
and all the weight matrices Ul = Ml (Wl ) have full rank.
First, one observes that the subnetwork consisting of all the layers from the input layer till layer
k − 1 satisfies the conditions of Lemma A.1. Thus by applying Lemma A.1 to this subnetwork,
one obtains that there exist (Wl , bl )k−1
which all the matrices (Ul )k−1
l=1 for
l=1 , except for max-pooling
p
q
layers, have full rank and it holds that fk−1
(xi ) 6= fk−1
(xj ) for every p, q ∈ [Pk−1 ], i 6= j. The
main idea now is to fix the parameters of these layers and pick (Wk , bk ) such that Uk = Mk (Wk )
has full rank and it holds rank(A) = N . Let us define the set
[ [ 
p
p
S=
a ∈ Rlk−1
a, fk−1
(xi ) − fk−1
(xj ) = 0 .
i6=j p∈[Pk−1 ]
p
p
From the above construction, it holds that fk−1
(xi ) 6= fk−1
(xj ) for every p ∈ [Pk−1 ], i 6= j, and
thus S is the union of a finite number of hyperplanes which thus has measure zero. Let us denote by
Q = [a1 , . . . , aTk ] ∈ Rlk−1 ×Tk a parameter matrix that contains all the convolutional filters of layer
k in its columns. Pick at ∈ Rlk−1 \ S for every t ∈ [Tk ], so that it holds that Uk = Mk (Q) has
full rank. Note here that such matrix Q always exists. Indeed, Q is chosen from a positive measure
set as its columns (i.e. at ) are picked from a positive measure set. Moreover, the set of matrices Q
for which Mk (Q) has low rank has just measure zero due to Lemma 2.5. Thus there always exists
at least one matrix Q so that all of its columns do not belong to S and that Mk (Q) has full rank.
In the rest of the proof, the value of matrix Q is fixed. Let α ∈ R be a free parameter. Since σk
is a continuous and non-constant function, there exist a β ∈ R such that σk (β) 6= 0. Let the value
of β be fixed as well. We construct the convolutional filters Wk = [wk1 , . . . , wkTk ] and the biases
bk ∈ Rnk of layer k as follows. For every p ∈ [Pk−1 ], t ∈ [Tk ], j = (p, t), we define

wkt = −αat ,
p
(bk )j = α at , fk−1
(xj ) + β.

It follows that Wk = −αQ and thus Uk = Mk (Wk ) = −αMk (Q) as Mk is a linear map.
Moreover, since Mk (Q) has full rank by construction, it holds that Uk has full rank for every
15

α 6= 0. As α varies, we get a family of matrices A(α) ∈ RN ×nk where it holds for every i ∈
[N ], j = (p, t) ∈ [nk ] that




p
p
p
A(α)ij = σk wkt , fk−1
(xi ) + (bk )j = σk α at , fk−1
(xj ) − fk−1
(xi ) + β .
(10)
Note that each row of A(α) corresponds to one training sample and that permutations of the rows of
A(α) do not change the rank of A(α). We construct a permutation γ of {1, 2, . . . , N } as follows.
For every j = 1, 2, . .l. , Nm, let (p, t) be the
by j (the inverse transformation for
l tuple
m determined

j
j
given j ∈ [nk ] is p = Tk and t = j −
Tk − 1 Tk ) and define
γ(j) =

arg min
i∈{1,2,...,N } \ {γ(1),...,γ(j−1)}

p
at , fk−1
(xi ) .

Note that γ(j) is unique for every 1 ≤ j ≤ N since at ∈
/ S. It is clear that γ constructed as above
is a permutation of {1, 2, . . . , N } since at every step we take a different element from the index set
[N ]. From the definition of γ(j), it holds that for every j = (p, t) ∈ [N ], i ∈ [N ], i > j that
p
p
at , fk−1
(xγ(j) ) < at , fk−1
(xγ(i) ) .

We can relabel the training data according to the permutation so that w.l.o.g we can assume that γ
is the identity permutation, that is, γ(j) = j for every j ∈ [N ], in which case it holds for every
j = (p, t) ∈ [N ], i ∈ [N ], i > j that
p
p
at , fk−1
(xj ) < at , fk−1
(xi ) .

(11)

Under the above construction of (Wl , bl )kl=1 , we are ready to show that there exist α for which
rank(A(α)) = N. Since σk satisfies Assumption 3.2, we consider the following cases.
1. Case 1: There are finite constants µ+ , µ− ∈ R s.t. lim σk (t) = µ− and lim σk (t) = µ+
t→−∞

t→∞

and µ+ µ− = 0.
Let us consider the first case where µ− = 0. From (10) and (11) one obtains

j=i
σk (β)
lim A(α)ij = µ− = 0 i > j
α→+∞

ηij
i<j

(12)

where ηij is given for every i < j where j = (p, t) as

p
p
µ− , at , fk−1
(xj ) − fk−1
(xi ) < 0
ηij =
p
p
µ+ , at , fk−1 (xj ) − fk−1
(xi ) > 0
Note that ηij cannot be zero for i 6= j because at ∈
/ S. In the following, let us denote
A(α)1:N,1:N as a sub-matrix of A(α) that consists of the first N rows and columns. By the
Leibniz-formula one has
det(A(α)1:N,1:N ) = σk (β)N +

X

sign(π)

π∈SN \{γ}

N
Y

A(α)π(j)j

(13)

j=1

where SN is the set of all N ! permutations of the set {1, . . . , N } and γ is the identity
permutation. Now, one observes that for every permutation π 6= γ, there always exists at
least one component j where π(j) > j in which case it follows from (12) that
lim

α→∞

N
Y

A(α)π(j)j = 0.

j=1

Since there are only finitely many such terms in (13), one obtains
lim det(A(α)1:N,1:N ) = σk (β)N 6= 0

α→∞

where the last inequality follows from our choice of β. Since det(A(α)1:N,1:N ) is
a continuous function of α, there exists α0 ∈ R such that for every α ≥ α0 it
16

holds det(A(α)1:N,1:N ) 6= 0 and thus rank(A(α)1:N,1:N ) = N which further implies
rank(A(α)) = N. Thus the corresponding set of feature vectors {fk (x1 ), . . . , fk (xN )} are
linearly independent.
For the case where µ+ = 0, one can argue similarly. The only difference is that one
considers now the limit for α → −∞. In particular, (10) and (11) lead to

i=j
σk (β)
lim A(α)ij = µ+ = 0 i > j
α→−∞

ηij = 0 i < j.
For every permutation π 6= γ there always exists at least one component j where π(j) > j,
in which case it holds that
lim

α→−∞

N
Y

A(α)π(j)j = 0.

j=1

and thus it follows from the Leibniz formula that
lim det(A(α)1:N,1:N ) = σk (β)N 6= 0.

α→−∞

Since det(A(α)1:N,1:N ) is a continuous function of α, there exists α0 ∈ R such that for
every α ≤ α0 it holds det(A(α)1:N,1:N ) 6= 0 and thus rank(A(α)1:N,1:N ) = N which
further implies rank(A(α)) = N. Thus the set of feature vectors at layer k are linearly
independent.
2. Case 2: There are positive constants ρ1 , ρ2 , ρ3 , ρ4 s.t. |σk (t)| ≤ ρ1 eρ2 t for t < 0 and
|σk (t)| ≤ ρ3 t + ρ4 for t ≥ 0.
Our proof strategy is essentially similar to the previous case. Indeed, for every permutation
π 6= γ there always exist at least one component j = (p, t) ∈ [N ] where π(j) > j in which
p
p
case δj := at , fk−1
(xj ) − fk−1
(xπ(j) ) < 0 due to (11). For sufficiently large α > 0, it
holds that αδj + β < 0 and thus one obtains from (10) that
|A(α)π(j)j | = |σk (αδj + β)| ≤ ρ1 eρ2 β e−αρ2 |δj | .
If π(j) = j then |A(α)π(j)j | = |σk (β)| which is a constant. For π(j) < j, one notices
p
p
that δj := at , fk−1
(xj ) − fk−1
(xπ(j) ) can only be either positive or negative as at ∈
/ S.
In this case, if δj < 0 then it can be bounded by the similar exponential term as above for
sufficiently large α. Otherwise it holds αδj + β > 0 for sufficiently large α > 0 and we get
|A(α)π(j)j | = |σ(αδj + β)| ≤ ρ3 δj α + ρ3 β + ρ4 .
Overall, for sufficiently large α > 0, there must exist positive constants P, Q, R, S, T such
that it holds for every π ∈ SN \ {γ} that
N
Y

A(α)π(j)j ≤ R(P α + Q)S e−αT .

j=1

The upper bound goes to zero as α goes to ∞. This combined with the Leibniz formula
from (13), we get limα→∞ det(A(α)1:N,1:N ) = σk (β)N 6= 0. Since det(A(α)1:N,1:N )
is a continuous function of α, there exists α0 ∈ R such that for every α ≥ α0 it holds
det(A(α)1:N,1:N ) 6= 0 and thus rank(A(α)1:N,1:N ) = N which implies rank(A(α)) = N.
Thus the set of feature vectors at layer k are linearly independent.
Overall, we have shown that there always exist (Wl , bl )kl=1 such that the set of feature vectors
{fk (x1 ), . . . , fk (xN )} at layer k are linearly independent. Moreover, (Wl , bl )kl=1 have been chosen
so that all the weight matrices Ul = Ml (Wl ), except for max-pooling layers, have full rank for
every 1 ≤ l ≤ k.
A.3

P ROOF OF T HEOREM 3.5

To prove Theorem 3.5, the following key property of real analytic functions is required.
17

Lemma A.2 Nguyen (2015); Mityagin (2015) If f : Rn → R is a real analytic function which is
not identically zero then the set {x ∈ Rn | f (x) = 0} has Lebesgue measure zero.
Any linear function is real analytic and the set of real analytic functions is closed under addition,
multiplication and composition, see e.g. Prop. 2.2.2 and Prop. 2.2.8 in Krantz & Parks (2002).
As we assume that all the activation functions of the first k layers are real analytic, we get that
the function fk is a real analytic function of (Wl , bl )kl=1 as it is the composition of real analytic
functions. Now, we recall from our definition that Fk = [fk (x1 ), . . . , fk (xN )]T ∈ RN ×nk is the
output matrix at layer k for all training samples. One observes that the set of low rank matrices
Fk can be characterized by a system of equations such that all the nNk determinants of all N × N
sub-matrices of Fk are zero. As the determinant is a polynomial in the entries of the matrix and
thus an analytic function of the entries and composition of analytic functions are again analytic, we
conclude that each determinant is an analytic function of the network parameters of the first k layers.
By Theorem 3.4, there exists at least one set of parameters of the first k layers such that one of these
determinant functions is not identically zero and thus by Lemma A.2, the set of network parameters
where this determinant is zero has Lebesgue measure zero. But as all sub-matrices need to have low
rank in order that rank(Fk ) < N , it follows that the set of parameters where rank(Fk ) < N has
Lebesgue measure zero.

B
B.1

M ISSING P ROOFS OF S ECTION 4
P ROOF OF L EMMA 4.3

To prove Lemma 4.3, we first derive standard backpropagation in Lemma B.1. In the following
we use the Hadamard product ◦, which for A, B ∈ Rm×n is defined as A ◦ B ∈ Rm×n with
∂Φ
(A ◦ B)ij = Aij Bij . Let δkj (xi ) = ∂gkj
(xi ) be the derivative of Φ w.r.t. the value of unit j at layer
k evaluated at a single sample xi . We arrange these vectors for all training samples into a single
matrix ∆k = [δk: (x1 ), . . . , δk: (xN )]T ∈ RN ×nk . The following lemma is a slight modification of
Lemma 2.1 in (Nguyen & Hein, 2017) for which we provide the proof for completeness.
Lemma B.1 Given some hidden layer 1 ≤ k ≤ L − 1. Let (σk+1 , . . . , σL−1 ) be differentiable.
Then the following hold:

FL − Y,
l=L
1. ∆l =
T
(∆l+1 Ul+1
) ◦ σl0 (Gl ), k + 1 ≤ l ≤ L − 1
T
2. ∇Ul Φ = Fl−1
∆l , ∀ k + 1 ≤ l ≤ L

Proof:
1. By definition, it holds for every i ∈ [N ], j ∈ [nL ] that
∂Φ
(∆L )ij = δLj (xi ) =
= fLj (xi ) − yij
∂gLj (xi )
and hence, ∆L = FL − Y.
For every k + 1 ≤ l ≤ L − 1, the output of the network for a single training sample can
be written as the composition of differentiable functions (i.e. the outputs of all layers from
l + 1 till the output layer), and thus the chain rule yields for every i ∈ [N ], j ∈ [nl ] that
(∆l )ij = δlj (xi ) =

nl+1
X
∂g(l+1)s (xi ) ∂flj (xi )
∂Φ
∂Φ
=
∂glj (xi )
∂g
(x
)
∂flj (xi ) ∂glj (xi )
i
(l+1)s
s=1
nl+1

=

X

δ(l+1)s (xi )(Ul+1 )js σ 0 (glj (xi ))

s=1
nl+1

=

X
s=1

and hence ∆l =

T
(∆l+1 Ul+1
)

0

◦ σ (Gl ).
18

T

(∆(l+1) )is (Ul+1 )sj σ 0 ((Gl )ij )

2. For every k + 1 ≤ l ≤ L − 1, r ∈ [nl−1 ], s ∈ [nl ], one has
N

N

N

X ∂Φ ∂gls (xi ) X
X
∂Φ
T
=
=
δls (xi )f(l−1)r (xi ) =
(Fl−1
)ri (∆l )is
∂(Ul )rs
∂g
(x
)
∂(U
)
ls
i
l
rs
i=1
i=1
i=1

T
= Fl−1
∆l rs
T
and hence ∇Ul Φ = Fl−1
∆l .


The following straightforward inequalities are also helpful to prove Lemma 4.3. Let λmin (·) and
λmax (·) denotes the smallest and largest eigenvalue of a matrix.
Lemma B.2 Let A ∈ Rm×n with m ≥ n. Then it holds σmax (A) kxk2 ≥ kAxk2 ≥ σmin (A) kxk2
for every x ∈ Rn .
q
p
T T
kAxk
Proof: Since m ≥ n, it holds that σmin (A) = λmin (AT A) = min x xAT xAx = min kxk 2
2
p
kAxk
and thus σmin (A) ≤ kxk 2 for every x ∈ Rn . Similarly, it holds σmax (A) = λmax (AT A) =
2
q
T T
kAxk
kAxk
max x xAT xAx = max kxk 2 and thus σmax (A) ≥ kxk 2 for every x ∈ Rn .

2

2

Lemma B.3 Let A ∈ Rm×n , B ∈ Rn×p with m ≥ n. Then it holds σmax (A) kBkF ≥ kABkF ≥
σmin (A) kBkF .
Proof: Since m ≥ n, it holds that λmin (AT A) = σmin (A)2 and λmax (AT A) = σmax (A)2 . Thus
2
2
we have kABkF = tr(B T AT AB) ≥ λmin (AT A) tr(B T B) = σmin (A)2 kBkF . Similarly, it holds
2
2
kABkF = tr(B T AT AB) ≤ λmax (AT A) tr(B T B) = σmax (A)2 kBkF .


Proof of Lemma 4.3 We first prove the lower bound. Let Im denotes an m-by-m identity matrix
and ⊗ the Kronecker product. From Lemma B.1 it holds ∇Uk+1 Φ = FLT ∆k+1 and thus
vec(∇Uk+1 Φ) = (Ink+1 ⊗ FkT ) vec(∆k+1 ).
It follows that
∇Uk+1 Φ F = (Ink+1 ⊗ FkT ) vec(∆k+1 )

2

≥ σmin (Fk ) kvec(∆k+1 )k2 = σmin (Fk ) k∆k+1 kF
(14)

where the inequality follows from Lemma B.2 for the matrix (Ink+1 ⊗ FkT ) ∈ Rnk nk+1 ×N nk+1 with
nk ≥ N by Assumption 4.1. Using Lemma B.1 again, one has
T
0
k∆k+1 kF = (∆k+2 Uk+2
) ◦ σk+1
(Gk+1 )
0
≥ σk+1
(Gk+1 )

F

min

T
∆k+2 Uk+2

0
= σk+1
(Gk+1 )

min

Uk+2 ∆Tk+2

0
≥ σk+1
(Gk+1 )

σ (Uk+2 ) k∆k+2 kF
min min

F
F

where the last inequality follows from Lemma B.3 for the matrices Uk+2 ∈ Rnk+1 ×nk+2 and ∆Tk+2
with nk+1 ≥ nk+2 by Assumption 4.1. By repeating this for k∆k+2 kF , . . . , k∆L−1 kF , one gets
k∆k+1 kF ≥

 L−1
Y


 L−1

Y
kσl0 (Gl )kmin σmin (Ul+1 ) k∆L kF =
kσl0 (Gl )kmin σmin (Ul+1 ) kFL − Y kF

l=k+1

l=k+1

(15)
From (14), (15), one obtains
∇Uk+1 Φ

F

 L−1

Y
≥ σmin (Fk )
kσl0 (Gl )kmin σmin (Ul+1 ) kFL − Y kF
l=k+1

19

which proves the lower bound.
The proof for upper bound is similar. Indeed one has
∇Uk+1 Φ

F

= (Ink+1 ⊗ FkT ) vec(∆k+1 )

2

≤ σmax (Fk ) kvec(∆k+1 )k2 = σmax (Fk ) k∆k+1 kF
(16)

where the inequality follows from Lemma B.2 Now, one has
T
0
k∆k+1 kF = (∆k+2 Uk+2
) ◦ σk+1
(Gk+1 )

≤
=
≤

0
σk+1
(Gk+1 ) max
0
σk+1 (Gk+1 ) max
0
σk+1
(Gk+1 ) max

F
T
∆k+2 Uk+2 F
Uk+2 ∆Tk+2 F

σmax (Uk+2 ) k∆k+2 kF

where the last inequality follows from Lemma B.3. By repeating this chain of inequalities for
k∆k+2 kF , . . . , k∆L−1 kF , one obtains:
k∆k+1 kF ≤

 L−1
Y


 L−1

Y
kσl0 (Gl )kmax σmax (Ul+1 ) k∆L kF =
kσl0 (Gl )kmax σmax (Ul+1 ) kFL − Y kF .

l=k+1

l=k+1

(17)
From (16), (17), one obtains that
∇Uk+1 Φ

F


 L−1
Y
kσl0 (Gl )kmax σmax (Ul+1 ) kFL − Y kF
≤ σmax (Fk )
l=k+1

which proves the upper bound.
B.2

P ROOF OF T HEOREM 4.5
1. Since layer k + 1 is fully connected, it holds at every critical point in Sk that ∇Wk+1 Φ =
0 = ∇Uk+1 Φ. This combined with Theorem 4.4 yields the result.
L
2. One
 basically needs to show that there exist (Wl , bl )l=1 such that it holds:
L
Φ (Wl , bl )l=1 = 0, rank(Fk ) = N and Ul = Ml (Wl ) has full rank ∀l ∈ [k + 2, L]

Note that the last two conditions are fulfilled by the fact that (Wl , bl )L
l=1 ∈ Sk .
By Assumption 4.1, the subnetwork consisting of the first k layers satisfies the condition of
Theorem 3.4. Thus by applying Theorem 3.4 to this subnetwork, one obtains that there exist
(Wl , bl )kl=1 such that rank(Fk ) = N . In the following, we fix these layers and show how
to pick (Wl , bl )L
l=k+1 such that FL = Y. The main idea now is to make the output of all the
training samples of the same class become identical at layer k + 1 and thus they will have
the same network output. Since there are only m classes, there would be only m distinct
outputs for all the training samples at layer L − 1. Thus if one can make these m distinct
outputs become linearly independent at layer L−1 then there always exists a weight matrix
WL that realizes the target output Y as the last layer is just a linear map by assumption.
Moreover, we will show that, except for max-pooling layers, all the parameters of other
layers in the network can be chosen in such a way that all the weight matrices (Ul )L
l=k+2
achieve full rank. Our proof details are as follows.
Case 1: k = L − 1
T
T
It holds rank(FL−1 ) = N. Pick bL = 0 and WL = FL−1
(FL−1 FL−1
)−1 Y .
Since the output layer is fully connected, it follows from Definition 2.2 that
FL = FL−1 WL + 1N bTL = Y. Since rank(Fk ) = N and the full rank condition on
L
(Wl )L
/ Sk which finishes the
l=k+2 is not active when k = L − 1, it holds that (Wl , bl )l=1 ∈
proof.
Case 2: k = L − 2
It holds rank(FL−2 ) = N. Let A ∈ Rm×nL−1 be a full row rank matrix such that Aij ∈
range(σL−1 ). Note that nL−1 ≥ nL = m due to Assumption 4.1. Let D ∈ RN ×nL−1
20

be a matrix satisfying Di: = Aj: whenever xi belongs to class j for every i ∈ [N ], j ∈
[m]. By construction, FL−2 has full row rank, thus we can pick bL−1 = 0, WL−1 =
−1
T
T
FL−2
(FL−2 FL−2
)−1 σL−1
(D). Since layer L − 1 is fully connected by assumption, it
follows from Definition 2.2 that FL−1 = σL−1 (FL−2 WL−1 + 1N bTL−1 ) = D and thus
(FL−1 )i: = Di: = Aj: whenever xi belongs to class j.
So far, our construction of the first L − 1 layers has led to the fact that all the training
samples belonging to the same class will have identical output at layer L − 1. Since A has
full row rank by construction, we can pick for the last layer bL = 0, WL = AT (AAT )−1 Z
where Z ∈ Rm×m is our class embedding matrix with rank(Z) = m. One can easily check
that AWL = Z and that FL = FL−1 WL + 1N bTL = FL−1 WL where the later follows from
Definition 2.2 as the output layer is fully connected. Now one can verify that FL = Y.
Indeed, whenever xi belongs to class j one has
(FL )i: = (FL−1 )Ti: WL = (A)Tj: WL = Zj: = Yi: .
−1
Moreover, since rank(Fk ) = N and rank(WL ) = rank(AT (AAT )
Z) = m, it holds that
L
(Wl , bl )L
/ Sk . Therefore, there exists (Wl , bl )L
l=1 ∈
l=1 ∈ Sk with Φ (Wl , bl )l=1 = 0.

Case 3: k ≤ L − 3
It holds rank(Fk ) = N. Let E ∈ Rm×nk+1 be any matrix such that Eij ∈ range(σk+1 )
and Eip 6= Ejq for every 1 ≤ i 6= j ≤ N, 1 ≤ p, q ≤ nk+1 . Let D ∈ RN ×nk+1 satisfies
−1
Di: = Ej: for every xi from class j. Pick bk+1 = 0, Wk+1 = FkT (Fk FkT )−1 σk+1
(D).
Note that the matrix is invertible as Fk has been chosen to have full row rank. Since layer
k + 1 is fully connected by our assumption, it follows from Definition 2.2 that Fk+1 =
σk+1 (Fk Wk+1 + 1N bTk+1 ) = σk+1 (Fk Wk+1 ) = D and thus it holds
(Fk+1 )i: = Di: = Ej:

(18)

for every xi from class j.
So far, our construction has led to the fact that all training samples belonging to the same
class have identical output at layer k + 1. The idea now is to see E as a new training
data matrix of a subnetwork consisting of all layers from k + 1 till the output layer L. In
particular, layer k + 1 can be seen as the input layer of this subnetwork and similarly, layer
L can be seen as the output layer. Moreover, every row of E ∈ Rm×nk+1 can be seen as
a new training sample to this subnetwork. One can see that this subnet together with the
training data matrix E satisfy the conditions of Theorem 3.4 at the last hidden layer L − 1.
In particular, it holds that
• The rows of E ∈ Rm×nk+1 are componentwise different from each other, and thus the
input patches must be also different from each other, and thus E satisfies Assumption
3.1
• Every layer from k +1 till L−1 is convolutional or fully connected due to Assumption
4.1
• The width of layer L − 1 is larger than the number of samples due to Assumption 4.1,
that is, nL−1 ≥ nL = m
• (σk+2 , . . . , σL−1 ) satisfy Assumption 3.2 due to Assumption 4.1
By applying Theorem 3.4 to this subnetwork and training data E, we obtain that there must
L−1
exist (Wl , bl )L−1
l=k+2 for which all the weight matrices (Ul )l=k+2 have full rank such that
the set of corresponding m outputs at layer L − 1 are linearly independent. In particular,
let A ∈ Rm×nL−1 be the corresponding outputs of E through this subnetwork then it holds
that rank(A) = m. Intuitively, if one feeds Ej: as an input at layer k + 1 then one would
get Aj: as an output at layer L − 1. This combined with (18) leads to the fact that if one
now feeds (Fk+1 )i: = Ej: as an input at layer k + 1 then one would get at layer L − 1 the
output (FL−1 )i: = Aj: whenever xi belongs to class j.
Last, we pick bL = 0, WL = AT (AAT )−1 Z. It follows that AWL = Z. Since the output
layer L is fully connected, it holds from Definition 2.2 that FL = FL−1 WL + 1N bTL =
FL−1 WL .
21

One can verify now that FL = Y. Indeed, for every sample xi from class j it holds that
(FL )i: = (FL−1 )Ti: WL = ATj: WL = Zj: = Yi: .
Overall, we have shown that Φ = 0. In addition, it holds rank(Fk ) = N from the conL−1
struction of the first k layers. All the matrices (Ul )l=k+2
have full rank by the construction of the subnetwork from k + 1 till L. Moreover, UL = WL also has full rank since
rank(WL ) = rank(AT (AAT )−1 Z) = m. Therefore it holds (Wl , bl )L
l=1 ∈ Sk .
B.3

P ROOF OF C OROLLARY 4.6

It is clear that the network structure satisfies the conditions of Theorem 4.4 as every layer is fully
connected. Moreover, the input patches also satisfy Assumption 3.1 because every input patch is
simply one training sample in this case but since there are no identical training samples, one derives
that the input patches must be different from each other.
Since all the conditions of Theorem 4.4 are met, the application of Theorem 4.4 yields the result.

22

