Metraipolis › archive › dc_85c8aaee043f

Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks — arXiv:2611.07973

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.07973
License (as archived): CC0-1.0
Archived: 2026-11-06T14:50:47.996Z
SHA-256 of the archived text: da100fe360e33ea9300e45ed0b2ca02ba0b085a61589e2fc7c8f12fbc5644878
Stable URL of this page: https://metraipolis.com/documento/dc_85c8aaee043f

How to cite

Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks — arXiv:2611.07973 — arXiv (en), https://arxiv.org/abs/2611.07973 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_85c8aaee043f (Metraipolis archive dc_85c8aaee043f, sha256 da100fe360e33ea9300e45ed0b2ca02ba0b085a61589e2fc7c8f12fbc5644878)

BibTeX

@misc{dc85c8aaee043f,
  title = {Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks — arXiv:2611.07973},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07973},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_85c8aaee043f; sha256 da100fe360e33ea9300e45ed0b2ca02ba0b085a61589e2fc7c8f12fbc5644878},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07973. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Theta_{\mathbf n}(k^{\sum_{\ell=1}^{T}\rho_{\ell-1}})$ in $k$, where $\rho_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$. When every hidden width is at least $d$, the tight order simplifies to $\Theta_{\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 $\Theta_{\mathbf n}\!\left(k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}\rho_{\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 $\Lambda$ 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 $\Theta_{d,T}(\Lambda^{d\lfloor T/2\rfloor})$ as $\Lambda\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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.07973 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:21:42.638Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).