Generalization Bounds and Model Complexity for Kolmogorov–Arnold Networks

Authors: Xianyang Zhang, Huijuan Zhou
Primary area: learning theory
Keywords: Deep neural networks, Empirical process, Generalization bounds, Kolmogorov-Arnold representation theorem, Model complexity

Abstract:
Kolmogorov–Arnold Network (KAN) is a network structure recently proposed in Liu et al. (2024) 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$ 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.

Decision: accept (poster)
Reviewer scores: 8, 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729397597694

thread_type:
official_review

<thread_object>
creator: reviewer_gezs

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730056915291

thread_type:
official_review

<thread_object>
creator: reviewer_xdbu

<content>
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.

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.

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.

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$)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730450746041

thread_type:
official_review

<thread_object>
creator: reviewer_u9e2

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696344768

thread_type:
official_review

<thread_object>
creator: reviewer_mrks

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731094983544

thread_type:
official_review

<thread_object>
creator: reviewer_vaj9

<content>
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.

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.

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"?

questions:
See Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1732490551805

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
First and foremost, we express our sincere gratitude to the five reviewers for their invaluable feedback, which has helped us improve the quality of our manuscript. We have revised our manuscript, taking all the reviewers' comments into consideration. Before providing point-by-point responses, we would like to summarize the major changes we have made to address the reviewers' main concerns.

1. We highlight our technical contributions relative to existing works and further discuss the implications of our main results.
    
2. We discuss the derived bounds and compare them with the corresponding bound for MLPs; see Section A.1 of the appendix.

3. We refine our excess risk bounds under the sub-exponential tail condition on $G(\mathbf{x},y)$ and $B(y)$; see Section A.2 of the appendix.

4. We derive a lower bound on the empirical Rademacher complexity for KANs; see Section A.3 of the appendix;

5. We provide additional numerical results and discussions in Section A.4 of the appendix. 

We have highlighted the changes in red in the revision. Below, we provide point-by-point responses to each reviewer's comments.

References

[R1] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.

[R2] Alexander Dylan Bodner, Antonio Santiago Tepsich, Jack Natan Spolski, and Santiago Pourteau. Convolutional kolmogorov-arnold networks. arXiv preprint arXiv:2406.13155, 2024.

[R3] Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and inference. Econometrica, 89(1):181–213, 2021.

[R4] Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljačić, Thomas Y Hou, and Max Tegmark. Kan: Kolmogorov-arnold networks. arXiv preprint arXiv:2404.19756, 2024.

[R5] Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, pages 1875–1897, 2020.

[R6] Yixuan Wang, Jonathan W Siegel, Ziming Liu, and Thomas Y Hou. On the expressiveness and spectral bias of kans. arXiv preprint arXiv:2410.01803, 2024.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.