Research map / Learning theory and algorithms / Sample complexity
Data Amplification: A Unified and Competitive Approach to Property Estimation
Yi Hao, Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu
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 f* with 2n samples instead of the empirical estimator with n\log^{1/2-\epsilon}n samples | Property estimators satisfying the paper's smoothness conditions · All underlying distributions | estimation loss: L_{f^*}(p, 2n) \le \left(1+\frac{3}{\log^{\epsilon}n}\right)L_{f^E}(p, n \log^{\frac{1}{2}-\epsilon}n)+C_f\min\left\{ \f | Improved |
| Use f* with n samples rather than f^E with n\sqrt{\log n} samples | Entropy, support size, support coverage, power sums, and distance to uniformity · Six tested distributions per property | mean squared error: n\sqrt{\log n} | Improved |
| Use f* instead of the best previous estimator | Five symmetric properties · Tested distributions, with uniform and near-uniform Dirichlet exceptions for PML | mean squared error | Mixed |
| Use f* rather than estimators optimized for worst-case distributions | Property estimation · More-skewed distributions | relative efficacy | Improved |
| Use f* rather than the empirical estimator | Normalized support size · Tested distributions, except near-uniform cases where PML performs better | mean squared error | Improved |
Closest papers by meaning
- Data Amplification: Instance-Optimal Property Estimation (ICML 2020 · similarity 0.94)
- Unified Sample-Optimal Property Estimation in Near-Linear Time (NeurIPS 2019 · similarity 0.89)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.85)
- One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently (NeurIPS 2024 · similarity 0.84)
- A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation (ICML 2025 · similarity 0.84)
- Active Fourier Auditor for Estimating Distributional Properties of ML Models (AAAI 2025 · similarity 0.83)
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.
