📊 statistics

Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks

This paper establishes theoretical bounds for the optimization, generalization, and differential privacy of gradient descent on two-layer Kolmogorov-Arnold Networks, demonstrating that polylogarithmic network width suffices for efficient non-private training but becomes necessary under privacy constraints, thereby revealing a qualitative gap between private and non-private regimes.

Original authors: Puyu Wang, Junyu Zhou, Philipp Liznerski, Marius Kloft

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Puyu Wang, Junyu Zhou, Philipp Liznerski, Marius Kloft

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize patterns, like distinguishing between different types of DNA sequences or handwritten numbers. Usually, we use a standard "brain" for robots called a Multilayer Perceptron (MLP). Think of an MLP as a factory assembly line where every worker (neuron) uses the exact same, rigid tool to do their job. It works well, but it's a bit clumsy.

Recently, scientists invented a new kind of robot brain called a Kolmogorov–Arnold Network (KAN). Instead of using rigid tools, every worker in a KAN gets to learn their own custom, flexible tool. This makes the robot much better at spotting complex patterns, especially in science and biology.

However, there was a big problem: nobody knew the rules for how to train these new robots efficiently, how to make sure they didn't just memorize the training data (generalization), or how to train them without stealing secrets from the data (privacy).

This paper is like a user manual and a safety guide for training these new KAN robots using a method called Gradient Descent (which is just a fancy way of saying "learning by trial and error").

Here is what the authors discovered, broken down into simple concepts:

1. The "Goldilocks" Size (Optimization)

When you build a KAN, you have to decide how many workers (neurons) to hire. This is called the width.

The Old Belief: You needed a massive factory (a huge number of workers) to get good results.
The New Discovery: You don't need a massive factory. You only need a small, manageable team (specifically, a number of workers that grows very slowly as the problem gets bigger).
The Analogy: Imagine trying to solve a maze. The old theory said you needed an army of people to find the exit. This paper shows that a small, well-coordinated scout team is actually enough to find the path quickly.

2. Not Just Memorizing (Generalization)

If you teach a student too many specific facts, they might fail a test with slightly different questions. This is called "overfitting."

The Discovery: Because KANs have this special flexible structure, when you train them with the right number of workers, they don't just memorize the training data. They actually learn the rules of the game.
The Result: The paper proves mathematically that if you stop training at the right time, the robot will perform well on new, unseen data. It's like a student who learns the concept of "gravity" rather than just memorizing that "apples fall," so they can predict that "feathers fall" too.

3. The Privacy Shield (Differential Privacy)

In fields like medicine or biology, you can't just share patient data to train a robot. You need Differential Privacy (DP). This is like adding a layer of "static noise" to the data so that no single person's information can be reverse-engineered, but the overall pattern remains clear.

The Challenge: Adding noise usually makes learning harder. You might think you need a huge team to overcome the noise.
The Surprise: The paper found that even with this privacy noise, you still only need a small team (a polylogarithmic width) to get good results.
The Catch: If you make the team too big, the noise gets amplified, and the robot gets confused. It's like trying to hear a whisper in a crowded room; if the room gets too big, the noise drowns out the signal.
The "Aha!" Moment: The authors found a qualitative gap here. Without privacy, a small team is enough. With privacy, a small team is not just enough, it is necessary. If you make the team too big, you actually hurt the privacy-protected performance.

4. Knowing When to Stop (Early Stopping)

The paper also gives advice on how long to train the robot.

Training Too Long: If you keep training the robot for too long, it starts to memorize the noise in the data (or the privacy noise), and its performance on new data gets worse.
The Advice: Stop training at a specific "sweet spot." The paper provides a formula to find this spot based on how much data you have and how much privacy you need.
The Analogy: It's like cooking a steak. If you cook it too long, it burns. The paper tells you exactly how many minutes to cook it so it's perfect, no matter how big the pan (width) is.

Summary of the "Rules of the Road"

The authors ran experiments (on fake data and real handwritten numbers) to prove their math works in the real world. They found:

Don't overbuild: You don't need a massive network. A moderate size is best.
Don't overtrain: Stop training before the robot starts memorizing the noise.
Privacy is tricky: When protecting privacy, keeping the network small is actually a feature, not a bug. It prevents the privacy noise from ruining the learning.

In a nutshell: This paper gives us the mathematical proof that these new, flexible AI models (KANs) can be trained efficiently, safely, and effectively without needing massive resources, provided we follow the specific rules about size and training time they discovered.

Technical Summary: Optimization, Generalization, and Differential Privacy Bounds for Gradient Descent on Kolmogorov–Arnold Networks

Problem Statement

Kolmogorov–Arnold Networks (KANs) have emerged as a structured alternative to standard Multilayer Perceptrons (MLPs), replacing fixed pointwise nonlinearities with learnable univariate edge functions. While empirical results suggest KANs excel in tasks involving structured interactions (e.g., scientific computing, genomics), a principled theoretical understanding of their training dynamics, generalization capabilities, and privacy properties remains limited. Existing theoretical analyses are predominantly algorithm-independent, focusing on expressivity rather than the behavior of concrete training algorithms like Gradient Descent (GD). Furthermore, the interaction between network width, optimization dynamics, and statistical generalization in KANs is poorly understood, particularly in the context of Differential Privacy (DP), where adding noise to gradients introduces stochastic perturbations on a non-convex landscape.

Methodology

