# Optimal Testing for Properties of Distributions

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2015.

## Built on by (most cited first, 30 of 36)

- [Credal Learning Theory](https://mlsanity.com/paper/2402.00957/) (2024)
- [Conformalized Credal Regions for Classification with Ambiguous Ground Truth](https://mlsanity.com/paper/2411.04852/) (2024)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Conformal Prediction Regions are Imprecise Highest Density Regions](https://mlsanity.com/paper/2502.06331/) (2025)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)
- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Mathematical Framework for Online Social Media Auditing](https://mlsanity.com/paper/2209.05550/) (2022)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [Estimation of discrete distributions with high probability under chi2-divergence](https://mlsanity.com/paper/2510.25400/) (2025)
- [Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions](https://mlsanity.com/paper/2603.04635/) (2026)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [Asymptotic Causal Inference](https://mlsanity.com/paper/2109.09653/) (2021)
- [As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing](https://mlsanity.com/paper/2110.06325/) (2021)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)
- [New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions](https://mlsanity.com/paper/2308.00089/) (2023)
- [Reframing Data Value for Large Language Models Through the Lens of Plausibility](https://mlsanity.com/paper/2409.00284/) (2024)
- [Optimal Transport for ε-Contaminated Credal Sets: To the Memory of Sayan Mukherjee](https://mlsanity.com/paper/2410.03267/) (2024)

## Abstract (arXiv)

Given samples from an unknown distribution p, is it possible to distinguish whether p belongs to some class of distributions C versus p being far from every distribution in C? This fundamental question has received tremendous attention in statistics, focusing primarily on asymptotic analysis, and more recently in information theory and theoretical computer science, where the emphasis has been on small sample size and computational complexity. Nevertheless, even for basic properties of distributions such as monotonicity, log-concavity, unimodality, independence, and monotone-hazard rate, the optimal sample complexity is unknown. We provide a general approach via which we obtain sample-optimal and computationally efficient testers for all these distribution families. At the core of our approach is an algorithm which solves the following problem: Given samples from an unknown distribution p, and a known distribution q, are p and q close in chi2-distance, or far in total variation distance? The optimality of our testers is established by providing matching lower bounds with respect to both n and varepsilon. Finally, a necessary building block for our testers and an important byproduct of our work are the first known computationally efficient proper learners for discrete log-concave and monotone hazard rate distributions.