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

”...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?

”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 agree that our evidence does not definitively justify the MRF model. In fact, natural image data likely doesn't perfectly satisfy the MRF assumption. Nonetheless, our evidence strongly suggests that something close to the MRF model holds, and there is extensive precedent for modeling images as MRFs in the image processing literature—please see the "General Author Response". We believe the theoretical conclusions of this work are most novel and striking in this context. Regarding additional experiments, please see the "General Author Response".

”In lines 1402-1403, which theoretical results or resarch does ‘However, it is known that no estimator can achieve this rate’ refer to?”

This refers to the classical nonparametric rate for estimating Lipschitz continuous densities. These rates are well-known for the $L^2$ risk (e.g. [1-2] below); for the case of the $L^1$ risk corresponding results can be found in [3-4].

[1] Charles J Stone. Optimal rates of convergence for nonparametric estimators. The Annals of Statistics, 8(6):1348–1360, 1980.

[2] A.B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics, New York, 2009.

[3] Theorem 1, L. Devroye and L. Gyorfi. Nonparametric Density Estimation: The L1 View. Wiley Interscience Series in Discrete Mathematics. Wiley, 1985.

[4] Theorem 6.3.8, Evarist Giné and Richard Nickl. Mathematical foundations of infinite-dimensional statistical models. Number 40. Cambridge University Press, 2016.

”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?“

You are correct. We will re-word this to be more clear.

We will be sure to incorporate your suggestions in "minor 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.”

Please see the “General Author Response” regarding experiments.

”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?”

Figure 3 supports our argument that a grid MRF $(L_{w,h})^k$ reasonably models CIFAR images by demonstrating two key consequences of the MRF assumption:

• As pixels become more spatially distant, their dependence weakens (confirmed in the top row of Figure 3).
• Two pixels $a$ and $b$ should be independent when conditioned on pixels surrounding $a$ (depending on $k$). The intuition is that $a$ should contain no more information about $b$ than the collection of pixels surrounding $a$. Since testing this directly is challenging, we made two simplifications:
  1. We condition on just one adjacent pixel $a'$ rather than all surrounding pixels, testing if this neighboring pixel captures most of the information in $a$.
  2. We fix $a'$ to a specific value rather than testing independence across all values

Even with simplification 1, we observe that conditioning strongly reduces the dependence between $a$ and $b$, supporting our claim of strong local dependence and weak distant dependence.

We do not claim this definitively confirms the MRF model—indeed, it is unlikely to be perfectly satisfied. However, our findings support MRFs as a useful framework for understanding image statistics. Please see our "General Author Response" for more on the MRF assumption, particularly its widespread acceptance in the image processing community.

”I am not entirely convinced about dependence... accurately capturing the hardness of a problem as opposed to support on low-dimensional manifold”

”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$)...”

Thanks for the intriguing reference and example; it will be useful to keep in mind going forward.

To begin, we emphasize that the MRF assumption provides a view of high-dimensional data that is, in some sense, orthogonal to the manifold hypothesis. Keeping in mind that MRF assumption corresponds to the Markov graph not being complete (some edges missing), and we can demonstrate all four possible combinations of MRF/manifold hypothesis satisfaction in 2D, where the MRF assumption reduces to X and Y being independent:

• MRF true, MH true: $X \sim \text{unif}[0,1]$, $Y \sim \text{unif}[0,0.01]$,$X$ and $Y$ independent (your example: density concentrated in coordinate-aligned subspace)
• MRF true, MH false: $X,Y \sim \text{unif}[0,1]$, $X$ and $Y$ independent (density not concentrated)
• MRF false, MH true: $X \sim \text{unif}[0,1]$, $X=Y$
• MRF false, MH false: $X,Y \sim N(0,1)$, weakly correlated

This generalizes to higher dimensions with more complex graphs, where the manifold hypothesis satisfaction becomes a matter of intrinsic dimension rather than binary. Regarding images, our experiments (Figure 3, and Appendix F for COCO) show that distant pixels are weakly correlated, with correlation essentially vanishing when conditioned on nearby pixels (noting that higher resolution images require greater pixel separation). While some theoretical work exists on using conditional independence to improve nonparametric density estimation [1], theoretically justifying this for MRFs in the context of images is novel.

