Generalization Bounds and Model Complexity for Kolmogorov–Arnold Networks

## Abstract

Abstract Kolmogorov–Arnold Network (KAN) is a network structure recently proposed in Liu et al. ( 2024c ) that offers improved interpretability and a more parsimonious design in many science-oriented tasks compared to multi-layer perceptrons. This work provides a rigorous theoretical analysis of KAN by establishing generalization bounds for KAN equipped with activation functions that are either represented by linear combinations of basis functions or lying in a low-rank Reproducing Kernel Hilbert Space (RKHS). In the first case, the generalization bound accommodates various choices of basis functions in forming the activation functions in each layer of KAN and is adapted
to different operator norms at each layer. For a particular choice of operator norms, the bound scales with the l 1 subscript 𝑙 1 l_{1} italic_l start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT norm of the coefficient matrices and the Lipschitz constants for
the activation functions, and it has no dependence on combinatorial parameters (e.g., number of nodes) outside of logarithmic factors. Moreover, our result does not require the boundedness assumption on the loss function and, hence, is applicable to a general class of regression-type loss functions.
In the low-rank case, the generalization bound scales polynomially with the underlying ranks as well as the Lipschitz constants of the activation functions in each layer. These bounds are empirically investigated for KANs trained with stochastic gradient descent on simulated and real data sets. The numerical results demonstrate the practical relevance of these bounds.

## 1 Introduction

The Kolmogorov-Arnold representation theorem (KART) states that if $f$ is a multivariate continuous function defined on $[0,1]^{d}$, then $f$ can be written as a finite composition of continuous functions of a single variable, and the binary operation of addition. More specifically, $f$ can be represented by a two-layer network in the form of

$$ $\displaystyle f(x_{1},\dots,x_{d})=\sum^{2d}_{i=0}\psi_{i}\left(\sum^{d}_{j=1} \psi_{i,j}(x_{j})\right),$ $$

where $\psi_{i,j}:[0,1]\rightarrow\mathbb{R}$ and $\psi_{i}:\mathbb{R}\rightarrow\mathbb{R}$. Motivated by KART, Liu et al. () introduced the Kolmogorov–Arnold Networks (KANs), expanding on the original two-layer network to accommodate arbitrary depths. Mathematically, the KANs can be concisely described through the compositions of $L$ multivariate vector-valued functions:

$$ $\displaystyle\text{KAN}({\mathbf{x}})=\bm{\Psi}_{L}\circ\bm{\Psi}_{L-1}\circ \cdots\circ\bm{\Psi}_{1}({\mathbf{x}}),\quad{\mathbf{x}}\in\mathbb{R}^{d_{0}},$ $$

where $\bm{\Psi}_{i}$ is a matrix of univariate functions:

$$ $\displaystyle\bm{\Psi}_{i}=\begin{pmatrix}\psi_{i,1,1}&\psi_{i,1,2}&\cdots& \psi_{i,1,d_{i-1}}\\ \psi_{i,2,1}&\psi_{i,2,2}&\cdots&\psi_{i,2,d_{i-1}}\\ \vdots&\vdots&\ddots&\vdots\\ \psi_{i,d_{i},1}&\psi_{i,d_{i},2}&\cdots&\psi_{i,d_{i},d_{i-1}}\end{pmatrix}$ $$

with $\psi_{i,j,k}:\mathbb{R}\rightarrow\mathbb{R}$. Here, we have defined

$$ $\displaystyle\bm{\Psi}_{i}({\mathbf{x}})=\left(\sum^{d_{i-1}}_{j=1}\psi_{i,1,j }(x_{j}),\dots,\sum^{d_{i-1}}_{j=1}\psi_{i,d_{i},j}(x_{j})\right)^{\top}$ (1) $$

for ${\mathbf{x}}=(x_{1},\dots,x_{d_{i-1}})^{\top}\in\mathbb{R}^{d_{i-1}}$ and $1\leq i\leq L$. The node values for the $i$th layer are given by

$$ ${\mathbf{x}}_{i}=(x_{i,1},\dots,x_{i,d_{i}})^{\top}=\bm{\Psi}_{i}\circ\bm{\Psi }_{i-1}\circ\cdots\circ\bm{\Psi}_{1}({\mathbf{x}})$ $$

where $x_{i,j}=\sum^{d_{i-1}}_{k=1}\psi_{i,j,k}(x_{i-1,k})$ is defined recursively.

Figure: Figure 1: Illustration of Kolmogorov-Arnold Networks, where the edges are associated with one-dimensional trainable functions while the nodes perform summation.
Refer to caption: x1.png

In contrast to multi-layer perceptions (MLPs), which use fixed activation functions on nodes, KANs utilize learnable activation functions along the edges. This architectural shift eliminates the need for conventional linear weight matrices. Instead, KANs replace each weight parameter with a trainable one-dimensional function. In KANs, nodes serve as aggregation points, summing incoming signals without applying non-linear transformations; see Figure 1 for an illustration. Liu et al. () demonstrated the potential of KANs for science-oriented tasks due to its accuracy and interpretability. Subsequent research has explored the application of KANs in various domains such as graphs (Bresson et al., ; De Carlo et al., ; Kiamari et al., ),
partial differential equations (Wang et al., ; Shukla et al., ),
operator learning (Abueidda et al., ; Nehma & Tiwari, ),
tabular data (Poeta et al., ),
time series (Genet & Inzirillo, ; Vaca-Rubio et al., ; Xu et al., ), human activity recognition (Liu et al., ),
neuroscience (Herbozo Contreras et al., ; Yang et al., ),
quantum science (Kundu et al., ; Li et al., ),
computer vision (Azam & Akhtar, ; Bodner et al., ; Cheon, ; Li et al., ; Seydi, ),
kernel learning (Zinage et al., ),
nuclear physics (Liu et al., ),
electrical engineering (Peng et al., ),
and biology (Pratyush et al., ).
Unlike MLPs, KANs allow a flexible way to specify and estimate the activation functions from training samples. Various choices of activation functions have been recently investigated, including B-splines Liu et al. (), wavelets (Seydi, ; Bozorgasl & Chen, ),
radial basis functions (Li, ; Ta, ),
Fourier series (Xu et al., ),
finite basis (Howard et al., ),
Jacobi basis functions (Aghaei, ),
polynomial basis functions (Seydi, ),
and rational functions (Aghaei, ).
Additional techniques for KANs have also been proposed, such as regularization (Altarabichi, ),
Kansformer (combining transformer with KANs) (Chen et al., ),
adaptive grid update (Rigas et al., ),
federated learning (Zeydan et al., ),
and Convolutional KANs (Bodner et al., ). A survey on the recent development of KANs can be found in Hou & Zhang ().

### 1.1 Contributions

Despite the increasing interest in applying KANs to various scientific problems and exploring the best ways to construct the network structure and training process, there is currently no recent research focusing on quantifying the complexity of KANs to the best of our knowledge. Additionally, there is a need to understand how the performance of KANs is impacted by network structure and its complexity.
The contribution of this work can be summarized as follows.

- •
Theorem 3 below will give the rigorous statement of the generalization bound for KANs, which (i) accommodates different choices of basis functions in forming the activation functions in each layer; (ii) is adapted to
various operator norms at each layer;
(iii) scales with the $l_{1}$ norm of the coefficient matrices and the Lipschitz constants for the activation
functions for a particular choice of operator norms; (iv) has no dependence on combinatorial parameters (e.g., number of nodes) outside of logarithmic factors; (v) does not require the boundedness assumption on the loss function.
- •
Theorem 4 presents the generalization bound when the activation functions for each layer belong to a Reproducing Kernel Hilbert Space (RKHS) with a low-rank structure. The bound scales polynomially with the underlying ranks as well as the Lipschitz constants of the activation functions in each layer.
- •
We empirically investigate these bounds when the KANs are trained with stochastic gradient descent (SGD) on simulated and real data sets. The results shed new light on how the performance of KANs is affected by the underlying network structure and the network complexity. In particular, we observe that the complexity measure derived in Section 2 is tightly correlated with the excess loss, demonstrating the complexity measure’s practical relevance.

### 1.2 Related works

Generalization bounds for MLPs have long been studied in the literature on learning theory; see, e.g., Bartlett (); Anthony et al. ().
More recently, Bartlett et al. () provided a margin bound and corresponding Rademacher analysis that can be adapted to various operator norms at each layer. The proof technique therein was inspired by the early result for two-layer networks in Bartlett (). Farrell et al. () established non-asymptotic bounds for MLPs for a general class of nonparametric regression-type loss functions. Schmidt-Hieber () showed that MLPs with a sparsely connected structure achieve the minimax rates of convergence (up to a logarithmic factor) under a general composition assumption on the regression function.

The contribution of the present work is to provide a generalization bound for the novel KAN network structure, which is fundamentally different from the traditional MLPs as demonstrated in Liu et al. (, ).
The current analysis uses covering numbers and is closely related to earlier covering number bounds in Anthony et al. () and the recent results in Bartlett et al. () for MLPs. The current proof also utilizes Maurey’s sparsification lemma. However, it is important to highlight some key differences with existing results for MLPs. Firstly, our results can be seen as a non-trivial extension of MLP results to a more flexible network structure specified through a more general choice of activation functions. Secondly, Bartlett et al. () focuses on the margin-based multiclass generalization bound, which has a bounded loss function (more precisely, the ramp loss). In contrast, our results cover a wider range of loss functions (including the ramp loss for classification and a general class of regression-type loss functions), which are not required to be bounded. Thirdly, the results for KANs with a low-rank structure in Section 2.3 appear to be new, and we are not aware of comparable results for MLPs in the recent literature.

The rest of the article is organized as follows: We provide the generalization bounds for KANs equipped with activation functions that are either represented
by a set of basis functions or lying in a low-rank space in Sections 2.2 and 2.3, respectively. Section 3 presents numerical results to support the theoretical findings. Section 4 concludes and discusses a few open problems for future research.

## 2 Statistical Analysis

We focus on the supervised learning task, which aims to predict a response using a set of covariates. Suppose we have $n$ independent observations $({\mathbf{x}}_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}$ with $1\leq i\leq n$ generated from some distribution $P$, where $\mathcal{X}\subset\mathbb{R}^{d_{0}}$ and $\mathcal{Y}\subset\mathbb{R}^{d_{L}}$. Let $\mathcal{L}(\cdot,\cdot)$ be a loss function defined on $\mathcal{Y}\times\mathcal{Y}$. We consider the KAN-induced neural network class

$$ $\displaystyle\mathcal{M}=\{f(\cdot)=\bm{\Psi}_{L}\circ\bm{\Psi}_{L-1}\circ \cdots\circ\bm{\Psi}_{1}(\cdot):\bm{\Psi}_{l}\in\mathcal{F}_{l},l=1,2,\dots,L\},$ $$

for some pre-specified function classes $\mathcal{F}_{l}$, where $\bm{\Psi}\in\mathcal{F}_{l}$ is a map from $\mathbb{R}^{d_{l-1}}$ to $\mathbb{R}^{d_{l}}$. Given any $f\in\mathcal{M}$, we define the generalization error (or risk)
$R(f)=\mathbb{E}[\mathcal{L}(f({\mathbf{x}}),y)]$ for $({\mathbf{x}},y)\sim P$.
To find the optimal predictor within $\mathcal{M}$, we minimize the empirical risk function

$$ $\displaystyle\min_{f\in\mathcal{M}}\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({ \mathbf{x}}_{i}),y_{i}).$ (2) $$

