Learning Functions: When Is Deep Better Than Shallow

Introduction

There are two main theory questions about Deep Neural Networks. The first question is about the power of the architecture – which classes of functions can it approximate well? The second question is about learning the unknown coefficients from the data: why is SGD so unreasonably efficient, at least in appearance? Are good minima easier to find in deep rather than in shallow networks? In this paper we describe a set of approximation theory results that include answers to why and when deep networks are better than shallow by using the idealized model of a deep network as a binary tree. In a separate paper, we show that the binary tree model with its associated results can indeed be extended formally to the very deep convolutional networks of the ResNet type which have only a few stages of pooling and subsampling.

This paper compares shallow (one-hidden layer) networks with deep networks (see for example Figure 1). Both types of networks use the same small set of operations – dot products, linear combinations, a fixed nonlinear function of one variable, possibly convolution and pooling. The logic of the paper is as follows.

Both shallow (a) and deep (b) networks are universal, that is they can approximate arbitrarily well any continuous function of $d$ variables on a compact domain.

We show that the approximation of functions with a compositional structure – such as $f(x_{1},\cdots,x_{d})=h_{1}(h_{2}\cdots(h_{j}(h_{i1}(x_{1},x_{2}),h_{i2}(x_{3},x_{4})),\cdots))$ – can be achieved with the same degree of accuracy by deep and shallow networks but that the number of parameters, the VC-dimension and the fat-shattering dimension are much smaller for the deep networks than for the shallow network with equivalent approximation accuracy. It is intuitive that a hierarchical network matching the structure of a compositional function should be “better” at approximating it than a generic shallow network but universality of shallow networks makes the statement less than obvious. Our result makes clear that the intuition is indeed correct and provides quantitative bounds.

Why are compositional functions important? We argue that the basic properties of scalability and shift invariance in many natural signals such as images and text require compositional algorithms that can be well approximated by Deep Convolutional Networks. Of course, there are many situations that do not require shift invariant, scalable algorithms. For the many functions that are not compositional we do not expect any advantage of deep convolutional networks.

Previous work

The success of Deep Learning in the present landscape of machine learning poses again an old theory question: why are multi-layer networks better than one-hidden-layer networks? Under which conditions? The question is relevant in several related fields from machine learning to function approximation and has appeared many times before.

Most Deep Learning references these days start with Hinton’s backpropagation and with Lecun’s convolutional networks (see for a nice review [LeCun et al., 2015]). Of course, multilayer convolutional networks have been around at least as far back as the optical processing era of the 70s. The Neocognitron ([Fukushima, 1980]) was a convolutional neural network that was trained to recognize characters. The HMAX model of visual cortex ([Riesenhuber and Poggio, 1999a]) was described as a series of AND and OR layers to represent hierarchies of disjunctions of conjunctions. There are several recent papers addressing the question of why hierarchies. Sum-Product networks, which are equivalent to polynomial networks (see [B. Moore and Poggio, 1998, Livni et al., 2013]), are a simple case of a hierarchy that can be analyzed ([Delalleau and Bengio, 2011]). [Montufar et al., 2014] provided an estimation of the number of linear regions that a network with ReLU nonlinearities can synthesize in principle but leaves open the question of whether they can be used for learning. Examples of functions that cannot be represented efficiently by shallow networks have been given very recently by [Telgarsky, 2015]. Most relevant to this paper is the work on hierarchical quadratic networks ([Livni et al., 2013]), together with function approximation results ([Pinkus, 1999, Mhaskar, 1993]).

Compositional functions

We assume that the shallow networks do not have any structural information on the function to be learned (here its compositional structure), because they cannot represent it directly. Deep networks with standard architectures on the other hand do represent compositionality and can be adapted to the details of such prior information. Thus, it is natural to conjecture that hierarchical compositions of functions such as

are approximated more efficiently by deep than by shallow networks.

In addition, both shallow and deep representations may or may not reflect invariance to group transformations of the inputs of the function ( [Soatto, 2011, Anselmi et al., 2015]). Invariance is expected to decrease the complexity of the network, for instance its VC-dimension. Since we are interested in the comparison of shallow vs deep architectures, here we consider the generic case of networks (and functions) for which invariance is not assumed.

