Research map / Learning theory and algorithms / Sample complexity

Generalization Bounds and Model Complexity for Kolmogorov–Arnold Networks

ICLR 2025 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives generalization bounds for Kolmogorov–Arnold Networks with basis-expansion activations (l1-norm coefficient bound, no loss boundedness needed) and low-rank RKHS activations, and checks that the derived complexity measure correlates with excess loss in SGD-trained KANs on simulated and MNIST/CIFAR-10 data.

Problem

Lacking theoretical understanding of how KAN network structure and complexity affect generalization; existing MLP bounds do not directly cover KANs with learnable edge activations.

Approach

Covering-number analysis of layered KAN classes via an iterative layer-wise argument plus Maurey's sparsification lemma, with activations either as l1-bounded basis expansions (Lipschitz-controlled) or low-rank Sobolev/RKHS functions; the resulting complexity measure is tied to products of layer Lipschitz constants and l1 norms of coefficients.

Key results

• The complexity measure (prod of Lipschitz constants)^(2/3) times sum (B_i c_i)^(2/3) tracks the excess loss curve closely across four simulated setups and MNIST/CIFAR-10 during 1000 SGD epochs.
• Generalization bounds hold without boundedness of the loss for the basis-expansion case, covering squared, pinball, and Huber losses.
• Low-rank RKHS result gives a bound polynomial in ranks and Lipschitz constants with no explicit dependence on number of nodes.

Measured effects reported in the paper

Limitations

• Lower bound not derived, so tightness is unknown.
• Analysis does not prove that SGD yields a predictor in the constrained class; the bound applies uniformly over the class.
• Requires Lipschitz constants of basis functions and bounded inputs; the empirical complexity uses upper-bound estimates of Lipschitz constants.

Experimental setup

Datasets: simulated regression and classification datasets (f1, f2 with Unif(-1,1) inputs) MNIST CIFAR-10

Benchmarks: MNIST CIFAR-10 simulated regression and classification setups (i)-(iv)

Metrics: excess loss (test minus training loss) normalized model complexity measure

Baselines: MLP generalization bound (Golowich-style / Bartlett-type ramp loss bound)

Builds on: Kolmogorov-Arnold Networks Bartlett et al. margin bounds for neural networks Maurey sparsification lemma

Closest papers by meaning

• Koopman-based generalization bound: New aspect for full-rank weights (ICLR 2024 · similarity 0.90)
• KAN: Kolmogorov–Arnold Networks (ICLR 2025 · similarity 0.90)
• On the expressiveness and spectral bias of KANs (ICLR 2025 · similarity 0.89)
• Generalization Bounds for Rank-sparse Neural Networks (NeurIPS 2025 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.88)
• PowerMLP: An Efficient Version of KAN (AAAI 2025 · similarity 0.87)