Dimension-Independent Rates for Structured Neural Density Estimation

Authors: Robert A. Vandermeulen, Wai Ming Tai, Bryon Aragam
Primary area: learning theory
Keywords: density estimation, nonparametric density estimation, graphical model, nonparametric, neural network, deep learning, learning theory, Markov random field, generative model, convergence rate, image processing, curse of dimensionality

Abstract:
We show that deep neural networks achieve dimension-independent rates of convergence for learning structured densities such as those arising in image, audio, video, and text applications. More precisely, we show that neural networks with a simple $L^2$-minimizing loss achieve a rate of $n^{-1/(4+r)}$ in nonparametric density estimation when the underlying density is Markov to a graph whose maximum clique size is at most $r$, and we show that in the aforementioned applications, this size is typically constant, i.e., $r=O(1)$. We then show that the optimal rate in $L^1$ is $n^{-1/(2+r)}$ which, compared to the standard nonparametric rate of $n^{-1/(2+d)}$, shows that the effective dimension of such problems is the size of the largest clique in the Markov random field. These rates are independent of the data's ambient dimension, making them applicable to realistic models of image, sound, video, and text data. Our results provide a novel justification for deep learning's ability to circumvent the curse of dimensionality, demonstrating dimension-independent convergence rates in these contexts.

Decision: reject
Reviewer scores: 5, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1730560611041

thread_type:
official_review

<thread_object>
creator: reviewer_xtr6

<content>
summary:
The authors study the upper bounds of the sample requirements for probability density estimation using deep learning. They establish an upper bound on the $L_1$ error for probability density estimation based on the size of the largest clique in the undirected graph of data, i.e., the Markov random field (MRF). Furthermore, for one-dimensional or two-dimensional array data, the authors present an upper bound on the $L_1$ error, deriving an upper bound on the size of cliques of the data. They also provide proofs for these theoretical results.

strengths:
* To the best of my knowledge, the upper bound on the estimation error for density estimation based on the structure of the undirected graph model is novel. The theoretical results of this study are considered important for understanding the sample requirements of density estimation for high-dimensional data.
* Proofs are provided for these theoretical results, and no major errors have been found.

weaknesses:
#### Major weaknesses:
* The empirical evidence is limited for supporting the author's conclusions regarding the MRF structure of image data. Thus, it is still unclear whether the sample requirements in Corollary 4.5 align with those for image data based solely on the experimental results of this study.
* Additionally, it is desirable to conduct numerical experiments using synthetic data that supports the upper bounds of $L_1$ error for probability density estimation based on the size of the largest clique. 

#### Minor weaknesses:
* Line 016-017: The statement “this size is typically independent of the data dimensionality” is more appropriate than “this size is typically constant, i.e., $r = O(1)$” in the lines, as this study does not focus on cases where the data dimensionality approaches infinity.
* Lines 419-422: A more detailed explanation or definition of $L_{d \times d'}$ and $L^+_{d \times d'}$ would clarify their specific meanings.

