Dimension-Independent Rates for Structured Neural Density Estimation
Authors: Robert A. Vandermeulen
Wai Ming Tai
Bryon Aragam
Venue: ICML 2025 poster (2025)
Keywords: density estimation
image processing
Markov random field
graphical model
nonparametric statistics
high-dimensional statistics
sample complexity
Primary area: theory->learning_theory
TL;DR: We show how deep neural networks achieve dimension-independent rates for learning structured densities typical of image, audio, video, and text data.

Abstract: We show that deep neural networks can achieve dimension-independent rates of convergence for learning structured densities typical of image, audio, video, and text data. For example, in images, where each pixel becomes independent of the rest of the image when conditioned on pixels at most $t$ steps away, a simple $L^2$-minimizing neural network can attain a rate of $n^{-1/((t+1)^2+4)}$, where $t$ is independent of the ambient dimension $d$, i.e. the total number of pixels. We further provide empirical evidence that, in real-world applications, $t$ is often a small constant, thus effectively circumventing the curse of dimensionality. Moreover, for sequential data (e.g., audio or text) exhibiting a similar local dependence structure, our analysis shows a rate of $n^{-1/(t+5)}$, offering further evidence of dimension independence in practical scenarios.

Dimension-Independent Rates for Structured Neural Density Estimation
Robert A. Vandermeulen
Wai Ming Tai Bryon Aragam
Abstract
the mass of the density is heavily concentrated around a lower-dimensional subset of that space, such as an embed- ded manifold. As we will show later, for complex data types of significant interest-images, video, sound, and text-this assumption is intimately linked spatio-temporal locality, For instance, in data such images, video, sound, and text, spatio-tempone locality implies that nearby covariates e.g. pixel intensities at adjacent positions in an image-tend to be strongly dependent, suggesting that the data is effectively constrained to lower-dimensional subspace.
We show that deep neural networks can achieve inneensionnidependeen rates of convergence for learning structured densities typical of image, au- dio, video, and text data. For example, in images, where each pixel becomes independent of the rest of the image when conditioned on pixels at most steps away, a simple T.2 -minimiziin neural net- work can attain a rate of n 11((((++))+++ +4), where is independent of the ambient dimension d, i.e. the total number of pixels. We further provide em- pirical evidence that, real-world applications, t is often a small constant, thus effectively circum- venting the curse of dimensionality. Moreover, for sequential data (e.g., audio or text) exhibiting similar local dependence structure, our anal- ysis shows a rate of n 11(++))) offering further evidence of dimension independence practical scenarios.
This paper investigates the benefits of leveraging the con- verse structure: The independence of spatio-temporally dis- tant covariates. Covariates that are spatio-lemporally distant often exhibit near- sear-independence, particularly after condi- tioning on nearby covariates. Consider a sound recording: two one-second segments separated by a minute might share common elements, such as the same speaker. However, given the intervening minute of audio, these segments be- come effectively independent. The minute-long interval contains sufficient information to render the separated seg- ments mutually uninformative. This principle of conditional independence extends to various data types, including im- ages, where pixels far apart tend to be independent when conditioned on the surrounding region.
1. Introduction
Deep learning has emerged as remarkably effective ap- proach to numerous statistical problems that were histori- cally extremely challenging, especially in high-dimensional settings. Deep generative models, for example, can approx- imate densities with thousands millions of dimensions using merely few million data points (Oussidi & Elhas- souny, 2018 8; Ho et al., 2020; Cao et al., 2024). This stands in stark contrast to standard density estimation theory, which would demand astronomical sample sizes due to the curse of dimensionality. At the same time, it is known that if a density satisfies certain assumptions such as monotonicity, convexity, sparsity, mixtures, or additivity, the curse of di- mensionality can be mitigated. Perhaps the most widely accepted explanation for deep learning's ability to circum- vent this curse is the manifold hypothesis (Bengio et al., 2013; Brahma et al., 2016). This hypothesis posits that, de- spitc a distribution's 's ambient space being high-dimon high-dimensional,
For spatial Mata-focusing on images for concreteness-il it is well known that a pixel becomes independent of the rest of the image when conditioned on all pixels within certain distance f, following an argument similar to the one made for sound segments above. We show that, under this as- sumption, density estimation using a neural network with a simple 7.2-minimzzing loss achieves a rate of approximately n -1((0+))))+4) In contrast the standard rate in nonpara- metric density estimation for the same class of densities is n 11((2++)) where d represents the total number of covari- ates. This implies that the effective dimension is of order t² instead of d. For comparison, in images, is typically on the order of 3-8 (see Section 3), whereas d is the full image dimensionality given by width times height, which would be substantially larger than in practice. For ex- ample, consider simple benchmark datasets like MNIST (28 x 28, 784) or CelebA (256 x 256, d = 65 536). Similarly, for sequential data, diimension-nndepennn rate of 111((+55) is achieved.
Correspondence to: Robert Vandermeulen <robert.anton. wawnoowwwaaeemeeueeenmaaaae gom.....mmmm....................
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Giinension-Indeeendee Rates for Structured Neural Density Estimation
A key aspect of the results presented here is that remains largely independent of the overall size of the image or the total duration of the temporal data. Returning to the sound recording example, a one-second segment may become in- dependent of the rest of the recording when conditioned on the minute of audio preceding and following it, Crucially, this conditional independence holds regardless of whether the full recording spans three minutes or an hour.
Kuzborskij & Szepesvári, 2022: Oko al., 2023; Zhang et al., 2024; Kwon & Chae, 2024). This rate implies that the sample complexity grows exponentially in the dimension d, making the success of deep neural networks for esti- mating densities with millions of dimensions all the more remarkable. Various types of structure have been studied to improve the rate of convergence. For example, Hall & Zhou (2003); Hall et al. (2005); Vandermeulen & Ledent (2021), Vandermeulen (2023); Chhor et al. (2024) show that one can achieve dimension-indeeeeden rates of convergence for nonparametric density estimation by assuming a mul- tiview model-a type of low-rank structure. However, in the context of deep learning, this phenomenon is most often explained via the manifold hypothesis.
2. Background and Related Work
In this section, we lay the foundation for our main results by introducing key concepts and related work. We begin by discussing traditional approaches to nonparametric density estimation and their limitations, particularly the curse of dimensionality. We then explore the manifold hypothesis, widely accepted explanation for the success of deep learn- ing in high-dimensional settings, along with other structural hypotheses used in nonparametric density estimation. Fol- lowing this, we review the basics of Markov random fields (MRFs) and their applications in modeling various types of data, including images and sequential information. This background will provide the necessary context for under- standing the novelty of our approach, which leverages MRFs to achieve dimensioo-inneeendenn convergence rates in den- sity estimation. While our framework offers an alternative perspective to the manifold hypothesis, it neither precludes nor implies it; rather, the two assumptions address different structural properties of high-dimensional data.
2.2. Manifold Hypothesis
The manifold hypothesis posits that many high-dimensional real-world distributions concentrate around lower- dimensional spaces, such as submanifolds of the ambient space. The success of deep learning methods in handling digh-dimensional data, such as images, videos, and audio, is frequently attributed to the manifold hypothesis.
For example, Pope et al. (2021) determined that the in- trinsic dimension of the ImageNet dataset lies between 25 and 40 dimensions, significantly lower than its ambient dimension. Further supporting this hypothesis, Carlsson et al. (2008) discovered that the set of 3 x 3 pixel patches from natural images concentrates around a 2-dimensional manifold. Theoretically, distributions concentrating around lower-dimensional subsets of the ambient space have been shown to yield improved estimation properties. For instance, Weed & Bach (2019) demonstrated that while the empirical distribution typically converges at rate -1/dd to the true distribution in Wasserstein distance, when the data has a lower d' o'ddiennsional structure, it converges at the faster rate of n 111/"". Similar results illustrating the manifold hy- pothesis and its benefits abound in the literature (Pelletier, 2005; Ozakin & Gray, 2009; Jiang, 2017; Schmidt- 2019; Nakada & Imaizumi, 2020; Berenfeld et al., 2022: Chae et al., 2023; Jiao al., 2023; Tang & Yang. 2024). An- other line of related work uses Barron functions, which are class of functions inspired by neural networks, to achieve dimension- ffree rates (Barron, 1993; Klusowski & Barron, 2018; 8; Ma et al., 2022; Cole & Lu, 2024). in contrast to our use of Lipschitz-type assumptions.
2.1. Nonparametric Density Estimation
Density estimation is the task of estimating a d- dimensional target probability density p from observed data, üid p. Of course, this is classical problem for which we do not intend to provide comprehensive overview, and instead refer readers to books such as (De- vroye& & Gyorfi, 1985; Devroye & Lugosi, 2001; Tsybakov, 2009) for additional background. For general densities p. nonparametric density estimators like kernel density esti- mators or histograms (Devroye & Gyorfi, 1985; Devroye & Lugosi, 2001) converge p for any density given sufficient data, but notably suffer from the curse of dimensionality. For instance, when is Lipschitz continuous', the I,- er- ror [p(x) pm(()) dæ= = |lp p. converges at the rate Ol--1/(2+-)) This nonparametric rate is known to be optimal for Lipschitz continuous densities, and numerous studies over the past decade have established that neural networks and generative models can achieve this optimal rate (Liang, 2017: Singh al., 2018: Uppal et al., 2019;
X1,...,Xx, Xx,
While the manifold hypothesis explains local dependen- cies, it's worth considering scenarios that deviate from this model. For example, the manifold hypothesis cannot be sat- isfied when covariates are independent. This is easily seen between two independent covariates x ~ Px and y Py, whose joint density Px, y) = px (x)py(v) fills a rectan- gle in their product space. More generally, if a probability
A function/ f: R2d + R is Lipschitz continuous if there exists L 2 0 such that [x) - f(y)] < L L|x - Vll, for all x, y. Our results extend to more general families (c.g. Hölder), however, we present our main results in the Lipschitz setting for simplicity.
2

---

