证明了深度越深，计算最大值所需宽度呈指数增长。
A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory
- 用图论方法分析隐藏层结构，关联非光滑边界与团
- 深度3到log log d时，宽度需至少d^(1+1/(2^(k-2)-1))
- 首次对最大值函数给出无条件超线性下界，适合理论研究者
研究使用ReLU神经网络精确计算d个实数输入的最大值问题。证明了深度层次结构：当深度满足3≤k≤log₂(log₂(d))时，网络宽度必须达到Ω(d^{1+1/(2^{k-2}-1)})才能表示最大值函数。这是该基础算子在深度k≥3时首个无条件的超线性下界，即使深度随d变化也成立。证明基于组合论证，将最大值函数的不可导脊线与第一隐层诱导图中的团对应起来，利用极值图论中的Turán定理，说明过窄网络无法捕捉最大值的非线性特征。这表明尽管最大值函数形式简单，其内在复杂性源于非可导超平面的几何结构，并为深度神经网络下界证明提供了新方法。
原文摘要 · Abstract (English)
We consider the problem of exact computation of the maximum function over $d$ real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width $Ω\big(d^{1+\frac{1}{2^{k-2}-1}}\big)$ is necessary to represent the maximum for any depth $3\le k\le \log_2(\log_2(d))$. This is the first unconditional super-linear lower bound for this fundamental operator at depths $k\ge3$, and it holds even if the depth scales with $d$. Our proof technique is based on a combinatorial argument and associates the non-differentiable ridges of the maximum with cliques in a graph induced by the first hidden layer of the computing network, utilizing Turán's theorem from extremal graph theory to show that a sufficiently narrow network cannot capture the non-linearities of the maximum. This suggests that despite its simple nature, the maximum function possesses an inherent complexity that stems from the geometric structure of its non-differentiable hyperplanes, and provides a novel approach for proving lower bounds for deep neural networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。