Generalization Bounds and Model Complexity for Kolmogorov-Arnold Networks

• URL: http://arxiv.org/abs/2410.08026v1
• Date: Thu, 10 Oct 2024 15:23:21 GMT
• Title: Generalization Bounds and Model Complexity for Kolmogorov-Arnold Networks
• Authors: Xianyang Zhang, Huijuan Zhou,
• Abstract summary: Kolmogorov-Arnold Network (KAN) is a network structure recently proposed by Liu et al. Work provides a rigorous theoretical analysis of KAN by establishing generalization bounds for KAN equipped with activation functions.
• Score: 1.5850926890180461
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kolmogorov-Arnold Network (KAN) is a network structure recently proposed by 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.

Related papers

• How (Implicit) Regularization of ReLU Neural Networks Characterizes the Learned Function -- Part II: the Multi-D Case of Two Layers with Random First Layer [2.1485350418225244]
  We give an exact macroscopic characterization of the generalization behavior of randomized, shallow NNs with ReLU activation. We show that RSNs correspond to a generalized additive model (GAM)-typed regression in which infinitely many directions are considered.
  arXiv  Detail & Related papers  (2023-03-20T21:05:47Z)
• Deterministic equivalent and error universality of deep random features learning [4.8461049669050915]
  This problem can be seen as a natural generalization of the widely studied random features model to deeper architectures. First, we prove universality of the test error in a universality ridge setting where the learner and target networks share the same intermediate layers, and provide a sharp formula for it. Second, we conjecture the universality of the test error in the more general setting of arbitrary convex losses and generic learner/target architectures.
  arXiv  Detail & Related papers  (2023-02-01T12:37:10Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• From Kernel Methods to Neural Networks: A Unifying Variational Formulation [25.6264886382888]
  We present a unifying regularization functional that depends on an operator and on a generic Radon-domain norm. Our framework offers guarantees of universal approximation for a broad family of regularization operators or, equivalently, for a wide variety of shallow neural networks.
  arXiv  Detail & Related papers  (2022-06-29T13:13:53Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Model based Multi-agent Reinforcement Learning with Tensor Decompositions [52.575433758866936]
  This paper investigates generalisation in state-action space over unexplored state-action pairs by modelling the transition and reward functions as tensors of low CP-rank. Experiments on synthetic MDPs show that using tensor decompositions in a model-based reinforcement learning algorithm can lead to much faster convergence if the true transition and reward functions are indeed of low rank.
  arXiv  Detail & Related papers  (2021-10-27T15:36:25Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Analytical bounds on the local Lipschitz constants of affine-ReLU functions [0.0]
  We mathematically determine upper bounds on the local Lipschitz constant of an affine-ReLU function. We show how these bounds can be combined to determine a bound on an entire network. We show several examples by applying our results to AlexNet, as well as several smaller networks based on the MNIST and CIFAR-10 datasets.
  arXiv  Detail & Related papers  (2020-08-14T00:23:21Z)
• Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theory [9.210074587720172]
  We explain the universal approximation capabilities of deep residual neural networks through geometric nonlinear control. Inspired by recent work establishing links between residual networks and control systems, we provide a general sufficient condition for a residual network to have the power of universal approximation.
  arXiv  Detail & Related papers  (2020-07-12T14:53:30Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  We study estimation in a class of generalized Structural equation models (SEMs) We formulate the linear operator equation as a min-max game, where both players are parameterized by neural networks (NNs), and learn the parameters of these neural networks using a gradient descent. For the first time we provide a tractable estimation procedure for SEMs based on NNs with provable convergence and without the need for sample splitting.
  arXiv  Detail & Related papers  (2020-07-02T17:55:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.