Generalization Bounds and Model Complexity for Kolmogorov-Arnold Networks

Response to Reviewer geZs: Part I

*1. 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].* **Ans:** While some of the techniques used in our analysis are based on prior work in [R1], our analysis yields several new findings: (i) excess risk bounds concerning unbounded loss functions and (ii) results related to activation functions within low-rank Sobolev spaces. Importantly, our innovation lies in applying these theoretical tools to analyze new types of deep neural network structures that have not been previously studied to the best of our knowledge. Please refer to page 3 of the revision for the discussions. *2. 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 $O(n^{-1/2})$. For example, if $s=2$, then the bound in Theorem 3 is of the order of $n^{-1/4}$.* **Ans:** We appreciate your thoughtful comments. The current result is due to the relatively weak moment assumption we impose and the Markov inequality used in the proof. Indeed, if we assume that $G(\mathbf{x},y)$ and $B(y)$ both have sub-exponential tails, then by using a more delicate analysis and Bernstein's inequality, we can obtain improved rates and dependence on $\eta$. Specifically, the bound in Theorem 3 can be improved to that with probability greater than $1-\epsilon-\tau-\eta$ \begin{align*} R(f)\leq & \frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(f(\mathbf{x}_i),y_i) + \frac{144\sqrt{\zeta_0}\{\log(C n\log(n)/\sqrt{\zeta_0})\vee 1\}}{n} +\frac{C\log(n)\sqrt{\log(2/\epsilon)}}{\sqrt{n}}+\frac{C\log(n)\log(2/\epsilon)}{3n} + C\sqrt{\frac{\log(1/\eta)}{n}}, \end{align*} where $\zeta_0=\tilde{\alpha}^3\log(2\tilde{d}\tilde{p})(C\log(nC/\tau))^2$ and $C$ is a large enough constant. Note that the dependency $1/\eta$ in the original bound has been improved to $\sqrt{\log(1/\eta)}$ by using the Bernstein inequality and the term $n^{(1-s)/(2s)}$ has been improved to $n^{-1/2}$ due to the sub-exponential tails. Essentially, there is a trade-off between the moment condition and the rate we could achieve. Due to the page limit, we included these results and discussions in the appendix. *3. 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.* **Ans:** Thank you for the comment. Let us highlight the key technical challenges (in addition to those for MLPs) in deriving covering number estimates for KANs. The first challenge involves finding an appropriate application of Maurey's sparsification lemma, specifically in constructing $V_1,\dots,V_N$ in Lemma 1 for KANs (which is not as straightforward as the case of MLPs). The second challenge lies in controlling the effect of $\mathbf{\Psi}(\mathbf{0})$ on the covering numbers. The term $\mathbf{\Psi}(\mathbf{0})$ is similar to the ReLU function evaluated at the bias for MLPs (note that for MLPs, $\mathbf{\Psi}_l(\mathbf{x}) = \sigma(\mathbf{W}_l\mathbf{x} + \mathbf{b}_l)$ and $\mathbf{\Psi}(\mathbf{0}) = \sigma(\mathbf{b}_l)$). Previous analyses like [R1] did not fully address the impact of the bias terms. Our analysis provides a more complete treatment of this aspect. Although our proof techniques build upon existing tools, we extend beyond previous results in several ways: (i) We showed to what extent the empirical process theory can be adapted to deal with a more general type of network structure (which indeed includes MLPs as a special case); (ii) We establish excess risk bounds for unbounded loss functions (now strengthened with high-probability bounds and improved convergence rates); (iii) We analyze KANs with activation functions lying in low-rank Sobolev spaces. With our new findings, we demonstrate how classical techniques can be adapted to handle more general and flexible network structures that have not been previously analyzed.

Response to Reviewer geZs: Part II

