Research map / Federated learning and privacy / Differential privacy
Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes differentially private kernel ERM, kernel mean embedding release, and private data release for general kernels by combining K-means-based Nyström random features with DP linear learners.
Problem
Differentially private kernel learning has been limited for general (non-translation-invariant) kernels, scalability, and test-data-free prediction, and DP kernel mean embedding release suffers from high dimensionality.
Approach
Use a DP K-means-based Nyström approximation to build data-dependent random features for general kernels, then apply existing DP linear ERM (or DP KME/data release) on top of those features, with privacy via the composition theorem.
Key results
- On a simulated polynomial-boundary task, the DP 3rd-order polynomial kernel ERM with 200 Nystrom features outperforms Gaussian RFF and linear kernels across privacy budgets.
- For DP kernel mean embedding on adult, the DP K-means Nystrom method yields lower RKHS embedding error than the Balog et al. (2018) algorithm and subsampling Nystrom across privacy budgets.
- Theorems give excess empirical risk bound En,m(beta)+c||K-K_hat||_2^2/(2 lambda n) for the proposed DP kernel ERM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the 3rd-order polynomial kernel instead of the Gaussian RBF or linear kernel | scalable DP kernel ERM · simulated classification | classification accuracy | Helped |
| use K-means-based Nyström landmarks instead of subsampling-based Nyström landmarks | DP KME · Adult | RKHS embedding error | Helped |
| use K-means-based Nyström landmarks instead of data-independent random landmarks | DP KME · Adult | RKHS embedding error | Helped |
| allocate 20% of the privacy budget to random-feature construction and 80% to DP ERM instead of allocating equally | DP kernel ERM · simulated classification | classification accuracy | Helped |
| use Nyström-based methods instead of random Fourier features | kernel matrix approximation · Adult | relative Frobenius approximation error | Helped |
Surprising findings
- Allocating 20% of the privacy budget to random feature construction and 80% to DP ERM improved accuracy over the equal split, suggesting the equal allocation is not optimal.
Limitations
- Current implementation is limited to Euclidean data because DP K-means is used; K-medoids suggested as remedy.
- Balance of privacy budget between Nystrom features and DP ERM is not theoretically optimized and tuning may leak privacy.
- Small epsilon values degrade the data-dependent Nystrom accuracy.
Experimental setup
Datasets: simulated truncated-normal mixture data adult bank marketing CDC diabetes health indicators credit card fraud MNIST
Benchmarks: simulated polynomial-boundary classification adult KME approximation error bank/CDC/credit/MNIST KME estimation
Metrics: classification accuracy RKHS embedding error relative Frobenius kernel approximation error
Baselines: Chaudhuri et al. 2011 random Fourier features Balog et al. 2018 Algorithm 1 Subsampling-based DP Nystrom Hall et al. 2013
Builds on: Chaudhuri et al. 2011 DP ERM via random features Kifer et al. 2012 DP linear ERM Zhang et al. 2008 K-means Nystrom Balog et al. 2018 DP kernel mean embedding Hall et al. 2013 functional perturbation Zheng et al. 2017 local DP ERM polynomial approximation
Closest papers by meaning
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.89)
- Multi-Class Support Vector Machine with Differential Privacy (NeurIPS 2025 · similarity 0.88)
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · similarity 0.87)
- The importance of feature preprocessing for differentially private linear optimization (ICLR 2024 · similarity 0.87)
- Efficiently Computing Similarities to Private Datasets (ICLR 2024 · similarity 0.87)
- Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.