Research map / Learning theory and algorithms / Sample complexity
Breaking the curse of dimensionality in structured density estimation
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 that nonparametric density estimation of Lipschitz densities Markov to an arbitrary undirected graph has sample complexity governed by a new graphical quantity, graph resilience, rather than dimension, degree, diameter, or sparsity.
Problem
Estimating a structured multivariate density that satisfies Markov conditions of an undirected graph, where the nonparametric worst-case rate suffers from the curse of dimensionality; the goal is to characterize when this curse can be avoided.
Approach
Introduces graph resilience, the length of the shortest disintegration (repeatedly removing one vertex from each connected component), and shows the TV sample complexity of Lipschitz Markov densities scales as (1/eps)^{r+2} with r the resilience, via a covering-number argument over discretized Markov probability tensors.
Key results
- Sample complexity n ~ r d^{r/2+1} / eps^{r+2} (up to logs) for Lipschitz densities Markov to a graph with resilience r, uniform over the class and matched by a lower bound among graphs of resilience at most r.
- Trees have resilience O(log d) in general and at most depth k for bounded-depth trees; paths have O(log d); 2D grids have O(sqrt(d)); complete graphs have resilience d.
- Resilience is not captured by max degree, diameter, or sparsity: star graphs have resilience at most 2 despite linear degree, and cliques have diameter 1 but resilience d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Markov structure with graph resilience r instead of making no structural assumption | L-Lipschitz density estimation in d dimensions · Total variation density estimation | sample complexity: \frac{d^{d}}{\varepsilon^{d+2}} -> \frac{rd^{r/2+1}L^r}{\varepsilon^{r+2}} | Helped |
| Use a tree with depth k | Graph-resilience estimator · Trees (depth k) | sample complexity: \varepsilon^{-(k+2)} | Helped |
| Use general tree structure | Graph-resilience estimator · Trees (general) | sample complexity: \sim \varepsilon^{-(\log(d)+2)} | Helped |
| Use path structure | Graph-resilience estimator · Paths | sample complexity: \sim \varepsilon^{-(\log(d)+2)} | Helped |
| Use grid structure | Graph-resilience estimator · Grid | sample complexity: \sim \varepsilon^{-(\sqrt{d}+2)} | Helped |
| Use complete-graph structure | Graph-resilience estimator · Complete graph | sample complexity: \varepsilon^{-(d+2)} | No clear effect |
| Estimate without structural assumptions rather than using a graph with resilience r | L-Lipschitz density estimation · Total variation density estimation | sample complexity: \frac{d^{d}}{\varepsilon^{d+2}} -> \frac{rd^{r/2+1}L^r}{\varepsilon^{r+2}} | Hurt |
Surprising findings
- Resilience is not controlled by local graph parameters such as degree, diameter, or sparsity; a star graph with linear degree has resilience at most 2.
- A single missing edge makes the effective dimension strictly smaller than d, since resilience equals d only for complete graphs.
Limitations
- Sample complexity bounds are stated up to log factors and dimension-dependent constants.
- Results are theoretical; no empirical experiments on real data are reported.
Experimental setup
Metrics: total variation distance sample complexity
Baselines: standard nonparametric rate for Lipschitz densities
Builds on: Scheffé-type minimum distance selection (Devroye and Lugosi) RODEO estimator nonparanormal models
Closest papers by meaning
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.87)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.86)
- Sample Complexity Bounds for Estimating Probability Divergences under Invariances (ICML 2024 · similarity 0.85)
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.85)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.85)
- Chain of Log-Concave Markov Chains (ICLR 2024 · 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.