# Data Amplification: Instance-Optimal Property Estimation

arXiv: https://arxiv.org/abs/1903.01432 · HTML: https://mlsanity.com/paper/1903.01432/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

## Built on by (most cited first, 5 of 5)

- [Sequential Community Mode Estimation](https://mlsanity.com/paper/2111.08535/) (2021)
- [Auditing Fairness under Model Updates: Fundamental Complexity and Property-Preserving Updates](https://mlsanity.com/paper/2601.05909/) (2026)
- [Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics](https://mlsanity.com/paper/2607.00224/) (2026)
- [Synthesis of pulses from particle detectors with a Generative Adversarial Network (GAN)](https://mlsanity.com/paper/2401.05295/) (2024)
- [Instance Dependent Testing of Samplers using Interval Conditioning](https://mlsanity.com/paper/2512.06458/) (2025)

## Abstract (arXiv)

The best-known and most commonly used distribution-property estimation technique uses a plug-in estimator, with empirical frequency replacing the underlying distribution. We present novel linear-time-computable estimators that significantly "amplify" the effective amount of data available. For a large variety of distribution properties including four of the most popular ones and for every underlying distribution, they achieve the accuracy that the empirical-frequency plug-in estimators would attain using a logarithmic-factor more samples. Specifically, for Shannon entropy and a very broad class of properties including ℓ1-distance, the new estimators use n samples to achieve the accuracy attained by the empirical estimators with nlog n samples. For support-size and coverage, the new estimators use n samples to achieve the performance of empirical frequency with sample size n times the logarithm of the property value. Significantly strengthening the traditional min-max formulation, these results hold not only for the worst distributions, but for each and every underlying distribution. Furthermore, the logarithmic amplification factors are optimal. Experiments on a wide variety of distributions show that the new estimators outperform the previous state-of-the-art estimators designed for each specific property.