*4. Is it possible to give high-probability generalization bounds for unbounded loss functions?* **Ans:** Related to our answer to your second point, we have derived high-probability generalization bounds for unbounded loss functions. Please refer to Section A.2 of the appendix for the new results. *5. 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?* **Ans:** For a fair comparison, let us consider the bound derived in Theorem 2 with $C=0$ and $\max_i B(y_i)$ being finite. Note that $\zeta = \tilde{\alpha}^3 \log(2\tilde{d}\tilde{p}) \max_i B^2(y_i)$ because this setting is closest to the one for MLPs considered in [R1]. Ignoring the smaller order terms, the bound can be expressed as $$O\left( \frac{||\mathbf{X}||R _ {\text{KAN}}}{n} \log(n)\log(2\tilde{d}\tilde{p}) + \sqrt{\frac{\log(1/\epsilon)}{n}}\right),$$ where $R _ {\text{KAN}}=\left(\prod^{L} _ {j=1}\rho _ j\right)\left(\sum^{L} _ {i=1}(B_ic_i)^{2/3}\right)^{3/2}.$ There have been several results in the literature concerning risk bounds or estimation error bounds for MLP or feedforward networks, such as [R1, R3, R5]. The most closely related work is [R1], which shows that with probability greater than $1-\epsilon$, the error bound is of the order \begin{align*} O\left(\frac{||\mathbf{X}||R_{\mathcal{A}}}{\gamma n}\log(n)\log(W)+\sqrt{\frac{\log(1/\epsilon)}{n}}\right), \end{align*} where $R_{\mathcal{A}}$ is a measure of model complexity (similar to $R$ defined above), $\gamma$ is the margin in the ramp loss and $W$ is the network width (similar to $\tilde{d}$ in our case). When $R$ and $R_{\mathcal{A}}$ are of the same order (denoted by $R\asymp R_{\mathcal{A}}$), the two bounds are also of the same order. This is not surprising, as $R \asymp R _ {\mathcal{A}}$ implies that the two classes have the same order of complexities. On the other hand, if $R = o(R _ {\mathcal{A}})$ and $R _ {\mathcal{A}}/\sqrt{n} \rightarrow +\infty$, then the bound for KANs is of a smaller order than the bound for MLPs. This situation occurs when the underlying true regression function can be more effectively approximated using KANs (e.g., the true regression function can be exactly expressed by a KAN network). As discussed in [R4], KANs may require fewer parameters than MLPs to approximate the same underlying true function because KANs leverage the inherently low-dimensional representation of the true function, whereas MLPs do not. Below, we provide a numerical example to support this claim. We use the symbol $\phi$ with different subscripts to denote different spline functions (linear combinations of spline basis). We consider the regression settings, $y=f(x)+\epsilon$, where $\epsilon$ is a mean-zero random error, and: **Example 1.** $f(x)=\sum_{j=0}^{99}\phi_j(x_j)$, which can be exactly represented by a KAN of shape [100, 1]; **Example 2.** $f(x)=\phi_{1,0}(\sum_{j=0}^{99}\phi_{0,0,j}(x_j))+\phi_{1,1}(\sum_{j=0}^{99}\phi_{0,1,j}(x_j))$, which can be exactly represented by a KAN of shape [100, 2, 1]. We employed KAN with shapes [100, 1], [100, 2, 1], and MLP with shapes [100, 6, 1] and [100, 12, 1] for the two settings, respectively. Since the number of basis splines used in KAN is 6, the widths for the MLP were set so that the two networks have a similar number of parameters. The test errors (mean squared errors) are shown in the following table. | | Example 1 | Example 2 | |-------|---------|-----------| | KAN | 2.0765 | 1.1184e-02| | MLP | 10.5546 | 5.8772e-02| We observe that the test error of the MLP network is approximately five times that of the KAN network. We also tested MLPs with different shapes and observed that neither decreasing nor increasing the widths or depths significantly improved the test error. Although the examples considered are special cases where the regression functions can be exactly represented by a KAN, we point out that the MLP is a special structure of KAN (e.g., when the identity function is included as a basis function and ReLU is used as the activation function). Therefore, the KAN network has a greater capability to reflect the underlying true regression function, and when it does so, we can expect a lower test error. A similar phenomenon has been observed in [R4]; see Figures 3.1-3.3 therein.

Response to Reviewer xDbU: Part I

