# Memory Efficient And Minimax Distribution Estimation Under Wasserstein Distance Using Bayesian Histograms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 19 Jul 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [Visual Feature Attribution using Wasserstein GANs](https://mlsanity.com/paper/1711.08998/) (2017)
- [Approximate Bayesian computation with the Wasserstein distance](https://mlsanity.com/paper/1905.03747/) (2019)
- [Frequentist coverage and sup-norm convergence rate in Gaussian process regression](https://mlsanity.com/paper/1708.04753/) (2017)
- [On parameter estimation with the Wasserstein distance](https://mlsanity.com/paper/1701.05146/) (2017)
- [Quantile Propagation for Wasserstein-Approximate Gaussian Processes](https://mlsanity.com/paper/1912.10200/) (2019)
- [ERA: Entity Relationship Aware Video Summarization with Wasserstein GAN](https://mlsanity.com/paper/2109.02625/) (2021)
- [Concentration of discrepancy-based approximate Bayesian computation via Rademacher complexity](https://mlsanity.com/paper/2206.06991/) (2022)
- [The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems](https://mlsanity.com/paper/1405.7903/) (2014)

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

- [Stochastic Weight Sharing for Bayesian Neural Networks](https://mlsanity.com/paper/2505.17856/) (2025)

## Abstract (arXiv)

We study Bayesian histograms for distribution estimation on [0,1]d under the Wasserstein Wv, 1 ≤ v < ∞ distance in the i.i.d sampling regime. We newly show that when d < 2v, histograms possess a special textitmemory efficiency property, whereby in reference to the sample size n, order nd/2v bins are needed to obtain minimax rate optimality. This result holds for the posterior mean histogram and with respect to posterior contraction: under the class of Borel probability measures and some classes of smooth densities. The attained memory footprint overcomes existing minimax optimal procedures by a polynomial factor in n; for example an n1 - d/2v factor reduction in the footprint when compared to the empirical measure, a minimax estimator in the Borel probability measure class. Additionally constructing both the posterior mean histogram and the posterior itself can be done super--linearly in n. Due to the popularity of the W1,W2 metrics and the coverage provided by the d < 2v case, our results are of most practical interest in the (d=1,v =1,2), (d=2,v=2), (d=3,v=2) settings and we provide simulations demonstrating the theory in several of these instances.