acceptodds
Under review as a conference paper at ICLR 2027

Exact Privacy Calibration for Random-Feature Kernel Means

Abstract

Random Fourier features enable compact releases of private kernel means for querying and learning. Uniform-sensitivity calibration ignores variation in feature distances across random maps and can require more Gaussian noise than necessary. For scale mixtures of Gaussian kernels, we derive exact calibration of map-independent isotropic Gaussian noise for public Fourier feature means with independent or orthogonal frequencies. With independent frequencies, the required variance approaches half the uniform-sensitivity variance as the feature count grows on unbounded domains, with further reductions under public input bounds. Independent sampling also requires the least noise on the full input space among nonresonant designs with the same marginal frequency distribution and feature count. These noise reductions improve query accuracy most when privacy noise dominates feature approximation. Experiments across five kernels and four datasets show lower query error. With protected labels, our calibration improves data reconstruction and downstream SVM accuracy, with gains of – percentage points at over uniform-sensitivity calibration.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, kernel methods, random Fourier features

Reviews

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

This paper proposes an improved privacy calibration for releasing random-feature kernel means. By accounting for randomness in the feature map, it reduces the noise required for the same privacy guarantee. I find it very difficult to read and follow their development, due to the lack of insights and explanations.

Critical strengths

None.

Critical weaknesses

Releasing a private embedding once and reusing it for generation or learning were already possible in DP-MERF. The contribution is sharper calibration within this framework. The experiments do not establish an advantage over DP-HP or private Nyström methods.

The gain is bounded and often small in absolute terms. On unbounded domains the noise variance is at most halved, and larger reductions require a public domain bound. At the reference setting, the absolute query-error differences in Table 3 are tiny and nearly constant across kernels and datasets. Since query values are never reported, readers cannot judge practical significance. Relative gains are large only when privacy noise dominates the error. Reporting relative errors, or an equivalent privacy budget or sample size, would help.

On Adult, the headline accuracy improvement accompanies lower macro-F1, and performance can deteriorate as noise decreases toward the unperturbed reference. The private bandwidth experiments contain further reversals. These outcomes are reported but insufficiently explained. Class-specific errors, reconstructed class proportions, and solver convergence diagnostics would help distinguish the effects of regularization, reconstruction, and noise. The substantial losses from reconstruction even without privacy noise also deserve discussion.

Questions for authors

For Adult, what calibration results if the domain diameter is the largest distance between valid one-hot encoded records rather than the diagonal of the clipping box? Also, orthogonal features reduce the approximation error by roughly 26 times. Is it driven by the one-hot geometry or by the bandwidth choice? Can you explain the accuracy–macro-F1 disagreement and the deterioration as noise decreases?

Does the method remain competitive against private Nyström method under comparable total budgets?

5 comments

Thank you for your detailed feedback on the presentation of our results and the evidence for their practical value.

We believe that addressing the comments from all reviewers has substantially improved the paper. We have uploaded a revised manuscript incorporating the changes made in response to these comments. Changes are marked in blue. Throughout our responses, equation, section, table, and figure numbers refer to the revision.

We have tried to answer each point with a change in the manuscript. We welcome any further comments or questions. If the revision and our responses resolve all of your concerns, we would be grateful if you could reconsider your score.

Significance and presentation.

Random Fourier feature means are widely used in private kernel learning [1, 2]. Their practical value is also evident in our comparisons: ORF with Uniform AG has lower query MSE than DP-HP and private Nyström on all four datasets at all six tested privacy budgets (Figure 7 in Appendix G.6).

Conventional calibration uses a uniform sensitivity bound that requires more noise than the joint release needs. We identify how the feature map's randomness changes this privacy requirement and derive the exact privacy profile and minimum isotropic Gaussian noise scale. Tight noise calibration is a central problem in differential privacy.

At ε=1\varepsilon=1, Exact reduces ORF query MSE by 12–57% and improves SVM accuracy by 1.1–9.8 percentage points over Uniform AG (Figures 2 and 5).

