acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

The theoretical understanding of differentially private stochastic gradient descent (DP-SGD) with temporally correlated noise remains limited, particularly for non-convex neural network training. As a first step, we study two-layer Kolmogorov–Arnold Networks (KANs), a recently introduced architecture with learnable spline-based edge functions. We establish the first optimization risk bounds for clipped mini-batch DP-SGD with correlated noise in this setting, with explicit dependence on temporal correlation, clipping, mini-batch sampling, and network width. Existing arguments fail for three reasons: temporal dependence breaks the conditional-centering step; projection obstructs the cross-iteration cancellation of correlated perturbations; and active clipping breaks the empirical-gradient structure. We address these issues through shifted and auxiliary dynamics, a weighted empirical loss, and a high-probability localization argument. Our bound shows that temporal correlation reduces the leading noise terms, the clipping threshold enters essentially through an effective step size, and private training admits an explicit network width range. Experiments on synthetic data and MNIST support the predicted optimization effect of temporal correlation. As an application, we derive population risk guarantees via algorithmic stability. Our framework recovers non-private mini-batch SGD, independent-noise DP-SGD, and their full-batch counterparts as special cases.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, SGD, Correlated Noise, Kolmogorov–Arnold Networks, Optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wtC9OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies two-layer Kolmogorov–Arnold networks (KANs) trained using clipped mini-batch DP-SGD with temporally correlated Gaussian noise. Despite the nonconvex training objective, it establishes empirical and population risk bounds that explicitly characterize the effects of clipping, noise correlation, mini-batch sampling, and network geometry. The analysis combines shifted dynamics, a weighted empirical loss, and localization, with population risk analyzed through algorithmic stability. Experiments on synthetic data and MNIST illustrate the potential optimization benefits of temporal correlation.

Critical strengths
  1. An interesting theoretical problem. Understanding the effect of correlated-noise is very valuable to the DP field. The paper addresses this question in a nonconvex setting with several interacting sources of complexity.
  2. Useful technical ideas. The analysis relies on several ideas (such as the comparator argument and an shifted-iterate construction that exposes noise cancellation) that offer insight into noise cancellation and contribute beyond a straightforward combination of existing results. These ideas may also be useful beyond KANs. While I have not verified every proof step, I find the overall proof strategy insightful.
  3. Interpretable guarantees. The explicit characterization of the effects of clipping and noise correlation in the bounds helps explain their impacts on performance. Moreover, these results also cover many existing results, such as no clipping, independetn noise, etc.
Critical weaknesses
  1. Limited scope of the theoretical guarantees. The analysis focuses on two-layer KANs with the logistic loss. As the authors also acknowledged, extending the results to other architectures, jointly trained layers, or different loss functions remains an open question.
  2. The connection between theory and experiments could be clearer. The guarantees impose coupled conditions on network width, step size, and noise level. Clarifying how the experimental configurations relate to these conditions would help readers understand which aspects of the theory the experiments support.
Questions for authors
  1. Theorem 1 does not explicitly state the required choice of the projection radius R∗R_*. Given that the proof analyzes an auxiliary unprojected trajectory, could the authors clarify how R∗R_* should be selected and whether the guarantee relies on projection remaining inactive? Intuitively, how would a smaller radius affect optimization?
  2. Assumption 2 appears central to the analysis, and its expression resembles the logistic loss function. To what extent is this separability condition tied to logistic loss, and what modifications or additional assumptions would be needed to extend the analysis to other loss functions?
3 comments
AuthorsOpenReview ↗

Response to Reviewer wtC9 (1/2)

We thank the reviewer for the careful and constructive review. In response, we have made the following changes in the revision.

  1. Optimization and population risk guarantees for joint training of both layers (Theorems 61 and 62, Appendix I).
  2. A reorganized Appendix H with detailed experimental settings and additional experiments.
  3. The projection radius R∗R_* is now stated explicitly in Theorem 1.

Our point-by-point responses follow.


W1: The analysis focuses on two-layer KANs with the logistic loss. As the authors also acknowledged, extending the results to other architectures, jointly trained layers, or different loss functions remains an open question.

A. First, we have now extended our optimization and population risk guarantees to jointly training both layers, stated as Theorems 61 and 62 in Appendix I of the revision, with complete proofs. The resulting bounds have the same leading rates as those obtained when only the first layer is trained, up to replacing dd by d+1d+1 in the leading noise-dependent term, and the network-width requirements remain of the same order.

Second, we consider two-layer KANs as a first step toward understanding the learning guarantees of neural networks trained by DP-SGD with correlated noise. Extending the analysis to deeper KANs and other neural network architectures is an interesting direction for future work, but would require additional techniques to control their training dynamics.

