Research map / Image generation / Fast diffusion sampling
Dimension-Independent Rates for Structured Neural 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 L2-minimizing ReLU networks over clique-factorized Markov random field densities achieve dimension-independent density estimation rates governed by the largest clique size.
Problem
Nonparametric density estimation suffers the curse of dimensionality (rate n^{-1/(2+d)}); the paper asks why neural density estimators succeed on high-dimensional structured data such as images, audio, video and text.
Approach
Model structured densities as Markov random fields over power graphs so that the density factorizes over maximal cliques; fit each clique factor with a ReLU network via an L2 (squared-error) empirical minimization. The convergence rate then depends on the largest clique size r instead of the ambient dimension d, with an approximately optimal L1 rate n^{-1/(2+r)} from a Scheffé-tournament estimator
Key results
- The L2-minimizing ReLU estimator attains L1 rate n^{-1/(4+r)} (up to log factors) for Lipschitz positive densities Markov to a graph with max clique size r.
- For 2-power grid graphs of images the rate is n^{-1/7} (grid) and n^{-1/9} (grid with diagonals), independent of image dimension.
- A Scheffé-tournament estimator achieves the L1 rate n^{-1/(2+r)}, improving on the nonparametric rate n^{-1/(2+d)}; for tree MRFs (clique size 2) the rate is n^{-1/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an MRF factorization with largest clique size r | L2-minimizing neural density estimation · MRF density estimation | L1 error convergence rate: O(n^{-1/(2+d)}) to \widetilde{O}_p \left(n^{-1/(4+r)}\right) | Helped |
| Use a power-2 grid MRF | L2-minimizing neural density estimation · Grid images | L1 error convergence rate: n^{-1/7} | Helped |
| Use a power-2 grid-with-diagonals MRF | L2-minimizing neural density estimation · Grid images with diagonals | L1 error convergence rate: n^{-1/9} | Helped |
| Use a Scheffé Tournament estimator instead of the tractable neural estimator | MRF density estimation · MRF density estimation | L1 error convergence rate: \widetilde{O}_p \left(n^{-1/(2+r)}\right) versus \widetilde{O}_p \left(n^{-1/(4+r)}\right) | Helped |
Surprising findings
- Pixels in CIFAR-10 appear nearly independent when conditioned on a single adjacent pixel, suggesting the grid MRF assumption may be more conservative than necessary.
Limitations
- The L2 estimator's rate is only proven as an L2 (and hence L1 via Hölder) bound with log factors, and the optimal-rate estimator is computationally intractable.
- Whether the optimal rate n^{-1/(2+r)} is achievable with neural networks and a tractable loss is left open.
- The claim that image, audio, video and text data have small clique sizes is supported by limited empirical evidence (pixel correlation plots) rather than a systematic validation.
Experimental setup
Datasets: CIFAR-10 COCO 2014
Metrics: convergence rate in L1 and L2 norm
Baselines: standard nonparametric (histogram / kernel) density estimation tree density estimation
Builds on: Hammersley-Clifford theorem Schaefer-style ReLU approximation theory (Suzuki-type network approximation) Scheffé tournament estimators
Closest papers by meaning
- Nonparametric Estimation of a Factorizable Density using Diffusion Models (NeurIPS 2026 · similarity 0.85)
- Shallow diffusion networks provably learn hidden low-dimensional structure (ICLR 2025 · similarity 0.83)
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.83)
- Generalization in diffusion models arises from geometry-adaptive harmonic representations (ICLR 2024 · similarity 0.83)
- Dynamic Sparse Training versus Dense Training: The Unexpected Winner in Image Corruption Robustness (ICLR 2025 · similarity 0.83)
- Neural Networks Perform Sufficient Dimension Reduction (AAAI 2025 · similarity 0.83)
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.