We approximate functions of $d$ variables of the form of Equation (1) with networks in which the activation nonlinearity is a smoothened version of the so called ReLU, originally called ramp by Breiman and given by $\sigma(x)=x_{+}=max(0,x)$ . The architecture of the deep networks reflects Equation (1) with each node $h_{i}$ being a ridge function.

It is important to emphasize here that the properties of state-of-art Deep Learning Neural Networks (DLNNs) of the ResNet type ([He et al., 2015]), with their small kernel size and many layers, are well represented by our results on binary tree architectures, as we show formally elsewhere. Visual cortex has a similar compositional architecture with receptive fields becoming larger and larger in higher and higher visual areas, with each area corresponding to a recurrent layer in a deep neural network ([Liao and Poggio, 2016]).

Main results

For the hierarchical binary tree network, the analogous spaces are defined by considering the compact set $W_{H,r,2}^{\mbox{NN}}$ to be the class of all functions $f$ which have the same structure (e.g., (1)), where each of the constituent functions $h$ is in $W_{r,2}^{\mbox{NN}}$ (applied with only $2$ variables). We define the corresponding class of deep networks $\mathcal{D}_{n}$ to be set of all functions with the same structure, where each of the constituent functions is in $\mathcal{S}_{n}$. We note that in the case when $d$ is an integer power of $2$, the number of parameters involved in an element of $\mathcal{D}_{n}$ – that is, weights and biases, in a node of the binary tree is $(d-1)(d+2)n$.

The following theorem estimates the degree of approximation for shallow and deep networks. We remark that the assumptions on $\sigma$ in the theorem below are not satisfied by the ReLU function $x\mapsto x_{+}$, but they are satisfied by smoothing the function in an arbitrarily small interval around the origin.

Proof. Theorem 1(a) was proved by [Mhaskar, 1996]. To prove Theorem 1(b), we observe that each of the constituent functions being in $W_{r,2}^{\mbox{NN}}$, (3) applied with $d=2$ implies that each of these functions can be approximated from $\mathcal{S}_{n}$ up to accuracy $n^{-r/2}$. Our assumption that $f\in W_{H,r,2}^{\mbox{NN}}$ implies that each of these constituent functions is Lipschitz continuous. Hence, it is easy to deduce that, for example, if $P$, $P_{1}$, $P_{2}$ are approximations to the constituent functions $h$, $h_{1}$, $h_{2}$, respectively within an accuracy of $\epsilon$, then

for some constant $c>0$ independent of the functions involved. This leads to (4). $\square$

The constants involved in $\mathcal{O}$ in (3) will depend upon the norms of the derivatives of $f$ as well as $\sigma$. Thus, when the only a priori assumption on the target function is about the number of derivatives, then to guarantee an accuracy of $\epsilon$, we need a shallow network with $\mathcal{O}(\epsilon^{-d/r})$ trainable parameters. If we assume a hierarchical structure on the target function as in Theorem 1, then the corresponding deep network yields a guaranteed accuracy of $\epsilon$ only with $\mathcal{O}(\epsilon^{-2/r})$ trainable parameters.

and the curse for $W_{r,d}^{\mbox{NN}}$ by

We note that the curse depends only on the compact set $W_{r,d}^{\mbox{NN}}$, and represents the best that can be achieved by any continuous parameter selection and recovery processes. It is shown by [DeVore et al., 1989] that $\mathsf{curse}(W_{r,d}^{\mbox{NN}},\epsilon)\geq c\epsilon^{-d/r}$ for some constant $c>0$ depending only on $d$ and $r$. So, the estimate implied by (3) is the best possible among all reasonable methods of approximating arbitrary functions in $W_{r,d}^{\mbox{NN}}$, although by itself, the estimate (3) is blind to the process by which the approximation is accomplished; in particular, this process is not required to be robust. Similar considerations apply to the estimate (4), and we will explain the details in Section 4.2 in a different context.

The lower bound on the $n$–width implies only that there is some function in $W_{r,d}^{\mbox{NN}}$ for which the approximation cannot be better than that suggested by (3). This begs the question whether this function could be unreasonably pathological, and for most functions arising in practice, clever ideas can lead to a substantially better accuracy of approximation, its smoothness notwithstanding. At this time, we are not able to address this question in the context of neural networks as in Theorem 1, but we are able to do so if each unit evaluates a Gaussian network. Accordingly, we now turn to our new results in this direction. The proofs will be published separately.