We revised the abstract and introduction to clarify our focus on reducing the noise required for differentially private kernel mean releases through exact calibration. Sections 3 and 4 explain the purpose of each stage of the analysis before presenting the formal results. We also added a notation table at the start of the appendix.

Contribution.

Releasing and reusing a private mean of random Fourier features is an established approach in private kernel learning, used in DP-MERF [1] and compressive learning [2]. Our results reduce the Gaussian noise required for these releases at the same (ε,δ)(\varepsilon,\delta) guarantee.

For each dataset in our ORF query experiments, Exact guarantees ε=1\varepsilon=1 while Uniform AG guarantees only ε=1.46\varepsilon=1.46–1.861.86 at the same noise scale and δ=10−6\delta=10^{-6} (Table 8 in Appendix G.2).

DP-HP and private Nyström.

To address these comparisons, we added DP-HP [4] and private Nyström [3] results in Appendix G.6, Figure 7. All methods use the same RBF queries, records, and total privacy budgets, with δ=10−6\delta=10^{-6}. At ε=1\varepsilon=1:

DatasetORF Uniform AGORF ExactPrivate NyströmDP-HP
Adult3.391e-061.446e-063.146e-031.237e-03
Covertype6.177e-064.317e-068.592e-042.766e-03
USPS1.218e-051.074e-051.879e-021.752e-04
ISOLET3.928e-062.482e-065.776e-032.855e-01

ORF with Uniform AG has lower query MSE than both alternatives. Exact further reduces ORF query MSE by 12–57% relative to Uniform AG.

References

[1] Frederik Harder et al. DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-preserving Data Generation. AISTATS, 2021.

[2] A. Chatalic et al. Compressive learning with privacy guarantees. Information and Inference, 2021.

[3] Bonwoo Lee, Jeongyoun Ahn, and Cheolwoo Park. Differential Privacy in Scalable General Kernel Learning via K-means Nyström Random Features. NeurIPS, 2024.

[4] Margarita Vinaroz et al. Hermite Polynomial Features for Private Data Generation. ICML, 2022.

Kernel approximation and calibration gains.

The results in the submitted Table 3 (Table 6 in Appendix G.1 of the revision) used r=2pr=2p for every kernel. Equation (19) decomposes query MSE into RFF approximation error and privacy noise variance. Approximation error decreases as rr increases, and at r=2pr=2p it was substantially larger for the other kernels than for RBF. Because Exact calibration reduces the noise term, the relative improvement is small when approximation error dominates.

We then compared kernels at similar approximation accuracy, measured without DP noise. Table 7 in Appendix G.1 reports the smallest tested rr whose approximation MSE is no larger than that of RBF at r=2pr=2p, with these rr values ranging from 4p4p to 128p128p across the four non-RBF kernels and datasets. Figure 6 in Appendix G.1 shows the relative MSE reductions as rr increases, with filled markers indicating the minimum rr values reported in Table 7. At these points, the reductions are comparable to or greater than those of RBF at r=2pr=2p for both ε=0.1\varepsilon=0.1 and 11.

Query scale and equivalent privacy budgets.

Table 8 in Appendix G.2 reports query means, standard deviations, and root mean squared percentage errors (RMSPE) at ε=1\varepsilon=1. RMSPE divides each query's squared error by the square of its true value before averaging and taking the square root.

DatasetQuery meanQuery SDAG RMSPE (%)Exact RMSPE (%)Equivalent AG ε\varepsilon
Adult0.92620.010250.1990.1301.859
Covertype0.91040.008120.2730.2291.769
USPS0.60410.062310.6510.6191.463
ISOLET0.69540.033000.2890.2311.465

The last column gives the Uniform AG privacy budget at the noise scale for which Exact guarantees ε=1\varepsilon=1, with δ=10−6\delta=10^{-6} for both.

Adult metrics and decreasing noise.

Adult's minority class comprises 24.76% of the protected data and 23.62% of the evaluation data. At ε=1\varepsilon=1 and λ=0.002\lambda=0.002, Table 14 in Appendix I.3 gives the following results, shown here with error rates for each class (percentages):

