- 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
- 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.
- 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.
- 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
- 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.
- 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
- Theorem 1 does not explicitly state the required choice of the projection radius . Given that the proof analyzes an auxiliary unprojected trajectory, could the authors clarify how should be selected and whether the guarantee relies on projection remaining inactive? Intuitively, how would a smaller radius affect optimization?
- 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
Response to Reviewer wtC9 (2/2)
Q1: Could the authors clarify how 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 . We take , 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 for all , 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 . 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 .
(3) Effect of a smaller radius. If is below this order, two things can happen. First, the comparator may fall outside , 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 strengthens the width requirement, which scales as . This is where the lower bound 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 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 and , 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.
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.
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 d by d+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 γ, 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.1 and T=400 as the new mini-batch example in Section 5, satisfying the condition BT/n≥3log(4/δ) 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.
Overall, the observed trends are qualitatively consistent with the theory.