2 Deep and shallow Gaussian networks

We wish to consider shallow networks where each channel evaluates a Gaussian non–linearity; i.e., Gaussian networks of the form

Since one of our goals is to show that our results on the upper bounds for the accuracy of approximation are the best possible for individual functions, the class $W_{r,d}$ needs to be refined somewhat. Toward that goal, we define next a regularization expression, known in approximation theory parlance as a $K$–functional, by

There exists a constant $c>0$ depending on $d$ alone with the following property. Let $\{\mathcal{C}_{m}\}$ be a sequence of finite subsets with $\mathcal{C}_{m}\subset[-cm,cm]^{d}$, with

If $\gamma>0$ and $f\in\mathcal{W}_{\gamma,d}$, then for integer $m\geq 1$, there exists $G\in\mathcal{N}_{|\mathcal{C}_{m}|,m}$ with centers at points in $\mathcal{C}_{m}$ such that

Moreover, the coefficients of $G$ can be chosen as linear combinations of the data $\{f(\mathbf{x}):\mathbf{x}\in\mathcal{C}_{m}\}$.

We note that the set of centers $\mathcal{C}_{m}$ can be chosen arbitrarily subject to the conditions stated in the theorem; there is no training necessary to determine these parameters. Therefore, there are only $\mathcal{O}(m^{2})$ coefficients to be found by training. This means that if we assume a priori that $f\in\mathcal{W}_{\gamma,d}$, then the number of trainable parameters to theoretically guarantee an accuracy of $\epsilon>0$ is $\mathcal{O}(\epsilon^{-2d/\gamma})$. We will comment on the optimality of this estimate later.

The analogue of Theorem 2 is the following.

Moreover, the coefficients of each constituent $G_{v}$ can be chosen as linear combinations of the data $\{f(\mathbf{x}):\mathbf{x}\in\mathcal{C}_{m,v}\}$.

Clearly, Theorem 3 is applicable only for those target functions which have the hierarchical structure prescribed by the binary tree. It is not difficult to generalize the theorem to the case when the structure confirms rather to a more general directed acyclic graph, but for simplicity, we will continue to assume the binary tree structure in this section. Therefore, Theorem 3 can be compared with Theorem 2 only in the following sense. A target function $f$ satisfying the tree structure can also be thought of as a shallow function of $L$ arguments, where $L$ is the number of leaves of the binary tree (the input variables). Then the set $V$ contains $\leq L$ elements as well. If $f$ satisfies the smoothness conditions in both the theorems, and an accuracy of $\epsilon>0$ is required, then a shallow network requires $\mathcal{O}(\epsilon^{-2L/\gamma})$ trainable parameters, while the deep network requires only $\mathcal{O}(L\epsilon^{-4/\gamma})$ trainable parameters.

How good are these results for individual functions? If we know that some oracle can give us Gaussian networks that achieve a given accuracy with a given complexity, does it necessarily imply that the target function is smooth as indicated by the above theorems? It is in this context that we need to measure the complexity in terms of minimal separation among the centers; such a result will then hold even if we allow the oracle to chose a very large number of channels. The following is a converse to Theorems 2 and 3, demonstrating that the accuracy asserted by these theorems is possible if and only if the target function is in the smoothness class required in these theorems.

Then $f\in\mathcal{T}\mathcal{W}_{\gamma,2}$.

3 VC bounds

A direct connection between regression and binary classification is provided by the following observation (due to [Livni et al., 2013]): Theorems 11.13 and 14.1 from [Anthony and Bartlett, 2002] show that the fat-shattering dimension is upper-bounded by the VC-dimension of a slightly larger class of networks, which has a similar VC-dimension to the original class, hence the fat-shattering dimension can also be bounded. The following theorem can be deduced from the results in Section 4 and a well known result ([Anthony and Bartlett, 2002], [Mhaskar et al., 2016]):

The VC-dimension of the shallow network with $N$ units is bounded by $(d+2)N^{2}$; the VC-dimension of the binary tree network with $n(d-1)$ units is bounded by $4n^{2}(d-1)^{2}$.

A general framework for hierarchical, compositional computations