Our goal here is to establish a bound on $R(f)$ for every $f\in\mathcal{M}$. In particular, let $\hat{f}$ be the predictor resulting from an optimization scheme (e.g., SGD, Adam, or L-BFGS) that solves (2). Our result implies a bound on the generalization error $R(\hat{f})$.

### 2.1 Notation and definitions

We introduce the notion of proper covering numbers. For a set $\mathcal{U}$ equipped with some norm $\|\cdot\|$, we let $\mathcal{N}(\mathcal{U},\epsilon,\|\cdot\|)$ be the smallest number of a subset $\mathcal{V}$ of $\mathcal{U}$ such that for any $u\in\mathcal{U}$, there exists a $v\in\mathcal{V}$ so that $\|v-u\|\leq\epsilon.$
Let ${\mathbf{X}}=[{\mathbf{x}}_{1},\dots,{\mathbf{x}}_{n}]^{\top}\in\mathbb{R}^{n
\times d}$ for ${\mathbf{x}}_{i}\in\mathbb{R}^{d}$ and $\mathcal{F}$ be a class of multivariate vector-valued functions mapping from $\mathbb{R}^{d}$ to $\mathbb{R}^{m}$. For any $\bm{\Psi}\in\mathcal{F}$, we write $\bm{\Psi}({\mathbf{X}})=[\bm{\Psi}({\mathbf{x}}_{1}),\dots,\bm{\Psi}({\mathbf{
x}}_{n})]^{\top}\in\mathbb{R}^{n\times m}.$ For a matrix $A=(a_{ij})$, we denote by $\|A\|_{2}=\sqrt{\sum_{i,j}a_{ij}^{2}}$ its Frobenius norm.

### 2.2 Risk analysis: activation functions represented by basis functions

Let
$\mathcal{H}_{i}({\mathbf{X}}):=\{\bm{\Psi}_{i}\circ\cdots\circ\bm{\Psi}_{1}
\circ\bm{\Psi}_{0}({\mathbf{X}}):\bm{\Psi}_{l}\in\mathcal{F}_{l},l=1,2,\dots,i\}$, where
$\bm{\Psi}_{0}({\mathbf{X}})={\mathbf{X}}$ is the identity map.
Given $\epsilon_{i},\rho_{i}>0$ for $1\leq i\leq L$, we define
$s_{1}=\epsilon_{1}$ and
$s_{k}=\sum^{k}_{i=1}(\prod^{k}_{j=i+1}\rho_{j})\epsilon_{i}$ for $k=2,\dots,L$, where we set
$\prod^{b}_{j=a}\rho_{j}=1$ for $a>b$.
The subscript $i$ in the norm $|\cdot|_{i}$ below merely indicates an index and does not refer to any $l_{i}$ norm.

###### Proposition 1 .

Suppose $\bm{\Psi}_{i}\in\mathcal{F}_{i}$ is a map from $\mathbb{R}^{d_{i-1}}$ to $\mathbb{R}^{d_{i}}$, which satisfies
$|\bm{\Psi}({\mathbf{X}})-\bm{\Psi}({\mathbf{X}}^{\prime})|_{i}\leq\rho_{i}|{
\mathbf{X}}-{\mathbf{X}}^{\prime}|_{i-1}$ for $\rho_{i}>0$ and ${\mathbf{X}},{\mathbf{X}}^{\prime}\in\mathbb{R}^{n\times d_{i-1}}$.
Then we have

$$ $\begin{split}&\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),s_{L},|\cdot|_{L})\\ \leq&\prod^{L-1}_{i=0}\sup_{\bm{\Psi}_{1},\dots,\bm{\Psi}_{i}}\mathcal{N}(\{ \bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots\circ\bm{\Psi}_{0}({ \mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{i+1}\},\epsilon_{i+1},|\cdot|_{i+1}), \end{split}$ (3) $$

where when $i=0$, the first term in the product is given by $\mathcal{N}\left(\{\bm{\Psi}({\mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{1}\},
\epsilon_{1},|\cdot|_{1}\right).$

Proposition 1 establishes an upper bound on $\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),s_{L},|\cdot|_{L})$ in terms of the covering numbers

$$ $\mathcal{N}(\{\bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots\circ \bm{\Psi}_{0}({\mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{i+1}\},\epsilon_{i+1},| \cdot|_{i+1}).$ $$

It is built upon an iterative argument that generalizes those for MLPs (Anthony et al., ; Bartlett et al., ) and is adapted to various operator norms (i.e., $|\cdot|_{i}$) at each layer.
To better understand these quantities, we will start by presenting a result when the activation functions can be written as linear combinations of a set of basis functions. This is a common practice, and the literature has investigated several choices of basis functions, such as B-splines, wavelets, radial basis, Fourier series, finite basis, etc.; see, e.g., Liu et al. (); Seydi (); Li (); Xu et al. (); Howard et al. ().
The proof of the following result relies on Maurey’s sparsification lemma stated in the appendix; also see Lemma 1 of Zhang ().

###### Proposition 2 .

Suppose $\bm{\Psi}({\mathbf{x}})=(\psi_{1}({\mathbf{x}}),\dots,\psi_{m}({\mathbf{x}}))$ with
$\psi_{i}({\mathbf{x}})=\sum^{p}_{j=1}\beta_{ij}g_{ij}({\mathbf{x}})$ for $1\leq i\leq m$. Here $\{g_{ij}:i=1,2,\dots,m;j=1,2,\dots,p\}$ is a set of basis functions defined on $\mathbb{R}^{d}$. Let $\mathbf{B}=(\beta_{ij})\in\mathbb{R}^{m\times p}$ and $\mathbf{G}({\mathbf{X}})=(g_{ij}({\mathbf{x}}_{k}))\in\mathbb{R}^{m\times p
\times n}$. Define $\|\mathbf{B}\|_{r}=(\sum^{m}_{i=1}\sum^{p}_{j=1}|\beta_{ij}|^{r})^{1/r}$ and

$$ $\|\mathbf{G}({\mathbf{X}})\|_{v,s}=\left\{\sum^{m}_{i=1}\sum^{p}_{j=1}\left( \sum^{n}_{k=1}|g_{ij}({\mathbf{x}}_{k})|^{v}\right)^{s/v}\right\}^{1/s}$ $$

for $0<v\leq 2$ and $r,s>0$ with $1/r+1/s=1$.
We assume that $\|\mathbf{B}\|_{r}\leq b_{m,p,n}$ and $\|\mathbf{G}({\mathbf{X}})\|_{v,s}\leq c_{m,p,n}$, where $b_{m,p,n},c_{m,p,n}$ are both allowed to grow with $m,p$ and $n$. Then, we have

$$ $\displaystyle\log\mathcal{N}\left(\left\{\bm{\Psi}({\mathbf{X}})\in\mathbb{R}^ {n\times m}:\bm{\Psi}\in\mathcal{F}\right\},\epsilon,\|\cdot\|_{2}\right)\leq \frac{b_{m,p,n}^{2}c_{m,p,n}^{2}}{\epsilon^{2}}\log(2mp).$ $$

With the above results, we now provide a bound on the covering number of $\mathcal{H}_{L}({\mathbf{X}})$.
We make the following assumptions.

###### Assumption 1 .

Assume that $\|{\mathbf{X}}\|_{2}\leq D$ for some constant $D>0$.

###### Assumption 2 .

Suppose $\bm{\Psi}_{l}$ belongs to the following function space

$$ $\displaystyle\mathcal{F}_{l}=$ $\displaystyle\Bigg{\{}\bm{\Psi}=(\psi_{1},\dots,\psi_{d_{l}}):\psi_{i}(\cdot)= \sum^{p_{l}}_{j=1}\beta_{ij}^{(l)}g_{ij}^{(l)}(\cdot),\|\bm{\Psi}({\mathbf{x}} )-\bm{\Psi}({\mathbf{x}}^{\prime})\|_{2}\leq\rho_{l}\|{\mathbf{x}}-{\mathbf{x} }^{\prime}\|_{2},$ $\displaystyle\|\bm{\Psi}(\mathbf{0})\|_{2}\leq C_{l},\|\mathbf{B}_{l}\|_{1}= \sum^{d_{l}}_{i=1}\sum^{p_{l}}_{j=1}|\beta_{ij}^{(l)}|\leq B_{l}\Bigg{\}},$ $$

for some constants $\rho_{l},B_{l},C_{l}>0.$
Further, assume that

$$ $\displaystyle|g_{ij}^{(l)}({\mathbf{x}})-g_{ij}^{(l)}({\mathbf{x}}^{\prime})| \leq c_{ij}^{(l)}\|{\mathbf{x}}-{\mathbf{x}}^{\prime}\|_{2}.$ (4) $$

We make a set of remarks regarding the above assumptions.

###### Remark 1 .

Note that the bound on the $l_{2}$ norm of $\mathbf{X}$ is allowed to grow in our theorem. Moreover, Assumption 1 can be relaxed by requiring the bound to hold with high probability, which can be justified when the distribution of $\mathbf{X}$ has a sufficiently light tail, e.g., sub-Guassian or sub-exponential tails.

###### Remark 2 .

The form of $\bm{\Psi}$ in Assumption 2 is indeed more general than the additive structure in (1), as $g_{ij}^{(l)}$ is a multivariate function. Consider $\bm{\Psi}=(\psi_{1},\dots,\psi_{d_{l}})$, where

$$ $\displaystyle\psi_{i}({\mathbf{x}})=\sum_{j=1}^{d_{l-1}}\psi_{i,j}(x_{j}), \quad\psi_{i,j}(x_{j})=\sum_{k=1}^{b_{l}}\beta_{i,j,k}g_{j,k}(x_{j}),$ (5) $$

and ${g_{j,k}}$ is a set of univariate basis functions. This can be viewed as a special form of the activation function specified in Assumption 2, where the set of $p_{l}$ basis functions $g_{ij}^{(l)}$ is given by $\{g_{j,k}:1\leq j\leq d_{l-1},1\leq k\leq b_{l}\}$.

###### Remark 3 .

When $\{g_{ij}^{(l)}\}_{j}$ is a set of univariate B-spline basis functions with degree $p$ and the knots $\{\xi_{i,j}^{(l)}\}_{j}$, we have
$c_{ij}^{(l)}\leq 2p/\Delta_{i}^{(l)},$
where $\Delta_{i}^{(l)}=\max_{j}(\xi^{(l)}_{i,j+p}-\xi^{(l)}_{i,j})$.

###### Remark 4 .

Let $\|\mathbf{B}_{l}\|_{0}=|\{\beta_{ij}^{(l)}\neq 0:1\leq i\leq d_{l},1\leq j\leq
p
_{l}\}|$ be the number of non-zero coefficients in $\mathbf{B}_{l}$. Suppose $\max_{i,j}|\beta_{ij}^{(l)}|\leq B_{\max}$. Then we have $\|\mathbf{B}_{l}\|_{1}\leq B_{\max}\|\mathbf{B}_{l}\|_{0}$.

###### Remark 5 .

The tightest Lipschitz constant
for $\bm{\Psi}$ is given by

$$ $\displaystyle\rho^{*}=\sup_{{\mathbf{x}}\neq{\mathbf{x}}^{\prime}}\frac{\|\bm{ \Psi}({\mathbf{x}})-\bm{\Psi}({\mathbf{x}}^{\prime})\|_{2}}{\|{\mathbf{x}}-{ \mathbf{x}}^{\prime}\|_{2}}.$ $$

When $\bm{\Psi}({\mathbf{x}})=\mathbf{A}{\mathbf{x}}+\mathbf{b}$ is linear, $\rho^{*}$ is simply the spectral norm of the matrix $\mathbf{A}$ (denoted by $\|\mathbf{A}\|_{\sigma}$). When $\bm{\Psi}$ takes the form in (5), we can write $\bm{\Psi}({\mathbf{x}})={\mathbf{A}}{\mathbf{g}}({\mathbf{x}})$, where ${\mathbf{A}}\in\mathbb{R}^{d_{l}\times(d_{l-1}b_{l})}$ with the $(i,(j-1)b_{l}+k)$th element of ${\mathbf{A}}$ being $\beta_{i,j,k}$, and
${\mathbf{g}}({\mathbf{x}})\in\mathbb{R}^{d_{l-1}b_{l}}$ with the $((j-1)b_{l}+k)$th element of ${\mathbf{g}}({\mathbf{x}})$ being $g_{j,k}(x_{j})$. We can deduce that

$$ $\rho^{*}\leq\|{\mathbf{A}}\|_{\sigma}\sqrt{\sum_{k=1}^{b_{l}}a_{k}^{2}}$ $$

if $|g_{j,k}(x)-g_{j,k}(x^{\prime})|\leq a_{k}|x-x^{\prime}|$. Moreover, under Condition (4), $\rho^{*}\leq\|{\mathbf{A}}\|_{\sigma}c_{l}\sqrt{b_{l}}$, where we define $c_{l}=\max_{i,j}c_{ij}^{(l)}$.

Let $C=\max_{l}C_{l}$. Further, define
$\tilde{\alpha}=\sum_{i=1}^{L}\alpha_{i}$ with

$$ $\displaystyle\alpha_{i}=B_{i}^{2/3}c_{i}^{2/3}\left(\prod^{L}_{j=i+1}\rho_{j} \right)^{2/3}\left(C\sum^{i-1}_{j=0}\prod^{i}_{k=i-j+1}\rho_{k}+D\prod^{i}_{k= 1}\rho_{k}\right)^{2/3}.$ $$

The value of $\tilde{\alpha}$ indicates how complex the network is. It is influenced by the $l_{1}$ norm of the coefficient matrices (i.e., $B_{i}$) and is also affected by the product of the Lipschitz constants ($\rho_{l}$) for the activation functions at each layer. Note that for MLPs, the corresponding Lipschitz constants are equal to the spectral norms of the weight matrices. When $C=0$ (i.e., $C_{l}=0$ for all $1\leq l\leq L$), $\alpha_{i}=(B_{i}c_{i}D\prod_{j=1}^{L}\rho_{j})^{2/3}$ and

$$ $\tilde{\alpha}=\left(D\prod_{j=1}^{L}\rho_{j}\right)^{2/3}\sum^{L}_{i=1}(B_{i} c_{i})^{2/3}.$ $$

###### Theorem 1 .

Under Assumptions 1-2,

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),\epsilon,\|\cdot\|_ {2})\leq\frac{\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})}{\epsilon^{2}},$ $$

