# Near-Optimal Bounds for Testing Histogram Distributions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 63 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 12 of 12)

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions](https://mlsanity.com/paper/1508.05538/) (2015)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)
- [Near-Optimal Closeness Testing of Discrete Histogram Distributions](https://mlsanity.com/paper/1703.01913/) (2017)
- [Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms](https://mlsanity.com/paper/1802.08513/) (2018)

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

- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)

## Abstract (arXiv)

We investigate the problem of testing whether a discrete probability distribution over an ordered domain is a histogram on a specified number of bins. One of the most common tools for the succinct approximation of data, k-histograms over [n], are probability distributions that are piecewise constant over a set of k intervals. The histogram testing problem is the following: Given samples from an unknown distribution p on [n], we want to distinguish between the cases that p is a k-histogram versus varepsilon-far from any k-histogram, in total variation distance. Our main result is a sample near-optimal and computationally efficient algorithm for this testing problem, and a nearly-matching (within logarithmic factors) sample complexity lower bound. Specifically, we show that the histogram testing problem has sample complexity widetilde Theta (√nk / varepsilon + k / varepsilon2 + √n / varepsilon2).