Finally, our analysis focuses on binary classification with the logistic loss. The proofs rely on the margin-decay, self-boundedness, and smoothness properties of the loss, suggesting that extensions to other classification losses satisfying suitable conditions may be possible. Extending the results to regression, however, would require different analytical techniques, which we leave for future work.

W2: The guarantees impose coupled conditions on network width, step size, and noise level. Clarifying how the experimental configurations relate to these conditions would help readers understand which aspects of the theory the experiments support.

A. We thank the reviewer for this helpful suggestion. The coupled conditions on network width, step size, and noise level are sufficient conditions for our theoretical guarantees. They involve implicit constants, logarithmic factors, and the separability margin γ\gamma, and thus do not provide exact numerical prescriptions for the experimental parameters. Our experiments are therefore designed to examine the qualitative predictions of the theory rather than to verify these sufficient conditions directly. In the revision, we have reorganized Appendix H, providing detailed experimental settings and additional experiments.

In particular, the matched-privacy experiments in Appendix H.3 use the same B/n=0.1B/n=0.1 and T=400T=400 as the new mini-batch example in Section 5, satisfying the condition BT/n≥3log⁡(4/δ)BT/n\ge 3\log(4/\delta) of Proposition 43. The noise multipliers are calibrated using the sensitivity bound of this proposition and the analytic Gaussian mechanism. The experiments and the predictions they examine are summarized below.

Varied quantityPrediction examinedLocation
Correlation λ\lambda (fixed κ\kappa)Correlation-dependent noise factors in Theorem 1Figure 2 (Section 4.2)
Step size η\etaQuadratic noise term grows with ηeff\eta_{\mathrm{eff}}Figures 3, 4 (Appendix H.2)
Correlation λ\lambda (fixed privacy)Mini-batch example in Section 5 and the tradeoff in Remark 2Figure 5 (Appendix H.3)
Batch size BBNoise terms scale with ceff∝1/Bc_{\mathrm{eff}}\propto 1/BFigure 6 (Appendix H.4)
Network width mmSufficient network width and growth of the quadratic noise term with mmFigures 6, 7 (Appendix H.4)
Clipping threshold CclipC_{\mathrm{clip}}Dependence through ηeff\eta_{\mathrm{eff}} in the active clipping regime (Remark 1)Figure 6 (Appendix H.4)

Overall, the observed trends are qualitatively consistent with the theory.

AuthorsOpenReview ↗

Response to Reviewer wtC9 (2/2)

Q1: Could the authors clarify how R∗R_* should be selected and whether the guarantee relies on projection remaining inactive? Intuitively, how would a smaller radius affect optimization?

A. Thank you for these questions. We answer them in turn.

(1) Choice of R∗R_*. We take R∗≍log⁡(T/ρclip)+log⁡(n/δ)γR_*\asymp\frac{\log(T/\rho_{\mathrm{clip}})+\sqrt{\log(n/\delta)}}{\gamma}, which is now stated explicitly in Theorem 1 of the revision. This is the order of the distance from the initialization to the comparator constructed from Assumption 2, and is also sufficient to contain the auxiliary trajectory under the conditions of Theorem 1.

(2) Role of the projection. The guarantee applies to the projected Algorithm 1. Inactivity of the projection is not assumed. It is established in the proof, where we show that, under the conditions of Theorem 1 and with high probability, the auxiliary unprojected trajectory stays inside K=B(W0,R∗)\mathcal K=\mathcal B(\mathbf W_0,R_*) for all t≤Tt\le T, so it coincides with the iterates of Algorithm 1 (Step 5 of the proof sketch). The projection is nevertheless needed for Theorem 2. In the stability analysis, the two coupled trajectories on neighboring datasets always remain in K\mathcal K. Their common Gaussian perturbations cancel in the difference of the pre-projection updates, while the non-expansiveness of the projection controls the distance between the resulting iterates. The DP guarantee holds for every fixed choice of R∗R_*.

(3) Effect of a smaller radius. If R∗R_* is below this order, two things can happen. First, the comparator may fall outside K\mathcal K, so the low-loss comparator used in our analysis is no longer guaranteed to be feasible. Second, the projection may become active, restricting the updates and potentially limiting progress toward a low-loss solution, while also preventing us from exploiting the exact noise cancellation in our shifted-iterate analysis. This is one of the technical challenges discussed in Section 4.1. Conversely, a larger R∗R_* strengthens the width requirement, which scales as R∗4R_*^4. This is where the lower bound Ω~(γ−4)\widetilde\Omega(\gamma^{-4}) on the width in Theorem 1 comes from. The stated order ensures the required localization without unnecessarily enlarging the projection region.