ReleaseAccuracyMacro-F1Majority errorMinority errorReconstructed minority share
Unperturbed77.1047.390.4495.5124.87
Uniform AG78.7267.9111.9751.3825.09
Exact80.2366.947.1560.5825.06

Exact makes fewer errors on the majority class and more on the minority class than Uniform AG, explaining its higher accuracy and lower macro-F1.

The deterioration as noise decreases is consistent with the regularizing effect of modest DP noise observed in prior work [5]. Both noisy releases reduce minority errors compared with the unperturbed reconstruction.

The reconstruction and SVM training objectives decrease and flatten in the cases with reversals (Figure 11 in Appendix I.3). These curves show no sustained divergence.

References

[5] Harsha Nori et al. Accuracy, Interpretability, and Differential Privacy via Explainable Boosting. ICML, 2021.

Loss without privacy noise.

The large noiseless losses at r=2pr=2p mainly reflect the limited feature count. Keeping the bandwidth, reconstruction procedure, and λ\lambda fixed, we obtain the following accuracies (%) without privacy noise:

rrUSPS originalUSPS reconstructedISOLET originalISOLET reconstructed
2p2p93.0386.3688.9780.76
4p4p93.1789.0988.7781.46
8p8p93.1591.3188.8483.13
16p16p93.2192.2088.9785.95
32p32p93.1792.4088.8487.17
64p64p93.1492.9788.9087.94

At r=64pr=64p, accuracy on reconstructed data is within one percentage point of accuracy on the original data on both datasets.

Valid one-hot domain.

The main experiments use coordinate clipping and box diameters as a common rule across datasets. Adult's public encoding constraints allow a smaller diameter, L2=28L^2=28. Table 11 in Appendix G.5 gives the scales at ε=1\varepsilon=1, δ=10−6\delta=10^{-6}:

Calibrationiid noise scaleORF noise scaleORF variance / AG
Uniform AG1.689872e-31.689872e-31.000
Exact, box9.57886e-49.54103e-40.319
Exact, valid domain5.54975e-45.47820e-40.105

ORF query MSE decreases from 1.44565×10−61.44565\times10^{-6} with the box bound to 8.35449×10−78.35449\times10^{-7} with the encoding constraints, a further 42.2% reduction. Uniform AG gives 3.391×10−63.391\times10^{-6}.

ORF's approximation gain.

The large gap appears mainly due to the bandwidth. On Adult, the ratio of iid to ORF approximation MSE is 24.45 at the reference RBF bandwidth parameter γ=1/p\gamma=1/p (about 26 from the rounded table entries). Changing γ\gamma to 8/p8/p and 32/p32/p reduces the ratio to 11.36 and 1.92, respectively.

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

The paper studies Gaussian noise calibration for private kernel means represented by random Fourier features. It accounts for the randomness of the public feature map when analyzing the joint release of the map and the noisy mean. The authors derive exact privacy profiles for independent and orthogonal random features. On unbounded domains, the required noise variance for independent features approaches half that of Uniform AG calibration as the number of features grows. They also establish an optimality result for independent sampling within a specified class of frequency designs.

The experiments evaluate kernel queries, data reconstruction, and SVM classification. They show that tighter calibration can improve accuracy, particularly when privacy noise is a substantial source of error. The downstream gains depend on the dataset and regularization setting.

Critical strengths
  1. The paper gives a precise way to reduce the noise needed for private random-feature means. Accounting for the public map's randomness leads to an exact privacy profile, and the asymptotic half-variance result provides a clear measure of the potential improvement. This is useful because it improves calibration without changing the form of the released statistic.

  2. Theorem 4 provides an optimality result within a clearly defined design class. On Rp\mathbb{R}^p, independent sampling minimizes the required noise among the nonresonant designs considered. The comparison fixes the number of frequencies, their marginal distribution, and the use of fixed, map-independent isotropic Gaussian noise. This gives a principled reference for assessing dependent designs such as ORF.