There are many phenomena in nature that have descriptions along a range of rather different scales. An extreme case consists of fractals which are infinitely self-similar, iterated mathematical constructs. As a reminder, a self-similar object is similar to a part of itself (i.e. the whole is similar to one or more of the parts). Many objects in the real world are statistically self-similar, showing the same statistical properties at many scales: clouds, river networks, snow flakes, crystals and neurons branching. A relevant point is that the shift-invariant scalability of image statistics follows from the fact that objects contain smaller clusters of similar surfaces in a selfsimilar fractal way. [Ruderman, 1997] analysis shows that image statistics reflects the property of compositionality of objects and parts: parts are themselves objects, that is selfsimilar clusters of similar surfaces in the physical world. The closely related property of compositionality was a main motivation for hierarchical models of visual cortex such as HMAX which can be regarded as a pyramid of AND and OR layers ([Riesenhuber and Poggio, 1999b]), that is a sequence of conjunctions and disjunctions.

The final step in the argument uses the results of previous sections to claim that a nonlinear node with two inputs and enough units (that is, channels) can approximate arbitrarily well each of the $H_{2}$ blocks. This leads to conclude that deep convolutional neural networks are natural approximators of scalable, shift-invariant operators.

Discussion

Implicit in the results in Section 4.1 is the fact that a hierarchical network can approximate a high degree polynomial $P$ in the input variables $x_{1},\cdots,x_{d}$, that can be written as a hierarchical composition of lower degree polynomials. For example, let

Since $Q$ is nominally a polynomial of coordinatewise degree $2^{11}$, [Mhaskar, 1996, Lemma 3.2] shows that a shallow network with $2^{11}+1$ units is able to approximate $Q$ arbitrarily well on $I^{d}$. However, because of the hierarchical structure of $Q$, [Mhaskar, 1996, Lemma 3.2] shows also that a hierarchical network with $9$ units can approximate the quadratic expression, and $10$ further layers, each with $3$ units can approximate the successive powers. Thus, a hierarchical network with $11$ layers and $39$ units can approximate $Q$ arbitrarily well. We note that even if $Q$ is nominally of degree $2^{11}$, each of the monomial coefficients in $Q$ is a function of only $9$ variables, $A,\cdots,I$. A similar, simpler example was tested using standard DLNN software and is shown in Figure 3.

These arguments suggest that the proof of Theorem 1 can be used to show (see [Mhaskar et al., 2016]) that functions approximated well by sparse polynomials can be learned efficiently by deep networks with a tree or graph structure that matches the polynomial. We recall that in a similar way several properties of certain Boolean functions can be “read out” from the terms of their Fourier expansion corresponding to “large” coefficients, that is from a polynomial that approximates well the function (see [Poggio et al., 2015]). In this sense our Theorem 1 should cover recently described functions that cannot be represented efficiently by shallow networks (see [Telgarsky, 2015]).

Classical results ([Hastad, 1987]) about the depth-breadth tradeoff in circuits design show that deep circuits are more efficient in representing certain Boolean functions than shallow circuits. These results have been often quoted in support of the claim that deep neural networks can represent functions that shallow networks cannot. For instance [Bengio and LeCun, 2007] write “We claim that most functions that can be represented compactly by deep architectures cannot be represented by a compact shallow architecture”. The results of this paper (see Supplementary Material and [Mhaskar et al., 2016]) should settle the issue, justifying the original conjecture and providing an approach connecting results on Boolean functions with current real valued neural networks.

References

Appendix A Boolean functions

Our results sketched in the previous section are interesting not only in themselves but also because they suggest several connections to similar properties of Boolean functions. In fact our results seem to generalize properties already known for Boolean functions which are of course a special case of functions of real variables. We first recall some definitions followed by a few observations.