questions:
* You suggest that the image data is a MRF such that $L_{d \times d'}$ and $L_{d \times d'}^+$, $L_{d \times d'}^2$, or 
$(L_{d \times d'}^+)^2$ (lines 258-290 and lines 444-451).
     According to Corollary 4.5, this implies that the sample requirement for density estimation of the image data is at most $O(n^{-1/9})$. 
     However, it seems slightly challenging to reliably reach this conclusion solely based on the results presented in Figure 3. Could you provide references to any research that has empirically tested this claim using image data, thereby supporting the upper bound presented in the corollary? Alternatively, are there any experimental methodologies that could confirm this upper bound?
* In lines 1402-1403, which theoretical results or resarch does "However, it is known that no estimator can achieve this rate" refer to?
* The discription in lines 446-451 is confusing. Does it mean that, assuming that CIFAR-10 is a MFR of $(L_{32 \times 32}^+)^2$, the probability density of the images can be estimated with the data sample requirement of $(L_{32 \times 32}^+)^2$, i.e., $n^{-1/9}$ in Corollary 4.5?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730568507038

thread_type:
official_review

<thread_object>
creator: reviewer_eidw

<content>
summary:
The author(s) analyze a general class of densities that are markov to an undirected graph. Under the sense of density estimation, they derive the convergence rate of neural networks. The rate only depends on the effective dimension of the graph, i.e. the maximium clique size r.

strengths:
It's a joy to read the paper. The paper proposed a sound theorem on dimension-free convergence rate, which looks right to me. The paper clearly claimed the assumption for the convergence rate theorem, and justified the assumption and its connection to the real world applications. They put a lot of discussion on the assumption and explain the gap between the assumption.

weaknesses:
Though a lot of discussion on the assumption, the paper lacks the numerical results (example or real world application) to illustrate the convergence rate. As mentioned in line 511, it lacks the proof when the optimal rate happens.

questions:
I'm confused about the figure 3. The author(s) try to claim that the dependency of pixels are reduced given the observations of a neighboring pixel. Can author(s) explain how MRF is applied in this scenario and also provide experiment on the convergence rate with neural networks (better with MRF), in order to justify how MRF helps bypass the curse of dimensionality?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730577945287

thread_type:
official_review

<thread_object>
creator: reviewer_3xmu

<content>
summary:
The paper studies classical density estimation under the assumption that the data has markov random field structure. They show that there exist betwork architectures such that the curse of dimensionality (type $n^{-c/d}$ convergence rates, for $c$ some constant) is overcome by an ERM procedure if the dependency graph structure is sufficiently benign. I.e., if the largest clique is $O(r)$, the effective dimension is $r$ not $d$.

strengths:
* The authors offer an interesting pespective on ambient dimensionality via MRF clique size. 

* Overall I found the paper well-written/structured and easy to follow 

*I believe the results relating clique size to convergence rate are novel

* The paper is well-contextualized (i.e., wrt manifold hypothesis) and written with ample motivation with examples in mind.

* The power graph construction is interesting

weaknesses:
* I am not entirely convinced about dependence (in terms of graph hops, mixing or other related concepts) accurately capturing the hardness of a problem as opposed to support on low-dimensional manifold. See my question Q3 below. 

*Comment:  While I could infer the assumptions of the main theorem from the text preceding it, the assumptions are stated too implicitly for my taste. I think in particular the "markov property with respect to G" should be explicitly defined somewhere in the text (ideally with \cref in thm 4.2 to ease readibility).

questions:
Q1. Is it assumed that p is realizable by the hypothesis class in question in thm 4.2?

Q2. Could you comment on your section modeling CIFAR10 as an MRF. It is not obvious to me from your discussion following Corollary 4.5 that either hop structure is appropriate for modeling the ground truth distribution. Are there known results characterizing the locality of dependence on CIFAR (genuine question --- have very little background on image classification)?

Q3. I am not sure whether the MRF/clique assumption is so different from the manifold hypothesis, and would be interested to hear further comments on this. The example I have in mind is the following (which has both low clique size and low effective dimension --- neither of which actually capture the convergence rate of ERM which actually decreases with $d$). Consider, the Gaussian  autoregression $X_{t+1} = aX_t +W_t$ (say for a fix sequence length $d$) does not just have global dependence between all coordinates $X_t$ but is actually easier to learn for $|a| \geq 1$ (more dependency/no mixing --- see the classical result from Mann&Wald 1943 and note that regression is equivalent to density estimation in KL for this model).  Note also that if $|a| >> 1$ the process is concentrated on the last coordinates, making dimensionality relevant instead. Overall, this kind of begs the question to me what the actual notion of signal-noise actually is in density estimation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730798953958

thread_type:
official_review

<thread_object>
creator: reviewer_zqnm

<content>
summary:
This paper studies learning distributions (ie generative models) under the assumption that the Markov Random Field (MRF) generating the data has no large cliques. [A MRF has an associated graph $G$ which captures the conditional independence stucture of the data $x$: if any path from $i$ to $j$ in G goes through $k$, then $x_i$ and $x_j$ are conditionally indepndent given $k$. Crucially, the distribution p(x) can be written as a product of terms that depend only on $x_S$, where S is a subset of nodes in a clique of G.] The main result (Theorem 4.2) shows that the distribution can be learned in $n$ samples up to TV distance $n^{-1/(4+r)}$ where $r$ is the size of the largest clique in $G$ by ERM over a class of NNs.

This paper provides an alternative viewpoint to the manifold hypothesis for why generative models can perform well without needing a number of samples exponential in the ambient dimension. The authors posit that the MRF assumption may better capture the stucture in the data than the manifold hypothesis when many parts of the data are [conditionally] independent: for example pixels far apart in images, or words far apart in language.

strengths:
- The paper is well-written and very clear, including the proofs. 
- The motivation of wanting to consider structural assumptions that go beyond the manifold hypothesis is sound.
- While the MRF assumption is certainly idealistic, the authors suggest in their conclusion that ultimately these 2 could be viewed in conjunction, since they capture orthogonal types of structure in the data.

weaknesses:
My main concern is the theoretical contibutions are quite weak (and this is a theory paper)/
- The main result shows that Lipshitz MRFs can be learned by ERM over $\prod_{S \in clique(G)} \psi_S(x_S)$ neural networks, where $x_S$ is $x$ restricted to the inputs in the set $S$, and each $\psi_S$ is a neural network, achieving a rate of $n^{-1/(r + 4)}$. However, it is known how to learn such Lipshitz MRFs at a better rate of $n^{-1/(r + 2)}$, with a different (non NN-based) algorithm. While this algorithm may be computationally intractable, ERM over NNs is not necessarily tractable. 
- The proof of the main result (Thrm 4.2) seem to follow closely from results in Schmidt-Hieber 2017 which gives approximation of Liphsitz functions by NNs. I am unaware if there is any significant technical novelty in using this for MRFs.
- The consequences in section 4.3 are all quite trivial.

Discussion of Related work lacking:
- There is no discussion of the literature on learning MRFs. I am not an expert in the area but this is glaringly lacking, and I do wonder if the authors are reinventing the wheel with Theorem 4.8.
- Can the MRF be learned if the graph $G$ is unknown? The authors should discuss the literature here.


In light of some of the discussions with the authors, I am willing to see this paper accepted, though I feel the theoretical result should be better contextualized, including discussion of the following:

(1) Other work on non-parametric density estimation, in particular which avoids the curse of dimensionality. As in the authors' comments, they should explain which are subsumed by the MRF or Manifold hypothesis. 
(2) The difference between this work and the well-studied with MRFs, which typically involves learning the graph structure (though typically with additional parameteric assumptions). 
(3) Why do the authors get a $n^{-1/(r + 4)}$ rate for neural networks? Can NN possibly achieve the $n^{-1/(r + 2)}$ rate, or are they intrinsically limited? Other works (eg. https://arxiv.org/abs/2212.13848) achieve the minimax $n^{-1/(d + 2)}$ rate for learning Lipschitz functions on $R^d$. 

Ultimately, I still feel the theoretical contribution is non-surprising and not-particularly challenging: the paper shows that under the MRF assumption with clique size $r$ --- meaning the density can be written as a product of Lipshitz functions on $r$ coordinates --- density estimation can be done at the $n^{-1/(r + 2)}$ rate, matching the rate for Lipshitz density estimation in $r$ dimensions. If the density function is fit with neural networks, the rate achieved is slightly worse: $n^{-1/(r + 4)}$, while other works (eg. see above) in non-parametric learning with neural-networks do achieve the minimax rate.

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732150125370

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Author Response

comment:
# General Author Response

Many thanks to our reviewers for their thoughtful reviews.

A significant challenge in writing this paper was to present it in a way that bridges theory with applications in deep learning and computer vision, while making both theoretical and applied perspectives accessible and convincing to the other side. We were pleased to see from the positive reviews that we were largely successful in this regard, as evidenced by comments such as:

* Zqnm: “The paper is well-written and very clear, including the proofs.”
* Zqnm: “The motivation of wanting to consider structural assumptions that go beyond the manifold hypothesis is sound.”
* 3xmu: “The authors offer an interesting pespective on ambient dimensionality via MRF clique size.”
* 3xmu: “Overall I found the paper well-written/structured and easy to follow”
* 3xmu: “The paper is well-contextualized (i.e., wrt manifold hypothesis) and written with ample motivation with examples in mind.”
* eiDw: “It's a joy to read the paper.”
* Xtr6: “The theoretical results of this study are considered important for understanding the sample requirements of density estimation for high-dimensional data.”



Overall, only two concerns were raised by multiple reviewers: the lack of experiments and the validity of using a Markov random field (MRF) to model images. We address other issues in individual reviewer rebuttals.
## Lack of Experiments

__eiDw: ”Though a lot of discussion on the assumption, the paper lacks the numerical results (example or real world application) to illustrate the convergence rate.”__

__Xtr6: “Additionally, it is desirable to conduct numerical experiments using synthetic data that supports the upper bounds of error for probability density estimation based on the size of the largest clique.”__

We appreciate the reviewers' concern about the limited empirical validation. While we acknowledge this limitation, we note that:

* The paper's primary contribution is theoretical: Proving rigorously that neural networks can achieve dimension-independent rates in density estimation under commonly accepted assumptions. This provides yet another compelling justification for using DNNs in practice.

* More generally, our results establish fundamental bounds on learning distributions with MRF structure. In this sense our contributions are twofold: 1) We establish a general statistical framework for learning high-dimensional distributions with dimension-independent rates, and 2) We provide evidence (i.e. proofs) and intuition that neural networks are part of this framework and also achieve dimension-independent rates. 

* The local dependency structure we identify is already implicitly leveraged in successful practical methods, particularly in patch-based approaches to anomaly detection such as SoftPatch (NeurIPS 2022). These existing empirical successes provide indirect validation of our theoretical framework.


* 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.

 

## Validity of the MRF model

__3xmu: “I am not entirely convinced about dependence (in terms of graph hops, mixing or other related concepts) accurately capturing the hardness of a problem as opposed to support on low-dimensional manifold...”__

__Xtr6L: “The empirical evidence is limited for supporting the author's conclusions regarding the MRF structure of image data.”__

This concern was posed quite differently by the reviewers, so a detailed response will be included in the individual responses. We acknowledge that our evidence does not definitively confirm the MRF model—indeed, it is unlikely to be perfectly satisfied. However, many behaviors one would expect from the MRF model do hold, supporting it as a useful and novel framework for understanding image statistics. Moreover, there is extensive precedent for modeling images as MRFs in the image processing literature—this approach is so well-established that there are entire textbooks [1,2,3] ([1] has over 3,000 citations) and numerous highly-cited papers on the subject (e.g., [4] with 500+ citations and [5] with 900+ citations), further validating the reasonableness of our MRF-based approach to image modeling.

[1] Markov random field modeling in image analysis. Li 2009

[2] Markov Random Fields for Vision and Image Processing. Blake et al. 2011

[3] Markov Random Fields in Image Segmentation. Kato 2012

[4} Markov Random Field Image Models and Their Applications to Computer Vision. German and Graffigne 1986

[5] Combining markov random fields and convolutional neural networks for image synthesis. Li and Wand 2016
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors studied learning distributions where the data is generated by a Markov Random Field (MRF) with a clique assumption. The condition is considered as an alternative to the manifold hypothesis, where a significantly improved rate of density estimation can be achieved. 

Although the average score appears high, after reading into the discussions of reviewer Zqnm, and starting a further brief discussion with reviewers leading to a willingness to reduce their score by 3 points, this paper is far closer to borderline than the scores currently indicates. 

One of the main criticism is on the tightness of the rates of -1/(r+4), which compares against the known minimax rates of a complete MRF of -1/(r+2). There are additional concerns regarding the novelty of the techniques beyond existing work, the complexity of learning the MRF, and a lack of comparison versus existing rates. 

Although none of these issues are critical on its own, but if we put these all together, there are quite a bit of doubt on whether the contributions are sufficient. I believe there is still room for this paper to be improved, and addressing some of these concerns can push this paper easily over the borderline. Therefore at this point, I will recommend reject.