On the Expressive Power of Deep Learning: A Tensor Analysis
Nadav Cohen
Or Sharir
Amnon Shashua

COHENNADAV @ CS . HUJI . AC . IL
OR . SHARIR @ CS . HUJI . AC . IL
SHASHUA @ CS . HUJI . AC . IL

arXiv:1509.05009v3 [] 27 May 2016

The Hebrew University of Jerusalem

Abstract
It has long been conjectured that hypotheses spaces suitable for data that is compositional in
nature, such as text or images, may be more efficiently represented with deep hierarchical networks
than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical
justifications to date are limited. In particular, they do not account for the locality, sharing and
pooling constructs of convolutional networks, the most successful deep learning architecture to
date. In this work we derive a deep network architecture based on arithmetic circuits that inherently
employs locality, sharing and pooling. An equivalence between the networks and hierarchical
tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1)
decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using
tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions
that can be implemented by a deep network of polynomial size, require exponential size in order to
be realized (or even approximated) by a shallow network. Since log-space computation transforms
our networks into SimNets, the result applies directly to a deep learning architecture demonstrating
promising empirical performance. The construction and theory developed in this paper shed new
light on various practices and ideas employed by the deep learning community.
Keywords: Deep Learning, Expressive Power, Arithmetic Circuits, Tensor Decompositions

1. Introduction
The expressive power of neural networks is achieved through depth. There is mounting empirical
evidence that for a given budget of resources (e.g. neurons), the deeper one goes, the better the
eventual performance will be. However, existing theoretical arguments that support this empirical
finding are limited. There have been many attempts to theoretically analyze function spaces generated by network architectures, and their dependency on network depth and size. The prominent
approach for justifying the power of depth is to show that deep networks can efficiently express
functions that would require shallow networks to have super-polynomial size. We refer to such
scenarios as instances of depth efficiency. Unfortunately, existing results dealing with depth efficiency (e.g. Hastad (1986); Håstad and Goldmann (1991); Delalleau and Bengio (2011); Martens
and Medabalimi (2014)) typically apply to specific network architectures that do not resemble ones
commonly used in practice. In particular, none of these results apply to convolutional networks
(LeCun and Bengio (1995)), which represent the most empirically successful and widely used deep
learning architecture to date. A further limitation of current results is that they merely show existence of depth efficiency (i.e. of functions that are efficiently realizable with a certain depth but
cannot be efficiently realized with shallower depths), without providing any information as to how
frequent this property is. These shortcomings of current theory are the ones that motivated our work.
c N. Cohen, O. Sharir & A. Shashua.

C OHEN S HARIR S HASHUA

The architectural features that specialize convolutional networks compared to classic feedforward fully-connected networks are threefold. The first feature, locality, refers to the connection
of a neuron only to neighboring neurons in the preceding layer, as opposed to having the entire
layer drive it. In the context of image processing (the most common application of convolutional
networks), locality is believed to reflect the inherent compositional structure of data – the closer
pixels are in an image, the more likely they are to be correlated. The second architectural feature of
convolutional networks is sharing, which means that different neurons in the same layer, connected
to different neighborhoods in the preceding layer, share the same weights. Sharing, which together
with locality gives rise to convolution, is motivated by the fact that in natural images, the semantic
meaning of a pattern often does not depend on its location (i.e. two identical patterns appearing in
different locations of an image often convey the same semantic content). Finally, the third architectural idea of convolutional networks is pooling, which is essentially an operator that decimates
layers, replacing neural activations in a spatial window by a single value (e.g. their maximum or
average). In the context of images, pooling induces invariance to translations (which often do not
affect semantic content), and in addition is believed to create a hierarchy of abstraction in the patterns neurons respond to. The three architectural elements of locality, sharing and pooling, which
have facilitated the great success of convolutional networks, are all lacking in existing theoretical
studies of depth efficiency.
In this paper we introduce a convolutional arithmetic circuit architecture that incorporates locality, sharing and pooling. Arithmetic circuits (also known as Sum-Product Networks, Poon and
Domingos (2011)) are networks with two types of nodes: sum nodes, which compute a weighted
sum of their inputs, and product nodes, computing the product of their inputs. We use sum nodes to
implement convolutions (locality with sharing), and product nodes to realize pooling. The models
we arrive at may be viewed as convolutional networks with product pooling and linear point-wise activation. They are attractive on three accounts. First, as discussed in app. E, convolutional arithmetic
circuits are equivalent to SimNets, a new deep learning architecture that has recently demonstrated
promising empirical results on various image recognition benchmarks (Cohen et al. (2016)). Second, as we show in sec. 3, convolutional arithmetic circuits are realizations of hierarchical tensor
decompositions (see Hackbusch (2012)), opening the door to various mathematical and algorithmic
tools for their analysis and implementation. Third, the depth efficiency of convolutional arithmetic
circuits, which we analyze in sec. 4, was shown in the subsequent work of Cohen and Shashua
(2016) to be superior to the depth efficiency of the popular convolutional rectifier networks, namely
convolutional networks with rectified linear (ReLU) activation and max or average pooling.
Employing machinery from measure theory and matrix algebra, made available through their
connection to hierarchical tensor decompositions, we prove a number of fundamental results concerning the depth efficiency of our convolutional arithmetic circuits. Our main theoretical result
(thm. 1 and corollary 2) states that besides a negligible (zero measure) set, all functions that can
be realized by a deep network of polynomial size, require exponential size in order to be realized,
or even approximated, by a shallow network. When translated to the viewpoint of tensor decompositions, this implies that almost all tensors realized by Hierarchical Tucker (HT) decomposition
(Hackbusch and Kühn (2009)) cannot be efficiently realized by the classic CP (rank-1) decomposition. To the best of our knowledge, this result is unknown to the tensor analysis community, in
which the advantage of HT over CP is typically demonstrated through specific examples of tensors
that can be efficiently realized by the former and not by the latter. Following our main result, we
present a generalization (thm. 3 and corollary 4) that compares networks of arbitrary depths, show2

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

ing that the amount of resources one has to pay in order to maintain representational power while
trimming down layers of a network grows double exponentially w.r.t. the number of layers cut off.
We also characterize cases in which dropping a single layer bears an exponential price.
The remainder of the paper is organized as follows. In sec. 2 we briefly review notations and
mathematical background required in order to follow our work. This is followed by sec. 3, which
presents our convolutional arithmetic circuits and establishes their equivalence with tensor decompositions. Our theoretical analysis is covered in sec. 4. Finally, sec. 5 concludes. In order to keep
the manuscript at a reasonable length, we defer our detailed survey of related work to app. D, covering works on the depth efficiency of boolean circuits, arithmetic circuits and neural networks, as
well as different applications of tensor analysis in the field of deep learning.

2. Preliminaries
We begin by establishing notational conventions that will be used throughout the paper. We denote
vectors using bold typeface, e.g. v ∈ Rs . The coordinates of such a vector are referenced with
regular typeface and a subscript, e.g. vi ∈ R. This is not to be confused with bold typeface and a
subscript, e.g. vi ∈ Rs , which represents a vector that belongs to some sequence. Tensors (multidimensional arrays) are denoted by the letters “A” and “B” in calligraphic typeface, e.g. A, B ∈
RM1 ×···×MN . A specific entry in a tensor will be referenced with subscripts, e.g. Ad1 ...dN ∈ R.
Superscripts will be used to denote individual objects within a collection. For example, v(i) stands
for vector i and Ay stands for tensor y. In cases where the collection of interest is indexed by
multiple coordinates, we will have multiple superscripts referencing individual objects, e.g. al,j,γ
will stand for vector (l, j, γ). As shorthand for the Cartesian product of the Euclidean space Rs with
itself N times, we will use the notation (Rs )N . Finally, for a positive integer k we use the shorthand
[k] to denote the set {1, . . . , k}.
We now turn to establish a baseline, i.e. to present basic definitions and results, in the broad and
comprehensive field of tensor analysis. We list here only the essentials required in order to follow
the paper, referring the interested reader to Hackbusch (2012) for a more complete introduction to
the field 1 . The most straightforward way to view a tensor is simply as a multi-dimensional array:
Ad1 ,...,dN ∈ R where i ∈ [N ], di ∈ [Mi ]. The number of indexing entries in the array, which are
also called modes, is referred to as the order of the tensor. The term dimension stands for the number
of values an index can take in a particular mode. For example, the tensor A appearing above has
order N and dimension Mi in mode i, i ∈ [N ]. The space of all possible configurations A can take
is called a tensor space and is denoted, quite naturally, by RM1 ×···×MN .
A central operator in tensor analysis is the tensor product, denoted ⊗. This operator intakes
two tensors A and B of orders P and Q respectively, and returns a tensor A ⊗ B of order P + Q,
defined by: (A ⊗ B)d1 ...dP +Q = Ad1 ...dP · BdP +1 ...dP +Q . Notice that in the case P = Q = 1, the
tensor product reduces to an outer product between vectors. Specifically, v ⊗ u – the tensor product
between u ∈ RM1 and v ∈ RM2 , is no other than the rank-1 matrix vu> ∈ RM1 ×M2 . In this
(i) to denote the joint tensor product v(1) ⊗· · ·⊗v(N ) .
context, we will often use the shorthand ⊗N
i=1 v
N
(i)
Tensors of the form ⊗i=1 v are called pure or elementary, and are regarded as having rank-1
(assuming v(i) 6= 0 ∀i). It is not difficult to see that any tensor can be expressed as a sum of rank-1
1. The definitions we give are concrete special cases of the more abstract algebraic definitions given in Hackbusch
(2012). We limit the discussion to these special cases since they suffice for our needs and are easier to grasp.

3

C OHEN S HARIR S HASHUA

tensors:
A=

Z
X

vz(1) ⊗ · · · ⊗ vz(N )

, vz(i) ∈ RMi

(1)

z=1

A representation as above is called a CANDECOMP/PARAFAC decomposition of A, or in short,
a CP decomposition 2 . The CP-rank of A is defined as the minimum number of terms in a CP
decomposition, i.e. as the minimal Z for which eq. 1 can hold. Notice that for a tensor of order 2,
i.e. a matrix, this definition of CP-rank coincides with that of standard matrix rank.
A symmetric tensor is one that is invariant to permutations of its indices. Formally, a tensor A of order N which is symmetric will have equal dimension M in all modes, and for every permutation π : [N ] → [N ] and indices d1 . . .dN ∈ [M ], the following equality will hold:
M ×···×M is
Adπ(1) ...dπ(N ) = Ad1 ...dN . Note that for a vector v ∈ RM , the tensor ⊗N
i=1 v ∈ R
symmetric. Moreover, every symmetric
tensor may be expressed as a linear combination of such
P
(symmetric rank-1) tensors: A = Z
λ
z=1 z · vz ⊗ · · · ⊗ vz . This is referred to as a symmetric CP
decomposition, and the symmetric CP-rank is the minimal Z for which such a decomposition exists.
Since a symmetric CP decomposition is in particular a standard CP decomposition, the symmetric
CP-rank of a symmetric tensor is always greater or equal to its standard CP-rank. Note that for the
case of symmetric matrices (order-2 tensors) the symmetric CP-rank and the original CP-rank are
always equal.
A repeating concept in this paper is that of measure zero. More broadly, our analysis is framed
in measure theoretical terms. While an introduction to the field is beyond the scope of the paper (the
interested reader is referred to Jones (2001)), it is possible to intuitively grasp the ideas that form the
basis to our claims. When dealing with subsets of a Euclidean space, the standard and most natural
measure in a sense is called the Lebesgue measure. This is the only measure we consider in our
analysis. A set of (Lebesgue) measure zero can be thought of as having zero “volume” in the space
of interest. For example, the interval between (0, 0) and (1, 0) has zero measure as a subset of the
2D plane, but has positive measure as a subset of the 1D x-axis. An alternative way to view a zero
measure set S follows the property that if one draws a random point in space by some continuous
distribution, the probability of that point hitting S is necessarily zero. A related term that will be
used throughout the paper is almost everywhere, which refers to an entire space excluding, at most,
a set of zero measure.

3. Convolutional Arithmetic Circuits
We consider the task of classifying an instance X = (x1 , . . . , xN ), xi ∈ Rs , into one of the
categories Y := {1, . . . , Y }. Representing instances as collections of vectors is natural in many
applications. In the case of image processing for example, X may correspond to an image, and
x1 . . . xN may correspond to vector arrangements of (possibly overlapping) patches around pixels. As customary, classification is carried out through maximization of per-label score functions {hy }y∈Y , i.e. the predicted label for the instance X will be the index y ∈ Y for which the
score value hy (X) is maximal. Our attention is thus directed to functions over the instance space
X := {(x1 , . . . , xN ) : xi ∈ Rs } = (Rs )N . We define our hypotheses space through the following
2. CP decomposition is regarded as the classic and most basic tensor decomposition, dating back to the beginning of
the 20’th century (see Kolda and Bader (2009) for a historic survey).

4

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

hidden layer
input X

representation 1x1 conv
global
pooling

xi

rep  i, d   fd  x i 

Z

M

dense
(output)

Z

Y

out  y   a y , pool :

conv  i, z   a z ,i , rep  i,:

pool  z    i 1 conv  i, z 
N

Figure 1: CP model – convolutional arithmetic circuit implementing CP (rank-1) decomposition.
representation of score functions:
hy (x1 , . . . , xN ) =