**Clarity** *While the flow of the paper is clear, I wish technical results were complemented by an intuitive discussion. Specifically,* *1. 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.* **Ans:** Thank you for raising this point. We acknowledge that the connection between our theoretical results and practical insights could have been articulated more clearly. Our contribution regarding network structure and complexity is demonstrated through several key aspects of our work: (i) Our derived generalization bound explicitly includes a complexity term, $\tilde{\alpha}$, which quantifies the structural properties of KANs. This provides a theoretical measure of how choices in network architecture impact learning performance. (ii) Our simulation results in Section 3 demonstrate a strong empirical correlation between this complexity measure and the observed generalization error. Specifically, we found that the difference between the test loss and training loss is strongly correlated with $\tilde{\alpha}$ in our numerical examples. (iii) This theoretical-empirical connection suggests a practical design principle: the generalization performance of KANs can be improved by controlling this complexity measure. This insight naturally leads to a potential regularization strategy where the identified complexity term could be used as a regularizer in the training objective. We have provided a more detailed discussion about this point in the revision. *2. Empirical results lack discussion completely.* **Ans:** We have added more details and discussions of the empirical results in Section A.4 of the revision. **Quality.** *The empirical results should be more comprehensive and include more details.* *1. Some very particular choices are made for the synthetic target functions, however, they are never motivated or explained.* **Ans:** Thank you for the comments. The regression functions used in the simulation studies are two examples considered in the original KAN paper [R4]. They serve as representative examples of synthetic functions for the low-dimensional and high-dimensional cases, respectively. *2. 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.* **Ans:** We have included the figure showing the curves of KAN complexity and test loss in Figure 3 and provided additional details of experiments in Section A.4 of the revision. *3. 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.* **Ans:** Directly comparing the bound with the generalization error in finite samples may not be particularly meaningful, as the bound depends on some unknown constants, and the coefficients of certain terms in the bound are unlikely to be tight. One practical value of our findings is that they help us understand (i) how to quantitatively represent model complexity in KANs and (ii) how model complexity can influence generalization performance. Specifically, model complexity can be represented in a compact form using the scalar: $$R _ {\text{KAN}} = \left(\prod _ {j=1}^{L}\rho_j\right)\left(\sum _ {i=1}^{L}(B_ic_i)^{2/3}\right)^{3/2}.$$ Our empirical results indicate a strong correlation between excess loss/test loss and $R_{\text{KAN}}$. This finding highlights the importance of developing regularization techniques, whether explicit or implicit (such as early stopping or penalization), to control this complexity measure, which could potentially improve generalization performance. We have included additional numerical results and discussions in Section A.4 of the appendix.

Response to Reviewer xDbU

Thank you for your feedback. The current numerical experiments serve two goals: (i) they provide a cautionary note about training KANs in the over-parameterized regime without regularization, highlighting the necessity of some form of regularization to prevent overfitting; (ii) they demonstrate the relevance of network complexity in predicting a network's generalization performance for both unregularized and regularized KANs (see Figure 4). The newly added numerical results indicate that with appropriate regularization, KANs can achieve significantly improved performance in terms of test loss. In view of Figure 4, the performance of regularized KANs is aligned more with the "common expectations." We will continue investigating regularized KANs and report any interesting findings along this line. It is true that neural networks can perform well even when over-parameterized, but this does not imply that they can do so without any form of regularization. With proper regularization, over-parameterized networks can generalize well and may experience the so-called double descent phenomenon. This is also evident in simpler models, such as ridge/ridgeless high-dimensional least squares regression, as shown in the work of Hastie et al. (2020, https://arxiv.org/pdf/1903.08560), where the underlying estimator is properly regularized (for example, they studied interpolated estimators with the minimum $l_2$ norm). The NTK provides an alternative theory that connects DNNs trained through gradient descent with kernel methods, relating the convergence of DNN training to the positive definiteness of the limiting NTK. Their theory also supports the use of some form of regularization, such as early stopping, which is explicitly mentioned in their work. Our theory and numerical results do not contradict the existing findings and "common expectations" for DNNs in this regard; rather, they provide insights into how model complexity affects generalization and advocate for the use of regularization in KANs. As KANs are a relatively new type of network structure, there are still many open questions regarding their potential and behavior under different settings. For instance, do KANs exhibit the double descent phenomenon? As you pointed out, it remains unclear whether one can establish results parallel to those of NTK/NNGP. What is the most effective way to regularize KANs? We view our work as an initial step in understanding KAN generalization, and we believe the above questions are all worthwhile research problems that deserve further investigation.

Response to Reviewer u9e2: Part I

