Research map / Learning theory and algorithms / Sample complexity
Sample Complexity Bounds for Estimating Probability Divergences under Invariances
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.
Derives sample complexity bounds for estimating 1-Wasserstein, Sobolev IPMs, MMD, and density (L2, L∞) under Lie group invariances on compact manifolds, via a Laplace-Beltrami Fourier estimator and a local Weyl's law for invariant functions.
Problem
Estimating probability divergences (1-Wasserstein, Sobolev IPMs, MMD) and densities from samples when the underlying distribution is invariant under a smooth Lie group action on a compact manifold; the goal is to quantify how invariances reduce sample complexity.
Approach
Replace the empirical measure with a Laplace-Beltrami Fourier estimator restricted to G-invariant eigenfunctions, with heat-kernel smoothing (1-Wasserstein) or spectral truncation (Sobolev/density). Invariances reduce the effective sample size by a factor given by the quotient volume and improve the exponent via the quotient dimension, using a new local Weyl's law for invariant functions.
Key results
- 1-Wasserstein estimation rate improves from (vol(M)/n)^(1/dim M) to (vol(M/G)/n)^(1/d) with d = dim(M/G); for finite groups this amounts to replacing n by n|G|.
- For MMD-regime Sobolev IPMs (alpha > d/2), the bound sqrt(Z(alpha;G)/n) gives a gain factor Z(alpha)/Z(alpha;G) that can scale as |G|^(2alpha) on the circle.
- On a 6-dimensional torus experiment, the invariant estimator outperforms the non-invariant empirical estimator and full data augmentation for Sobolev IPM with alpha=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use G-invariance when estimating the 1-Wasserstein distance instead of treating the distribution as unrestricted | 1-Wasserstein estimation · Compact manifold with G-invariant distributions | expected 1-Wasserstein error: \Big ( \frac{\vol(\calM/G)}{n} \Big)^{\frac{1}{d}} | Helped |
| Use G-invariance when estimating smooth distributions | Smooth 1-Wasserstein estimation · Compact manifold with G-invariant smooth distributions | expected 1-Wasserstein error: \Big ( \frac{\vol(\calM/G)}{n} \Big)^{\frac{s+1}{2s+d}} | Helped |
| Use G-invariance when estimating Sobolev IPMs for α<d/2 | Sobolev IPM estimation · Compact manifold with G-invariant smooth distributions | expected Sobolev IPM error: \Big ( \frac{\vol(\calM/G)}{n} \Big)^{\frac{s+\alpha}{2s+d}} | Helped |
| Use G-invariance when estimating Sobolev IPMs at α=d/2 | Sobolev IPM estimation · Compact manifold with G-invariant distributions | expected Sobolev IPM error: \sqrt{ \frac{ \vol(\calM/G)\log(n)}{n} } | Helped |
| Use G-invariance when estimating MMDs | MMD estimation · Compact manifold with G-invariant distributions | expected MMD error: \sqrt{ \frac{ \mathcal{Z}(\alpha;G)}{n} } | Helped |
| Use G-invariance when estimating densities in L² | L² density estimation · Compact manifold with G-invariant smooth distributions | expected L² density estimation error: \Big ( \frac{\vol(\calM/G)}{n} \Big)^{\frac{s}{2s+d}} | Helped |
| Use G-invariance when estimating densities in L∞ | L∞ density estimation · Compact manifold with G-invariant smooth distributions, s>d/2 | expected L∞ density estimation error: \Big ( \frac{(\vol(\calM/G))^{\frac{2s}{s-d/2}}} {n} \Big)^{\frac{s-d/2}{2s+d}} | Helped |
| Use the invariant estimator with regularization rather than full data augmentation | Sobolev IPM estimation with α=1 · Synthetic six-dimensional flat torus | Sobolev IPM convergence | Helped |
Surprising findings
- Full data augmentation performs worse than the invariant estimator, showing the importance of bias-variance regularization.
- For L-infinity density estimation, the effective sample gain can exceed the group size linearly (e.g., n|G|^3 for d=4, s=6).
Limitations
- Density estimation in L-infinity uses a simple algorithm and may be improvable without invariances; tighter invariant bounds left open.
- Assumes a known connected compact boundaryless smooth manifold with isometric group action.
- Experiments are small, synthetic, and parameter T was not optimized.
Experimental setup
Datasets: synthetic distributions on 6-dimensional flat torus
Benchmarks: synthetic 6-dimensional flat torus experiment (Sobolev IPM with alpha=1)
Metrics: convergence rate of estimated Sobolev IPM
Baselines: empirical measure full data augmentation
Builds on: Weyl's law Kantorovich duality Sobolev IPMs maximum mean discrepancy
Closest papers by meaning
- Sample Complexity of Probability Divergences under Group Symmetry (ICML 2023 · similarity 0.94)
- Hierarchical Integral Probability Metrics: A distance on random probability measures with low sample complexity (ICML 2024 · similarity 0.86)
- Breaking the curse of dimensionality in structured density estimation (NeurIPS 2024 · similarity 0.85)
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity (ICML 2025 · similarity 0.85)
- Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.84)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.84)
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.