The power of deeper networks for expressing natural functions
David Rolnick∗ , Max Tegmark†
Dept. of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139 and
Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139

arXiv:1705.05502v1 [cs.LG] 16 May 2017

(Dated: May 17, 2017)
It is well-known that neural networks are universal approximators, but that deeper networks tend
to be much more efficient than shallow ones. We shed light on this by proving that the total number
of neurons m required to approximate natural classes of multivariate polynomials of n variables
grows only linearly with n for deep neural networks, but grows exponentially when merely a single
hidden layer is allowed. We also provide evidence that when the number of hidden layers is increased
from 1 to k, the neuron requirement grows exponentially not with n but with n1/k , suggesting that
the minimum number of layers required for computational tractability grows only logarithmically
with n.
I.

INTRODUCTION

Deep learning has lately been shown to be a very powerful
tool for a wide range of problems, from image segmentation to machine translation. Despite its success, many
of the techniques developed by practitioners of artificial
neural networks (ANNs) are heuristics without theoretical guarantees. Perhaps most notably, the power of feedforward networks with many layers (deep networks) has
not been fully explained. The goal of this paper is to shed
more light on this question and to suggest heuristics for
how deep is deep enough.
It is well-known [1–3] that nonlinear neural networks with
a single hidden layer can approximate any function under
reasonable assumptions, but it is possible that the networks required will be extremely large. Recent authors
have shown that some functions can be approximated by
deeper networks much more efficiently (i.e. with fewer
neurons) than by shallower ones. However, many of the
functions in question are complicated or arise from “existence proofs” without explicit constructions, and the
results often apply only to types of network rarely used
in practice.
Deeper networks have been shown to have greater representational power with respect to various notions of complexity, including piecewise linear decision boundaries [4]
and topological invariants [5]. Recently, Poole et al. [6]
and Raghu et al. [7] showed that the trajectories of input
variables attain exponentially greater length and curvature with greater network depth. Work including [8] and
[9] shows that there exist functions that require exponential width to be approximated by a shallow network.
Mhaskar, Liao, and Poggio [10], in considering compositional functions with this property, inquire whether explicit examples must be pathologically complicated.
Various authors have also considered the power of deeper

∗ drolnick@mit.edu
† tegmark@mit.edu

network of types other than the standard feedforward
model. The problem has also been posed for sum-product
networks [11] and restricted Boltzmann machines [12].
Cohen, Sharir, and Shashua [13] showed, using tools from
tensor decomposition, that shallow arithmetic circuits
can express only a measure-zero set of the functions expressible by deep circuits. A weak generalization of this
result to convolutional neural networks was shown in [14].
In summary, recent years have seen a wide variety of theoretical demonstrations of the power of deep neural networks. It is important and timely to extend this work
to make it more concrete and actionable, by deriving
resource requirements for approximating natural classes
of functions using today’s most common neural network
architectures. Lin, Tegmark, and Rolnick [15] recently
proved that it is exponentially more efficient to use a
deep network than a shallow network when approximating the product of input variables. In the present paper,
we will greatly extend these results to include broad natural classes of multivariate polynomials, and to tackle the
question of how resource use depends on the precise number of layers. Our results apply to standard feedforward
ANNs with general nonlinearities and are borne out by
empirical tests.
The rest of this paper is organized as follows. In §II B,
we consider the complexity of approximating a multivariate polynomial p(x) using a feedforward neural network
with input x = (x1 , . . . , xn ). We show (Theorem II.4)
that for general sparse p, exponentially many neurons are
required if the network is shallow, but at most linearly
many for a deep network. For monomials p, we calculate
(Theorem II.1) exactly the minimum number of neurons
required for a shallow network. These theorems apply for
all nonlinear activation functions σ with nonzero Taylor
coefficients; a slightly weaker result (Theorem II.2) holds
for an even broader class of σ.
In §II C, we present similar results (Propositions II.5
and II.6) for approximating univariate polynomials. In
this case, shallow networks require linearly many neurons
while for deep networks it suffices to use only logarithmically many neurons. In §II D, we tie the difficulty of

2
approximating polynomials by shallow networks to the
complexity of tensor decomposition (Proposition II.7).
In §III A, we consider networks with a constant number
k of hidden layers. For input of dimension n, we show
(Theorem III.1) that products can be approximated with
a number of neurons exponential in n1/k , and justify our
theoretical predictions with empirical results. While still
exponential, this shows that problems unsolvable by shallow networks can be tractable even for k > 1 of modest
size.
Finally, in §III B, we compare our results on feedforward neural networks to prior work on the complexity of
Boolean circuits. We conclude that these problems are
independent, and therefore that established hard problems in Boolean complexity do not provide any obstacle
to analogous results for standard deep neural networks.