Q2: To what extent is the separability condition in Assumption 2 tied to logistic loss, and what modifications or additional assumptions would be needed to extend the analysis to other loss functions?

A. The separability condition requires that the training data can be linearly separated with a positive margin γ\gamma in the tangent feature space induced by the network at initialization, and is independent of the choice of loss function.

In our analysis, NTK separability allows us to construct a comparator with sufficiently large classification margins, while the exponential decay of the logistic loss ensures that this comparator achieves a small empirical risk. The self-boundedness and smoothness properties of the loss, namely ∣ℓ′(a)∣≤min⁡(1,ℓ(a))|\ell'(a)|\le\min(1,\ell(a)) and ℓ′′(a)≤∣ℓ′(a)∣\ell''(a)\le|\ell'(a)|, are further used to control the training dynamics. Thus, the analysis could be extended to other classification losses with analogous margin-decay, self-boundedness, and smoothness properties. Regression losses such as the squared loss do not satisfy these properties, and extending our guarantees to regression remains an open problem, as noted in the conclusion.

I want to thank the authors for the detailed responses. My concerns have been sufficiently addressed. I maintain my original assessment and recommend accept.

Reviewer_hAo1OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper establishes an optimization risk bound for DP-SGD with temporally correlated noise (DP-λCGD) for two-layer KANs (only the first layer is trained). The authors identify the scientific bottlenecks of the proof and propose to use shifted and auxiliary dynamics to alleviate them. The paper is mostly theoretical, and the experiments focus on the effect of λ\lambda on synthetic data and MNIST (3 vs. 8).

Critical strengths
  • The authors propose the first optimization risk bound for clipped mini-batch DP-SGD with correlated noise (DP-λCGD) in a non-convex setting. The proposed bound makes explicit the effect of clipping, of the correlation parameter λ\lambda and of the network width on the risk.
Critical weaknesses
  • The result is limited to two-layer KANs with only the first layer trained. The authors claim that it can easily be extended to the case where both layers are trained, but this is not proven.
  • The experiments focus only on λ\lambda and do not cover the other parameters of the bound (clipping threshold, width mm, batch size, etc.).
  • The paper relies heavily on a very long appendix (about 50 pages), which may make it better suited to a journal.
Questions for authors
  • How do the authors explain the collapse of the accuracy in Fig. 3 when λ\lambda is close to one?
  • How large is the benefit of temporal correlation under a matched privacy budget in practice?
2 comments
AuthorsOpenReview ↗

Response to Reviewer hAo1

We thank the reviewer for the careful and constructive review. We have made the following main changes in the revision.

  1. Guarantees for joint training of both layers (Theorems 61 and 62, Appendix I).
  2. Experiments on the batch size, network width, and clipping threshold (Appendix H.4).
  3. Experiments under a matched privacy budget (Appendix H.3).

Our point-by-point responses follow.


W1: Can the results be extended, with proof, to joint training of both layers?

A. We have now provided rigorous optimization and population risk guarantees for jointly training both layers, stated as Theorems 61 and 62 in Appendix I of the revision, with complete proofs. The resulting bounds have the same leading rates as in the fixed-second-layer setting, up to replacing dd by d+1d+1 in the leading noise-dependent term, and the network-width requirements remain of the same order.

W2: The experiments focus only on λ\lambda and do not cover the other parameters of the bound (clipping threshold, width, batch size, etc.).

A. We have added experiments on the batch size BB, network width mm, and clipping threshold CclipC_{\mathrm{clip}} in Appendix H.4 of the revision (Figures 6 and 7). Our experiments show the following: (1) At a fixed noise multiplier κ\kappa, the benefit of temporal correlation grows as the batch size BB decreases. (2) For network width mm, performance largely stabilizes once mm exceeds roughly 3232 for both private and non-private training, consistent with our sufficient-width condition, which depends only polylogarithmically on nn for fixed γ\gamma. Moreover, temporal correlation reduces the loss gap between private and non-private training across all tested widths. (3) At a fixed effective step size ηeff\eta_{\mathrm{eff}}, the final training loss is nearly independent of the clipping threshold when clipping is active for essentially all examples, consistent with Remark 1. These observations are qualitatively consistent with Theorem 1.

W3: The paper relies heavily on a very long appendix (about 50 pages), which may make it better suited to a journal.

A. We appreciate this observation. A large part of the appendix is included for completeness. Beyond the proofs of the two main theorems, it provides detailed derivations for the special cases recovered by our framework, such as independent noise DP-SGD and non-private training, as well as additional experiments. The main text is self-contained, and the key ideas can be followed from the proof sketch in Section 4.3 without reading the appendix.

