Depth Separation for Neural Networks
Amit Daniely

Understanding Convolution for Semantic Segmentation
    [
    December 30, 2023
===================================================



Understanding Convolution for Semantic Segmentation
    [
    December 30, 2023
===================================================




Let f:^d-1×^d-1→ be a function of the form f(,') = g(,') for g:[-1,1]→. We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate f whenever g cannot be approximated by a low degree polynomial. Moreover, for many g's, such as g(x)=sin(π d^3x), the number of neurons must be 2^Ω(dlog(d)). Furthermore, the result holds w.r.t. the uniform distribution on ^d-1×^d-1.
As many functions of the above form can be well approximated by poly-size depth three networks with poly-bounded weights, this establishes a separation between depth two and depth three networks w.r.t. the uniform distribution on ^d-1×^d-1.





§ INTRODUCTION AND MAIN RESULT


Many aspects of the expressive power of neural networks has been studied over the years. In particular, separation for deep networks <cit.>, expressive power of depth two networks <cit.>, and more <cit.>.
We focus on the basic setting of depth 2 versus depth 3 networks. We ask what functions are expressible (or well approximated) by poly-sized depth-3 networks, but cannot be approximated by an exponential size depth-2 network. 

Two recent papers <cit.> addressed this issue. Both papers presented a specific function f:^d→ and a distribution  on ^d such that f can be approximated w.r.t.  by a (d)-size depth 3 network, but not by a (d)-size depth 2 network. In <cit.> this was shown for f being the inner product mod 2 and  being the uniform distribution on {0,1}^d×{0,1}^d. In <cit.> it was shown for a different (radial) function and some (unbounded) distribution.

We extend the above results and prove a similar result for an explicit and rich family of functions, and w.r.t. the uniform distribution on ^d-1×^d-1. In addition, our lower bound on the number of required neurons is stronger: while previous papers showed that the number of neurons has to be exponential in d, we show exponential dependency on dlog(d). Last, our proof is short, direct and is based only on basic Harmonic analysis over the sphere. In contrast, <cit.>'s proof is rather lengthy and requires advanced technical tools such as tempered distributions, while <cit.> relied on the discrepancy of the inner product function mod 2. On the other hand, <cit.> do not put any restriction on the magnitude of the weights, while we and <cit.> do require a mild (exponential) bound.  


Let us fix an activation function σ:→. For ∈^n we denote σ() = (σ(x_1),…,σ(x_n)).
We say that F:^d-1×^d-1→ can be implemented by a depth-2 σ-network of width r and weights bounded by B if

    F(,') = w^T_2σ(W_1 + W'_1' + b_1)+b_2 ,

where W_1,W'_1∈ [-B,B]^r× d, w_2∈ [-B,B]^r, b_1∈ [-B,B]^r and b_2∈ [-B,B].
Similarly, F:^d-1×^d-1→ can be implemented by a depth-3 σ-network of width r and weights bounded by B if

    F(,') = w^T_3σ(W_2σ(W_1 + W'_1' + b_1)+b_2) + b_3

for W_1,W'_1∈ [-B,B]^r× d, W_2∈ [-B,B]^r× r, w_3∈ [-B,B]^r, b_1, b_2∈ [-B,B]^r and b_3∈ [-B,B].
Denote

    N_d,n=d+n-1d-1-d+n-3d-1=(2n+d-2)(n+d-3)!/n!(d-2)! .

Let μ_d be the probability measure on [-1,1] given by dμ_d(x) = Γ(d/2)/√(π)Γ(d-1/2)(1-x^2)^d-3/2dx and define

    A_n,d(f) = min_p is degree n-1 polynomialf-p_L^2(μ_d)

Our main theorem shows that if A_n,d(f) is large then (,')↦ f(,') cannot be approximated by a small depth-2 network.


Let N:^d-1×^d-1→ be any function implemented by a depth-2 σ-network of width r, with weights bounded by B. Let f:[-1,1]→ and define F:^d-1×^d-1→ by F(,') = f(,').
Then, for all n,

    N - F_L^2(^d-1×^d-1)≥  A_n,d(f)(A_n,d(f) - 2rBmax_|x|≤√(4d)B+B|σ(x)|+2B/√(N_d,n))




Let us consider the case that σ(x)=max(0,x) is the ReLU function, f(x) = sin(π d^3x), n=d^2 and B=2^d. In this case, lemma <ref> implies that A_n,d(f) ≥1/5eπ. Hence, to have 1/50e^2π^2-approximation of F, the number of hidden neuorons has to be at least,

    √(N_d,d^2)/20eπ 2^2d(1+√(4d)) + 2^d+1 = 2^Ω(dlog(d))

On the other hand, corollary <ref> implies that F can be ϵ-approximated by a ReLU network of depth 3, width 16π d^5/ϵ and weights bounded by 2π d^3













§ PROOFS

Throughout, we fix a dimension d. All functions f:^d-1→ and f:^d-1×^d-1→ will be assumed to be square integrable w.r.t. the uniform measure. Likewise, functions f:[-1,1]→ and f:[-1,1]× [-1,1]→ will be assumed to be square integrable w.r.t. μ_d or μ_d×μ_d. Norms and inner products of such functions are of the corresponding L^2 spaces. We will use the fact that μ_d is the probability measure on [-1,1] that is obtained by pushing forward the uniform measure on ^d-1 via the function ↦ x_1. We denote by _n:L^2(μ_d)→ L^2(μ_d) the projection on the complement of the space of degree ≤ n-1 polynomials. Note that A_n,d(f)=_n,df_L^2(μ_d).



 §.§ Some Harmonic Analysis on the Sphere

The d dimensional Legendre polynomials are the sequence of polynomials over [-1,1] defined by the recursion formula

    P_n(x)=2n+d-4/n+d-3xP_n-1(x) - n-1/n+d-3P_n-2(x)
        P_0≡ 1, P_1(x)=x

We also define h_n:S^d-1× S^d-1→ by h_n(,') = √(N_d,n)P_n(,'), and for ∈ S^d-1 we denote L^_n(') = h_n(,'). We will make use of the following properties of the Legendre polynomials.


  * For every d≥ 2, the sequence {√(N_d,n)P_n} is orthonormal basis of the Hilbert space L^2(μ_d).

  * For every n, ||P_n||_∞=1 and P_n(1)=1.

  * L_i^,L_j^' = P_i(,')δ_ij. 








 §.§ Main Result

We say that f:^d-1×^d-1→ is an inner product function if it has the form f(,') = ϕ(,') for some function ϕ:[-1,1]→.
Let _d⊂ L^2(^d-1×^d-1) be the space of inner product functions. We note that

    f^2 = __'ϕ^2(,')  =  _ϕ^2 = ϕ^2

Hence, the correspondence ϕ↔ f defines an isomorphism of Hilbert spaces between L^2(μ_d) and _d. In particular, the orthonormal basis {√(N_d,n)P_n}_n=0^∞ is mapped to {h_n}_n=0^∞. In particular,

    _n(∑_i=0^∞α_ih_i ) = ∑_i=n^∞α_ih_i

Let ,'∈^d-1. We say that f:^d-1×^d-1→ is (,')-separable if it has the form f(,') = ψ(,,',') for some ψ:[-1,1]^2→. We note that each neuron implements a separable function. 
Let _,'⊂ L^2(^d-1×^d-1) be the space of (,')-separable functions.
We note that

    f^2 = _,'ψ^2(,, ',')  =  ψ^2

Hence, the correspondence ψ↔ f defines an isomorphism of Hilbert spaces between L^2(μ_d×μ_d) and _,'. In particular, the orthonormal basis {√(N_d,n)P_n ⊗√(N_d,m)P_m}_n,m=0^∞ is mapped to {L_n^⊗ L_n^'}_n,m=0^∞.