*1. 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.* **Ans:** We appreciate your thoughtful comment. While we acknowledge that traditional complexity measures alone may not fully explain the generalization behavior of deep neural networks - we believe there remains value in theoretical analyses using these classical tools for several reasons: 1. Foundational Understanding: Classical complexity measures offer a rigorous mathematical framework that can provide insights into the fundamental properties of neural networks. In some instances, the bounds derived using these measures and tools have been shown to achieve optimal rates, such as the minimax rate. 2. Complementary Perspective: Our analysis using traditional metrics complements rather than contradicts newer approaches. Recent works have shown that combining classical tools with neural network-specific considerations can lead to meaningful results, e.g., [R1, R3, R5]. 3. Complexity Measures: The complexity measures involved in the bounds (i.e., the quantity $\tilde{\alpha}$) shed some light on how the generalization error is affected by the network structure, which might motivate ways to regularize KANs during the training process. Indeed, our numerical results suggest that these measures are strongly correlated with the difference between the test loss and training loss and thus could be practically relevant. Similar findings for MLPs were also reported in [R1]. In the revision, we have added discussions acknowledging the known limitations of traditional complexity measures in the analysis of deep neural networks and clarified how our analysis fits into the broader landscape of generalization theory; see page 3 of the revision. *2. 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.* **Ans:** Thank you for the comment. Below, we will clarify the practical relevance and applicability of these assumptions. 1. Lipschitzness: Lipschitz continuity is a widely used assumption in nonparametric statistics. Function classes that exhibit Lipschitz continuity include: (i) differentiable functions with bounded derivatives, (ii) convex functions, (iii) monotonic functions, and (iv) piecewise linear functions. Notably, functions that belong to the Hölder space, Sobolev space, or the space of continuous and bounded variation are also Lipschitz continuous. 2. Boundedness: First, the assumption of input boundedness (i.e., $||\mathbf{X}||\leq D$) is not unreasonable, as real-world data typically exists within a compact domain. For example, normalized image pixels fall within the range $[0,1]$, and standardized features in tabular data adhere to similar constraints. We can relax this assumption by only requiring that $||\mathbf{X}|| \leq D$ holds with high probability, specifically that $P(||\mathbf{X}||\leq D) \geq 1-\epsilon$ for a small value of $\epsilon$, where the constant $D$ is allowed to grow with $n$. Bounded functional space is a natural requirement in empirical process theory; without it, the complexity of the functional space (as measured by covering numbers or Rademacher complexity) is infinity, making technical analysis infeasible. While the boundedness condition on the loss is valid for certain cases, such as non-convex least squares loss, Ramp loss, and Ramp $\epsilon$-insensitive loss, there are also numerous instances where the loss function is unbounded. We acknowledge this limitation and derive the generalization error bounds for unbounded loss functions in the paper; see, for example, Theorems 3 and 5.

Response to Reviewer mrKs: Part I