Q1: How do the authors explain the collapse of the accuracy in Fig. 3 when λ\lambda is close to one?

A. This behavior is consistent with the deterioration of our optimization and population risk bounds under the fixed-privacy calibration, reflecting the tradeoff noted in Remark 2. Both the empirical risk (Theorem 1) and the population risk (Theorem 2) are controlled by AcorrA_{\mathrm{corr}}, which contains the quadratic noise-dependent term ((1−λ)2+λ2ηeff)ηeffceff2md\big((1-\lambda)^2+\lambda^2\eta_{\mathrm{eff}}\big)\eta_{\mathrm{eff}}c_{\mathrm{eff}}^2md with ceff∝κλc_{\mathrm{eff}}\propto\kappa_\lambda. Under the fixed-privacy calibration used in Appendix H.3, the noise multiplier κλ\kappa_\lambda increases rapidly as λ\lambda approaches one (Table 1 of the revision). The factor (1−λ)2(1-\lambda)^2 offsets this increase, whereas the contribution λ2ηeffκλ2\lambda^2\eta_{\mathrm{eff}}\kappa_\lambda^2 grows and can dominate. Hence temporal correlation helps for moderate λ\lambda, while the bounds deteriorate when λ\lambda is close to one. In the revision, the fixed-privacy experiments, which replace Fig. 3 of the original submission, are reported in Appendix H.3 (Figure 5 and Table 1), where the training loss (left panels) is minimized and the held-out accuracy (right panels) is maximized at an intermediate λ\lambda, before deteriorating beyond it.

Q2: How large is the benefit of temporal correlation under a matched privacy budget in practice?

A. We have added experiments under a matched privacy budget (ϵ,10−5)(\epsilon,10^{-5}) in Appendix H.3 of the revision (Figure 5), where the noise multiplier is recalibrated for each λ\lambda without subsampling amplification. Compared with independent noise (λ=0\lambda=0), the best λ\lambda improves the held-out accuracy as follows.

ϵ\epsilonSyntheticMNIST 3 vs. 8
158.9% → 62.8%78.7% → 86.0%
267.2% → 72.5%89.4% → 91.4%
476.4% → 78.4%92.5% → 93.0%

The gains are generally larger under stronger privacy constraints, since the privacy noise itself becomes smaller as ϵ\epsilon grows. The best performance is attained for λ\lambda between 0.60.6 and 0.80.8.

Thank you for the detailed rebuttal and the additional experiment. I will maintain my current score, as the limited scope of the paper keeps me from recommending a higher rating. That said, I believe the paper is worth publishing.

Reviewer_sL5iOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper gives optimization bounds (average training loss along the trajectory) for clipped mini-batch DP-SGD with DP-λ\lambdaCGD noise, ξt=κ(Zt−λZt−1)\xi_t = \kappa (Z_t - \lambda Z_{t-1}), on two-layer B-spline KANs where only the first-layer coefficients W\mathbf{W} are trained and the second layer c\mathbf{c} stays at its random init. Assumptions are bounded basis/activation derivatives and NTK separability with margin γ\gamma. Theorem 1 bounds 1T∑t=0T−1LS(Wt)\frac{1}{T}\sum_{t=0}^{T-1} \mathcal{L}_S(\mathbf{W}_t) in terms of an effective step size ηeff=ρclipη\eta_{\mathrm{eff}} = \rho_{\mathrm{clip}} \eta with ρclip=min⁡{1,Cclip/Gδ}\rho_{\mathrm{clip}} = \min \lbrace 1, C_{\mathrm{clip}}/G_\delta \rbrace, an effective noise level ceff=Cclipκ/(Bρclip)c_{\mathrm{eff}} = C_{\mathrm{clip}} \kappa /(B \rho_{\mathrm{clip}}), the batch size BB, horizon TT, width mm and λ\lambda. The noise terms are (1−λ)ceff/(γT)(1-\lambda) c_{\mathrm{eff}}/(\gamma \sqrt{T}) and ((1−λ)2+λ2ηeff)ηeffceff2md\big((1-\lambda)^2 + \lambda^2 \eta_{\mathrm{eff}}\big) \eta_{\mathrm{eff}} c_{\mathrm{eff}}^2 m d, and there is an admissible width window Ω~(γ−4)≤m≤O~(⋅)\tilde{\Omega}(\gamma^{-4}) \le m \le \tilde{O}(\cdot). The proof works on an unprojected auxiliary trajectory, shifts the iterate by ηcprivZt\eta c_{\mathrm{priv}} Z_t to expose the (1−λ)(1-\lambda) cancellation, freezes the clipping coefficients so that the clipped average is the gradient of a weighted empirical loss, and closes a localization bootstrap so the projection is inactive. Theorem 2 turns this into a population risk bound via stability. Section 5 shows correlation strictly helps at matched privacy in a full-batch (B=nB = n) finite-horizon example (E.1), while under a worst-case mini-batch calibration (Theorem 35) the rate matches independent noise, O(1/(γn)+d/(γ4nε))O\big(1/(\gamma \sqrt{n}) + \sqrt{d}/(\gamma^4 n \varepsilon)\big). Experiments are small (m=32m = 32, p=8p = 8, n=5000n = 5000, B=125B = 125, T=400T = 400, 5 seeds), run at fixed κ∈{6.3,11.8}\kappa \in \lbrace 6.3, 11.8 \rbrace, and show the averaged training loss going down with λ\lambda on synthetic data and MNIST 3-vs-8; Appendix H has fixed-privacy accuracy curves.