Please also see our “General Author Response.”

”Is it assumed that p is realizable by the hypothesis class in question in thm 4.2?”

No; p need only satisfy Lipschitz continuity, positivity, the MRF assumption, and have compact support. From a learning theory perspective, the hypothesis class grows with $n$ (increasing width, depth, etc.). For any fixed $n$, the hypothesis space consists of a single neural network architecture over all possible parameter values. As $n$ increases, the network grows, yielding a richer hypothesis space. More formally, this is a sieve estimator approximating the class of Lipschitz densities.

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

It would be helpful if you could elaborate a bit. We can see many possible ways to interpret your question, including:

• Is the general concept of modeling natural images as an MRF reasonable?
• Is CIFAR-10 specifically is reasonably modeled as an MRF?
• Is the specific MRF in Cor 4.5 appropriate (maybe a larger exponent)?
• Are local patches of images actually highly dependent.

We provide a general response that should address your concerns. Please also see our "General Author Response" regarding the extensive foundation for MRF-based image modeling in the image processing literature.

There is substantial work characterizing the structure of $m\times m$ image patches in natural images. For instance, "Emergence of simple-cell receptive field properties by learning a sparse code for natural images" (Nature 1996) found these regions have "sparse representations" in appropriate bases. As we noted:

Further supporting this hypothesis, Carlsson et al. (2008) discovered that the set of $3\times × 3$ pixel patches from natural images concentrates around a 2-dimensional manifold.

These patches typically correspond to oriented edges or textures—features that neural networks learn to detect (see Figure 3 the NeurIPS 2012 AlexNet paper). The key insight is the limited degrees of freedom: within an image patch, a small collection of pixels largely determines the remainder, indicating strong dependence. While this geometric perspective is well-studied, we're unaware of probabilistic or information-theoretic approaches testing this. Our Figure 3 demonstrates pixel decorrelation with distance (especially when conditioned on nearby pixels). While we know of no prior work explicitly investigating this phenomenon, it would likely be unsurprising to the image processing community. We can provide correlation heatmaps if helpful. Regarding CIFAR-10's specific dependence structure or rigorous justification for the exponent 2 in Corollary 4.5, we know of no targeted studies—most work addresses natural images broadly.

[1] Nonparametric estimation of component distributions in a multivariate mixture. Hall and Zhou, 2003

”My main concern is the theoretical contibutions are quite weak”

”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 main technical novelty lies in (a) avoiding Lipschitz assumptions on the potentials, (b) a nontrivial analysis of the covering numbers for families of MRF densities that delivers dimension-independent rates. Regarding (a), while the analysis would be quite trivial if one simply assumes that the clique potentials in $p = \prod_{V'} \psi_{V'}$ are all Lipschitz continuous, proceeding with only the assumption that $p$ is Lipschitz is more challenging. (Note that in practice the clique potentials are unknown and untestable, so it would be artificial to impose assumptions on them.)

We believe that this analysis, combined with the practical connection of MRFs to high-dimensional data such as images, is novel and significant to the deep learning (and hence ICLR) community—a point with which the other reviewers seem to agree.

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

The comments regarding nonparametric MRF learning are well-taken. While we are not aware of any results on density estimation as in Theorem 4.8, there is relevant literature we should discuss, including results on structure learning in special cases such as nonparanormal graphical models and general non-Gaussian models. We will incorporate this discussion in a revision.

Notably, none of these results cover density estimation and more importantly do not establish dimension-independent rates. Another notable feature of our results is the use of neural networks, which is more relevant in contemporary applications.

Nonparanormal

Regularized rank-based estimation of high-dimensional nonparanormal graphical models. Xue and Zou, 2013

High Dimensional Semiparametric Gaussian Copula Graphical Models. Liu et al., 2012

Sparse Nonparametric Graphical Models. Lafferty et al., 2013

The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs. Liu et al., 2009

Non-Gaussian

High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence. Ravikumar et al., 2008

Learning non-Gaussian graphical models via Hessian scores and triangular transport. Baptista et al., 2023

Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks. Zheng et al., 2023