🤖 machine learning

Population Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise

This paper establishes the first population risk bounds for Kolmogorov-Arnold Networks trained via mini-batch DP-SGD with correlated noise, overcoming technical challenges in non-convex optimization to provide sharper generalization guarantees that better reflect practical training scenarios than prior full-batch or independent-noise analyses.

Original authors: Puyu Wang, Jan Schuchardt, Nikita Kalinin, Junyu Zhou, Sophie Fellenz, Christoph Lampert, Marius Kloft

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Puyu Wang, Jan Schuchardt, Nikita Kalinin, Junyu Zhou, Sophie Fellenz, Christoph Lampert, 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

The Big Picture: Teaching a Smart Robot While Keeping Secrets

Imagine you have a very smart robot (called a Kolmogorov-Arnold Network, or KAN) that you want to teach how to recognize patterns, like identifying diseases from medical scans or predicting stock market trends.

Usually, to teach this robot, you show it thousands of examples. However, these examples often contain sensitive private information (like a patient's name or a company's trade secrets). You don't want the robot to memorize these secrets and accidentally reveal them later.

To stop this, mathematicians use a technique called Differential Privacy (DP). Think of this as adding a little bit of "static" or "noise" to the lessons the robot receives. This noise is like fog; it makes it hard for the robot to memorize any single specific example, but it's still smart enough to learn the general rules.

The Problem:

Old Theory: Previous math theories about how well these robots learn with privacy were based on a very slow, inefficient way of teaching called "Full-Batch." It's like a teacher reading the entire textbook to the class before asking a single question. In the real world, we teach in "mini-batches" (reading a few pages, asking a question, reading a few more). The old math didn't work for this faster, real-world method.
The Noise Issue: Standard privacy methods add "random static" that changes completely every time (Independent Noise). But researchers recently found that if the static is "correlated"—meaning the static from the last lesson helps cancel out the static from the current lesson—it works much better. It's like noise-canceling headphones. However, no one had proven mathematically that this "noise-canceling" trick works for these specific smart robots (KANs) when they are being taught quickly with mini-batches.

The Solution:
This paper is the first to write down the mathematical "guarantees" (risk bounds) for teaching these KAN robots using:

Mini-batches (the fast, real-world way).
Correlated Noise (the smart, noise-canceling privacy method).

The Core Challenges: Why Was This So Hard?

The authors faced two main hurdles, which they describe as "technical obstacles":

The "Echo" Problem: In standard privacy, the noise is random and independent. If you add noise today, it doesn't affect tomorrow. But with correlated noise, today's noise is linked to yesterday's. In math, this breaks the usual "centering" tricks used to prove things work. It's like trying to balance a stack of blocks where the bottom block keeps shifting based on how the top block moved yesterday.
The "Bouncer" Problem: To keep the robot from learning weird, extreme patterns, the training algorithm has a "bouncer" (called a projection step) that kicks the robot's settings back into a safe zone if they get too wild. The authors found that this bouncer accidentally messes up the "noise-canceling" effect. It's like a bouncer at a club who stops the noise-canceling headphones from working because they are holding the door open.

How They Solved It: The Three-Step Magic Trick

To get around these problems, the authors invented a new way of looking at the math:

The "Ghost" Robot (Auxiliary Unprojected Dynamics): Instead of watching the real robot (which gets kicked by the bouncer), they imagined a "Ghost Robot" that never gets kicked. They proved that the Ghost Robot behaves almost exactly like the real one, as long as the real robot stays in the safe zone.
The "Shifted" View (Shifted Iterate): They realized that because the noise is linked to the past, they couldn't just look at the robot's current position. They had to "shift" their perspective, effectively absorbing the current noise into the robot's state. This allowed them to see how the noise from yesterday and today cancel each other out, like two waves crashing and smoothing the water.
The "Confidence Check" (High-Probability Bootstrap): They used a statistical trick to prove that, with very high probability, the real robot never actually needs the bouncer. It stays in the safe zone on its own. This meant they could ignore the bouncer in their math and just use the "Ghost Robot" equations, which were much easier to solve.

The Results: What Did They Prove?

The paper provides a formula that tells us exactly how well the robot will perform on new, unseen data.

