Abstract

Let $f:{\mathbb{S}}^{d-1}\times{\mathbb{S}}^{d-1}\to{\mathbb{R}}$ be a function of the form $f({\mathbf{x}},{\mathbf{x}}^{\prime})=g(\langle{\mathbf{x}},{\mathbf{x}}^{\prime}\rangle)$ for $g:[-1,1]\to{\mathbb{R}}$ . 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(\pi d^{3}x)$ , the number of neurons must be $2^{\Omega\left(d\log(d)\right)}$ . Furthermore, the result holds w.r.t. the uniform distribution on ${\mathbb{S}}^{d-1}\times{\mathbb{S}}^{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 ${\mathbb{S}}^{d-1}\times{\mathbb{S}}^{d-1}$ .