Published as a conference paper at ICLR 2018

O N THE E XPRESSIVE P OWER OF OVERLAPPING
A RCHITECTURES OF D EEP L EARNING
Or Sharir & Amnon Shashua
The Hebrew University of Jerusalem
{or.sharir,shashua}@cs.huji.ac.il

arXiv:1703.02065v4 [cs.LG] 24 Feb 2018

A BSTRACT
Expressive efficiency refers to the relation between two architectures A and B,
whereby any function realized by B could be replicated by A, but there exists
functions realized by A, which cannot be replicated by B unless its size grows significantly larger. For example, it is known that deep networks are exponentially
efficient with respect to shallow networks, in the sense that a shallow network
must grow exponentially large in order to approximate the functions represented
by a deep network of polynomial size. In this work, we extend the study of expressive efficiency to the attribute of network connectivity and in particular to the
effect of ”overlaps” in the convolutional process, i.e., when the stride of the convolution is smaller than its filter size (receptive field). To theoretically analyze
this aspect of network’s design, we focus on a well-established surrogate for ConvNets called Convolutional Arithmetic Circuits (ConvACs), and then demonstrate
empirically that our results hold for standard ConvNets as well. Specifically, our
analysis shows that having overlapping local receptive fields, and more broadly
denser connectivity, results in an exponential increase in the expressive capacity of
neural networks. Moreover, while denser connectivity can increase the expressive
capacity, we show that the most common types of modern architectures already
exhibit exponential increase in expressivity, without relying on fully-connected
layers.

1

I NTRODUCTION

One of the most fundamental attributes of deep networks, and the reason for driving its empirical
success, is the “Depth Efficiency” result which states that deeper models are exponentially more
expressive than shallower models of similar size. Formal studies of Depth Efficiency include the
early work on boolean or thresholded circuits (Sipser, 1983; Yao, 1989; Håstad and Goldmann,
1991; Hajnal et al., 1993), and the more recent studies covering the types of networks used in
practice (Pascanu et al., 2013; Montúfar et al., 2014; Eldan and Shamir, 2016; Cohen et al., 2016a;
Cohen and Shashua, 2016; Telgarsky, 2016; Safran and Shamir, 2016; Raghu et al., 2016; Poole
et al., 2016). What makes the Depth Efficiency attribute so desirable, is that it brings exponential
increase in expressive power through merely a polynomial change in the model, i.e. the addition
of more layers. Nevertheless, depth is merely one among many architectural attributes that define
modern networks. The deep networks used in practice consist of architectural features defined by
various schemes of connectivity, convolution filter defined by size and stride, pooling geometry and
activation functions. Whether or not those relate to expressive efficiency, as depth has proven to be,
remains an open question.
In order to study the effect of network design on expressive efficiency we should first define ”efficiency” in broader terms. Given two network architectures A and B, we say that architecture A is
expressively efficient with respect to architecture B, if the following two conditions hold: (i) any
function h realized by B of size rB can be realized (or approximated) by A with size rA ∈ O(rB );
(ii) there exist a function h realized by A with size rA , that cannot be realized (or approximated)
by B, unless rB ∈ Ω(f (rA )) for some super-linear function f . The exact definition of the sizes rA
and rB depends on the measurement we care about, e.g. the number of parameters, or the number
of “neurons”. The nature of the function f in condition (ii) determines the type of efficiency taking
place – if f is exponential then architecture A is said to be exponentially efficient with respect to
1

Published as a conference paper at ICLR 2018

architecture B, and if f is polynomial so is the expressive efficiency. Additionally, we say A is
completely efficient with respect to B, if condition (ii) holds not just for some specific functions
(realizable by A), but for all functions other than a negligible set.
In this paper we study the efficiency associated with the architectural attribute of convolutions,
namely the size of convolutional filters (receptive fields) and more importantly its proportion to
their stride. We say that a network architecture is of the non-overlapping type when the size of the
local receptive field in each layer is equal to the stride. In that case, the sets of pixels participating
in the computation of each two neurons in the same layer are completely separated. When the stride
is smaller than the receptive field we say that the network architecture is of the overlapping type. In
the latter case, the overlapping degree is determined by the total receptive field and stride projected
back to the input layer – the implication being that for the overlapping architecture the total receptive
field and stride can grow much faster than with the non-overlapping case.
As several studies have shown, non-overlapping convolutional networks do have some theoretical
merits. Namely, non-overlapping networks are universal (Cohen et al., 2016a; Cohen and Shashua,
2016), i.e. they can approximate any function given sufficient resources, and in terms of optimization, under some conditions they actually possess better convergence guaranties than overlapping
networks. Despite the above, there are only few instances of strictly non-overlapping networks used
in practice (e.g. Sharir et al. (2016); van den Oord et al. (2016)), which raises the question of why
are non-overlapping architectures so uncommon? Additionally, when examining the kinds of
architectures typically used in recent years, which employ a mixture of both overlapping and nonoverlapping layers, there is a trend of using ever smaller receptive fields, as well as non-overlapping
layers having an ever increasing role (Lin et al., 2014; Springenberg et al., 2015; Szegedy et al.,
2015). Hence, the most common networks used practice, though not strictly non-overlapping, are
increasingly approaching the non-overlapping regime, which raises the question of why having just
slightly overlapping architectures seems sufficient for most tasks?
In the following sections, we will shed some light on these questions by analyzing the role of
overlaps through a surrogate class of convolutional networks called Convolutional Arithmetic Circuits (ConvACs) (Cohen et al., 2016a) – instead of non-linear activations and average/max pooling
layers, they employ linear activations and product pooling. ConvACs, as a theoretical framework to
study ConvNets, have been the focused of several works, showing, amongst other things, that many
of the results proven on this class are typically transferable to standard ConvNets as well (Cohen
and Shashua, 2016; 2017). Though prior works on ConvACs have only considered non-overlapping
architectures, we suggest a natural extension to the overlapping case that we call Overlapping ConvACs. In our analysis, which builds on the known relation between ConvACs and tensor decompositions, we prove that overlapping architectures are in fact completely and exponentially more efficient
than non-overlapping ones, and that their expressive capacity is directly related to their overlapping
degree. Moreover, we prove that having even a limited amount of overlapping is sufficient for attaining this exponential separation. To further ground our theoretical results, we demonstrate our
findings through experiments with standard ConvNets on the CIFAR10 image classification dataset.

2

OVERLAPPING C ONVOLUTIONAL A RITHMETIC C IRCUITS

In this section, we introduce a class of convolutional networks referred to as Overlapping Convolutional Arithmetic Circuits, or Overlapping ConvACs for short. This class shares the same architectural features as standard ConvNets, including some that have previously been overlooked by
similar attempts to model ConvNets through ConvACs, namely, having any number of layers and
unrestricted receptive fields and strides, which are crucial for studying overlapping architectures.
For simplicity, we will describe this model only for the case of inputs with two spatial dimensions,
e.g. color images, and limiting the convolutional filters to the shape of a square.
We begin by presenting a broad definition of
a Generalized Convolutional (GC) layer as a
fusion of a 1×1 linear operation with a pooling function – this view of convolutional layers
is motivated by the all-convolutional architecture (Springenberg et al., 2015), which replaces
all pooling layers with convolutions with stride

previous layer

H(in)

R

H(out)

(R)
x(1) · · · x
.. . .
.
. ..
.

x(R

R

H(in)

2

GC layer

2

D(out)

H (out) = H (in)
S

)

D(in)

2

2

2

y = g(W (1) x(1) + b(1) , . . . , W (R ) x(R ) + b(R ) )

Figure 1: An illustration of a GC Layer.

Published as a conference paper at ICLR 2018

input

