Exact Privacy Calibration for Random-Feature Kernel Means

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 $1$–$10$ percentage points at $\epsilon =1$ over uniform-sensitivity calibration.