where $\tilde{d}=\max_{i}d_{i}$ and $\tilde{p}=\max_{i}p_{i}$.

It is worth noting that the above bound has no dependence on combinatorial parameters such as the number of nodes and the number of basis functions for each activation function outside of the logarithmic factor. Built upon the above results, we now derive a bound on the generalization error $R(f)$. We impose the following assumption on the loss function.

###### Assumption 3 .

Given $v\in\mathcal{Y}$,
$\mathcal{L}(\cdot,v)$ is
Lipschitz in the sense that
$|\mathcal{L}(u,v)-\mathcal{L}(u^{\prime},v)|\leq B(v)\|u-u^{\prime}\|_{2}$ for any $u,u^{\prime}\in\mathcal{Y}$ and $B(\cdot):\mathcal{Y}\rightarrow\mathbb{R}_{>0}$. Further suppose $\mathcal{L}(f(\cdot),\cdot)\in[0,M]$ for any $f\in\mathcal{M}$.

###### Theorem 2 .

Under Assumptions 1-3, we have with probability greater than $1-\epsilon$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{144\sqrt{\zeta}\{\log(nM/(3\sqrt{\zeta}))\vee 1\}}{n}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n}$ $$

for any $f\in\mathcal{M}$, where $\zeta=\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})\max_{i}B^{2}(y_{i})$.

Assumption 3 requires the loss to be bounded, which is satisfied by the ramp loss in multiclass classification. However, this excludes many other unbounded loss functions. By using a truncation argument, we can relax the boundedness condition on $\mathcal{L}$ in Assumption 3. This relaxation would allow the result below to cover a general class of nonparametric regression-type loss functions, including squared loss, pinball loss, and Huber loss.

###### Assumption 4 .

Given $v\in\mathcal{Y}$,
$\mathcal{L}(\cdot,v)$ is
Lipschitz in the sense that
$|\mathcal{L}(u,v)-\mathcal{L}(u^{\prime},v)|\leq B(v)\|u-u^{\prime}\|_{2}$ for any $u,u^{\prime}\in\mathcal{Y}$ and $B(\cdot):\mathcal{Y}\rightarrow\mathbb{R}_{>0}$. Further suppose $\sup_{f\in\mathcal{M}}|\mathcal{L}(f(\cdot),\cdot)|\leq G(\cdot,\cdot)$ and $\mathbb{E}[G^{s}({\mathbf{x}},y)]<C^{\prime}<\infty$ for $({\mathbf{x}},y)\sim P$ and some $s>1$, and $\mathbb{E}[B^{s^{\prime}}(y_{i})]<C^{\prime\prime}<\infty$ for $s^{\prime}>0.$

###### Theorem 3 .

Under Assumptions 1,2 and 4, we have with probability greater than $1-\epsilon-\tau-\eta$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{144\sqrt{\zeta_{0}}\{\log(n^{(2s+1)/(2s)}/(3\sqrt{\zeta_{0}}))\vee 1\}}{n}$ $\displaystyle+\frac{2\sqrt{\log(2/\epsilon)}}{n^{(s-1)/(2s)}}+\frac{32\log(2/ \epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{\eta n^{(s-1)/(2s)}}$ $$

for $\epsilon,\tau,\eta>0$ and any $f\in\mathcal{M}$, where $\zeta_{0}=\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})(nC^{\prime\prime}/\tau)^
{2/s^{\prime}}$.

As an implication of the above theorem, consider the empirical risk minimization problem in (2), where $\mathcal{M}=\{f(\cdot)=\bm{\Psi}_{L}\circ\bm{\Psi}_{L-1}\circ\cdots\circ\bm{
\Psi}_{1}(\cdot):\bm{\Psi}_{l}\in\mathcal{F}_{l},l=1,2,\dots,L\}$ with $\mathcal{F}_{l}$ specified in Assumption 2.
Due to the uniformity over the class $\mathcal{M}$, the risk bound in Theorem 3 holds for any solution to Problem (2) resulting from an optimization scheme (assuming that the resulting solution still belongs to $\mathcal{M}$).

Let $f^{*}=\text{argmin}_{f\in\mathcal{M}}\mathbb{E}[\mathcal{L}(f({\mathbf{x}}),y)]$ for $({\mathbf{x}},y)\sim P$ and $R(f^{*})$ be the corresponding generalization error. As a byproduct of Theorem 3, we obtain a bound on the excess risk.

###### Corollary 1 .

Let $\widehat{f}\in\mathcal{M}$ satisfy that $\sum^{n}_{i=1}\mathcal{L}(\widehat{f}({\mathbf{x}}_{i}),y_{i})\leq\sum^{n}_{i=
1}\mathcal{L}(f^{*}({\mathbf{x}}_{i}),y_{i})$. Suppose Assumptions 1,2 and 4 hold, where $s\geq 2$ in Assumption 4. We have with probability greater than $1-\epsilon-\tau-2\eta$,

$$ $\displaystyle R(\widehat{f})-R(f^{*})\leq$ $\displaystyle\frac{144\sqrt{\zeta_{0}}\{\log(n^{(2s+1)/(2s)}/(3\sqrt{\zeta_{0} }))\vee 1\}}{n}+(1+\eta^{-1/2})\sqrt{\frac{2(C^{\prime})^{2/s}\log(2/\epsilon) }{n}}$ $\displaystyle+\frac{32\log(2/\epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{ \eta n^{(s-1)/(2s)}},$ $$

for $\epsilon,\tau,\eta>0$, where $\zeta_{0}=\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})(nC^{\prime\prime}/\tau)^
{2/s^{\prime}}$.

The condition $\sum^{n}_{i=1}\mathcal{L}(\widehat{f}({\mathbf{x}}_{i}),y_{i})\leq\sum^{n}_{i=
1}\mathcal{L}(f^{*}({\mathbf{x}}_{i}),y_{i})$
only requires $\widehat{f}$ to have an empirical loss smaller than that induced by $f^{*}$ and it does not necessitate that $\widehat{f}$ be the global minimizer of Problem (2).

###### Proposition 1 .

###### Proposition 2 .

###### Assumption 1 .

###### Assumption 2 .

###### Remark 1 .

###### Remark 2 .

###### Remark 3 .

###### Remark 4 .

###### Remark 5 .

###### Theorem 1 .

###### Assumption 3 .

###### Theorem 2 .

###### Assumption 4 .

###### Theorem 3 .

###### Corollary 1 .

### 2.3 Risk analysis: activation functions in low-rank RKHS

This subsection studies the case where the activation function $\bm{\Psi}_{l}$ belongs to an RKHS with a low-rank structure.
Note that when $\bm{\Psi}_{l}({\mathbf{x}})=\mathbf{A}{\mathbf{x}}+\mathbf{b}$ is an affine map, the low-rank assumption translates into a low-rank condition on the matrix $\mathbf{A}$.

To proceed, we let $\mathcal{N}_{\mathcal{K}}(\Omega)$ be an RKHS on $\Omega\subseteq\mathbb{R}^{d}$ associated with a reproducing kernel $\mathcal{K}$. Denote by $\|\cdot\|_{\mathcal{N}_{\mathcal{K}}}$ the corresponding RKHS norm. We focus on the scenario where $\mathcal{K}$ is the isotropic Matérn kernel function, i.e.,

$$ $\displaystyle\mathcal{K}({\mathbf{x}})=\frac{1}{\Gamma(\nu-d/2)2^{\nu-d/2-1}} \|{\mathbf{x}}\|_{2}^{\nu-d/2}\mathcal{K}_{\nu-d/2}(\|{\mathbf{x}}\|_{2}),$ $$

after a proper reparametrization, where $\mathcal{K}_{\nu-d/2}$ is the modified Bessel function of the second kind, and $\|\cdot\|_{2}$ denotes the Euclidean norm. The parameter $\nu>d/2$ controls the smoothness of functions in $\mathcal{N}_{\mathcal{K}}(\Omega)$.
Corollary 10.13 in Wendland (), and the extension theorem in (DeVore & Sharpley, ) imply that the corresponding RKHS coincides with a Sobolev space with smoothness $\nu$. To model vector-valued functions, we consider the Cartesian product of $\mathcal{N}_{\mathcal{K}}(\Omega)$, denoted by $\mathcal{N}_{\mathcal{K}}^{\otimes m}(\Omega)$, given by

$$ $\displaystyle\mathcal{N}_{\mathcal{K}}^{\otimes m}(\Omega)=\left\{\bm{\Psi}=( \psi_{1},\dots,\psi_{m}):\psi_{i}\in\mathcal{N}_{\mathcal{K}}(\Omega),1\leq i \leq m\right\}.$ $$