M
X
d1 ...dN =1

Ayd1 ,...,dN

N
Y

fθdi (xi )

(2)

i=1

fθ1 . . .fθM : Rs → R are referred to as representation functions, selected from a parametric family
F = {fθ : Rs → R}θ∈Θ . Natural choices for this family are wavelets, radial basis functions (Gaussians), and affine functions followed by point-wise activation (neurons). The coefficient tensor Ay
has order N and dimension M in each
mode. Its entries correspond to a basis of M N point-wise
QN
product functions {(x1 , . . . , xN ) 7→ i=1 fθdi (xi )}d1 ...dN ∈[M ] . We will often consider fixed linearly independent representation functions fθ1 . . .fθM . In this case the point-wise product functions
are linearly independent as well (see app. C.1), and we have a one to one correspondence between
score functions and coefficient tensors. To keep the manuscript concise, we defer the derivation of
our hypotheses space (eq. 2) to app. C, noting here that it arises naturally from the notion of tensor
products between L2 spaces.
Our eventual aim is to realize score functions hy with a layered network architecture. As a
first step along this path, we notice that hy (x1 , . . . , xN ) is fully determined by the activations of
the M representation functions fθ1 . . .fθM on the N input vectors x1 . . .xN . In other words, given
{fθd (xi )}d∈[M ],i∈[N ] , the score hy (x1 , . . . , xN ) is independent of the input. It is thus natural to consider the computation of these M ·N numbers as the first layer of our networks. This layer, referred
to as the representation layer, may be conceived as a convolutional operator with M channels, each
corresponding to a different function applied to all input vectors (see fig. 1).
Once we have constrained our score functions to have the structure depicted in eq. 2, learning
a classifier reduces to estimation of the parameters θ1 . . .θM , and the coefficient tensors A1 . . .AY .
The computational challenge is that the latter tensors are of order N (and dimension M in each
mode), having an exponential number of entries (M N each). In the next subsections we utilize
tensor decompositions (factorizations) to address this computational challenge, and show how they
are naturally realized by convolutional arithmetic circuits.

5

C OHEN S HARIR S HASHUA

3.1. Shallow Network as a CP Decomposition of Ay
The most straightforward way to factorize a tensor is through a CP (rank-1) decomposition (see
sec. 2). Consider a joint CP decomposition for the coefficient tensors {Ay }y∈Y :
Ay =

Z
X

ayz · az,1 ⊗ · · · ⊗ az,N

(3)

z=1

where ay ∈ RZ for y ∈ Y (ayz stands for entry z of ay ), and az,i ∈ RM for i ∈ [N ], z ∈ [Z]. The
decomposition is joint in the sense that the same vectors az,i are shared across all classes y. Clearly,
if we set Z = M N this model is universal, i.e. any tensors A1 . . .AY may be represented.
Substituting our CP decomposition (eq. 3) into the expression for the score functions in eq. 2,
we obtain:
!
Z
N
M
X
Y
X
z,i
hy (X) =
ayz
ad fθd (xi )
z=1

i=1

d=1

From this we conclude that the network illustrated in fig. 1 implements a classifier (score functions)
under the CP decomposition in eq. 3. We refer to this network as CP model. The network consists
of a representation layer followed by a single hidden layer, which in turn is followed by the output.
The hidden layer begins with a 1 × 1 conv operator, which is simply a 3D convolution with Z
channels and receptive field 1 × 1. The convolution may operate without coefficient sharing, i.e. the
filters that generate feature maps by sliding across the previous layer may have different coefficients
at different spatial locations. This is often referred to in the deep learning community as a locallyconnected operator (see Taigman et al. (2014)). To obtain a standard convolutional operator, simply
enforce coefficient sharing by constraining the vectors az,i in the CP decomposition (eq. 3) to be
equal to each other for different values of i (this setting is discussed in sec. 3.3). Following conv
operator, the hidden layer includes global product pooling. Feature maps generated by conv are
reduced to singletons through multiplication of their entries, creating a vector of dimension Z. This
vector is then mapped into the Y network outputs through a final dense linear layer.
To recap, CP model (fig. 1) is a shallow (single hidden layer) convolutional arithmetic circuit
that realizes the CP decomposition (eq. 3). It is universal, i.e. it can realize any coefficient tensors
with large enough size (Z). Unfortunately, since the CP-rank of a generic tensor is exponential in
its order (see Hackbusch (2012)), the size required for CP model to be universal is exponential (Z
exponential in N ).
3.2. Deep Network as a Hierarchical Decomposition of Ay
In this subsection we present a deep network that corresponds to the recently introduced Hierarchical Tucker tensor decomposition (Hackbusch and Kühn (2009)), which we refer to in short as
HT decomposition. The network, dubbed HT model, is universal. Specifically, any set of tensors
Ay represented by CP model can be represented by HT model with only a polynomial penalty in
terms of resources. The advantage of HT model, as we show in sec. 4, is that in almost all cases
it generates tensors that require an exponential size in order to be realized, or even approximated,
by CP model. Put differently, if one draws the weights of HT model by some continuous distribution, with probability one, the resulting tensors cannot be approximated by a polynomial CP model.
Informally, this implies that HT model is exponentially more expressive than CP model.

6

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

input X

hidden layer 0

representation

1x1 conv

hidden layer L-1
(L=log2N)

pooling

1x1 conv
xi
r0

M

rep  i, d   fd  x i 

conv0  j,    a

0, j ,

r0
poolL1   

, rep  j,:

pool0  j,   

rL1



j '2 j 1,2 j

conv0  j ',  



j '1,2

pooling
rL1

dense
(output)
Y

convL1  j ',  

out  y   a L, y , poolL1 :

Figure 2: HT model – convolutional arithmetic circuit implementing hierarchical decomposition.
HT model is based on the hierarchical tensor decomposition in eq. 4, which is a special case
of the HT decomposition as presented in Hackbusch and Kühn (2009) (in the latter’s terminology,
we restrict the matrices Al,j,γ to be diagonal). Our construction and theoretical results apply to the
general HT decomposition as well, with the specialization done merely to bring forth a network that
resembles current convolutional networks 3 .

φ

1,j,γ

=

r0
X

a1,j,γ
a0,2j−1,α ⊗ a0,2j,α
α

α=1

···
rl−1

φl,j,γ

=

X
α=1

al,j,γ
φl−1,2j−1,α ⊗ φl−1,2j,α
α
| {z } | {z }
order 2l−1

order 2l−1

···
rL−2

φL−1,j,γ

=

X
α=1

aL−1,j,γ
φL−2,2j−1,α ⊗ φL−2,2j,α
α
|
{z
} | {z }
order

N
4

order

N
4

rL−1
y

A

=

X
α=1

aL,y
φL−1,1,α ⊗ φL−1,2,α
α |
{z } | {z }
order

N
2

order

(4)

N
2

The decomposition in eq. 4 recursively constructs the coefficient tensors {Ay }y∈[Y ] by assembling vectors {a0,j,γ }j∈[N ],γ∈[r0 ] into tensors {φl,j,γ }l∈[L−1],j∈[N/2l ],γ∈[rl ] in an incremental fashion.
The index l stands for the level in the decomposition, j represents the “location” within level l, and
γ corresponds to the individual tensor in level l and location j. rl is referred to as level-l rank,
and is defined to be the number of tensors in each location of level l (we denote for completeness
rL := Y ). The tensor φl,j,γ has order 2l , and we assume for simplicity that N – the order of Ay ,
is a power of 2 (this is merely a technical assumption also made in Hackbusch and Kühn (2009), it
does not limit the generality of our analysis).
The parameters of the decomposition are the final level weights {aL,y ∈ RrL−1 }y∈[Y ] , the intermediate levels’ weights {al,j,γ ∈ Rrl−1 }l∈[L−1],j∈[N/2l ],γ∈[rl ] , and the first level vectors {a0,j,γ ∈
P
N
RM }j∈[N ],γ∈[r0 ] . This totals at N · M · r0 + L−1
l=1 2l · rl−1 · rl + Y · rl−1 individual parame3. If we had not constrained Al,j,γ to be diagonal, pooling operations would involve entries from different channels.

7

C OHEN S HARIR S HASHUA

ters, and if we assume equal ranks r := r0 = · · · = rL−1 , the number of parameters becomes
N · M · r + N · r2 + Y · r.
The hierarchical decomposition (eq. 4) is universal, i.e. with large enough ranks rl it can represent any tensors. Moreover, it is a super-set of the CP decomposition (eq. 3). That is to say,
all tensors representable by a CP decomposition having Z components are also representable by a
hierarchical decomposition with ranks r0 = r1 = · · · = rL−1 = Z 4 . Note that this comes with
a polynomial penalty – the number of parameters increases from N · M · Z + Z · Y in the CP
decomposition, to N · M · Z + Z · Y + N · Z 2 in the hierarchical decomposition. However, as we
show in sec. 4, the gain in expressive power is exponential.
Plugging the expression for Ay in our hierarchical decomposition (eq. 4) into the score function
hy given in eq. 2, we obtain the network displayed in fig. 2 – HT model. This network includes a
representation layer followed by L = log2 N hidden layers which in turn are followed by the output.
As in the shallow CP model (fig. 1), the hidden layers consist of 1 × 1 conv operators followed by
product pooling. The difference is that instead of a single hidden layer collapsing the entire spatial
structure through global pooling, hidden layers now pool over size-2 windows, decimating feature
maps by a factor of two (no overlaps). After L = log2 N such layers feature maps are reduced to
singletons, and we arrive at a 1D structure with rL−1 nodes. This is then mapped into Y network
outputs through a final dense linear layer. We note that the network’s size-2 pooling windows (and
the resulting number of hidden layers L = log2 N ) correspond to the fact that our hierarchical
decomposition (eq. 4) is based on a full binary tree over modes, i.e. it combines (through tensor
product) two tensors at a time. We focus on this setting solely for simplicity of presentation, and
since it is the one presented in Hackbusch and Kühn (2009). Our analysis (sec. 4) could easily be
adapted to hierarchical decompositions based on other trees (taking tensor products between more
than two tensors at a time), and that would correspond to networks with different pooling window
sizes and resulting depths.
HT model (fig. 2) is conceptually divided into two parts. The first is the representation layer,
transforming input vectors x1 . . .xN into N ·M real-valued scalars {fθd (xi )}i∈[N ],d∈[M ] . The second and main part of the network, which we view as an “inference” engine, is the convolutional
arithmetic circuit that takes the N ·M measurements produced by the representation layer, and accordingly computes Y class scores at the output layer.
To recap, we have now a deep network (fig. 2), which we refer to as HT model, that computes
the score functions hy (eq. 2) with coefficient tensors Ay hierarchically decomposed as in eq. 4.
The network is universal in the sense that with enough channels rl , any tensors may be represented.
Moreover, the model is a super-set of the shallow CP model presented in sec. 3.1. The question of
depth efficiency now naturally arises. In particular, we would like to know if there are functions that
may be represented by a polynomially sized deep HT model, yet require exponential size from the
shallow CP model. The answer, as described in sec. 4, is that almost all functions realizable by HT
model meet this property. In other words, the set of functions realizable by a polynomial CP model
has measure zero in the space of functions realizable by a given polynomial HT model.
4. To see this, simply assign the first level vectors a0,j,γ with CP’s basis vectors, the last level weights with CP’s
per-class weights, and the intermediate levels’ weights with indicator vectors.

8

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

3.3. Shared Coefficients for Convolution
The 1 × 1 conv operator in our networks (see fig. 1 and 2) implements a local linear transformation
with coefficients generally being location-dependent. In the special case where coefficients do not
depend on location, i.e. remain fixed across space, the local linear transformation becomes a standard convolution. We refer to this setting as coefficient sharing. Sharing is a widely used structural
constraint, one of the pillars behind the successful convolutional network architecture. In the context of image processing (prominent application of convolutional networks), sharing is motivated by
the observation that in natural images, the semantic content of a pattern often does not depend on its
location. In this subsection we explore the effect of sharing on the expressiveness of our networks,
or more specifically, on the coefficient tensors Ay they can represent.
For CP model, coefficient sharing amounts to setting az := az,1 = · · · = az,N in the CP
decomposition (eq. 3), transforming the latter to a symmetric CP decomposition:
y

A =

Z
X
z=1

ayz · |az ⊗ ·{z
· · ⊗ a}z , az ∈ RM , ay ∈ RZ
N times

CP model with sharing is not universal (not all tensors Ay are representable, no matter how large Z
is allowed to be) – it can only represent symmetric tensors.
In the case of HT model, sharing amounts to applying the following constraints on the hierarchil
cal decomposition in eq. 4: al,γ := al,1,γ = · · · = al,N/2 ,γ for every l = 0. . .L − 1 and γ = 1. . .rl .
Note that in this case universality is lost as well, but nonetheless generated tensors are not limited
to be symmetric, already demonstrating an expressive advantage of deep models over shallow ones.
In sec. 4 we take this further by showing that the shared HT model is exponentially more expressive
than CP model, even if the latter is not constrained by sharing.

