ReLU网络深度表达力新进展

引言

ReLU（Rectified Linear Unit）神经网络是现代深度学习的基石之一。一个ReLU网络由多层仿射变换和逐分量应用的ReLU激活函数 $\sigma (x)=\max \{0,x\}$ 交替组成。理解网络的深度（即隐藏层的数量）如何影响其表达力（能够表示的函数类别）是理论深度学习的核心问题之一。¹

本文综述该领域在2025年前后的重大突破：研究者推翻了关于最大函数（MAX函数）深度复杂度的著名猜想，并给出了显著改善的上界。

背景：CPWL函数与深度下界

ReLU网络的基本性质

ReLU网络是连续分段线性函数（Continuous Piecewise Linear, CPWL），反之，Arora等人证明每个CPWL函数都可以由某个ReLU网络精确表示。¹² 这自然引出一个复杂性理论问题：表示给定函数至少需要多少层？

设 ${\text{CPWL}}_n$ 为定义在 ${\mathbb{R}}^n$ 上的CPWL函数集合，${\text{ReLU}}_{n,k}$ 为可以用 $k$ 个隐藏层表示的函数集合。Wang和Sun³证明每个 $f\in {\text{CPWL}}_n$ 可以写成若干个MAX函数的线性组合：

$$f(x)=\sum _{i=1}^s{\sigma }_i{\text{MAX}}_{n+1}(A_i(x))$$

其中 $A_i$ 是仿射映射，${\sigma }_i\in \{\pm 1\}$。

Hertrich等人的猜想

由于MAX函数是理解深度的关键目标函数，Hertrich、Basu、Di Summa和Skutella（ NeurIPS ‘21 / SIDMA ‘23）⁴提出以下猜想：

猜想（Hertrich, Basu, Di Summa, Skutella, 2021）：表示 $n$ 个输入的最大函数 ${\text{MAX}}_n(x)=\max \{x_1,\dots ,x_n\}$ 至少需要 $\lceil {\log }_2(n)\rceil$ 个隐藏层。

此前，Arora等人²已证明 $\lceil {\log }_2(n+1)\rceil$ 层足以表示所有CPWL函数（通过二分树结构实现MAX）。该猜想认为这个上界是下界，即最优的。

该猜想在多个特殊情况下得到验证：

• Mukherjee和Basu⁵证明 $n=3$ 时需要2层
• Haase、Hertrich和Loho（ICLR ‘23）⁶证明对于整数权重的网络，该下界是紧的

新进展：推翻猜想

主要结果

2025年，Bakaev、Brunck、Hertrich、Stade和Yehudayoff¹在论文《Better Neural Network Expressivity: Subdividing the Simplex》中推翻了该猜想。他们的核心结果表明：

定理1：对于 $n\ge 1$，${\text{MAX}}_{3n+2}$ 可以用 $n+1$ 个隐藏层表示：
${\text{MAX}}_{3n+2}\in {\text{ReLU}}_{n+1}$

定理2：对于 $n\ge 3$，所有CPWL函数都可以用 $\lceil {\log }_3(n-1)\rceil +1$ 个隐藏层表示：
${\text{CPWL}}_n={\text{ReLU}}_{n,\lceil {\log }_3(n-1)\rceil +1}$

这意味着表示深度复杂度从 $\lceil {\log }_2(n+1)\rceil$ 改进为 $\lceil {\log }_3(n-1)\rceil +1$，渐近改进了常数因子 $\ln (2)/\ln (3)\approx 0.63$。

关键突破：MAX₅的两层表示

该证明的关键一步是展示MAX₅可以用恰好2个隐藏层精确表示：

命题3：计算5个输入最大值的网络所需的最少隐藏层数恰好为2。

他们给出的显式构造为：¹

$$M(x)=\frac{1}{2}[P_1(x)+P_2(x)+P_3(x)+P_4(x)+Q(x)-R_{13}(x)-R_{14}(x)-R_{23}(x)-R_{24}(x)]$$

其中每个项（如 $P_1$）本身是若干max函数的嵌套组合，可由两层网络实现。这一定理还蕴含所有4输入CPWL函数都可用2层网络实现。

证明方法：三角形单纯形细分

多面体几何视角

新证明的核心思想是建立ReLU网络与多面体几何之间的深刻联系。¹⁷

每个多面体 $P$ 对应其支撑函数：

$$h_P(x)=\max \{⟨x,p⟩:p\in P\}$$

支撑函数是凸的、正齐次的CPWL函数。MAXₙ的Newton多面体是 ${\Delta }_{n-1}=\text{conv}\{e_1,\dots ,e_n\}$，即 ${\mathbb{R}}^n$ 中的 $(n-1)$ 维单纯形。

深度复杂度与Minkowski差

表示支撑函数 $h_X$ 所需的隐藏层数，等价于找到两个多面体 $P,Q\in {\mathcal{P}}_k$（由凸包和Minkowski和递归构造），使得 $X+P=Q$。⁷ 这被称为形式Minkowski差。

单纯形细分方法

研究者发现，与其直接构造 $P,Q$，不如将单纯形 ${\Delta }_{n-1}$ 细分为若干”更简单”的多面体。关键引理为：¹

