# Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 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)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)

## Abstract (arXiv)

We study the problem of robustly learning multi-dimensional histograms. A d-dimensional function h: D rightarrow ℝ is called a k-histogram if there exists a partition of the domain D subseteq ℝd into k axis-aligned rectangles such that h is constant within each such rectangle. Let f: D rightarrow ℝ be a d-dimensional probability density function and suppose that f is OPT-close, in L1-distance, to an unknown k-histogram (with unknown partition). Our goal is to output a hypothesis that is O(OPT) + ε close to f, in L1-distance. We give an algorithm for this learning problem that uses n = tildeOd(k/ε2) samples and runs in time tildeOd(n). For any fixed dimension, our algorithm has optimal sample complexity, up to logarithmic factors, and runs in near-linear time. Prior to our work, the time complexity of the d=1 case was well-understood, but significant gaps in our understanding remained even for d=2.