Benefits of depth in neural networks
Abstract
For any positive integer $k$ , there exist neural networks with $\Theta(k^{3})$ layers, $\Theta(1)$ nodes per layer, and $\Theta(1)$ distinct parameters which can not be approximated by networks with $\mathcal{O}(k)$ layers unless they are exponentially large — they must possess $\Omega(2^{k})$ nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: $\Omega(2^{k^{3}})$ total tree nodes are required).
中文速览
深度神经网络与浅层网络之间的表达能力差距究竟有多大，一直是理论研究的核心问题。这项工作证明：对任意正整数 k，存在一类仅用 Θ(k³) 层、每层 Θ(1) 个节点就能表示的函数，任何层数不超过 O(k) 的浅层网络若想逼近它，节点数必须达到指数级别 Ω(2^k)——也就是说，深度可以指数级地压缩网络规模。证明的核心思想是"振荡计数"：多层复合可以用极少的参数构造出高度振荡的函数，而在固定层数下单纯增加节点只能线性地叠加振荡，无法以多项式代价匹配高振荡目标函数。这一结论不局限于标准 ReLU 网络，还覆盖了卷积网络、求和-积网络以及提升决策树（boosted decision trees）等主流模型，从理论上为"深层网络优于浅层网络"提供了严格的数学支撑。
原文 arXiv:1602.04485;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1602.04485v2