标题： 更好的神经网络表达能力：细分单纯形 显示英文标题

标题： Better Neural Network Expressivity: Subdividing the Simplex

摘要： 这项工作研究了ReLU神经网络的表达能力，重点是其深度。一系列先前的工作表明，$\lceil \log_2(n+1) \rceil$个隐藏层就足以计算$\mathbb{R}^n$上的所有连续分段线性（CPWL）函数。 Hertrich、Basu、Di Summa和Skutella（NeurIPS'21）推测，这一结果是最优的，即像最大函数这样的某些CPWL函数在$\mathbb{R}^n$上需要这种深度。 我们否定了这个猜想，并证明了$\lceil\log_3(n-1)\rceil+1$个隐藏层就足以计算$\mathbb{R}^n$上的所有CPWL函数。 证明中的一个关键步骤是，具有两个隐藏层的ReLU神经网络可以精确表示五个输入的最大函数。 更一般地，我们证明了$\lceil\log_3(n-2)\rceil+1$个隐藏层就足以计算$n\geq 4$个数的最大值。 我们的构造几乎匹配了 Averkov、Hojny 和 Merkert（ICLR'25）在特殊情况下（ReLU 网络且权重为小数时）的$\lceil\log_3(n)\rceil$下界。 这些构造可以通过单纯形到“更简单”多面体的多面体细分来获得几何解释。 显示英文摘要

摘要： 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) 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.