For Non-Private Training: They showed that even without privacy noise, using mini-batches with this specific type of robot (KAN) works very well, often better than older theories suggested.
For Private Training (Independent Noise): They confirmed that the standard "random static" method works, but they gave a sharper, more accurate formula for how much privacy you get for how much accuracy you lose.
For Private Training (Correlated Noise): This is the big win. They proved that using the "noise-canceling" (correlated) method works for these robots.
- The Catch: They found that while correlated noise is great in theory, the math gets complicated when you try to balance the "privacy budget" (how much privacy you need) with the "noise level." In their specific setup, the benefits of the noise-canceling were sometimes offset by the need to add more noise to satisfy strict privacy rules. However, they established the first mathematical foundation for this, showing that it is possible and providing the tools to make it work better in the future.

Summary Analogy

Imagine you are trying to teach a class of students (the KAN) to solve a puzzle.

Old Way: You read the whole puzzle book to them at once (Full-Batch). It's slow and boring.
Real World: You show them a few pages at a time (Mini-Batch).
Privacy: You want them to learn the logic of the puzzle, but not memorize the specific numbers on the page, because those numbers are secret. So, you whisper a little static in their ears while they study.
The Innovation: Instead of whispering random static every time, you whisper a pattern that cancels out the previous whisper (Correlated Noise).
The Paper's Contribution: Before this paper, no one knew if this "patterned whispering" would actually help the students learn the puzzle logic without getting confused. The authors proved that it does work, but they also showed that you have to be very careful about how you whisper the pattern, or the students might get confused by the "bouncer" (the safety rules) interfering with the whispers. They provided the exact recipe (the math bounds) to make this work.

Technical Summary: Population Risk Bounds for Kolmogorov–Arnold Networks Trained by DP-SGD with Correlated Noise

1. Problem Statement

The paper addresses a critical gap in the theoretical understanding of Kolmogorov–Arnold Networks (KANs), a structured alternative to Multi-Layer Perceptrons (MLPs) that parameterizes interactions via learnable univariate functions. While KANs have demonstrated strong empirical performance in scientific and engineering domains involving sensitive data, existing theoretical guarantees for their generalization (population risk) are limited.

Specifically, prior work [60] established population risk bounds for KANs only under full-batch Gradient Descent (GD) and independent-noise Differential Privacy (DP). This leaves two significant practical regimes unanalyzed:

Mini-batch Stochastic Gradient Descent (SGD) with Gradient Clipping: The standard training recipe for modern neural networks, which fundamentally alters optimization dynamics compared to full-batch GD.
Correlated-Noise DP Mechanisms: Recent mechanisms (e.g., DP- $\lambda$ CGD [28]) introduce temporal correlations in noise ( $\xi_t = \kappa(Z_t - \lambda Z_{t-1})$ ) to improve the privacy-utility trade-off. Standard DP theory assumes independent noise, and no population risk bounds exist for correlated-noise training in non-convex settings like KANs.

The core challenge is that temporal dependence in noise breaks the "conditional-centering" structure essential for standard one-step SGD analysis, while the projection steps used to ensure stability in non-convex optimization obstruct the partial cancellation of correlated perturbations.

2. Methodology and Technical Approach

The authors establish population risk bounds by decomposing the risk into optimization risk (convergence to the empirical minimum) and generalization gap (difference between empirical and population risk).

A. Optimization Analysis (Non-Convex, Correlated Noise)
To handle the correlated noise in a non-convex regime, the authors develop a novel proof framework that bypasses the limitations of standard projected SGD arguments:

Auxiliary Unprojected Dynamics: They introduce an auxiliary trajectory $\{\tilde{W}_t\}$ that evolves without projection but uses the same mini-batches and noise. This allows the analysis to focus on the noise structure without the obstruction of the projection operator.
Shifted Iterate: To address the lack of conditional centering in correlated noise (where $E[\xi_t | \mathcal{F}_{t-1}] \neq 0$ ), they define a shifted iterate $U_t = \tilde{W}_t + \eta c_{priv} Z_t$ . This transformation absorbs the current Gaussian perturbation, revealing a cancellation structure where the leading correlated term reduces to a residual proportional to $(1-\lambda)$ .
High-Probability Bootstrap: They employ a "stopped" analysis to certify that the auxiliary trajectory remains within a localized region where KAN-specific curvature estimates (based on the Neural Tangent Kernel margin) hold. This involves proving that the projection is inactive with high probability, thereby equating the projected iterates $W_t$ with the auxiliary unprojected iterates $\tilde{W}_t$ .