Let $\text{span}(\psi_{1},\dots,\psi_{m})$ be the linear space spanned by $\{\psi_{i}\}^{m}_{i=1}$ and $\text{dim}(\text{span}(\psi_{1},\dots,\psi_{m}))$ be its dimension.
For $\bm{\Psi}=(\psi_{1},\dots,\psi_{m})\in\mathcal{N}_{\mathcal{K}}^{\otimes m}$, write $\|\bm{\Psi}\|_{\mathcal{N}_{\mathcal{K}}^{\otimes m}}^{2}=\sum^{m}_{i=1}\|\psi
_{i}\|_{\mathcal{N}_{\mathcal{K}}}^{2}$. Define

$$ $\displaystyle\mathcal{A}_{r}=\left\{\bm{\Psi}=(\psi_{1},\dots,\psi_{m})\in \mathcal{N}_{\mathcal{K}}^{\otimes m}:\text{dim}(\text{span}(\psi_{1},\dots, \psi_{m}))\leq r\right\}$ $$

and $\mathcal{A}_{r}(R)=\{\bm{\Psi}\in\mathcal{A}_{r}:\|\bm{\Psi}\|_{\mathcal{N}_{
\mathcal{K}}^{\otimes m}}\leq R\}$. Recall that $\bm{\Psi}({\mathbf{X}})=[\bm{\Psi}({\mathbf{x}}_{1}),\dots,\bm{\Psi}({\mathbf{
x}}_{n})]^{\top}$ and $\|\bm{\Psi}({\mathbf{X}})\|_{2}^{2}=\sum^{m}_{i=1}\sum^{n}_{j=1}\psi_{i}^{2}({
\mathbf{x}}_{j})$.

We state the following bound on the metric entropy of $\left\{\bm{\Psi}({\mathbf{X}})\in\mathbb{R}^{n\times m}:\bm{\Psi}\in\mathcal{A
}_{r}(R)\right\}$ whose proof relies on the equivalence between the RKHS and the Sobolev space.

###### Proposition 3 (Proposition A.3 of Wang & Zhou ( 2020 ) ) .

Under the above setups, we have

$$ $\displaystyle\log\mathcal{N}\left(\left\{\bm{\Psi}({\mathbf{X}})\in\mathbb{R}^ {n\times m}:\bm{\Psi}\in\mathcal{A}_{r}(R)\right\},\epsilon,\|\cdot\|_{2}\right)$ $\displaystyle\leq$ $\displaystyle mr\log\left(1+\frac{\widetilde{C}R\sqrt{rn}}{\epsilon}\right)+r \left(\frac{\widetilde{C}R\sqrt{rn}}{\epsilon}\right)^{d/\nu},$ $$

where $\widetilde{C}$ is a positive constant.

###### Assumption 5 .

Suppose $\bm{\Psi}_{l}$ belongs to the following function space

$$ $\mathcal{F}_{l}=\left\{\bm{\Psi}=(\psi_{1},\dots,\psi_{d_{l}})\in A_{r_{l}}(R_ {l}):\|\bm{\Psi}({\mathbf{x}})-\bm{\Psi}({\mathbf{x}}^{\prime})\|_{2}\leq\rho_ {l}\|{\mathbf{x}}-{\mathbf{x}}^{\prime}\|_{2}\right\},$ $$

where $\rho_{l},r_{l}$ and $R_{l}$ are some positive constants.

###### Proposition 4 .

Set $b_{i}=\widetilde{C}R_{i}\sqrt{r_{i}n}$ and $\tilde{b}=\sum^{L}_{i=1}b_{i}$. Under Assumption 5, we have

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),\epsilon,\|\cdot\|_ {2})\leq\sum^{L}_{i=1}d_{i}r_{i}\left(\frac{\tilde{b}\prod^{L}_{j=i+1}\rho_{j} }{\epsilon}\right)^{(d_{i-1}/\nu)\vee 1}.$ $$

###### Theorem 4 .

Define

$$ $\xi=\sum^{L}_{i=1}d_{i}r_{i}\left(\max_{i}B(y_{i})\tilde{b}\prod^{L}_{j=i+1} \rho_{j}\right)^{(d_{i-1}/\nu)\vee 1},$ $$

where $\tilde{b}=\sum^{L}_{i=1}b_{i}$ with $b_{i}=\widetilde{C}R_{i}\sqrt{r_{i}n}$.
Suppose $\tilde{d}:=\max_{i}d_{i}>\nu.$ Under Assumptions 3 and 5, we have with probability greater than $1-\epsilon$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{6\widetilde{C}^{\prime}(\xi)^{\nu/\tilde{d}}}{n^{(\nu/\tilde{d}+1)/2}( \tilde{d}/\nu-1)^{\nu/\tilde{d}}}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n}$ $$

for any $f\in\mathcal{M}$ and some constant $\widetilde{C}^{\prime}>0$.

Theorem 4 generalizes the results for low-rank kernel ridge regression to a multi-layer network structure induced by KANs with activation functions belonging to an RKHS.
The generalization bound here scales polynomially with the underlying ranks as well as the Lipschitz constants of the activation functions in each layer. Also, it has no explicit dependence on combinatorial parameters.

###### Remark 6 .

Given a set of (fixed) activation functions $\bm{\Phi}_{l}\in\mathcal{N}_{\mathcal{K}}^{\otimes{d_{l}}}$ for $1\leq l\leq L$,
we define the function class

$$ $\widetilde{\mathcal{F}}_{l}=\left\{\widetilde{\bm{\Psi}}=\bm{\Phi}_{l}+\bm{ \Psi}:\bm{\Psi}\in A_{r_{l}}(R_{l}),\|\widetilde{\bm{\Psi}}({\mathbf{x}})- \widetilde{\bm{\Psi}}({\mathbf{x}}^{\prime})\|_{2}\leq\rho_{l}\|{\mathbf{x}}-{ \mathbf{x}}^{\prime}\|_{2}\right\}.$ $$

Then, the conclusion in Theorem 4 remains true when the activation function in layer $l$ belongs to $\widetilde{\mathcal{F}}_{l}$. Suppose $\bm{\Phi}_{l}$ is an activation obtained from pre-training, and we perform a fine-tuning to find the activation functions for some new downstream tasks. Then, we require the update after the fine-tuning process to lie on a low-rank space $A_{r_{l}}(R_{l})$. This kind of strategy has been shown to be effective for fine-tuning large language models; see, e.g., (Hu et al., ).

To conclude this section, we present the following results that are parallel to Theorem 3 and Corollary 1. Let

$$ $\xi_{0}=\sum^{L}_{i=1}d_{i}r_{i}\left\{\left(\frac{nC^{\prime\prime}}{\tau} \right)^{2/s^{\prime}}\tilde{b}\prod^{L}_{j=i+1}\rho_{j}\right\}^{(d_{i-1}/\nu )\vee 1},$ (6) $$

where $\tilde{b}=\sum^{L}_{i=1}b_{i}$ with $b_{i}=\widetilde{C}R_{i}\sqrt{r_{i}n}$.

###### Theorem 5 .