Dimension-Indeen Fanneeneon-Iddeeendennt Rates for Structured Neural Density Estimation
measure is supported on a manifold, there is limit on how many covariates can be mutually independent. We formalize this with the following proposition.
of {x1y..., xa), the graph indicates that the random vec- tors X and x3 are conditionally independent given x if there is no path from A to B that doesn't I pass through C.
Proposition 2.1. Let M TRe be regular submanifold of dimension d' < d. Let X = (X1....,XA,, Xa) be a ran- dom vector distributed according to probubility measure supported on M, such that each marginal X₃ has a non- degenerate probability density function pt. Then, for any the random vari-
Consider a simple example with random variables x, y. and 2, where x = y + 6x and z = + <2. with 6x. <2 and y being jointly independent. In this scenario, the distribu- tions of x and z are conditionally independent given y. The corresponding MRF for this example is given by:
subset of d' + coordinates ables XI,....;XI cannot be mutually independent.
Z
The proof of this proposition can be found in the appendices. This result formalizes the intuition that in higher dimensions, the manifold hypothesis limits the amount of independence that is allowed. In this sense, the manifold hypothesis is complementary to our MRF approach.
While an MRF conveys information about conditional in- dependence, the absence of such information in the MRF does not necessarily imply dependence in the actual data. In other words, covariates can be conditionally independent in reality even if this independence is not explicitly represented in the MRF. Thus, the MRF provides a conservative model of independence re relationships, capturing known or assumed conditional independencies without ruling out additional in- dependencies that may exist in the data. Consequently, any random vector associated with a complete graph-where all vertices are adjacent to one another is a valid MRF, since it provides no information about the independence of the co- variates. This is because every vertex is connected to every other vertex, so removing any number of vertices will never separate the graph into multiple components. Because it conveys no information about the conditional independence of the covariates, it even applies to a random vector where all entries are independent.
Finally, while the manifold hypothesis is arguably the most widely accepted explanation for the learnability of high- dimensional models, particularly within the deep learning community, is far from the only structural assumption con- sidered in the broader nonparametric estimation literature. Various alternative approaches have been explored such as monotonicity (Groeneboom, 1984), convexity (Groeneboom et al., 2001), log-concave (Samworth, 2018), sparsity (Liu et al., 2007), mixtures (Genovese & Wasserman, 2000), and additive models (Stone, 1985). Crucially, with the exception of additivity and sparsity, these assumptions do not address the curse of dimensionality. While sparsity is special case of the manifold hypothesis (e.g. the manifold is a lincar subspace or union of linear subspaces), realistic models of image, audio, video, and text data do not satisfy additivity assumptions. From this perspective, we propose a novel approach to mitigating the curse of dimensionality that is on the one hand much more general than additivity while at the same complementing the manifold hypothesis.
Remark 2.2. After the initial posting of our paper, were made aware of the related work by Bos & Schmidt-Hieber (2023) which proposes supervised approach to density estimation that also leverages the Markov assumption to break the curse of dimensionality in density estimation.
2.4. MRFs in Applications
2.3. Markov Random Fields
MRFs are widely used in applications; Figure 1 illustrates three of the most common families of MRFs.
Our intuition about natural images suggests that pixels that distant from one another tend to become more inde- pendent. This observation naturally leads to modeling the space of images ab MRF, where local dependencies are captured while allowing for independence between distant pixels (Li, 1994; 2009; Blake et al., 201 1). Here, we briefly review the requisite concepts from MRFs as they are used in vision and imaging applications.
Paths (a.k.a. Markoy chains) One of the most well- known MRFs is the Markov chain. A Markov chain of length d corresponds to the "path" graph La of d random variables. The above example with x, y, z corresponds to the graph La and the MRF corresponding to L4 shown in Figure 1. In a Markov chain, the indices are often interpreted as a time parameter. A classic example a gambling scenario: A person's 's money time t + 1 is conditionally independent of their total value at time / - (for > 0). given their value at time t. This property, known as the Markov property, encapsulates the idea that the future state depends only on the present state, not on past states. Markov chains have a long history of use for modeling sequential information,
A Markov random field (MRF) consists of random vec- tor x (X1....,X.)) and graph g = (V, E), where the graph's vertices correspond to the entries of the random vector, i.e., V= = (xi...., x.].. The graph encodes infor- mation about the conditional independence of the vector's 's entries. For a set A = (aI..... } C {I.....d)) d). let XA = (X Given three disjoint subsets A, B, C
3

---

Dimension-Indeeendeed Rates for Structured Neural Density Estimation
OOOO (a) Path (IA)
(b) Grid (Laxa) (c) Grid+Diagonals (Iixaa)
(a)
(b)
(c)
(d)
Figure 1: Examples of common Markov random field graphs.
Figure 2: The leftmost image (a) is 640 427 pixel photo- graph from the COCO 2014 dataset (Lin et al., 2014). Image (b) shows an enlarged version of the 102 x 102 pixel region outlined in (a). Images (c) and (d) display the 12-pixel and 1-pixel width borders of that region, respectively. Modeling this image with an MRF graph L640x427 or 4 would imply that the distribution of the missing interior in (d) de- pends exclusively of the image in (a) being uninformative for predicting this interior region. In contrast, predicting the interior using the 12-pixel border in (c) is more reasonable. This scenario cor- responds to models like L840x427 or (L640x427) which capture more extensive local dependencies. It's important to note that for the MRF model to hold, the interior doesn't t need to be deterministically constructed from the surround- ing pixels. Rather, the surrounding pixels need only provide sufficient information about the interior (e.g.. that it's cat's face) such that the rest of the image doesn't 't contribute any additional information for predicting the interior region.
including audio and text data.
Grids (a.k.a. lattices) Beyond sequential data, MRFs have seen significant use in image processing. this work, we focus on grayscale images for simplicity, bearing in mind that the results extend to RGB/color images well. For im- age processing. the classic MRF model consists of a random variable that is a 2-dimensional grid X = [Xs,]e,s and graph G where all pixels adjacent in X are also adjacent in G. Figure contains one example from two different types of grid graphs: one standard "grid" graph L3x3 and one "grid with diagonals" graph Li where the subscripts indicate the number of rows and columns of vertices, respectively. For the remainder of this work, our references to "grid" graphs encompass both pariants-thoss with and without diagonal connections-unles. explicitly stated otherwise.
its 1-pixel wide border, with the rest
Such models have seen wide use in image processing and computer vision (see Li, 1994; 2009; Blake et al., 2011, for an overview). Denoising stands as perhaps the most common application of MRFs in image processing. This approach assumes that each pixel is best predicted using just its neighbours and ignoring the rest of the image. While this model proves effective for mitigating phenomena like additive white noise (Keener, 2010), it falls short as com- prehensive image model. Similarly, the path graph, often used for sequential data, oversimplifies the complex depen- dencies in realistic sequential data.
3.1. Long-Range Dependencies
Simplistic models such as path and grid MRFs fail to capture the richer, longer-range dependencies present in real-world data. For example, in the audio example above, the content of the missing second likely influenced by a broader con- text than just its immediate neighbours. For instance, the rhythm theme established in the preceding few seconds, or the anticipation of what follows immediately after, could be crucial for predicting the missing segment. This mod- erately broader context is entirely discarded by the basic path MRF Similarly, for image data, the standard grid MRF model suggests that a region of an image depends only on its immediate bordering pixels. However, realistic images often exhibit patterns and structures that span multiple pixels in various directions. For example, the edge of an object or gradient in lighting might extend across several pixels, cre- ating dependencies that the basic grid model fails to capture. Figure 2 illustrates this concept concretely, demonstrating the effects of different MRF models on image inpainting tasks and highlighting the implications of varying levels of contextual information. These limitations motivate the need for more sophisticated MRF models where segments or regions are more extensively connected, allowing for the incorporation of relevant contextual information without necessarily spanning the entire dataset.
3. Improving The Path and Grid Markov Random Field Models
While standard path and grid MRF models may suffice for correcting extremely local or high-frequency noise in sequential or spatial data, they fall far short of capturing the true distribution of complex data types. Consider, for example, audio data consisting of 21-second clips where the middle second is missing and needs to be predicted. According to the path MRF model, this missing second would depend solely on the audio samples directly preceding and following it. Consequently, under Markov chain (i.e. path MRF) model, the remaining 20 seconds of audio (less two samples) would be deemed completely uninformative for predicting the middle second, given these two adjacent samples. In this section we propose a richer model for capturing longer-range dependencies via power graphs.
To model sequential and spatial data more realistically, we

---

Rimension-Indepennde Rates for Structured Neural Density Estimation
05
05
Figure 3: Illustrations of a path graph and its powers. Top: The path graph I5.. Middle: The power graph 7.. Bottom: The power graph Lg. In Ls. only immediately contiguous vertices are connected. In L3 every group of three contigu- vertices forms complete subgraph. In Lg. every group of four contiguous vertices forms complete subgraph. This progression demonstrates increasing connectivity among nearby vertices in the graph.
1.
0.
0.-
0.5
Figure 5: Top row: Scatterplots comparing the grayscale
values of pixels in CIFAR-10. The left image shows (8,8) vs (8,9) and the right shows (8,8) (9,12).
Bottom row: These show the same scatterplots, conditioned pixel (9,8) having a value approximately equal to 0.48 (the median value for this pixel across the dataset).
These plots demonstrate how pixel correlations decrease with distance and how conditioning on a neighboring pixel can significantly reduce correlations, supporting the use of Markov Random Field models for image data. Similar plots for the COCO dataset and for audio data from the Google Speech Commands Dataset (Warden, 2018) can be found in Appendix E.
(c)
(d)
Figure 4: Comparison of vertex neighborhoods in different graph structures. (a) Neighborhood of a vertex in a standard grid graph Laxd- (b) Neighborhood of the same vertex in the power graph La (c) Neighborhood of vertex in grid graph with diagonals L (d) Neighborhood of the same vertex in the power graph ?
3.2. Experimental Validation
While MRFs are extremely well-established image pro- cessing (Li, 2009; Blake et al., 2011), 1), is nonetheless in- structive and informative experimentally validate these assumptions using natural images. We provide exam- ple using CIFAR-10 here, while similar experiments using the COCO and Google Speech Commands datasets are pre- sented Appendix E. The top row of Figure 5 shows the grayscale values of pixel (8,8) versus selected other pixels for 100 randomly chosen images from the CIFAR-10 train- ing dataset. The bottom row repeats this experiment, but conditioned the value of the adjacent pixel (9,8) being near its median value.
propose using the "power graph" of the path and grid mod- els. For graph G, the power graph G' with E N is defined the graph where add an edge between every pair of vertices within t steps of each other in G, with G G. Figures and 4 illustrate this concept using path graphs and grid graphs, respectively. This construction causes contigu- ous sections of sequences and patches of grids to become fully connected, as demonstrated in Figure
Applying this power graph concept a grid graph assumes that local patches of images highly dependent, making no assumptions about conditional independence within patch. It also implies that, in general, distant regions of an image become independent as the distance between them increases, and that these regions are independent when con- ditioned on sufficiently wide separating region of pixels.
These experiments reveal that, when conditioned on the ad- jacent pixel, the dependence (as measured by correlation) decreases significantly. Notably, pixels (8,8) and (9,12) ap- pear almost completely independent when conditioned on
5