Critical strengths

The technical story holds together. Section 4.1 correctly names the three things that break (conditional centering, the projection versus the cross-step cancellation, clipping destroying the gradient structure), and the fixes fit: the shifted iterate, the frozen-coefficient weighted loss with ρclipLS≤LS,tα≤LS\rho_{\mathrm{clip}}\mathcal{L}_S \le \mathcal{L}^{\alpha}_{S,t} \le \mathcal{L}_S, and the stopped localization argument. Getting back the Wang et al. (2026) rates for full-batch DP-GD and plain GD, and the usual 1/n+d/(nε)1/\sqrt{n} + \sqrt{d}/(n\varepsilon) for independent-noise DP-SGD, is a decent sanity check, and I take it as evidence that the long proofs are at least not wildly off.

Remark 1 is the clearest takeaway in the paper: in the active clipping regime the threshold only enters through ηeff\eta_{\mathrm{eff}} (up to logs), so aggressive clipping can be undone with a larger nominal step size η\eta, and above GδG_\delta raising the threshold only adds noise. That is a statement practitioners can use.

Critical weaknesses
  • The claim about correlation is not established in the regime the paper is about. The λ\lambda-dependence in Theorem 1 is at fixed κ\kappa. At fixed κ\kappa, less accumulated noise for larger λ\lambda is what one expects before doing any analysis, since the injected noise mostly telescopes; the question that matters is matched (ε,δ)(\varepsilon, \delta). The paper answers that positively only for full batch with exact finite-horizon calibration (E.1). Under its own mini-batch calibration (Theorem 35, which is an operator-norm bound times a high-probability participation count, with no amplification) κ\kappa has to grow like (1−λT)/(1−λ)(1-\lambda^T)/(1-\lambda), so the linear noise term (1−λ) ceff(1-\lambda)\,c_{\mathrm{eff}} is unchanged and the quadratic one gets multiplied by 1+λ2ηeff/(1−λ)2≥11 + \lambda^2\eta_{\mathrm{eff}}/(1-\lambda)^2 \ge 1. In the mini-batch setting the correlated bound is therefore no better than the independent one. So the theory does not explain the phenomenon that motivates the paper, and the abstract's "temporal correlation reduces the leading noise terms" needs a qualifier. The Section 4 experiments (fixed κ\kappa, vary λ\lambda) only confirm the direction everybody expects; none of the non-obvious predictions get tested (the interior optimum λ⋆=1/(1+ηeff)\lambda^\star = 1/(1+\eta_{\mathrm{eff}}), clipping compensated by ηeff\eta_{\mathrm{eff}}, the width window). The fixed-privacy curves in Appendix H do not say which accountant recalibrated κ\kappa, so I cannot tell whether they correspond to Theorem 35 at all.

  • The scope is narrower than the title. The second layer is frozen, while Wang et al. (2026), the closest prior work, train both layers. The analysis is local/NTK, with a data-dependent margin γ\gamma sitting inside the step-size condition and the projection radius R⋆R^\star. KAN-ness only enters through the constants of Assumption 1. What remains is a careful but incremental extension of Wang et al. built from known pieces: the shifted iterate is the perturbed-iterate view of anti-correlated noise (Orvieto et al. 2022; Koloskova et al. 2023), and frozen clipping weights and localization bootstraps are standard. I checked the statement of Theorem 1 and the special-case rates for consistency; I did not go through the roughly 50 pages of proofs line by line.