Under Assumptions 4 and 5, we have with probability greater than $1-\epsilon-\tau-\eta$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{6\widetilde{C}^{\prime}(\xi_{0})^{\nu/\tilde{d}}}{n^{(\nu/\tilde{d}+1)/2 }(\tilde{d}/\nu-1)^{\nu/\tilde{d}}}$ $\displaystyle+\frac{2\sqrt{\log(2/\epsilon)}}{n^{(s-1)/(2s)}}+\frac{32\log(2/ \epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{\eta n^{(s-1)/(2s)}}$ $$

for any $f\in\mathcal{M}$ and $\epsilon,\tau,\eta,\widetilde{C}^{\prime}>0$.

###### Corollary 2 .

Let $\widehat{f}\in\mathcal{M}$ satisfy that $\sum^{n}_{i=1}\mathcal{L}(\widehat{f}({\mathbf{x}}_{i}),y_{i})\leq\sum^{n}_{i=
1}\mathcal{L}(f^{*}({\mathbf{x}}_{i}),y_{i})$. Suppose Assumptions 1,2 and 4 hold, where $s\geq 2$ in Assumption 4. We have with probability greater than $1-\epsilon-\tau-2\eta$,

$$ $\displaystyle R(\widehat{f})-R(f^{*})\leq$ $\displaystyle\frac{6\widetilde{C}^{\prime}(\xi_{0})^{\nu/\tilde{d}}}{n^{(\nu/ \tilde{d}+1)/2}(\tilde{d}/\nu-1)^{\nu/\tilde{d}}}(1+\eta^{-1/2})\sqrt{\frac{2( C^{\prime})^{2/s}\log(2/\epsilon)}{n}}$ $\displaystyle+\frac{32\log(2/\epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{ \eta n^{(s-1)/(2s)}},$ $$

for $\epsilon,\tau,\eta>0$, where $\xi_{0}$ is defined in (6).

###### Remark 7 .

Combining the arguments from Theorems 3 and 5, we can derive a generalization bound for KANs in the more general case. This applies when the activation functions of certain layers belong to the class in Assumption 2, while the activation functions of other layers have a low-rank structure, e.g., as specified in Remark 6.

###### Proposition 3 (Proposition A.3 of Wang & Zhou ( 2020 ) ) .

###### Assumption 5 .

###### Proposition 4 .

###### Theorem 4 .

###### Remark 6 .

###### Theorem 5 .

###### Corollary 2 .

###### Remark 7 .

## 3 Numerical Studies

We used both the simulated and real datasets to demonstrate the relationship between the excess loss and the complexity of KANs. We constructed the KANs such that the output of each layer at $\mathbf{0}$ is $\mathbf{0}$, i.e., $\bm{\Psi}_{i}(\mathbf{0})=\mathbf{0}$. Therefore, we used $(\prod_{j=1}^{L}\rho_{j})^{2/3}\sum^{L}_{i=1}(B_{i}c_{i})^{2/3},$
which was proportional to $\tilde{\alpha}$, as the measure of complexity, where the Lipschitz constants $\rho_{j}$s were estimated by their upper bounds provided in Remark 5.

For the simulation, we generated $x_{i}$ from $\sim\text{Unif}(-1,1)$ independently, and let

$$ $\displaystyle f_{1}(x_{1},x_{2},x_{3},x_{4})=\exp\left(\frac{1}{2}\left\{\sin( \pi(x_{1}^{2}+x_{2}^{2}))+\sin(\pi(x_{3}^{2}+x_{4}^{2}))\right\}\right),$ $\displaystyle f_{2}(x_{1},\dots,x_{100})=\exp\left\{\frac{1}{100}\sum_{i=1}^{1 00}\sin^{2}\left(\frac{\pi x_{i}}{2}\right)\right\},$ $$

for the low-dimensional and high-dimensional cases, respectively. We considered the following four setups:

$$ $\displaystyle\text{(i)}\;y=f_{1}(x_{1},x_{2},x_{3},x_{4})\times\exp(\epsilon), \quad\epsilon\sim N(-\log(1.04)/2,\log(1.04));$ $\displaystyle\text{(ii)}\;y=f_{2}(x_{1},\dots,x_{100})\times\exp(\epsilon), \quad\epsilon\sim N(-\log(1.04)/2,\log(1.04));$ $\displaystyle\text{(iii)}\;P(y=1)=\frac{1}{1+f_{1}(x_{1},x_{2},x_{3},x_{4})}, \quad P(y=0)=1-P(y=1);$ $\displaystyle\text{(iv)}\;P(y=1)=\frac{1}{1+f_{2}(x_{1},\dots,x_{100})},\quad P (y=0)=1-P(y=1),$ $$

where we have chosen the distribution of $\epsilon$ such that the mean and standard deviation of $\exp(\epsilon)$ are equal to 1 and 0.2, respectively. We set the sample sizes of both the training set and test set to be 10,000 for all four datasets. The shape of KAN used for (i) and (iii) was $[4,50,100,50,1]$, and was $[100,50,100,50,1]$ for (ii) and (iv). We refer the readers to Section 2.2 of Liu et al. () for the definition of the shape of a KAN that is represented by an integer array.

We also investigated the MNIST and CIFAR-10 datasets. We used the features extracted from a pre-trained AlexNet model as input for the KANs. The extracted features were 1000-dimensional for both datasets. We employed the KAN with the shape $[1000,50,100,50,10]$.

We run 1000 epochs for each dataset. The results are shown in Figure 2, where we normalize the values of the complexity measures (note that the normalization does not affect the shape of the KAN complexity curve) so that the two curves can be presented in the same plot. The plots in Figure 2 illustrate that our proposed measure of complexity for the KAN networks, $\tilde{\alpha}$, tightly correlates with the excess loss in all the cases. It is surprising to observe that the complexity measure curve closely follows the shape of the excess loss. These results highlight the practical relevance of the generalization bounds derived in Section 2.

Figure: Figure 2: The excess loss and (normalized) complexity of KANs trained with SGD on the four simulated datasets (i–iv) and the MNIST and CIFAR10 datasets. The loss for (iii), (iv), MNIST, and CIFAR10 is the cross-entropy loss, and that for (i) and (ii) is the mean squared error.
Refer to caption: x2.png

## 4 Discussions

We derive generalization bounds for KANs when the activation functions are either represented by linear combinations of basis functions or lying in a low-rank RKHS. These bounds are empirically investigated for the KAN networks trained with SGD on simulated and real data sets. The numerical results indicate a strong correlation between the excess loss and the complexity measure, demonstrating the practical relevance of the generalization bounds.

To conclude, we mention a few future research directions. (i) It would be interesting to derive a lower bound and see how well it matches the upper bound. Also, additional work is needed to determine which norms are well-adapted to KANs as used in practice; (ii) A more careful analysis is needed to show that SGD applied to KAN results in a well-behaved predictor and leads to a refined generalization bound; (iii) Theorem 3 may be improved with a relaxed restriction on the Lipschitz constants of the basis functions $\{g_{ij}^{(l)}\}$; (iv) It was observed that explicit regularization contributes little to the generalization performance of neural networks (Zhang et al., ). It is of interest to see if a similar conclusion holds for KANs and whether other types of regularization help to improve the generalization performance.

## Appendix A Appendix

### A.1 Auxiliary lemmas

The following lemma is useful in the proof of Proposition 2; see Lemma 1 of Zhang () and Lemma A.6 of Bartlett et al. ().

###### Lemma 1 (Maurey’s sparsification lemma) .

For a Hilbert space $\mathcal{H}$ with the norm $\|\cdot\|$, let $U\in\mathcal{H}$ be given with the representation $U=\sum^{N}_{l=1}a_{l}V_{l}$, where $V_{l}\in\mathcal{H}$ and $a_{l}\geq 0$. Then, for any positive integer $k$, there exists a choice of nonnegative integers $(k_{1},\dots,k_{N})$ such that $\sum_{i=1}^{N}k_{i}=k$ and

$$ $\displaystyle\left\|U-\frac{\|\mathbf{a}\|_{1}}{k}\sum^{N}_{l=1}k_{l}V_{l} \right\|^{2}\leq\frac{\|\mathbf{a}\|_{1}}{k}\sum^{N}_{l=1}a_{l}\|V_{l}\|^{2} \leq\frac{\|\mathbf{a}\|_{1}^{2}}{k}\max_{i}\|V_{i}\|^{2},$ $$

where $\mathbf{a}=(a_{1},\dots,a_{N})$ and $\|\mathbf{a}\|_{1}=\sum^{N}_{l=1}a_{l}$.

The proof of Theorem 2 makes use of the following two lemmas. The first lemma shows that $R(f)$ can be related to the empirical Rademacher complexity of the neural network function class. The second lemma connects the empirical Rademacher complexity with the corresponding covering number through the integral entropy.

###### Lemma 2 (Theorem 2.1 in Bartlett et al. ( 2005 ) ) .

Let $\mathcal{F}$ be a class of functions that maps $\mathcal{X}$ into $[-M,M]$ for some $M>0$. Assume that there is some $r\geq 0$ such that for every $f\in\mathcal{F}$, $\text{var}(f(\mathbf{x}))\leq r$. Then for every $\epsilon>0$, with probability at least $1-\epsilon$ over the data ${\mathbf{X}}=[{\mathbf{x}}_{1},\dots,{\mathbf{x}}_{n}]^{\top}$, we have

$$ $\displaystyle\sup_{f\in\mathcal{F}}\left\{\mathbb{E}[f({\mathbf{x}})]-\frac{1} {n}\sum^{n}_{i=1}f({\mathbf{x}}_{i})\right\}\leq 6\mathcal{R}(\mathcal{F}({ \mathbf{X}}))+\sqrt{\frac{2r\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon)}{3 n},$ $$

where $\mathcal{F}({\mathbf{X}})=\{(f({\mathbf{x}}_{1}),\dots,f({\mathbf{x}}_{n})):f
\in\mathcal{F}\}$ and $\mathcal{R}(\mathcal{F}({\mathbf{X}}))$ is the empirical Rademacher complexity of $\mathcal{F}$, i.e.,

$$ $\mathcal{R}(\mathcal{F}({\mathbf{X}}))=\frac{1}{n}\mathbb{E}\left[\sup_{f\in \mathcal{F}}\sum^{n}_{i=1}e_{i}f({\mathbf{x}}_{i})\Big{|}{\mathbf{X}}\right],$ $$

with $e_{i}$ being a set of independent Rademacher random variables, i.e., $P(e_{i}=\pm 1)=1/2.$

###### Lemma 3 (Lemma A.5 in Bartlett et al. ( 2017 ) ) .

Let $\mathcal{F}$ be a real-valued function class taking values in $[0,M]$ and assume that $\mathbf{0}\in\mathcal{F}$. Then we have

$$ $\displaystyle\mathcal{R}(\mathcal{F}({\mathbf{X}}))\leq\inf_{a>0}\left(\frac{4 a}{\sqrt{n}}+\frac{12}{n}\int^{M\sqrt{n}}_{a}\sqrt{\log\mathcal{N}(\mathcal{F} ({\mathbf{X}}),\epsilon,\|\cdot\|_{2})}d\epsilon\right).$ $$

###### Lemma 1 (Maurey’s sparsification lemma) .

###### Lemma 2 (Theorem 2.1 in Bartlett et al. ( 2005 ) ) .

###### Lemma 3 (Lemma A.5 in Bartlett et al. ( 2017 ) ) .

### A.2 Proofs of the main results

###### Proof of Proposition 1 .

We divide the proof into three steps.
Step 1: Choose an $\epsilon_{1}$ cover $\mathcal{N}_{1}$ of
$\{\bm{\Psi}({\mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{1}\}$. Then we have

$$ $\displaystyle|\mathcal{N}_{1}|\leq\mathcal{N}\left(\{\bm{\Psi}({\mathbf{X}}): \bm{\Psi}\in\mathcal{F}_{1}\},\epsilon_{1},|\cdot|_{1}\right):=N_{1}.$ $$

Step 2: For every $\bm{\Phi}\in\mathcal{N}_{i}$, we construct an $\epsilon_{i+1}$ cover $\mathcal{G}_{i+1}(\bm{\Phi})$ of
$\{\bm{\Psi}(\bm{\Phi}):\bm{\Psi}\in\mathcal{F}_{i+1}\}$. Since the covers are proper, we have $\bm{\Phi}=\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots\circ\bm{\Psi}_{0}({
\mathbf{X}})$ for some $(\bm{\Psi}_{i},\dots,\bm{\Psi}_{1})\in\mathcal{F}_{i}\times\mathcal{F}_{i-1}
\times\cdots\times\mathcal{F}_{1}$ and $\mathcal{G}_{i+1}(\bm{\Phi})\subset\mathcal{H}_{i+1}({\mathbf{X}})$. Thus, we must have

$$ $\displaystyle|\mathcal{G}_{i+1}(\bm{\Phi})|\leq\sup_{\bm{\Psi}_{1},\dots,\bm{ \Psi}_{i}}\mathcal{N}(\{\bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ \cdots\circ\bm{\Psi}_{0}({\mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{i+1}\}, \epsilon_{i+1},|\cdot|_{i+1}):=N_{i+1}.$ $$

Finally, we form the cover

$$ $\mathcal{N}_{i+1}=\cup_{\bm{\Phi}\in\mathcal{N}_{i}}\mathcal{G}_{i+1}(\bm{\Phi }),$ $$

which satisfies that

$$ $|\mathcal{N}_{i+1}|\leq|\mathcal{N}_{i}|N_{i+1}\leq\prod^{i+1}_{j=1}N_{j}.$ $$

Step 3:
By the definition of $s_{i}$, we have $s_{i}\rho_{i+1}+\epsilon_{i+1}=s_{i+1}$. We shall prove (3) using induction. By construction, we can find $\tilde{f}_{1}\in\mathcal{N}_{1}$ such that

$$ $|\tilde{f}_{1}({\mathbf{X}})-\bm{\Psi}_{1}\circ\bm{\Psi}_{0}({\mathbf{X}})|_{1 }\leq\epsilon_{1}=s_{1}.$ $$

Now suppose we can find $\tilde{f}_{i}\in\mathcal{N}_{i}$ such that

$$ $\displaystyle|\tilde{f}_{i}({\mathbf{X}})-\bm{\Psi}_{i}\circ\cdots\circ\bm{ \Psi}_{0}({\mathbf{X}})|_{i}\leq s_{i}.$ $$

By the construction of $\mathcal{N}_{i+1}$, given $\tilde{f}_{i}\in\mathcal{N}_{i}$ and $\bm{\Psi}_{i+1}\in\mathcal{F}_{i+1}$, we can find $\tilde{f}_{i+1}\in\mathcal{N}_{i+1}$ such that

$$ $\displaystyle|\tilde{f}_{i+1}({\mathbf{X}})-\bm{\Psi}_{i+1}\circ\tilde{f}_{i}( {\mathbf{X}})|_{i+1}\leq\epsilon_{i+1}.$ $$

Then, by the triangle inequality, we have

$$ $\displaystyle|\tilde{f}_{i+1}({\mathbf{X}})-\bm{\Psi}_{i+1}\circ\bm{\Psi}_{i} \circ\cdots\circ\bm{\Psi}_{0}({\mathbf{X}})|_{i+1}$ $\displaystyle\leq$ $\displaystyle|\tilde{f}_{i+1}({\mathbf{X}})-\bm{\Psi}_{i+1}\circ\tilde{f}_{i}( {\mathbf{X}})|_{i+1}+|\bm{\Psi}_{i+1}\circ\tilde{f}_{i}({\mathbf{X}})-\bm{\Psi }_{i+1}\circ\bm{\Psi}_{i}\circ\cdots\circ\bm{\Psi}_{0}({\mathbf{X}})|_{i+1}$ $\displaystyle\leq$ $\displaystyle\epsilon_{i+1}+\rho_{i+1}|\tilde{f}_{i}({\mathbf{X}})-\bm{\Psi}_{ i}\circ\cdots\circ\bm{\Psi}_{0}({\mathbf{X}})|_{i+1}$ $\displaystyle\leq$ $\displaystyle\epsilon_{i+1}+\rho_{i+1}s_{i}=s_{i+1}.$ $$

The conclusion thus follows.
∎

###### Proof Proposition 2 .

Let $E_{ij}({\mathbf{X}})\in\mathbb{R}^{n\times m}$, where its $i$th column equals $(g_{ij}({\mathbf{x}}_{1})/b_{ij},\dots,g_{ij}({\mathbf{x}}_{n})/b_{ij})^{\top}$
with $b_{ij}=(\sum_{k=1}^{n}|g_{ij}({\mathbf{x}}_{k})|^{v})^{1/v}$
and all the other elements are equal to zero. Further, define the set

$$ $\displaystyle\{V_{1},\dots,V_{N}\}=\left\{\tau E_{ij}({\mathbf{X}}):\tau\in\{- 1,1\},1\leq i\leq m,1\leq j\leq p\right\},$ $$

where $N=2mp$. We can view $V_{i}$’s as elements in the Hilbert space $\mathbb{R}^{n\times m}$ equipped with the inner product $\langle A,\widetilde{A}\rangle=\text{trace}(A^{\top}\widetilde{A})$ and norm $\|A\|_{2}$ for $A,\widetilde{A}\in\mathbb{R}^{n\times m}$. We have

$$ $\displaystyle\bm{\Psi}({\mathbf{X}})=\sum^{m}_{i=1}\sum^{p}_{j=1}\tau_{ij}b_{ ij}|\beta_{ij}|E_{ij}({\mathbf{X}})=\sum^{N}_{l=1}\alpha_{l}V_{l},$ $$

for $\alpha_{l}\geq 0$ and $\tau_{ij}=\text{sign}(\beta_{ij})$. Note that

$$ $\displaystyle\max_{1\leq i\leq N}\|V_{i}\|_{2}=\max_{1\leq i\leq m,1\leq j\leq p }\frac{(\sum_{k=1}^{n}|g_{ij}({\mathbf{x}}_{k})|^{2})^{1/2}}{(\sum_{k=1}^{n}|g _{ij}({\mathbf{x}}_{k})|^{v})^{1/v}}\leq 1,$ $$

and

$$ $\displaystyle\|\mathbf{a}\|_{1}=\sum^{N}_{l=1}|a_{l}|=\sum^{m}_{i=1}\sum^{p}_{ j=1}b_{ij}|\beta_{ij}|\leq\|\mathbf{G}({\mathbf{X}})\|_{v,s}\|\mathbf{B}\|_{r} \leq b_{m,p,n}c_{m,p,n},$ $$

where $1/s+1/r=1$ and $s,r>0.$ Therefore, $\bm{\Psi}({\mathbf{X}})\in\{b_{m,p,n}c_{m,p,n}\sum^{N}_{l=1}a_{l}V_{l}:a_{l}
\geq 0,\sum_{l}a_{l}=1\}$ (this is because the convex hull of $\{V_{1},\dots,V_{N}\}$ always contains the origin).
Now we define

$$ $\displaystyle\mathcal{C}_{k}=$ $\displaystyle\left\{\frac{b_{m,p,n}c_{m,p,n}}{k}\sum^{N}_{i=1}k_{i}V_{i}:k_{i} \geq 0,\sum^{N}_{i=1}k_{i}=k\right\}$ $\displaystyle=$ $\displaystyle\left\{\frac{b_{m,p,n}c_{m,p,n}}{k}\sum^{k}_{j=1}V_{i_{j}}:(i_{1} ,\dots,i_{k})\in[N]^{k}\right\}.$ $$

By construction, $|\mathcal{C}_{k}|\leq N^{k}$. Using Lemma 1, there exists nonnegative integers $(k_{1},\dots,k_{N})$ with $\sum_{i=1}^{N}k_{i}=k$ such that

$$ $\displaystyle\left\|\bm{\Psi}({\mathbf{X}})-\frac{b_{m,p,n}c_{m,p,n}}{k}\sum^{ N}_{i=1}k_{i}V_{i}\right\|_{2}^{2}\leq\frac{b_{m,p,n}^{2}c_{m,p,n}^{2}}{k}\max _{1\leq i\leq N}\|V_{i}\|^{2}=\frac{b_{m,p,n}^{2}c_{m,p,n}^{2}}{k}.$ $$

By setting $\epsilon^{2}=b_{m,p,n}^{2}c_{m,p,n}^{2}/k$, $\mathcal{C}_{k}$ forms an $\epsilon$ cover of $\left\{\bm{\Psi}({\mathbf{X}})\in\mathbb{R}^{n\times m}:\bm{\Psi}\in\mathcal{F
}\right\}$ and the result follows.
∎

###### Proof of Theorem 1 .

Given $(\bm{\Psi}_{1},\dots,\bm{\Psi}_{l-1})\in\mathcal{F}_{1}\times\cdots\times
\mathcal{F}_{l-1}$,
we define ${\mathbf{X}}^{(l-1)}(\bm{\Psi}_{1},\dots,\bm{\Psi}_{l-1})=[{\mathbf{x}}_{1}^{(
l-1)},\dots,{\mathbf{x}}_{n}^{(l-1)}]^{\top}$, where ${\mathbf{x}}_{k}^{(l-1)}=\bm{\Psi}_{l-1}\circ\bm{\Psi}_{l-2}\circ\cdots\circ
\bm{\Psi}_{0}({\mathbf{x}}_{k})$ for $1\leq k\leq n$.
Then, we have

$$ $\|\mathbf{G}^{(l)}({\mathbf{X}}^{(l-1)}(\bm{\Psi}_{1},\dots,\bm{\Psi}_{l-1}))- \mathbf{G}^{(l)}(\mathbf{0})\|_{\infty,2}=\max_{i,j}\left(\sum^{n}_{k=1}|g_{ij }^{(l)}({\mathbf{x}}_{k}^{(l-1)})-g_{ij}^{(l)}(\mathbf{0})|^{2}\right)^{1/2}$ $$

for $\mathbf{G}^{(l)}({\mathbf{X}})=(g_{ij}^{(l)}({\mathbf{x}}_{k}))\in\mathbb{R}^{
d_{l}\times p_{l}\times n}$.
We note that

$$ $\displaystyle\|\mathbf{G}^{(l)}({\mathbf{X}}^{(l-1)}(\bm{\Psi}_{1},\dots,\bm{ \Psi}_{l-1}))-\mathbf{G}^{(l)}(\mathbf{0})\|_{2}$ $\displaystyle\leq$ $\displaystyle c_{l}\|\bm{\Psi}_{l}(\bm{\Psi}_{l-1}\circ\cdots\circ\bm{\Psi}_{0 }({\mathbf{X}}))\|_{2}$ $\displaystyle\leq$ $\displaystyle c_{l}\left(\|\bm{\Psi}_{l}(\bm{\Psi}_{l-1}\circ\cdots\circ\bm{ \Psi}_{0}({\mathbf{X}}))-\bm{\Psi}_{l}(\mathbf{0})\|_{2}+\|\bm{\Psi}_{l}( \mathbf{0})\|_{2}\right)$ $\displaystyle\leq$ $\displaystyle c_{l}\left(\rho_{l}\|\bm{\Psi}_{l-1}\circ\cdots\circ\bm{\Psi}_{0 }({\mathbf{X}})\|_{2}+\|\bm{\Psi}_{l}(\mathbf{0})\|_{2}\right)$ $\displaystyle\leq$ $\displaystyle c_{l}\left(\sum^{l-1}_{j=0}\|\bm{\Psi}_{l-j}(\mathbf{0})\|_{2} \prod^{l}_{i=l-j+1}\rho_{i}+\|{\mathbf{X}}\|_{2}\prod^{l}_{i=1}\rho_{i}\right)$ $\displaystyle\leq$ $\displaystyle c_{l}\left(C\sum^{l-1}_{j=0}\prod^{l}_{i=l-j+1}\rho_{i}+D\prod^{ l}_{i=1}\rho_{i}\right).$ $$

By Proposition 1, we have

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),s_{L},\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle\sum^{L-1}_{i=0}\sup_{\bm{\Psi}_{1},\dots,\bm{\Psi}_{i}}\log \mathcal{N}(\{\bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots\circ \bm{\Psi}_{0}({\mathbf{x}}):\bm{\Psi}\in\mathcal{F}_{i+1}\},\epsilon_{i+1},\| \cdot\|_{2})$ $\displaystyle=$ $\displaystyle\sum^{L-1}_{i=0}\sup_{\bm{\Psi}_{1},\dots,\bm{\Psi}_{i}}\log \mathcal{N}(\{\bar{\bm{\Psi}}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots \circ\bm{\Psi}_{0}({\mathbf{x}}):\bm{\Psi}\in\mathcal{F}_{i+1}\},\epsilon_{i+1 },\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle\sum^{L}_{i=1}\frac{\|B_{i}\|_{1}^{2}c_{i}^{2}\left(C\sum^{i-1}_{ j=0}\prod^{i}_{k=i-j+1}\rho_{k}+D\prod^{i}_{k=1}\rho_{k}\right)^{2}}{\epsilon^ {2}_{i}}\log(2d_{i}p_{i})$ $$

where $\bar{\bm{\Psi}}(\cdot)=\bm{\Psi}(\cdot)-\bm{\Psi}(\mathbf{0})$. For any $\epsilon>0$, set

$$ $\displaystyle\epsilon_{i}=\frac{\alpha_{i}\epsilon}{\tilde{\alpha}\prod^{L}_{j =i+1}\rho_{j}}.$ $$

Then, we have $s_{L}=\sum^{L}_{i=1}\left(\prod^{L}_{j=i+1}\rho_{j}\right)\epsilon_{i}=\epsilon$ and hence

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),\epsilon,\|\cdot\|_ {2})\leq\frac{\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})}{\epsilon^{2}}.$ $$

∎

###### Proof of Theorem 2 .

Define the class
$\mathcal{M}_{\mathcal{L}}({\mathbf{X}})=\{(\mathcal{L}(f({\mathbf{x}}_{1}),y_{
1}),\dots,\mathcal{L}(f({\mathbf{x}}_{n}),y_{n})):f\in\mathcal{M}\}$. By Assumption 3, we have

$$ $\displaystyle\log\mathcal{N}(\mathcal{M}_{\mathcal{L}}({\mathbf{X}}),\epsilon, \|\cdot\|_{2})\leq\frac{\tilde{\alpha}^{3}\log(2\tilde{d}\tilde{p})\max_{i}B^{ 2}(y_{i})}{\epsilon^{2}}=\frac{\zeta}{\epsilon^{2}}.$ $$

Lemma 3 implies that

$$ $\displaystyle\mathcal{R}(\mathcal{M}_{\mathcal{L}}({\mathbf{X}}))\leq$ $\displaystyle\inf_{a>0}\left(\frac{4a}{\sqrt{n}}+\frac{12}{n}\int^{\sqrt{n}M}_ {a}\sqrt{\frac{\zeta}{\epsilon^{2}}}d\epsilon\right)$ $\displaystyle=$ $\displaystyle\inf_{a>0}\left(\frac{4a}{\sqrt{n}}+\frac{12\sqrt{\zeta}}{n}\log( M\sqrt{n}/a)\right)$ $\displaystyle\leq$ $\displaystyle\frac{12\sqrt{\zeta}}{n}+\frac{12\sqrt{\zeta}\log(nM/(3\sqrt{ \zeta}))}{n}$ $\displaystyle\leq$ $\displaystyle\frac{24\sqrt{\zeta}\{\log(nM/(3\sqrt{\zeta}))\vee 1\}}{n}.$ $$

Using Lemma 2 with $r=2M^{2}$, we have with probability greater than $1-\epsilon$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{144\sqrt{\zeta}\{\log(nM/(3\sqrt{\zeta}))\vee 1\}}{n}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n},$ $$

for any $f\in\mathcal{M}$.
∎

###### Proof of Theorem 3 .

Define the class
$\mathcal{M}_{\mathcal{L},M}({\mathbf{X}})=\{(\mathcal{L}(f({\mathbf{x}}_{1}),y
_{1})\wedge M,\dots,\mathcal{L}(f({\mathbf{x}}_{n}),y_{n})\wedge M):f\in
\mathcal{M}\}$.
Following the arguments in the proof of Theorem 2 with $\mathcal{M}_{\mathcal{L}}({\mathbf{X}})$ replaced by $\mathcal{M}_{\mathcal{L},M}({\mathbf{X}})$, we can show that
with probability greater than $1-\epsilon$,

$$ $\displaystyle\mathbb{E}[\mathcal{L}(f({\mathbf{x}}),y)\wedge M]\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i}) \wedge M+\frac{144\sqrt{\zeta}\{\log(nM/(3\sqrt{\zeta}))\vee 1\}}{n}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n}.$ $$