*1. Assumption 1 presumes the uniform boundedness of the dataset. Typically, this bound scales with $\sqrt{n}$, which could degrade the derived bounds.* **Ans:** Thanks for the comment. It is true that the bound $D$ generally scales with $\sqrt{n}$. However, this scaling does not degrade the derived bounds. For instance, let us consider the bound derived in Theorem 2. The constant $D$ appears in this bound through $\zeta = \tilde{\alpha}^3 \log(2\tilde{d}\tilde{p})\max _ i B^2(y _ i)$. We note that $\tilde{\alpha}^3$ is proportional to $D^2$, which is of the order $O(n)$ when the input dimension is fixed asymptotically. Therefore, neglecting some smaller order terms, the bound can be expressed as follows: $$O\left( \frac{R _ {\text{KAN}}}{\sqrt{n}}\log(n)\log(2\tilde{d}\tilde{p}) + \sqrt{\frac{\log(1/\epsilon)}{n}}\right),$$ where $R _ {\text{KAN}}=(\prod^{L} _ {j=1}\rho _ j)(\sum^{L} _ {i=1}(B_ic_i)^{2/3})^{3/2}$ is a measure of the network complexity. When $R=O((\log(n))^a)$ for some $a>0$, we achieve the $O(n^{-1/2})$ rate up to some logarithmic factor. Indeed, a similar dependence on $D$ appears in the bound for MLPs; see Theorem 1.1 of [R1]. We can relax this assumption by only requiring that $||\mathbf{X}|| \leq D$ holds with high probability, specifically that $P(||\mathbf{X}||\leq D) \geq 1-\epsilon$ for a small value of $\epsilon$. *2. Although KANs are expected to demonstrate superior approximation capability due to their inherent nature, there is no comparison with other models, such as MLPs. Based on the obtained theory, is it possible to identify a problem setting where KANs outperform MLPs?* **Ans:** Thank you for the helpful suggestion. To address this, let us begin by making a theoretical comparison between the bounds we derived and those for MLPs. Based on this comparison, we will then present a numerical example to demonstrate that KANs can outperform MLPs in certain scenarios. It is important to emphasize that our primary aim is not merely to advocate for the use of KANs but to gain a deeper understanding of the potential advantages and disadvantages of this new type of network structure from a theoretical perspective. To make a fair comparison, we again consider the bound derived in Theorem 2 with $C=0$ and $\max_i B(y_i)$ being finite because this setting is closest to the one for MLPs considered in \cite{bartlett2017spectrally}. Recall from the paper that $\zeta = \tilde{\alpha}^3 \log(2\tilde{d}\tilde{p}) \max _ i B^2(y _ i)$. Ignoring the smaller order terms, the bound can be expressed as $$O\left( \frac{||\mathbf{X}||R_{\text{KAN}}}{n} \log(n)\log(2\tilde{d}\tilde{p}) + \sqrt{\frac{\log(1/\epsilon)}{n}}\right).$$ There have been several recent results in the literature concerning risk bounds or estimation error bounds for MLPs, such as [R1, R3, R5]. The most closely related work is [R1], which shows that with probability greater than $1-\epsilon$, the error bound is of the order \begin{align*} O\left(\frac{||\mathbf{X}||R_{\mathcal{A}}}{\gamma n}\log(n)\log(W)+\sqrt{\frac{\log(1/\epsilon)}{n}}\right), \end{align*} where $R_{\mathcal{A}}$ is a measure of model complexity (similar to $R$ defined above), $\gamma$ is the margin in the ramp loss and $W$ is the network width (similar to $\tilde{d}$ in our case). When $R$ and $R_{\mathcal{A}}$ are of the same order (denoted by $R\asymp R_{\mathcal{A}}$), the two bounds are also of the same order. This is not surprising, as $R \asymp R _ {\mathcal{A}}$ implies that the two classes have the same order of complexities. On the other hand, if $R = o(R _ {\mathcal{A}})$ and $R _ {\mathcal{A}}/\sqrt{n} \rightarrow +\infty$, then the bound for KANs is of a smaller order than the bound for MLPs. This situation occurs when the underlying true regression function can be more effectively approximated using KANs (e.g., the true regression function can be exactly expressed by a KAN network). As discussed in [R4], KANs may require fewer parameters than MLPs to approximate the same underlying true function because KANs leverage the inherently low-dimensional representation of the true function, whereas MLPs do not. Below, we provide a numerical example to support this claim. We use the symbol $\phi$ with different subscripts to denote different spline functions (linear combinations of spline basis). We consider the regression settings, $y=f(x)+\epsilon$, where $\epsilon$ is a mean-zero random error, and: **Example 1.** $f(x)=\sum_{j=0}^{99}\phi_j(x_j)$, which can be exactly represented by a KAN of shape [100, 1]; **Example 2.** $f(x)=\phi_{1,0}(\sum_{j=0}^{99}\phi_{0,0,j}(x_j))+\phi_{1,1}(\sum_{j=0}^{99}\phi_{0,1,j}(x_j))$, which can be exactly represented by a KAN of shape [100, 2, 1].

Response to Reviewer mrKs: Part II