4. Theorems of Network Capacity
The first contribution of this paper, presented in sec. 3, is the equivalence between deep learning
architectures successfully employed in practice, and tensor decompositions. Namely, we showed
that convolutional arithmetic circuits as in fig. 2, which are in fact SimNets that have demonstrated
promising empirical performance (see app. E), may be formulated as hierarchical tensor decompositions. As a second contribution, we make use of the established link between arithmetic circuits
and tensor decompositions, combining theoretical tools from these two worlds, to prove results that
are of interest to both deep learning and tensor analysis communities. This is the focus of the current
section.
The fundamental theoretical result proven in this paper is the following:
Theorem 1 Let Ay be a tensor of order N and dimension M in each mode, generated by the
recursive formulas in eq. 4. Define r := min{r0 , M }, and consider the space of all possible
configurations for the parameters of the composition – {al,j,γ }l,j,γ . In this space, the generated
tensor Ay will have CP-rank of at least rN/2 almost everywhere (w.r.t. Lebesgue measure). Put
differently, the configurations for which the CP-rank of Ay is less than rN/2 form a set of measure
zero. The exact same result holds if we constrain the composition to be “shared”, i.e. set al,j,γ ≡
al,γ and consider the space of {al,γ }l,γ configurations.
From the perspective of deep learning, thm. 1 leads to the following corollary:
9

C OHEN S HARIR S HASHUA

Corollary 2 Given linearly independent representation functions {fθd }d∈[M ] , randomizing the
weights of HT model (sec. 3.2) by a continuous distribution induces score functions hy that with
probability one, cannot be approximated arbitrarily well (in L2 sense) by a CP model (sec. 3.1)
with less than min{r0 , M }N/2 hidden channels. This result holds even if we constrain HT model
with weight sharing (sec. 3.3) while leaving CP model in its general form.
That is to say, besides a negligible set, all functions that can be realized by a polynomially sized
HT model (with or without weight sharing), require exponential size in order to be realized, or even
approximated, by CP model. Most of the previous works relating to depth efficiency (see app. D)
merely show existence of functions that separate depths (i.e. that are efficiently realizable by a deep
network yet require super-polynomial size from shallow networks). Corollary 2 on the other hand
establishes depth efficiency for almost all functions that a deep network can implement. Equally
importantly, it applies to deep learning architectures that are being successfully employed in practice
(SimNets – see app. E).
Adopting the viewpoint of tensor analysis, thm. 1 states that besides a negligible set, all tensors
realized by HT (Hierarchical Tucker) decomposition cannot be represented by the classic CP (rank1) decomposition if the latter has less than an exponential number of terms 5 . To the best of our
knowledge, this result has never been proved in the tensor analysis community. In the original
paper introducing HT decomposition (Hackbusch and Kühn (2009)), as a motivating example, the
authors present a specific tensor that is efficiently realizable by HT decomposition while requiring
an exponential number of terms from CP decomposition 6 . Our result strengthens this motivation
considerably, showing that it is not just one specific tensor that favors HT over CP, but rather, almost
all tensors realizable by HT exhibit this preference. Taking into account that any tensor realized by
CP can also be realized by HT with only a polynomial penalty in the number of parameters (see
sec. 3.2), this implies that in an asymptotic sense, HT decomposition is exponentially more efficient
than CP decomposition.
4.1. Proof Sketches
The complete proofs of thm. 1 and corollary 2 are given in app. B. We provide here an outline of
the main tools employed and arguments made along these proofs.
To prove thm. 1 we combine approaches from the worlds of circuit complexity and tensor decompositions. The first class of machinery we employ is matrix algebra, which has proven to be a
powerful source of tools for analyzing the complexity of circuits. For example, arithmetic circuits
have been analyzed through what is called the partial derivative matrix (see Raz and Yehudayoff
(2009)), and for boolean circuits a widely used tool is the communication matrix (see Karchmer
(1989)). We gain access to matrix algebra by arranging tensors that take part in the CP and HT
decompositions as matrices, a process often referred to as matricization. With matricization, the
tensor product translates to the Kronecker product, and the properties of the latter become readily
available. The second tool-set we make use of is measure theory, which prevails in the study of tensor decompositions, but is much less frequent in analyses of circuit complexity. In order to frame
5. As stated in sec. 3.2, the decomposition in eq. 4 to which thm. 1 applies is actually a special case of HT decomposition
as introduced in Hackbusch and Kühn (2009). However, the theorem and its proof can easily be adapted to account
for the general case. We focus on the special case merely because it corresponds to convolutional arithmetic circuit
architectures used in practice.
6. The same motivating example is given in a more recent textbook introducing tensor analysis (Hackbusch (2012)).

10

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

a problem in measure theoretical terms, one obviously needs to define a measure space of interest. For tensor decompositions, the straightforward space to focus on is that of the decomposition
variables. For general circuits on the other hand, it is often unclear if defining a measure space is
at all appropriate. However, when circuits are considered in the context of machine learning they
are usually parameterized, and defining a measure space on top of these parameters is an effective
approach for studying the prevalence of various properties in hypotheses spaces.
Our proof of thm. 1 traverses through the following path. We begin by showing that matricizing
a rank-1 tensor produces a rank-1 matrix. This implies that the matricization of a tensor generated by
a CP decomposition with Z terms has rank at most Z. We then turn to show that the matricization
of a tensor generated by the HT decomposition in eq. 4 has rank at least min{r0 , M }N/2 almost
everywhere. This is done through induction over the levels of the decomposition (l = 1. . .L). For
the first level (l = 1), we use a combination of measure theoretical and linear algebraic arguments
to show that the generated matrices have maximal rank (min{r0 , M }) almost everywhere. For the
induction step, the facts that under matricization tensor product translates into Kronecker product,
and that the latter increases ranks multiplicatively 7 , imply that matricization ranks in the current
level are generally equal to those in the previous level squared. Measure theoretical claims are then
made to ensure that this indeed takes place almost everywhere.
To prove corollary 2 based on thm. 1, we need to show that the inability of CP model to realize a
tensor generated by HT model, implies that the former cannot approximate score functions produced
by the latter. In general, the set of tensors expressible by a CP decomposition is not topologically
closed 8 , which implies that a-priori, it may be that CP model can approximate tensors generated
by HT model even though it cannot realize them. However, since the proof of thm. 1 was achieved
through separation of matrix rank, distances are indeed positive and CP model cannot approximate
HT model’s tensors almost always. To translate from tensors to score functions, we simply note
that in a finite-dimensional Hilbert space convergence in norm implies convergence in coefficients
under any basis. Therefore, in the space of score functions Q
(eq. 2) convergence in norm implies
convergence in coefficients under the basis {(x1 , . . . , xN )7→ N
i=1 fθdi (xi )}d1 ...dN ∈[M ] . That is to
say, it implies convergence in coefficient tensors.
4.2. Generalization
Thm. 1 and corollary 2 compare the expressive power of the deep HT model (sec. 3.2) to that of
the shallow CP model (sec. 3.1). One may argue that such an analysis is lacking, as it does not
convey information regarding the importance of each individual layer. In particular, it does not shed
light on the advantage of very deep networks, which at present provide state of the art recognition
accuracy, compared to networks of more moderate depth. For this purpose we present a generalization, specifying the amount of resources one has to pay in order to maintain representational power
while layers are incrementally cut off from a deep network. For conciseness we defer this analysis
to app. A, and merely state here our final conclusions. We find that the representational penalty is
double exponential w.r.t. the number of layers removed. In addition, there are certain cases where
the removal of even a single layer leads to an exponential inflation, falling in line with the suggestion
of Bengio (2009).
7. If denotes the Kronecker product, then for any matrices A and B: rank(A B) = rank(A)·rank(B).
8. Hence the definition of border rank, see Hackbusch (2012).

11

C OHEN S HARIR S HASHUA

5. Discussion
In this work we address a fundamental issue in deep learning – the expressive efficiency of depth.
There have been many attempts to theoretically analyze this question, but from a practical machine
learning perspective, existing results are limited. Most of the results apply to very specific types of
networks that do not resemble ones used in practice, and none of the results account for the localitysharing-pooling paradigm which forms the basis for convolutional networks – the most successful
deep learning architecture to date. In addition, current analyses merely show existence of depth
efficiency, i.e. of functions that are efficiently realizable by deep networks but not by shallow ones.
The practical implications of such findings are arguably slight, as a-priori, it may be that only a
small fraction of the functions realizable by deep networks enjoy depth efficiency, and for all the
rest shallow networks suffice.
Our aim in this paper was to develop a theory that facilitates an analysis of depth efficiency for
networks that incorporate the widely used structural ingredients of locality, sharing and pooling.
We consider the task of classification into one of a finite set of categories Y = {1. . .Y }. Our
instance space is defined to be the Cartesian product of N vector spaces, in compliance with the
common practice of representing natural data through ordered local structures (e.g. images through
patches). Each of the N vectors that compose an instance is represented by a descriptor of length M ,
generated by running the vector through M “representation” functions. As customary, classification
is achieved through maximization of score functions hy , one for every category y ∈ Y. Each score
function is a linear combination over the M N possible products that may be formed by taking one
descriptor entry from every input vector. The coefficients for these linear combinations conveniently
reside in tensors Ay of order N and dimension M along each axis. We construct networks that
compute score functions hy by decomposing (factorizing) the coefficient tensors Ay . The resulting
networks are convolutional arithmetic circuits that incorporate locality, sharing and pooling, and
operate on the N ·M descriptor entries generated from the input.
We show that a shallow (single hidden layer) network realizes the classic CP (rank-1) tensor
decomposition, whereas a deep network with log2 N hidden layers realizes the recently introduced
Hierarchical Tucker (HT) decomposition (Hackbusch and Kühn (2009)). Our fundamental result,
presented in thm. 1 and corollary 2, states that randomizing the weights of a deep network by some
continuous distribution will lead, with probability one, to score functions that cannot be approximated by a shallow network if the latter’s size is not exponential (in N ). We extend this result
(thm. 3 and corollary 4) by deriving analogous claims that compare two networks of any depths, not
just deep vs. shallow.
To further highlight the connection between our networks and ones used in practice, we show
(app. E) that translating convolution and product pooling computations to log-space (for numerical
stability) gives rise to SimNets – a recently proposed deep learning architecture which has been
shown to produce state of the art accuracy in computationally limited settings (Cohen et al. (2016)).
Besides the central line of our work discussed above, the construction and theory presented in
this paper shed light on various conjectures and practices employed by the deep learning community.
First, with respect to the pooling operation, our analysis points to the possibility that perhaps it has
more to do with factorization of computed functions than it does with translation invariance. This
may serve as an explanation for the fact that pooling windows in state of the art convolutional
networks are typically very small (see for example Simonyan and Zisserman (2014)), often much
smaller than the radius of translation one would like to be invariant to. Indeed, in our framework, as
12

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

we show in app. A, pooling over large windows and trimming down a network’s depth may bring to
an exponential decrease in expressive efficiency.
The second point our theory sheds light on is sharing. As discussed in sec. 3.3, introducing
weight sharing to a shallow network (CP model) considerably limits its expressive power. The network can only represent symmetric tensors, which in turn means that it is location invariant w.r.t.
input vectors (patches). In the case of a deep network (HT model) the limitation posed by sharing is
not as strict. Generated tensors need not be symmetric, implying that the network is capable of modeling location – a crucial ability in almost any real-world task. The above findings suggest that the
sharing constraint is increasingly limiting as a network gets shallower, to the point where it causes
complete ignorance to location. This could serve as an argument supporting the empirical success
of deep convolutional networks – they bind together the statistical and computational advantages of
sharing with many layers that mitigate its expressive limitations.
Lastly, our construction advocates locality, or more specifically, 1 × 1 receptive fields. Recent
convolutional networks providing state of the art recognition performance (e.g. Lin et al. (2014);
Szegedy et al. (2015)) make extensive use of 1 × 1 linear transformations, proving them to be
very successful in practice. In view of our model, such 1 × 1 operators factorize tensors while
providing universality with a minimal number of parameters. It seems reasonable to conjecture that
for this task of factorizing coefficient tensors, larger receptive fields are not significantly helpful,
as they lead to redundancy which may deteriorate performance in presence of limited training data.
Investigation of this conjecture is left for future work.

Acknowledgments
Amnon Shashua would like to thank Tomaso Poggio and Shai S. Shwartz for illuminating discussions during the preparation of this manuscript. We would also like to thank Tomer Galanti, Tamir
Hazan and Lior Wolf for commenting on draft versions of the paper. The work is partly funded by
Intel grant ICRI-CI no. 9-2012-6133 and by ISF Center grant 1790/12. Nadav Cohen is supported
by a Google Fellowship in Machine Learning.
References
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(1):2773–2832,
2014.
Richard Bellman, Richard Ernest Bellman, Richard Ernest Bellman, and Richard Ernest Bellman. Introduction to matrix analysis, volume 960. SIAM, 1970.
Yoshua Bengio. Learning Deep Architectures for AI. Foundations and Trends in Machine Learning, 2(1):
1–127, 2009.
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A comparison
between shallow and deep architectures. Neural Networks and Learning Systems, IEEE Transactions on,
25(8):1553–1565, 2014.
Joan Bruna and Stéphane Mallat. Invariant Scattering Convolution Networks. IEEE TPAMI, 2012.
Richard Caron and Tim Traynor. The zero set of a polynomial. WSMR Report 05-02, 2005.

13

C OHEN S HARIR S HASHUA

