Research map / Learning theory and algorithms / Sample complexity
Instance-Optimality for Private KL Distribution Estimation
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 minimax-optimal and instance-optimal (up to constants) private and non-private estimators for KL distribution estimation, via a "sampling twice" Good-Turing variant with calibrated private thresholding.
Problem
Estimating a discrete distribution over d symbols in KL divergence under (approximate/pure) differential privacy, where worst-case minimax optimality fails to predict per-instance performance and prior neighborhoods for instance optimality are too large or too small.
Approach
Introduces additive local neighborhoods (perturbations of size t/n, t/(nε), and sqrt(p_i/n)) for instance-optimality in KL, and a "sampling twice" Good-Turing-style estimator with low sensitivity (one-record change affects one count) that can be privatized via Laplace noise and calibrated thresholding for selecting small symbols.
Key results
- The DP instance-optimal sampling-twice estimator consistently outperforms the DP add-constant baseline across power-law and real-token experiments.
- The non-DP sampling-twice estimator is competitive (within constants) with the strongest non-DP Good-Turing baseline.
- The authors prove instance-optimality up to constant factors under additive neighborhoods of size t=24 ln d /(nε) for the DP algorithm, and show no DP estimator can be instance-optimal for neighborhoods with γ = o(1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the DP instance-optimal Sampling Twice estimator instead of Add-constant (DP) | KL distribution estimation · power-law distributions | KL error | Helped |
| use the DP instance-optimal Sampling Twice estimator instead of Add-constant (DP) | KL distribution estimation · Reddit token distribution | negative log likelihood ratio | Helped |
| use the DP instance-optimal Sampling Twice estimator instead of Add-constant (DP) | KL distribution estimation · Enron-email token distribution | negative log likelihood ratio | Helped |
| use the DP instance-optimal Sampling Twice estimator instead of Add-constant (DP) | KL distribution estimation · MMLU token distribution | negative log likelihood ratio | Helped |
| use non-DP Sampling Twice instead of the prior Good-Turing estimator | KL distribution estimation · power-law distributions | KL error | No clear effect |
| use non-DP Sampling Twice instead of the prior Good-Turing estimator | KL distribution estimation · real-world token distributions | negative log likelihood ratio | Mixed |
Surprising findings
- The minimax-optimal DP add-constant estimator performs poorly on realistic power-law and token distributions relative to Good-Turing-style estimators.
Limitations
- Instance-optimality holds only up to constant factors; exact instance-optimality is open.
- Experiments use a grid-searched hyperparameter set and only five random trials on a single MacOS CPU, limiting scale.
- Analysis uses Poisson sampling and central DP with Laplace noise; sensitivity analysis specific to the proposed design.
Experimental setup
Datasets: Reddit token distribution Enron-emails token distribution MMLU token distribution synthetic power-law distributions
Benchmarks: Reddit token distribution Enron-emails token distribution MMLU token distribution power-law distributions
Metrics: KL divergence (negative log likelihood term)
Baselines: Add-constant (DP) Good-Turing (non-DP)
Builds on: Good-Turing estimator Orlitsky and Suresh simplified Good-Turing Assouad's method permutation neighborhood instance optimality
Closest papers by meaning
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.91)
- Subset-Based Instance Optimality in Private Estimation (ICML 2023 · similarity 0.91)
- Instance-Optimal Private Density Estimation in the Wasserstein Distance (NeurIPS 2024 · similarity 0.90)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.89)
- Optimal Private Median Estimation under Minimal Distributional Assumptions (NeurIPS 2020 · similarity 0.89)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · 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.