Research map / Federated learning and privacy / Differential privacy
Improved Utility Analysis of Private CountSketch
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Gaussian noise to CountSketch and estimate coordinates with the median | CountSketch · Private CountSketch coordinate estimation | error threshold: α max{Δ,σ} | Helped |
| Use the median instead of the mean to combine repeated estimates | Private CountSketch · Private CountSketch coordinate estimation | robustness to outliers and adversarial data | Helped |
| Increase the number of repetitions k | Private CountSketch · Private CountSketch coordinate estimation | failure probability: 2 exp(-Ω(α² k)) | Helped |
| Use the median instead of the minimum estimator | Private Count-Min Sketch · Private coordinate estimation | variance as repetitions increase: O(k/log k) | Helped |
| Use the mean instead of the median to combine CountSketch estimates | CountSketch · Private coordinate estimation | robustness to outliers | Hurt |
| Use a larger number of repetitions | Private CountSketch on sparse vectors · Sparse vectors | similarity of error distribution to direct Gaussian mechanism: 15 or more | Helped |
| Use a larger number of repetitions | Private CountSketch on world cities · Population data with group privacy | noise-tail concentration | Helped |
| Use Private CountSketch instead of non-private CountSketch | CountSketch · kosarak and retail market basket datasets | error concentration | Hurt |
Closest papers by meaning
- The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches (NeurIPS 2025 · similarity 0.89)
- Sketched Gaussian Mechanism for Private Federated Learning (NeurIPS 2025 · similarity 0.88)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.87)
- Distributed Differentially Private Data Analytics via Secure Sketching (ICML 2025 · similarity 0.86)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.86)
- Privacy amplification by random allocation (NeurIPS 2025 · 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.