Tight bounds reveal complexity advantage of kolmogorov arnold networks

Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks

Machine Learning

Summary

The paper studies how complex certain specialized neural networks called Kolmogorov-Arnold networks (KANs) can be when they use piecewise linear functions. It provides exact mathematical limits on how many distinct linear pieces these networks can create, improving earlier estimates. The authors also compare KANs to common ReLU-based networks and show that KANs can achieve more complexity with the same number of parameters, especially when the network has multiple layers. This characterization helps understand the power of these networks and guides how to build them.

What this means in practice

  • For neural network architects: Design KAN architectures with optimal widths and segment counts to maximize representational complexity for fixed input dimensions and network depth.
  • For machine learning engineers: Choose between KANs and ReLU networks informed by their theoretical capacity advantage under parameter constraints for better model expressiveness.

A theory result. No direct application yet.

Authors

Ye Su, Yong Liu

Abstract

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.