- 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
Kernel approximation and calibration gains.
The results in the submitted Table 3 (Table 6 in Appendix G.1 of the revision) used for every kernel. Equation (19) decomposes query MSE into RFF approximation error and privacy noise variance. Approximation error decreases as increases, and at 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 whose approximation MSE is no larger than that of RBF at , with these values ranging from to across the four non-RBF kernels and datasets. Figure 6 in Appendix G.1 shows the relative MSE reductions as increases, with filled markers indicating the minimum values reported in Table 7. At these points, the reductions are comparable to or greater than those of RBF at for both and .
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 . RMSPE divides each query's squared error by the square of its true value before averaging and taking the square root.
| Dataset | Query mean | Query SD | AG RMSPE (%) | Exact RMSPE (%) | Equivalent AG |
|---|---|---|---|---|---|
| Adult | 0.9262 | 0.01025 | 0.199 | 0.130 | 1.859 |
| Covertype | 0.9104 | 0.00812 | 0.273 | 0.229 | 1.769 |
| USPS | 0.6041 | 0.06231 | 0.651 | 0.619 | 1.463 |
| ISOLET | 0.6954 | 0.03300 | 0.289 | 0.231 | 1.465 |
The last column gives the Uniform AG privacy budget at the noise scale for which Exact guarantees , with 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 and , Table 14 in Appendix I.3 gives the following results, shown here with error rates for each class (percentages):
| Release | Accuracy | Macro-F1 | Majority error | Minority error | Reconstructed minority share |
|---|---|---|---|---|---|
| Unperturbed | 77.10 | 47.39 | 0.44 | 95.51 | 24.87 |
| Uniform AG | 78.72 | 67.91 | 11.97 | 51.38 | 25.09 |
| Exact | 80.23 | 66.94 | 7.15 | 60.58 | 25.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 mainly reflect the limited feature count. Keeping the bandwidth, reconstruction procedure, and fixed, we obtain the following accuracies (%) without privacy noise:
| USPS original | USPS reconstructed | ISOLET original | ISOLET reconstructed | |
|---|---|---|---|---|
| 93.03 | 86.36 | 88.97 | 80.76 | |
| 93.17 | 89.09 | 88.77 | 81.46 | |
| 93.15 | 91.31 | 88.84 | 83.13 | |
| 93.21 | 92.20 | 88.97 | 85.95 | |
| 93.17 | 92.40 | 88.84 | 87.17 | |
| 93.14 | 92.97 | 88.90 | 87.94 |
At , 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, . Table 11 in Appendix G.5 gives the scales at , :
| Calibration | iid noise scale | ORF noise scale | ORF variance / AG |
|---|---|---|---|
| Uniform AG | 1.689872e-3 | 1.689872e-3 | 1.000 |
| Exact, box | 9.57886e-4 | 9.54103e-4 | 0.319 |
| Exact, valid domain | 5.54975e-4 | 5.47820e-4 | 0.105 |
ORF query MSE decreases from with the box bound to with the encoding constraints, a further 42.2% reduction. Uniform AG gives .
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 (about 26 from the rounded table entries). Changing to and reduces the ratio to 11.36 and 1.92, respectively.
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, 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 (ε,δ) guarantee.
For each dataset in our ORF query experiments, Exact guarantees ε=1 while Uniform AG guarantees only ε=1.46–1.86 at the same noise scale and δ=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. At ε=1:
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.