# Breaking the curse of dimensionality in structured density estimation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 70 references that are in the map.
- First posted on arXiv 10 Oct 2024.

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

- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [Composing graphical models with neural networks for structured representations and fast inference](https://mlsanity.com/paper/1603.06277/) (2016)
- [Causal Autoregressive Flows](https://mlsanity.com/paper/2011.02268/) (2020)
- [Deep ReLU network approximation of functions on a manifold](https://mlsanity.com/paper/1908.00695/) (2019)
- [Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions](https://mlsanity.com/paper/2402.15602/) (2024)
- [Graphical Normalizing Flows](https://mlsanity.com/paper/2006.02548/) (2020)
- [Nonparametric Density Estimation under Adversarial Losses](https://mlsanity.com/paper/1805.08836/) (2018)
- [Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses](https://mlsanity.com/paper/1902.03511/) (2019)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [Low-rank Characteristic Tensor Density Estimation Part I: Foundations](https://mlsanity.com/paper/2008.12315/) (2020)
- [How Well Can Generative Adversarial Networks Learn Densities: A Nonparametric View](https://mlsanity.com/paper/1712.08244/) (2017)
- [Structured Neural Networks for Density Estimation and Causal Inference](https://mlsanity.com/paper/2311.02221/) (2023)
- [Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian probability distributions](https://mlsanity.com/paper/2402.08082/) (2024)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [Optimal Rates for Nonparametric Density Estimation under Communication Constraints](https://mlsanity.com/paper/2107.10078/) (2021)
- [Low-rank Characteristic Tensor Density Estimation Part II: Compression and Latent Density Estimation](https://mlsanity.com/paper/2106.10591/) (2021)
- [Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation](https://mlsanity.com/paper/2204.00930/) (2022)
- [Sample Complexity Using Infinite Multiview Models](https://mlsanity.com/paper/2302.04292/) (2023)

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

- [PMODE: Theoretically Grounded and Modular Mixture Modeling](https://mlsanity.com/paper/2508.21396/) (2025)
- [Breaking the Curse with BAND: Nonparametric Distribution Estimation in High Dimensions](https://mlsanity.com/paper/2607.26955/) (2026)
- [XMatch: Enhancing Covariate-Aware Time Series Forecasting through Tree-Structured Exogenous Matching](https://mlsanity.com/paper/2609.34939/) (2026)

## Abstract (arXiv)

We consider the problem of estimating a structured multivariate density, subject to Markov conditions implied by an undirected graph. In the worst case, without Markovian assumptions, this problem suffers from the curse of dimensionality. Our main result shows how the curse of dimensionality can be avoided or greatly alleviated under the Markov property, and applies to arbitrary graphs. While existing results along these lines focus on sparsity or manifold assumptions, we introduce a new graphical quantity called "graph resilience" and show how it controls the sample complexity. Surprisingly, although one might expect the sample complexity of this problem to scale with local graph parameters such as the degree, this turns out not to be the case. Through explicit examples, we compute uniform deviation bounds and illustrate how the curse of dimensionality in density estimation can thus be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data.