B. Generalization Analysis
The generalization gap is bounded using algorithmic stability. By coupling two runs of the algorithm on neighboring datasets (using the same initialization, mini-batches, and noise sequence), the authors show that the additive noise terms cancel out in the difference of iterates. The stability bound depends on the optimization risk derived in the previous step.

C. Privacy Accounting
The paper provides a privacy guarantee for the correlated-noise mechanism (DP- $\lambda$ CGD) under uniform subsampling without replacement. It derives an analytical upper bound on the noise multiplier $\kappa$ required to satisfy $(\epsilon, \delta)$ -DP, utilizing dominating pairs and hockey-stick divergence to account for the correlation structure.

3. Key Contributions

The paper makes the following specific contributions:

First Population Risk Bounds for KANs in Practical Regimes: It establishes the first population risk bounds for two-layer KANs trained by clipped mini-batch SGD, covering both non-private and DP settings. This moves KAN theory beyond the full-batch GD setting of [60].
First Non-Convex Correlated-Noise DP Analysis: To the best of the authors' knowledge, this is the first population risk analysis for a correlated-noise mechanism in a non-convex setting. It instantiates this for KANs trained with clipped mini-batch DP-SGD.
Sharp Specializations: The results recover and improve upon existing bounds:
- For non-private mini-batch SGD, the bounds yield an optimization and population risk of order $O(1/n)$ in the polylogarithmic-width regime, suppressing logarithmic factors and dependence on the NTK margin $\gamma$ .
- For independent-noise DP-SGD ( $\lambda=0$ ), the bounds match the convex DP-SCO lower bound of [7] up to logarithmic factors and improve upon the full-batch DP-GD results of [60] by reducing the required network width and the dependence on the NTK margin.
- For correlated-noise DP-SGD, the analysis identifies how the correlation parameter $\lambda$ influences the optimization risk, though the final population risk rate (under conservative privacy calibration) asymptotically matches the independent-noise rate.

4. Main Results

Under representative parameter regimes (polylogarithmic width $m \asymp \text{polylog}(n)$ ), the paper derives the following population risk rates for the averaged iterates:

Non-Private Mini-batch SGD:
$\text{Risk} \lesssim \frac{1}{n}$
This improves upon the $O(1/(\gamma^4 n))$ rate for full-batch GD in [60] by achieving $O(1/(\gamma^2 n))$ with a smaller required width.
Differentially Private (Independent and Correlated Noise):
Under $(\epsilon, \delta)$ -DP, both independent and correlated noise mechanisms attain the rate:
$\text{Risk} \lesssim \frac{1}{\gamma \sqrt{n}} + \frac{\sqrt{d}}{\gamma^4 n \epsilon}$
(up to polylogarithmic factors).
The analysis shows that while temporal correlation improves the optimization error term (scaling with $1-\lambda$ ), the conservative closed-form privacy calibration required for the theoretical guarantee offsets this gain in the final population risk bound. The authors note that sharper privacy accounting might reveal improved $\lambda$ -dependent rates.

5. Significance and Claims

The paper claims to provide the first optimization and population risk analysis of a correlated-noise mechanism for DP training beyond convex learning, specifically for neural networks (KANs).

Theoretical Novelty: The technical core—combining auxiliary unprojected dynamics, shifted iterates, and high-probability bootstrapping—offers a new route for analyzing correlated-noise DP training in non-convex regimes, which may be of independent interest beyond KANs.
Practical Relevance: By covering mini-batch SGD and correlated noise, the results bridge the gap between theoretical guarantees and the "standard recipe" used in modern deep learning and federated learning systems.
Limitations: The authors modestly acknowledge that the final population risk rate for correlated noise matches the independent-noise rate asymptotically under their current conservative privacy calibration. They identify sharper privacy accounting as an open question that could potentially unlock the theoretical benefits of correlation in the final risk bounds. Additionally, the analysis is currently restricted to two-layer KANs with fixed second-layer coefficients.