Research map / Federated learning and privacy / Differential privacy
Optimal Private Median Estimation under Minimal Distributional Assumptions
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 |
|---|---|---|---|
| Use the proposed PrivateMedian estimator under pure ε-differential privacy | Median estimation · Admissible distributions | sample complexity: O\left( \frac{\log \left( \frac{1}{\beta}\right)}{L^2 \alpha^2}+\frac{ \log \left(\frac{1}{\beta}\right)}{\varepsilon L\ | Helped |
| Set C=C_0 log n instead of a sufficiently large constant (ablation) | PrivateMedian · Admissible distributions | expected runtime: \tilde{O}(n) | Helped |
| Set C=C_0 log n instead of a sufficiently large constant (ablation) | PrivateMedian · Admissible distributions | sample complexity: n=O\left( \frac{\log \left( \frac{1}{\beta}\right)}{L^2 \alpha^2}+C_n\frac{ \log \left(\frac{1}{\beta}\right)}{\varepsil | Hurt |
Closest papers by meaning
- Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (NeurIPS 2019 · similarity 0.90)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.89)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.89)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.89)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.88)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.88)
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.