Dimension-Independent Rates for Structured Neural Density Estimation

“The main result (Theorem 4.2) is quite abstract in the sense, that it only makes a qualitative statement about the existence of neural networks achieving the bound. This in combination without sufficient practical experiments makes it difficult to judge how impactful this result is.”

We appreciate the reviewer’s concern about the limited empirical validation. While we acknowledge this limitation, we note that:

• The paper's primary contribution is theoretical: Proving rigorously that neural networks can achieve dimension-independent rates in density estimation under commonly accepted assumptions. This provides yet another compelling justification for using DNNs in practice.
• The local dependency structure we identify is already implicitly leveraged in successful practical methods, particularly in convolutional architectures and patch-based approaches to anomaly detection such as SoftPatch (NeurIPS 2022). Convolutional structures inherently exploit local dependencies through limited receptive fields, closely aligning with the Hammersley-Clifford theorem, which we use to prove our results.
• Due to strict space constraints (we are already at the page limit), we focused on developing the theoretical and intuitive foundations thoroughly. A comprehensive empirical study would require significant additional space to properly evaluate different architectures, datasets, and parameter settings.

“On thing I am missing a bit motivation wise is what the practical implications would be from this theorem. Too me it seems that the theorem mostly states that local (i.e. simpler) structure leads to better bound, which in itself is not surprising. What takeaway is there beyond that? In particular do you believe that the rate would be reasonable baseline for practical settings?”

The fact that real-world densities can be estimated with (a) dimension-independent rates through (b) neural density estimation is a surprising result, and indeed suggests this presents a reasonable baseline in practical settings. For the reasons outlined above, we leave it to future work to evaluate practical aspects more thoroughly, and indeed, we believe this is an important direction to pursue.

Moreover, the significant attention devoted simply to validating the manifold hypothesis [1,2,3] illustrates the community's interest in identifying structural assumptions that explain learnability in real-world data. From this viewpoint, the MRF framework we propose provides another natural way of suggesting structured function spaces—especially given that the Hammersley-Clifford theorem explicitly characterizes functions reflecting local conditional independence.

"What seems missing to me a bit is how one would go about estimating $r$ for a given dataset. Obviously for any real data there is nonzero but potentially negligible correlation based on distance. However it would be good if there was a rigorous way to determine what negligible means and how it is determined."

“How would one determine $r$ for a real dataset (efficiently)? What if the correlation is not zero far out but rather very small (think of $\epsilon \ll1$)? I am not an expert in that literature but in general most graph problems can be computationally quite expensive.

A significant advantage of the settings we consider is that they naturally suggest reasonable MRF structures (along with their $r$) that can be verified empirically, as we have shown. Indeed, datatypes for which DNNs have historically shown exceptional success—such as images, audio, and text—naturally exhibit conditional dependence structures closely related to the MRF framework we propose. This connection is well-established, as evidenced by comprehensive textbooks dedicated to applying Markov Random Fields to image processing tasks [4,5] .

Outside of these settings, we acknowledge that identifying the graph or $r$ from data can be challenging. With the extra space allotted for the camera ready we will include related work on the estimation of MRF graphs and $r$.

“In the abstract who is $d$, it does not appear in the formulas?”

This was an oversight on our part: $d$ is the ambient dimension of our data, i.e., the dimension of the data whose pdf we are estimating. We will make this clear in the camera ready.

[1] Pope et al. The intrinsic dimension of images and its impact on learning. ICLR, 2021(in paper)

[2] Carlsson et al. On the Local Behavior of Spaces of Natural Images. International Journal of Computer Vision, 76(1):1–12, January 2008.

[3] Brown et al. The Union of Manifolds Hypothesis, NeurIPS, 2022 (in paper)

[4] Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)

[5] Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011

“It would be useful to provide more explanation to the unfamiliar reader for the four examples of section E.”

We will extend this discussion. In our response to Reviewer ZT7H, we included a more technical explanation of how the manifold hypothesis connects to dependence. We can incorporate a similar discussion in the main text or appendix.

“While the theorem claims are applicable to diverse data time (audio, text, image), the illustrations are mostly performed with images. It would strengthen the claims to provide plots similar to Figures 3 and 8 (and possibly, an estimate of $r$) with another data type (e.g., with sequential data such as audio or text).”

We will gladly include a similar plot for a different data type in the next draft. It's worth noting that using Markov random fields to model images is well-established—line 215 cites two textbooks that are entirely on the subject. Our goal was simply to provide images to help the reader grasp the intuition.

"There are no real experiments here."

"No real experiments"

We appreciate the reviewer’s concern about the limited empirical validation. While we acknowledge this limitation, we note that:

• The paper's primary contribution is theoretical: Proving rigorously that neural networks can achieve dimension-independent rates in density estimation under commonly accepted assumptions. This provides yet another compelling justification for using DNNs in practice.
• The local dependency structure we identify is already implicitly leveraged in successful practical methods, particularly in convolutional architectures and patch-based approaches to anomaly detection such as SoftPatch (NeurIPS 2022). Convolutional structures inherently exploit local dependencies through limited receptive fields, closely aligning with the Hammersley-Clifford theorem, which we use to prove our results.
• Due to strict space constraints (we are already at the page limit), we focused on developing the theoretical and intuitive foundations thoroughly. A comprehensive empirical study would require significant additional space to properly evaluate different architectures, datasets, and parameter settings.

