Research map / Federated learning and privacy / Differential privacy
The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches
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.
Gives a tighter Rényi DP analysis of the Gaussian mixing mechanism (noisy Gaussian sketch) and uses it to build private linear and logistic regression algorithms with better accuracy than prior baselines.
Problem
Privacy guarantees of Gaussian sketching (GaussMix, S X + sigma xi) were previously loose, and existing DP linear regression via sketching lacked tight analysis; the goal is a tighter privacy analysis and better private regression.
Approach
Derive a closed-form RDP curve for the noisy Gaussian sketch by exploiting Gaussian rows with covariance X^T X + sigma^2 I, bounding the divergence via the minimum eigenvalue (scale bound), and use it to set noise in DP least squares (with privately estimated lambda_min) and, via a second-order logistic surrogate, DP logistic regression.
Key results
- The derived RDP bound gives epsilon <= k/(2gamma^2) + sqrt(2k log(1/delta))/gamma, tighter than the prior Sheffet bound with an extra 2log(4/delta)/gamma term.
- The proposed DP linear regression matches AdaSSP's theoretical excess risk rate and outperforms AdaSSP and Sheffet's Algorithm 1 across the evaluated regression datasets at the same privacy level.
- DP logistic regression via the sketching approach improves accuracy and computation time over objective perturbation on binary Fashion-MNIST and CIFAR100 subsets using private CNN embeddings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LinearMixing with the refined RDP analysis | private ordinary least squares · four regression datasets | empirical loss | Helped |
| use LinearMixing instead of AdaSSP | private ordinary least squares · four regression datasets | runtime | No clear effect |
| apply the new privacy analysis to the prior linear-regression algorithm | private ordinary least squares · four regression datasets | empirical loss | Helped |
| use the proposed sketching approach instead of objective perturbation | private logistic regression · Fashion-MNIST and CIFAR100 binary subsets | accuracy | Helped |
| use the proposed sketching approach instead of objective perturbation | private logistic regression · Fashion-MNIST and CIFAR100 binary subsets | computation time | Helped |
Surprising findings
- Retrofitting the new RDP analysis into Sheffet's Algorithm 1 also improves its performance.
Limitations
- Analysis requires a row bound and a scale bound on lambda_min, which cannot be enforced in general; without it the mechanism is a noisier Gaussian-mechanism analog.
- Analysis restricted to Gaussian sketches; other projection classes not covered.
- Applications limited to linear-regression-form problems; logistic regression uses a second-order polynomial approximation.
Experimental setup
Datasets: Communities & Crime Tecator Fashion-MNIST CIFAR100 synthetic Gaussian regression data
Benchmarks: Communities & Crime Tecator Fashion-MNIST CIFAR100 synthetic Gaussian regression
Metrics: excess empirical risk test accuracy runtime RDP curve comparison epsilon-delta privacy bound
Baselines: AdaSSP Algorithm 1 of Sheffet (2017) objective perturbation
Builds on: Gaussian mechanism Rényi differential privacy truncated concentrated DP AdaSSP objective perturbation
Closest papers by meaning
- Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising (ICML 2018 · similarity 0.89)
- Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy (ICML 2026 · similarity 0.89)
- Improved Utility Analysis of Private CountSketch (NeurIPS 2022 · similarity 0.89)
- Sketched Gaussian Mechanism for Private Federated Learning (NeurIPS 2025 · similarity 0.89)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.87)
- Differentially Private Model Merging (NeurIPS 2026 · similarity 0.86)
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.