The following theorem implies theorem <ref>, as under the conditions of theorem <ref>, any hidden neuron implement a separable function with norm at most Bmax_|x|≤√(4d)B+B|σ(x)|, and the bias term is a separable function with norm at most B.


Let f:^d-1×^d-1→ be an inner product function and let g_1,…,g_r:^d-1×^d-1→ be separable functions. Then

    f-∑_i=1^rg_i^2 ≥_nf(_nf - 2∑_i=1^rg_i/√(N_d,n))


We note that

    _,'h_n(,')L_i^()L_j^'(')    =   _L_i^()_'h_n(,')L_j^'(') 
       =   _L_i^()_'L^_n(')L_j^'(') 
       =   δ_nj_L_i^()P_n(,')
    
       =   δ_nj/√(N_d,n)_L_i^()L_n^'() 
       =   δ_njδ_ni P_n(,') /√(N_d,n)

Suppose now that f = ∑_i=n^∞α_ih_i and suppose that g = ∑^r_j=1 g_j where each g_j depends only on _j,,'_j,' for some _j,'_j∈ S^d-1. 
Write g_j(,')=∑_k,l=0^∞β^j_k,lL^_j_k()L^'_j_k('). By equation (<ref>), L^_j_k()L^'_j_l(') is orthogonal to f whever k l. Hence, if we replace each g_j with ∑_k=0^∞β^j_k,kL^_j_k()L^'_j_k('), the l.h.s. of (<ref>) does not increase. Likewise, the r.h.s. does not decrease.
Hence, we can assume w.l.o.g. that each g_j is of the form g_j(,')=∑_i=0^∞β^j_iL^_j_i()L^'_j_i('). Now, using (<ref>) again, we have that

    f-g^2     =   ∑_i=0^∞α_i h_i - ∑_j=1^r β^j_i  L^_j_i ⊗ L^'_j_i^2
    
       ≥   ∑_i=n^∞α_i h_i - ∑_j=1^r β^j_i  L^_j_i ⊗ L^'_j_i^2
    
       ≥   ∑_i=n^∞α_i^2  - 2∑_i=n^∞∑_j=1^rα_i h_i, β^j_i  L^_j_i ⊗ L^'_j_i
       =   _nf^2-2∑_i=n^∞∑_j=1^r β^j_iα_i  P_i(_j,'_j)/√(N_d,k)
       ≥   _nf^2-2∑^r_j=1∑_i=n^∞|β^j_i| |α_i|/√(N_d,n)
       ≥   _nf^2-2∑^r_j=11/√(N_d,n)√(∑_i=n^∞ |β^j_i|^2)√(∑_i=n^∞ |α_i|^2)
       ≥   _nf^2 - 2_nf∑_j=1^r g_j/√(N_d,n)





 §.§ Approximating the cosine function


Define g_d,m(x) = sin(π√(d)m x). Then, for any d≥ d_0, for a universal constant d_0>0, and for any degree k polynomial p we have

    ∫_-1^1 (g_d,m(x)-p(x))^2dμ_d(x) ≥m-k/4eπ m


We have that (e.g. <cit.>) dμ_d(x) = Γ(d/2)/√(π)Γ(d-1/2)(1-x^2)^d-3/2dx. Likewise, for large enough d and |x|< 1/√(d) we have 1-x^2 ≥ e^-2x^2≥ e^-2/d and hence (1-x^2)^d-3/2≥ e^-d-3/d≥ e^-1.
Likewise, since Γ(d/2)/Γ(d-1/2)∼√(d/2), we have that for large enough d and |x|≤1/√(d), dμ_d(x)≥√(d)/2eπ. Hence, for f≥ 0 we have

    ∫_-1^1 f(x)dμ_d(x) ≥∫_-d^-1/2^d^-1/2 f(x)dμ_d(x) ≥√(d)/2eπ∫_-d^-1/2^d^-1/2f(x)dx = 1/2eπ∫_-1^1f(t/√(d))dt

Applying this equation for f = g_d,m - p we get that

    ∫_-1^1 (g_d,m(x)-p(x))^2dμ_d(x) ≥1/2eπ∫_-1^1 (sin(π m x) - q(x))^2dx

Where q(x):=p(x/√(d)).
Now, in the 2m segments I_i = (-1+i-1/m,-1 + i/m),  i∈ [2m] we have at least m - k segments on which x↦sin(π m x) and q do not change signs and have opposite signs. On each of these intervals we have ∫_I (sin(π m x) - q(x))^2dx ≥∫^1/m_0sin^2(π m x)dx =1/2m.



Let σ(x)=max(x,0) be the ReLU activation, f:[-R,R]→ an L-Lipschitz function, and ϵ>0. There is a function

    g(x) = f(0) + ∑_i=1^m α_iσ(γ_i x-β_i)

for which g-f_∞≤ϵ. Furthermore, m≤2RL/ϵ, |β_i|≤ R, |α_i|≤ 2L, γ_i∈{-1,1}, and g is L-Lipschitz on all . 



Let f:[-1,1]→ [-1,1] be an L-Lipschitz function and let ϵ>0. Define F:^d-1×^d-1→ [-1,1] by F(,') = f(,'). There is a function G:^d-1×^d-1→ [-1,1] that satisfies F-G_∞≤ϵ and furthermore G can be implemented by a depth-3 ReLU network of width 16d^2L/ϵ and weights bounded by max(4,2L)

By Lemma <ref> there is a depth-2 network _square that calculates x^2/2 in [-2,2], with an error of ϵ/2dL and has width at most 16dL/ϵ and hidden layer weights bounded by 2, and prediction layer weights bounded by 4. For each i∈ [d] we can compose the linear function (,')↦ x_i+x'_i with _square to get a depth-2 network _i that calculates (x_i+x'_i)^2/2 with an error of ϵ/2dL and has the same width and weight bound as _square. Summing the networks _i and subtracting 1 results with a depth-2 network _inner that calculates ,' with an error of ϵ/2L and has width 16d^2L/ϵ and hidden layer weights bounded by 2, and prediction layer weights bounded by 4.

Now, again by lemma <ref> there is a depth-2 network _f that calculates f in [-1,1], with an error of ϵ/2, has width at most 2L/ϵ, hidden layer weights bounded by 1 and prediction layer weights bounded by 2L, and is L-Lipschitz. Finally, consider the depth-3 network _F that is the composition of _inner and _f. _F has width at most 16d^2L/ϵ weight bound of max(4,2L), and it satisfies

    |_F(,') - F(,')|    =    |_f(_inner(,')) - f(,')|
    
       ≤    |_f(_inner(,')) - _f(,')| + |_f(,')- f(,')|
    
       ≤    L|_inner(,') -,'| + ϵ/2
       ≤    Lϵ/2L + ϵ/2 = ϵ