We first note that

$$ $\displaystyle P(\max_{i}B^{2}(y_{i})>\varepsilon)\leq\sum^{n}_{i=1}P(B(y_{i})> \sqrt{\varepsilon})\leq\frac{nC^{\prime\prime}}{\varepsilon^{s^{\prime}/2}}.$ $$

Setting $\varepsilon=(nC^{\prime\prime}/\tau)^{2/s^{\prime}}$, we have $\zeta\leq\zeta_{0}$ with probability greater than $1-\tau$.
Next, under Assumption 4, we have

$$ $\displaystyle|R(f)-\mathbb{E}[\mathcal{L}(f({\mathbf{x}}),y)\wedge M]|\leq$ $\displaystyle\mathbb{E}[(\mathcal{L}(f({\mathbf{x}}),y)-M)\mathbf{1}\{\mathcal {L}(f({\mathbf{x}}),y)>M\}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[G({\mathbf{x}},y)\mathbf{1}\{G({\mathbf{x}},y)>M\}] \leq\frac{C^{\prime}}{M^{s-1}}.$ $$

Moreover,

$$ $\displaystyle\left|\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_ {i})-\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})\wedge M \right|\leq\frac{1}{n}\sum^{n}_{i=1}Z_{i},$ $$

where $Z_{i}=G({\mathbf{x}}_{i},y_{i})\mathbf{1}\{G({\mathbf{x}}_{i},y_{i})>M\}$. As

