KAN 线性区域数量上界与下界首次 matched，理论证明其对 ReLU 网络的多项式优势
Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks
数学圈好消息：KAN 网络的表达能力第一次有了紧的上界和下界，还证明深度大于等于 2 时线性区域比 ReLU 网络多出多项式倍，搞理论的朋友可以细看。
一篇 arXiv 论文针对连续分段线性（CPWL）Kolmogorov-Arnold 网络（KAN）的线性区域数量给出匹配的上下界，增长阶为 Θ(k^{Σρ})，其中每条边最多 k 个仿射段。当所有隐藏层宽度不小于输入维度 d 时，该阶简化为 Θ(k^{dT})，比 AISTATS 2025 中 Schoots 等人的上界 k^{Σn·n} 有严格渐近改进。在参数量不超过 Λ、深度 T 相同的条件下，论文证明 CPWL KAN 与 ReLU 网络的最大线性区域之比为 Θ(Λ^{d⌊T/2⌋})，当 T≥2 时 KAN 具有多项式优势。
Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks
Schoots et al.~\citep{schoots2025relating} (AISTATS 2025) established a generally loose upper bound on the number of linear regions of continuous piecewise-linear (CPWL) Kolmogorov--Arnold networks (KANs), without providing a lower bound. We consider a $T$-layer network with width vector $\mathbf n=(n_0,\ldots,n_T)$, input dimension $n_0=d$, output width $n_T=1$, and at most $k\geq2$ affine segments per edge. Our matching upper and lower bounds determine the tight growth order $Θ_{\mathbf n}(k^{\sum_{\ell=1}^{T}ρ_{\ell-1}})$ in $k$, where $ρ_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$. When every hidden width is at least $d$, the tight order simplifies to $Θ_{\mathbf n}(k^{dT})$. The upper bound of \citep{schoots2025relating} is $k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell}$. Our upper bound improves it by a factor of $Θ_{\mathbf n}\!\left(k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}ρ_{\ell-1}} \right)$, with strict asymptotic improvement whenever a hidden layer has width greater than one. We further compare CPWL KANs with rectified linear unit (ReLU) networks using dense parameterizations with at most $Λ$ parameters per model and the same fixed nonlinear depth $T$. Counting trainable knot locations and optimizing the widths and $k$, we prove that the maximum region count of CPWL KANs divided by that of ReLU networks is $Θ_{d,T}(Λ^{d\lfloor T/2\rfloor})$ as $Λ\to\infty$, yielding a polynomial advantage for KANs when $T\geq2$. These tight bounds characterize the attainable geometric complexity of CPWL KANs, providing a foundation for understanding their expressive power and guiding architectural design.