The concept is beautiful, but I am curious how the authors come up with the definition. Is there is any clear intuition to define it, or the authors start from the proof of the density estimation rate and then identify this key quantity?

At a high level, a disintegration outlines a method to estimate a density by inductively conditioning out the entries of a random vector. For instance, consider a random vector $[X_1,X_2]$. The disintegration $(X_1)-(X_2) \Rightarrow (X_1) \Rightarrow \emptyset$ corresponds to first estimating a histogram for $X_2$, and then, for each bin $b$ of the $X_2$ histogram, estimating a histogram for $X_1|X_2 \in b$. The resilience of a graph simply characterizes the shortest disintegration, i.e. the most efficient decomposition of a distribution into factors.

Removing one vertex from each component of a graph captures the idea that, after sufficient conditioning, these components become independent. This allows us to avoid estimating the high-dimensional joint density of all vertices in the graph. Instead, we can estimate the low-dimensional components individually and take their product. It's worth noting that for densities, we have the inequality: $\Vert\prod_{i=1}^d p_i - \prod_{j=1}^d q_j \Vert_1 \le \sum_{i=1}^d \Vert p_i - q_i \Vert_1$

Given an arbitrary graph, is there any concrete computational algorithm to calculate the exact resilience? If so, what’s the computational cost? I suppose the exact calculation is very expensive, that’s why the authors focused more on how to bound it.

We emphasize that it is not necessary to actually compute the exact resilience in order to benefit from it, which is one of the central aspects of this type of theory. The sample complexity is characterized by the resilience, whether or not it can be computed explicitly!

Moreover, the reviewer is correct that in general, it is easier to bound the resilience than it is to calculate it exactly. Of course, any disintegration leads to an upper bound on r(G). The fact any nontrivial upper bound (i.e. $r(G) < d$) leads to an improvement justifies focusing on upper bounds. Of course, it is an interesting future direction to explore algorithms for its computation.

Can the authors discuss some possible extensions? For example, what does the resilience look like for directed graphs, or for non-Markovian graphs?

This is a good question! It is not clear if the same notion of graph disintegration captures the sample complexity of density estimation in other types of graphs, but we will certainly mention this as a future direction in the discussion section.

”It would have been helpful to provide a proof-sketch of the main theorems in the main text…”

We are happy to incorporate this into the final draft.

”It would have also been useful to provide some simulation results on synthetic data as this would have helped empirically validate the theoretical results.”

”What is the running time of the algorithm w.r.t n, d and r?”

Please see the General Author Response.

”The density is assumed to be Lipschitz for the analysis, but can the results be extended to handle higher order smoothness (s times continuous differentiability)?”

This would involve modifying certain parts of the analysis, but we suspect that this is possible by using standard results on nonparametric estimation in function classes with higher order smoothness (say, Holder or Sobolev). We chose to stick with Lipschitz for two reasons: 1) Lipschitz is weaker than assuming higher-order smoothness, and 2) We want to keep the focus on the novel dimensional aspects of the problem through the Markov property and graph resilience.

”Can something be said about the optimality of the bounds? In particular, is the graph resilience the right quantity for this problem?"

As far as characterizing sample complexity in terms of resilience and dimension, for all dimensions $d$ and graph resilience $r$, we know that our rates cannot be improved.

We do know that there exists at least one class of distributions where the rate of convergence can be improved. For any Markov random fields with a tree graph, one can achieve an $L^1$ rate of convergence of $n^{-1/4}$, asymptotically. This corresponds to an effective dimension of $2$ and there exist trees where our results do not achieve this rate of convergence. On the other hand, our results are uniform rather than asymptotic, so it is possible that our results are optimal when considering uniform deviation bounds.

”In Corollary 4.12, why not show the dependence on t explicitly in the bound?”

We can include $t$ in Corollaries 4.12 and 4.14 in the final draft. The new rates will be $O(t\log(d))$ and $O(t^2 \sqrt{d})$ respectively.

“The only claim that I consider not well supported is related to lines 160-161, more concretely to the lower dimensional manifold. In order to support this claim, the authors should prove this claim by finding an example where the resilience r is lower than the dimension d and that cannot be mapped into a lower dimensional manifold.”

”However, the structure in the data is, by itself, a correlation measure, and therefore, it is not surprising that it reduces the effect of the curse of dimensionality.”

The way in which we are utilizing Markov random fields (MRFs) is novel and we agree that elaborating on this a bit is a good idea.

A simple example of this can be found with the empty graph with $d$ vertices and no edges, which has resilience 1. In this case all of the entries of a random vector $X = (X_1,\ldots,X_d)$ must be independent and thus its density must have the form $p(x_1,\ldots, x_d) = p_1(x_1)p_2(x_2) \cdots p_d(x_d)$. Thus the support of $p$, $\operatorname{supp}(p)$, is equal to $\operatorname{supp}(p_1) \times \cdots \times \operatorname{supp}(p_d)$ which is then a $d$-dimensional volume and hence has no low-dimensional structure whatsoever.

As another example we might consider the $d=2$ case where $p_1$ and $p_2$ are densities that don't concentrate near a single point, e.g., they are both uniformly distributed on $[0,1]$. In order for $X_1$ and $X_2$ to lie near a 1-dimensional manifold, then $X_1$ and $X_2$ must be strongly dependent and the MRF must have two vertices with an edge between them. Thus, in this case, the resilience is 2 but the manifold dimension is 1.

It's worth noting that a density's graph isn't unique. The complete graph, from which one can not conclude anything regarding independence structure or a density, applies to every density. The lack of edges between vertices in a Markov random field is what conveys information about a density, but removing edges tends to imply that the support of a density is filling more space.

”Are you willing to provide a code that allows to use your findings in practical data?”

”No practical applications are shown.”

Please see the General Author Response.

”The paper is not clearly written and in a way that only specialists in the field of graph modelling can understand. The relationship with classical methods like kernel density estimation is not clear.”

Kernel density estimators, along with histograms, can achieve the minimax optimal $n^{-1/(2+d)}$ rate of convergence for Lipschitz continuous densities. An important point about kernel density estimation is that it does not adapt well to graphical structure and thus suffer from the curse of dimensionality, which is an important part of our motivation. We will include this point in our paper. Please let us know if there is some other comparison you would like to see.