We employed KAN with shapes [100, 1], [100, 2, 1], and MLP with shapes [100, 6, 1] and [100, 12, 1] for the two settings, respectively. Since the number of basis splines used in KAN is 6, the widths for the MLP were set so that the two networks have a similar number of parameters. The test errors (mean squared errors) are shown in the following table. | | Example 1 | Example 2 | |-------|---------|-----------| | KAN | 2.0765 | 1.1184e-02| | MLP | 10.5546 | 5.8772e-02| We observe that the test error of the MLP network is approximately five times that of the KAN network. We also tested MLPs with different shapes and observed that neither decreasing nor increasing the widths or depths significantly improved the test error. Although the examples considered are special cases where the regression functions can be exactly represented by a KAN, we point out that the MLP is a special structure of KAN (e.g., when the identity function is included as a basis function and ReLU is used as the activation function). Therefore, the KAN network has a greater capability to reflect the underlying true regression function, and when it does so, we can expect a lower test error. A similar phenomenon has been observed in [R4]; see Figures 3.1-3.3 therein. *3. How tight are the obtained results? Is it feasible to derive lower bounds on generalization gaps and excess risk bounds in a simple setting?* **Ans:** Thank you for your comment. As we mentioned in response to your first comment, our derived bound can achieve a rate of $O(n^{-1/2})$, albeit with some logarithmic factors. This rate aligns with the best possible rate for the bounds for MLPs discussed in [R1]. The bottleneck of the current analysis comes from the use of the Rademacher complexity, which results in a rate of at least $O(n^{-1/2})$. Proving the tightness of the bounds is indeed a challenging task (even for MLPs in some problems). To partly address this concern, we derive a lower bound on the Rademacher complexity of the class induced by KANs; see Section A.3 of the appendix. Moreover, we can partly show the tightness of the bound in Theorem 2 by using the following fact. Suppose $\mathcal{L}$ satisfies that $|\mathcal{L}(f(\mathbf{x}),y)|\leq M$ for any $\mathbf{x},y$ and $f\in\mathcal{M}$. It is known that for any $\delta>0$, $$\sup _ {f\in\mathcal{M}}\left|R(f)-\frac{1}{n}\sum^{n} _ {i=1}\mathcal{L}(f(\mathbf{x} _ i),y _ i)\right| \geq \frac{\mathcal{R}(\mathcal{M} _ {\mathcal{L}}(\mathbf{X}))}{2} - \frac{\sup _ {f\in\mathcal{M}}|\mathbb{E}[\mathcal{L}(f(\mathbf{x}),y)]|}{\sqrt{n}} -\delta $$ with probability at least $1-\exp(-n\delta^2/(2M^2)).$ When $\mathcal{R}(\mathcal{M} _ {\mathcal{L}}(\mathbf{X}))=O(n^{-1/2})$, the bound in Theorems 2-3 are nearly tight (up to some logarithmic factors) when $R$ does not grow too fast. However, showing a lower bound for $R(\widehat{f})-\frac{1}{n}\sum^{n}_{i=1}\mathcal{L}(\widehat{f}(\mathbf{x}_i),y_i)$ is quite challenging and requires a more delicate analysis. We shall investigate this interesting problem in our future research. *4. 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.* **Ans:** The approximation capabilities of KANs generally depend on the form of the true underlying function and the choice of activation functions in the KAN network class. Suppose the underlying true function is defined on $[0,1]^n$ and admits the representation \begin{align*} f _ 0(\cdot)=\mathbf{\Phi} _ L\circ \mathbf{\Phi} _ {L-1}\circ \cdots \circ \mathbf{\Phi} _ 1(\cdot), \end{align*} where $\mathbf{\Phi} _ l=(\phi _ {l,i,j})$ with each $\phi _ {l,i,j}$ being $(k + 1)$ times continuously differentiable. Then, there exists a KAN network with the B-spline functions $\psi _ {l,i,j}$ with grid size $G$ such that \begin{align*} ||f _ 0(\mathbf{x}) - (\mathbf{\Psi} _ {L} \circ \mathbf{\Psi} _ {L-1} \circ \cdots \circ \mathbf{\Psi} _ 1)\mathbf{x} || _ {C^m} \leq c G^{-k-1+m}. \end{align*} where $||g|| _ {C^m} = \max_{|\beta| \leq m} \sup_{\mathbf{x} \in [0,1]^n} |D^\beta g(\mathbf{x})|$ and $c$ is some constant depending on $f_0$. A recent work [R6] shows that MLP with ReLU$^k$ activation functions (i.e., $\sigma(x)=\max(0,x)^k$) can be exactly represented using a KAN with degree $k$ splines. As a result, any function that can be approximated by MLP with ReLU$^k$ activation functions can also be approximated by KANs.

Response to reviewer Reviewer vaj9: Part I