引理10：MAXₙ所需的深度至多等于：存在多面体 $Q_1,\dots ,Q_m$ 使得 ${\Delta }_{n-1}={\bigcup }_i{Q}_i$，且每个交集 $Q_S$（有限交集）都属于 ${\mathcal{P}}_k$。

对于4-单纯形（${\Delta }_3$），他们将其细分为4个菱形金字塔（rhombic pyramids）。每个金字塔可以表示为一个点（${\mathcal{P}}_0$）与一个平行四边形（${\mathcal{P}}_1$）的凸包，即属于 ${\mathcal{P}}_2$。

通过棱锥构造（pyramid construction），${\Delta }_4=x_5\ast {\Delta }_3$ 的细分可以递归地推广到更高维，最终得到 ${\Delta }_n$ 到 ${\mathcal{P}}_2$ 类多面体的细分。

这揭示了几何直觉：每一层可以将需要”连接”的物体数量减少一个因子3，从而得到 ${\log }_3$ 的深度复杂度。

下界匹配分析

值得注意的是，研究者构造的网络仅使用分母为2的幂的权重（二进制分数），这恰好落入Averkov、Hojny和Merkert（ICLR ‘25）⁸研究的”十进制分数权重”网络类别。

后者证明对于这类网络，表示MAXₙ需要至少 $\lceil {\log }_3(n)\rceil$ 层。新构造的 $\lceil {\log }_3(n-2)\rceil +1$ 层上界与其下界几乎匹配（最多差一层）。

这表明：在允许小数权重的网络中，${\log }_3$ 深度复杂度可能是最优的。要进一步改进上界，需要使用分母含有大质因子的有理权重，甚至无理权重。

深度分离结果

除了MAX函数的精确表示复杂度，另一个重要研究方向是近似意义下的深度分离——是否存在函数可被depth-3网络高效近似，但depth-2网络即使规模指数大也无法近似？

Depth-2 vs Depth-3 指数分离

Safran、Reichman和Valiant（COLT ‘25）⁹给出了突破性结果：

定理：存在 $O(1)$-Lipschitz目标函数 $f:{\mathbb{R}}^d\to \mathbb{R}$，使得：

• depth-3网络可用 $\text{poly}(d)$ 规模高效近似 $f$（常数精度）
• depth-2网络除非规模指数大（$2^{\Omega (d)}$），否则无法近似 $f$

这是首个在Lipschitz常数、目标精度和定义域尺寸都固定为常数时成立的深度分离结果。之前的结果要求这些参数中至少有一个随维度多项式变化。

相关工作

Eldan和Shamir（COLT ‘16）¹⁰以及Daniely（COLT ‘17）¹¹早期也证明了depth-2与depth-3之间的分离，但使用的函数具有随维度振荡的Lipschitz参数。Telgarsky（COLT ‘16）¹²则证明了更深网络相对于浅层网络的指数级优势。

开放问题与未来方向

1. MAX₆的两层表示：虽然MAX₅已确定可用2层表示，但MAX₆是否也可以仍未知
2. 常数深度表示CPWL：是否存在某个固定常数 $k$ 使得所有CPWL函数都可用 $k$ 层网络表示？
3. 深度-宽度的权衡：深度如何与宽度交互以实现更高效的表示？
4. ICNN模型的深度下界：与普通ReLU网络不同，输入凸神经网络（ICNN）可能需要任意深度来表示某些CPWL函数¹³

参考文献

Footnotes

1. Bakaev, E., Brunck, F., Hertrich, C., Stade, J., & Yehudayoff, A. (2026). Better Neural Network Expressivity: Subdividing the Simplex. arXiv:2505.14338. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Arora, R., Basu, A., Mianjy, P., & Mukherjee, A. (2018). Understanding deep neural networks with rectified linear units. ICLR. ↩ ↩²

3. Wang, S., & Sun, X. (2005). Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, 51(12), 4425-4431. ↩

4. Hertrich, C., Basu, A., Di Summa, M., & Skutella, M. (2023). Towards lower bounds on the depth of ReLU neural networks. SIAM Journal on Discrete Mathematics, 37(2), 997-1029. (NeurIPS ‘21) ↩

5. Mukherjee, A., & Basu, A. (2017). Lower bounds over boolean inputs for deep neural networks with ReLU gates. arXiv:1711.03073. ↩

6. Haase, C., Hertrich, C., & Loho, G. (2023). Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. ICLR. ↩

7. Valerdi, J. (2024). On minimal depth in neural networks. arXiv:2402.15315. ↩ ↩²

8. Averkov, G., Hojny, C., & Merkert, M. (2025). On the expressiveness of rational ReLU neural networks with bounded depth. ICLR. ↩

9. Safran, I., Reichman, D., & Valiant, P. (2025). Depth separations in neural networks: Separating the dimension from the accuracy. COLT. ↩

10. Eldan, R., & Shamir, O. (2016). The power of depth for feedforward neural networks. COLT. ↩

11. Daniely, A. (2017). Depth separations in neural networks. COLT. ↩

12. Telgarsky, M. (2016). Benefits of depth in neural networks. COLT. ↩

13. Bakaev, E., Brunck, F., Hertrich, C., Reichman, D., & Yehudayoff, A. (2025). On the depth of monotone ReLU neural networks and ICNNs. arXiv:2505.06169. ↩