“I don't think there's enough evidence here to support the claim that images and audio have the kind of independence structure assumed. The evidence provided seems to just be that conditioning on some particular pixel for CIFAR images seems to give a plot where the pixel correlation is smaller, which is extremely weak.”

“Many of the claims about images having this conditional independence structure are not well-supported.”

"Need much more convincing evidence to support the claim that images have the kind of conditional independence structure assumed."

This model is extensively well-supported: On line 215 (left) we cite two entire textbooks on the application of Markov random fields to image analysis:

• Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)
• Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011

Other textbooks on Markov random fields for machine learning (e.g., A Blake, P Kohli, C Rother, Markov models for pattern recognition: from theory to applications, 2011) contain applications to text and audio data. For example the classic n-gram text model is exactly a Markov random field.

We included the images simply to give the reader an idea of how this model is manifest in real world data.

“I'm extremely surprised that the result presented here was not already known, perhaps as a corollary of some stronger result. No real comparison with any prior work is provided.”

“I'm not familiar enough with the literature here to know for sure, but am skeptical that the results in this paper were not already known.”

“I am generally skeptical that the theoretical results are not already known.”

"Explain relationship to prior work much more thoroughly"

To the best of our knowledge estimators that achieve these rates do not exist, let alone that they can be achieved with a neural network using a reasonably computationally tractable loss function. Our literature review is quite extensive, with over 40 citations, including up to date citations from 2023-24. We even discuss alternative approaches to obtaining faster rates at lines 125-143.

“Half of this paper is spent on just explaining MRFs, which most people in the ML community are probably already at least somewhat familiar with.”

"Most of the paper needs to be spent on explaining your contribution, not on establishing preliminaries, as is currently the case."

To maximize accessibility we tailored our work towards providing intuition to those who may not be so comfortable with these models, which has been appreciated by other reviewers (e.g. Reviewer 2ejB, “The paper is very well written and provides a comprehensive overview of the field and the problem setup.”)

"No supplementary material"

There are 9 pages of supplementary material in the appendix.

"A mild criticism is that while the theoretical results establish improved convergence rates when the probability distribution follows a known clique structure, they do not address how to infer this structure from data."

"The theoretical results assume that the clique structure of the probability distribution is given...?"

A significant advantage of the settings we consider is that they naturally suggest reasonable MRF structures that can be verified empirically, as we have shown. Indeed, datatypes for which DNNs have historically shown exceptional success—such as images, audio, and text—naturally exhibit conditional dependence structures closely related to the MRF framework we propose. This connection is well-established, as evidenced by comprehensive textbooks dedicated to applying Markov Random Fields to image processing tasks [1,2] .

Outside of these settings, we acknowledge that identifying the graph or $r$ from data can be challenging. With the extra space allotted for the camera ready we will include related work on the estimation of MRF graphs.

"The paragraph beginning with 'While the manifold hypothesis...' is quite confusing. The discussion seems to conflate the concept of a data distribution being supported on a manifold with the statistical independence of samples. For instance, two independent samples from a uniform distribution on a manifold are still independent, even though they lie within the manifold. I believe it would be helpful to clarify this distinction and refine the formulation of this idea."

We appreciate the reviewer’s observation and agree that the example is correct. In retrospect, our point was too vague, and we will update the paper to state this more precisely. First, we consider the manifold hypothesis:

Manifold hypothesis: A probability measure $\mu$ on $\mathbb{R}^d$ satisfies the “manifold hypothesis” if $\operatorname{supp}(\mu) \subset M$, where $M$ is a submanifold of $\mathbb{R}^d$ with dimension less than $d$.

Here we have the following lemma makes our point relating the manifold hypothesis and dependence precisely (which is maybe of interest in its own):

Lemma: Let $M \subset \mathbb{R}^d$ be a submanifold of dimension $d' < d$. Let $X = (X_1, \ldots, X_d)$ be a random variable defined by a probability density function $p$ on $M$ (using the standard manifold area/volume measure), and assume that for each $i$, the marginal distribution of $X_i$ is given by a probability density function $p_{X_i}$ (i.e. they are nondegenerate). Then for any subset of $d'+1$ coordinates $I_1, \ldots, I_{d'+1}$, the collection of random variables $\bigl( X_{I_1}, \ldots, X_{I_{d'+1}} \bigr)$ cannot be mutually independent.

So, for any density on a $d'$-dimensional manifold embedded in Euclidean space, where the marginal distribution for each covariate is non-degenerate, any collection of $d'+1$ covariates must exhibit some dependencies. In other words, the lower the intrinsic dimension $d'$, the more dependence must be present among the covariates. The proof this is simple somewhat technical: basically if we assume $d'+1$ covariates are independent then their support $\prod_{i=1}^{d'+1}$ looks like a $d'+1$ dimensional manifold, which contradicts the $d'$ dimensional manifold assumption (we will put this into the appendix).

“Figure 3: The visualization would be more informative if the entire dataset were used instead of just a subset."

The full dataset is 60,000 points, which would be difficult to visualize, so we felt that 100 randomly selected points made this plot easier to understand. We will happily add more points if you like.

"Is it possible to achieve the same rate of convergence with shallow neural networks?"

"“Do you think it is possible to design a kernel specifically adapted to the clique structure of the probability distribution that achieves a similar convergence rate?"

These are interesting questions! While we do not know of a shallow method or an adaptive kernel that achieves this directly, these are fascinating problems for future work. We hope that our results provide a foundation for further investigation into how and why dimension-independent rates are attainable in models for images, audio, and text.

[1] Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)

[2] Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011