Questions for authors
  1. Is there any regime of Theorem 1 combined with Theorem 35, with B<nB < n, where the correlated bound is strictly below the independent-noise bound at the same (ε,δ)(\varepsilon, \delta)? If not, please say so in the abstract and introduction.

  2. In Appendix H, how was κ\kappa recalibrated for each λ\lambda (which accountant, with or without amplification)? Is it consistent with Theorem 35?

  3. R⋆=CR τγR^\star = C_R\,\tau_\gamma and the step-size condition depend on the margin γ\gamma of the private sample. How does that square with the DP guarantee, and what R⋆R^\star did the experiments actually use?

  4. How does the shifted-iterate identity in Step 2 relate to the anti-PGD equivalence in Orvieto et al. (2022) and to Koloskova et al. (2023)? What is new beyond combining it with localization?

  5. Could you test one non-trivial prediction, for example loss invariance to CclipC_{\mathrm{clip}} at fixed ηeff\eta_{\mathrm{eff}} in the active clipping regime, or the optimum λ\lambda shifting with ηeff\eta_{\mathrm{eff}}?

6 comments
AuthorsOpenReview ↗

Response to Reviewer sL5i (1/4): Scope and Theoretical Results

We thank the reviewer for the careful and constructive review. We have made the following main changes in the revision.

  1. A mini-batch example under a matched privacy budget (Section 5 and Appendix E.3).
  2. Guarantees for joint training of both layers (Theorems 61 and 62, Appendix I).
  3. New experiments, including fixed-privacy experiments and experiments on the step size, batch size, network width, and clipping threshold (Appendix H).
  4. A discussion of the relation to existing analyses (Sections 4.1 and 4.2).

Our point-by-point responses follow.


1. Scope and Theoretical Results

W1 & Q1: Is there any regime in the mini-batch setting (B<nB<n) where the correlated bound is strictly below the independent-noise bound at the same (ϵ,δ)(\epsilon,\delta)?

A. Yes. In the revision, we add a mini-batch example showing that temporal correlation can yield a strictly smaller population risk bound than independent noise at the same (ϵ,δ)(\epsilon,\delta) when B<nB<n (Section 5 and Appendix E.3). The calibration in Theorem 35 uses a worst-case operator-norm sensitivity bound that does not account for the temporal spacing of record participations, and therefore does not establish an improvement in the mini-batch setting. Our example instead uses a refined privacy calibration based on Freedman's inequality, without subsampling amplification. We also add experiments under this calibration with the same B/n=0.1B/n=0.1 and T=400T=400 as in the example (Appendix H.3, Figure 5). At the same privacy budget, temporal correlation improves on independent noise, for instance from 78.7% to 86.0% held-out accuracy on MNIST and from 58.9% to 62.8% on synthetic data at ϵ=1\epsilon=1. Finally, we have revised the abstract and introduction to clarify the scope of the improvement under a common privacy budget.

Example. Let B<nB<n and BT≥3nlog⁡(4/δ)BT\ge 3n\log(4/\delta). Under the refined calibration, the linear and quadratic privacy-dependent terms are multiplied, relative to independent noise, by factors R1(λ)R_1(\lambda) and R2(λ)R_2(\lambda). For fixed B/n<1B/n<1, as T→∞T\to\infty, R1(λ)R_1(\lambda) converges to ((1−(1−2B/n)λ)/(1+λ))1/2<1\big((1-(1-2B/n)\lambda)/(1+\lambda)\big)^{1/2}<1 for every λ∈(0,1)\lambda\in(0,1), while the limit of R2(λ)R_2(\lambda) is 1−2(1−B/n)λ+O(λ2)1-2(1-B/n)\lambda+\mathcal O(\lambda^2) as λ→0+\lambda\to0^+. Thus, for sufficiently small λ>0\lambda>0, the improvement does not vanish as TT grows. For instance, with B/n=0.1B/n=0.1, T=400T=400, δ=10−4\delta=10^{-4}, λ=0.2\lambda=0.2, and any admissible ηeff≤0.1\eta_{\mathrm{eff}}\le0.1, we obtain R1≈0.894R_1\approx0.894 and R2≤0.805R_2\le0.805. Under the common admissibility conditions of Theorems 1 and 2, the correlated mechanism therefore achieves a strictly smaller population risk upper bound under the same privacy budget.

W2: Can the results be extended to joint training of both layers?

A. We have now extended our optimization and population risk guarantees to jointly training both layers, stated as Theorems 61 and 62 in Appendix I of the revision, with complete proofs. The resulting bounds have the same leading rates as those obtained when only the first layer is trained, up to replacing dd by d+1d+1 in the leading noise-dependent term, and the network-width requirements remain of the same order.

W2: Why two-layer KANs in the NTK regime, and can the analysis extend to other neural networks?