Nadav Cohen and Amnon Shashua. Simnets: A generalization of convolutional networks. Advances in
Neural Information Processing Systems (NIPS), Deep Learning Workshop, 2014.
Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decompositions.
International Conference on Machine Learning (ICML), 2016.
Nadav Cohen, Or Sharir, and Amnon Shashua. Deep simnets. IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2016.
G Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and
Systems, 2(4):303–314, 1989.
Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In Advances in Neural
Information Processing Systems, pages 666–674, 2011.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. arXiv preprint
arXiv:1512.03965, 2015.
F Girosi and T Poggio. Networks and the best approximation property. Biological cybernetics, 63(3):169–
176, 1990.
W Hackbusch and S Kühn. A New Scheme for the Tensor Representation. Journal of Fourier Analysis and
Applications, 15(5):706–722, 2009.
Wolfgang Hackbusch. Tensor Spaces and Numerical Tensor Calculus, volume 42 of Springer Series in
Computational Mathematics. Springer Science & Business Media, Berlin, Heidelberg, February 2012.
Benjamin D Haeffele and René Vidal. Global Optimality in Tensor Factorization, Deep Learning, and Beyond. CoRR abs/1202.2745, cs.NA, 2015.
András Hajnal, Wolfgang Maass, Pavel Pudlák, Márló Szegedy, and György Turán. Threshold circuits of
bounded depth. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 99–110.
IEEE, 1987.
Johan Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual
ACM symposium on Theory of computing, pages 6–20. ACM, 1986.
Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1(2):113–129, 1991.
Kurt Hornik, Maxwell B Stinchcombe, and Halbert White. Multilayer feedforward networks are universal
approximators. Neural networks, 2(5):359–366, 1989.
Brian Hutchinson, Li Deng, and Dong Yu. Tensor Deep Stacking Networks. IEEE Trans. Pattern Anal. Mach.
Intell. (), 35(8):1944–1957, 2013.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the Perils of Non-Convexity: Guaranteed
Training of Neural Networks using Tensor Methods. CoRR abs/1506.08473, 2015.
Frank Jones. Lebesgue integration on Euclidean space. Jones & Bartlett Learning, 2001.
Mauricio Karchmer. Communication complexity a new approach to circuit depth. 1989.
Tamara G Kolda and Brett W Bader. Tensor Decompositions and Applications. SIAM Review (), 51(3):
455–500, 2009.

14

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan V Oseledets, and Victor S Lempitsky. Speeding-up
Convolutional Neural Networks Using Fine-tuned CP-Decomposition. CoRR abs/1202.2745, , 2014.
Yann LeCun and Yoshua Bengio. Convolutional networks for images, speech, and time series. The handbook
of brain theory and neural networks, 3361(10), 1995.
Min Lin, Qiang Chen, and Shuicheng Yan. Network In Network. International Conference on Learning
Representations, 2014.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. Advances in Neural Information Processing Systems, 2014.
Wolfgang Maass, Georg Schnitger, and Eduardo D Sontag. A comparison of the computational power of
sigmoid and Boolean threshold circuits. Springer, 1994.
James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks. arXiv
preprint arXiv:1411.7717, 2014.
James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel. On the representational efficiency
of restricted boltzmann machines. In Advances in Neural Information Processing Systems, pages 2877–
2885, 2013.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions
of deep neural networks. In Advances in Neural Information Processing Systems, pages 2924–2932, 2014.
Alexander Novikov, Anton Rodomanov, Anton Osokin, and Dmitry Vetrov. Putting MRFs on a Tensor Train.
ICML, pages 811–819, 2014.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of inference regions of deep feed
forward networks with piece-wise linear activations. arXiv preprint arXiv, 1312, 2013.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8:143–195,
January 1999.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In Computer Vision
Workshops (ICCV Workshops), 2011 IEEE International Conference on, pages 689–690. IEEE, 2011.
Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171–207, 2009.
Benjamin Rossman, Rocco A Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for
boolean circuits. arXiv preprint arXiv:1504.03398, 2015.
Walter Rudin. Functional analysis. international series in pure and applied mathematics, 1991.
Thomas Serre, Lior Wolf, and Tomaso Poggio. Object Recognition with Features Inspired by Visual Cortex.
CVPR, 2:994–1000, 2005.
Hendra Setiawan, Zhongqiang Huang, Jacob Devlin, Thomas Lamar, Rabih Zbib, Richard M Schwartz, and
John Makhoul. Statistical Machine Translation Features with Multitask Tensor Networks. Proceedings of
the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint
Conference on Natural Language Processing of the Asian Federation of Natural Language Processing,
cs.CL, 2015.
Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions.
Foundations and Trends in Theoretical Computer Science, 5(3–4):207–388, 2010.
15

C OHEN S HARIR S HASHUA

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
Michael Sipser. Borel sets and circuit complexity. ACM, New York, New York, USA, December 1983.
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Y Ng. Reasoning With Neural Tensor
Networks for Knowledge Base Completion. Advances in Neural Information Processing Systems, pages
926–934, 2013.
Le Song, Mariya Ishteva, Ankur P Parikh, Eric P Xing, and Haesun Park. Hierarchical Tensor Decomposition
of Latent Tree Graphical Models. ICML, pages 334–342, 2013.
Maxwell Stinchcombe and Halbert White. Universal approximation using feedforward networks with nonsigmoid hidden layer activation functions. International Joint Conference on Neural Networks, pages
613–617 vol.1, 1989.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan,
Vincent Vanhoucke, and Andrew Rabinovich. Going Deeper with Convolutions. CVPR, 2015.
Yaniv Taigman, Ming Yang, Marc’Aurelio Ranzato, and Lior Wolf. DeepFace: Closing the Gap to HumanLevel Performance in Face Verification. In CVPR ’14: Proceedings of the 2014 IEEE Conference on
Computer Vision and Pattern Recognition. IEEE Computer Society, June 2014.
Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv preprint arXiv:1509.08101,
2015.
Y Yang and D B Dunson. Bayesian conditional tensor factorizations for high-dimensional classification.
Journal of the American Statistical, 2015.
Dong Yu, Li Deng, and Frank Seide. Large Vocabulary Speech Recognition Using Deep Tensor Neural
Networks. INTERSPEECH, pages 6–9, 2012.
Daniel Zoran and Yair Weiss. ”Natural Images, Gaussian Mixtures and Dead Leaves”. Advances in Neural
Information Processing Systems, pages 1745–1753, 2012.

16

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

Appendix A. Generalized Theorem of Network Capacity
In sec. 4 we presented our fundamental theorem of network capacity (thm. 1 and corollary 2), showing that
besides a negligible set, all functions that can be realized by a polynomially sized HT model (with or without
weight sharing), require exponential size in order to be realized, or even approximated, by CP model. In
terms of network depth, CP and HT models represent the extremes – the former has only a single hidden
layer achieved through global pooling, whereas the latter has L = log2 N hidden layers achieved through
minimal (size-2) pooling windows. It is of interest to generalize the fundamental result by establishing a
comparison between networks of intermediate depths. This is the focus of the current appendix.
We begin by defining a truncated version of the hierarchical tensor decomposition presented in eq. 4:
φ1,j,γ

=

r0
X

a1,j,γ
a0,2j−1,α ⊗ a0,2j,α
α

α=1

..
.
rl−1

φ

l,j,γ

=

X
α=1

al,j,γ
φl−1,2j−1,α ⊗ φl−1,2j,α
α
| {z } | {z }
order 2l−1

order 2l−1

..
.
rLc −1

A

=

X

c
aL
α

2L−Lc +1

⊗

j=1

α=1

φLc −1,j,α
| {z }

(5)

order 2Lc −1

The only difference between this decomposition and the original is that instead of completing the full process
with L := log2 N levels, we stop after Lc ≤L. At this point remaining tensors are binded together to form
the final order-N tensor. The corresponding network will simply include a premature global pooling stage
that shrinks feature maps to 1 × 1, and then a final linear layer that performs classification. As before, we
consider a shared version of the decomposition in which al,j,γ ≡ al,γ . Notice that this construction realizes
a continuum between CP and HT models, which correspond to the extreme cases Lc = 1 and Lc = L
respectively.
The following theorem, a generalization of thm. 1, compares a truncated decomposition having L1 levels,
to one with L2 < L1 levels that implements the same tensor, quantifying the penalty in terms of parameters:
Theorem 3 Let A(1) and A(2) be tensors of order N and dimension M in each mode, generated by
(1) L1 −1
the truncated recursive formulas in eq. 5, with L1 and L2 levels respectively. Denote by {rl }l=0
and
(2)
(1)
(2)
2 −1
{rl }L
the
composition
ranks
of
A
and
A
respectively.
Assuming
w.l.o.g.
that
L
>
L
,
we
define
1
2
l=0
(1)
(1)
r := min{r0 , ..., rL2 −1 , M }, and consider the space of all possible configurations for the parameters of
A(1) ’s composition – {a(1),l,j,γ }l,j,γ . In this space, almost everywhere (w.r.t. Lebesgue measure), the generL−L2
(2)
ated tensor A(1) requires that rL2 −1 ≥ (r)2
if one wishes that A(2) be equal to A(1) . Put differently, the
(2)

L−L2

configurations for which A(1) can be realized by A(2) with rL2 −1 < (r)2
form a set of measure zero. The
exact same result holds if we constrain the composition of A(1) to be “shared”, i.e. set a(1),l,j,γ ≡ a(1),l,γ
and consider the space of {a(1),l,γ }l,γ configurations.
In analogy with corollary 2, we obtain the following generalization:
Corollary 4 Suppose we are given linearly independent representation functions fθ1 . . .fθM , and consider
two networks that correspond to the truncated hierarchical tensor decomposition in eq. 5, with L1 and L2
hidden layers respectively. Assume w.l.o.g. that L1 > L2 , i.e. that network 1 is deeper than network 2, and
define r to be the minimal number of channels across the representation layer and the first L2 hidden layers
of network 1. Then, if we randomize the weights of network 1 by a continuous distribution, we obtain, with
17

C OHEN S HARIR S HASHUA

probability one, score functions hy that cannot be approximated arbitrarily well (in L2 sense) by network 2
L−L2
if the latter has less than (r)2
channels in its last hidden layer. The result holds even if we constrain
network 1 with weight sharing while leaving network 2 in its general form.
Proofs of thm. 3 and corollary 4 are given in app. B. Hereafter, we briefly discuss some of their implications. First, notice that we indeed obtain a generalization of the fundamental theorem of network capacity
(thm. 1 and corollary 2), which corresponds to the extreme case L1 = L and L2 = 1. Second, note that for the
baseline case of L1 = L, i.e. a full-depth network has generated the target score function, approximating this
with a truncated network draws a price that grows double exponentially w.r.t. the number of missing layers.
Third, and most intriguingly, we see that when L1 is considerably smaller than L, i.e. when a significantly
truncated network is sufficient to model our problem, cutting off even a single layer leads to an exponential
price, and this price is independent of L1 . Such scenarios of exponential penalty for trimming down a single
layer were discussed in Bengio (2009), but only in the context of specific functions realized by networks that
do not resemble ones used in practice (see Håstad and Goldmann (1991) for an example of such result). We
prove this in a much broader, more practical setting, showing that for convolutional arithmetic circuit (SimNet – see app. E) architectures, almost any function realized by a significantly truncated network will exhibit
this behavior. The issue relates to empirical practice, supporting the common methodology of designing networks that go as deep as possible. Specifically, it encourages extending network depth by pooling over small
regions, avoiding significant spatial decimation that brings network termination closer.
We conclude this appendix by stressing once more that our construction and theoretical approach are
not limited to the models covered by our theorems (CP model, HT model, truncated HT model). These are
merely exemplars deemed most appropriate for initial analysis. The fundamental and generalized theorems
of network capacity are similar in spirit, and analogous theorems for networks with different pooling window
sizes and depths (corresponding to different tensor decompositions) may easily be derived.

Appendix B. Proofs
B.1. Proof of Theorems 1 and 3
Our proof of thm. 1 and 3 relies on basic knowledge in measure theory, or more specifically, Lebesgue
measure spaces. We do not provide here a comprehensive background on this field (the interested reader is
referred to Jones (2001)), but rather supplement the brief discussion given in sec. 2, with a list of facts we
will be using which are not necessarily intuitive:
• A union of countably (or finitely) many sets of zero measure is itself a set of zero measure.
• If p is a polynomial over d variables that is not identically zero, the set of points in Rd in which it
vanishes has zero measure (see Caron and Traynor (2005) for a short proof of this).
• If S ⊂ Rd1 has zero measure, then S × Rd2 ⊂ Rd1 +d2 , and every set contained within, have zero
measure as well.
In the above, and in the entirety of this paper, the only measure spaces we consider are Euclidean spaces
equipped with Lebesgue measure. Thus when we say that a set of d-dimensional points has zero measure, we
mean that its Lebesgue measure in the d-dimensional Euclidean space is zero.
Moving on to some preliminaries from matrix and tensor theory, we denote by [A] the matricization of
an order-N tensor A (for simplicity, N is assumed to be even), where rows correspond to odd modes and
columns correspond to even modes. Namely, if A ∈ RM1 ×···×MN , the matrix [A] has M1 ·M3 · . . . ·MN −1
rows and M2 ·M4 · . . . ·MN columns, rearranging the entries of the tensor such that Ad1 ...dN is stored in row
PN/2
QN/2
PN/2
QN/2
index 1+ i=1 (d2i−1 −1) j=i+1 M2j−1 and column index 1+ i=1 (d2i −1) j=i+1 M2j . To distinguish
from the tensor product operation ⊗, we denote the Kronecker product between matrices by . Specifically,
for two matrices A ∈ RM1 ×M2 and B ∈ RN1 ×N2 , A B is the matrix in RM1 N1 ×M2 N2 that holds Aij Bkl
in row index (i − 1)N1 + k and column index (j − 1)N2 + l. The basic relation that binds together tensor
18

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