The authors develop a unified theoretical framework to analyze two-layer KANs trained via Gradient Descent (GD) and its differentially private variant (DP-GD). The study focuses on a two-layer KAN with a single hidden layer of width $m$ , scalar output, and univariate edge functions parameterized by B-spline bases.

Key methodological components include:

Reference-Point Framework: The analysis is anchored by a reference point $\Theta^*$ (e.g., an interpolating solution). The authors derive bounds relative to the distance between the initialization and this reference point, utilizing a "stay-in-a-ball" property to ensure iterates remain in a region where the loss landscape is locally smooth and almost convex.
Self-Consistent Curvature Control: A double induction strategy is employed to simultaneously bound the cumulative training loss and the distances of iterates from the initialization and reference point. This ensures that the Hessian eigenvalues remain uniformly controlled along the trajectory, addressing the challenge that curvature in KANs depends sensitively on parameter deviations.
Trajectory-Wise Sensitivity and Stability: For the private setting, the authors perform a trajectory-wise sensitivity analysis of the projected DP-GD recursion. They explicitly calibrate Gaussian noise to satisfy $(\epsilon, \delta)$ -DP and analyze the resulting utility bounds.
Assumptions: The theoretical results rely on:
- NTK Separability: A condition weaker than the positive-definiteness of the Neural Tangent Kernel (NTK) Gram matrix, assuming the existence of a direction in parameter space that separates the data with a margin $\gamma$ .
- Logistic Loss: Specialized analysis for logistic loss under the NTK-separable assumption.
- Boundedness: Assumptions on the smoothness and boundedness of the activation functions and B-spline basis functions.

Key Contributions

1. Optimization and Fast-Rate Generalization

The paper establishes the first algorithm-dependent generalization bounds specifically for GD-trained KANs.

Optimization: Under NTK separability, the authors prove that a polylogarithmic network width ( $m \ge \text{polylog}(n, T)$ ) is sufficient for GD to achieve an optimization risk (training loss) of order $\tilde{O}(1/T)$ . This contrasts with prior work requiring polynomial width scaling.
Generalization: Combining optimization guarantees with algorithmic stability analysis, the paper derives a fast generalization rate of $\tilde{O}(1/n)$ for the population risk. This result highlights an implicit regularization bias of GD toward solutions that remain close to the initialization.

2. Differential Privacy and Utility

The authors provide the first utility analysis of DP gradient-based methods for KANs.

Noise Calibration: They derive explicit Gaussian noise variance requirements to ensure $(\epsilon, \delta)$ -DP for DP-GD on KANs, controlling sensitivity via projection onto bounded domains rather than gradient clipping.
Utility Bounds: Under NTK separability, the trajectory-averaged population risk for DP-GD is bounded by $\tilde{O}(\sqrt{d}/(n\epsilon))$ , matching the classical lower bound for general convex Lipschitz problems.
Width Necessity: A critical theoretical finding is that while polylogarithmic width is sufficient for non-private GD, it is shown to be essentially necessary for DP-GD to attain the desired utility bound. This reveals a qualitative gap between non-private and private training regimes, where privacy constraints impose stricter structural requirements.

3. Practical Implications

The theory guides practical hyperparameter selection:

Non-Private GD: Increasing width $m$ beyond a critical threshold yields diminishing returns for both training and test accuracy. Similarly, test accuracy saturates after a critical number of iterations $T$ , suggesting early stopping is beneficial for generalization.
Private DP-GD: Under a fixed privacy budget, the theory suggests using moderate widths and early stopping. Excessive width or iterations amplify the injected privacy noise, degrading utility.

Results

Theoretical Bounds: The paper provides rigorous bounds for optimization risk, population risk, and private utility. Specifically, for DP-GD, the utility bound $\tilde{O}(\sqrt{d}/(n\epsilon))$ is achieved with polylogarithmic width, matching the minimax lower bound for convex Lipschitz problems.
Empirical Validation: Experiments on synthetic logistic data and MNIST validate the theoretical predictions:
- Saturation Points: Both training and test accuracy plateau beyond empirically observed critical widths ( $m_{crit}$ ) and iterations ( $T_{crit}$ ).
- Private Utility: In the DP setting, utility peaks at moderate $m$ and $T$ before degrading due to noise accumulation, confirming the theoretical trade-off.
- NTK Separability: Empirical measurements of the NTK margin on nonlinear synthetic datasets show that KANs satisfy the separability assumption and exhibit larger margins than parameter-matched ReLU networks, particularly as width increases.

Significance and Claims

The paper claims to provide the first principled theoretical foundation for training KANs using gradient-based methods, bridging the gap between their empirical success and theoretical understanding.

Theoretical Advancement: It moves beyond algorithm-independent expressivity results to offer concrete guarantees for GD iterates, demonstrating that KANs can achieve fast convergence and generalization rates with significantly smaller widths (polylogarithmic) than previously thought necessary for MLPs under similar assumptions.
Privacy Insights: The work uniquely identifies a qualitative gap between private and non-private training, showing that privacy constraints necessitate specific width regimes to maintain utility, a finding not present in prior non-private analyses.
Practical Guidance: By linking theoretical bounds to empirical observations, the paper offers actionable guidance for practitioners regarding network architecture (width) and training duration (early stopping) to optimize performance while respecting privacy constraints.

The authors acknowledge limitations, noting that the analysis is currently restricted to two-layer KANs, assumes smooth activation functions, and focuses on full-batch GD rather than stochastic variants (SGD). Future work is proposed to extend these guarantees to deeper architectures and non-smooth activations.