A. Our primary goal is to establish theoretical guarantees for DP-SGD with temporally correlated noise in non-convex neural networks. We study two-layer KANs as a concrete first step, where the network structure allows us to establish the required gradient and curvature estimates and derive optimization and population risk bounds under NTK separability. Our analysis suggests potential extensions to other neural networks satisfying analogous geometric conditions, although verifying these conditions would require architecture-specific analysis. Importantly, our results do not require the network width to grow polynomially with the sample size nn. Extensions beyond the NTK regime remain an interesting direction for future work.

AuthorsOpenReview ↗

Response to Reviewer sL5i (2/4): Theoretical Novelty

2. Theoretical Novelty

W2 & Q4: How does the analysis relate to Wang et al. (2026), to the shifted iterate of Orvieto et al. (2022) and Koloskova et al. (2023), and to frozen clipping weights and localization bootstraps? What is new beyond combining them?

A. Our analysis uses the shifted-iterate transformation of Orvieto et al. (2022) and Koloskova et al. (2023), together with the NTK localization framework of Wang et al. (2026). However, in our setting with temporally correlated noise, mini-batch sampling, and active clipping, the conditions underlying these analyses become coupled, so that controlling one component affects the others. Resolving these interactions requires new estimates to control the resulting error terms. The table below summarizes the differences, and the four points that follow explain the key challenges and their solutions. We have also added a discussion in Sections 4.1 and 4.2 of the revision.

Wang et al. (2026)Orvieto et al. (2022)Koloskova et al. (2023)Ours
Noiseindependentanticorrelated (λ=1\lambda=1)linearly correlatedλ∈[0,1)\lambda\in[0,1)
Gradients (analysis)full gradientfull gradientfull gradientmini-batch
Settingtwo-layer KAN, NTK-separableLipschitz third-order derivativesLL-smoothtwo-layer KAN, NTK-separable
Clippingnonono†yes
Projectionyesnonoyes
Guaranteerisk boundsimplicit regularizationstationarityrisk bounds

†Gradient clipping is omitted from the analysis (Koloskova et al., 2023, Section 3).

(1) Conditional centering versus correlated noise. The DP-GD analysis of Wang et al. (2026) exploits the conditional centering of independent Gaussian noise, both to eliminate cross terms in expectation and to obtain high-probability bounds via martingale concentration. This property no longer holds for temporally correlated noise. The shifted iterate exposes the cross-iteration noise cancellation, leaving a residual term proportional to 1−λ1-\lambda and an additional mismatch term that must be controlled separately.

(2) Shifted iterate versus projection. The shifted-iterate identity holds for unprojected dynamics, whereas in Wang et al. (2026) the projection keeps the iterates in the local region. Projection generally destroys the exact cancellation of correlated noise. We therefore introduce an auxiliary unprojected trajectory and prove that it coincides with the projected algorithm with high probability. Thus, projection inactivity must be established as part of the analysis.

(3) Global smoothness versus local comparator geometry. Koloskova et al. (2023) control the mismatch between their virtual sequence and the real iterates using global smoothness. However, global smoothness alone does not yield the comparator inequality needed for our risk analysis, which holds only near initialization. We control the mismatch through the self-bounding property of the loss, which yields the λ2ηeff\lambda^2\eta_{\mathrm{eff}} contribution in Theorem 1. Unlike standard NTK localization arguments, our analysis must simultaneously control the shifted and auxiliary unprojected trajectories, including the Gaussian displacement between them. We establish this through a high-probability bootstrap, which also contributes to the correlation-dependent upper bound on the network width.

(4) Active clipping versus the comparator argument. Per-sample clipping has previously been analyzed through clipping factors. For example, Bu et al. (2023) show that per-sample clipping can prevent the training loss from decreasing monotonically. In our setting, the averaged clipped gradient is not the gradient of the empirical loss, so the usual comparator argument cannot be applied directly. We instead construct an iteration-dependent weighted empirical loss by freezing the clipping coefficients, and establish a local comparator inequality for this auxiliary loss. This allows us to handle arbitrary positive clipping thresholds together with temporally correlated noise. In the active clipping regime, the clipping threshold enters the bound essentially through the effective step size ηeff\eta_{\mathrm{eff}}, up to logarithmic factors (Remark 1).

Together, these arguments establish optimization and population risk guarantees for clipped mini-batch DP-SGD with temporally correlated noise (Theorems 1 and 2), recover the full-batch rates of Wang et al. (2026), and support the matched-privacy improvements established in Section 5.

AuthorsOpenReview ↗

Response to Reviewer sL5i (3/4): Experiments

3. Experiments

W1 & Q5: Could the experiments test non-trivial predictions of the theory, for example the invariance to CclipC_{\mathrm{clip}} at fixed ηeff\eta_{\mathrm{eff}}, the admissible width range, or the optimal λ\lambda?

A. Thank you for this suggestion. We have added experiments examining these theoretical predictions in Appendix H of the revision.