product, matricization and Kronecker product is [A ⊗ B] = [A] [B], where A and B are tensors of even
orders. Two additional facts we will make use of areP
that the matricization
Pr is a linear operator (i.e. for scalars
r
α1 . . .αr and tensors with the same size A1 . . .Ar : [ i=1 αi Ai ] = i=1 αi [Ai ]), and less trivially, that for
any matrices A and B, the rank of A B is equal to rank(A) · rank(B) (see Bellman et al. (1970) for a
proof). These two facts, along with the basic relation laid out above, lead to the conclusion that:
(z)

2L/2

(z)>

v2i−1 v2i

zh

}|
i{
h
i Y
(z)
(z)
(z)
(z)
rank v1 ⊗ · · · ⊗ v2L =
rank v2i−1 ⊗ v2i = 1
i=1

and thus:
" Z
#
Z
Z
h
i X
h
i
X
X
(z)
(z)
(z)
(z)
(z)
(z)
rank
λz v1 ⊗ · · · ⊗ v2L = rank
λz v1 ⊗ · · · ⊗ v2L ≤
rank v1 ⊗ · · · ⊗ v2L = Z
z=1

z=1

z=1

In words, an order-2L tensor given by a CP-decomposition (see sec. 2) with Z terms, has matricization with
rank at most Z. Thus, to prove that a certain order-2L tensor has CP-rank of at least R, it suffices to show
that its matricization has rank of at least R.
We now state and prove two lemmas that will be needed for our proofs of thm. 1 and 3.
Lemma 5 Let M, N ∈ N, and define the following mapping taking x ∈ R2M N +N to three matrices:
A(x) ∈ RM ×N , B(x) ∈ RM ×N and D(x) ∈ RN ×N . A(x) simply holds the first M N elements of x, B(x)
holds the following M N elements of x, and D(x) is a diagonal matrix that holds the last N elements of x on
its diagonal. Define the product matrix U (x) := A(x)D(x)B(x)> ∈ RM ×M , and consider the set of points
x for which the rank of U (x) is different from r := min{M, N }. This set of points has zero measure. The
result will also hold if the points x reside in RM N +N , and the same elements are used to assign A(x) and
B(x) (A(x) ≡ B(x)).
Proof Obviously rank(U (x)) ≤ r for all x, so it remains to show that rank(U (x)) ≥ r for all x but a
set of zero measure. Let Ur (x) be the top-left r × r sub-matrix of U (x). If Ur (x) is non-singular then of
course rank(U (x)) ≥ r as required. It thus suffices to show that the set of points x for which det Ur (x) = 0
has zero measure. Now, det Ur (x) is a polynomial in the entries of x, and so it either vanishes on a set of
zero measure, or it is the zero polynomial (see Caron and Traynor (2005)). All that is left is to disqualify
the latter option, and that can be done by finding a specific point x0 for which det Ur (x0 ) 6= 0. Indeed,
we may choose x0 such that D(x0 ) is the identity matrix and A(x0 ), B(x0 ) hold 1 on their main diagonal
and 0 otherwise. This selection implies that Ur (x0 ) is the identity matrix, and in particular det Ur (x0 ) 6= 0.

Lemma 6 Assume we have p continuous mappings from Rd to RM ×N taking the point y to the matrices A1 (y). . .Ap (y). Assume that under these mappings, the points y for which every i ∈ [p] satisfies
rank(Ai (y)) < r formPa set of zero measure. Define a mapping from Rp × Rd to RM ×N given by
p
(x, y) 7→ A(x, y) :=
i=1 xi · Ai (y). Then, the points (x, y) for which rank(A(x, y)) < r form a
set of zero measure.
Proof Denote S := {(x, y) : rank(A(x, y)) < r} ⊂ Rp × Rd . We would like to show that this set has zero
measure. We first note that since A(x, y) is a continuous mapping, and the set of matrices A ∈ RM ×N which
have rank less than r is closed, S is a closed set and in particular measurable. Our strategy for computing its
measure will be as follows. For every y ∈ Rd we define the marginal set S y := {x : rank(A(x, y)) < r} ⊂
Rp . We will show that for every y but a set of zero measure, the measure of S y is zero. An application of
Fubini’s theorem will then prove the desired result.
19

C OHEN S HARIR S HASHUA

Let C be the set of points y ∈ Rd for which ∀i ∈ [p] : rank(Ai (y)) < r. By assumption, C has zero
measure. We now show that for y0 ∈ Rd \ C, the measure of S y0 is zero. By the definition of C there exists
an i ∈ [p] such that rank(Ai (y0 )) ≥ r. W.l.o.g., we assume that i = 1, and that the top-left r × r sub-matrix
of A1 (y0 ) is non-singular. Regarding y0 as fixed, the determinant of the top-left r × r sub-matrix of A(x, y0 )
is a polynomial in the elements of x. It is not the zero polynomial, as setting x1 = 1, x2 = · · · = xp = 0
yields A(x, y0 ) = A1 (y0 ), and the determinant of the latter’s top-left r × r sub-matrix is non-zero. As a
non-zero polynomial, the determinant of the top-left r × r sub-matrix of A(x, y0 ) vanishes only on a set of
zero measure (Caron and Traynor (2005)). This implies that indeed the measure of S y0 is zero.
We introduce a few notations towards our application of Fubini’s theorem. First, the symbol 1 will be
used to represent indicator functions, e.g. 1S is the function from Rp × Rd to R that receives 1 on S and 0
elsewhere. Second, we use a subscript of n ∈ N to indicate that the corresponding set is intersected with the
hyper-rectangle of radius n. For example, Sn stands for the intersection between S and [−n, n]p+d , and Rdn
stands for the intersection between Rd and [−n, n]d (which is equal to the latter). All the sets we consider
are measurable, and those with subscript n have finite measure. We may thus apply Fubini’s theorem to get:
Z
Z
Z
Z
Z
Z
Z
Z
1Sn =
1S =
1S y =
1S y +
1S y
(x,y)∈Rp+d
n

(x,y)

x∈Rp
n

y∈Rd
n

x∈Rp
n

y∈Rd
n ∩C

y∈Rd
n \C

x∈Rp
n

Recall that the set C ∈ Rd has zero measure, and for every y ∈
/ RC the measure of S y ∈ Rp is zero. This
implies that both integrals in the last
R expression vanish, and thus 1Sn = 0. Finally, we use the monotone
convergence theorem to compute 1S :
Z
Z
Z
1S =
lim 1Sn = lim
1Sn = lim 0 = 0
n→∞

n→∞

n→∞

This shows that indeed our set of interest S has zero measure.
With all preliminaries and lemmas in place, we turn to prove thm. 1, establishing an exponential efficiency
of HT decomposition (eq. 4) over CP decomposition (eq. 3).
Proof [of theorem 1] We begin with the case of an “unshared” composition, i.e. the one given in eq. 4 (as
opposed to the “shared” setting of al,j,γ ≡ al,γ ). Denoting for convenience φL,1,1 := Ay and rL = 1, we
will show by induction over l = 1, ..., L that almost everywhere (at all points but a set of zero measure)
l
w.r.t. {al,j,γ }l,j,γ , all CP-ranks of the tensors {φl,j,γ }j∈[N/2l ],γ∈[rl ] are at least r2 /2 . In accordance with our
discussion in the beginning of this subsection, it suffices to consider the matricizations [φl,j,γ ], and show that
l
these all have ranks greater or equal to r2 /2 almost everywhere.
For the case l = 1 we have:
r0
X
φ1,j,γ =
a1,j,γ
a0,2j−1,α ⊗ a0,2j,α
α
α=1
0
, by B ∈ RM ×r0 the matrix with columns
Denote by A ∈ R
the matrix with columns {a0,2j−1,α }rα=1
0,2j,α r0
r0 ×r0
1,j,γ
{a
}α=1 , and by D ∈ R
the diagonal matrix with a
on its diagonal. Then, we may write
1,j,γ
[φ1,j,γ ] = ADB > , and according to lemma
5
the
rank
of
[φ
]
equals
r := min{r0 , M } almost everywhere

w.r.t. {a0,2j−1,α }α , {a0,2j,α }α , a1,j,γ . To see that this holds almost everywhere w.r.t. {al,j,γ }l,j,γ , one
should merely recall that for any dimensions d1 , d2 ∈ N, if the set S ⊂ Rd1 has zero measure, so does
any subset of S × Rd2 ⊂ Rd1 +d2 . A finite union of zero measure sets has zero measure, thus the fact that
rank[φ1,j,γ ] = r holds almost everywhere individually for any j ∈ [N/2] and γ ∈ [r1 ], implies that it holds
almost everywhere jointly for all j and γ. This proves our inductive hypothesis (unshared case) for l = 1.
l−1
0
0
Assume now that almost everywhere rank[φl−1,j ,γ ] ≥ r2 /2 for all j 0 ∈ [N/2l−1 ] and γ 0 ∈ [rl−1 ]. For
some specific choice of j ∈ [N/2l ] and γ ∈ [rl ] we have:

M ×r0

rl−1

φl,j,γ =

X

rl−1

al,j,γ
φl−1,2j−1,α ⊗ φl−1,2j,α =⇒ [φl,j,γ ] =
α

α=1

X
α=1

20

al,j,γ
[φl−1,2j−1,α ]
α

[φl−1,2j,α ]

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

Denote Mα := [φl−1,2j−1,α ] [φl−1,2j,α ] for α = 1. . .rl−1 . By our inductive assumption, and by the general
property rank(A B) = rank(A)·rank(B), we have that almost everywhere the ranks of all matrices Mα
Prl−1 l,j,γ
l−1
l−1
l
are at least r2 /2 · r2 /2 = r2 /2 . Writing [φl,j,γ ] = α=1
aα · Mα , and noticing that {Mα } do not
l
l,j,γ
depend on a
, we turn our attention to lemma 6. The lemma tells us that rank[φl,j,γ ] ≥ r2 /2 almost
everywhere. Since a finite union of zero measure sets has zero measure, we conclude that almost everywhere
l
rank[φl,j,γ ] ≥ r2 /2 holds jointly for all j ∈ [N/2l ] and γ ∈ [rl ]. This completes the proof of the theorem in
the unshared case.
Proving the theorem in the shared case may be done in the exact same way, except that for l = 1 one
needs the version of lemma 5 for which A(x) and B(x) are equal.

We now head on to prove thm. 3, which is a generalization of thm. 1. The proof will be similar in nature
to that of thm. 1, yet slightly more technical. In short, the idea is to show that in the generic case, expressing
L
A(1) as a sum of tensor products between tensors of order 2L2 −1 requires at least rN/2 2 terms. Since A(2) is
N/2L2
(2)
(1)
expressed as a sum of rL2 −1 such terms, demanding A = A implies rL2 −1 ≥ r
.
To gain technical advantage and utilize known results from matrix theory (as we did when proving
thm. 1), we introduce a new tensor “squeezing” operator ϕ. For q ∈ N, ϕq is an operator that receives a
tensor with order divisible by q, and returns the tensor obtained by merging together the latter’s modes in
groups of size q. Specifically, when applied to the tensor A ∈ RM1 ×···×Mc·q (c ∈ N), ϕq returns a tensor of
c which holdsQ
Ad1 ...dc·q in the location defined by the following index for every mode t ∈ [c]:
Porder
q
q
1 + i=1 (di+q(t−1) − 1) j=i+1 Mj+q(t−1) . Notice that when applied to a tensor of order q, ϕq returns a
vector. Also note that if A and B are tensors with orders divisible by q, and λ is a scalar, we have the desirable
properties:
• ϕq (A ⊗ B) = ϕq (A) ⊗ ϕq (B)
• ϕq (λA + B) = λϕq (A) + ϕq (B)
For the sake of our proof we are interested in the case q = 2L2 −1 , and denote for brevity ϕ := ϕ2L2 −1 .
PZ
(z)
As stated above, we would like to show that in the generic case, expressing A(1) as z=1 φ1 ⊗ · · · ⊗
L
(z)
(z)
φN/2L2 −1 , where φi are tensors of order 2L2 −1 , implies Z ≥ rN/2 2 . Applying ϕ to both sides of such a
PZ
(z)
(z)
(z)
decomposition gives: ϕ(A(1) ) = z=1 ϕ(φ1 ) ⊗ · · · ⊗ ϕ(φN/2L2 −1 ), where ϕ(φi ) are now vectors. Thus,
L

to prove thm. 3 it suffices to show that in the generic case, the CP-rank of ϕ(A(1) ) is at least rN/2 2 , or
L
alternatively, that the rank of the matricization [ϕ(A(1) )] is at least rN/2 2 . This will be our strategy in the
following proof:
Proof [of theorem 3] In accordance with the above discussion, it suffices to show that in the generic case
L
rank[ϕ(A(1) )] ≥ rN/2 2 . To ease the path for the reader, we reformulate the problem using slightly simpler
notations. We have an order-N tensor A with dimension M in each mode, generated as follows:
φ1,j,γ

=

r0
X

a1,j,γ
a0,2j−1,α ⊗ a0,2j,α
α

α=1

..
.
rl−1

φl,j,γ

=

X
α=1

al,j,γ
φl−1,2j−1,α ⊗ φl−1,2j,α
α
| {z } | {z }
order 2l−1

order 2l−1

..
.
rL1 −1

A

=

X

L1 ,1,1
aα

α=1

2L−L1 +1

⊗

j=1

φL1 −1,j,α
| {z }
order 2L1 −1

21

C OHEN S HARIR S HASHUA

where:
• L1 ≤ L := log2 N
• r0 , ..., rL1 −1 ∈ N>0
• a0,j,α ∈ RM for j ∈ [N ] and α ∈ [r0 ]
• al,j,γ ∈ Rrl−1 for l ∈ [L1 − 1], j ∈ [N/2l ] and γ ∈ [rl ]
• aL1 ,1,1 ∈ RrL1 −1
Let L2 be a positive integer smaller than L1 , and let ϕ be the tensor squeezing operator that merges groups
of 2L2 −1 modes. Define r := min{r0 , ..., rL2 −1 , M }. With [·] being the matricization operator defined
L
in the beginning of the appendix, our task is to prove that rank[ϕ(A)] ≥ rN/2 2 almost everywhere w.r.t.
{al,j,γ }l,j,γ . We also consider the case of shared parameters – al,j,γ ≡ al,γ , where we would like to show
that the same condition holds almost everywhere w.r.t. {al,γ }l,γ .
Our strategy for proving the claim is inductive. We show that for l = L2 . . .L1 − 1, almost everywhere
l−L2
it holds that for all j and all γ: rank[ϕ(φl,j,γ )] ≥ r2
. We then treat the special case of l = L1 , showing
L
that indeed rank[ϕ(A)] ≥ rN/2 2 . We begin with the setting of unshared parameters (al,j,γ ), and afterwards
attend the scenario of shared parameters (al,γ ) as well.
Our first task is to treat the case l = L2 , i.e. show that rank[ϕ(φL2 ,j,γ )] ≥ r almost everywhere jointly
for all j and all γ (there is actually no need for the matricization [·] here, as ϕ(φL2 ,j,γ ) are already matrices).
Since a union of finitely many zero measure sets has zero measure, it suffices to show that this condition
holds almost everywhere when specific j and γ are chosen. Denote by ei a vector holding 1 in entry i and 0
elsewhere, by 0 a vector of zeros, and by 1 a vector of ones. Suppose that for every j we assign a0,j,α to be
eα when α ≤ r and 0 otherwise. Suppose also that for all 1 ≤ l ≤ L2 − 1 and all j we set al,j,γ to be eγ
when γ ≤ r and 0 otherwise. Finally, assume we set aL2 ,j,γ = 1 for all j and all γ. These settings imply that
2L2 −2
for every j, when γ ≤ r we have φL2 −1,j,γ = ⊗j=1
(eγ ⊗ eγ ), i.e. the tensor φL2 −1,j,γ holds 1 in location
(γ, ..., γ) and 0 elsewhere. If γ > r then φL2 −1,j,γ is the zero tensor. We conclude from this that there are
indices 1 ≤ i1 < ... < ir ≤ M L2 −1 such that ϕ(φL2 −1,j,γ ) = eiγ for γ ≤ r, and that for γ > r we have
ϕ(φL2 −1,j,γ ) = 0. We may thus write:
! rL −1
rL2 −1
r
2
X
X
X
L2 −1,2j−1,α
L2 −1,2j,α
L2 ,j,γ
ϕ(φL2 −1,2j−1,α )⊗ϕ(φL2 −1,2j,α ) =
eiα e>
φ
⊗φ
=
ϕ(φ
)=ϕ
iα
α=1

α=1

α=1

Now, since i1 . . .ir are different from each other, the matrix ϕ(φL2 ,j,γ ) has rank r. This however does not
prove our inductive hypothesis for l = L2 . We merely showed a specific parameter assignment for which
it holds, and we need to show that it is met almost everywhere. To do so, we consider an r × r sub-matrix
of ϕ(φL2 ,j,γ ) which is non-singular under the specific parameter assignment we defined. The determinant
of this sub-matrix is a polynomial in the elements of {al,j,γ }l,j,γ which we know does not vanish with the
specific assignments defined. Thus, this polynomial vanishes at subset of {al,j,γ }l,j,γ having zero measure
(see Caron and Traynor (2005)). That is to say, the sub-matrix of ϕ(φL2 ,j,γ ) has rank r almost everywhere,
and thus ϕ(φL2 ,j,γ ) has rank at least r almost everywhere. This completes our treatment of the case l = L2 .
We now turn to prove the propagation of our inductive hypothesis. Let l ∈ {L2 + 1, ..., L1 − 1}, and
assume that our inductive hypothesis holds for l − 1. Specifically, assume that almost everywhere w.r.t.
l−1−L2
{al,j,γ }l,j,γ , we have that rank[ϕ(φl−1,j,γ )] ≥ r2
jointly for all j ∈ [N/2l−1 ] and all γ ∈ [rl−1 ].
l−L2
l,j,γ
We would like to show that almost everywhere, rank[ϕ(φ
)] ≥ r2
jointly for all j ∈ [N/2l ] and all
γ ∈ [rl ]. Again, the fact that a finite union of zero measure sets has zero measure implies that we may
prove the condition for specific j ∈ [N/2l ] and γ ∈ [rl ]. Applying the squeezing operator ϕ followed by

22

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

matricization [·] to the recursive expression for φl,j,γ , we get:
"
!# "rl−1
#
rl−1
X
X
[ϕ(φl,j,γ )] =
al,j,γ
al,j,γ
ϕ
φl−1,2j−1,α ⊗ φl−1,2j,α
=
ϕ(φl−1,2j−1,α ) ⊗ ϕ(φl−1,2j,α )
α
α
α=1

α=1

rl−1

=

X

al,j,γ
[ϕ(φl−1,2j−1,α )]
α

[ϕ(φl−1,2j,α )]

α=1

For α = 1. . .rl−1 , denote the matrix [ϕ(φl−1,2j−1,α )] [ϕ(φl−1,2j,α )] by Mα . The fact that the Kronecker
product multiplies ranks, along with our inductive assumption, imply that almost everywhere rank(Mα ) ≥
l−1−L2
l−1−L2
l−L2
r2
· r2
= r2
. Noting that the matrices Mα do not depend on al,j,γ , we apply lemma 6
l−L2
and conclude that almost everywhere rank[ϕ(φl,j,γ )] ≥ r2
, which completes the prove of the inductive
propagation.
Next, we treat the special case l = L1 . We assume now that almost everywhere rank[ϕ(φL1 −1,j,γ )] ≥
2L1 −1−L2
r
jointly for all j and all γ. Again, we apply the squeezing operator ϕ followed by matricization [·],
this time to both sides of the expression for A:
rL1 −1

[ϕ(A)] =

X

L1 ,1,1
aα

2L−L1 +1

α=1

[ϕ(φL1 −1,j,α )]

j=1

L−L1 +1

2
[ϕ(φL1 −1,j,α )] for α = 1. . .rL1 −1 . Using again the multiplicative
As before, denote Mα := j=1
rank property of the Kronecker product along with our inductive assumption, we get that almost everywhere
Q2L−L1 +1 2L1 −1−L2
rank(Mα ) ≥ j=1
r
= rL−L2 . Noticing that {Mα }α∈[rL1 −1 ] do not depend on aL1 ,1,1 , we
apply lemma 6 for the last time and get that almost everywhere (w.r.t. {al,j,γ }l,j,γ ), the rank of [ϕ(A)] is at
least rL−L2 . This completes our proof in the case of unshared parameters.
Proving the theorem in the case of shared parameters (al,j,γ ≡ al,γ ) can be done in the exact same way
as above. In fact, all one has to do is omit the references to j and the proof will apply. Notice in particular
that the specific parameter assignment we defined to handle l = L2 was completely symmetric, i.e. it did not
include any dependence on j.

B.2. Proof of Corollaries 2 and 4
Corollaries 2 and 4 are a direct continuation of thm. 1 and 3 respectively. In the theorems, we have shown
that almost all coefficient tensors generated by a deep network cannot be realized by a shallow network if
the latter does not meet a certain minimal size requirement. The corollaries take this further, by stating that
given linearly independent representation functions fθ1 . . .fθM , not only is efficient realization of coefficient
tensors generally impossible, but also efficient approximation of score functions. To prove this extra step,
we recall from the proofs of thm. 1 and 3 (app. B.1) that in order to show separation between the coefficient
tensor of a deep network and that of a shallow network, we relied on matricization rank. Specifically, we
derived constants RD , RS ∈ N, RD > RS , such that the matricization of a deep network’s coefficient tensor
had rank greater or equal to RD , whereas the matricization of a shallow network’s coefficient tensor had rank
smaller or equal to RS . Given this observation, corollaries 2 and 4 readily follow from lemma 7 below (the
lemma relies on basic concepts and results from the topic of L2 Hilbert spaces – see app. C.1 for a brief
discussion on the matter).
Lemma 7 Let fθ1 . . .fθM ∈L2 (Rs ) be a set of linearly independent functions, and denote by T the (Euclidean) space of tensors with order N and dimension M in each mode. For a given tensor A ∈ T , denote

23

C OHEN S HARIR S HASHUA


by h(A) the function in L2 (Rs )N defined by:
h(A)

(x1 , . . . , xN ) 7→

M
X

Ad1 ...dN

N
Y

fθdi (xi )

i=1

d1 ,...,dN =1

Let {Aλ }λ∈Λ ⊂ T be a family of tensors, and A∗ be a certain target tensor that lies outside the family.
Assume that for all λ ∈ Λ we have rank([Aλ ]) < rank([A∗ ]), where [·] is the matricization operator
defined in app. B.1. Then, the distance in L2 (Rs )N between h(A∗ ) and {h(Aλ )}λ∈Λ is strictly positive,
i.e. there exists an  > 0 such that:
Z
2
h(Aλ ) − h(A∗ ) > 
∀λ ∈ Λ :
Proof The fact that {fθd (x)}d∈[M ] are linearly independent in L2 (Rs ) implies that the product functions

QN
{ i=1 fθdi (xi )}d1 ...dN ∈[M ] are linearly independent in L2 (Rs )N (see app. C.1). Let (h(t) )∞
t=1 be a seQN
quence of functions that lie in the span of { i=1 fθdi (xi )}d1 ...dN ∈[M ] , and for every t ∈ N denote by A(t)
the coefficient tensor of h(t) under this basis, i.e. A(t) ∈ T is defined by:
h(t) (x1 , . . . , xN ) =

M
X

(t)

Ad1 ,...,dN

fθdi (xi )

i=1

d1 ,...,dN =1


∗
2
Assume that (h(t) )∞
(Rs )N :
t=1 converges to h(A ) in L
Z
lim
h(t) − h(A∗ )
t→∞

N
Y

2

=0

In a finite-dimensional Hilbert space, convergence in norm implies convergence in representation coefficients
under any preselected basis. We thus have:
(t)

t→∞

∀d1 . . .dN ∈ [M ] : Ad1 ,...,dN −−−→ A∗d1 ,...,dN
∗
This means in particular that in the tensor
in the closure of {A(t) }∞
t=1 . Accordingly, in order
 space T , A lies
2
s N
∗
to show that the distance in L (R )
between h(A ) and {h(Aλ )}λ∈Λ is strictly positive, it suffices to
show that the distance in T between A∗ and {Aλ }λ∈Λ is strictly positive, or equivalently, that the distance
between the matrix [A∗ ] and the family of matrices {[Aλ ]}λ∈Λ is strictly positive. This however is a direct
implication of the assumption ∀λ ∈ Λ : rank([Aλ ]) < rank([A∗ ]).

Appendix C. Derivation of Hypotheses Space
In order to keep the body of the paper at a reasonable length, the presentation of our hypotheses space (eq. 2)
in sec. 3 did not provide the grounds for its definition. In this appendix we derive the hypotheses space step by
step. After establishing basic preliminaries on the topic of L2 spaces, we utilize the notion of tensor products
between such spaces to reach a universal representation as in eq. 2 but with M → ∞. We then make use
of empirical studies characterizing the statistics of natural images, to argue that in practice a moderate value
of M (M ∈ Ω(100)) suffices.

C.1. Preliminaries on L2 Spaces
When dealing with functions over scalars, vectors or collections of vectors, we consider L2 spaces, or more
formally, the Hilbert spaces of Lebesgue measurable square-integrable real functions equipped with standard
24

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

(point-wise) addition and scalar multiplication, as well as the inner-product defined by integral over pointwise multiplication. The topic of L2 function spaces lies at the heart of functional analysis, and requires basic
knowledge in measure theory. We present here the bare necessities required to follow this appendix, referring
the interested reader to Rudin (1991) for a more comprehensive introduction.
R
For our purposes, it suffices to view an L2 space as a vector space of all functions f satisfying f 2 < ∞.
This vector space is infinite dimensional, and a set of functions F ⊂ L2 is referred to as total if the closure of
its span covers the entire space, i.e. if forRanyPfunction g ∈ L2 and  > 0, there exist functions f1 . . .fK ∈ F
K
and coefficients c1 . . .cK ∈ R such that | i=1 ci · fi − g|2 < . F is regarded as linearly independent
if all of its finite subsets are linearly independent, i.e. for any f1 . . .fK ∈ F, fi 6= fj , and c1 . . .cK ∈ R, if
PK
2
i=1 ci · fi = 0 then c1 = · · · = cK = 0. A non-trivial result states that L spaces in general must contain
2
s
total and linearly independent sets, and moreover, for any s ∈ N, L (R ) contains a countable set of this type.
It seems reasonable to draw an analogy between total and linearly independent sets in L2 space, and bases
in a finite dimensional vector space. While this analogy is indeed appropriate from our perspective, total and
linearly independent sets are not to be confused with bases for L2 spaces, which are typically defined to be
orthonormal.
It can be shown (see for example Hackbusch (2012)) that for any natural numbers s and N , if {fd (x)}d∈N
QN
is a total or a linearly independent set in L2 (Rs ), then {(x1 , . . . , xN ) 7→ i=1 fdi (xi )}d1 ...dN ∈N , the ins N
duced point-wise
 product functions on (R ) , form a set which is total or linearly independent, respectively,
in L2 (Rs )N . As we now briefly outline, this result actually emerges from a deep relation between tensor
products and Hilbert spaces. The definitions given in sec. 2 for a tensor, tensor space, and tensor product, are
actually concrete special cases of much deeper, abstract algebraic concepts. A more formal line of presentation considers multiple vector spaces V1 . . .VN , and defines their tensor product space V1 ⊗ · · · ⊗VN to be a
specific quotient space of the space freely generated by their Cartesian product set. For every combination of
vectors v(i) ∈ Vi , i ∈ [N ], there exists a corresponding element v(1) ⊗ · · · ⊗v(N ) in the tensor product space,
and moreover, elements of this form span the entire space. If V1 . . .VN are Hilbert spaces, it is possible to
equip V1 ⊗ · · · ⊗VN with a natural inner-product operation, thereby turning it too into a Hilbert space. It may
(i)
then be shown that if the sets {vα }α ⊂ Vi , i ∈ [N ], are total or linearly independent, elements of the form
(N )
(1)
vα1 ⊗ · · · ⊗ vαN are total or linearly independent, respectively, in V1 ⊗ · · · ⊗VN . Finally,Qwhen the underN
lying Hilbert spaces are L2 (Rs ), the point-wise product mapping f1 (x)⊗ · · · ⊗fN (x) 7→ i=1 fi (xi ) from


⊗N
the tensor product space L2 (Rs )
:= L2 (Rs )⊗ · · · ⊗L2 (Rs ) to L2 (Rs )N , induces an isomorphism of
Hilbert spaces.

C.2. Construction
Recall from sec. 3 that our instance space is defined as X := (Rs )N , in accordance with the common practice of representing natural data through ordered local structures (for example images are often represented
through small patches around their pixels). We classify instances into categories Y := {1. . .Y } via maximization of per-labelscore functions {hy : (Rs )N → R}y∈Y . Our hypotheses space H is defined to be the
subset of L2 (Rs )N from which score functions may be taken.
In app. C.1 we stated that if {fd (x)}d∈N is a total set in L2 (Rs ), i.e. if every function in L2 (Rs ) can
be arbitrarily well approximated by a linear combination of a finite subset of {fd (x)}d∈N , then the point
QN
wise products {(x1 , . . . , xN ) 7→ i=1 fdi (xj )}d1 ,...,dN ∈N form a total set in L2 (Rs )N . Accordingly, in a
universal hypotheses space H = L2 (Rs )N , any score function hy may be arbitrarily well approximated by
finite linear combinations of such point-wise products. A possible formulation of this would be as follows.
Assume we are interested in -approximation of the score function hy , and consider a formal tensor Ay
having N modes and a countable infinite dimension in each mode i ∈ [N ], indexed by di ∈ N. Then, there
exists such a tensor, with all but a finite number of entries set to zero, for which:
hy (x1 , . . . , xN ) ≈

X
d1 ...dN ∈N

25

Ayd1 ,...,dN

N
Y
i=1

fdi (xi )

(6)

C OHEN S HARIR S HASHUA

Given that the set of functions {fd (x)}d∈N ⊂L2 (Rs ) is total, eq. 6 defines a universal hypotheses space.
There are many possibilities for choosing a total set of functions. Wavelets are perhaps the most obvious
choice, and were indeed used in a deep network setting by Bruna and Mallat (2012). The special case of
Gabor wavelets has been claimed to induce features that resemble representations in the visual cortex (Serre
et al. (2005)). Two options we pay special attention to due to their importance in practice are:
• Gaussians (with diagonal covariance):
fθ (x) = N x; µ, diag(σ 2 )



(7)

where θ = (µ ∈ Rs , σ 2 ∈ Rs++ ).
• Neurons:

fθ (x) = σ x> w + b

(8)

s

where θ = (w ∈ R , b ∈ R) and σ is a point-wise non-linear activation such as threshold σ(z) =
1 [z > 0], rectified linear unit (ReLU) σ(z) = max{z, 0} or sigmoid σ(z) = 1/(1 + e−z ).
In both cases, there is an underlying parametric family of functions F = {fθ : Rs → R}θ∈Θ of which
a countable total subset may be chosen. The fact that Gaussians as above are total in L2 (Rs ) has been
proven in Girosi and Poggio (1990), and is a direct corollary of the Stone-Weierstrass theorem. To achieve
countability, simply consider Gaussians with rational parameters (mean and variances). In practice, the choice
of Gaussians (with diagonal covariance) give rises to a “similarity” operator as described by the SimNet
architecture (Cohen and Shashua (2014); Cohen et al. (2016)). For the case of neurons we must restrict the
domain Rs to some bounded set, otherwise the functions are not integrable. This however is not a limitation
in practice, and indeed neurons are widely used across many application domains. The fact that neurons
are total has been proven in Cybenko (1989) and Hornik et al. (1989) for threshold and sigmoid activations.
More generally, it has been proven in Stinchcombe and White (1989) for a wide class of activation functions,
including linear combinations of ReLU. See Pinkus (1999) for a survey of such results. For countability, we
may again restrict parameters (weights and bias) to be rational.
In the case of Gaussians and neurons, we argue that a finite set of functions suffices, i.e. that it is
possible to choose fθ1 . . .fθM ∈ F that will suffice in order to represent score functions required for natural
tasks. Moreover, we claim that M need not be large (e.g. on the order of 100). Our argument relies on
statistical properties of natural images, and is fully detailed in app. C.3. It impliesQthat under proper choice of
N
{fθd (x)}d∈[M ] , the finite set of point-wise product functions {(x1 , . . . , xN ) 7→ i=1 fθdi (xi )}d1 ,...,dN ∈[M ]
spans the score functions of interest, and we may define for each label y a tensor Ay of order N and dimension
M in each mode, such that:
hy (x1 , . . . , xN ) =

M
X
d1 ,...,dN =1

Ayd1 ,...,dN

N
Y

fθdi (xi )

(2)

i=1

which is exactly the hypotheses space presented in sec. 3. Notice that if {fθd (x)}d∈[M ] ⊂L2 (Rs ) are linearly
independent (there is no reason to choose them otherwise), then so are the product functions {(x1 , . . . , xN ) 7→

QN
2
(Rs )N (see app. C.1), and a score function hy uniquely determines the
i=1 fθdi (xi )}d1 ,...,dN ∈[M ] ⊂L
coefficient tensor Ay . In other words, two score functions hy,1 and hy,2 are identical if and only if their
coefficient tensors Ay,1 and Ay,2 are the same.

C.3. Finite Function Bases for Classification of Natural Data
In app. C.2 we laid out the framework of classifying instances in the space X := {(x1 , . . . , xN ) : xi ∈ Rs } =
(Rs )N into labels Y := {1, . . . , Y } via maximization of per-label score functions hy : X → R:
ŷ(x1 , . . . , xN ) = argmax hy (x1 , . . . , xN )
y∈Y

26

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

where hy (x1 , . . . , xN ) is of the form:
hy (x1 , . . . , xN ) =

M
X

Ayd1 ,...,dN

N
Y

fθdi (xi )

(2)

i=1

d1 ,...,dN =1

and {fθ }d∈[M ] are selected from a parametric family of functions F = {fθ : Rs → R}θ∈Θ . For universality,
i.e. for the ability of score functions hy to approximate any function in L2 (X ) as M → ∞, we required that it
be possible to choose a countable subset of F that is total in L2 (Rs ). We noted that the families of Gaussians
(eq. 7) and neurons (eq. 8) meet this requirement.
In this subsection we formalize our argument that a finite value for M is sufficient when X represents
natural data, and in particular, natural images. Based on empirical studies characterizing the statistical properties of natural images, and in compliance with the number of channels in a typical convolutional network
layer, we find that M on the order of 100 typically suffices.
Let D be a distribution of labeled instances (X, ȳ) over X × Y (we use bar notation to distinguish the
label ȳ from the running index y), and DX be the induced marginal distribution of instances X over X . We
would like to show, given particular assumptions on D, that there exist functions fθ1 , . . . , fθM ∈ F and
tensors A1 , . . . , AY of order N and dimension M in each mode, such that the score functions hy defined in
eq. 2 achieve low classification error:
 

L0−1
(h
,
.
.
.
,
h
)
:=
E
1
ȳ
=
6
argmax
h
(X)
(9)
1
Y
y
(X,ȳ)∼D
D
y∈Y

1 [·] here stands for the indicator function, taking the value 1 when its argument is true, and 0 otherwise.

Let {h∗y }y∈Y be a set of “ground truth” score functions for which optimal prediction is achieved, or more
specifically, for which the expected hinge-loss (upper bounds the 0-1 loss) is minimal:
(h∗1 , . . . , h∗Y ) =
where:

argmin
h01 ,...,h0Y :X →R

Lhinge
(h01 , . . . , h0Y )
D




0
0
0
0
Lhinge
(h
,
.
.
.
,
h
)
:=
E
max
1
[y
=
6
ȳ]
+
h
(X)
−
h
(X)
(X,ȳ)∼D
1
Y
y
ȳ
D
y∈Y

(10)

Our strategy will be to select score functions hy of the format given in eq. 2, that approximate h∗y in the sense
of low expected maximal absolute difference:


E := EX∼DX max hy (X) − h∗y (X)
(11)
y∈Y

We refer to E as the score approximation error obtained by hy . The 0-1 loss of hy with respect to the labeled
example (X, ȳ) ∈ X × Y is bounded as follows:


1 ȳ 6= argmax hy (X) ≤ max {1 [y 6= ȳ] + hy (X)} − hȳ (X)
y∈Y

y∈Y

1 [y 6= ȳ] +

+ hy (X) − h∗y (X) − h∗ȳ (X) + h∗ȳ (X) − hȳ (X)


≤ max 1 [y 6= ȳ] + h∗y (X) − h∗ȳ (X) + max hy (X) − h∗y (X) + h∗ȳ (X) − hȳ (X)
y∈Y
y∈Y


∗
∗
≤ max 1 [y 6= ȳ] + hy (X) − hȳ (X) + 2 max hy (X) − h∗y (X)

= max
y∈Y



h∗y (X)

y∈Y

y∈Y

Taking expectation of the first and last terms above with respect to (X, ȳ) ∼ D, and recalling the definitions
given in eq. 9, 10 and 11, we get:
hinge ∗
L0−1
(h1 , . . . , h∗Y ) + 2E
D (h1 , . . . , hY ) ≤ LD

27

C OHEN S HARIR S HASHUA

In words, the classification error of the score functions hy is bounded by the optimal expected hinge-loss
plus a term equal to twice their score approximation error. Recall that we did not constrain the optimal score
functions h∗y in any way. Thus, assuming a label is deterministic given an instance, the optimal expected
hinge-loss is essentially zero, and the classification error of hy is dominated by their score approximation
error E (eq. 11). Our problem thus translates to showing that hy can be selected such that E is small.
At this point we introduce our main assumption on the distribution D, or more specifically, on the
marginal distribution of instances DX . According to various studies, in natural settings, the marginal distribution of individual vectors in X , e.g. of small patches in images, may be relatively well captured by a
Gaussian Mixture Model (GMM) with a moderate number (on the order of 100 or less) of distinct components. For example, it was shown in Zoran and Weiss (2012) that natural image patches of size 2×2, 4×4,
8×8 or 16×16, can essentially be modeled by GMMs with 64 components (adding more components barely
improved the log-likelihood). This complies with the common belief that a moderate number of low-level
templates suffices in order to model the vast majority of local image patches. Following this line, we model
the marginal distribution of xi with a GMM having M components with means µ1 . . .µM ∈ Rs . We assume
that the components are well localized, i.e. that their standard deviations are small compared to the distances
between means, and also compared to the variation of the target functions h∗y . In the context of images for
example, the latter two assumptions imply that a local patch can be unambiguously assigned to a template,
and that the assignment of patches to templates determines the class of an image. Returning to general instances X, their probability mass will be concentrated in distinct regions of the space X , in which for every
i ∈ [N ], the vector xi lies near µci for some ci ∈ [M ]. The score functions h∗y are approximately constant
in each such region. It is important to stress here that we do not assume statistical independence of xi ’s, only
that their possible values can be quantized into M templates µ1 , . . . , µM .
Under our idealized assumptions on DX , the expectation in the score approximation error E can be
discretized as follows:


M
X
E := EX∼DX max hy (X) − h∗y (X) =
Pc1 ,...,cN max hy (Mc1 ,...,cN ) − h∗y (Mc1 ,...,cN )
y∈Y

y∈Y

c1 ,...,cN =1

(12)
where Mc1 ,...,cN := (µP
c1 , . . . , µcN ) and Pc1 ,...,cN stands for the probability that xi lies near µci for every
i ∈ [N ] (Pc1 ,...,cN ≥0,
c1 ,...,cN Pc1 ,...,cN = 1).
We now turn to show that fθ1 . . .fθM can be chosen to separate GMM components, i.e. such that for
every c, d ∈ [M ], fθd (µc ) 6= 0 if and only if c = d. If the functions fθ are Gaussians (eq. 7), we can simply
set the mean of fθd to µd , and its standard deviations to be low enough such that the function effectively
vanishes at µc when c 6= d. If fθ are neurons (eq. 8), an additional requirement is needed, namely that the
GMM component means µ1 . . .µM be linearly separable. In other words, we require that for every d ∈ [M ],
there exist wd ∈ Rs and bd ∈ R for which wd> µc + bd is positive if c = d and negative otherwise. This may
seem like a strict assumption at first glance, but notice that the dimension s is often as large, or even larger,
then the number of components M . In addition, if input vectors xi are normalized to unit length (a standard
practice with image patches for example), µ1 . . .µM will also be normalized, and thus linear separability is
trivially met. Assuming we have linear separability, one may set θd = (wd , bd ), and for threshold or ReLU
activations we indeed get fθd (µc ) 6= 0 ⇐⇒ c = d. With sigmoid activations, we may need to scale (wd , bd )
so that wd> µc + bd  0 when c6=d, and that would ensure that in this case fθd (µc ) effectively vanishes.
Assuming we have chosen fθ1 . . .fθM to separate GMM components, and plugging-in the format of hy
given in eq. 2, we get the following convenient form for hy (Mc1 ,...,cN ):
hy (Mc1 ,...,cN ) = Ayc1 ,...,cN

N
Y

fθci (µci )

i=1

Assigning the coefficient tensors through the following rule:
h∗y (Mc1 ,...,cN )
Ayc1 ,...,cN = QN
i=1 fθci (µci )
28

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

implies:
hy (Mc1 ,...,cN ) = h∗y (Mc1 ,...,cN )
for every y ∈ Y and c1 . . .cN ∈ [M ]. Plugging this into eq. 12, we get a score approximation error of zero.
To recap, we have shown that when the parametric functions fθ are Gaussians (eq. 7) or neurons (eq. 8),
not only are the score functions hy given in eq. 2 universal when M → ∞ (see app. C.2), but they can also
achieve zero classification error (eq. 9) with a moderate value of M (on the order of 100) if the underlying
data distribution D is “natural”. In this context, D is regarded as natural if it satisfies two conditions. The
first, which is rather mild, requires that a label be completely determined by the instance. For example, an
image will belong to one category with probability one, and to the rest of the categories with probability
zero. The second condition, which is far more restrictive, states that input vectors composing an instance
can be quantized into a moderate number (M ) of templates. The assumption that natural images exhibit this
property is based on various empirical studies where it is shown to hold approximately. Since it does not hold
exactly, our analysis is approximate, and its implication in practice is that the classification error introduced
by constraining score functions to have the format given in eq. 2, is negligible compared to other sources of
error (factorization of the coefficient tensors, finiteness of training data and difficulty in optimization).

Appendix D. Related Work
The classic approach for theoretically analyzing the power of depth focused on investigation of the computational complexity of boolean circuits. An early result, known as the “exponential efficiency of depth”,
may be summarized as follows: for every integer k, there are boolean functions that can be computed by a
circuit comprising alternating layers of AND and OR gates which has depth k and polynomial size, yet if one
limits the depth to k − 1 or less, an exponentially large circuit is required. See Sipser (1983) for a formal
statement of this classic result. Recently, Rossman et al. (2015) have established a somewhat stronger result,
showing cases where not only are polynomially wide shallow boolean circuits incapable of exact realization,
but also of approximation (i.e. of agreeing with the target function on more than a specified fraction of input
combinations). Other classical results are related to threshold circuits, a class of models more similar to
contemporary neural networks than boolean circuits. Namely, they can be viewed as neural networks where
each neuron computes a weighted sum of its inputs (possibly including bias), followed by threshold activation
(σ(z) = 1[z ≥ 0]). For threshold circuits, the main known result in our context is the existence of functions
that separate depth 3 from depth 2 (see Hajnal et al. (1987) for a statement relating to exact realization, and
the techniques in Maass et al. (1994); Martens et al. (2013) for extension to approximation).
More recent studies focus on arithmetic circuits (Shpilka and Yehudayoff (2010)), whose nodes typically
compute either a weighted sum or a product of their inputs 9 (besides their role in studying expressiveness,
deep networks of this class have been shown to support provably optimal training Livni et al. (2014)). A special case of this are the Sum-Product Networks (SPNs) presented in Poon and Domingos (2011). SPNs are
a class of deep generative models designed to efficiently compute probability density functions. Their summation weights are typically constrained to be non-negative (such an arithmetic circuit is called monotone),
and in addition, in order for them to be valid (i.e. to be able to compute probability density functions), additional architectural constraints are needed (e.g. decomposability and completeness). The most widely known
theoretical arguments regarding the efficiency of depth in SPNs were given in Delalleau and Bengio (2011).
In this work, two specific families of SPNs were considered, both comprising alternating sum and product
layers – a family F whose nodes form a full binary tree, and a family G with n nodes per layer (excluding
the output), each connected to n − 1 nodes in the preceding layer. The authors show that functions implemented by these networks require an exponential number of nodes in order to be realized by shallow (single
9. There are different definitions for arithmetic circuits in the literature. We adopt the definition given in Martens and
Medabalimi (2014), under which an arithmetic circuit is a directed acyclic graph, where nodes with no incoming
edges correspond to inputs, nodes with no outgoing edges correspond to outputs, and the remaining nodes are either
labeled as “sum” or as “product”. A product node computes the product of its child nodes. A sum node computes a
weighted sum of its child nodes, where the weights are parameters linked to its incoming edges.

29

C OHEN S HARIR S HASHUA

hidden-layer networks). The limitations of this work are twofold. First, as the authors note themselves, it only
analyzes the ability of shallow networks to realize exactly functions generated by deep networks, and does
not provide any result relating to approximation. Second, the specific SPN families considered in this work
are not universal hypothesis classes and do not resemble networks used in practice. Recently, Martens and
Medabalimi (2014) proved that there exist functions which can be efficiently computed by decomposable and
complete (D&C) SPNs of depth d + 1, yet require a D&C SPN of depth d or less to have super-polynomial
size for exact realization. This analysis only treats approximation in the limited case of separating depth 4
from depth 3 (D&C) SPNs. Additionally, it only deals with specific separating functions, and does not convey information regarding how frequent these are. In other words, according to this analysis, it may be that
almost all functions generated by deep networks can be efficiently realized by shallow networks, and there
are only few pathological functions for which this does not hold. A further limitation of this analysis is that
for general d, the separation between depths d + 1 and d is based on a multilinear circuit result by Raz and
Yehudayoff (2009), that translates into a network that once again does not follow the common practices of
deep learning.
There have been recent attempts to analyze the efficiency of network depth in other settings as well.
The most commonly used type of neural networks these days includes neurons that compute a weighted
sum of their inputs (with bias) followed by Rectified Linear Unit (ReLU) activation (σ(z) = max{0, z}).
Pascanu et al. (2013) and Montufar et al. (2014) study the number of linear regions that may be expressed
by such networks as a function of their depth and width, thereby showing existence of functions separating
deep from shallow (depth 2) networks. Telgarsky (2015) shows a simple construction of a depth d width 2
ReLU network that operates on one-dimensional inputs, realizing a function that cannot be approximated by
ReLU networks of depth o(d/ log d) and width polynomial in d. Eldan and Shamir (2015) provides functions
expressible by ReLU networks of depth 3 and polynomial width, which can only be approximated by a depth
2 network if the latter’s width is exponential. The result in this paper applies not only to ReLU activation,
but also to the standard sigmoid (σ(z) = 1/(1 + e−z )), and more generally, to any universal activation (see
assumption 1 in Eldan and Shamir (2015)). Bianchini and Scarselli (2014) also considers different types of
activations, studying the topological complexity (through Betti numbers) of decision regions as a function of
network depth, width and activation type. The results in this paper establish the existence of deep vs. shallow
separating functions only for the case of polynomial activation. While the above works do address more
conventional neural networks, they do not account for the structure of convolutional networks – the most
successful deep learning architectures to date, and more importantly, they too prove only existence of some
separating functions, without providing any insight as to how frequent these are.
We are not the first to incorporate ideas from the field of tensor analysis into deep learning. Socher
et al. (2013), Yu et al. (2012), Setiawan et al. (2015), and Hutchinson et al. (2013) all proposed different
neural network architectures that include tensor-based elements, and exhibit various advantages in terms of
expressiveness and/or ease of training. In Janzamin et al. (2015), an alternative algorithm for training neural networks is proposed, based on tensor decomposition and Fourier analysis, with proven generalization
bounds. In Novikov et al. (2014), Anandkumar et al. (2014), Yang and Dunson (2015) and Song et al. (2013),
algorithms for tensor decompositions are used to estimate parameters of different graphical models. Notably, Song et al. (2013) uses the relatively new Hierarchical Tucker decomposition (Hackbusch and Kühn
(2009)) that we employ in our work, with certain similarities in the formulations. The works differ considerably in their objectives though: while Song et al. (2013) focuses on the proposal of a new training algorithm,
our purpose in this work is to analyze the expressive efficiency of networks and how that depends on depth.
Recently, Lebedev et al. (2014) modeled the filters in a convolutional network as four dimensional tensors,
and used the CP decomposition to construct an efficient and accurate approximation. Another work that draws
a connection between tensor analysis and deep learning is the recent study presented in Haeffele and Vidal
(2015). This work shows that with sufficiently large neural networks, no matter how training is initialized,
there exists a local optimum that is accessible with gradient descent, and this local optimum is approximately
equivalent to the global optimum in terms of objective value.

30

O N THE E XPRESSIVE P OWER OF D EEP L EARNING : A T ENSOR A NALYSIS

Appendix E. Computation in Log-Space with SimNets
A practical issue one faces when implementing arithmetic circuits is the numerical instability of the product
operation – a product node with a large number of inputs is easily susceptible to numerical overflow or
underflow. A common solution to this is to perform the computations in log-space, i.e. instead of computing
activations we compute their log. This requires the activations to be non-negative toQ
begin with,
P and alters
the sum and product operations as follows. A product simplyPturns into a P
sum, as log i αi = i log αi . A
sum becomes what is known as log-sum-exp or softmax: log i αi = log i exp(log αi ).
Turning to our networks, the requirement that all activations be non-negative does not limit their universality. The reason for this is that the functions fθ are non-negative in both cases of interest – Gaussians (eq. 7)
and neurons (eq. 8). In addition, one can always add a common offset to all coefficient tensors Ay , ensuring
they are positive without affecting classification. Non-negative decompositions (i.e. decompositions with all
weights holding non-negative values) can then be found, leading all network activations to be non-negative.
In general, non-negative tensor decompositions may be less efficient than unconstrained decompositions, as
there are cases where a non-negative tensor supports an unconstrained decomposition that is smaller than its
minimal non-negative decomposition. Nevertheless, as we shall soon see, these non-negative decompositions
translate into a proven architecture, which was demonstrated to achieve comparable performance to state of
the art convolutional networks, thus in practice the deterioration in efficiency does not seem to be significant.
Naı̈vely implementing CP or HT model (fig. 1 or 2 respectively) in log-space translates to log activation
following the locally connected linear transformations (convolutions if coefficients are shared, see sec. 3.3),
to product pooling turning into sum pooling, and to exp activation following the pooling. However, applying
exp and log activations as just described, without proper handling of the inputs to each computational layer,
would not result in a numerically stable computation 10 .
The SimNet architecture (Cohen and Shashua (2014); Cohen et al. (2016)) naturally brings forth a numerically stable implementation of our networks. The architecture is based on two ingredients – a flexible
similarity measure and the MEX operator:


X
1
1
exp(β(xj + bj ))
MEXβ (x, b) := log 
β
N j
The similarity layer, capable of computing both the common convolutional operator as well as weighted
lp norm, may realize the representation by computing log fθ (xi ), whereas MEX can naturally implement
both log-sum-exp and sum-pooling (limβ→0 MEXβ (x, 0) = meanj {xj }) in a numerically stable manner.
Not only are SimNets capable of correctly and efficiently implementing our networks, but they have
already been demonstrated (Cohen et al. (2016)) to perform as well as state of the art convolutional networks
on several image recognition benchmarks, and outperform them when computational resources are limited.

10. Naı̈ve implementation of softmax is not numerically stable, as it involves storing αiP= exp(log αi ) directly. This
however can be easily corrected by defining c := maxi log αi , and computing log i exp(log αi − c) + c. The
result is identical, but now we only exponentiate negative numbers (no overflow), with at least one of these numbers
equal to zero (no underflow).

31