*1. 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?* **Ans:** The primary objective of the numerical experiments in Section 3 is to showcase the generalization performance of KANs and to analyze how the complexity measure $\tilde{\alpha}$, which appears in the derived bounds, impacts KANs' performance. The activation functions in the implemented KANs are linear combinations of basis functions, including SiLU and Spline basis, as considered by [R4]. We have provided more details in Section A.4 of the revision. *2. Can the authors comment further on the convergence rate of excess risk established in Corollary 1 and Corollary 2? What does the parameter 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?* **Ans:** For clarity, we will organize our response into three sections. **Interpretation of the rate in Corollary 1.** Consider the upper bound on the excess risk in Corollary 1. We first explain what the parameters represent in this bound: (i) $\zeta_0$ is a parameter that quantifies the impact of the KAN network structure on the excess risk. It depends on the model complexity measure $\tilde{\alpha}$, the network width $\tilde{d}$ and the (maximum) number of basis functions $\tilde{p}$ involved in the activation functions; (ii) $\epsilon,\tau$ and $\eta$ determines a trade-off between the bound and the probability of the event that this bound holds. To understand this bound and obtain a more explicit rate, let us ignore the logarithmic terms, the smaller order terms, and the dependence on $\epsilon,\tau$, and $\eta$. The order of the upper bound can be simplified to \begin{align*} O\left(\frac{\sqrt{\zeta_0}}{n}+\frac{1}{n^{(s-1)/(2s)}}\right), \end{align*} where up to a logarithmic factor, $\zeta_0$ is of the order $\tilde{\alpha}^3 n^{2/s'}$ with $\tilde{\alpha}^3$ being proportional to $D^2$. Recall that $D$ is a bound of $||\mathbf{X}|| _ 2$, which is of the order $O(\sqrt{n})$ when the input dimension is fixed asymptotically. Also, suppose $C=0$. Then we have $\zeta_0 = O(n^{1+2/s'}R^2)$ with $R _ {\text{KAN}} =(\prod^{L} _ {j=1}\rho _ j)(\sum^{L}_{i=1}(B_ic_i)^{2/3})^{3/2}$, which measures the network complexity. It thus implies that the bound is of the order \begin{align*} O\left(\frac{R _ {\text{KAN}}}{n^{1/2-1/s'}}+\frac{1}{n^{(s-1)/(2s)}}\right). \end{align*} We note that the excess risk has an order close to the rate $O(n^{-1/2})$ when $s'$ and $s$ are large. In particular, if $G(\mathbf{x},y)$ and $B(y_i)$ both have sub-exponential tails (so that all their moments exist) and $R=O((\log(n))^a)$ for some $a>0$, the excess risk has the rate $O(n^{-1/2})$ up to some logarithmic factors. See Section A.3 for the precise statements. **Interpretation of the rate in Corollary 2.** Next, we consider the upper bound on the excess risk in Corollary 2. The parameter $\xi_0$ has a similar interpretation as that of $\zeta_0$. It measures the model complexity and depends on the smoothness parameter $\nu$ of the Sobolev space, the network widths $d_i$, the underlying ranks $r_i$, the bounds on the RKHS norms of the activation functions $R_i$ and the Lipschitz constants $\rho_i.$ Again, ignoring the logarithmic terms, the bound is of the order \begin{align*} O\left(\frac{\xi_0^{\nu/\tilde{d}}}{n^{(\nu/\tilde{d}+1)/2}}+\frac{1}{n^{(s-1)/(2s)}}\right). \end{align*} In view of the definition of $\xi_0$, when $\tilde{d}>\nu$, we have \begin{align*} \xi_0^{\nu/\tilde{d}} = O\left(n^{2/s'+1/2}\right) \end{align*} and hence, the bound can be simplified to \begin{align*} O\left(\frac{1}{n^{\nu/(2\tilde{d})-2/s'}}+\frac{1}{n^{(s-1)/(2s)}}\right). \end{align*} When $G(\mathbf{x},y)$ and $B(y_i)$ both have sub-exponential tails (so that all their moments exist), the excess risk has the rate $O(n^{-\nu/(2\tilde{d})})$. Note that when $\tilde{d}<\nu$, with similar arguments, the corresponding rate would become $O(n^{-1/2})$ up to some logarithmic factors.

Response to reviewer Reviewer vaj9: Part II

**Comparison with the results for MLP.** For a fair comparison, let us consider the bound derived in Theorem 2 with $C=0$ and $\max_i B(y_i)$ being finite because this setting is closest to the one for MLPs considered in [R1]. Recall from the paper that $\zeta = \tilde{\alpha}^3 \log(2\tilde{d}\tilde{p}) \max _ i B^2(y _ i)$. Ignoring the smaller order terms, the bound can be expressed as $$O\left( \frac{||\mathbf{X}||R _ {\text{KAN}}}{n} \log(n)\log(2\tilde{d}\tilde{p}) + \sqrt{\frac{\log(1/\epsilon)}{n}}\right),$$ where $R _ {\text{KAN}} =(\prod^{L} _ {j=1}\rho _ j)(\sum^{L}_{i=1}(B_ic_i)^{2/3})^{3/2}$ is the complexity measure of KANs. There have been several results in the literature concerning risk bounds or estimation error bounds for MLP or feedforward networks, such as [R1, R3, R5]. The most closely related work is [R1], which shows that with probability greater than $1-\epsilon$, the error bound is of the order $$ O\left(\frac{||\mathbf{X}||R _ {\mathcal{A}}}{\gamma n}\log(n)\log(W)+\sqrt{\frac{\log(1/\epsilon)}{n}}\right), $$ where $R_{\mathcal{A}}$ is a measure of model complexity (similar to $R _ {\text{KAN}}$ defined above), $\gamma$ is the margin in the ramp loss and $W$ is the network width (similar to $\tilde{d}$ in our case). When $R$ and $R_{\mathcal{A}}$ are of the same order (denoted by $R\asymp R_{\mathcal{A}}$), the two bounds are also of the same order. This is not surprising, as $R \asymp R _ {\mathcal{A}}$ implies that the two classes have the same order of complexities. On the other hand, if $R = o(R _ {\mathcal{A}})$ and $R _ {\mathcal{A}}/\sqrt{n} \rightarrow +\infty$, then the bound for KANs is of a smaller order than the bound for MLPs. This situation occurs when the underlying true regression function can be more effectively approximated using KANs (e.g., the true regression function can be exactly expressed by a KAN network). As discussed in [R4], KANs may require fewer parameters than MLPs to approximate the same underlying true function because KANs leverage the inherently low-dimensional representation of the true function, whereas MLPs do not. Below, we provide a numerical example to support this claim. We use the symbol $\phi$ with different subscripts to denote different spline functions (linear combinations of spline basis). We consider the regression settings, $y=f(x)+\epsilon$, where $\epsilon$ is a mean-zero random error, and: **Example 1.** $f(x)=\sum_{j=0}^{99}\phi_j(x_j)$, which can be exactly represented by a KAN of shape [100, 1]; **Example 2.** $f(x)=\phi_{1,0}(\sum_{j=0}^{99}\phi_{0,0,j}(x_j))+\phi_{1,1}(\sum_{j=0}^{99}\phi_{0,1,j}(x_j))$, which can be exactly represented by a KAN of shape [100, 2, 1]. We employed KAN with shapes [100, 1], [100, 2, 1], and MLP with shapes [100, 6, 1] and [100, 12, 1] for the two settings, respectively. Since the number of basis splines used in KAN is 6, the widths for the MLP were set so that the two networks have a similar number of parameters. The test errors (mean squared errors) are shown in the following table. | | Example 1 | Example 2 | |-------|---------|-----------| | KAN | 2.0765 | 1.1184e-02| | MLP | 10.5546 | 5.8772e-02| We observe that the test error of the MLP network is approximately five times that of the KAN network. We also tested MLPs with different shapes and observed that neither decreasing nor increasing the widths or depths significantly improved the test error. Although the examples considered are special cases where the regression functions can be exactly represented by a KAN, we point out that the MLP is a special structure of KAN (e.g., when the identity function is included as a basis function and ReLU is used as the activation function). Therefore, the KAN network has a greater capability to reflect the underlying true regression function, and when it does so, we can expect a lower test error. A similar phenomenon has been observed in [R4]; see Figures 3.1-3.3 therein. *3. 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''?* **Ans:** Thank you for the suggestion. In the revision, we have changed the title of Section 2.3 to ``Risk analysis: activation functions in low-rank Sobolev Space''.