(1) Invariance to CclipC_{\mathrm{clip}} at fixed ηeff\eta_{\mathrm{eff}}. We fix ηeff=1\eta_{\mathrm{eff}}=1 and vary CclipC_{\mathrm{clip}} from G/32G/32 to 4G4G, where GG is the largest per-example gradient norm at initialization, used as an empirical proxy for GδG_\delta. The final training losses are reported below (Figure 6 in Appendix H.4).

Cclip/GC_{\mathrm{clip}}/G1/321/161/81/41/2124
λ=0\lambda=00.5930.5930.5920.5940.6190.6630.7120.747
λ=0.5\lambda=0.50.5210.5210.5190.5210.5560.6160.6640.711
λ=0.9\lambda=0.90.4920.4920.4880.4890.5220.5870.5930.615

When Cclip≤G/4C_{\mathrm{clip}}\le G/4, the final training loss varies by less than 0.0050.005 across the tested clipping thresholds for each λ\lambda, supporting the invariance predicted by Remark 1. For larger thresholds, clipping becomes less prevalent and performance deteriorates. Once Cclip>GC_{\mathrm{clip}}>G, the noise scale in the parameter updates also increases.

(2) Network width. We vary mm from 88 to 256256 and compare with non-private training under the same initialization. The performance largely stabilizes once mm exceeds roughly 3232, for both private and non-private training (Figure 6 in Appendix H.4). This suggests that relatively modest network widths suffice in this setting, consistent with our sufficient-width condition, which depends only polylogarithmically on nn for a fixed separability margin γ\gamma. The loss gap caused by privacy noise is generally larger for wider networks, consistent with the quadratic noise-dependent term in Theorem 1, which grows with mm and gives rise to the upper bound on the width. Temporal correlation reduces the gap at every width, typically to around one quarter of that of independent noise for λ=0.5\lambda=0.5, and to below 10−310^{-3} for λ=0.9\lambda=0.9 (Figure 7 in Appendix H.4).

(3) Effect of λ\lambda. For fixed κ\kappa, the quadratic noise factor (1−λ)2+λ2ηeff(1-\lambda)^2+\lambda^2\eta_{\mathrm{eff}} is minimized at λ=1/(1+ηeff)\lambda=1/(1+\eta_{\mathrm{eff}}). The full bound also contains a linear noise term proportional to 1−λ1-\lambda. In our fixed-κ\kappa experiments, the training loss generally decreases with λ\lambda across all tested step sizes (Figure 2 in Section 4.2 and Figures 3–4 in Appendix H.2), consistent with the benefit of temporal noise cancellation. Under a fixed privacy budget, however, an interior optimum appears, with the best performance attained for λ\lambda between 0.60.6 and 0.80.8 (Figure 5 in Appendix H.3), reflecting the tradeoff with privacy calibration discussed in Remark 2.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers and the AC

We sincerely thank all reviewers for their careful reading and constructive feedback, based on which we were able to further improve the manuscript. We have uploaded a revised PDF, in which the changes in the main text are marked in blue. The conclusions of our original main theorems remain unchanged.

We summarize the main improvements here:

  1. Mini-batch improvement under a matched privacy budget (sL5i, hAo1). We provide a new example with B<nB<n showing that temporal correlation yields a strictly smaller population risk bound than independent noise under the same (ϵ,δ)(\epsilon,\delta), using a refined privacy calibration without subsampling amplification (Section 5 and Appendix E.3). New experiments under the corresponding calibration, using uniform mini-batch sampling and the same B/nB/n and TT as in the example, demonstrate improvements in held-out accuracy (Appendix H.3).

  2. Joint training of both layers (hAo1, sL5i, wtC9). We extend our optimization and population risk guarantees to jointly training both layers, with complete proofs (Theorems 61 and 62 in Appendix I). The resulting bounds preserve the leading rates of the fixed-second-layer setting, with network-width requirements of the same order.

  3. Additional experiments and connections to theory (hAo1, sL5i, wtC9). We add experiments on the step size, batch size, network width, and clipping threshold, examining their corresponding effects in Theorem 1 (Appendices H.2 and H.4). We also provide detailed experimental settings (Appendix H.1) and clarify which qualitative predictions of the theory each experiment examines.

  4. Technical novelty relative to prior work (sL5i). We clarify the theoretical advances over Wang et al. (2026) and the relationship between our shifted-iterate analysis and the approaches of Orvieto et al. (2022) and Koloskova et al. (2023). In particular, we explain the additional technical challenges arising from local network geometry, projection, and active clipping (Sections 4.1 and 4.2).

We thank all reviewers and the AC again for their time and valuable feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.