B.

Multivariate polynomials

The following theorem generalizes a result of Lin,
Tegmark, and Rolnick [15] to arbitrary monomials. By
setting r1 = r2 = . . . = rn = 1 below, we recover their
result that the product of n numbers requires 2n neurons
in a shallow network but can be done with linearly many
neurons in a deep network.
Theorem II.1. Let p(x)
Pn denote the monomial
Suppose that the
xr11 xr22 · · · xrnn , with N =
i=1 ri .
nonlinearity σ(x) has nonzero Taylor coefficients up to
xN . Then:
m1 (p, σ) =
m(p, σ) ≤

n
Y

(ri + 1),

i=1
n
X

(7dlog2 (ri )e + 4),

(1)
(2)

i=1

where dxe denotes the smallest integer that is at least x.
II.

THE INEFFICIENCY OF SHALLOW
NETWORKS

In this section, we compare the efficiency of shallow networks (those with a single hidden layer) and deep networks at approximating multivariate polynomials.

A.

Definitions

Let σ(x) be a nonlinear function, k a positive integer, and
p(x) a multivariate polynomial of degree d. We define
mk (p, σ) to be the minimum number of neurons (excluding input and output) required to approximate p with
a neural net having k hidden layers and nonlinearity σ,
where the error of approximation is of degree at least
d + 1 in the input variables. Thus, in particular, m1 (p, σ)
is the minimal integer m such that:
m
X
j=1

wj σ

n
X

!
aij xi

= p(x) + O(xd+1
+ . . . + xd+1
n ).
1

i=1

Note that approximation up to degree d allows us to approximate any polynomial to high precision as long as
the input variables are small enough. In particular, for
homogeneous polynomials of degree d, we can adjust the
weights so as to scale each variable by a constant λ  1
before input, and then scale the output by 1/λd , in order
to achieve arbitrary precision.
We set m(p, σ) = mink≥0 mk (p, σ). We will show that
there is an exponential gap between m1 (p, σ) and m(p, σ)
for various classes of polynomials p.

Proof. Without loss of generality, suppose that ri > 0 for
i = 1, . . . , n. Let X be the multiset1 in which xi occurs
with multiplicity ri .
Qn
We first show that i=1 (ri + 1) neurons are sufficient to
approximate p(x). Appendix A in [15] demonstrates that
for variables y1 , . . . , yN , the product y1 · · · · · yN can be
approximated as a linear combination of the 2N functions
σ(±y1 ± · · · ± yN ).
Consider setting y1 , . . . , yN equal to the elements of multiset X. Then, we conclude that we can approximate p(x)
as a linear combination of the functions σ(±y1 ±· · ·±yN ).
However, these functions are not all distinct: there are
ri + 1 distinct ways to assign ± signs to ri copies of xi
(ignoring
Qn permutations of the signs). Therefore, there
are i=1 (ri + 1) distinctQfunctions σ(±y1 ± · · · ± yN ),
n
proving that m1 (p, σ) ≤ i=1 (ri + 1).
We now adapt methods introduced in [15] to show that
this number of neurons is also necessary for approximating p(x). Let m ≡ m1P
(p, σ) and suppose that σ(x) has
∞
k
the Taylor expansion
k=0 σk x . Then, by grouping
terms of each order, we conclude that there exist constants aij and wj such that
!N
m
n
X
X
σN
wj
aij xi
= p(x)
(3)
j=1

σk

m
X
j=1

1

i=1

wj

n
X

!k
aij xi

=0

for 0 ≤ k ≤ N − 1. (4)

i=1

That is, a collection of elements of X, in which each element is
allowed to occur multiple times.

3
For each S ⊆ X, let us take the derivative of equations
(3) and (4) by every variable that occurs in S, where we
take multiple derivatives of variables that occur multiple
times. This gives
!N −|S|
m
n
Y
X
Y
σN · N ! X
wj
ahj
aij xi
=
xi , (5)
|S|! j=1
i=1
h∈S
i6∈S
!k−|S|
m
n
Y
X
σk · k! X
wj
ahj
aij xi
=0
(6)
|S|! j=1
i=1

7dlog2 (ri )e neurons arranged in a deep network. Thereri
fore,
P we can approximate all of the xi using a total of
i 7dlog2 (ri )e neurons. From [15], we know that these
n terms can be multiplied
using 4n additional neurons,
P
giving us a total of i (7dlog2 (ri )e + 4). This completes
the proof.
In order to approximate a degree-N polynomial effectively with a single hidden layer, we must naturally assume that σ has nonzero N th Taylor coefficient. However, if we do not wish to make assumptions about the
other Taylor coefficients of σ, we can still prove the following weaker result:

h∈S

Qn
for |S| ≤ k ≤ N − 1. Observe that there are i=1 (ri + 1)
choices for S, since each variable xi can b included
anywhere
from 0 to ri times. Define A to
Qn
Q be the
( i=1 (ri + 1))×m matrix with entries AS,j = h∈S ahj .
We claim that A has full row rank. This would show that
the number of columns m is at least the number of rows
Q
n
i=1 (ri + 1), proving the desired lower bound on m.

Theorem II.2. Once again, let p(x) P
denote the monon
· · xrnn . Then, for N =
mial xr11 xr22 · Q
i=1 ri , we have
n
m1 (p, σ) ≤
(r
+
1)
if
σ
has
nonzero
N th Tayi
i=1
lor coefficient. For any σ, we have that m1 (p, σ) is at
least the maximum
coefficient in the univariate polynoQ
mial g(y) = i (1 + y + . . . + y ri ).

Suppose towards contradiction that the rows AS` ,• admit
a linear dependence:
r
X

Proof outline. The first statement follows as in the proof
of Theorem II.1. For the second, consider once again
the equation (5). The left-hand side can be written, for
any S, as the linear combination of basis functions of the
form:
!N −|S|
n
X
aij xi
.
(7)

c` AS` ,• = 0,

`=1

where the coefficients c` are nonzero and the S` denote distinct subsets of X. Set s = max` |S` |. Then,
take the dot product of each side of the above equation by the vector with entries (indexed by j) equal to
Pn
N −s
wj ( i=1 aij xi )
:
0=

r
X

c`

`=1

=

+

m
X

wj

j=1

X

c`

Y

ahj

wj

aij xi

Y

ahj

j=1

h∈S`

i=1

X

m
X

Y

n
X

c`

j=1

wj

ahj

!N −|S` |

n
X

`|(|S` |=s)

`|(|S` |<s)

Letting S vary over multisets of fixed size s, we see that
the right-hand side of (5) attains every degree-s monomial that divides p(x). The number of such monomials is
the coefficient Cs of the term y s in the polynomial g(y).
Since such monomials are linearly independent, we conclude that the number of basis functions of the form (7)
above must be at least at least Cs . Picking s to maximize
Cs gives us the desired result.

!N −s

i=1

h∈S`
m
X

n
X

i=1

aij xi
!(N +|S` |−s)−|S` |
aij xi

.

Corollary II.3. If p(x) is the product of the inputs
(i.e. r1 = · · ·p= rn = 1), we conclude that m1 (p, σ) ≥
n
n
bn/2c ∼ 2 / πn/2, under the assumption that the nth
Taylor coefficient of σ is nonzero.

|S` |!
·0
σk · k!

It is natural now to consider the cost of approximating general polynomials. However, without further constraint, this is relatively uninstructive because polynomials of degree d in n variables live within a space of dimension n+d
d , and therefore most require exponentially
many neurons for any depth of network. We therefore
consider polynomials of sparsity c: that is, those that
can be represented as the sum of c monomials. This includes many natural functions.

i=1

h∈S`

We can use (5) to simplify the first term and (6) (with
k = N + |S` | − s) to simplify the second term, giving us:
0=

X

c` ·

h6∈S`

`|(|S` |=s)

=

X
`|(|S` |=s)

Y
|S` |!
·
xh +
σN · N !

c` ·

