用精确代数方法证明12维最大值函数仅需两层ReLU网络精确表示。
Shallower ReLU Network Representations via Exact Linear Algebra
- 通过符号化约简将问题转为有理数上的线性方程组求解
- 首次实现n≤12时max函数的精确两层表示，突破此前n≤5限制
- 可推广至d≤11维任意连续分段线性函数，层数呈对数增长
我们研究了ReLU网络精确表示分段线性函数所需的最小深度，聚焦于最大函数。近期该问题在机器学习与理论计算机科学领域受到广泛关注。本文证明：对于任意n≤12，max_n(x)=max{x₁,…,xₙ} 可被两层隐藏层的ReLU网络精确表示。此前结果仅知n≤5。我们通过在候选解空间中进行精确的计算机辅助搜索实现此构造：经对称性约简后，得到一个定义在ℚ上的有限线性方程组，其任一解均可导出最大函数的有效表示。所得结构具有规律性的第一隐藏层，支持递归嵌套至更深网络。由此得出max_n的精确表示最多只需⌈log₆(n/2)⌉+1层隐藏层。因此，ℝᵈ上任意连续分段线性函数均可被最多⌈log₆((d+1)/2)⌉+1层隐藏层的ReLU网络精确表示；特别地，当d≤11时，两层足够。这些结果改进了此前[Bakaev et al., STOC'26]基于三进制对数的界。
原文摘要 · Abstract (English)
We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that $\max_n(x)=\max\{x_1,\ldots,x_n\}$ is exactly representable with two hidden layers for every $n\leq 12$. Previously, this was only known up to $n\leq5$ [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we obtain a finite system of linear equations over $\mathbb{Q}$ such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into deeper networks. This yields an exact ReLU representation of $\max_n$ with at most $\lceil \log_6(n/2) \rceil+1$ hidden layers. Consequently, every continuous piecewise-linear function on $\mathbb{R}^d$ admits an exact representation with at most $\lceil\log_6((d+1)/2)\rceil+1$ hidden layers; in particular, two hidden layers suffice for $d\leq 11$. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。