One of the most important and versatile tools for theoretical computer scientists for the study of functions of $n$ Boolean variables, their related circuit design and several associated learning problems, is the Fourier transform over the Abelian group $\mathcal{Z}^{n}_{2}$ . This is known as Fourier analysis over the Boolean cube $\{-1,1\}^{n}$. The Fourier expansion of a Boolean function $f:\{-1,1\}^{n}\to\{-1,1\}$ or even a real-valued Boolean function $f:\{-1,1\}^{n}\to$ is its representation as a real polynomial, which is multilinear because of the Boolean nature of its variables. Thus for Boolean functions their Fourier representation is identical to their polynomial representation. In the following we will use the two terms interchangeably. Unlike functions of real variables, the full finite Fourier expansion is exact instead of an approximation and there is no need to distingush between trigonometric and real polynomials. Most of the properties of standard harmonic analysis are otherwise preserved, including Parseval theorem. The terms in the expansion correspond to the various monomials; the low order ones are parity functions over small subsets of the variables and correspond to low degrees and low frequencies in the case of polynomial and Fourier approximations, respectively, for functions of real variables.

The section in the main text referring to sparse functions suggests the following approach to characterize which functions are best learned by which type of network – for instance shallow or deep. The structure of the network is reflected in polynomials that are best approximated by it – for instance generic polynomials or sparse polynomials (in the coefficients) in $d$ variables of order $k$. The tree structure of the nodes of a deep network reflects the structure of a specific sparse polynomial. Generic polynomial of degree $k$ in $d$ variables are difficult to learn because the number of terms, trainable parameters and associated VC-dimension are all exponential in $d$. On the other hand, functions approximated well by sparse polynomials can be learned efficiently by deep networks with a tree structure that matches the polynomial. We recall that in a similar way several properties of certain Boolean functions can be “read out” from the terms of their Fourier expansion corresponding to “large” coefficients, that is from a polynomial that approximates well the function.

Classical results [Hastad, 1987] about the depth-breadth tradeoff in circuits design show that deep circuits are more efficient in representing certain Boolean functions than shallow circuits. Hastad proved that highly-variable functions (in the sense of having high frequencies in their Fourier spectrum) in particular the parity function cannot even be decently approximated by small constant depth circuits (see also [Linial et al., 1993]). These results on Boolean functions have been often quoted in support of the claim that deep neural networks can represent functions that shallow networks cannot. For instance Bengio and LeCun [Bengio and LeCun, 2007] write “We claim that most functions that can be represented compactly by deep architectures cannot be represented by a compact shallow architecture”.”. It seems that the results summarized in this paper provide a general approach connecting results on Boolean functions with current real valued neural networks. Of course, we do not imply that the capacity of deep networks is exponentially larger than the capacity of shallow networks. As pointed out by Shalev-Shwartz, this is clearly not true, since the VC dimension of a network depends on the number of nodes and parameters and not on the depth. We remark that a nice theorem was recently published [Telgarsky, 2015], showing that a certain family of classification problems with real-valued inputs cannot be approximated well by shallow networks with fewer than exponentially many nodes whereas a deep network achieves zero error. This is a special case of our results and corresponds to high-frequency, sparse trigonometric polynomials.

Finally, we want to speculate about a series of observations on Boolean functions that may show an interesting use of our approach using the approximating polynomials and networks for studying the learning of general functions. It is known that within Boolean functions the $AC^{0}$ class of polynomial size constant depth circuits is characterized by Fourier transforms where most of the power spectrum is in the low order coefficients. Such functions can be approximated well by a polynomial of low degree and can be learned well by considering only such coefficients. In general, two algorithms [Mansour, 1994] seems to allow learning of certain Boolean function classes:

the low order algorithm that approximates functions by considering their low order Fourier coefficients and

the sparse algorithm which learns a function by approximating its significant coefficients.

Decision lists and decision trees can be learned by algorithm 1. Functions with small $L_{1}$ norm can be approximated well by algorithm 2. Boolean circuits expressing DNFs can be approximated by 1 but even better by 2. In fact, in many cases most of the coefficients of the low terms may still be negligeable and furthermore it may the case that a function can be approximated by a small set of coefficients but these coefficients do not correspond to low-order terms. All these cases are consistent with the description we have in section on sparse functions. For general functions they may suggest the following. Many functions can be learned efficiently in terms of their low order coefficients and thus by shallow networks. This corresponds to using Tikhonov regularization that effectively cuts out high frequencies. Other functions must be learned in terms of their sparse coefficients by a deep network with an appropriate architecture. This is more similar to $L_{1}$ regularization. The sparsity approach which corresponds to deep networks includes the shallow Tikhonov approach and thus is more general and preferrable at least as long as computational and sample complexity issues are not taken into account.