Research map / Learning theory and algorithms / Sample complexity
Hierarchical Integral Probability Metrics: A distance on random probability measures with low sample complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows the Wasserstein-over-Wasserstein distance between laws of random probabilities has sample complexity slower than any polynomial, and proposes the hierarchical IPM (HIPM) that achieves parametric rates, with a gradient-ascent numerical method in 1D.
Problem
Distances between laws of random probabilities (probability measures on spaces of probability measures) are needed for nonparametric Bayesian and ML comparisons, but the Wasserstein-over-Wasserstein distance has very slow sample complexity due to the infinite dimensionality of P(X).
Approach
Replace the inner Wasserstein-over-IPM construction with a distance that takes the sup over Lipschitz test functions f of the 1D Wasserstein distance between the laws of the random integrals P(f); this yields a smaller function class (functions of P(f) only), giving parametric convergence while remaining a lower bound on W_W.
Key results
- Wasserstein-over-Wasserstein sample complexity is lower bounded by c_gamma n^{-gamma} for any gamma>0 for Dirichlet processes, while the Lipschitz HIPM achieves E[d_Lip] <= C n^{-1/2} in dimension 1 (n^{-1/2} log n in d=2, n^{-1/d} for d>2).
- For Dirichlet processes and empirical measures, W_W(DP(alpha,P1),DP(alpha,P2)) = W(P1,P2) for any alpha, extending to species sampling processes via a coupling argument.
- Numerical experiments in 1D with gradient ascent show the HIPM converges faster than W_W when comparing independent realizations of the same hierarchical empirical measure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Wasserstein over Wasserstein with Lipschitz HIPM for empirical estimation | Laws of random probabilities · Bounded subsets of R^d | expected estimation error rate: Wasserstein over Wasserstein: C \frac{ \log(\log(n))}{\log(n)}; Lipschitz HIPM: C_1 n^{-1/2} (d = 1), C_2 n^{-1/2} \log( | Helped |
| Use the hierarchical empirical measure instead of the Dirichlet multinomial approximation | Dirichlet process approximation · P_0 in R | Wasserstein over Wasserstein error upper bound: \frac{1}{\sqrt{N}} \int_{-\infty}^{+\infty} \sqrt{F_0(x)(1- F_0(x))} \mathrm{d} x; \sqrt{\frac{\alpha}{N(\alpha+1)}} \in | No clear effect |
| Use truncated stick-breaking rather than the Dirichlet multinomial or hierarchical empirical approximation | Dirichlet process approximation · Large concentration parameter | approximation error: 2 \bigg( \frac{\alpha}{\alpha+1} \bigg)^N \int_{-\infty}^{+\infty} F_0(x)(1- F_0(x)) \mathrm{d} x | Hurt |
| Use truncated stick-breaking when the space is high-dimensional or N is consistently larger than the concentration parameter | Dirichlet process approximation · High-dimensional space or N larger than α | approximation error | Helped |
Surprising findings
- The Wasserstein over Wasserstein distance between independent realizations of the same Dirichlet process has sample complexity slower than any polynomial rate.
Limitations
- Numerical method restricted to one-dimensional spaces and relies on non-concave gradient ascent without convergence guarantees.
- Sample complexity theory derived only for probabilities on bounded metric spaces.
- Qualitative difference between W_W and HIPM is not fully understood.
Experimental setup
Metrics: Wasserstein over Wasserstein distance HIPM distance convergence rate in sample size n upper and lower bounds
Baselines: Wasserstein over Wasserstein distance Dirichlet multinomial process truncated stick-breaking
Builds on: Wasserstein distance integral probability metrics max-sliced Wasserstein distance species sampling processes Dirichlet process
Closest papers by meaning
- Scalable Sobolev IPM for Probability Measures on a Graph (ICML 2025 · similarity 0.86)
- A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.86)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.86)
- Sample Complexity Bounds for Estimating Probability Divergences under Invariances (ICML 2024 · similarity 0.86)
- Integral Imprecise Probability Metrics (NeurIPS 2025 · similarity 0.85)
- Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.