Depth Separation for Neural Networks
Amit Daniely Google Brain
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}$ .
中文速览
判断一个两层神经网络（depth-2 network）是否能逼近定义在高维球面上的内积函数（inner product function）是神经网络表达能力研究中的核心问题，而已有工作要么证明方法复杂、要么仅针对特殊分布。本文利用球面上的基本调和分析（harmonic analysis），给出了一个简洁的证明：只要目标函数 g 无法被低次多项式很好地逼近，多项式宽度的两层网络（即便允许指数级大的权重）就无法在球面均匀分布下逼近对应的内积函数；对于像 g(x)=sin(πd³x) 这样的函数，所需神经元数量至少是 2^Ω(d log d)，比前人指数级下界更强。与此同时，论文证明三层网络（depth-3 network）只需多项式宽度和多项式有界权重就能高精度逼近同一类函数，从而在自然的均匀球面分布下严格建立了两层与三层网络之间的表达能力分离，为理解网络深度的本质作用提供了清晰而初等的理论依据。
原文 arXiv:1702.08489;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1702.08489v1