Critical weaknesses
  1. The main classification experiments provide limited evidence about the practical value of the full numerical ORF calibration. In the reference settings, the cross-label term in Eq. (22) determines the noise scale and gives half the Uniform AG variance. These results demonstrate the benefit of lower noise, but leave the role of the numerical profile calibration less clear. Reporting the actual noise scales and certification values would help connect the experimental results to the procedure in Appendix D.1.

  2. The noise calibration of the multiclass DP-SVM baseline needs further justification. Appendix I.1 uses a sensitivity bound of 42/(nλ)4\sqrt{2}/(n\lambda). For the stated regularized Crammer–Singer objective with unit-norm features, the exact minimizer admits a bound of 22/(nλ)2\sqrt{2}/(n\lambda). If this tighter bound applies to the implementation, it would halve the baseline's noise standard deviation. This could affect the reported advantage over direct DP-SVM.

Questions for authors
  1. Could you report the actual noise scales and the corresponding values of U(nσ)U(n\sigma) for the USPS and ISOLET reference experiments at ϵ=5\epsilon=5? Please explain how these values satisfy Eqs. (57)–(58) and relate to the statement that the cross-label term determines the experimental noise scale.

  2. What accounts for the factor 424\sqrt{2} in the multiclass baseline's sensitivity bound? Does the tighter bound for the exact minimizer apply to your implementation? If so, how does recalibrating the baseline affect the comparison?

3 comments

Thank you for your careful review and your questions about ORF calibration and the multiclass sensitivity bound.

We believe that addressing the comments from all reviewers has substantially improved the paper. We have uploaded a revised manuscript incorporating the changes made in response to these comments. Changes are marked in blue. Throughout our responses, equation, section, table, and figure numbers refer to the revision.

We welcome any further comments or questions. If the revision and our responses resolve all of your concerns, we would be grateful if you could reconsider your score.

The role of ORF calibration.

In every condition in Figure 5, σO≤σG/2\sigma_{\rm O}\le\sigma_G/\sqrt2, where σG\sigma_G (σU\sigma_{\rm U} in the revision) is the Uniform AG scale. Equation (22) therefore selects the cross-label scale:

σlab=max⁡{σO,σG/2}=σG/2.\sigma_{\mathrm{lab}}=\max\{\sigma_{\rm O},\sigma_G/\sqrt2\}=\sigma_G/\sqrt2.

ORF calibration establishes the comparison required by Equation (22), even when σG/2\sigma_G/\sqrt2 is selected. We have made this role explicit in Section 5.4.

The noise scales used in Figure 5 are the same for all four datasets, with n=5000n=5000, r=2pr=2p, and δ=10−6\delta=10^{-6}:

ε\varepsilonσlab\sigma_{\mathrm{lab}}
0.10.010268517
0.20.005370844
0.50.002279039
10.001194920
20.000630874
50.000277200

To analyze when σO\sigma_{\rm O} instead determines the final scale, we added Proposition 10 in Appendix D.3. Its sufficient condition for σO>σG/2\sigma_{\rm O}>\sigma_G/\sqrt2 can hold with a smaller RBF bandwidth.

Appendix J provides experimental examples where smaller bandwidths make σO\sigma_{\rm O} determine the final noise scale. We estimated the bandwidth from the data with differential privacy. At r=2pr=2p, the estimated bandwidths are smaller than the reference ℓ=p/2\ell=\sqrt{p/2} on all four datasets at all six tested privacy budgets. The calibrated ORF scale exceeds σG/2\sigma_G/\sqrt2 on average for every dataset and budget (Table 15 in Appendix J.1).

USPS and ISOLET at epsilon 5.

For the USPS and ISOLET experiments in Figure 5 at ε=5\varepsilon=5, the noise scale is σG/2\sigma_G/\sqrt2, where σG\sigma_G (σU\sigma_{\rm U} in the revision) is the Uniform AG scale. Equation (57) gives an upper bound U(nσ)U(n\sigma) on the ORF privacy profile δO(ε;σ)\delta_{\rm O}(\varepsilon;\sigma). If σG/2\sigma_G/\sqrt2 satisfies Equation (58), then σO≤σG/2\sigma_{\rm O}\le\sigma_G/\sqrt2, and Equation (22) selects σG/2\sigma_G/\sqrt2. At this noise scale, the values are:

DatasetσG/2\sigma_G/\sqrt2U(nσG/2)U(n\sigma_G/\sqrt2)
USPS2.771997176×10−42.771997176\times10^{-4}9.249161605×10−79.249161605\times10^{-7}
ISOLET2.771997176×10−42.771997176\times10^{-4}8.802925660×10−78.802925660\times10^{-7}

Both values satisfy U(nσG/2)≤δ−η=9.9×10−7U(n\sigma_G/\sqrt2)\le\delta-\eta=9.9\times10^{-7}. Since σG/2\sigma_G/\sqrt2 satisfies the condition in Equation (58), the cross-label term determines the experimental noise scale in Equation (22).

Multiclass sensitivity.

We mistakenly followed the 42/(nλ)4\sqrt2/(n\lambda) bound in Park et al.'s public code [2]. Equation (11) of their paper [1] gives 22/(nλ)2\sqrt2/(n\lambda) for the stated objective. We reran the multiclass DP-SVM experiments with this bound and updated Figure 5 and Appendix I.2. Adult's binary baseline is unchanged.

The accuracy gains of Exact over the corrected baseline across all four datasets and six privacy budgets in Figure 5 are shown below, in percentage points:

Datasetε=0.1\varepsilon=0.10.20.20.50.5112255
Adult0.001.301.643.853.171.28
Covertype28.1227.8224.5715.1610.158.42
USPS16.6910.9617.4413.9010.078.82
ISOLET4.8211.8834.2149.6350.9533.12

Exact retains higher accuracy in 23 of the 24 conditions and equal accuracy on Adult at ε=0.1\varepsilon=0.1.

References

[1] Jinseong Park, Yujin Choi, and Jaewook Lee. Multi-Class Support Vector Machine with Differential Privacy. NeurIPS, 2025.

[2] https://github.com/JinseongP/private_multiclass_svm

The author's response has addressed my concerns. I have no objection to the AC's decision to accept this paper, and I will maintain my score.

Thank you for confirming that our response addressed your concerns. We would appreciate your candid feedback on what further improvements would be needed for a stronger recommendation. This would help us develop the work further.

Reviewer_tmz9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies privacy noise calibration for random-feature kernel mean embeddings under differential privacy. It proposes an exact calibration method that accounts for the distribution of feature distances across randomly sampled Fourier maps, rather than relying on conventional uniform-sensitivity bounds. The theoretical analysis establishes exact privacy profiles for independent and orthogonal random features and demonstrates that the proposed calibration can asymptotically reduce the required Gaussian noise variance by half on unbounded domains. Experiments across five kernels and four datasets demonstrate improvements in kernel query accuracy, data reconstruction quality, and downstream SVM classification performance.

Critical strengths
  • The paper provides a theoretically rigorous analysis of privacy calibration for random-feature kernel means.
  • The paper conducts comprehensive experiments across different kernel families, datasets, privacy budgets, and random-feature configurations.
Critical weaknesses
  • The applicability of the proposed exact calibration is limited by several assumptions, including data-independent random-feature maps, map-independent isotropic Gaussian noise, and Gaussian scale-mixture kernels.
  • The comparison with direct DP-SVM in Section 5.4 may not sufficiently establish the advantages of the proposed approach for downstream learning. As shown in Figure 5, the reconstructed-data SVM uses a regularization parameter of λ=0.002\lambda=0.002, while direct DP-SVM uses λ=0.5\lambda=0.5.
  • The computational overhead of the proposed calibration requires further investigation.
Questions for authors

See weaknesses.

1 comment

Thank you for your careful review and your questions about the scope of the method and the experimental comparisons.

We believe that addressing the comments from all reviewers has substantially improved the paper. We have uploaded a revised manuscript incorporating the changes made in response to these comments. Changes are marked in blue. Throughout our responses, equation, section, table, and figure numbers refer to the revision.

We welcome any further comments or questions. If the revision and our responses resolve all of your concerns, we would be grateful if you could reconsider your score.

