每多一层ReLU网络,可指数级减少所需神经元数。
Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks
- 构建深度递增的函数,证明每层都能指数压缩参数量
- 深度k+1网络仅需宽度O(d⁴),而深度k网络误差超1/24
- 首次实现深度3与2间指数分离,适用于理论研究者
我们证明了ReLU神经网络存在深度层次结构,每一层增加均可使神经元数量指数级减少。对所有k≥2,构造了一个全局[0,1]取值、1-利普希茨的函数,该函数由深度为(k+1)、宽度为O(d⁴)的网络实现;而任何深度为k、权重无限制且宽度不超过2^d/(2d(k−1))的网络,在支持于原点指数距离处的绝对连续分布下,平方L₂误差至少为1/24。据我们所知,这是首个在所有相邻固定深度间的指数层次结构,也是首个在浅层网络深度至少为3时,实现两固定深度间指数分离的结果。该下界也直接推出精确计算的层次结构。当k=2时,给出了深度3与2之间紧支撑的分离,回答了Safran、Eldan和Shamir(2019)提出的问题。但所用分布质量集中于指数半径处,使该层次结构脱离常规正则性范畴,无法导出重大阈值电路下界。此外,还证明了一个更规则目标的精确分离:该函数全局[0,1]取值,利普希茨常数为O(√d),将单位超立方体映射至[0,1]。它可被多项式宽度的深度4网络计算,而任何在单位超立方体上与其一致的深度3网络,即使权重无限制,也需指数级第一层神经元。
原文摘要 · Abstract (English)
We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all $k\geq2$, we construct a globally $[0,1]$-valued, $1$-Lipschitz function realized by a depth-$(k+1)$ network of width $\mathcal{O}(d^4)$, whereas any depth-$k$ network with unrestricted weights and width at most $\frac{2^d}{2d(k-1)}$ has squared $L_2$ error at least $1/24$ under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least $3$. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case $k=2$ gives a compactly supported separation between depths $3$ and $2$ with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally $[0,1]$-valued and $\mathcal{O}(\sqrt d)$-Lipschitz and maps the unit hypercube onto $[0,1]$. It is computed by a polynomial-width depth-$4$ network, whereas any depth-$3$ network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。