Research map / Federated learning and privacy / Differential privacy
Perturb-and-Project: Differentially Private Similarities and Marginals
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.
Revisits input perturbation for DP: add Gaussian noise to the input then project onto a convex admissible set, with projections computed via alternating projections and sum-of-squares relaxations, yielding improved private cosine-similarity release and k-way marginal algorithms (including odd k and sparse datasets).
Problem
Differentially private release of pairwise cosine similarities and k-way marginal queries over binary datasets, where existing polynomial-time methods are weak for odd k and efficient projections are hard.
Approach
Perturb-and-project: add Gaussian noise to the input matrix/tensor, then project onto a convex admissible set; error is governed by the Gaussian complexity of the set, so structured sets give better bounds. Sum-of-squares relaxations supply tight convex supersets that can be projected onto efficiently, and alternating projections make projection practical.
Key results
- Private cosine similarity release achieves expected squared Frobenius error O(Δ√log(2/δ)/ε)·n^{3/2} in polynomial time, versus a √n factor worse for the naive Gaussian mechanism.
- k-way marginal algorithm achieves error O(m·n^{k/4}·√log(2/δ)/ε) for even k and O(m·(n^k·k·log n)^{1/4}·√log(2/δ)/ε) for odd k in time m·n^{O(k)}.
- For t-sparse datasets, error improves over the dense bound when t ≤ n^{5/6}/log n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use perturb-and-project to privately release pair-wise cosine similarities | Unit-vector datasets · Pair-wise cosine similarities | expected squared Frobenius error: O\Paren{\frac{\Delta\cdot \sqrt{\log (2/\delta)}}{\epsilon}}\cdot n^{3/2} | Helped |
| Use perturb-and-project for odd-k marginals instead of existing polynomial-time algorithms | k-way marginal algorithms · k-way marginals, odd k | expected average query-wise squared error: n^{1/2}/(k\log n) | Helped |
| Use the sparse-dataset algorithm when each vector has at most t non-zero entries | Perturb-and-project · k-way marginals, t-sparse datasets | expected average query-wise squared error | Helped |
| Use the Gaussian mechanism on the input instead of perturb-and-project | k-way marginal algorithms · k-way marginals | error: O\Paren{\frac{\log (2,\delta)}{\epsilon^2}}\cdot n^{k} | Hurt |
Surprising findings
- Input perturbation with projection matches the best known (conjecturally optimal) guarantees for a large class of projection functions.
- The Gaussian mechanism with projection can be made practical by alternating projections needing only logarithmically many steps, recovering clipping and PSD eigenvalue truncation as subroutines.
Limitations
- Projections onto the exact admissible sets are conjecturally hard, so polynomial-time algorithms use SoS relaxations with weaker guarantees for odd k.
- Sparse-dataset guarantees only improve over dense ones when t ≤ n^{5/6}/log n.
- Gaussian complexity bounds for SoS sets rely on conjectured computational hardness, so optimality is not proven unconditionally.
Experimental setup
Metrics: expected squared Frobenius error expected average query-wise squared error
Baselines: Gaussian mechanism exponential-time marginal algorithms prior flattening-based k-way marginal algorithms
Builds on: Gaussian mechanism objective perturbation sum-of-squares relaxations for injective tensor norms
Closest papers by meaning
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.89)
- Efficient and Private Marginal Reconstruction with Local Non-Negativity (NeurIPS 2024 · similarity 0.88)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.87)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.87)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.87)
- Certification for Differentially Private Prediction in Gradient-Based Training (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.