$$ $\displaystyle P\left(\frac{1}{n}\sum^{n}_{i=1}Z_{i}>\varepsilon\right)\leq \frac{C^{\prime}}{\varepsilon M^{s-1}},$ $$

the conclusion follows by setting $\varepsilon=C^{\prime}/(\eta M^{s-1})$ and $M=n^{1/(2s)}$.
∎

###### Remark 8 .

When $s\geq 2$, we note that $\text{var}(\mathcal{L}(f({\mathbf{x}}),y))\leq\mathbb{E}[G^{2}({\mathbf{x}},y)
]\leq(\mathbb{E}[G^{s}({\mathbf{x}},y)])^{2/s}\leq(C^{\prime})^{2/s}$.
Thus by Lemma 2 with $r=(C^{\prime})^{2/s}$, the term $\frac{2\sqrt{\log(2/\epsilon)}}{n^{(s-1)/(2s)}}$ in Theorem 3 can be replaced by $\sqrt{\frac{2(C^{\prime})^{2/s}\log(2/\epsilon)}{n}}$,
leading to the risk-bound

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{144\sqrt{\zeta_{0}}\{\log(n^{(2s+1)/(2s)}/(3\sqrt{\zeta_{0}}))\vee 1\}}{n}$ $\displaystyle+\sqrt{\frac{2(C^{\prime})^{2/s}\log(2/\epsilon)}{n}}+\frac{32 \log(2/\epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{\eta n^{(s-1)/(2s)}}.$ $$

###### Proof of Corollary 1 .

By Remark 8 and the definition of $\widehat{f}$,
we have with probability greater than $1-\epsilon-\tau-\eta$,

$$ $\displaystyle R(\widehat{f})\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f^{*}({\mathbf{x}}_{i}),y_{i })+\frac{144\sqrt{\zeta_{0}}\{\log(n^{(2s+1)/(2s)}/(3\sqrt{\zeta_{0}}))\vee 1 \}}{n}$ $\displaystyle+\sqrt{\frac{2(C^{\prime})^{2/s}\log(2/\epsilon)}{n}}+\frac{32 \log(2/\epsilon)}{3n^{(2s-1)/(2s)}}+\frac{2C^{\prime}}{\eta n^{(s-1)/(2s)}}.$ $$

Note that

$$ $\displaystyle P\left(\left|\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f^{*}({\mathbf {x}}_{i}),y_{i})-R(f^{*})\right|>\varepsilon\right)\leq\frac{\text{var}( \mathcal{L}(f^{*}({\mathbf{x}}),y))}{n\epsilon^{2}}\leq\frac{\mathbb{E}[G^{2}( {\mathbf{x}},y)]}{n\epsilon^{2}}\leq\frac{(C^{\prime})^{2/s}}{n\epsilon^{2}}.$ $$

The conclusion follows by setting $\varepsilon=\sqrt{(C^{\prime})^{2/s}/(n\eta)}$.
∎

###### Proof of Proposition 4 .

The results follow from Propositions 1 and 3. In particular,
by Proposition 1, we have

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),s_{L},\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle\sum^{L-1}_{i=0}\sup_{\bm{\Psi}_{1},\dots,\bm{\Psi}_{i}}\log \mathcal{N}(\{\bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1}\circ\cdots\circ \bm{\Psi}_{0}({\mathbf{X}}):\bm{\Psi}\in\mathcal{F}_{i+1}\},\epsilon_{i+1},\| \cdot\|_{2}),$ $$

where $\mathcal{F}_{i+1}$ is defined in Assumption 5.
By Proposition 3,

$$ $\displaystyle\log\mathcal{N}(\{\bm{\Psi}\circ\bm{\Psi}_{i}\circ\bm{\Psi}_{i-1} \circ\cdots\circ\bm{\Psi}_{0}({\mathbf{X}}):\bm{\Psi}\in A_{r_{i+1}}(R_{i+1}) \},\epsilon_{i+1},\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle d_{i+1}r_{i+1}\log\left(1+\frac{\widetilde{C}R_{i+1}\sqrt{r_{i+1 }n}}{\epsilon_{i+1}}\right)+r_{i+1}\left(\frac{\widetilde{C}R_{i+1}\sqrt{r_{i+ 1}n}}{\epsilon_{i+1}}\right)^{d_{i}/\nu}$ $$

uniformly over all $\bm{\Psi}_{1},\dots,\bm{\Psi}_{i}$.
For any $\epsilon>0$, set

$$ $\displaystyle\epsilon_{i}=\frac{b_{i}\epsilon}{\tilde{b}\prod^{L}_{j=i+1}\rho_ {j}}.$ $$

Then, we have $s_{L}=\sum^{L}_{i=1}\left(\prod^{L}_{j=i+1}\rho_{j}\right)\epsilon_{i}=\epsilon$ and for small enough $\epsilon$,

$$ $\displaystyle\log\mathcal{N}(\mathcal{H}_{L}({\mathbf{X}}),\epsilon,\|\cdot\|_ {2})\leq$ $\displaystyle\sum^{L}_{i=1}\left\{d_{i}r_{i}\log\left(1+\frac{\tilde{b}\prod^{ L}_{j=i+1}\rho_{j}}{\epsilon}\right)+r_{i}\left(\frac{\tilde{b}\prod^{L}_{j=i+ 1}\rho_{j}}{\epsilon}\right)^{d_{i-1}/\nu}\right\}$ $\displaystyle\leq$ $\displaystyle\sum^{L}_{i=1}d_{i}r_{i}\left(\frac{\tilde{b}\prod^{L}_{j=i+1} \rho_{j}}{\epsilon}\right)^{(d_{i-1}/\nu)\vee 1},$ $$

where we have used the fact that $\log(1+x)\leq x$ for $x\geq 0.$
∎

###### Proof of Theorem 4 .

Recall
$\mathcal{M}_{\mathcal{L}}({\mathbf{X}})=\{(\mathcal{L}(f({\mathbf{x}}_{1}),y_{
1}),\dots,\mathcal{L}(f({\mathbf{x}}_{n}),y_{n})):f\in\mathcal{M}\}$. By Assumption 3, we have

$$ $\displaystyle\log\mathcal{N}(\mathcal{M}_{\mathcal{L}}({\mathbf{X}}),\epsilon, \|\cdot\|_{2})\leq\sum^{L}_{i=1}d_{i}r_{i}\left(\frac{\max_{i}B(y_{i})\tilde{b }\prod^{L}_{j=i+1}\rho_{j}}{\epsilon}\right)^{(d_{i-1}/\nu)\vee 1}\leq\frac{ \xi}{\epsilon^{\tilde{d}/\nu}}.$ $$

Lemma 3 implies that

$$ $\displaystyle\mathcal{R}(\mathcal{M}_{\mathcal{L}}({\mathbf{X}}))\leq$ $\displaystyle\inf_{a>0}\left(\frac{4a}{\sqrt{n}}+\frac{12}{n}\int^{\sqrt{n}M}_ {a}\frac{\xi}{\epsilon^{\tilde{d}/\nu}}d\epsilon\right)$ $\displaystyle=$ $\displaystyle\inf_{a>0}\left(\frac{4a}{\sqrt{n}}+\frac{12\xi}{n}\frac{a^{1- \tilde{d}/\nu}-(\sqrt{n}M)^{1-\tilde{d}/\nu}}{\tilde{d}/\nu-1}\right)$ $\displaystyle\leq$ $\displaystyle\frac{\widetilde{C}^{\prime}(\xi)^{\nu/\tilde{d}}}{n^{(\nu/\tilde {d}+1)/2}(\tilde{d}/\nu-1)^{\nu/\tilde{d}}}$ $$

for some constant $\widetilde{C}^{\prime}>0.$
Using Lemma 2 with $r=2M^{2}$, we have with probability greater than $1-\epsilon$,

$$ $\displaystyle R(f)\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i})+ \frac{6\widetilde{C}^{\prime}(\xi)^{\nu/\tilde{d}}}{n^{(\nu/\tilde{d}+1)/2}( \tilde{d}/\nu-1)^{\nu/\tilde{d}}}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n}$ $$

for any $f\in\mathcal{M}$.
∎

###### Proof of Theorem 5 .

Define the class
$\mathcal{M}_{\mathcal{L},M}({\mathbf{X}})=\{(\mathcal{L}(f({\mathbf{x}}_{1}),y
_{1})\wedge M,\dots,\mathcal{L}(f({\mathbf{x}}_{n}),y_{n})\wedge M):f\in
\mathcal{M}\}$.
Following the arguments in the proof of Theorem 4 with $\mathcal{M}_{\mathcal{L}}({\mathbf{X}})$ replaced by $\mathcal{M}_{\mathcal{L},M}({\mathbf{X}})$, we have
with probability greater than $1-\epsilon$,

$$ $\displaystyle\mathbb{E}[\mathcal{L}(f({\mathbf{x}}),y)\wedge M]\leq$ $\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f({\mathbf{x}}_{i}),y_{i}) \wedge M+\frac{6\widetilde{C}^{\prime}(\xi)^{\nu/\tilde{d}}}{n^{(\nu/\tilde{d} +1)/2}(\tilde{d}/\nu-1)^{\nu/\tilde{d}}}$ $\displaystyle+\sqrt{\frac{4M^{2}\log(2/\epsilon)}{n}}+\frac{32M\log(2/\epsilon )}{3n}.$ $$

The rest of the proof is similar to those in the proof of Theorem 3, and we omit the details.
∎