Scope.

Data-independent random feature maps are widely used in private kernel learning [1-4]. In our query comparisons, ORF with Uniform AG has lower mean query MSE than DP-HP [5] and private Nyström [6] on all four datasets at all six tested privacy budgets (Figure 7 in Appendix G.6).

The proposed exact calibration also extends to data-dependent random feature maps constructed with a privately estimated bandwidth. We allocate part of the privacy budget to estimating the bandwidth, then calibrate the mean release conditional on that estimate. Appendix J evaluates this extension.

Isotropic Gaussian noise is the standard choice for the Gaussian mechanism [7]. The scale is map-independent in conventional calibration because it is set using a worst-case sensitivity bound that applies to every feature map.

Scale mixtures of Gaussian kernels cover widely used kernel families, including RBF, rational-quadratic, Matérn, and Euclidean Laplacian kernels. Figure 4 and Appendix G.1 evaluate these kernels.

Regularization.

We initially used a common λ\lambda, but direct DP-SVM performed poorly. We then selected λ=0.002\lambda=0.002 for the reconstructed-data methods and λ=0.5\lambda=0.5 for direct DP-SVM in preliminary experiments for each method, keeping these values fixed across datasets and privacy budgets. Section 5.4 now states this selection procedure.

To assess the effect of this choice, we added comparisons at all nine shared penalties in Appendix I.2, separately at ε=0.1,1,5\varepsilon=0.1,1,5 (Figures 8 to 10). Each mean gain below is in percentage points and averages the conditions where that method has higher accuracy.

Penalty comparisonExact higherExact's mean gain when aheadEqualDirect higherDirect's mean gain when ahead
Same λ\lambda, 108 conditions8424.2114103.17
Best λ\lambda per method, 12 conditions1116.05011.73

With each method's best λ\lambda, Exact is ahead by an average of 14.56 percentage points across all 12 conditions. Direct DP-SVM is ahead only on USPS at ε=5\varepsilon=5.

Calibration cost.

Table 2 in Appendix D.4 reports the calibration times:

Datasetiid (s)ORF (s)
Adult0.5933.77
Covertype0.329.83
USPS1.43103.78
ISOLET3.7087.79

Iid calibration is fast because independent frequencies reduce the calculation to a one-dimensional distance distribution. ORF must account for dependence among orthogonal frequencies and evaluate the privacy profile over a range of input distances, which requires more numerical integration.

References

[1] Frederik Harder et al. DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-preserving Data Generation. AISTATS, 2021.

[2] A. Chatalic et al. Compressive learning with privacy guarantees. Information and Inference, 2021.

[3] Jinseong Park et al. Efficient differentially private kernel support vector classifier for multi-class classification. Information Sciences, 2023.

[4] Yujin Choi et al. Differentially private upsampling for enhanced anomaly detection in imbalanced data. Engineering Applications of Artificial Intelligence, 2026.

[5] Margarita Vinaroz et al. Hermite Polynomial Features for Private Data Generation. ICML, 2022.

[6] Bonwoo Lee, Jeongyoun Ahn, and Cheolwoo Park. Differential Privacy in Scalable General Kernel Learning via K-means Nyström Random Features. NeurIPS, 2024.

[7] Borja Balle and Yu-Xiang Wang. Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. ICML, 2018.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Follow-up on our responses and revised manuscript

Dear Reviewers and Area Chair,

Thank you again for your time and comments.

We have posted responses to each review and uploaded a revised manuscript incorporating the additional experiments and clarifications. These include additional baseline comparisons, experiments across kernels, and clarification of the ORF noise calibration.

Before the discussion closes, we would appreciate hearing whether our responses address your concerns and which points still need clarification. We would be happy to discuss further.

Area_Chair_NNA6OpenReview ↗

Dear Reviewers

Since the author-reviewer discussion ends soon, I encourage the reviewer to review the authors' rebuttals and let them know whether their responses are satisfactory and whether any concerns remain, if you haven't done so.

Thank you for your time and effort in reviewing for ICLR 2027.

Best wishes,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.