representa(on hidden layer 1
GC

hidden
layer L-2

hidden
layer L-1

GC

R(1),S(1)

xi

GC
(output)

GC

R(L-2),S(L-2)

rep(i, d) = f✓d (xi )

M

D(1)

D(L-2)

D(L-1)

D(L)
hy (x1 , . . . , xN )

Figure 2: An illustration of a Generalized Convolutional Network.
greater than 1. The input to a GC layer is a 3order tensor (multi-dimensional array), having
width and height equal to H (in) ∈ N and depth
D(in) ∈ N, also referred to as channels, e.g. the
input could be a 2D image with RGB color channels. Similarly, the output of the layer has width
(in)
and height equal to H (out) ∈ N and D(out) ∈ N channels, where H (out) = HS for S ∈ N that is
referred to as the stride, and has the role of a sub-sampling operation. Each spatial location (i, j) at
the output of the layer corresponds to a 2D window slice of the input tensor of size R × R × D(in) ,
extended through all the input channels, whose top-left corner is located exactly at (i·S, j ·S), where
R ∈ N is referred to as its local receptive field, or filter size. For simplicity, the parts of window
((out)
slices extending beyond the boundaries have zero value. Let y ∈ RD
be a vector representing
(in)
(1)
(R2 )
the channels at some location of the output, and similarly, let x , . . . , x
∈ RD be the set of
vectors representing the slice, where each vector represents the channels at its respective location
inside the R × R window, then the operation of a GC layer is defined as follows:
2

2

2

y = g(W (1) x(1) + b(1) , . . . , W (R ) x(R ) + b(R ) ),

2

(out)

(in)

2

(out)

×D
where W (1) , . . . , W (R ) ∈ RD
and b(1) , . . . , b(R ) ∈ RD
are referred to as the
(out)
(out)
(out)
weights and biases of the layer, respectively, and g : RD
× · · · × RD
→ RD
is some
point-wise pooling function. See fig. 1 for an illustration of the operation a GC layer performs.

With the above definitions, a GC network is simply a sequence of L GC layers, where for l ∈
[L] ≡ {1, . . . , L}, the l’th layer is specified by a local receptive field R(l) , a stride S (i) , D(l) output
channels, parameters θ(l) , and a pooling function g (l) . For classification tasks, the output of the last
layer of the network typically has 1×1 spatial dimensions, i.e. a vector, where each output channel
y ∈ [Y ] ≡ [D(L) ] represents the score function of the y’th class, denoted by hy , and inference is
perform by y ∗ = arg maxy hy (X). Oftentimes, it is common to consider the output of the very
first layer of a network as a low-level feature representation of the input, which is motivated by
the observation that these learned features are typically shared across different tasks and datasets
over the same domain (e.g. edge and Gabor filters for natural images). Hence, we treat this layer
as a separate fixed “zeroth” convolutional layer referred to as the representation layer, where the
operation of the layer can be depicted as applying a set of fixed functions {fd : Rs → R}M
d=1 to the
window slices denoted by x1 , . . . , xN ∈ Rs , i.e. the entries of the output tensor of this layer are
given by {fd (xi )}d∈[M ],i∈[N ] . With these notations, the output of a GC network can be viewed as a
function hy (x1 , . . . , xN ). The entire GC network is illustrated in fig. 2.
Given a non-linear point-wise activation function σ(·) (e.g. ReLU), then settingall poolingfunctions
PR2 (i)
2
for c ∈
to average pooling followed by the activation, i.e. g(x(1) , . . . , x(R ) )c = σ
i=1 xc

[D(out) ], give rise to the common all-convolutional network with σ(·) activations, which served
as the initial motivation for our formulation. Alternatively, choosing instead a product pooling
QR2 (i)
2
function, i.e. g(x(1) , . . . , x(R ) )c = i=1 xc for c ∈ [D(out) ], results in an Arithmetic Circuit,
i.e. a circuit containing just product and sum operations, hence it is referred to as a Convolutional
Arithmetic Circuit, or ConvAC. It is important to emphasize that ConvACs, as originally introduced
by Cohen et al. (2016a), are typically described in a very different manner, through the language
of tensor decompositions (see app. A for background). Since vanilla ConvACs can be seen as an
alternating sequence of 1×1 convolutions and non-overlapping product pooling layers, then the two
formulations coincide when all GC layers are non-overlapping, i.e. for all l ∈ [L], R(l) = S (l) . If,
however, some of the layers are overlapping, i.e. there exists l ∈ [L] such that R(l) > S (l) , then our
formulation through GC layers diverges, and give rise to what we call Overlapping ConvACs.
3

Published as a conference paper at ICLR 2018

Given that our model is an extension of the ConvACs framework, it inherits many of its desirable
attributes. First, it shares most of the same traits as modern ConvNets, i.e. locality, sharing and pooling. Second, it can be shown to form a universal hypotheses space (Cohen et al., 2016a). Third, its
underlying operations lend themselves to mathematical analysis based on measure theory and tensor
analysis (Cohen et al., 2016a). Forth, through the concept of generalized tensor decompositions (Cohen and Shashua, 2016), many of the theoretical results proven on ConvACs could be transferred
to standard ConvNets with ReLU activations. Finally, from an empirical perspective, they tend to
work well in many practical settings, e.g. for optimal classification with missing data (Sharir et al.,
2016), and for compressed networks (Cohen et al., 2016b).
While we have just established that the non-overlapping GC Network with a product pooling function is equivalent to vanilla ConvACs, one might wonder if using overlapping layers instead could
diminish what these overlapping networks can represent. We show that not only is it not the case,
but prove the more general claim that a network of a given architecture can realize exactly the same
functions as networks using smaller local receptive fields, which includes the non-overlapping case.
Proposition 1. Let A and B be two GC Networks with a product pooling function. If the architecture
of B can be derived from A through the removal of layers with 1×1 stride, or by decreasing the local
receptive field of some of its layers, then for any choice of parameters for B, there exists a matching
set of parameters for A, such that the function realized by B is exactly equivalent to A. Specifically,
A can realize any non-overlapping network with the same order of strides (excluding 1×1 strides).
Proof sketch. This follows from two simple claims: (i) a GC layer can produce an output equivalent
to that of a GC layer with a smaller local receptive field, by “zeroing” its weights beyond the smaller
local receptive field; and (ii) GC layers with 1×1 receptive fields can be set such that their output is
equal to their input, i.e. realize the identity function. With these claims, the local receptive fields of
A can be effectively shrank to match the local receptive fields of B, and any additional layers of A
with stride 1×1 could be set such that they are realizing the identity mapping, effectively “removing”
them from A. See app. C.2 for a complete proof.
Proposition 1 essentially means that overlapping architectures are just as expressive as nonoverlapping ones of similar structure, i.e. same order of non-unit strides. As we recall, this satisfies the first condition of the efficiency property introduced in sec. 1, and does so regardless if we
measure the size of a network as the number of parameters, or the number of “neurons”1 . In the following section we will cover the preliminaries required to show that overlapping networks actually
lead to an increase in expressive capacity, which under some settings results in an exponential gain,
proving that the second condition of expressive efficiency holds as well.

3

A NALYZING E XPRESSIVE E FFICIENCY T HROUGH G RID T ENSORS

In this section we describe our methods for analyzing the expressive efficiency of overlapping ConvACs that lay the foundation for stating our theorems. A minimal background on tensor analysis
required to follow our work can be found in sec. 3.1, followed by presenting our methods in sec. 3.2.
3.1

P RELIMINARIES

In this sub-section we cover the minimal background on tensors analysis required to understand
our analysis. A tensor A ∈ RM1 ⊗···⊗MN of order N and dimension Mi in each mode i ∈ [N ] ≡
{1, . . . , N }, is a multi-dimensional array with entries Ad1 ,...,dN ∈ R for all i ∈ [N ] and di ∈ [Mi ].
For simplicity, henceforth we assume that all dimensions are equal, i.e. M ≡ M1 = . . . = MN .
One of the central concepts in tensor analysis is that of tensor matricization, i.e. rearranging its
entries to the shape of a matrix. Let P ∪· Q = [N ] be a disjoint partition of its indices, such that
P = {p1 , . . . , p|P | } with p1 < . . . < p|P | , and Q = {q1 , . . . , q|Q| } with q1 < . . . < q|Q| . The
matricization of A with respect to the partition P ∪· Q, denoted by JAKP,Q , is the M |P | -by-M |Q|
matrix holding the entries of A, such that for all i ∈ [N ] and di ∈ [M ] the entry Ad1 ,...,dN is placed
1
We take here the broader definition of a “neuron”, as any one of the scalar values comprising the output
array of an arbitrary layer in a network. In the case the output array is of width and height equal to H and C
channels, then the number of such “neurons” for that layer is H 2 · C.

4

Published as a conference paper at ICLR 2018

P|P |
P|Q|
in row index 1 + t=1 (dpt − 1)M |P |−t and column index 1 + t=1 (dqt − 1)M |Q|−t . Lastly, the
tensors we study in this article originate by examining the values of some given function at a set
of predefined points and arranging them in a tensor referred to as the grid tensor of the function.
Formally, let f : Rs ×. . .×Rs → R be a function, and let {x(1) , . . . , x(M ) ∈ Rs } be a set of vectors
called template vectors, then the grid tensor of f is denoted by A(f ) ∈ RM ⊗...⊗M and defined by
A(f )d1 ,...,dN = f (x(d1 ) , . . . , x(dN ) ) for all d1 , . . . , dN ∈ [M ].
3.2

B OUNDING THE S IZE OF N ETWORKS VIA G RID T ENSORS

We begin with a discussion on how to have a well-defined measure of efficiency. We wish to compare the efficiency of non-overlapping ConvACs to overlapping ConvACs, for a fixed set of M representation functions (see sec. 2 for definitions). While all functions realizable by non-overlapping
ConvACs with shared representation functions lay in the same function subspace (see Cohen et al.
(2016a)), this is not the case for overlapping ConvACs, which can realize additional functions outside the sub-space induced by non-overlapping ConvACs. We cannot therefore compare both architectures directly, and need to compare them through an auxiliary objective. Following the work
of Cohen and Shashua (2016), we instead compare architectures through the concept of grid tensors, and specifically, the grid tensor defined by the output of a ConvAC, i.e. the tensor A(h) for
h(x1 , . . . , xN ). Unlike with the ill-defined nature of directly comparing the functions of realized
by ConvACs, Cohen and Shashua (2016) proved that assuming the fixed representation functions
are linearly independent, then there exists template vectors x(1) , . . . , x(M ) , for which any nonoverlapping ConvAC architecture could represent all possible grid tensors over these templates,
given sufficient number of channels at each layer. More specifically, if Fij = fi (x(j) ), then these
template vector are chosen such that F is non-singular. Thus, once we fix a set of linearly independent representation functions, we can compare different ConvACs, whether overlapping or not,
on the minimal size required for them to induce the same grid tensor, while knowing such a finite
number always exists.
One straightforward direction for separating between the expressive efficiency of two network architectures A and B is by examining the ranks of their respective matricized grid tensors. Specifically,
Let A(h(A) ) and A(h(B) ) denote the grid tensors of A and B, respectively, and let (P, Q) be a partition of [N ], then we wish to find an upper-bound on the rank of JA(h(A) )KP,Q
 as a function of its
size on one hand, while showing on the other hand that rank JA(h(B) )KP,Q can be significantly
greater. One benefit of studying efficiency through a matrix rank is that not only we attain separation bounds for exact realization, but also immediately gain access to approximation bounds by
examining the singular values of the matricized grid tensors. This brings us to the following lemma,
which connects upper-bounds that were previously found for non-overlapping ConvACs (Cohen and
Shashua, 2017), with the grid tensors induced by them (see app. C.1 for proof):
Lemma 1. Let hy (x1 , . . . , xN ) be a score function of a non-overlapping ConvAC with a fixed set of
M linearly independent and continuous representation functions, and L GC layers. Let (P, Q) be
a partition dividing the spatial dimensions of the output of the representation layer into two equal
parts, either along the horizontal or vertical axis, referred to as the “left-right” and “top-bottom”
partitions, respectively. Then, for any template vectors such that F is non-singular and for any
choice of the parameters of the network, it holds that rank (JA(hy )KP,Q ) ≤ D(L−1) .
Lemma 1 essentially means that it is sufficient to show that overlapping ConvACs can attain
ranks super-polynomial in their size to prove they are exponentially efficient with respect to nonoverlapping ConvACs. In the next section we analyze how the overlapping degree is related to the
rank, and under what cases it leads to an exponentially large rank.

4

T HE E XPRESSIVE E FFICIENCY OF OVERLAPPING A RCHITECTURES

In this section we analyze the expressive efficiency of overlapping architectures. We begin by defining our measures of the overlapping degree that will used in our claims, followed by presenting our
main results in sec. 4.2. For the sake of brevity, an additional set of results, in light of the recent
work by Cohen and Shashua (2017) on “Pooling Geometry”, is deferred to app. B.
5

Published as a conference paper at ICLR 2018

4.1

T HE OVERLAPPING D EGREE OF A N ETWORK

To analyze the efficiency of overlapping archiInput Layer
tectures, we will first formulate more rigorously
the measurement of the overlapping degree of
Total
a given architecture. As mentioned in sec. 1,
Layer L-1
Stride
we do so by defining the concepts of the total receptive field and total stride of a given
(l)
(l)
Layer L
layer l ∈ [L], denoted by TR and TS , reTotal
spectively. Both measurements could simply be Receptive
Field
thought of as projecting the accumulated local
receptive fields (or strides) to the the first layer,
as illustrated in fig. 3, which represent a type of Figure 3: Illustrating the total receptive field and
global statistics of the architecture. However, total stride attributes for the L’th layer, which
note that proposition 1 entails that a given ar- could be seen as the projected receptive field and
chitecture could have a smaller effective total stride with respect to the input layer. Together,
receptive field, for some settings of its parame- they capture the overlapping degree of a network.
ters. This leads us to define the α-minimal total
receptive field, for any α ∈ R+ , as the smallest effective total receptive field still larger than α,
(l,α)
which we denote by TR . The exact definitions of the above concepts are formulated as follows:
(Q
l
(i)
l≥1
(l)
(l)
(1)
(l)
i=1 S
TS ≡ TS (S , . . . , S ) ≡
(1)
1
l=0

Xl−1 
(l)
(l)
(l−1)
(k−1)
TR ≡ TR (R(1) , S (1) , . . . , R(l) , S (l) ) ≡ R(l) · TS
+
R(k) − S (k) · TS
(2)
(l,α)
TR

≡

(l,α)
TR (R(1) , S (1) , . . . , R(l) , S (l) )

(l−1)

where we omitted the arguments of TS

≡

argmin

k=1
(l)
TR (t1 , S (1) , . . . , tl , S (l) )

(3)

∀i∈[l],S (i) ≤ti ≤R(i)
(l)
TR (t1 ,S (1) ,...,tl ,S (l) )>α
(k−1)

and TS

for the sake of visual compactness.

Notice that for non-overlapping networks the total receptive field always equals the total stride, and
that only at the end of the network, after the spatial dimension collapses to 1×1, does the the total
receptive field grow to encompass the entire size of the representation layer. For overlapping networks this is not the case, and the total receptive field could grow much faster. Intuitively, this means
that values in regions of the input layer that are far apart would be combined by non-overlapping
networks only near the last layers of such networks, and thus non-overlapping networks are effectively shallow in comparison to overlapping networks. Base on this intuition, in the next section we
analyze networks with respect to the point at which their total receptive field is large enough.
4.2

M AIN R ESULTS

With all the preliminaries in place, we are ready to present our main result:
Theorem 1. Assume a ConvAC with a fixed representation layer having M output channels and both
width and height equal to H, followed by L GC layers, where the l’th layer has a local receptive
field R(l) , a stride S (l) , and D(l) output channels. Let K ∈ [L] be a layer with a total receptive
(K)
(K)
(K)
field TR ≡ TR (R(1) , S (1) , . . . , R(K) , S (K) ), such that TR > H2 . Then, for any choice of
parameters, except a null set (with respect to the Lebesgue measure), and for any template vectors
such that F is non-singular, the following equality holds:
rank (JA(hy )KP,Q ) ≥ D


&
H


 H−T (K,b /2c)

R

+1·
T

where (P, Q) is either the “left-right”
D ≡ min{M, D(K) , 12 min1≤l≤K D(l) }.

(K)
S

or

the

'
H
(K)
T
S

“top-bottom”

(4)
partitions

and

Proof sketch. Because the entries of the matricized grid tensors are polynomials in the parameters,
then according to a lemma by Sharir et al. (2016), if there is a single example that attains the above
6

Published as a conference paper at ICLR 2018

input
H

representa+on

>

H
2

Arbitrary Layers

Conv

Conv

stride
1x1
>

H

Conv

H
2

M

Output

M

Figure 4: A network architectures beginning with large local receptive fields greater than N/2 and at
least M output channels. According to theorem 1, for almost all choice of parameters we obtain a
function that cannot be approximated by a non-overlapping architecture, if the number of channels
H2
in its next to last layer is less than M 2 .
lower-bound on the rank, then it occurs almost everywhere with respect to the Lebesgue measure on
the Euclidean space of the parameters.
Given the last remark, the central part of our proof is simply the construction of such an example.
First we find a set of parameters for the simpler case where the first GC layer is greater than a
quarter of the input, satisfying the conditions of the theorem. The motivation behind the specific
construction is the pairing of indices from each side of the partition, such that they are both in the
same local receptive field, and designing the filters such that the output of each local application of
them defines a mostly diagonal matrix of rank D, with respect to these two indices. The rest of the
parameters are chosen such that the output of the entire network results in a product of the entries
of these matrices. Under matricization, this results in a matrix who is equivalent2 to a Kronecker
product of mostly diagonal matrices. Thus, the matricization rank is equal to the product of the
ranks of these matrices, which results in the exponential form of eq. 4. Finally, we extend the above
example to the general case, by realizing the operation of the first layer of the above example through
multiple layers with small local receptive fields. See app. C.1 for the definitions and lemmas we rely
on, and see app. C.3 for a complete proof.
Combined with Lemma 1, it results in the following corollary:
Corollary 1. Under the same setting as theorem 1, and for all choices of parameters of an overlapping ConvAC, except a negligible set, any non-overlapping ConvAC that realizes (or approximates)
the same grid tensor must be of size at least:

D


&
H


 H−T (K,b /2c)

R

+1·
T

(K)
S

'
H
(K)
T
S

.

While the complexity of the generic lower-bound above might seem incomprehensible at first, its
generality gives us the tools to analyze practically any kind of feed-forward architecture. As an
example, we can analyze the lower bound for the well known GoogLeNet architecture (Szegedy
et al., 2015), for which the lower bound equals 3298 , making it clear that using a non-overlapping
architecture for this case is infeasible. Next, we will focus on specific cases for which we can derive
more intelligible lower bounds.
According to theorem 1, the lower bound depends on the first layer for which its total receptive field
is greater than a quarter of the input. As mentioned in the previous section, for non-overlapping
networks this only happens after the spatial dimension collapses to 1×1, which entails that both
the total receptive field and total stride would be equal to the width H of the representation layer,
and substituting this values in eq. 4 results simply in D – trivially meaning that to realize one nonoverlapping network by another non-overlapping network, the next to last layer must have at least
half the channels of the target network.
On the other extreme, we can examine the case where the first GC layer has a local receptive field R
greater than a quarter of its input, i.e. R > H/2. Since the layers following the first GC layer do not
affect the lower bound in this case, it applies to any arbitrary sequence of layers as illustrated in fig. 4.
For simplicity we will also assume that the stride S is less than H/2, and that H2 is evenly divided
2

Two matrices are equivalent if one could be converted to the other by elementary row or column operations.

7

Published as a conference paper at ICLR 2018

input

representa.on

Block 0

BxB Conv

Block L-1

2x2 Conv

BxB Conv

R: BxB
S: 1x1

H

2x2 Conv

output

R: 2x2
S: 2x2

D(1)

M

H

D(1)

D(L-1)

D(L-1)

Figure 5: The common network architecture of alternating B×B “conv” and 2×2 “pooling” layers.
If B ≤ H/5+1 and D(l) ≥ 2M for all 1 ≤ l < L, then the lower bound of theorem 1 for this
(2B−1)2
4

network results in M

by S. In this case the
H2
2S

.

H
2 -minimal

receptive field equals to

H
2

+ 1, and thus the lower bound results

in D . Consider the case of D = M and S = 1, then a non-overlapping architecture that satisfies
this lower bound is of the order of magnitude at which it could already represent any possible grid
tensor. This demonstrate our point from the introduction, that through a a polynomial change in the
architecture, i.e. increasing the receptive field, we get an exponential increase in expressivity.
Though the last example already demonstrates that a polynomially sized overlapping architecture
could lead to an exponential separation, in practice, employing such large convolutions is very resource intensive. The common best practice is to use multiple small local receptive fields of size
B × B, where the typical values are B = 3 or B = 5, separated by a 2 × 2 “pooling” layers,
i.e. layers with both stride and local receptive field equal to 2 × 2. For simplicity, we assume that
H = 2L for some L ∈ N. See fig. 5 for an illustration of such a network. Analyzing the above
network with theorem 1 results in the following proposition:
Proposition 2. Consider a network comprising a sequence of GC blocks, each block begins with a
layer whose local receptive field is B×B and its stride 1×1, followed by a layer with local receptive
field 2×2 and stride 2×2, where the output channels of all layers are at least 2M , and the spatial
dimension of the representation layer is H×H for H=2L . Then, the lower bound describe by eq. 4
for the above network is greater than or equal to:
τ (B, H) ≡ M

(2B−1)2
2

whose limits are limB→∞ τ (B, H) = M
ing B ≤

H
5

+ 1, then τ (B, H) ≥ M

·(1+ 2B−2
H )

H2
2

(2B−1)2
4

−2

=M

H2
2

−2

H−1
·(1+ 2B−1
)

and limH→∞ τ (B, H) = M

,

(2B−1)2
2

. Finally, assum-

.

Proof sketch. We first find a closed-form expression for the total receptive field and stride of each
of the B×B layers in the given network. We then show that for layers whose total receptive field
H
H
is greater than H
2 , its α-minimal total receptive field, for α= 2 , is equal to 2 +1. We then use the
above to find the first layer who satisfies the conditions of theorem 1, and then use our closed-forms
expressions to simplify the general lower bound for this case. See app. C.4 for a complete proof.

In particular, for the typical values of M = 64, B = 5, and H ≥ 20, the lower bound is at
least 6420 , which demonstrates that even having a small amount of overlapping already leads to an
exponential separation from the non-overlapping case. When B grows in size, this bound approaches
the earlier result we have shown for large local receptive fields encompassing more than a quarter
of the image. When H grows in size, the lower bound is dominated strictly by the local receptive
fields. Also notice that based on proposition 2, we could also derive a respective lower bound
for a network following VGG style architecture (Simonyan and Zisserman, 2014), where instead
of a single convolutional layer before every “pooling” layer, we have K layers, each with a local
receptive field of C × C. Under this case, it is trivial to show that the bound from proposition 2
holds for B = K · (C − 1) + 1, and under the typical values of C = 3 and K = 2 it once again
results in a lower bound of at least 6420 .
8

100.00
93.33
86.67
80.00
73.33
66.67
60.00
53.33
46.67
40.00

B=1
B=2
B=3
B=4
B=5
16

32

64

128

256

Number of Channels

512

1024

32

64

128

256

Number of Channels

512

1024

100.00
93.33
86.67
80.00
73.33
B=1
66.67
B=2
60.00
B=3
53.33
B=4
46.67
B=5
40.00
1.0e+03 4.1e+03 1.6e+04 6.6e+04 2.6e+05 1.0e+06 4.2e+06 1.7e+07
100.00
93.33
86.67
80.00
73.33
B=1
66.67
B=2
60.00
B=3
53.33
B=4
46.67
B=5
40.00
1.0e+03 4.1e+03 1.6e+04 6.6e+04 2.6e+05 1.0e+06 4.2e+06 1.7e+07 6.7e+07

2048

B=1
B=2
B=3
B=4
B=5
16

Train Accuracy (%)

100.00
93.33
86.67
80.00
73.33
66.67
60.00
53.33
46.67
40.00

Train Accuracy (%)

Train Accuracy (%)

Train Accuracy (%)

Published as a conference paper at ICLR 2018

Number of Parameters

2048

Number of Parameters

Figure 6: Training accuracies of standard ConvNets on CIFAR-10 with data augmentations, where
the results of spatial augmentations presented at the top row, and color augmentations at the bottom
row. Each network follows the architecture of proposition 2, with with receptive field B and using
the same number of channels across all layers, as specified by the horizontal axis of left plot. We
plot the same results with respect to the total number of parameters in the right plot.

5

E XPERIMENTS

In this section we show that the theoretical results of sec. 4.2 indeed hold in practice. In other
words, there exists tasks that require the highly expressive power of overlapping architectures, on
which non-overlapping architectures would have to grow by an exponential factor to achieve the
same level of performance. We demonstrate this phenomenon on standard ConvNets with ReLU
activations that follow the same architecture that was outlined in proposition 2, while varying the
number of channels and the size of the receptive field of the B×B “conv” layers. The only change
we made, was to replace the 2×2-“pooling” layers of the convolutional type, with the standard 2×2max-pooling layers, and using the same number of channels across all layers. This was done for the
purpose of having all the learned parameters located only at the (possibly) overlapping layers. More
specifically, the network has 5 blocks, each starting with a B×B convolution with C channels,
stride 1×1, and ReLU activation, and then followed by 2×2 max-pooling layer. After the fifth
“conv-pool”, there is a final dense layer with 10 outputs and softmax activations.
We train each of these networks for classification over the CIFAR-10 dataset, with two types of
data augmentation schemes: (i) spatial augmentations, i.e. randomly translating (up to 3 pixels in
each direction) and horizontally flipping each image, and (ii) color augmentations following Dosovitskiy et al. (2014), i.e. randomly adding a constant shift (at most ±0.3) to the hue, saturation,
and luminance, for each attribute separately, and in addition randomly sampling a multiplier (in
the range [0.5, 1.5]) just to the saturation and luminance. Though typically data augmentation is
only used for the purpose of regularization, we employ it for the sole purpose of raising the hardness of the regular CIFAR-10 dataset, as even small networks can already overfit and effectively
memorize its small dataset. We separately test both the spatial and color augmentation schemes
to emphasize that our empirical results cannot be explained simply by spatial-invariance type arguments. Finally, the training itself is carried out for 300 epochs with ADAM (Kingma and Ba,
2015) using its standard hyper-parameters, at which point the loss of the considered networks have
stopped decreasing. We report the training accuracy over the augmented dataset in fig. 6, where for
each value of the receptive field B, we plot its respective training accuracies for variable number
of channels C. The source code for reproducing the above experiments and plots can be found at
https://github.com/HUJI-Deep/OverlapsAndExpressiveness.
It is quite apparent that the greater B is chosen, the less channels are required to achieve the same
accuracy. Moreover, for the non-overlapping case of B=1, more than 2048 channels are required
to reach the same performance of networks with B>2 and just 64 channels under the spatial aug9

Published as a conference paper at ICLR 2018

mentations – which means effectively exponentially more channels were required. Even more so,
under the color augmentations, we were not able to train non-overlapping networks to reach even the
smallest overlapping network (B = 2 and C = 16). In terms of total number of parameters, there
is a clear separation between the overlapping and the non-overlapping types, and we once again
see more than an order of magnitude increase in the number of parameters between an overlapping
and non-overlapping architectures that achieve similar training accuracy. As a somewhat surprising
result, though based only on our limited experiments, it appears that for the same number of parameters, all overlapping networks attain about the same training accuracy, suggesting perhaps that
having the smallest amount of overlapping already attain all the benefits overlapping provides, and
that increasing it further does not affect the performance in terms of expressivity.
As final remark, we also wish to acknowledge the limitations of drawing conclusions strictly from
empirical experiments, as there could be alternative explanations to these observations, e.g. the
effects overlapping has on the optimization process. Nevertheless, our theoretical results suggests
this is less likely the case.

6

D ISCUSSION

The common belief amongst deep learning researchers has been that depth is one of the key factors in the success of deep networks – a belief formalized through the depth efficiency conjecture.
Nevertheless, depth is one of many attributes specifying the architecture of deep networks, and each
could potentially be just as important. In this paper, we studied the effect overlapping receptive
fields have on the expressivity of the network, and found that having them, and more broadly denser
connectivity, results in an exponential gain in the expressivity that is orthogonal to the depth.
Our analysis sheds light on many trends and practices in contemporary design of neural networks.
Previous studies have shown that non-overlapping architectures are already universal (Cohen et al.,
2016a), and even have certain advantages in terms of optimization (Brutzkus and Globerson, 2017),
and yet, real-world usage of non-overlapping networks is scarce. Though there could be multiple
factors involved, our results clearly suggest that the main culprit is that non-overlapping networks
are significantly handicapped in terms of expressivity compared to overlapping ones, explaining why
the former are so rarely used. Additionally, when examining the networks that are commonly used
in practice, where the majority of the layers are of the convolutional type with very small receptive
field, and only few if any fully-connected layers (Simonyan and Zisserman, 2014; Springenberg
et al., 2015; He et al., 2016), we find that though they are obviously overlapping, their overlapping
degree is rather low. We showed that while denser connectivity can increase the expressive capacity, even in the most common types of modern architectures already exhibit exponential increase in
expressivity, without relying on fully-connected layers. This could partly explain that somewhat surprising observation, as it is probable that such networks are sufficiently expressive for most practical
needs simply because they are already in the exponential regime of expressivity. Indeed, our experiments seems to suggests the same, in which we saw that further increases in the overlapping degree
beyond the most limited overlapping case seems to have insignificant effects on performance – a
conjecture not quite proven by our current work, but one we wish to investigate in the future.
There are relatively few other works which have studied the role of receptive fields in neural networks. Several empirical works (Li and Perona, 2005; Coates et al., 2011; Krizhevsky et al., 2012)
have demonstrated similar behavior, showing that the classification accuracy of networks can sharply
decline as the degree of overlaps is decreased, while also showing that gains from using very large
local receptive fields are insignificant compared to the increase in computational resources. Other
works studying the receptive fields of neural networks have mainly focused on how to learn them
from the data (Coates and Ng, 2011; Jia et al., 2012). While our analysis has no direct implications to those specific works, it does lay the ground work for potentially guiding architecture design,
through quantifying the expressivity of any given architecture. Lastly, Luo et al. (2016) studied
the effective total receptive field of different layers, a property of a similar nature to our total receptive field, where they measure the the degree to which each input pixel is affecting the output
of each activation. They show that under common random initialization of the weights, the effective total receptive field has a gaussian shape and is much smaller than the maximal total receptive
field. They additionally demonstrate that during training the effective total receptive field grows in
size, and suggests that weights should be initialized such that the initial effective receptive field is
10

Published as a conference paper at ICLR 2018

large. Their results strengthen our theory, by showing that trained networks tend to maximize their
effective receptive field, taking full potential of their expressive capacity.
To conclude, we have shown both theoretically and empirically that overlapping architectures have
an expressive advantage compared to non-overlapping ones. Our theoretical analysis is grounded on
the framework of ConvACs, which we extend to overlapping configurations. Though are proofs are
limited to this specific case, previous studies (Cohen and Shashua, 2016) have already shown that
such results could be transferred to standard ConvNets as well, using most of the same mathematical
machinery. While adapting our analysis accordingly is left for future work, our experiments on
standard ConvNets (see sec. 5) already suggest that the core of our results should hold in this case as
well. Finally, an interesting outcome of moving from non-overlapping architectures to overlapping
ones is that the depth of a network is no longer capped at log2 (input size), as has been the case in
the models investigated by Cohen et al. (2016a) – a property we will examine in future works
ACKNOWLEDGMENTS
This work is supported by Intel grant ICRI-CI #9-2012-6133, by ISF Center grant 1790/12 and by
the European Research Council (TheoryDL project).

R EFERENCES
Alon Brutzkus and Amir Globerson. Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs.
In International Conference on Machine Learning ICML, February 2017.
Adam Coates and Andrew Y Ng. Selecting Receptive Fields in Deep Networks. Advances in Neural Information Processing Systems, 2011.
Adam Coates, Andrew Y Ng, and Honglak Lee. An Analysis of Single-Layer Networks in Unsupervised
Feature Learning. International Conference on Artificial Intelligence and Statistics, pages 215–223, 2011.
Nadav Cohen and Amnon Shashua. Convolutional Rectifier Networks as Generalized Tensor Decompositions.
In International Conference on Machine Learning, May 2016.
Nadav Cohen and Amnon Shashua. Inductive Bias of Deep Convolutional Networks through Pooling Geometry. In International Conference on Learning Representations ICLR, April 2017.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the Expressive Power of Deep Learning: A Tensor Analysis.
In Conference on Learning Theory COLT, May 2016a.
Nadav Cohen, Or Sharir, and Amnon Shashua. Deep SimNets. In Computer Vision and Pattern Recognition
CVPR, May 2016b.
Alexey Dosovitskiy, Jost Tobias Springenberg, Martin A Riedmiller, and Thomas Brox. Discriminative Unsupervised Feature Learning with Convolutional Neural Networks. In Advances in Neural Information Processing Systems NIPS, Deep Learning Workshop, 2014.
Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In Conference on
Learning Theory COLT, May 2016.
Wolfgang Hackbusch. Tensor Spaces and Numerical Tensor Calculus, volume 42 of Springer Series in Computational Mathematics. Springer Science & Business Media, Berlin, Heidelberg, February 2012.
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold Circuits of
Bounded Depth. J. Comput. Syst. Sci. (), 46(2):129–154, 1993.
Johan Håstad and Mikael Goldmann. On the Power of Small-Depth Threshold Circuits. Computational Complexity (), 1(2):113–129, 1991.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition.
Computer Vision and Pattern Recognition, pages 770–778, 2016.
Yangqing Jia, Chang Huang, and Trevor Darrell. Beyond spatial pyramids - Receptive field learning for pooled
image features. Computer Vision and Pattern Recognition, 2012.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference
on Learning Representations, 2015.

11

Published as a conference paper at ICLR 2018

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet Classification with Deep Convolutional
Neural Networks. Advances in Neural Information Processing Systems, pages 1106–1114, 2012.
Fei-Fei Li and Pietro Perona. A Bayesian Hierarchical Model for Learning Natural Scene Categories. Computer
Vision and Pattern Recognition, 2:524–531, 2005.
Min Lin, Qiang Chen, and Shuicheng Yan. Network In Network. In International Conference on Learning
Representations ICLR, 2014.
Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard S Zemel. Understanding the Effective Receptive Field in
Deep Convolutional Neural Networks. Advances in Neural Information Processing Systems, pages 4898–
4906, 2016.
Guido F Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the Number of Linear Regions
of Deep Neural Networks. CoRR abs/1202.2745, stat.ML:2924–2932, 2014.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward
networks with piece-wise linear activations. arXiv.org, December 2013.
Ben Poole, Subhaneil Lahiri, Maithreyi Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing
Systems NIPS, Deep Learning Workshop, 2016.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power
of deep neural networks. arXiv.org, June 2016.
Itay Safran and Ohad Shamir. Depth Separation in ReLU Networks for Approximating Smooth Non-Linear
Functions. CoRR abs/1202.2745, cs.LG, 2016.
Or Sharir, Ronen Tamari, Nadav Cohen, and Amnon Shashua. Tensorial Mixture Models. arXiv.org, October
2016.
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. CoRR abs/1202.2745, , 2014.
Michael Sipser. Borel sets and circuit complexity. ACM, New York, New York, USA, December 1983.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for Simplicity:
The All Convolutional Net. In Workshop track of International Conference on Learning Representations,
2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan,
Vincent Vanhoucke, and Andrew Rabinovich. Going Deeper with Convolutions. In Computer Vision and
Pattern Recognition CVPR, 2015.
Yaniv Taigman, Ming Yang, Marc’Aurelio Ranzato, and Lior Wolf. DeepFace: Closing the Gap to HumanLevel Performance in Face Verification. In Computer Vision and Pattern Recognition CVPR. IEEE Computer Society, June 2014.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory COLT, May 2016.
Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. CoRR
abs/1609.03499, 2016.
Andrew Chi-Chih Yao. Circuits and Local Computation. STOC, pages 186–196, 1989.

12

Published as a conference paper at ICLR 2018

input X

hidden layer 0
representa.on

1x1 conv

hidden layer L-1

pooling

1x1 conv

pooling

dense
(output)

rL-1

Y

xi

r0

M
rep(i, d) = f✓d (xi )

pool0 (j, ) =

⌦
↵
conv(j, ) = a0,j, , rep(j, :)

Y

rL-1

r0
conv0 (j 0 , )

poolL

1 ( )=

Y

convL

0
1 (j , )

j 0 covers space

j 0 2window

⌦
out(y) = aL,y , poolL

1 (:)

↵

Figure 7: The original Convolutional Arithmetic Circuits as presented by Cohen et al. (2016a).

A

BACKGROUND ON C ONVOLUTIONAL A RITHMETIC C IRCUITS

We base our analysis on the convolutional arithmetic circuit (ConvAC) architecture introduced by Cohen et al.
(2016a), which is illustrated by fig. 7, and can be simply thought of as a regular ConvNet, but with linear activations and product pooling layers, instead of the more common non-linear activations (e.g. ReLU)
and average/max pooling. More specifically, each point in the input space of the network, denoted by
X = (x1 , . . . , xN ), is represented as an N -length sequence of s-dimensional vectors x1 , . . . , xN ∈ Rs .
X is typically thought of as an image, where each xi corresponds to a local patches from that image. The first
layer of the network is referred to as the representation layer, consisting of applying M representation functions
fθ1 , . . . , fθM : Rs → R on each local patch xi , giving rise to M feature maps. Under the common setting,
where the representation functions are selected to be fθd (x) = σ(wdT x + bd ) for some point-wise activation
σ(·) and parameterized by θd = (wd , bd ) ∈ Rs × R, the representation layer reduces to the standard convolutional layer. Other possibilities, e.g. gaussian functions with diagonal covariances, have also been considered
in Cohen et al. (2016a). Following the representation layer, are hidden layers indexed by l = 0, . . . , L − 1,
each begins with a 1 × 1 conv operator, which is just an rl−1 × 1 × 1 convolutional layer with rl−1 input channels and rl output channels, with the sole exception that parameters of each kernel could be spatially unshared
(known as locally-connected layer (Taigman et al., 2014)). Following each conv layer is a spatial pooling, that
takes products of non-overlapping two-dimensional windows covering the output of the previous layer, where
for l = L − 1 the pooling window is the size of the entire spatial dimension (i.e. global pooling), reducing
its output’s shape to a rL−1 × 1 × 1, i.e. an rL−1 -dimensional vector. The final L layer maps this vector
with a dense linear layer into the Y network outputs, denoted by hy (x1 , . . . , xN ), representing score functions
classifying each X to one of the classes through: y ∗ = argmaxy hy (x1 , . . . , xN ). As shown in Cohen et al.
(2016a), these functions have the following form:
hy (x1 , . . . , xN ) =

M
X

Ayd1 ,...,dN

d1 ,...,dN =1

N
Y

fθdi (xi )

(5)

i=1

where Ay , called the coefficients tensor, is a tensor of order N and dimension M in each mode, which for the
sake of discussion can simply be seen as a multi-dimensional array, specified by N indices d1 , . . . , dN each
ranging in {1, . . . , M }, with entries given by polynomials in the network’s conv weights. A byproduct of eq. 5
is that for a fixed set of M representation functions, all functions represented by ConvACs lay in the same
subspace of functions.

B

C OMPARISON TO P OOLING G EOMETRY

From theorem 1 we learn that overlaps give rise to networks which almost always cannot be efficiently implemented by non-overlapping ConvAC with standard pooling geometry. However, as proven by Cohen and
Shashua (2017), a ConvAC that uses a different pooling geometry – i.e. the input to the pooling layers are not
strictly contiguous windows from the previous layer – also cannot be efficiently implemented by the standard
ConvAC with standard pooling geometry. This raises the question of whether overlapping operations are simply equivalent to a ConvAC with a different pooling geometry and nothing more. We answer this question in
two parts. First, a ConvAC with a different pooling geometry might be able to implement some function more
efficiently than ConvAC with standard pooling geometry, however, the reverse is also true, that a ConvAC with
standard pooling can implement some functions more efficiently than ConvAC with alternative pooling. In contrast, a ConvAC that uses overlaps is still capable to implement efficiently any function that a non-overlapping
ConvAC with standard pooling can. Second, we can also show that some overlapping architectures are exponentially efficient than any non-overlapping ConvAC regardless of its pooling geometry. This is accomplished
by first extending lemma 1 to this case:

13

Published as a conference paper at ICLR 2018

Lemma 2. Under the same conditions as lemma 1, if for all partitions P ∪· Q such that |P | = |Q| = N/2
it holds that rank (JA(hy )KP,Q ) ≥ T , then any non-overlapping ConvAC regardless of its pooling geometry
must have at least T channels in its next to last layer to induce the same grid tensor.
Next, in theorem 2 below show that some overlapping architectures can induce grid tensors whose matricized
rank is exponential for any equal partition of its indices, proving they are indeed exponentially more efficient:
Theorem 2. Under the same settings as theorem 1, consider a GC network whose representation layer is
followed by a GC layer with local receptive field H × H, stride 1 × 1, and D ≥ M output channels, whose
parameters are “unshared”, i.e. unique to each spatial location in the output of the layer as opposed to shared
across them, followed by (L − 1) arbitrary GC layers, whose final output is a scalar. For any choice of the
parameters, except a null set (with respect to the Lebesgue measure) and for any template vectors such that F
H2

is non-singular, then the matricized rank of the induced grid tensor is equal to M 2 , for any equal partition of
the indices. The exact same result holds if the parameters of the first GC layers are “shared” and D ≥ M · H 2 .
Proof sketch. We follow the same steps of our proof of theorem 1, however, we do not construct just one
specific overlapping network that attains a rank of D ≥ M · H 2 , for all possible matricizations of the induced
grid tensor. Instead, we construct a separate network for each possible matricization. This proves that with
respect to the Lebesgue measure over the network’s parameters space, separately for each pooling geometry,
the set of parameters for which the lower bound does not hold is of measure zero. Since a finite union of zero
measured sets is also of measure zero, then the lower bound with respect to all possible pooling geometries
holds almost everywhere, which concludes the proof sketch. See app. C.5 for a complete proof.
It is important to note that though the above theorem shows that pooling geometry on its own is less expressive
than overlapping networks with standard pooling, it does not mean that pooling geometry is irrelevant. Specifically, we do not yet know the effect of combining both overlaps and alternative pooling geometries together.
Additionally, many times sufficient expressivity is not the main obstacle for solving a specific task, and the
inductive bias induced by a carefully chosen pooling geometry could help reduce overfitting.

C

D EFERRED P ROOFS

In this section we present our proofs for the theorems and claims stated in the body of the article.

C.1

P RELIMINARIES

In this section we lay out the preliminaries required to understand the proofs in the following sections. We
begin with a limited introduction to tensor analysis, followed by quoting a few relevant known results relating
tensors to ConvACs.
We begin with basic definitions and operations relating to tensors. Let A ∈ RM1 ⊗···⊗MN be a tensor of order
N and dimension Mi in each mode i ∈ [N ] (where [N ] = {1, . . . , N }), i.e. Ad1 ,...,dN ∈ R for all i ∈ [N ]
(2)
(1)
and di ∈ [Mi ]. For tensors A(1) and A(2) of orders N (1) and N (2) , and dimensions Mi1 and Mi2 in each of
(1)
(2)
(1)
(2)
the modes i1 ∈ [N ] and i2 ∈ [N ], respectively, we define their tensor product A ⊗ A as the order
N (1) + N (2) tensor, where


(1)
(2)
A(1) ⊗ A(2)
= Ad1 ,...,d (1) · Ad (1) ,...,d (1) (2)
d1 ,...,d (1)
N
+N (2)

N

N

+1

N

+N

For a set of vectors v(1) ∈ RM1 , . . . , v(N ) ∈ RMN , the N ordered tensor A = v(1) ⊗· · ·⊗v(N ) is called an
elementary tensor, or rank-1 tensor. More generally, any tensor can be represented as a linear combination of
P
(Z,1)
rank-1 tensors, i.e. A = Z
⊗· · ·⊗v(Z,1) , known as rank-1 decomposition, or CP decomposition,
z=1 v
where the minimal Z for which this equality holds is knows as the tensor rank of A. Given a set of matrices
0
0
F (1) ∈RM1 ×M1 , . . . , F (N ) ∈RMN ×MN , we denote by F = (F (1) ⊗· · ·⊗F (N ) ) the linear transformation from
0
0
RM1 ⊗···⊗MN to RM1 ⊗···⊗MN , such that for any elementary tensor A, with notations as above, it holds that:
F(A) = F (1) (v(1) ) ⊗ · · · ⊗ F (N ) (v(N ) )
F(A) is defined for a general tensor A through its rank-1 decomposition comprising elementary tensors and
applying F on each of them, which can be shown to be equivalent to
F(A)k1 ,...,kN =

M1
X
d1 =1

MN

···

X
dN =1

14

Ad1 ,...,dN

N
Y
i=1

(i)

Fki ,di

(6)

Published as a conference paper at ICLR 2018

· = [N ] be a disjoint partition of its
A central concept in tensor analysis is that of tensor matricization. Let P ∪Q
indices, such that P = {p1 , . . . , p|P | } with p1 < . . . < p|P | , and Q = {q1 , . . . , q|Q| } withq1 < . . . <q|Q| .
Q|P |
The matricization of A with respect to the partition P ∪· Q, denoted by JAKP,Q , is the
t=1 Mpt -by
Q
|Q|
matrix holding the entries of A, such that for all i ∈ [N ] and di ∈ [Mi ] the entry Ad1 ,...,dN is
t=1 Mqt
Q|Q|
P|Q|
Q|P |
P |
placed in row index 1 + |P
t=1 (dqt − 1)
t=1 (dpt − 1)
t0 =t+1 Mqt0 .
t0 =t+1 Mpt0 and column index 1 +
Applying the matricization operator J·KP,Q on the tensor product operator results in the Kronecker Product, i.e.
for an N -ordered tensor A, a K-ordered tensor B, and the partition P ∪· Q = [N + K], it holds that
JA ⊗ BKP,Q = JAKP ∩[N ],Q∩[N ]

JBK(P −N )∩[K],(Q−N )∩[K]

where P − N and Q − N are simply the sets obtained by subtracting the number N from every element of P
or Q, respectively. In concrete terms, the Kronecker product for the matrices A ∈ RM1 ×M2 and B ∈ RN1 ×N2
results in the matrix A B ∈ RM1 N1 ×M2 N2 holding Aij Bkl in row index (i − 1)N1 + k and column index
(j − 1)N2 + l. An important property of the Kronecker product is that rank (A B) = rank (A) · rank (B).
Typically, when wish to compute rank (JAKP,Q ), we will first decompose it to a Kronecker product of matrices.
For a linear transform F, as defined above in eq.6, and a partition P ∪· Q, if F (1) , . . . , F (N ) are non-singular
matrices, then F is invertible and the matrix rank of JAKP,Q equals to the matrix rank of JF(A)KP,Q (see proof
in Hackbusch (2012)). Finally, we define the concept of grid tensors: for a function
f : Rs × · · · × Rs → R and a set of template vectors x(1) , . . . , x(M ) ∈ Rs , the N -order grid tensor A(f ) is
defined by (A(f ))d1 ,...,dN = f (x(d1 ) , . . . , x(dN ) ).
In the context of ConvACs, circuits and the functions they can realize are typically examined through the
matricization of the grid tensors they induce. The following is a succinct summary of the relevant known
results used in our proofs – for a more detailed discussion, see previous works (Cohen et al., 2016a; Cohen
and Shashua, 2016; 2017). Using the same notations from eq. 5 describing a general ConvAC, let Ay be
the coefficients tensor of order N and dimension M in each mode, and let fθ1 , . . . , fθM :Rs →R be a set
of M representation functions (see app. A). Under the above definitions, a non-overlapping ConvAC can be
said to decompose the coefficients tensor Ay . Different network architectures correspond to known tensor
decompositions: shallow networks corresponds to rank-1 decompositions, and deep networks corresponds to
Hierarchical Tucker decompositions.
In Cohen and Shashua (2017), it was found that the matrix rank of the matricization of the coefficients tensors
Ay could serve as a bound for the size of networks decomposing Ay . For the conventional non-overlapping
ConvAC and the contiguous “low-high” partition P = {1, . . . , N/2}, Q = {N/2 + 1, . . . , N } of [N ], the rank
of the matricization JAy KP,Q serves as a lower-bound on the number of channels of the next to last layer of
any network which decomposes the coefficients tensor A. In the common case of square inputs, i.e. the input
is of shape H × H and N = H 2 , it is more natural to represent indices by pairs (j, i) denoting the spatial
location of each “patch” x(j,i) , where the first argument denotes the vertical location and the second denotes the
horizontal location. Under such setting the equivalent “low-high” partitions are either the “left-right” partition,
i.e. P = {(j, i)|j ≤ H
}, Q = {(j, i)|j > H
}, or the “top-bottom” partition, i.e. P = {(j, i)|i ≤ H
}, Q =
2
2
2
H
{(j, i)|i > 2 }. More generally, when considering networks using other pooling geometries, i.e. not strictly
contiguous pooling windows, then for each pooling geometry there exists a corresponding partition P ∪· Q such
that rank (JAy KP,Q ) serves as its respective lower-bound.
Though the results in Cohen and Shashua (2017) are strictly based on the matricization rank of the coefficients tensors, they can be transferred to the matricization rank of grid tensors as well. Grid tensors were
first considered for analyzing ConvACs in Cohen and Shashua (2016). For a set of M template vectors
x(1) , . . . , x(M ) ∈ Rs , we define the matrix F ∈ RM ×M by Fij = fθj (x(i) ). With the above notations
in place, we can write the the grid tensor A(hy ) for the function hy (x1 , . . . , xN ) as:
A(hy )k1 ,...,kN = hy (x(k1 ) , . . . , x(kN ) )
=

M
X

Ayd1 ,...,dN

=

fθdi (x(ki ) )

i=1

d1 ,...,dN =1
M
X

N
Y

Ayd1 ,...,dN

d1 ,...,dN =1

N
Y

Fki ,di

i=1

⇒ A(hy ) = (F ⊗ · · · ⊗ F )(Ay )
If the representation functions are linearly independent and continuous, then we can choose the template vectors such that F is non-singular (see Cohen and Shashua (2016)), which according to the previous discussion on tensor matricization, means that for any partition P ∪· Q and any coefficients tensor Ay , it holds that
rank (JAy KP,Q ) = rank (JA(hy )KP,Q ). Thus, any lower bound on the matricization rank of the grid tensor

15

Published as a conference paper at ICLR 2018

translates to a lower bound on the matricization rank of the coefficients tensors, which in turn serves as lower
bound on the size of non-overlapping ConvACs. The above discussion leads to the proof of lemma 1 and
lemma 2 that were previously stated:
Proof of lemma 1 and lemma 2. For the proofs of the base results with respect to the coefficients tensor, see
Cohen and Shashua (2017). To prove it is possible to choose the template vectors such that F is non-singular,
see Cohen and Shashua (2016). To prove that if F is non-singular, then the grid tensor and the coefficients
tensor have the same matricization rank, see lemma 5.6 in Hackbusch (2012).
We additionally quote the following lemma regarding the prevalence of the maximal matrix rank for matrices
whose entries are polynomial functions:
Lemma 3. Let M, N, K ∈ N, 1 ≤ r ≤ min{M, N } and a polynomial mapping A : RK → RM ×N , i.e.
for every i ∈ [M ] and j ∈ [N ] it holds that Aij : Rk → R is a polynomial function. If there exists a point
x ∈ RK such that rank (A(x)) ≥ r, then the set {x ∈ RK |rankA(x) < r} has zero measure (with respect to
the Lebesgue measure over RK ).
Proof. See Sharir et al. (2016).
Finally, we simplify the notations of the GC layer with product pooling function for the benefit of following our
(l−1)
×R(l) ×R(l)
proofs below. We will represent the parameters of the l’th GC layer by {(w(l,c) ∈ RD
, b(l,c) ∈
(l)
(l)
(in)
(in)
(in)
RR ×R )}c∈[D(l) ] , where w(l,c) represents the weights and b(l,c) the biases. Let X ∈ RH ×H ×D
be the input to the layer and Y ∈ RD
Yc,u,v

(out)

×H (out) ×H (out)

be the output, then the following equality holds:


(in)
(l)
(l)
D
R
X (l,c)
YR
Y
(l,c)
bji +
wdji Xd,uS (l) +j,vS (l) +i 
(7)
=
j=1 i=1

d=1

The above treats the common case where the parameters are shared across all spatial locations,
but sometimes we wish to consider the “unshared” case, in which there is are different weights
(l−1)
×R(l) ×R(l)
and biases for each location, which we denote by {(w(l,c,u,v) ∈ RD
, b(l,c,u,v) ∈
R(l) ×R(l)
R
)}c∈[D(l) ],u∈[H (out) ],v∈[H (out) ] .
With the above definitions and lemmas in place, we are ready to prove the propositions and theorems from the
body of the article.

C.2

P ROOF OF P ROPOSITION 1

Proposition 1 is a direct corollary of the following two claims:
(in)

(in)

(in)

(out)

(out)

(out)

×H
×H
be a function realized by a single GC
→ RD
Claim 1. Let f :RD ×H ×H
layer with R × R local receptive field, S × S stride, and D(out) output channels, that is parameterized by
(out)
{(w(c) , b(c) )}D
. For all R̃ ≥ R, a GC layer with R̃×R̃ local receptive field, S×S stride, and C output
c=1
(out)
channels, parameterized by {(w̃(c) , b̃(c) )}D
, could also realize f . The same is true for the unshared case
c=1
of both layers.

Proof. The claim is trivially satisfied by setting w̃(c) such that it is equal to w(c) in all matching coordinates,
while using zeros for all other coordinates. Similarly, we set b̃(c) to be equal to b(c) in all matching coordinates,
while using ones for all other coordinates.
(in)

(in)

(in)

(out)

(out)

(out)

×H
×H
Claim 2. Let f :RD ×H ×H
→ RD
be a function realized by a GC layer with
(out)
R×R local receptive field and 1×1 stride, parameterized by {(w(c) , b(c) )}D
. Then there exists an asc=1
signment to (w, b) such that f is the identity function f (X) = X. The same is true for the unshared case of
both layers.

Proof. From claim 1 it is sufficient to show the above holds for R = 1. Indeed, setting
(
1 d=c
(c)
wd =1[d=c] =
0 d 6= c
and b(c) ≡ 0 satisfies the claim.

16

Published as a conference paper at ICLR 2018

C.3

P ROOF OF T HEOREM 1

We wish to show that for all choices of parameters, except a null set (with respect to Lebesgue measure) the
grid tensor induced by the given GC network has rank satisfying eq. 4. Since the entries of the matricized grid
tensor are polynomial function of its parameters, then according to lemma 3, it is sufficient to find a single
example that achieves this bound. Hence, our proof is simply the construction of such an example.
Recall that the template vectors must hold that for the matrix F , defined by Fij = fj (x(i) ), where {fj }M
j=1
are the representation matrices, is a non-singular matrix. We additionally assume in the following claims that
the output of the representation layer is of width and height equal to H ∈ N, where H is an even number – the
claims and proofs can however be easily adapted to the more general case.
Assume a ConvAC as described in the theorem, with representation layer defined according to above, followed
by L GC layers, where the l’th layer has a local receptive field of R(l) , a stride of S (l) , and D(l) output channels.
We first construct our example, that achieves the desired matricization rank, for the simpler case where the first
layer following the representation layer has a local receptive field large enough, i.e. when it is larger than
H
. Recall that for the first layer the total receptive field is equal to its local receptive field. In the context of
2
theorem 1, this first layer satisfies the conditions necessary to produce the lower bound given in the theorem.
The specific construction is presented in the following claim, which relies on utilizing the large local receptive
field to match each spatial location in the left side of the input with one from the right side, such that for each
such pair, the respective output of the first layer will represent a mostly diagonal matrix. We then set the rest
of the parameters such that the output of the entire network is defined by a tensor product of mostly diagonal
matrices. Since the matricization rank of the tensor product of matrices is equal to the product of the individual
ranks, it results in an exponential form of the rank as is given in the theorem.
Claim 3. Assume a ConvAC as defined above, ending with a single scalar output. For all l ∈ [L], the param(l−1)
(l)
(l)
×R(l) ×R(l)
eters of the l-th GC layer are denoted by {(w(l,c) ∈ RD
, b(l,c) ∈ RR ×R )}c∈[D(l) ] . Let
h(x1 , . . . , xN ) be the function realized the output of network. Additionally define R ≡ R(1) , S ≡ S (1) and
D ≡ min{D(1) , M }. If R > H
, and the weights w(1,c) and biases b(1,c) of the first GC layer layer are set
2
to:
(

−α F −1 m,c c ≤ D and (j, i) ∈ {(1, 1), (ρ, τ )}
(1,c)
wmji =
0
Otherwise


β c ≤ D and (j, i) ∈ {(1, 1), (ρ, τ )}
(1,c)
bji = 1 c ≤ D and (j, i) 6∈ {(1, 1), (ρ, τ )}

0 Otherwise
where β =

2α
,
D

then there exists an assignment to α and the parameters of the other GC layers such that
H−R
H
rank (JA(h)KP,Q ) = Db S +1c·d S e , where P ∪· Q is either the “left-right” or “top-bottom” partition, and
(ρ, τ ) equals to (1, R) or (R, 1), respectively.
Proof. The proof for either the “left-right” or “top-bottom” partition is completely symmetric, thus it is
enough to prove the claim for the “left-right” case, where (ρ, τ ) = (1, R). We wish to compute the entry
A(h)d(1,1) ,...,d(H,H) of the induced grid tensor for arbitrary indices d(1,1) , . . . , d(H,H) . Let O ∈ RM ×H×H be
the 3-order tensor output of the representation layer, where Om,j,i = Fd(j,i) ,m for the aforementioned indices
and for all 1 ≤ i, j ≤ H and m ∈ [M ].
We begin by setting the parameters of all layers following the first GC layer, such that they are equal to computing the sum along the channels axis of the output of the first GC layer, followed by a global product of all of
the resulting sums. To achieve this, we can first assume w.l.o.g. that these layers are non-overlapping through
proposition 1. We then set the parameters of the second GC layer to w(2,c) = 1 and b(2,c) ≡ 0, i.e. all
ones and all zeros, respectively, which is equivalent to taking the sum along the channels axis for each spatial
location, followed by taking the products over non-overlapping local receptive fields of size R(2) . For the other
layers, we simply set them as to take just the output of(the first channel of the output of the preceding layer,
1 d=1
(l,c)
which is equal to setting their parameters to wdji =
and b(l,c) ≡ 0. Setting the parameters as
0 d 6= 1
described above results in:
!
(1)
R
M
Y D
X Y
X
(1,c)
(1,c)
(A(h))d(1,1) ,...,d(H,H) =
(8)
bji +
wmji Om,uS+j,vS+i
0≤uS<H c=1 j,i=1
|
0≤vS<H

17

m=1

{z

g(u,v,c,j,i)

}

Published as a conference paper at ICLR 2018

where we extended O with zero-padding for the cases where uS + j > H or vS + i > H, as mentioned in
sec. 2. Next, we go through the technical process of reducing eq. 8 to a product of matrices.
(1,c)

(1,c)

Substituting the values of wdji and bji with those defined in the claim, and computing the value of
g(u, v, c, j, i) results in:


P
−1
β−α M
F
c ≤ D and vS + R ≤ H and (j, i) ∈ {(1, 1), (1, R)}

m=1 F
m,c d(uS+j,vS+i) ,m


PM


−1

β
−
α
F
F
c
≤ D and vS + R > H and (j, i) = (1, 1)

m=1
m,c d(uS+j,vS+i) ,m
g(u, v, c, j, i) = β
c ≤ D and vS + R > H and (j, i) = (1, R)



c ≤ D and (j, i) 6∈ {(1, 1), (1, R)}
1


0
c>D


−1
β − α FF
c ≤ D and vS + R ≤ D and (j, i) ∈ {(1, 1), (1, R)}



d(uS+1,vS+i) ,c


−1

β
−
α
F
F
c ≤ D and vS + R > H and (j, i) = (1, 1)

d(uS+1,vS+i) ,c
= β
c ≤ D and vS + R > H and (j, i) = (1, R)



1
c ≤ D and (j, i) 6∈ {(1, 1), (1, R)}



0
c>D
from which we derive:

2

 Dβ − αβ(1[d(uS+1,vS+1) ≤D] + 1[d(uS+1,vS+R) ≤D] ) vS + R ≤ H
+ α2 1[d(uS+1,vS+1) =d(uS+1,vS+R) ≤D]
f (u, v) ≡
g(u, v, c, j, i) =

Dβ 2 − αβ1
c=1 j,i=1
vS + R > H
[d(uS+1,vS+1) ≤D]
Q
where (A(h))d(1,1) ,...,d(H,H) = 0≤uS<H f (u, v).
(1)
D
X

R
Y

0≤vS<H

At this point we branch into two cases. If S divides R − 1, then for all u, v ∈ N such that vS + R ≤ H and
) depends only on the indices d(uS+1,vS+1) and
uS < H, the above expression for f (u, v) and f (u, v + R−1
S
d(uS+1,vS+R) , while these two indices affect only the aforementioned expressions. By denoting
(u,v)
Ad(uS+1,vS+1) ,d(uS+1,vS+R) = f (u, v) · f (u, v + R−1
), we can write it as:
S



Dβ 2 − 2αβ + α2 1[i=j] Dβ 2 − αβ
i, j ≤ D





 Dβ 2 − αβ Dβ 2
i ≤ D and j > D
(u,v)
2
Aij
=
2

Dβ
−
αβ
i > D and j ≤ D


2

i, j > D
Dβ 2
where i, j ∈ [M ] stand for the possible values of d(uS+1,vS+1) and d(uS+1,vS+R) , respectively. Substituting
1/4
2α
, results in:
, as stated in the claim, and setting α = D
D
2


1[i=j] i, j ≤ D


4
i ≤ D and j > D
(u,v)
= D
Aij
2

i > D and j ≤ D
D

8
i, j > D
D


which means rank A(u,v) = D. Since (A(h))d(1,1) ,...,d(H,H) equals to the product
Q
(u,v)
, then JA(h)KP,Q equals to the Kronecker product of the matrices
0≤uS<H Ad
(uS+1,vS+1) ,d(uS+1,vS+R)
β=

0≤vS≤H−R

in {A(u,v) |0 ≤ uS < H, 0 ≤ vS ≤ H − R}, up to permutation of its rows and columns, which do not affect
its matrix rank. Thus, the matricization rank of A(h) satisfies:
H−R
(u,v)
H
|0≤uS<H,0≤vS≤H−R}|
rank (JA(h)K ) = D|{A
= Db S +1c·d S e
P,Q

which proves the claim for this case.
If S does not divide R − 1, then for all u, v ∈ N, such that vS + R ≤ H and uS < H, it holds that f (u, v)
depends only on the indices d(uS+1,vS+1) and d(uS+1,vS+R) , and they affect only f (u, v). Additionally, for
all u, v ∈ N, such that H < vS + R, vS < H and uS < H, it holds that f (u, v) depends only on the index
(u,v)
d(uS+1,vS+1) , and this index affects only f (u, v). Let us denote Ad(uS+1,vS+1) ,d(uS+1,vS+R) = f (u, v) for
vS + R ≤ H:



Dβ 2 − 2αβ + α2 1[i=j]
i, j ≤ D



 Dβ 2 − αβ
i ≤ D and j > D
(u,v)

Aij
=
2

Dβ
−
αβ
i > D and j ≤ D


 Dβ 2 
i, j > D

18

Published as a conference paper at ICLR 2018

which by setting β =

2α
D

and α = 1 results in:


1[i=j]

2
(u,v)
Aij
= D
2


D

4
D

i, j ≤ D
i ≤ D and j > D
i > D and j ≤ D
i, j > D



(u,v)
which means rank A(u,v) = D. For vS + R > H, and we can define the vector ad(uS+1,vS+1) = f (u, v),
which by using the same values of α and β results in:
(
2
i≤D
(u,v)
ai
= D
4
i>D
D
By viewing a(u,v) as either a column or row vector, depending on whether d(uS+1,vS+1) ∈ P or
d(uS+1,vS+1) ∈ Q, respectively, it holds that JA(h)KP,Q equals to the Kronecker product of the matrices in
{A(u,v) } 0≤uS<H ∪ {a(u,v) } 0≤uS<H , up to permutations of its rows and columns, which do not affect
H−R<vS<H
0≤vS≤H−R


the rank. Since a(u,v) 6= 0 then rank a(u,v) = 1, which means the matricization rank of A(h) once again
holds:
rank (JA(h)KP,Q ) = D|{A

(u,v)

|0≤uS<H,0≤vS≤H−R}|

= Db

H−R
+1
S

c·d H
S e

In the preceding claim we have describe an example for the case where the total receptive of the first GC layer
is already large enough for satisfying the conditions of the theorem. In the following claim we extend this result
for the general case. This is accomplished by showing that a network comprised of just L GC layers with local
receptive fields {R(l) × R(l) }l∈[L] , strides {S (l) × S (l) }l∈[L] , and output channels {D(l) }l∈[L] , can effectively
compute the same output as the first GC layer from claim 3, for all inputs 3 .
Recall that the layer from claim 3 performs an identical transformation on each M × 1 × 1 patch from its input,
followed by taking the point-wise product of far-away pairs of transformed patches. Thus, the motivation
behind the specific construction we use, is to use the first of the L layers to perform this transformation, while
using half of its output channels for storing the transformed patch from the same location, and the other half for
storing a transformed patch, but from a location farthest to the right, constrained by its local receptive field. This
is equal to having one set of transformed patches sitting still, while another “shifted” set of transformed patches.
The other layers simply pass the the first half of the channels as is, using an identity operation as defined in
claim 2, while continuously shifting the other half of the channels more and more to the left, bringing faraway
patches closer together. Finally, at the last layer we take both halves and multiple them together.
Claim 4. Assume Φ is a ConvAC comprised of just L GC layers as described above, where the output of the
network is not limited to a scalar value. Assume the total stride of the L-th GC layer is greater than H/2, and
(L)
(L,α)
let TS and TR
be the total stride and the α-minimal total receptive field, respectively, for α = bH/2c + 1.
(L,α)
(L)
Let Ψ be a ConvAC comprised of a single GC layer with local receptive field R ≡ TR
, stride S ≡ TS ,
output channels D ≡ min{ 21 min1≤l<L D(l) , D(L) }, where its weights and biases are set to the following:
(
Am,c (j, i) ∈ {(1, 1) , (ρ, τ )}
(c)
wmji =
0
Otherwise
(
βc (j, i) ∈ {(1, 1) , (ρ, τ )}
(c)
bji =
1 Otherwise
for β ∈ RD , A ∈ RM ×D and (ρ, τ ) ∈ {(1, R), (R, 1)}. Then, there exists a set of weights to the layers
of Φ such that for every input X, the output of Φ is equivalent to the output of Ψ for channels ≤ D, and zero
otherwise.
Proof. The two possible cases for (ρ, τ ) are completely symmetric, thus it is enough to prove the claim just
for (ρ, τ ) = (1, R). Additionally, we can assume w.l.o.g. that ∀l, R(l) > 1, by setting any 1 × 1 layer to act
as pass-through according to claim 2, and also assume that the α-minimal total receptive field is exactly equal
to the total receptive field of the L-th layer, by applying claim 1 to realize an equivalent network with smaller
windows. Finally, the case for L = 1 is trivial, and thus we assume L > 1.
3

Notice that in this context, there is no representation layer, and the input can be any 3-order tensor.

19

Published as a conference paper at ICLR 2018

n
o
Let us set the parameters w(l,k) , b(l,k) of the layers of Φ as follows:

(l,k)

wdji

(l,k)

bji


−Ad,k
(l = 1) and (1 ≤ k ≤ D) and (j, i) = (1, 1)





−A
(l = 1) and (D < k ≤ 2D) and (j, i) = (1, R(l) )
d,k−D




(1 < l < L) and (1 ≤ k ≤ D) and (j, i) = (1, 1)
1[d=k]
= 1[d=k]
(1 < l < L) and (D < k ≤ 2D) and (j, i) = (1, R(l) )


1[d=k]
(l = L) and (1 ≤ k ≤ D) and (j, i) = (1, 1)




1
(l
= L) and (1 ≤ k ≤ D) and (j, i) = (1, R(l) )

[d=M
+k]


0
Otherwise

βk
(l = 1) and (1 ≤ k ≤ D) and (j, i) = (1, 1)





β
(l = 1) and (D < k ≤ 2D) and (j, i) = (1, R(l) )
k−D




(1 < l < L) and (1 ≤ k ≤ D) and (j, i) = (1, 1)
0
= 0
(1 < l < L) and (D < k ≤ 2D) and (j, i) = (1, R(l) )


0
(l = L) and (1 ≤ k ≤ D) and (j, i) = (1, 1)




0
(l
= L) and (1 ≤ k ≤ D) and (j, i) = (1, R(l) )



1
Otherwise

(l)

(l)

(l)

It is left to prove the above satisfies the claim. Let O(l) ∈ RD ×H ×H be the output of the l-th layer,
for l ∈ [0, . . . , L], where H (l) is the width and height of the output. We additionally assume that for indices
beyond the bounds of [D(l) ] × [H (l) ] × [H (l) ] the value of O(l) is zero, i.e. we assume zero padding when
applying the convolutional operation of the GC layer. We extend the definition for l = 0, by setting D(0) ≡ M
and H (0) ≡ H, where we identify O(0) with the input to the network Φ. Given the above, the output of the
first layer for k ∈ [D(1) ] and 0 ≤ u, v < H (1) , is as follows:

(1)
Ok,u+1,v+1

=

(1)
R
Y


b(1,k)
ji

j,i=1

+

(0)
D
X


(1,k) (0)
wdji Od,uSh +j,vSw +i 

d=1


PM
(0)

Ad,k · Od,uSh +1,vSw +1
βk + d=1
PM
(0)
= βk−D + d=1 Ad,k−D · Od,uS
(1)
h +1,vSw +R


1

1≤k≤D
D < k ≤ 2D
Otherwise

We will show by induction that for 1 < l < L, k ∈ [D(l) ] and 0 ≤ u, v < H (l) the output of the l-th layer
(l)
Ok,u+1,v+1 always equals to:

(l)

Ok,u+1,v+1


1

Ok,uη(l) +1,vη(l) +1
1
= Ok,uη(l) +1,vη(l) +ξ(l)


1

k≤D
D < k ≤ 2D
Otherwise

Q
P
(k)
where η (l) = li=2 S (i) and ξ (l) = R(l) · η (l−1) + l−1
− S (l) ) · η (k−1) . It is trivial to verify that for
k=2 (R
l = 2 it indeed holds, since:

(2)

Ok,u+1,v+1

 (1)

Ok,uS (2) +1,vS (2) +1
= O(1) (2)
(2)
(2)

 k,uS +1,vS +R
1

20

k≤D
D < k ≤ 2D
Otherwise

Published as a conference paper at ICLR 2018

where η (2) = S (2) and ξ (2) = R(2) . Assume the claim holds up to l − 1, and we will show it also holds for l:


(l)
(l−1)
R
DX
Y
(l)
(l,k)
(l,k)
l−1
bji +

Ok,u+1,v+1 =
wdji O
(l)
(l)
d,uS

j,i=1

+j,vS

+i

d=1

 (l−1)
k≤D

Ok,uS (l) +1,vS (l) +1
= O(l−1)(l)
D
< k ≤ 2D
(l)
(l)

 k,uS +1,vS +R
1
Otherwise
 (1)

Ok,(uS (l) )η(l−1) +1,(vS (l) )η(l−1) +1

Induction Hypothesis ⇒ = O(1) (l) (l−1)
+1,(vS (l) +R(l) −1)η (l−1) +ξ(l−1)
k,(uS )η



1

1

k≤D
Ok,uη(l) +1,vη(l) +1
1
= Ok,uη(l) +1,vη(l) +ξ(l) D < k ≤ 2D


1
Otherwise

k≤D
D < k ≤ 2D
Otherwise

Were we used the fact that η (l) = S (l) η (l−1) and ξ (l) = R(l) η (l−1) + ξ (l−1) − η (l−1) .
(L)

Finally, we show that Ok,u+1,v+1 for k ≤ D and 0 ≤ u, v < H (L) equals to the output of the single GC layer
specified in the claim:


(L−1)
(L)
DX
R
Y
(L,k)
(L−1)
(L,k)
(L)
bji
wdji Od,uS (L) +j,vS (L) +i 
+
Ok,u+1,v+1 =
j,i=1

d=1

(L−1)

(L−1)

(1)

(1)

= Ok,uS (L) +1,vS (L) +1 · Ok,uS (L) +1,vS (L) +R(L)
= Ok,uη(L) +1,vη(L) +1 · Ok,uη(L) +1,vη(L) +ξ(L)


(0)
D
X
(0)
= βk +
Ad,k Od,uη(L) S (1) +1,vη(L) S (1) +1 
d=1


· βk +

(0)
D
X


(0)

Ad,k Od,uη(L) S (1) +1, vη(L) +ξ(L) −1 S (1) +R(1) ) 
(
)



(0)
(0)
D
D
X
X
(0)
(0)


= βk +
Ad,k O
Ad,k O
β
+
k
(L)
(L)
d=1

d=1

d,uTS

+1,vTS

+1

d=1


(L)

d,uTS

(L)

+1,vTS

(L)

+TR



which is indeed equal to the single GC layer. For k > D, both the bias and the weights for the last layer are
(L)
zero, and thus Ok,u+1,v+1 = 1.
Finally, with the above two claims set in place, we can prove our main theorem:
Proof. (of theorem 1) Using claim 4 we can realize the networks from claim 3, for which the matricization
rank for either partition equals to:


H

l
m

 H−T (K,b /2c)
R

+1· H

D

TS

TS

Since for any matricization [A (Ψ)]P,Q the entries of the matricization are polynomial functions with respect
to the parameters of the network, then, according to lemma 3, the set of parameters of Φ, that does not attain
the above rank, has zero measure. Since the union of zero measured sets is also of measure zero, then all
parameters except a set of zero measure attain this matricization rank for both partitions at once, concluding
the proof.

C.4

P ROOF OF P ROPOSITION 2

Following theorem 1, to compute the lower bound for the network described in proposition 2, we need to find
the first layer for which its total receptive field is greater than H/2, and then estimate its total stride and its

21

Published as a conference paper at ICLR 2018

α-minimal total receptive field, for α = bH/2c. In the following claims we analyze the above properties of the
given network:
Claim 5. The total stride and total receptive field of the l-th B × B layer in the given network, i.e. the
(2l − 1)-th GC layer after the representation layer, are given by the following equations:
(2l−1)

TS
(2l−1)

TR

(S (1) , . . . , S (2l−1) ) = 2l−1

(R(1) , S (1) , . . . , R(2l−1) , S (2l−1) ) = (2B − 1)2l−1 − B + 1

(2l−1)

Proof. From eq. 1 it immediately follows that TS
(S (1) , . . . , S (2l−1) ) = 2l−1 . From eq. 2, the 2 × 2 stride
(2l)
2 layers do not contribute to the receptive field as R
− S (2l) = 0, which results in the following equation:
(2l−1)

TR

(R(1) , S (1) , . . . , R(2l−1) , S (2l−1) ) = B · 2l−1 +

l−1
X
(B − 1)2i−1
i=1

= B · 2l−1 + (B − 1)(2l−1 − 1)
= (2B − 1)2l−1 − B + 1

Claim 6. The α-minimal total receptive field for the l-th B × B layer in the given network, for α ∈ N and
2l−1 ≤ α < 2l − 1, always equals (α + 1).
Proof. From eq. 3, the following holds:
(2l−1,α)

TR

=

(2l−1)

argmin

TR

∀i∈[l],1≤t2i−1 ≤B

(t1 , 1, 2, 2, t3 , 1, . . . , t2l−1 , 1)

(2l−1)
TR
(t1 ,1,2,2,t3 ,1,...,t2l−1 ,1)>α

=

t2l−1 · 2l−1 +

argmin
∀i∈[l],1≤t2i−1 ≤B
P
i−1
>α
t2l−1 ·2l−1 + l−1
i=1 (t2i−1 −1)2

l−1
X
(t2i−1 − 1)2i−1
i=1

Notice that the right term in the equation resembles a binary representation. If we limit t2i−1 to the set {1, 2},
this term can represent any number in the set {0, . . . , 2l−1 − 1}, and by choosing t2l−1 = 1, the complete term
can represent any number in the set {2l−1 , . . . , 2l − 1}, and specifically, for 2l−1 ≤ α < 2l − 1, there exists an
(2l−1,α)
= α+1.
assignment for t2i−1 ∈ {1, 2} for i ∈ [l−1] such that this terms equal (α+1), and thus TR
With the above general properties for the given network, we can simplify the expression for the lower bound
given in theorem 1:
Claim
7.
If
the
l-th
B × B
layer
in
the
given
network
satisfies
(2l−1)
TR
(R(1) , S (1) , . . . , R(2l−1) , S (2l−1) ) > H/2, then the lower bound given in theorem 1 equals to
2L−2l+1
M2
Proof. From the description of the network and the previous claims it holds that D = M , H = 2L ,
(2l−1)
(2l−1,bH/2c)
TS
= 2l−1 , and TR
= 2L−1 + 1. Substituting all the above in eq. 4 results in:


(Eq. 4) = M
j

=M
= M2



L
· 2
l−1

2L −2L−1 −1
+1
2l−1

2

k
1
2L−l +1− l−1
·2L−l+1
2

2L−2l+1

With all of the above claims in place, we our ready to prove proposition 2:

22

Published as a conference paper at ICLR 2018

Proof. (of proposition 2) From claim 5, we can infer which is the first B × B layer such that its receptive field
is greater than H/2:
(2B − 1) · 2l−1 − B + 1 > 2L−1
2L + 2B − 2
2B − 1


2L + 2B − 2
⇒ l = 1 + log2
2B − 1
⇒ l > log2

Combining the above with claim 7, results in:

M

22L−2l+1

=M

2

≥ M2
(2L ≡ H) ⇒ = M
=M
The limits and the special case for B ≤

C.5

H
5



L
2L−1−2 log2 2 +2B−2
2B−1
L
2L−1−2 log2 2 +2B−2
2B−1

H2
2

H−1 −2
(1+ 2B−1
)

(2B−1)2
2

−2

·(1+ 2B−2
H )

+ 1 are both direct corollaries of the above expressions.

P ROOF OF THEOREM 2

We begin by proving an analogue of claim 3, where we show that for any given matricization of the grid tensor
A(h), induced by the overlapping network realizing the function h, the matricization rank is exponential. The
motivation behind the construction, for when parameters are “unshared”, is that we can utilized the fact that
there are separate sets of kernels, with local receptive fields the size of the input, for each spatial location.
Thus, each kernel can “connect” the index (of the grid tensor) matching its spatial location, with almost any
other index, and specifically such that the two indices come from different sets of the matricization I ∪· J of
A(h). For the “shared” case, we simply use polynomially more output channels to simulate the “unshared”
case.
2

Claim 8. For an arbitrary even partition (I, J) of {(1, 1), . . . , (H, H)}, such that |I| = |J| = H2 , there
exists an assignment to the parameters of the network given in theorem 2, for either the “unshared” or “shared”
settings, such that rank (JA(h)K) = M

H2
2

.

2

Proof. Let (I, J) be an arbitrary even partition of {(1, 1), . . . , (H, H)}, such that |I| = |J| = H2 , I =
2
{i1 , . . . , i|I| }, and J = {j1 , . . . , j|J| }, where for k ∈ [ H2 ] it holds that ik < ik+1 and jk < jk+1 (using
H2

2
such that qk = ik
lexical ordering), and we assume w.l.o.g. that i1 = (1, 1). We define the set {(qk , pk )}k=1
and pk = jk if ik < jk , and otherwise qk = jk and pk = ik .

We prove the t“unshared” case first, where the parameters of the first GC layers are given by
{(w(c,u,v) , b(c,u,v) )}D,H,H
c=1,u=1,v=1 , for which we choose the following assignment:
(c,u,v)
wm,j,i

(c,u,v)
bj,i

=

=

(
(F −1 )m,c

c ≤ M and ∃k ∈

0
(
0

Otherwise

1[c≤M ]

c ≤ M and ∃k ∈

h

h

H2
2

H2
2

i

i

, qk = (u, v) and (j, i) ∈ {(1, 1), pk − qk + (1, 1)}

, qk = (u, v) and (j, i) ∈ {(1, 1), pk − qk + (1, 1)}

Otherwise

where for u, v ∈ [H] such that qk = (u, v) it holds that pk − qk + (1, 1) ∈ {(1, 1), . . . , (H, H)} because
qk ≤ pk . Similar to the proof of claim 3, we set all layers following the first GC layer such that the following
equality holds:
(A(h))d(1,1) ,...,d(H,H) =

H X
D Y
H
Y

(c,u,v)
bji

u,s=1 c=1 j,i=1

+

M
X
m=1

23

!
(c,u,v)
wmji Om,u+j−1,v+i−1

Published as a conference paper at ICLR 2018

Which under the assignment to parameters we chose earlier, it results in:
!
H 2/2 D
M
YX X
−1
(A(h))d(1,1) ,...,d(H,H) =
(F )m,c Fdqk ,m
k=1 c=1

m=1

M
X

!
(F

−1

)m,c Fdpk ,m

m=1

H 2/2

=

D
YX
(F · F −1 )dqk ,c · (F · F −1 )dpk ,c

k=1 c=1
H 2/2

=

D
YX

1[dqk =c] · 1[dpk =c]

k=1 c=1
H 2/2

=

Y

1[dqk =dpk ]

k=1

which means JA(h)K(I,J) equals to the Kronecker product of

H2
2

M ×M -identity matrices, up to permutations

of its rows and columns which do not affect its matrix rank. Thus, rank (JA(h)K) = M

H2
2

.

For the “shared” setting, we denote the parameters of the first GC layer by {(w(d) , b(d) )}D
c=1 , and set them as:

 −1
2
∃c ∈[M ]∃u,

(F )m,c
h v2∈
i [H], d = cH + uH + v

(d)
H
and ∃k ∈ 2 , qk = (u, v) and (j, i) ∈ {(1, 1), pk − qk + (1, 1)}
wm,j,i =


0
Otherwise


2
∃c ∈[M ]∃u,

0
h v2∈
i [H], d = cH + uH + v

(d)
and ∃k ∈ H2 , qk = (u, v) and (j, i) ∈ {(1, 1), pk − qk + (1, 1)}
bj,i =


1[d≤M H 2 ] Otherwise
the parameters of the other layers are set as in the “unshared” case, and the proof follows similarly.
In the preceding claim, we have found a separate example for each matricization, such that the matricization
rank is exponential. In the following proof of the theorem 2, we leverage basic properties from measure theory
to show that almost everywhere the induced grid tensor has an exponential matricization rank, under every
possible even matricization – without explicitly constructing such an example.
Proof. (of theorem 2) For any even partition (I, J) of {(1, 1), . . . , (H, H)}, according to claim 8 there exist
parameters for which rank (JA(h)K)(I,J) = M

H2
2

, and thus according to lemma 3 the set of parameters for

H2
2

which rank (JA(h)K) < M
is of measure zero. Since the finite union of sets of measure zero is also
of measure zero, then almost everywhere (with respect to the Lebesgue measure) the parameters results in
networks such that for all even partitions rank (JA(h)K)(I,J) = M

24

H2
2

.