|S` |!
·
σN · N !

Y

X
`|(|S` |<s)

c` ·

xh .

h6∈S`

Q
Since the monomials xi ∈S` xi are linearly independent,
this contradicts our assumption that the c` are nonzero.
We conclude thatQA has full row rank, and therefore that
n
m1 (p, σ) = m ≥ i=1 (ri + 1). This completes the proof
of equation (1).
For equation (2), it follows from Proposition II.6 part
(2) below that for each i, we can approximate xri i using

The following theorem, when combined with Theorem
II.1, shows that general polynomials p with subexponential sparsity have exponential large m1 (p, σ), but subexponential m(p, σ).

4
Theorem II.4. Suppose that p(x) is a multivariate polynomial of degree N , with c monomials
q1 (x), q2 (x), . . . , qc (x). Suppose that the nonlinearity
σ(x) has nonzero Taylor coefficients up to xN . Then,
1. m1 (p, σ) ≥ 1c maxj m1 (qj , σ).
P
2. m(p, σ) ≤ j m(qj , σ).
Proof outline. Our proof in Theorem II.1 relied upon the
fact that all nonzero partial derivatives of a monomial
are linearly independent. This fact is not true for general polynomials p; however, an exactly similar argument
shows that m1 (p, σ) is at least the number of linearly independent partial derivatives of p, taken with respect to
multisets of the input variables.
Consider the monomial q of p such that m1 (q, σ) is maximized, and suppose that q(x) = xr11 xr22 · · ·Q
xrnn . By Theon
rem II.1, m1 (q, σ) is equal to the number i=1 (ri + 1) of
distinct monomials that can be obtained by taking partial derivatives of q. Let Q be the set of such monomials,
and let D be the set of (iterated) partial derivatives corresponding to them, so that for d ∈ D, we have d(q) ∈ Q.
Consider the set of polynomials P = {d(p) | d ∈ D}. We
claim that there exists a linearly independent subset of
P with size at least |D|/c. Suppose to the contrary that
P 0 is a maximal linearly independent subset of P with
|P 0 | < |D|/c.
Since p has c monomials, every element of P has at most
c monomials. Therefore, the total number of distinct
monomials in elements of P 0 is less than |D|. However,
there are at least |D| distinct monomials contained in elements of P , since for d ∈ D, the polynomial d(p) contains
the monomial d(q), and by definition all d(q) are distinct
as d varies. We conclude that there is some polynomial
p0 ∈ P \P 0 containing a monomial that does not appear
in any element of P 0 . But then p0 is linearly independent of P 0 , a contradiction since we assumed that P 0 was
maximal.
We conclude that some linearly independent subset of
P has size at least |D|/c, and therefore that the space
of partial derivatives of p has rank at least |D|/c =
m1 (q, σ)/c. This proves part (1) of the theorem. Part (2)
follows immediately from the definition of m(p, σ).

only logarithmically many neurons in a deep network.
Thus, depth allows us to reduce networks from linear
to logarithmic size, while for multivariate polynomials
the gap was between exponential and linear. The difference here arises because the dimensionality of the space
of univariate degree-d polynomials is linear in d, which
the dimensionality of the space of multivariate degree-d
polynomials is exponential in d.
Proposition II.5. Let σ be a nonlinear function with
nonzero Taylor coefficients. Then, we have m1 (p, σ) ≤
d + 1 for every univariate polynomial p of degree d.
Proof. Pick a0 , a1 , . . . , ad to be arbitrary, distinct real
numbers. Consider the Vandermonde matrix A with
entries Aij = aji . It is well-known that det(A) =
Q
0
i<i0 (ai − ai ) 6= 0. Hence, A is invertible, which means
that multiplying its columns by nonzero values gives another invertible matrix. Suppose that we multiply
P the
jth column of A by σj to get A0 , where σ(x) = j σj xj
is the Taylor expansion of σ(x).
Now, observe that the ith row of A0 is exactly the coefficients of σ(ai x), up to the degree-d term. Since A0
is invertible, the rows must be linearly independent, so
the polynomials σ(ai x), restricted to terms of degree at
most d, must themselves be linearly independent. Since
the space of degree-d univariate polynomials is (d + 1)dimensional, these d+1 linearly independent polynomials
must span the space. Hence, m1 (p, σ) ≤ d + 1 for any
univariate degree-d polynomial p. In fact, we can fix the
weights from the input neuron to the hidden layer (to be
a0 , a1 , . . . , ad , respectively) and still represent any polynomial p with d + 1 hidden neurons.
Proposition II.6. Let p(x) = xd , and suppose that σ(x)
is a nonlinear function with nonzero Taylor coefficients.
Then:
1. m1 (p, σ) = d + 1.
2. m(xd , σ) ≤ 7dlog2 (d)e.
Proof. Part (1) follows from part (1) of Theorem II.1
above, by setting n = 1 and r1 = d.
For part (2), observe that we can approximate the square
x2 of an input x with three neurons in a single layer:
1

C.

Univariate polynomials

As with multivariate polynomials, depth can offer an exponential savings when approximating univariate polynomials. We show below (Proposition II.5) that a shallow
network can approximate any degree-d univariate polynomial with a number of neurons at most linear in d.
The monomial xd requires d + 1 neurons in a shallow network (Proposition II.6), but can be approximated with

2σ 00 (0)

(σ(x) + σ(−x) − 2σ(0)) = x2 + O(x4 ).

We refer to this construction as a square gate, and the
construction of [15] as a product gate. We also use identity
gate to refer to a neuron that simply preserves the input
of a neuron from the preceding layer (this is equivalent
to the skip connections in residual nets).
Consider a network in which each layer contains a square
gate (3 neurons) and either a product gate or an identity gate (4 or 1 neurons, respectively), according to the

5
following construction: The square gate squares the output of the preceding square gate, yielding inductively a
k
result of the form x2 , where k is the depth of the layer.
Writing d in binary, we use a product gate if there is a 1
in the 2k−1 -place; if so, the product gate multiplies the
output of the preceding product gate by the output of
the preceding square gate. If there is a 0 in the 2k−1 place, we use an identity gate instead of a product gate.
k
k−1
Thus, each layer computes x2 and multiplies x2
to
the computation if the 2k−1 -place in d is 1. The process
stops when the product gate outputs ud .
This network clearly uses at most 7dlog2 (d)e neurons,
with a worst case scenario where d + 1 is a power of
2.

Proof. Suppose that we can approximate p(u) using a
neural net with m neurons in a single hidden layer. Then,
there exist vectors a1 , a2 , . . . , am of weights from the input to the hidden layer such that
p(u) ≈ w1 σ(a1 · u) + · · · + wm σ(am · u).
If we consider only terms of degree d, we obtain
p(u) = σd

m
X

wi (ai · u)d

(8)

i=1

The symmetric tensor
T=

m
X

(σd wi )ai ⊗ · · · ⊗ ai

i=1

D.

Tensor decomposition

We conclude this section by noting interesting connections between the value m1 (p, σ) and the established hard
problem of tensor decomposition. Specifically, we show
(Proposition II.7) that the minimum number of neurons
required to approximate a polynomial p equals the symmetric tensor rank of a tensor constructed from the coefficients of p.
Let T be an order-d symmetric tensor of dimensions n ×
· · · × n. We say that T is symmetric if the entry Ti1 i2 ···id
is identical for any permutation of i1 , i2 , . . . , id . For T
symmetric, the symmetric tensor rank RS (T) is defined
to be the minimum r such that T can be written
T=

r
X

λi ai ⊗ · · · ⊗ ai ,

i=1

with λ ∈ R and ai ∈ Rn for each i [16]. Thus, for d = 1,
T is simply a real number and RS (T) = 1. For d = 2, T
is a symmetric matrix, and the symmetric tensor rank is
simply the rank of T, where one can take the values λi
above to be eigenvalues of the matrix T.
For a multiset S, we let π(S) denote the number of distinct permutations of S. Thus, if q1 , . . . , qs are frequencies for elements in S, we have


q1 + · · · + qs
π(S) =
.
q1 , . . . , qs
For p(u) = p(u1 , . . . , un ) a homogeneous multivariate
polynomial of degree d, we define the monomial tensor
T(p) as follows:
T(p)j1 ···jd = [uj1 · · · ujd ]p /π({j1 , . . . , jd }),
where [•]p denotes the coefficient of a monomial in p.
Proposition II.7. For p(u) = p(u1 , . . . , un ) a homogeneous multivariate polynomial of degree d, we have
m1 (p) ≥ RS (T (p)).

has symmetric tensor rank at most m. Furthermore, by
equation (8), we have
X
p(u) =
Tj1 ···jd (uj1 · · · ujd ).
1≤j1 ,...,jd ≤m

By the definition of T, the entries Tj1 ···jd are equal up to
permutation of j1 , . . . , jd . Therefore, T must equal the
monomial tensor T(p), showing that m ≥ RS (T(p)) as
desired.
Corollary II.8. Let p(u) = p(u1 , . . . , un ) be a multivariate polynomial of degree d. For c = 0, 1, . . . , d, let
pc (u) be the homogeneous polynomial obtained by taking
all terms of p(u) with degree c. If RS is the maximum
symmetric rank of T(pc (u)), then m1 (p) ≥ RS .
The proof of this statement closely follows that of Proposition II.7.
Various results are known for the symmetric rank of tensors over the complex numbers C [16]. Notably, Alexander and Hirschowitz [17] showed in a highly non-trivial
proof that the symmetric rank of a generic symmetric tensor
 of dimension n and order k over C equals
d n+k−1
/ne, with the exception of a few small values
k
of k and n. However, this result does not hold over the
real numbers R, and in fact there can be several possible
generic ranks for symmetric tensors over R [16].

III.

HOW EFFICIENCY IMPROVES WITH
DEPTH

We now consider how mk (p, σ) scales with k, interpolating between exponential in n (for k = 1) and linear
in n (for k = log n). In practice, networks with modest
k > 1 are effective at representing natural functions. We
explain this theoretically by showing that the cost of approximating the product polynomial drops off rapidly as
k increases.

6
A.

ditions

Networks of constant depth

By repeated application of the shallow network construction in Lin, Tegmark, and Rolnick [15], we obtain the
following upper bound on mk (p, σ), which we conjecture
to be essentially tight. Our approach is reminiscent of
tree-like network architectures discussed e.g. in [10], in
which groups of input variables are recursively processed
in successive layers.

0 = −λ

Y

bj +

j6=i

i−1
X

Qk

j=h+1 bj

bi

h=1


+ (log 2) 

k
Y

!
2bh


bj  2bi , for 1 ≤ i ≤ k

(11)

j=i+1

0=n−

k
Y

bj .

(12)

j=1

Theorem III.1. For p(x) equal to the product
x1 x2 · · · xn , and for any σ with all nonzero Taylor coefficients, we have:


1/k
mk (p, σ) = O n(k−1)/k · 2n
.

(9)

Dividing (11) by
recursion

Qk

j=i+1 bj

and rearranging gives us the

bi = bi−1 + log2 (bi−1 − 1/ log 2).

(13)

Thus, the optimal bi are not exactly equal but very slowly
increasing with i (see Figure 1).

Proof. We construct a network in which groups of the
n inputs are recursively multiplied. The n inputs are
first divided into groups of size b1 , and each group is
multiplied in the first hidden layer using 2b1 neurons (as
described in [15]). Thus, the first hidden layer includes
a total of 2b1 n/b1 neurons. This gives us n/b1 values to
multiply, which are in turn divided into groups of size
b2 . Each group is multiplied in the second hidden layer
using 2b2 neurons. Thus, the second hidden layer includes
a total of 2b2 n/(b1 b2 ) neurons.
We continue in this fashion for b1 , b2 , . . . , bk such that
b1 b2 · · · bk = n, giving us one neuron which is the product
of all of our inputs. By considering the total number of
neurons used, we conclude

mk (p, σ) ≤

k
X
i=1

n
Qi

j=1 bj

2bi =

k
X



k
Y


i=1


bj  2bi . (10)

j=i+1

FIG. 1: The optimal settings for {bi }ki=1 as n varies are shown
for k = 1, 2, 3. Observe that the bi converge to n1/k for large
n, as witnessed by a linear fit in the log-log plot. The exact
values are given by equations (12) and (13).

Setting bi = n1/k , for each i, gives us the desired bound
(9).
The following conjecture states that the bound given in
Theorem III.1 is (approximately) optimal.
In fact, we can solve for the choice of bi such that the
upper bound in (10) is minimized, under the condition
b1 b2 · · · bk = n. Using the technique of Lagrange multipliers, we know that the optimum occurs at a minimum
of the function

L(bi , λ) :=

n−

k
Y
i=1

!
bi

λ+

k
X



k
Y


i=1

Conjecture III.2. For p(x) equal to the product
x1 x2 · · · xn , and for any σ with all nonzero Taylor coefficients, we have
mk (p, σ) = 2Θ(n

1/k

)

,

(14)


bj  2bi .

j=i+1

Differentiating L with respect to bi , we obtain the con-

i.e., the exponent grows as n1/k as n → ∞.
We empirically tested Conjecture III.2 by training ANNs
to predict the product of input values x1 , . . . , xn with

7
n = 20 (see Figure 2). The rapid interpolation from
exponential to linear width aligns with our predictions.
In our experiments, we used feedforward networks with
dense connections between successive layers, with nonlinearities instantiated as the hyperbolic tangent function.
Similar results were also obtained for rectified linear units
(ReLUs) as the nonlinearity, despite the fact that this
function does not satisfy our hypothesis of being everywhere differentiable. The number of layers was varied,
as was the number of neurons within a single layer. The
networks were trained using the AdaDelta optimizer [18]
to minimize the absolute value of the difference between
the predicted and actual values. Input variables xi were
drawn uniformly at random from the interval [0, 2], so
that the expected value of the output would be of manageable size.

B.

Circuit complexity

It is interesting to consider how our results on the inapproximability of simple polynomials by polynomial-size
neural networks compare to results for Boolean circuits.
Recall that T C 0 is defined as the set of problems that
can be solved by a Boolean circuit of constant depth and
polynomial size, where the circuit is allowed to use AND,
OR, NOT, and MAJORITY gates of arbitrary fan-in.2 It is
an open problem whether T C 0 equals the class T C 1 of
problems solvable by circuits for which the depth is logarithmic in the size of the input.
In this section, we consider the feasibility of strong general no-flattening results. It would be very interesting if
one could show that general polynomials p in n variables
require a superpolynomial number of neurons to approximate for any constant number of hidden layers. That
is, for each integer k ≥ 1, we would like to prove a lower
bound on mk (p, σ) that grows fast than polynomially in
n.
Such a result might seem to address questions such as
whether T C 0 and T C 1 are equal. However, Boolean circuits compute using 0/1 values, while the neurons of our
artificial neural networks take on arbitrary real values.
To preserve 0/1 values at all neurons, we can restrict inputs to such values and take the nonlinear activation to
be the Heaviside step function:
(
σ(x) =

0
1

if x ≤ 0
if x > 0.

This gives us essentially a multi-layered perceptron, as
inspired by McCulloch and Pitts [19].

FIG. 2: Performance of trained networks in approximating
the product of 20 input variables, ranging from red (high
mean error) to blue (low mean error). The curve w =
1/k
n(k−1)/k · 2n
for n = 20 is shown in black. In the region
above and to the right of the curve, it is possible to effectively
approximate the product function (Theorem III.1).

Eq. (14) provides a helpful rule of thumb for how deep is
deep enough. Suppose, for instance, that we wish to keep
typical layers no wider than about a thousand (∼ 210 )
neurons. Eq. (14) then implies n1/k <
∼ 10, i.e., that the
number of layers should be at least
k>
∼ log10 n.

We assume also that each neuron has access to a
fixed bias constant: that is, a neuron receiving inputs
x1 , x2 , . . . , xn is of the form σ(a0 + a1 x1 + a2 x2 + · · · +
an xn ) where a0 , a1 , a2 , . . . , an are real constants. Such
a neuron corresponds to a weighted threshold gate in
Boolean circuits.
It follows from the work of [20] and [21] that such artificial
neural nets (ANNs), with constant depth and polynomial
size, have exactly the same power as T C 0 circuits. That
is, weighted threshold gates can simulate and be simulated by constant-depth, polynomial-size circuits of AND,
OR, NOT, and MAJORITY gates. The following are simple
constructions for these four types of gates using weighted

2

An AND gate evaluates True if all its inputs do so, an OR gate
evaluates True if any of its inputs do so, a NOT gate evaluates
True if its input is False and vice versa, and a MAJORITY gate
evaluates True if at least half of its inputs do so.

8
thresholds.
n
X

!


1
xi − n −
2
i=1
!
n
X
1
OR(x1 , x2 , . . . , xn ) = σ
xi −
2
i=1


1
NOT(x) = σ
−x
2
!
n
X
n−1
MAJORITY(x1 , x2 , . . . , xn ) = σ
xi −
2
i=1
AND(x1 , x2 , . . . , xn ) = σ

Thus, we should not hope easily to prove general noflattening results for Boolean functions, but the case
of polynomials in real-valued variables may be more
tractable. Simply approximating a real value by a
Boolean circuit requires arbitrarily many bits. Therefore,
performing direct computations on real values is clearly
intractable for T C 0 circuits. Moreover, related work such
as [4, 8, 13] has already proven gaps in expressivity for
real-valued neural networks of different depths, for which
the analogous results remain unknown in Boolean circuits.

IV.

CONCLUSION

We have shown how the power of deeper ANNs can be
quantified even for simple polynomials. We have proven
that there is an exponential gap between the width of
shallow and deep networks required for approximating
a given sparse polynomial. For n variables, a shallow
network requires size exponential in n, while a deep network requires at most linearly many neurons. Networks
with a constant number k > 1 of hidden layers appear
to interpolate between these extremes, following a curve
exponential in n1/k . This suggests a rough heuristic for
the number of layers required for approximating simple
functions with neural networks. For example, if we want
no layers to have more than 103 neurons, say, then the
minimum number of layers required grows only as log10 n.

of convolutional neural nets. That is, each neuron in a
layer is assumed to be connected only to a small subset of
neurons from the previous layer, rather than the entirety
of them (or some large fraction). In fact, we showed
(e.g. Prop. II.6) that there exist natural functions that
can be computed in a linear number of neurons, where
each neuron is connected to at most two neurons in the
preceding layer, which nonetheless cannot be computed
with fewer than exponentially many neurons in a single
layer, no matter how may connections are used. Our
construction can also easily be framed with reference to
the other properties mentioned in [13]: those of sharing
(in which weights are shared between neural connections)
and pooling (in which layers are gradually collapsed, as
our construction essentially does with recursive combination of inputs).
This paper has focused exclusively on the resources (notably neurons and synapses) required to compute a given
function. An important complementary challenge is to
quantify the resources (e.g. training steps) required to
learn the computation, i.e., to converge to appropriate
weights using training data — possibly a fixed amount
thereof, as suggested in [22]. There are simple functions
that can be computed with polynomial resources but require exponential resources to learn [23]. It is quite possible that architectures we have not considered increase
the feasibility of learning. For example, residual networks
(ResNets) [24] and unitary nets (see e.g. [25, 26]) are no
more powerful in representational ability than conventional networks of the same size, but by being less susceptible to the “vanishing/exploding gradient” problem,
it is far easier to optimize them in practice. We look
forward to future work that will help us understand the
power of neural networks to learn.

V.

ACKNOWLEDGMENTS

It is worth noting that our constructions enjoy the property of locality mentioned in [13], which is also a feature

This work was supported by the Foundational Questions
Institute http://fqxi.org/, the Rothberg Family Fund for
Cognitive Science and NSF grant 1122374. We thank
Scott Aaronson, Surya Ganguli, David Budden, and
Henry Lin for helpful discussions and suggestions.

[1] G. Cybenko, Mathematics of Control, Signals, and Systems (MCSS) 2, 303 (1989).
[2] K. Hornik, M. Stinchcombe, and H. White, Neural networks 2, 359 (1989).
[3] K.-I. Funahashi, Neural networks 2, 183 (1989).
[4] G. F. Montufar, R. Pascanu, K. Cho, and Y. Bengio,
in Advances in Neural Information Processing Systems
(NIPS) (2014), pp. 2924–2932.
[5] M. Bianchini and F. Scarselli, IEEE transactions on neu-

ral networks and learning systems 25, 1553 (2014).
[6] B. Poole, S. Lahiri, M. Raghu, J. Sohl-Dickstein, and
S. Ganguli, in Advances In Neural Information Processing Systems (NIPS) (2016), pp. 3360–3368.
[7] M. Raghu, B. Poole, J. Kleinberg, S. Ganguli,
and J. Sohl-Dickstein, arXiv preprint arXiv:1611.08083
(2016).
[8] M. Telgarsky, Journal of Machine Learning Research
(JMLR) 49 (2016).

9
[9] R. Eldan and O. Shamir, in 29th Annual Conference on
Learning Theory (2016), pp. 907–940.
[10] H. Mhaskar, Q. Liao, and T. Poggio, arXiv preprint
arXiv:1603.00988v4 (2016).
[11] O. Delalleau and Y. Bengio, in Advances in Neural Information Processing Systems (NIPS) (2011), pp. 666–674.
[12] J. Martens, A. Chattopadhya, T. Pitassi, and R. Zemel,
in Advances in Neural Information Processing Systems
(NIPS) (2013), pp. 2877–2885.
[13] N. Cohen, O. Sharir, and A. Shashua, Journal of Machine
Learning Research (JMLR) 49 (2016).
[14] N. Cohen and A. Shashua, in International Conference
on Machine Learning (ICML) (2016).
[15] H. W. Lin, M. Tegmark, and D. Rolnick, arXiv preprint
arXiv:1608.08225v3 (2016).
[16] P. Comon, G. Golub, L.-H. Lim, and B. Mourrain, SIAM
Journal on Matrix Analysis and Applications 30, 1254
(2008).
[17] J. Alexander and A. Hirschowitz, Journal of Algebraic
Geometry 4, 201 (1995).
[18] M. D. Zeiler, arXiv preprint arXiv:1212.5701 (2012).

[19] W. S. McCulloch and W. Pitts, The bulletin of mathematical biophysics 5, 115 (1943).
[20] A. K. Chandra, L. Stockmeyer, and U. Vishkin, SIAM
Journal on Computing 13, 423 (1984).
[21] N. Pippenger, IBM journal of research and development
31, 235 (1987).
[22] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals,
in Proceedings of the International Conference on Learning Representations (ICLR) (2017).
[23] S. Shalev-Shwartz, O. Shamir, and S. Shammah, arXiv
preprint arXiv:1703.07950 (2017).
[24] K. He, X. Zhang, S. Ren, and J. Sun, in Proceedings of
the IEEE Conference on Computer Vision and Pattern
Recognition (2016), pp. 770–778.
[25] M. Arjovsky, A. Shah, and Y. Bengio, in International
Conference on Machine Learning (2016), pp. 1120–1128.
[26] L. Jing, Y. Shen, T. Dubček, J. Peurifoy, S. Skirlo,
M. Tegmark, and M. Soljačić, arXiv preprint
arXiv:1612.05231 (2016).

