Research map / Learning theory and algorithms / Sample complexity
Data Amplification: Instance-Optimal Property Estimation
Yi Hao, Alon Orlitsky
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 competitive estimator instead of the empirical plug-in estimator | Shannon entropy · Every underlying distribution | mean absolute error: n -> n log n | Improved |
| Use the proposed competitive estimator instead of the empirical plug-in estimator | ℓ1-distance · Every pair of distributions p and q | mean absolute error: n -> n log n | Improved |
| Use the proposed estimator instead of the empirical plug-in estimator | Lipschitz additive properties · Every underlying distribution | mean absolute error: n -> n log n | Improved |
| Use the proposed estimator instead of the empirical plug-in estimator | Support size · Every underlying distribution | normalized mean absolute error: n -> n log S_{p} | Improved |
| Use the proposed estimator instead of the empirical plug-in estimator | Support coverage · Every underlying distribution | normalized mean absolute error: n -> n log C_{p} | Improved |
| Use the proposed estimator instead of the empirical estimator | Shannon entropy · Nine synthetic distributions | estimation accuracy | Improved |
| Use the proposed estimator instead of prior state-of-the-art estimators | Shannon entropy and support size · Nine synthetic distributions | accuracy and stability | Improved |
| Increase the amplification factor from sqrt(log n) to log n | Competitive property estimators · Sufficiently smooth additive properties | effective sample size: sqrt(log n) -> log n | Improved |
Closest papers by meaning
- Data Amplification: A Unified and Competitive Approach to Property Estimation (NeurIPS 2018 · similarity 0.94)
- Unified Sample-Optimal Property Estimation in Near-Linear Time (NeurIPS 2019 · similarity 0.89)
- On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood (NeurIPS 2022 · similarity 0.87)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.86)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.85)
- One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently (NeurIPS 2024 · similarity 0.84)
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.
