改进了ReLU网络深度下界，用更少层数实现所有分段线性函数。
Better Neural Network Expressivity: Subdividing the Simplex
- 通过细分单纯形的几何方法，设计高效网络结构。
- 仅需⌈log₃(n−1)⌉+1层即可计算任意n维分段线性函数。
- 适用于需要紧凑深度网络的研究者，如神经架构设计。
本文研究ReLU神经网络的表达能力，重点在深度方面。先前工作表明，⌈log₂(n+1)⌉层隐藏层足以计算ℝⁿ上的所有连续分段线性（CPWL）函数。Hertrich、Basu、Di Summa和Skutella（NeurIPS'21 / SIDMA'23）猜想该结果最优，即某些函数（如最大值函数）确实需要此深度。本文推翻该猜想，证明⌈log₃(n−1)⌉+1层已足够计算所有ℝⁿ上的CPWL函数。关键突破在于：两层ReLU网络可精确表示五个输入的最大值函数；更一般地，⌈log₃(n−2)⌉+1层可计算n≥4个数的最大值。构造接近Averkov、Hojny和Merkert（ICLR'25）给出的⌈log₃(n)⌉下界（当权重为十进制分数时）。这些构造具有单纯形多面体剖分的几何解释。
原文摘要 · Abstract (English)
This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that $\lceil \log_2(n+1) \rceil$ hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on $\mathbb{R}^n$. Hertrich, Basu, Di Summa, and Skutella (NeurIPS'21 / SIDMA'23) conjectured that this result is optimal in the sense that there are CPWL functions on $\mathbb{R}^n$, like the maximum function, that require this depth. We disprove the conjecture and show that $\lceil\log_3(n-1)\rceil+1$ hidden layers are sufficient to compute all CPWL functions on $\mathbb{R}^n$. A key step in the proof is that ReLU neural networks with two hidden layers can exactly represent the maximum function of five inputs. More generally, we show that $\lceil\log_3(n-2)\rceil+1$ hidden layers are sufficient to compute the maximum of $n\geq 4$ numbers. Our constructions almost match the $\lceil\log_3(n)\rceil$ lower bound of Averkov, Hojny, and Merkert (ICLR'25) in the special case of ReLU networks with weights that are decimal fractions. The constructions have a geometric interpretation via polyhedral subdivisions of the simplex into ``easier'' polytopes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。