###### Proof of Corollary 2 .

The proof is similar to the one for Corollary 1. We omit the details.
∎

###### Proof of Proposition 1 .

###### Proof Proposition 2 .

###### Proof of Theorem 1 .

###### Proof of Theorem 2 .

###### Proof of Theorem 3 .

###### Remark 8 .

###### Proof of Corollary 1 .

###### Proof of Proposition 4 .

###### Proof of Theorem 4 .

###### Proof of Theorem 5 .

###### Proof of Corollary 2 .

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weaknesses
soundness: 3
strengths: - I found the paper well-written, has a good flow, and I believe it presents very solid theoretical results.
- The theoretical results are novel as they present the first generalization error bound and complexity estimate of KAN.
- Frankly, KAN is an "interesting" yet "contentious" topic in the machine learning community ---   "interesting" in the sense that it has caught a lot of attentions and discussions in the community; "contentious" in the sense that it hasn’t achieved broad acceptance or visibility, especially since all the cited KAN-related papers (including the very first KAN paper (Liu et al. 2024)) have not been published in major machine learning venues. I believe this paper contribute to the theoretical understanding of KAN by estimating the excess risk in regression setting of two special classes of KAN. Although the current results are insufficient to conclude whether KAN achieves better generalization performance than traditional MLPs, they provide valuable insights that can encourage the community to further investigate the potential advantages and impact of KAN.
summary: This work addresses a gap in the current research on Kolmogorov–Arnold Networks (KANs) by (i) quantifying the complexity of KANs, and (ii) establishing high probability upper bounds of excess risk in regression task. Specifically, this work studies two special classes of KAN: (i) KAN with activation functions represented by basis functions, and (ii) KAN with activation functions on the RKHS induced by Matern kernel.
weaknesses: -  I find the purpose of the numerical experiments in Section 3 unclear. Are these experiments used to corroborate the complexity result in Theorem 1? If so,  are the activation functions in the implemented KAN chosen to be linear combination of basis functions?
- Can the authors comment further on the convergence rate of excess risk established in Corollary 1 and Corollary 2? What does the parameter $s$ represent? Also, how do these convergence rates compare to that of traditional MLP (say, ReLU feed-forward neural network)? Do we observe any advantage in the generalization of regression by using KAN? 
- It appears that Section 2.3 only considers RKHS induced by Matern kernel, instead of a general low-rank RKHS. Because of the equivalence between this specific RKHS and Sobolev space, would it be a better idea to change the title of Section 2.3 to ``Activation functions on Sobolev space"?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: - Based on the obtained theory, is it possible to identify a problem setting where KANs outperform MLPs?

- How tight are the obtained results? Is it feasible to derive lower bounds on generalization gaps and excess risk bounds in a simple setting?

- Can you discuss the approximation (representation) capabilities of KANs for certain function classes? This type of approximation analysis is often necessary for fully understanding the statistical performance of the model.
soundness: 3
strengths: KANs, inspired by the Kolmogorov-Arnold representation theorem, have gained attention for potentially efficient parameterization compared to MLPs. However, their statistical performance remains unclear, despite numerous attempts to develop more sophisticated structures and applications. To the best of my knowledge, this is the first work to derive generalization bounds for KANs.
summary: This paper explores the generalization capability of Kolmogorov-Arnold Networks (KANs). Specifically, the authors estimated the covering number under certain regularity assumptions and derived the generalization gaps (Theorems 2 and 3) and the excess risk bound (Corollary 1). Additionally, they examined the case where the activation function belongs to a Reproducing Kernel Hilbert Space (RKHS) with a low-rank structure, proving the generalization gaps (Theorems 4 and 5) and the excess risk bound (Corollary 2) that leverage this structure. Experiments validate the relevance of the theoretical bounds to the observed excess risk.
weaknesses: - Assumption 1 presumes the uniform boundedness of the dataset. Typically, this bound scales with $\sqrt{n}$, which could degrade the derived bounds.

- Although KANs are expected to demonstrate superior approximation capability due to their inherent nature, there is no comparison with other models such as MLPs.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: * Could the authors provide some empirical results on the comparison between the bounds and the actual generalization error? This would help convince me that these bounds are indeed non-vacuous in practice.
soundness: 2
strengths: This paper provides multiple generalization bounds for both bounded and unbounded loss functions, which may help in understanding how the network complexity impacts the generalization behavior of KANs.
summary: This paper investigates the generalization ability of Kolmogorov-Arnold Networks (KAN). Multiple generalization bounds are provided for both bounded and unbounded loss functions, which may help understanding how the network complexity impacts the generalization behavior of KANs. The results are further extended to the cases where activation functions belong to RKHS, and empirical results are given to demonstrate the relationship between performance and network complexity.
weaknesses: * It is consensus that traditional complexity measures (e.g. Rademacher complexity or covering numbers) are not sufficient to explain generalization for deep networks. As the analysis of this paper heavily relies on these metrics, the derived bounds are likely vacuous in practice.
* The theoretical analysis relies on tons of strong assumptions (e.g. Lipschitzness, boundedness) for almost every single part of the network (input, function space, loss function). To what extent these assumptions can be met in practice needs more clarification.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: - For the CIFAR-10 and MNIST experiments, why did the authors choose to run the experiments on top of the features of AlexNet instead of the “raw” input? How would that change the results presented in the paper?
- Figure 2 presents the excess loss and the “normalized” complexity measure as a function of the training time, however, it is never stated explicitly how the complexity measure depends on the training time. Am I correct that this dependence comes from the network parameters $B_i$? What are the values of $B_i$ used for the plot? Is it the $\ell_1$ norms of $\mathbf{B}_i$?
- Is it true that the theoretical results do not hold for cross-entropy loss? Can the authors comment on that in light of the use of cross-entropy loss in the experiments? 
- Can the authors provide an intuitive explanation for the role played by the value of $\phi$ evaluated at $0$ (and the constant $C$)?
soundness: 3
strengths: **Originality**. The contribution seems to be novel. To the best of my knowledge, this is the first work to present generalization bounds for KANs.

**Quality**. The theoretical contribution seems to be sound.

**Clarity**. The paper is well organized.

**Significance**. KANs have attracted much attention from the community lately and theoretical contributions would be very welcome.
summary: The paper studies generalization bounds for Kolmogorov–Arnold Network (KAN) using covering numbers (through Rademacher complexity). The authors further present a quantity $\alpha$ which they dub the network complexity and show empirically this measure qualitatively follows the excess risk.
weaknesses: **Clarity**. While the flow of the paper is clear, I wish technical results were complemented by an intuitive discussion. Specifically,
- The third point under main contributions claims “The results shed new light on how the performance of KANs is affected by the underlying network structure and the network complexity.” However, this point is never presented or discussed in the paper.
- Empirical results lack discussion completely.

**Quality**. The empirical results should be more comprehensive and include more details.
- Some very particular choices are made for the synthetic target functions, however, they are never motivated or explained.
- The performance of the networks (loss/accuracy rather than excess loss) is never presented. This is important in order to evaluate whether the regime the authors present in their result is an interesting one or not.
- The paper does not include empirical results for the generalization bounds. It would be of great interest to the reader to see whether the bound is tight.
- The tightness of the bound is never discussed.
- I would expect an appendix with details of the experiments. Specifically, the “normalization” procedure for the complexity measure is never explained. 

**Significance**. The significance of the result largely depends on the tightness of the bound, but it is never discussed or examined.

*Nits*:
- The appendices are never referenced. I would expect them to be referenced when relevant.
- The text in the figures is barely readable at any reasonable “zoom” level.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - It would be nice if the authors can included a detailed discussion on the technical challenge in the covering number estimates of the KANs. Especially, the authors should clarify the novelty of the theoretical analysis.



- Is it possible to give high-probability generalization bounds for unbounded loss functions.

- There is a lacking discussions of the generalization bounds for KANs with those for fully connected networks. Is there a clear advantage on the generalization behavior by theoretical analysis in the paper?

Minor point:

- $\mathcal{F}$ in Proposition 2 is not defined.
soundness: 3
strengths: KANs have found various applications in many scientific and engineering problems. The paper gives solid generalization analysis for KANs. The derived generalization bounds clearly show how the parameters affect the generalization, including the Lipschitzness and l1-norm constraint on the coefficients.
summary: The paper presents generalization bounds for KANs, where the activation functions are learned from the datasets. The paper considers activation functions that are eighter represented by linear combinations of basis functions or lying in a low-dimensional RKHS. The paper presents generalization bounds based on covering number analysis under some assumptions on the Lipschitzness of the activation functions and the l1-norm on the coefficients. The paper further shows that the analysis can be extended to unbounded loss functions, which can be applied to general regression loss functions. Experimental results are also given to verify the theoretical findings.
weaknesses: - The technical contribution seems to be limited. As far as I see, the theoretical analysis follows from existing covering number estimates of fully-connected neural networks [R1]. The idea is to build a recursive relationship of covering number estimates for neural networks with different layers (Proposition 1), which shares similarity to Lemma A.7 in [R1]. Furthermore, Proposition 2 also essentially similar to Lemma 3.2 in R1.


- The paper also gives generalization bounds for learning with unbounded loss functions. However, the results admit some drawbacks. First, the bound in Theorem 3 has a linear dependency $1/\eta$, where $\eta$ is a confidence parameter. This is much worse than the logarithmic dependency. Therefore, the results for unbounded loss functions are not with high probability. Indeed, they are just derived by truncating the prediction followed by Markov's inequality. Second, the bound involves $n^{(1-s)/(2s)}$ and would be much worse than the case with bounded loss function ($n^{-1/2}$). For example, if $s=2$, then the bound in Theorem 3 is of the order of $n^{-1/4}$.





R1: Bartlett, P.L., Foster, D.J. and Telgarsky, M.J., 2017. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30.

Meta-review: Summary:
This paper provides a theoretical analysis of Kolmogorov–Arnold Networks (KANs), including generalization bounds for regression tasks and analysis of network complexity. The work addresses both bounded and unbounded loss functions and offers empirical validation of theoretical insights. Despite some identified weaknesses, the contribution to understanding the generalization properties of KANs is solid, and the paper sets a valuable foundation for future work in this emerging area.

Strengths:
Novelty: The paper is among the first to establish theoretical bounds for KANs, contributing to the theoretical foundation of this novel architecture.

Thoroughness: The authors present comprehensive theoretical results, including complexity measures and empirical validation.

Relevance: Given the growing interest in KANs within the research community, the work provides timely insights into their properties.

Weaknesses:
Performance in Studied Regime: The empirical results indicate that KANs perform poorly in the examined regime, particularly without regularization.

Theoretical Impact: The derived bounds lack evidence of their ability to explain the practical performance of deep learning systems.
Lack of Insight on Advantages Over MLPs: The analysis does not provide a compelling explanation for why KANs might outperform MLPs in practice.

Innovation in Proof Techniques: While the theoretical results are sound, the proof techniques are incremental, building heavily on prior work in related areas.


Suggestions to Authors:

Acknowledge explicitly in the paper the identified weaknesses, including the limited empirical performance and lack of compelling theoretical justification for the superiority of KANs over MLPs.

Discuss the practical implications of the theoretical results more clearly, particularly in terms of how they could guide the design or regularization of KANs.

Consider adding further empirical experiments in future work, particularly in regimes where KANs are expected to perform competitively.

Conclusion:
Despite the highlighted weaknesses, the paper lays important groundwork for theoretical studies of KANs and will be a valuable resource for researchers interested in this architecture. I recommend acceptance, contingent on the authors incorporating suggested revisions to acknowledge and contextualize the limitations of their findings.

Decision: Accept (Poster)