# Unified Sample-Optimal Property Estimation in Near-Linear Time

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

## Key facts

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

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

- [Sequential Community Mode Estimation](https://mlsanity.com/paper/2111.08535/) (2021)
- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)
- [Testing Support Size More Efficiently Than Learning Histograms](https://mlsanity.com/paper/2410.18915/) (2024)
- [PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models](https://mlsanity.com/paper/2504.00608/) (2025)

## Abstract (arXiv)

We consider the fundamental learning problem of estimating properties of distributions over large domains. Using a novel piecewise-polynomial approximation technique, we derive the first unified methodology for constructing sample- and time-efficient estimators for all sufficiently smooth, symmetric and non-symmetric, additive properties. This technique yields near-linear-time computable estimators whose approximation values are asymptotically optimal and highly-concentrated, resulting in the first: 1) estimators achieving the O(k/(varepsilon2log k)) min-max varepsilon-error sample complexity for all k-symbol Lipschitz properties; 2) unified near-optimal differentially private estimators for a variety of properties; 3) unified estimator achieving optimal bias and near-optimal variance for five important properties; 4) near-optimal sample-complexity estimators for several important symmetric properties over both domain sizes and confidence levels. In addition, we establish a McDiarmid's inequality under Poisson sampling, which is of independent interest.