---

Dimension- Rates for Structured Neural Density Estimation
pixel (9,8). This provides strong evidence for the validity
squared loss) that can achieve hindeesionninddeeedeett rates of convergence for density estimation. This result is par- ticularly significant as it suggests path to overcoming the curse of dimensionality in high-dimensiona. density estima- tion tasks. By focusing on independence structures rather than dimension reduction, our approach offers a novel ex- planation for the success of deep learning methods pro- cessing complex, high-dimensional data, complementing and contrasting with the insights provided by the manifold hypothesis.
of the MRF model. The MRF model predicts that (8,8) and (9.12) should be independent when conditioned on sur- rounding pixels (the number of which depends on the graph power of the MRF graph). Remarkably, we observe that pixels appear independent when conditioned on just a single adjacent pixel, suggesting that the grid MRF assumption may be even more conservative than necessary.
3.3. Comparison to the Manifold Hypothesis
The power graph extension of path and grid MRFs presents fundamentally different perspective on modeling high- dimensional data compared to the widely accepted manifold hypothesis. While the manifold hypothesis posits that high- dimensional data concentrates around lower liwer-dimessionll structures, our MRF approach embraces the full dimen- sionality of the data, focusing instead on the independence structure between variables. This model aligns well with the observed structure various data types, capturing local dependencies while allowing for long-range independen- cies. For sequential data such audio or text, it accounts for strong dependencies between nearby elements while ac- knowledging the decreasing influence of distant context. In spatial data like images, it models high correlation between neighbouring pixels and gradual decorrelation as distance increases. Our experimental results provide compelling evidence for the MRF model's validity. The observed con- ditional independence between distant pixels, given inter- vening pixels, supports the fundamental assumptions of the power graph model.
4. MRF-Based Density Estimation with Neural Networks
After introducing some theoretical prerequisites we present our main result, showing that a structured density can be estimated at a rate that depends only on t. Our estimator is based on a neural network trained to minimize an empirical estimate of the L distance between the network's 's output and the target distribution p.
4.1. Structured Neural Density Estimation
Our estimator is based on the classical Hammersley-Cliffor Theorem (Hammersley & Clifford, 1971). Before presenting the theorem we must review few concepts. A graph G is called complete if every vertex is adjacent to every other vertex. For graph G = EV) clique is complete subgraph, i.c., G' = (V', EE) with V C V and E' C E, that is complete. A maximal clique of a graph is a set of cliques which are not contained within another clique. Observe that maximal cliques of the same graph can have different numbers of vertices. See Figure 6 for examples of maximal cliques. The collection of the maximal cliques of graph will be denoted C(G).
Moreover, in special cases, the manifold hypothesis can be seen as closely linked to conditional independence in MRFs. In images, for example, adjacent pixels x, and xj typically have similar values, causing the dataset con- centrate towards the linear subspace x; Xy, which is submanifold. The top left image in Figure 5 also illustrates this idea, where a strong concentration along the diagonal is evident. Nonetheless, these assumptions need not align in general: see Appendix F for illustrative examples of how these assumptions can vary independently.
Evidently, the manifold hypothesis cannot replace the MRF approach, and vice versa. Thus, it's important to note that our results are not meant to supersede the manifold hy- pothesis, but rather to augment and complement it. The manifold hypothesis explains sample efficiency from local structure, while the MRF model provides additional model efficiency from global perspective. Together, they pro- vide more comprehensive framework for understanding high- nigh-dimensional data.
Figure 6: A graph with maximal cliques denoted by sur- rounding rectangles.
Proposition 4.1 (Hammersley & Clifford, 1971). Let G (V, E) be a graph and p be probability density function satisfying the Markov property with respect to G. Let C(g) be the set of maximal cliques in G. Then
p(x)= = II
(v
Remarkably, in the following section, we will demonstrate that under these MRF assumptions, there exist estimators based on neural networks with standard loss functions (e.g.
V'EC(g)
where a. are the indices of a corresponding to V'.
6

---

Dimension-Indeeendeen Rates for Structured Neural Density Estimation
For neural networks we investigate estimators of the form:
The proof of the theorem, based on results from Schmidt- Hieber (2017), details the architectures and specifies how their parameters scale with the sample size. The minimax rate for density estimation on d-dimensional densities is O (n-1/(2-4)). so the "effective dimension" of an estimat- ing a density using the estimator from the theorem above is r + Consequently we see that the rate of convergence for density estimation can be greatly improved for MRFs with certain graphs G. In the next section, we explore the impli- cations of this result for the estimation of spatio-temporal data.
p(x)= = II (av.))
V'E((G)
where fhy, are ReLU networks with architectures dependent only on G and the sample size The weights are con- strained to |-1, 1], effectively implementing weight decay via constrained optimization rather than norm penalization.
Our estimator minimizes the integrated squared error be- tween p and our estimator pi:
Remark 4.3. Our results are not specific to ReLU networks and can be extended to any class of neural networks for which appropriate approximation bounds are available. For example, our results can be extended to various non-ReLU networks by using the results of Ohn & Kim (2019).
- / (p (x)))-((z)) (xx))² dx
/ dl -2 p(ar)p(a))da / (la))da..
In empirical minimization, the first term of equation 1 is constant. The second term can be estimated using the law of large numbers:
4.3. Consequences of Main Result
Our results indicate that the effective dimension of density estimation problems in spatio-temporal data, under MRF as- sumptions, determined by the size the largest clique in the underlying graph. This has significant implications for modeling and learning in domains such video, audio, and sequential data, where dependencies are often constrained within local neighbourhoods in space and time. In partic- ular, we show that for such data, the effective dimension can be far smaller than the ambient dimension, enabling significantly improved convergence rates.
I (()))(z)dd = Excp [p(x)] = Σ ((x))
lid where x1...., ~ p. i.c., the training data. Let Ud be the d-dimensional uniform distribution on the unit cube and ltd.
f ,2 U2. Then:
n
J p(w))dx = Eawuy [p())
Σ ple)). & n
1
For definitions of the graphs Laxd' and L we refer the reader to the examples in Figure 1. While these examples should provide intuitive understanding. formal definitions can be found in Appendix D.
From these two estimates we see that estimating the 2 distance between an estimator and a target density (ignoring the constant ||pl? term) is tractable.
Images We begin with the most compelling setting, corre- sponding to images:
4.2. Main Result
Lemma 4.4. Let Laxa' be a d d' grid graph with t d, d'.
We now present our theorem on the convergence rate for mi-miiiiiiin neural network- based density estimators:
The size of the largest clique in L' is less than or equal
10 441+33
Lemma 4.5. Let L be the d x d' grid graph with di- agonals, and t < d, d' The size of the largest clique in the graph (Laxæ) is (t ( 1)2
Let G = (V,E) be a finite graph and r be the size of the largest clique G. There exists a known sequence of architectures F such that for
Theorem 4.2.
Judging from the example in Figure 5, t already gives fairly reasonable model for images. Thus have the following dimension independent rate:
[1
2 Σ 1(x))
Pn arg min
dimension-inndeeedden
JeF=
1=1
Corollary 4.6 (Dimension-indeeendenn rates). The neural density estimator in Theorem 4.2 achieves a rate of
where Xi...., Xn Lid.
p. we have
Pp Pm E ŌŌ (0, (n-1/115)
lp 1olp E Öp (0 (n-I/atri).
for the grid graph L2x and
for any Lipschitz continuous, positive density p satisfying the Markov property with respect to G.
|p pull1 E Ö, (n (1-1/12)
7

---

Dimension-Independenn Rates for Structured Neural Density Estimation
for the grid with diagonals graph (Txxxa'²
varying data sizes. For instance, cropping an image would leave the maximum clique size unchanged (provided the cropping isn't too extreme), while expanding image would create larger graph but, assuming the underlying pattern holds, the maximum clique size would remain con- stant. This property results in a dimension- cowpssiioon-ideeeeeenn rate of learning that remains consistent across different image sizes. Thus, whether dealing with 100 x 100 pixel image or a 1000 x 1000 pixel image of similar content, the effec- tive learning rate remains tied to the maximum clique size rather than the total number of pixels, exemplifying true dimension independence in the learning process.
Even when t > 1, we have (t + 1)² + 2 < d. In practice we expect t = (11) so even with t > 1, the rates are still dimension-independen..
Recall that if a density p is an MRF with respect to graph G (V, E), it is also an MRF with respect to any graph g' = (V, F²) that contains all the edges from 9, i.e., E S E'. Thus, the absence of edges in an MRF repre- sents a stronger condition on p. In the graph L'xaar every 11 x (t + 1) block of vertices is fully connected. As demonstrated in Figure 5, when conditioned on an adjacent pixel, pixels tend to become independent with very little distance between them. Figure 5 shows that pixels (8,8) and (9,12) are seemingly independent conditioned on (9,8). Modeling CIFAR-10 as an MRF graph x would im- ply that (8,8) and (9.12) are independent conditioned on every pixel surrounding (8.8), a much more stringent re- quirement than conditioning on one adjacent pixel. Thus, modeling CIFAR-10 10 as (Lizxx3)) appears to be conser- vative approach. Consequently, the effective dimension for estimating CIFAR-I0 10 is (2 + 1)² 2 = 11 rather than 32 32 1024, an almost 100-fold improvement!
These extensions demonstrate the versatility of the MRF approach in modeling complex, high-dimensional data struc- tures across various modalities, while significantly reducing the effective dimensionality of the problem.
Hierarchical models Although not the primary focus of this work, our results have potential applications other data types not typically associated with deep learning, For instance, hierarchical data is often modeled as a rooted tree. For tree-structured MRFs, the following is a well-known:
Lemma 4.8. Let G be tree with at least two vertices. The size of the largest clique in G is 2.
Sequences For sequential data, we have the following lemma:
Estimating densities with a tree MRF has been studied previ- ously: In Liu et al. (201 I); Györf et al. (2022) it was found that one can estimate density with an unknown tree MRF, without the strong density assumption at a rate (nn-144 Compared to Theorem 4.2, this is an improvement by a factor of n2 but these estimators are not based on neural networks, which is our focus.
Lemma 4.7. Let La be a d-length path graph. The size of the largest clique in L2 is equal to min(t + 1, d..
Again, we observe that the effective dimension for the neural density estimator, + 3, can be far less than the ambient dimension for sequential data, such as audio.
The MRF approach can be extended to various data types, yielding similar dimension reduction results. For instance, color images can be modeled as dimennianai random tensor X E Rexxxx with graph G. In this model, the ver- tices in X. UX, j' are fully connected for li- I 1 and Lj - S 1, corresponding to a grid graph with diagonals where all channels are connected. Video data can be repre- sented by four-dimensional graphs corresponding to order-4 tensors in Rxxexwxh, with similar connectivity structure. While text data is discrete in nature, once tokenized and passed through d-dimensional word embeddings. it resem- bles spatial data with dimensions ddxt and can benefit from independence structure.
5. Conclusion
Neural density estimation has been the subject of intense study over the past few decades, dating at least back to (Magdon-Ismail & Atiya, 1998). There has recently been interest in designing structured neural density estimators that exploit graphical structure (Germain et al., 2015; John- son et al., 2016; Khemakhem al., 2021; Wehenkel & Louppe, 2021; Chen et al., 2024). In this work, we have pre- sented novel perspective on the success of neural networks in density estimation problems. Our approach, based on Markov random fields, offers an alternative explanation to the widely accepted manifold hypothesis for how and why deep learning can circumvent the curse of dimensionality, and aligns with these recent developments structured density estimation.
In all these cases, the maximum clique size is determined by how quickly independence is achieved spatio-temporally or in the embedding space, rather than by the overall data dimensionality. This approach yields effective dimensions that are orders of magnitude smaller than the ambient di- mension, leading to dimension-ing inmenssoon-ndependeen learning rates.
We have demonstrated that structured densities that satisfy the Markov property can achieve cameenion-inndpendeen convergence rates for neural density estimation on spatio- temporal data, Our MRF-based approach complements,
Crucially, this dimension independence is maintained across
8

---

Dimension-Independee Rates for Structured Neural Density Estimation
rather than replaces, the manifold hypothesis. We envision combination of local manifold-like structures and global MRF-like independence properties at play in real-world data, with the manifold hy- pothesis explaining local features and our MRF approach capturing broader independence structures.
Carlsson, G., Ishkhanov, T., de Silva, V., and Zomoro- dian, A. On the Local Behavior of Spaces of Nat- ural Images. International Journal of Computer Vi- sion, 76(1):1-12, January 2008. ISSN 1573-1405, doi:
scenarios with
120007//611260-000--003-------- URL https:/ /doi. ozg/10.1007/s112.
007-00565
This work opens avenues for future research, including in- vestigating the interplay between local manifold structures and global MRF properties, and developing practical algo- rithms exploiting these structures within existing models for neural networks.
Chac, M., Kim, D., Kim, Y., and Lin, L. A likelihood approach to nonparametric estimation of a singular distri- bution using deep generative models. Journal of machine learning research, 24(77):1 2023.
Chang, J. Stochastic processss, 2007. http:// stat otaattyylleeeee//ppoooooll/rrrre pdf.
Impact Statement
This work provides theoretical explanation for how neural networks learn high-dimensional spatio-temporal data with sample-efficient rates. We see direct societal or ethical risks specific to these results.
Accessed: Oct 1, 2024.
Chen, A., Shi, R. I., Gao, X., Baptista, R., and Krishnan, R. G. Structured neural networks for density estimation and causal inference. Advances in Neural Information Processing Systems, 36, 2024.
References
Chhor, J., Klopp, O., and Tsybakov, A. Generalized multi- view model: Adaptive density estimation under low-rank constraints. arXiv e-prints, art. arXiv:2404. 17209, April 2024. doi: 10.48550//2xxv.2444.72222
Barron, A. R. Universal approximation bounds for super- positions of a sigmoidal function. IEEE Transactions on Information theory, 39(3)9930-945, 1993.
Bengio, Y., Courville, A., and Vincent, P. Representation learning: A review and perspectives. IEEE Transac- tions Pattern Analysis and Machine Intelligence, 35 (8):1798-182)) 2013. doi: 10. 10.1 1..1109//AAM..213.5.5
Cole, F. and Lu, Y. Score-based generative models break the curse of dimensionality in learning family of sub-gaussian probability distributions. arXiv preprint arXiv:2402.08082 2024.
Devroye, L. and Gyorfi, L. Nonparametric Density Estima- tion: The L' View. Wiley Interscience Series in Discrete Mathematics, Wiley, 1985. ISBN 9780471816466
Berenfeld, C., Rosa, P., and Rousseau, J. Estimating a den- sity near an unknown manifold: a bayesian nonparametric approach. arXiv preprint arXiv:2205.157717 2022.
Devroye, and Lugosi, G. Combinatorial Methods in Density Estimation. Springer, New York, 2001.
Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. MIT Press, Cambridge, Mass, 2011. ISBN 1-283-25865-X.
Falconer, K. Fractal Geometry Mathematical Foundations and Applications. John Wiley Sons, Ltd, United States, 2nd edition, 2003. ISBN 978- 00-00-47-848--3-- Second Edition (major revision plus solutions manual).
Bos, Т. and Schmidt-Hicher J. A supervised deep learning method for nonparametric density estimation. arXiv e- prints, art. ar arXiv:2306.1144 10471, June 2023. doi: 10.48550/ arXiv.2306.104 10471.
Genovese, C. R. and Wasserman, L. Rates of conver- gence for the Gaussian mixture sieve. The Annals of Statistics, 28(4):1 105 - 1127, 2000. doi: 10. 1015956709. URL https: //tp:///ooiii///oo www//o.g......ooo 1214/ aos sos/1C159567CS
Brahma, P. P., Wu, D., and She, Y. Why deep learning works: A manifold disentanglement perspective. IEEE Transactions on Neural Networks and Learning Systems, 27(10):199722000 2016. doi: 10.1109/NNLS.2015. 2496947.
Germain, M., Gregor, K., Murray, I., and Larochelle, H. Made: Masked autoencoder for distribution estimation. International Conference on Machine Learning, pp- 881-889. PMLR, 2015.
Cao, H., Tan, C., Gao, Z., Xu, Y., Chen, G., Heng, P., and Li S. Z. A survey on generative diffuusion models. IEEE
Transactions on Knowledge and Data Engineering. 36
Groeneboom, P. Estimating a monotone density. Proceed- ings of the Berkeley conference in honor of Jerzy Neyman and Jack Kiefer, 1984.
(07):2814-288)) jul 2024. ISSN 1558-2191. doi: 10. 1109/TKDDE.20443331177

---

Dimension-Independee Rates for Structured Neural Density Estimation
Groeneboom, P., Jongbloed, G., and Wellner, J. A. Es- timation of Convex Function:
Klusowski, J. M. and Barron, A. R. Approximation by com- binations of relu and squared relu ridge functions with e and 6 controls. IEEE Transactions on Information Theory, 64(12)7744--7556 2018. doi: 10. 10.1109/TIT.2018 2874447.
Characterizations and Asymptotic Theory. The Annals of Statistics, 29(6):6633- 1698, 2001. doi: 10. 00.122///as/0011334443 //doi (edoi.org/100 121 4 ass / 101 5345958.
URL https:
Györfi, L., Kontorovich, A., and Weiss, R. Tree density estimation. IEEE Transactions on Information Theory, 6682):116-11176, 2022.
Kuzborskij, I. and Szepesvári, C. Learning Lipschitz func- tions by GD-trained shallow overparameterized ReLU neural networks. arXiv preprint arXiv:2212.13844, 2022.
Hall, P. and Zhou, X.-H. Nonparametric estimation of com- ponent distributions in multivariate mixture. Annals of Statistics, pp. 201-224, 2003.
Kwon, H. K. and Chae, M. Minimax optimal density es- timation using a shallow generative model with a one- dimensional latent variable. International Confer- ence on Artificial Intelligence and Statistics, pp. 469-477. PMLR, 2024.
Hall, P., Neeman, A., Pakyari, R., and Elmore, R. Nonpara- metric inference in multivariate mixtures. Biometrika, 92 (3):667-678, 2005.
Li, S. Z. Markov random field models in computer vision. In Eklundh, J.-O. (ed.). Computer Vision ECCV '94, pp. 361-370, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. ISBN 978-3-540-4840044
Hammersley, J. M. and Clifford, P. Markov fields on finite graphs and lattices. Unpublished manuscript, 46, 1971.
Ho, J., Jain, A., and Abbeel, Denoising diffusion probabilistic models. In Larochelle, H., Ranzato, M.. Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851. Curran Associates, Inc., 2020. URL ftt._elessaapper/2///leeee cc cc/paper Achccfees33Ac0000677111010072220 pdf.
Li S. Z. Markov Random Field Modeling in Image Analysis, Springer Publishing Company, Incorporated, 3rd edition, 2009. ISBN 978 0781848002784.
Liang, T. How well can generative adversarial networks (GAN) learn densities: A nonparametric view. arXiv preprint arXiv:
2017.
Lin, T.-Y, Maire, M., Belongie, S., Bourdev, L., Girshick, R., Hays, J., Perona, P., Ramanan, D., Zitnick, C. L., and Dollár, P. Microsoft COCO: Common Objects in Context. arXiv e-prints, art. arXiv: arXiv:1405.033 1405.032., May 2014. doi: 14485500arxi..1455.055
Jiang, H. Uniform convergence rates for kernel density esti- mation. In International Conference on Machine Learn- ing, pp. 1694-1703, 2017.
Jiao, Y., Shen, G., Lin, Y., and Huang, J. Deep nonparamet- ric regression on approximate manifolds: Nonasymptotic error bounds with polynomial prefactors. The Annals of Statistics, 5162)6691-716, 2023.
Liu, H., Lafferty, J., and Wasserman, Sparse nonpara- metric density estimation high dimensions using the rodeo. In Artificial Intelligence and Statistics, pp. 283- 290. PMLR, 2007.
Johnson, M. J., Duvenaud, D. K., Wiltschko, A., Adams, R. P., and Datta, S. R. Composing graphical models with neural networks for structured representations and fast inference. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29, pp. 2946- 2954. Curran Associates, Inc., 2016.
Liu, H., Xu, M., Gu, H., Gupta, A., Lafferty, J., and Wasser- man, L. Forest density estimation. The Journal of Ma- chine Learning Research, 12:907-951, 2011.
Ma, C., Wu, L., et al. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369-406 2022.
Keener, R. W. Bayesian Inference: Modeling and Com- putation, pp- 301-318. Springer New York, New York, NY, 2010. ISBN 978-0-387-93839-44
doi: 10.7/
Tagdon-Ismail M. and Atiya, A. Neural networks for density estimation. Advances in Neural Information Pro- cessing Systems, 11, 1998.
978-0-387-93889-- 15. URL https://///... /tte::///oo.///// /t/ddo.ooorgg 10. 100. 9988--88--- 0 387- 93839- 4_1
Khemakhem, I., Monti, R., Leech, R., and Hyvarinen, A. Causal autoregressive flows. In International Conference on Artificial Intelligence and statistics, pp. 3520-3522 PMLR, 2021.
Nakada, R. and Imaizumi, M. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1-38, 2020.
10

---

Dimension-Indeeeende Rates for Structured Neural Density Estimation
Ohn, I. and Kim, Y. Smooth function approximation by deep neural networks with general activation functions. arXiv preprint arXiv:190..0 190060696000, 2019.
Stone, C. J. Additive Regression and Other Nonparametric
Models. The Annals of Statistics, 13(2):689 705, 1985. doi: 10. 00.121//ass/11766499555 URL ht ht /dop:::/.i....//// /doi.
org
Oko, K., Akiyama, S., and Suzuki, Diffusion mod- els are minimax optimal distribution estimators. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learn- ing Research, pp. 26517-266 26582. PMLR, 23-29 Jul 2023. URL. https:::p.......p... httptppp://pppeeeeee /pproceeeddiicc ngs. mlr, presss/// v202/oko23a. html.
Tang, R. and Yang. Y. Adaptivity of diffusion models manifold structures. In International Conference Arti- ficial Intelligence and Statistics, pp. 1648-1656. PMLR, 2024.
Tsybakov, A. Introduction to nonparametric estimation. Springer Series in Statistics, New York, pp. 214, 2009, cited By 1.
Uppal, A., Singh, S., and Póczos, B. Nonparametric density estimation & convergence rates for GANs under Besov IPM losses. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' "rché--BBee F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9086- 9097, 2019. URL
Oussidi, A. and Elhassouny, A. Deep generative models: Survey. In 2018 International Conference on Intelligent Systems and Computer Vision (ISCV), pp. 1-8, 2018. doi: 10.1 N0.1109/SSAC.2011 1..1099/ACCV.2008835550)0 8354080.
Ozakin, A. and Gray, A. Submanifold density estimation. In Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C., and Culotta, A. (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL https://proceeiing..rr neurips. ce/ htapee/_ffieee/ppprr////////111 2ac206688330d448777454aaaaaa pdf.
neurips. wtt.rips.ccppappeeeeeeeee 1at00099/hhhhh E200ff891e6000550001666662222222 www.aa22ddds2-----aa..... Abstract. html.
Paper.
Vandermeulen, R. A. Sample complexity using infinite mul- tiview models. arXiv preprint arXiv:2302.04292, 2023.
Pelletier, B. Kernel density estimation on riemannian man- ifolds. Statistics & probability letters, 73(3):297-304, 2005.
Vandermeulen, R. A. and Ledent, A. Beyond smoothness: Incorporating low-rank analysis into nonparametric den- sity estimation. Advances Neural Information Process- ing Systems,
Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., and Gold- stein, The intrinsic dimension of images and its impact on learning. In International Conference on Learning Representations, 2021. URL https: pppprevven.eeeeeeeeeeeeee met/ffrune d= 9XzGq2J.
2021.
Warden, P. Speech Commands: A Dataset for Limited-
Vocabulary Speech Recognition. arXiv e-prints, art. April 2018. doi: 10.48550/arXiv.1800
03209.
Samworth, J. Recent Progress in Log- Concave Density Estimation. Statistical Science, 33(4):493 509, 2018. doi: 10. 111111211-8-S6666 httpsttp: //dii. 10 1214 //1 -006666.
Weed, J. and Bach, F. Sharp asymptotic and finite-sample rates of convergence of empirical measures Wasserstein distance. Bernoulli, 25(4A):2620 2648, 2019, doi: 10.3150/18-BEJ100 URL https: /doi org/10. 3150/ / 8 BEJ1 065.
Slhmidd-HHihher J. Nonparametrie regression using deep neural networks with relu activation function. arXiv preprint arXiv:1708 /.XV::/708.0663,, 2017.
Wehenkel, A. and Louppe, G. Graphical normalizing flows. International Conference on Artificial Intelligence and Statistics, pp. 37-45. PMLR, 2021.
Schmidt-Hieber, J. Deep ReLUU network approxima- tion of functions on a manifold. arXiv preprint arXiv:1908. 00695, 2019.
Zhang, K., Yin, H., Liang, F., and Liu, J. Minimax optimality score-based diffusion models: Beyond the density lower bound assumptions. arXiv preprint a4Xiv:2402. 5500,, 2024.
Singh, S., Uppal, A., Li, B., Li, C.-L., Zaheer, M., and Póczos, B. Nonparametric density estimation under adver- sarial losses. Advances in Neural Information Processing Systems, 31, 2018.

---

Dimensiio-Inndeeeneent Rates for Structured Neural Density Estimation
A. Proof of Proposition 2.1
Our proof of Proposition 2.1 makes use of notion of Hausdorff dimension, sometimes referred to as the Haus- dorff- Besicovitch dimension, along with few of its basic properties. The Hausdorff dimension provides way to assign a notion of dimension to in Euclidean space; for example, d' df-dimensional linear subspace of E has Hausdorff dimension d'. Before defining the Hausdorff dimension, first introduce the concept of Hausdorff measure. For measurable set A C IRd let |A] denote its Lebesgue measure.
For any set A C gd, its s-dimensional Hausdorff measure is defined as
{U:} is 6-cover of A
71" (A)) lim inf 6-40
A
The Hausdorff measure is, in some sense, the natural notion of measure for sets that may not have the same dimensionality as the ambient space. For example, for all d there exists a constant > 0 (the volume of the d-dimensional unit ball) such that for all measurable sets A C RR c,Hl' (A) = AA| (see equation (2.4) in Falconer (2003)). also aligns with volume on smooth divensiinnsional subsets, such as manifolds. A set has finite, positive Hausdorff measure for at most one value of s, which defined to be its Hausdorff dimension. This notion can be extended sets for which no such value of exists.
For set C IR,, its Hausdorff dimension is defined
dimn (A) = isf 0: (A) = 0} sup 2 0: (*) co}.
We will not explore Hausdorff dimension further, except to note the following three properties:
1. If S B, then (A) < dima(B) (Falconer, 2003, 32).
2. If f [d + R is Lipschitz continuous, then dimu dim=(f(A) (f(A) S dimg(A) (Falconer, 2003, Corollary 2.4).
3. If M is a differentiable m-dimensional regular submanifold of Rd, then dimm (M) = m (Falconer, 2003, p. 32).
Proof of Proposition 2.1. We proceed by contradiction. Assume that the proposition setting holds except there exists subset XI..... X1 Le that are mutually independent. Without loss of generality, we assume I; = for all i. Let π .MM + 41 be the projection onto the first d' + coordinates. Then the pushforward measure क / is given by d'+1 Oz=1 Ps and hence s has positive Lebesgue measure in gd'+1, It follows that its Hausdorff dimension dima (supp(**1)) d' 1.
On the other hand, we know that supp(TTи) C T (M)+ so
(ump(sup) S dimp(T (MM)).
(2)
Since ı is Lipschitz continuous we have that
dimy (Tnn(T(MM) < dimg (M).
(3)
Finally, since M is d' aiddimensional regular submanifold of Rdd, we have that
dimm(M) d'.
(4)
Combining equation 2, equation 3, and equation 4 it follows that
dimp(supp(T*1)) < d'
which contradictions (imp((up)(T d' + from before.
12

---

Hiieension-nneependee Rates for Structured Neural Density Estimation
B. Main Result: Notations and Preliminaries
Before proving the main theorem we will first establish some notation and auxiliary results. For a pair of functions f.g X R where an arbitrary domain, we define the f g to be pointwise function multiplication so (f-g)(z) = f())((z) for all æ X. For tuple of functions fi...., fm X + R. the product symbol I[ fr is defined to be pointwise function multiplication, i.e., (1) f2(2) fz(()) for all X. Let N be the set of positive integers. For any d N, let [d] = ( (1.).....d]
For set V C. [d] with V = foi...., f U e accepts a d-dimensional vector and outputs the indices at V, in order. The function ev,d can be thought of as selecting some indices from a vector. As a slight abuse of notation, the d subscript will be omitted.
where < bj for all < j. let eav R - R ; + [Te...... Tep J i.c.
RM
For graph G EV, the set of maximal cliques will be denoted C(G). and is set of subsets of V.
All of our results will assume the domain of the data is the unit cube [0, 1]s. A density will be called positive if p(x) > 0 for all x 1].. Since [0, 1j is compact, a direct consequence of this is that there exists O such that p(x) for all x.
B.1. Preliminary Results
Proposition B.1. Let be a Lipschitz continuous probability density [0, 1] which is everywhere positive on [0, 1]4 and satisfies the Markov property with respect to a graph G = =V, E). Then, for all E [0,
p(x)=
II V'EC(g)
vv (ev (x))
where each viv is Lipschitz continuous, and there exist constants C such that 0 < < C and S v/v S C for all V' E C(g).
Before proving this proposition first prove the following support lemma.
Lemma B.2. Let f.g: [0, 112 R be Lipschitz continuous with f 2 and g 2 8 for some Then f 9 and f/f are both Lipschitz continuous and there exists 8' O such that f g 8' and 1/f 8'.
Proof of Lemma B.2. Let f be -iiischht and be Lipschit. Because f and g are Lipschitz on a bounded set there exists Cj and Cg such that s Cy and g S Cg. Let x. y [0, 1] be arbitrary.
We will begin by proving the product portion of the lemma:
lf(x)g(=) - f(v)g(v)) = (f(=)((z) + f(v)(())
I Cg()(() ((v)l (() f(y)
< C -|1--=lll C,4s - vll2
< 2 max (Cy C,4,) || vll2-
The existence a positive lower bound for f --g follows immediately from / f.g 8
To prove the reciprocal portion of the lemma, observe that the function æ ++ 1/x is Lipschitz on the range of f. Since the composition of Lipschitz functions is itself Lipschitz, it follows that 1/f is Lipschitz. Finally we have that 1/f 2 1/C, finishing the proof.
Proof of Proposition B.I. This proof utilizes results from Chang (2007), a -i-ogre-s book currently used primarily as lecture notes. This work has constructive proof of the Hammersley- Clifford Theorem. For S c [d], let "ss Rd + Rd:r + (i E 5)]; i.e., indices outside of S are set to zero (the zero vector could actually be set to any arbitrary but fixed vector, e.g., set vector y E IRd and [ís]egs yı). From the Chang (2007) (3.15), the proof of the Hammersley-Cliffon Theorem, is shown that:
-llfffffr
p(x)
II
V'ec(G)
13

---

Aeneesioo-Independeee Rates for Structured Neural Density Estimation
where,
Il IVvvvv mod 2=0 P (7 (xr)
Vv (a)
(5)
AVVVvv mod 2=1 (7 (z))
For clarity do example of the index set of the product;
c c V.V V' v"I mod 2 = 0
denotes a product over all subsets of V where the set V" where V n V contains an even number of elements. From equation 5 it is clear that ty only depends on the indices of x in V' The regularity conditions hold due to Lemma B.2.
Given any set S. For any subset S' S S, let 1g be the indicator function from S to {0, 1), i.c.
0 if & S
1s(x) = {
for all x E S.
i E 8
Given any d E N,V= = (11 [d] and C 2 1. For any A E [b] let Ad,.AA be the subset of (0, 1]4
AdbAV = x (0, 1] 3 E
A 1 A
for all [IVI]
(6)
b
Let Q.a.ViC be the set of functions from [0, 1]d R
w WA (allasav(s) WA E [0.0].
Qda.Vv. = 1 H
Σ
For set C L (I0, 110) where 1 S oo and c > 0, a subset S L is called an c-cover L in L norm if, for any f C, there exists a C such that || - glla S e. Also, define (CC, be the cardinality of the smallest subset of L that is (closed) e-cover of L in L norm. Note that N(C,e) depends B. We will not specify it when it is clear in the context.
C. Proof of Theorem 4.2
Theorem C.1. Let G = (V, E) be a finite graph and r is the size of the largest clique in G. There exists a neural network architecture F*, such that, for
2
Pn. arg min feFi
11
f(X.)
t=1
where XI...., Xn then
1 Pm 12l2 E Öp (n- (n-1/(atr))
for any Lipschitz continuous, positive density p satisfying the Markov property with G.
This is stronger than L convergence since, through Hölder's inequality, we get Lt convergence the same rate.
Lemma C.2. Let (St E, μ)) be measure space, and let fi...., , fm and 91....s 9m be measurable and absolutely integrable functions Q. Further suppose there exists constant C. 2 0 such that, for all i E [m].
le S C and l1gella SC
Then the following inequality holds:
f
<
m 11
[A Dilloc
i=
14

---

Dimension-Indeeenni Rates for Structured Neural Density Estimation
Proof of Lemma C.2. We will proceed by induction on m.
Case 1: Trivial.
Induction: Suppose the lemma holds for some value of m. From the inductive hypothesis we have that
II
f
II
9
S
fm+11
II
gs
fm+1
+
9:
fm+1
II gs 9m+1
im1
170
Y73
m
gi
|l5m+1 1l,0
II
gi
115m+1
9m+1llx
00
m7
Y73
9i
C C Ilfm+1 - 9m+1llx
t=1
m
<0m-1
Il.fs 9: C C Ilfm+1 Imtill
m+11
00nh m
[Ifi - 9illoc
Space of Neural Network Architectures Define a space of neural networks as follows. Let be the ReLU activation function with will act element-wise vectors. For any l N, (Wn,..., W241) with w; E N, N and F >> 0, the space F (e, w.s. F) is defined by the functions f [0, 1 R we+1 which have the form:
(w) Wi Wr- 1
Wi Wox:
where F., (v) = oly u;). W; E R Xw,, where every entry in W; and v; have absolute value less than or equal to 1, || F. and sum of the total number of nonzero entries of W; and v; is less than equal s. In this work the output dimension of all neural networks will be 1, i.. W4+1 will always be assumed to be 1. This is the same space of neural 2017).
network models employed by (Schmidt-
Theorem C.3 (Theorem 5, Schmidt- Hieber, 2017). For any f E (10, 1]a, K) and any integers m 2 and N 2
max((3 + 1)x, (K + )) there exists ReLU network f E F(e, w. 8, oo) with depth
8 (m 5)(1 + [log2(max(( B))1).
(8)
widths
w (d, 6(d + [9]) ... 6(d+ [B]) 1),
(9)
and sparsity
s S 141(d + 3 1)443 (m
(10)
such that
|| -- A (2K + 1)(1 + & 326 m + N-
(11)
Lemma C.4 (Lemma 5, Remark Schmidt- 2017). For any 6 > 0,
log N(F(( w. 8, 00), (1.1(c)) S (s + 1) log (2 20 (l + 1)
C.1. Main Estimator Proofs
Proof of Theorem C.I. Recall that, given a graph G. C(g) is the set of maximal cliques in G. For any V e C(G). let Fv. = (Ev', SVv, 8, C.) where lv., wy 8, will be determined later. Also, let
II V'E((G)
q oevi qu E Fv
(12)
15

---

RimeeniionInndeeendee Rates for Structured Neural Density Estimation
We shall show that F is the neural network architecture satisfying the desired guarantees in Theorem C.I.
For any set of n ii.d. samples X Xn drawn from p, let
2 Σ F(X.))
Pr = arg min Ip JE
f11 and Pn = arg min
[ifl
(13)
Jer
21
Now, we would like bound the term 1/ plß. We first express it as
II,.
pl2
(l pll Ilp pll) + IlpT -1122
For the term I|ph - pl12 - -Ipp" pll. we further express it as
pll ( [1p11 l1 11
2 n n
li p12
llph pl1 I1pm.
pn (Xii
:=A
11e122 + |1 11
2 Σ
2 n
pn(xi) - 11pp - -P12
(14)
i=1
Before we bound A and B, first provide a useful inequality. For any p' E F., have
1p pl ( [1pl12 + 1Ip'11 Σ
px())
2=1
Σ (X.)) - 2 (p'.p)
1 Σ f(X,)
S max f
Ep(f)
since (p/P) [V' and p' E F*.
(15)
7
For the term A, we immediately have
2 n
A = 11 p11 (Ile11 /
+112m113
Σ Px())) 1=1
< 2 max Ee
Ep(f) Σ s(x))
since Pn E F²
1=1
For the term B, we have
2
B
11p12
11
Pn (Xi)
-11%% pll
i=1
2
lIpl2 + 1Ip;,
Σ
P (X,)
- ||pT" - pll
by the optimality of pr.
i=1
$ 2 max
(f)
Σ f(X.)
since Pn E F
-
7
i=1
By plugging them into equation 14, we have
n
1b, --11
max -E
Ey(f)
Σ f(X,)
+ 11p -pl13
(16)
n
16

---

Dimension-Inddeendeee Rates for Structured Neural Density Estimation
We first analyze the term lp pll in equation 16. From Proposition B.1, have that
II V eey. V'EC(G)
p
and there exists some Cs > 0 so that vh & Cp for all V' and that, for some Ly,, all d/v are Lu-Lipschitz continuous. We pick sufficiently large C that is greater than Cg. Also, by the definition o* in equation 12, we can pick a qu E Fv. for each V C(g) and form an f E FF such that
F
f f= II q ev..
ViEC(g)
We will specify each qv later. Then, we have
|lf 20 =
II VEE(()
qv o eyr
II VEC(G)
v/y ocy
< <)(()))
qV" e V/v Ev
by Lemma C.2
(17)
V'E((g)
00
Recall that Fv. = F(lv', w C). For any sufficiently large m, N E N which we will determine later, we pick
fv- 8 + (m + 5) + flog2 IV")),
wy = (IV"), + 1)N, 6([V' + 6(1"
2)
and recall that we have picked C to be a constant larger than Cy before. It is easy to check that the hypotheses of Theorem C.3 are satisfied with K Ly. 3 and d = = and hence, by Theorem C.3, if we pick
qv arg min 8p. Exp
pv. oer v/v ev
then have
qv eey. vv oev
< (2Lg) + ()(1++++1 1)6 N2- 11)'"' 1.NN-11111
O(N2- + +N N/1)
(18)
By plugging equation 18 into equation 17, we have
fl pll. S -1
Σ
O(N2 m + +N-1/r)-- 0(N2-
-(N2-- + -N1//r
V'E((G)
Recall that the domain [0, 1jd and hence we have
|If - 1 I 0.
1f(x) p(x)) |lf pll
Now, by the optimality of P in equation 13, have
lpp:. pll < Ilf - pll = Ilf - pll = 0(N22-2m + -22r))
(19)
Now, we take care of the term max
- - f(x)) in equation 16. To bound this term for all f E F* we first construct an e-cover of J in 1,00 Then, we use the Hoeffding's inequality to bound this term for each the c-cover
17

---

SimeeniionInndeenddee Rates for Structured Neural Density Estimation
and use the union bound control the total failure probability. To construct e-cover, we define the following notations. For any V C(g), let Fy be minimal - of Fvr in T where is sufficiently small value and will determine it later. Also, let
II @v ov liv E Fir] } VieC(g)
(20)
We will show that F is e-cover of F in L For any f E F. it can be expressed
f ==
II VEE(G)
qu eve for some qa Qv
Since Fvr is an टायकका cover of Fvr in 0 for all V E C((g), there exists a qv E Fiv such that
qv S CIC
By the definition of F, we set f E F to be
j II VIEC(G)
T oep
By Lemma C.2, we check that
| i
II VECCG)
QV'
II VV' VEC(g)
= =c(((0)-11
Σ
11 - 10o
V"CC(G)
Cle(g) -1
e.
Now, we return to the term max Bp(f) - a ((X))
Since F is an c-cover of F in L for any f E FF,,there there
exists a j F such that Il. flloc S and we have
(s) - 1 Σ ((x))
i=1
< (f) -E)(f) + 1x(()
Σ
f(x,)
+
1 Σ f(x.)
10xx)111 Σ f(X.)
1=1
1=1
1=1
a n Σ F(X.)
< 2e + Ex(f)
which implies
(f) - 1 M f(X,)
Ex(F) - Σ f(x.)
"
max -e
s 2e + max
(21)
JeF.
By Hoeffding's inequality and the union bound, for any
> the probability of
E 1 Σ f(x.) >6
max fe
bounded by |F* e Q((t))
18

---

Dimension-Indeeeeddee Rates for Structured Neural Density Estimation
To bound the term [F by the definition of F in equation 20, first have
log |=|= =
Σ
log [v.l.
Viecig)
For each term log |. by Lemma C.4, we have
log |v S (s + 1)
(Lv+ 1))1")2
+
We now bound the architecture parameters. Recall that
tv 8 + (m + 5) + [loge I'Il) for any V C(g) and
14 3)+3N((m 6)]-
Namely, we have
Nm
lv
Omm) and
(Nm) which implies log [Fvl S O(Nm² log
That means we have
log F
Σ V'CCG))
Nm O(N log - = ONNm² log
Nm
By setting t O(v
Nm² log Nnm ), have
Nm
Nnm
max fEF.
(p(
f(X.)
< <0(V
log
n
with at least probability
1 e Q(ntt) - 1 as + co. Plugging it into equation 21, we have
Nm² Nnm
max FE
Ef(f)
f(Xi) S 22 + Oly
log
(22)
n
Furthermore, by plugging equation 19 and equation 22 into equation 16, we have
ES( 1 Σ f(Xi)
pl1 <
max FEQ
+ 11pp% - -p11
==1
Nm2
Num
O(e +
log
222 + 222rr.
By picking
= n P
= - and
m
r + log n,
have
1b - -p13 < Ō(n -
19

---

Dimension-Inndeeeneer Rates for Structured Neural Density Estimation
D. Graph Proofs
For any d, d', & E N, define Laxa' to be the graph whose vertex set is [d] x [d"] and edge set is
((...)) i e [d], e [d') (1. + (d',5),, 51 -"
and ax to be the graph whose vertex set is [d] x [d"] and edge set is
((,,)))(,,))) 1 E [4.i.'' E [d') (1,5) + (2, (', - +1 - - s4.
For any d, d', N, define L to be the graph whose vertex set is [d] x [d'] and edge set is
(( i [d...j' e [d"], (i,j) * (f' max j1. - 1
and ( to be the graph whose vertex set is [d] x [d'] and edge set is
(((i.)). (E.))) 1, [d].5.'' E (d", (1, + (',, max - j1.11 - J'1) s tt.
For any d, 1 E N, define La to be the graph whose vertex set is [d] and edge set is {(i,)) i + j. j - j 2 1} and Ig to be the graph whose vertex set is [d] and edge set is {(i,j) | i # j. l j 2 t).
Proof of Lemma 4.4. For any clique C in (Laxd)) ) let (io: jo) (resp. (i1, ). (%: H6) and (i1,11) be the vertex in C' such that in jo is maximal (resp. i + Jn is minimal, i H is maximal and 8 ñi is minimal). Namely, the vertex set of C is subset of
8: (i.D)) [d], [d'), + sits 10 + jo. 1 í Si j S 1/ -j.-
By the definition of cliques and (Laxd!) )r, we have
(io + jo) - (i1 + ji) < - in + Lio -il S t
since there is an edge between (4o, jo) and (i1,51) since there is an edge between (4 and (f),))
(66 - 16) - (i] - ńi I 1/0 - x + 1/6 - 31 < t
To bound the size of S, we observe that, for each of the at most i + 1 possible values i + j1, i + +j + 1,..., to + jo equal to + there are at most 1+11 possible values among in + ji. i + Jí + +,.... in - % equal to i j by considering the
2
parity. Therefore, |S] is at most (t + 1) [+1
Hence, the size of the largest clique in (Laxa) ) is at most (t + 1)- [+1 2+41+3
2
Proof of Lemma 4.5. is easy to check that the subgraph of (x Hence, the size of the largest clique in af is at least (t + 1)2.
) induced by the vertex set + 1] x [t + 1] is a clique.
)
For any clique C in (T , let io (resp. i()) be the smallest (resp. largest) first index of the vertices in C and jo (resp. %%) be the smallest (resp. largest) second index of the vertices in C., Namely, the vertex set of C' is a subset of
s = (i.,))li [d].j E [d"]. ia S S Jo 16).
To bound the size of S, by the definition of cliques and (4 )r we have
1 -0 SL and H6 - jo S
Therefore, |S] is at most (t + 1)2.
Hence, the size of the largest clique in ) is (t + 1)2.
20

---

Dimension-Independeee Rates for Structured Neural Density Estimation
Proof of Lemma 4.7. It is easy check that the subgraph of L2 induced by the vertex set [min(L+ + 1, 1,d]] is clique. Hence, the size of the largest clique in I.y is at least min (t + 1,d].
For any clique C' in L.. let io (resp. jo) be the smallest (resp. largest) index of the vertex in C. Namely, the vertex set of C' is be subset of S = {ila E [d] 80 I i S jo). By the definition of cliques and L'd we have l - jl S min(t, d - 1}. Therefore, |S] at most min + 1, dd.
Hence, the size of the largest clique in L is min(t + 1, 1,d].
E. COCO and Google Speech Commands Scatter Plots COCO
coel
cor cosel
For 0.43
For cosl 0.09
(a) (120, (120,, 161)
(b) (120, 160) 162)
(c) (120, v60)v(120000 400)
(d) (120, (320, 520)
Cor, coot - 0.56
con coot - 0:42
Cor coot 0.02
Cor: coof. 0.03
(e) (120, (60) 161) cond. (f) (120, (60)v(120, 162) cond. (g) (120, 160) 100) cond. (h) (120, 160) ((200, 520) cond.
Figure 7: This figure presents scatter plots analogous to those in Figure 5 of the main text, but derived from the COCO training set (Lin et al., 2014). The conditional scatter plots are based on pixel (121,160) being near its median value.
Due to memory constraints, we used a subset of the data:
1. 4000 random samples were initially selected.
2. From these, 100 images with pixel (121,160) nearest to the median were chosen for the conditional plots.
Note that increasing the sample size for conditioning resulted in lower observed correlation. This is because a larger sample allows for a more precise conditioning, better approximating the true conditional distribution. The wider the range of values for the conditioning pixel (121,160), the more the selected points resemble the unconditional distribution, potentially introducing spurious correlation.
21

---

Dimension-Indeeendeee Rates for Structured Neural Density Estimation
Google Speech Commands
Here we consider the correlations and conditional correlations for covariates from audio data. We use the Google Speech Commands Dataset (Warden, 2018), focusing the "no" class. The corresponding plots are shown in Figure 8.
We note that the dataset contains more extreme outliers than the image datasets. For example, while 50% of all entries have magnitude 80 or less, the maximum magnitude in the dataset is 32,767. This causes some of the scatterplots in Figure 8 to appear off-center. We use 500 randomly selected samples, which helps reduce visual artifacts from quantization when plotting conditional correlations with fewer samples.
Unlike Figures 5 and 7, the z- and y-axes in each image here are not normalized to the same scale, and the r-values in the conditional plots are often skewed. None of these issues affect the underlying correlation or conditional independence properties aim to illustrate. While explored ways to account for these quirks in the visualizations, ultimately opted to present the raw plots for simplicity, as the effect on dependence structure is still clearly visible.
car, coot. 0.92
cor: coot - 0.84
cor coof. 0.57
cor coof 6:27
(a) ms v 50.2 ms
(b) 50 ms v 50.3 ms
(c) ms vs 51 ms
(d) 50 ms v ms
cost 0.07
reet 10
cor roet
n 07
(e) 50 v 50.2 ms cond.
(f) 50 ms v 50.3 ms cond.
(g) 50 ms vs 51 ms cond.
(h) 50 ms v 60 ms cond.
Figure& 8: This figure presents scatter plots analogous to those in Figures and 7, but derived from the "no" class of the Google Speech Commands Dataset (Warden, 2018). The plots compare the sample value at 50 ms with the values at other time points. The conditional graphs (bottom row) show the same comparisons, but conditioned on the value of the sample immediately after 50 ms being near its median. Note that the sampling rate of this dataset is 16,000 Hz, so each sample corresponds to approximately 0.1 ms.
22

---

Dimension-Indeeendeee Rates for Structured Neural Density Estimation
F. Decoupling the Manifold Hypothesis and the Markov Random Field Assumption
Here, we present four simple examples illustrating that the manifold hypothesis and the MRF assumption are, a fundamental sense, independent modeling concepts.
MRF true, MH true: ~ unif(o, 1j. Y ~ unif(O, 0.01J, X and Y independent
MRF true, MH false: X, Y unif(O, 1). X and Y independent
MRF false, MH true: ~ unif[0, 1], =Y
MRF false, MH false: X, Y (0, 1), weakly correlated
23


Reviews:
[{"review_id": "XMjc95krmW", "reviewer": "Reviewer_ZT7H", "summary": "Estimating probability densities is a recurring task in machine learning and statistics. However, this becomes challenging in high-dimensional settings due to the curse of dimensionality, where the number of required samples grows exponentially with the dimension.  \n\nThis paper addresses the challenge of high-dimensional density estimation by leveraging structured dependencies in real-world datasets such as images, videos, and text. These datasets often exhibit underlying structures that can be represented as graphs with small cliques, enabling more efficient estimation. The authors show theoretically the existence of deep neural networks trained to learn the density from samples that can achieve convergence rates that are independent of the dimension. In particular, when data dependencies are modeled by a power graph Markov random field, the neural network estimator converges at a rate of $n^{-1/(4+r)}$ in the $L^2$ norm, where $n$ is the number of samples and $r$ is the size of the largest clique in the graph of MRF. The notion of power graphs extends classical Markov random fields by capturing higher-order interactions.\n\n## Update after rebuttal\nI would like to thank the authors for their response. I am maintaining my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__\"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.\"__\n\n__\"The theoretical results assume that the clique structure of the probability distribution is given...?\"__\n\nA 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] .\n\nOutside 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.\n\n__\"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.\"__\n\nWe 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:\n\n__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$.\n\nHere we have the following lemma makes our point relating the manifold hypothesis and dependence precisely (which is maybe of interest in its own): \n\n__Lemma:__\nLet $ 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)$\ncannot be mutually independent.\n\nSo, 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).\n\n__“Figure 3: The visualization would be more informative if the entire dataset were used instead of just a subset.\"__\n\nThe 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.\n\n__\"Is it possible to achieve the same rate of convergence with shallow neural networks?\"__\n\n__\"“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?\"__\n\nThese 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.\n\n\n[1] Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)\n\n[2] Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011", "claims_and_evidence": "Overall, the paper is well-written, and its claims are clearly stated, well-supported, and their consequences are well discussed. 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.", "methods_and_evaluation_criteria": "The contribution of the article is theoretical and does not rely on empirical evaluation or benchmark datasets. While this provides valuable theoretical insights, the lack of an explicit method for learning the clique structure limits its immediate practical applicability. A discussion on how these theoretical findings could be integrated into practical density estimation frameworks would strengthen the paper.", "theoretical_claims": "I checked the proofs and did not find any glaring mistakes.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Density estimation is a recurring task in machine learning and statistics. This work contributes to the field by establishing dimension-independent convergence rates for structured probability densities.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "1) 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.\n\n2) Figure 3: The visualization would be more informative if the entire dataset were used instead of just a subset.", "questions_for_authors": "1) The theoretical results assume that the clique structure of the probability distribution is given. Could you elaborate on possible approaches for inferring this structure from data?\n\n2) Is it possible to achieve the same rate of convergence with shallow neural networks? \n\n3) 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? If so, how would such a kernel compare to the neural network approach in terms of efficiency and theoretical guarantees?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8hmxzorLUP", "reviewer": "Reviewer_ae2s", "summary": "This paper analyzes density estimation using a neural network under a conditional independence (MRF) assumption and shows that density estimation is possible with a dimension-independent rate under this assumption.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__\"There are no real experiments here.\"__\n\n__\"No real experiments\"__\n\nWe appreciate the reviewer’s concern about the limited empirical validation. While we acknowledge this limitation, we note that:\n* 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.\n* 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.\n* 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.\n\n\n__“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.”__\n\n__“Many of the claims about images having this conditional independence structure are not well-supported.”__\n\n__\"Need much more convincing evidence to support the claim that images have the kind of conditional independence structure assumed.\"__\n\nThis model is extensively well-supported: On line 215 (left) we cite two entire textbooks on the application of Markov random fields to image analysis:\n\n* Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)\n* Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011\n\nOther 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.\n\nWe included the images simply to give the reader an idea of how this model is manifest in real world data.\n\n__“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.”__\n\n__“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.”__\n\n__“I am generally skeptical that the theoretical results are not already known.”__\n\n__\"Explain relationship to prior work much more thoroughly\"__\n\nTo 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. \n\n__“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.”__\n\n__\"Most of the paper needs to be spent on explaining your contribution, not on establishing preliminaries, as is currently the case.\"__\n\nTo 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.”)\n\n__\"No supplementary material\"__\n\nThere are 9 pages of supplementary material in the appendix.", "claims_and_evidence": "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.", "methods_and_evaluation_criteria": "There are no real experiments here.", "theoretical_claims": "The theoretical claims are correct.", "experimental_designs_or_analyses": "No real experiments", "relation_to_broader_scientific_literature": "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.", "essential_references_not_discussed": "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.", "other_strengths_and_weaknesses": "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. Many of the claims about images having this conditional independence structure are not well-supported. I am generally skeptical that the theoretical results are not already known.", "other_comments_or_suggestions": "1) Explain relationship to prior work much more thoroughly\n2) Need much more convincing evidence to support the claim that images have the kind of conditional independence structure assumed.\n3) Most of the paper needs to be spent on explaining your contribution, not on establishing preliminaries, as is currently the case.", "questions_for_authors": "Please look at comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8WsmhwMSmT", "reviewer": "Reviewer_2eJb", "summary": "This paper claims to propose a novel theoretical framework that exploits the data structure using Markov Random Fields (MRFs) to provide a dimension independent converge rate for structured density estimation. It shows that using Markov Random Fields allows capturing local dependency between pixels while considering far-away pixels as nearly independent. It addresses the curse of dimensionality complementary to the manifold hypothesis.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__“It would be useful to provide more explanation to the unfamiliar reader for the four examples of section E.”__ \n\nWe 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.\n\n__“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).”__\n\nWe 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.", "claims_and_evidence": "The paper suggests using power graphs to model possible arbitrary long-range dependencies in the data structure, which is supposed to be more realistic compared to path and grid MRFs that only model extremely local correlations. This is motivated through the computation of correlation between pixel values in CIFAR-10 in Figure 3 and in COCO in Appendix D. \nThe paper proposes convergence rates for ReLU fully connected networks that are applicable to spatial (e.g., images) and sequential data (audio, text), spatiotemporal (e.g., videos), and hierarchical data through the main theoretical result which is the Theorem 4.2.", "methods_and_evaluation_criteria": "This paper is mostly theoretical, the evaluation of the approach compared to path and grid MRFs is qualitative with the correlation plots of Figure 3.", "theoretical_claims": "For ReLU fully connected networks, the paper claims to obtain a convergence rate in $O(n^{-1/(4+r)})$ where $n$ is the number of training samples and $r$ is the size of the largest clique in G, where G is the graph structure associated with the data distribution. This graph G can be obtained using the power graph of the original graph that represents the data structure to capture long-range dependencies. This is compared in the argumentation with $O(n^{-1/(2+d)})$, thus providing a large improvement with $r + 2 \\ll d$. Furthermore, $r$ is claimed to be mostly independent of the data dimension, thus providing Dimension-Independent Rates that alleviate the curse of dimensionality.", "experimental_designs_or_analyses": "Figure 3 shows a scatter plot that motivates the choice of using Markov random fields to model the data distribution, showing that (a) the correlation decreases with the distance and (b) conditioning on a neighboring pixel decreases the correlation. Furthermore, Figure 4 demonstrates the motivation for using Power Graphs instead of standard grid structures to model image distributions.", "relation_to_broader_scientific_literature": "The paper is based on the factorization property for Markov Random Fields Hammersley & Clifford, (1971). This is applied to ReLU neural networks considering Theorem 5 of Schmidt-Hieber, (2017). It also discusses the more general manifold hypothesis (Bengio et al., 2013; Brahma et al., 2016) in section 3.3 and in Appendix E. It would be useful to provide more explanation to the unfamiliar reader for the four examples of section E.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is very well written and provides a comprehensive overview of the field and the problem setup. The contribution is mostly theoretical with the provided convergence rate of Theorem 4.2, and it is then illustrated with numerous examples.", "other_comments_or_suggestions": "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).\n\nI would also suggest defining $n$ in the abstract.", "questions_for_authors": "The theoretical result holds for ReLU Networks. Any insights on how it may generalize (or not) to other spaces of networks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JguNEK0ALW", "reviewer": "Reviewer_SQfd", "summary": "The authors study density estimation for the setting of Markov Random Field (MRF) data where we only have local correlations (cliques). Under these assumptions they study the convergence rate of Neural Networks with their bounds only depend on the range of the correlations. Morally the dimension in convergence bounds can be substituted with the dimension of the effective dimension of the correlation range.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__“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.”__\n\nWe appreciate the reviewer’s concern about the limited empirical validation. While we acknowledge this limitation, we note that:\n* 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.\n* 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.\n* 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.\n\n__“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?”__\n\nThe 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.\n\nMoreover, 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.\n\n__\"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.\"__\n\n__“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.__\n\nA 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] .\n\nOutside 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$.\n\n__“In the abstract who is $d$, it does not appear in the formulas?”__\n\nThis 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.\n\n[1] Pope et al. The intrinsic dimension of images and its impact on learning. ICLR, 2021(in paper)\n\n[2] Carlsson et al. On the Local Behavior of Spaces of Natural Images. International Journal of Computer Vision, 76(1):1–12, January 2008.\n\n[3] Brown et al. The Union of Manifolds Hypothesis, NeurIPS, 2022 (in paper)\n\n[4] Li, S. Z. Markov Random Field Modeling in Image Analysis, 2009 (3000+ citations)\n\n[5] Blake, A., Kohli, P., and Rother, C. Markov random fields for vision and image processing. 2011", "claims_and_evidence": "The claims are supported by evidence.", "methods_and_evaluation_criteria": "Yes, given that this is a theory paper.", "theoretical_claims": "Checked them high level (i.e. skimmed the proof), did not find any major issue.", "experimental_designs_or_analyses": "Experiments seem ok.", "relation_to_broader_scientific_literature": "These results are relevant to the broader", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "Strengths:\n- Well motivated\n- Clearly written\n- From the theory side this is interesting research that can be built on.\n\nWeaknesses:\n- 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.\n- In terms of technical novelty it is not too much. The proofs use mostly standard techniques with the main results leaning on ideas from Schmidt-Hieber 17. ( This is critique solely on the *technical* novelty, considering known techniques in a different setting and carrying out all the computations and proofs does provide value)\n- - 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.", "other_comments_or_suggestions": "- In the abstract who is $d$, it does not appear in the formulas?", "questions_for_authors": "- 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 << 1$)? I am not an expert in that literature but in general most graph problems can be computationally quite expensive.\n- 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviews are mostly positive, and the only negative review has little concrete criticism. Using Neural Networks to learn MRFs is a novel idea, and the paper proves that DNNs can leverage this structure efficiently. I am in favor of accepting this paper.
Decision: Accept (poster)