Breaking the curse of dimensionality in structured density estimation

Authors: robert a vandermeulen
wai ming tai
bryon  aragam
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 21:34:54

Abstract: We consider the problem of estimating a structured multivariate density, subject to Markov conditions implied by an undirected graph. In the worst case, without Markovian assumptions, this problem suffers from the curse of dimensionality. Our main result shows how the curse of dimensionality can be avoided or greatly alleviated under the Markov property, and applies to arbitrary graphs. While existing results along these lines focus on sparsity or manifold assumptions, we introduce a new graphical quantity called ``graph resilience'' and show that it dictates the optimal sample complexity. Surprisingly, although one might expect the sample complexity of this problem to scale with local graph parameters such as the degree, this turns out not to be the case. Through explicit examples, we compute uniform deviation bounds and illustrate how the curse of dimensionality in density estimation can thus be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data.

Main paper: 
 introduction: 
 Density estimation is a classical problem in statistical machine learning, and provides the backbone of modern generative models such as diffusion models, which are now state-of-the-art density estimators for a variety of applications, as well as normalizing flows, energy-based models, and implicit generative models. At the same time, density estimation is a notoriously difficult problem in high-dimensions, known to suffer from the so-called curse of dimensionality. When the density depends on only a few variables or, more generally, is supported on a low-dimensional manifold, it is known that the curse of dimensionality can be circumvented by substituting the ambient dimension d with the effective dimension s (e.g. Lafferty and Wasserman, 2008; Yang and Tokdar, 2015) . But what happens when the distribution is spread over the entire space in a structured manner-is it still possible to circumvent the curse of dimensionality?Three representative examples are given in Figure 1 , corresponding to sequential, hierarchical, and spatial (or convolutional) data. In these examples, although both manifold and sparsity assumptions are violated, there are structured dependencies that one might hope to leverage when estimating the underlying density. These kinds of structures are pervasive in machine learning applications. For one example, consider computer vision and imaging. Images have long been modeled as a grid graph where adjacent pixels correspond to adjacent vertices (see Keener (2010) , for example). Such an assumption is very natural: pixels tend to be strongly dependent on nearby pixels and independent of far away pixels. See Figure 2 for an example of this.These examples are particularly appealing in applications, however, we emphasize that our problem setting is considerably more general, and applies to general dependence structures given by any Path (sequential data) Graph resilience: r = O(log d)Samples: n ≳ (1/ε) O(log d) Tree (hierarchical data) Graph resilience: r = O(1)Samples: n ≳ (1/ε) O(1) Grid (spatial data) Graph resilience: r = o(d)Samples: n ≳ (1/ε) o(d)Figure 1 : Examples of common structures that yield improvements in density estimation. As indicated by the path example on the left, which is also a tree, the worst-case resilience of any tree is r = O(log d), but for bounded-depth trees, r = O(1).Markov random field. Since real data is expected to (approximately) exhibit these types of structures, a reasonable question to ask is whether or not the curse of dimensionality persists in such structured settings.To formalize the notion of structured dependencies in a highdimensional, multivariate distribution, we adopt the framework of undirected graphical models, also known as Markov random fields (MRFs). In this setting, we are given samples from an unknown distribution P , with density p, over the random vector X = (X 1 , . . . , X d ), and it is assumed that P is Markov to some undirected graph G (see Section 3.1 for definitions). We treat both cases where G is a priori known, and where it is unknown but is in some known subset of all graphs. The graph G encodes the underlying dependence structure between the variables, which we hope simplifies the estimation problem. For example, when P is a Gaussian, this gives rise to the well-known Gaussian graphical model (Speed and Kiiveri, 1986) , and various extensions of this idea to nonparametric settings are known, including trees (Liu et al., 2011; Györfi et al., 2022) and nonparanormal models (Liu et al., 2009) . While this line of work also discusses the problem of structure learning, our focus is on the problem of nonparametric density estimation, which is comparatively understudied in graphical models. This may come as a surprise given the outsized literature on the general density estimation problem; see Section 2 for an overview of related work. In contrast to most existing work on density estimation, in lieu of imposing parametric or functional restrictions on P , the only assumption we make in addition to the Markov assumption is Lipschitz continuity.Overview Our main result establishes the sample complexity of estimating such a density-for arbitrary graphs G-in total variation (TV) distance: It is approximately (1/ε) r+2 , where r ≪ d is a novel graphical parameter we call graph resilience that depends only on G. Roughly, r is a measure of how connected the graph G is; the easier it is to disconnect G, the smaller r will be. The examples in Figure 1 illustrate a range of values from constant r = O(1) to sublinear r = O(√ d) = o(d).In the former case, this leads to an exponential improvement in the sample complexity over the usual nonparametric sample complexity of (1/ε) d . While it is not surprising that graphical structure (i.e. sparsity in the form of conditional independence) can make estimation easier, what is surprising is the quantity involved: It is not, as one might guess, one of the "usual" suspects such as sparsity, degree, or width. To capture the effective dimension of the problem and its resulting sample complexity, we introduce the concept of graph resilience. In particular, the usual suspects are insufficient to break the curse of dimensionality, whereas graph resilience does. Moreover, it is easy to construct examples where these are not only insufficient, but wholly misleading: Graph resilience can be controlled in graphs with unbounded degree, sparsity, and/or diameter.Our work also marks a substantial departure from the existing literature that focuses primarily on functional restrictions (e.g. compositional structure), sparsity (e.g. density regression), or lowdimensional embeddings (e.g. manifold hypothesis). Instead, we impose no explicit restrictions on the functional form (although certain restrictions are implicit through the Markov assumption). In practice, empirical evidence points to a combination of these properties prevailing in real-world data, Figure 2 : Heatmaps of the magnitude of the correlation between red pixel and every other pixel, using the CIFAR-10 training set. The left image shows the correlation without conditioning, the right image shows correlation conditioned on the green pixels. We see that the modeling the image as a Markov random grid is valid. and thus our approach hopefully serves to provide another practical assumption under which density estimation is feasible, and in particular, the curse of dimensionality can be avoided.Contributions More precisely, we make the following contributions.1. (Section 3.2) We introduce the graphical property of resilience (Definition 3.2), which approximately quantifies the connectivity of an undirected graph. Resilience is defined through the process of disintegration (Definition 3.1), which is described in detail. 2. (Section 3) We prove that the sample complexity of estimating a density p that is Markov to any undirected graph G scales with the resilience r = r(G), as opposed to the dimension d (Theorem 3.1). We also provide examples to show that other metrics such as degree, diameter, and sparsity cannot properly capture the sample complexity (Section 4.3). We also show that efficient estimation is still possible even if G is unknown (Theorem 3.2). 3. (Section 4) We demonstrate numerous concrete examples where the resilience (and hence the sample complexity) can either be exactly calculated or bounded. These examples include familiar graphs such as trees (including paths for sequential data), cliques, and grids (also known as lattice graphs), and represent a broad continuum of possible complexities (Section 4.2).All told, the potential savings implied by our results can be substantial, and are not isolated or pathological in any way: If there is a single independence relation satisfied by P , the effective dimension will be strictly less than the ambient dimension d, and in practical applications such as spatial or imaging data, there is an exponential savings in the sample complexity (see Figure 1 ). As we show, the graph resilience reveals a continuum of complexities ranging from dimensionindependent (i.e. r = O(1)), in which case the curse of dimensionality is circumvented completely, to dimension-dependent with nontrivial savings (e.g. r = o(d)). 
related work: 
 We begin by recalling classical rates and results on density estimation. The standard nonparametric rate for estimating an L-Lipschitz density p in d dimensions in TV distance is n -1/(d+2) ; see Devroye and Gyorfi (1985) ; Tsybakov (2009) ; Giné and Nickl (2015) for more details. This rate ignores dimension-dependent constants that affect finite-sample rates, and a more refined bound on the sample complexity (ignoring log-factors) is given in McDonald (2017) :n ≳ d d ε d+2 .(1)See also Ghorbani et al. (2020) ; Jiao et al. (2023) . For comparison, our main result is that onlyn ≳ rd r/2+1 ε r+2 (2)samples are needed (again up to log-factors) when p is Markov to an undirected graph G with resilience r = r(G), and this rate cannot be improved among graphs whose resilience is at most r. The improvement over (1) is clear: Not only the exponent, which dominates the rate, but also the constant is improved by replacing d with r, which can be much smaller than d (see examples in Section 4.2).Ignoring the dimension-dependent constant factor (as most papers do), the basic idea behind most results on circumventing the curse of dimensionality is to replace the d-dependence in the exponent of (1) with some s < d, where s is the effective dimension of the problem. Examples include sparsity, low-dimensional embeddings (e.g. manifold assumptions), and hierarchical and/or compositional structure. Viewed from this perspective, our main contribution is to propose a new measure of effective dimension in structured data, where s = r is the graph resilience.Recently, there has been a renewed interest in this problem along two broad axes: 1) Generative models as density estimators, and 2) Breaking the curse of dimensionality. In the remainder of this section, we review this related work.As noted in the introduction, density estimation is a classical problem with a literature dating back more than 50 years. Notably, Stone (1980 Stone ( , 1982) ) established minimax rates for nonparametric estimation problems including density estimation and regression. These papers derived the now-classical nonparametric rate n -β/(2β+d) for β-smooth densities, which implies the curse of dimensionality, i.e. unless p is very smooth, then the sample complexity of estimating p is exponential in the dimension. Yet, at the same time, the stark practical success of generative models suggest that high-dimensional density estimation may not be quite as intractable as this slow rate suggests. Motivated by these empirical observations, a growing line of work has established minimax optimality for a range of generative models, including GANs (Liang, 2017; Singh et al., 2018; Singh and Póczos, 2018; Uppal et al., 2019 Uppal et al., , 2020)) , diffusion models (Oko et al., 2023; Zhang et al., 2024; Cole and Lu, 2024; Tang and Yang, 2024) , and variational autoencoders (Tang and Yang, 2021; Kwon and Chae, 2024) .Other theoretical developments have focused on efficient algorithms (Acharya et al., 2021 (Acharya et al., , 2017;; Chan et al., 2014) in the univariate case.There has also been recent interest in developing density estimators that exploit graphical structure (Germain et al., 2015; Johnson et al., 2016; Khemakhem et al., 2021; Wehenkel and Louppe, 2021; Chen et al., 2024) . Of course, there is an enormous literature on algorithms and methods for general density estimation that we cannot cover here.Most closely related to our work are the papers Liu et al. (2007 Liu et al. ( , 2011)) ; Györfi et al. (2022) . Liu et al. (2007) use the RODEO estimator on a model that satisfies a sparsity assumption, i.e. only s ≪ d variables are involved in the nonparametric component. Liu et al. (2011) use forests to approximate the underlying density under certain regularity conditions; Györfi et al. (2022) relax these conditions and replace forests with trees. Their main result is a pointwise O(n -1/4 ) rate of convergence for estimating a tree-structured density, which is notably dimension-independent. The main difference between our results and these previous results is that our results apply to general graphs G that may not be trees or forests, in addition to being uniform in p and unimprovable (cf. Remark 1 in Györfi et al., 2022, in particular) . Most importantly, moving beyond tree-based models requires new ideas, and motivates our introduction of the graph resilience to measure the effective dimension of the estimation problem.After the initial posting of our paper, we were made aware of the related work by Bos and Schmidt-Hieber (2023) which proposes a supervised approach to density estimation that also leverages the Markov assumption to break the curse of dimensionality in density estimation.There is a long line of literature on understanding how and when the curse of dimensionality can be avoided. Common assumptions include the manifold assumption (Pelletier, 2005; Ozakin and Gray, 2009; Jiang, 2017; Schmidt-Hieber, 2019; Nakada and Imaizumi, 2020; Berenfeld et al., 2022; Jiao et al., 2023) , additive structure (Stone, 1985; Raskutti et al., 2012), compositional structure (Horowitz and Mammen, 2007; Juditsky et al., 2009; Kohler and Krzyżak, 2017; Schmidt-Hieber, 2017; Bauer and Kohler, 2019; Kohler and Langer, 2021; Shen et al., 2021) , low-rank structure (Hall and Zhou, 2003; Hall et al., 2005; Song and Dai, 2013; Amiridi et al., 2022a,b; Vandermeulen and Ledent, 2021; Vandermeulen, 2023) and sparsity (Liu et al., 2007; Lafferty and Wasserman, 2008; Yang and Tokdar, 2015) . Bach (2017) showed that neural networks are adaptive to many of these underlying structures.This line of work is particularly relevant as it pertains to breaking the curse of dimensionality via structural assumptions on the unknown parameter. Notably, it seems that the advantages of (in)dependence via the Markov property have not been thoroughly investigated. Our work aims to fill this gap for a wide range of structured models that do not fit into any of the classes above. Indeed, it is easy to construct densities that are non-sparse (i.e. every variable is active), non-additive and non-compositional (we consider arbitrary continuous densities), and are not supported on any lower-dimensional manifold, but that are Markov to a given graph G. 
main results: 
 Before presenting the main results of this paper we must present some basic background.Throughout the paper, we use undirected graphs to model the dependencies in P . We adopt the usual terminology and conventions from graphical models:G = (V, E) is an undirected graph with V = X = [d] and d = dim(X).To avoid technical complications, we assume compact support withEQUATIONwhere ⊥ ⊥ P denotes conditional independence in P . In other words, graph separation implies conditional independence, but not necessarily vice versa. See Lauritzen (1996) for a review of graphical modeling terminology.We term a subgraph of G to be a component ofG (sometimes called a connected component) if it is a maximal connected subgraph of G. A path in G is a sequence of vertices (v 0 , v 1 , . . . , v k ) such that v i -v i+1 in G (i.e. (i, i + 1) ∈ E).A simple path is a path without repeated vertices. The length of a path is the number of edges in the path; e.g. the length of (v 0 , v 1 , . . . , v k ) is k. A geodesic path between two vertices is any path of shortest length, and the distance between two vertices is the length of any geodesic between them. For graphs G, G ′ the notation G ⊕ G ′ denotes a disjoint union of graphs, i.e., the graph whose vertex set is the disjoint union of the vertices in G and G ′ and inherits edges from the edges in G andG ′ . For a graph G = (V, E), for V ′ ⊂ V , the graph G \ V ′ denotes the graph with vertices V \ V ′ and the edges {i, j} ∈ E where {i, j} ⊆ V \ V ′ .For When estimating these densities we will sometimes use the term sample complexity. This refers to the number of samples necessary to estimate a density to within ε error in total variation distance. For functions, f on [0, 1] d we define ∥f ∥ 1 = |f (x)|dx; this is the total variation distance.The key concept in this work, which characterizes the difficulty of estimating densities in D(G), is what we term the graph resilience of G. Graph resilience is based on a process we call a disintegration. In each step of the disintegration, one vertex is removed from every graph component. The total number of steps to the null graph is 3.Definition 3.1. For a graph G = (V, E), an r-tuple (V 1 , . . . , V r ) with V i ⊆ V is called a disintegra- tion of G if: 1. {V i } i is a partition of V ; 2. The elements of V 1 all lie in different components of G; 3. |V 1 | is equal to the number of components in G; 4. For all i ∈ [r -1] the elements of V i+1 lie in different components of G \ i j=1 V j ; 5. |V i+1 | is equal to the number of components in G \ i j=1 V j .The length of a disintegration is the value r in the above definition. A disintegration of length r will be called an r-disintegration.The first disintegration step, V 1 above, can be thought of as the process of picking one vertex from each component in G and removing it. The next step of a disintegration, V 2 above, then selects and removes one vertex from each component of the resultant graph. An r-disintegration is a sequence of r such steps until one is left with the null graph. It is possible for a graph to admit many different disintegrations of different lengths. A visual representation of the steps of a graph disintegration can be found in Figure 3 .The resilience of a graph G describes the length of the shortest possible disintegration of G.Definition 3.2. For a graph G, the resilience of G, denoted r(G), is the smallest r such that there exists a r-disintegration of G.We elaborate more on some properties of graph resilience in Section 4, including upper bounds for the graph resilience of several graphs corresponding to image or sequence data. First, we need to establish that graph resilience is the right metric for quantifying the sample complexity of density estimation.The following theorem characterizes the difficulty of estimating a density which is known to satisfy the Markov property in terms of its graph. All proofs are deferred the appendix.Theorem 3.1. Let G be a (known) graph whose number of vertices is d and resilience is r. Let L ≥ 0. For any 0 < ε < 1, there exists an algorithm that takesn = Ω rd r/2+1 L r ε r+2 log( dL ε ) + log(1/δ) ε 2 i.i.d.samples drawn from any p ∈ D L (G) and returns a distribution q such that ∥p -q∥ 1 ≤ ε with probability at least 1 -δ 3 .This corresponds to a convergence rate of O(n -1/(r+2) ) and is uniform over D L (G). For comparison, the rate O(n -1/(d+2) ) is known to be optimal for estimating densities in D d,L in the total variation norm (e.g. Beirlant and Gyorfi, 1998) . Consequently the rate O(n -1/(r+2) ) indicates that the rate of convergence when estimating densities in D L (G) is akin to estimating densities in D r,L . We will see in Section 4.2 that, for graphs typically used to represent audio or image data, the effective dimension for estimating densities can be drastically, even exponentially, smaller than the ambient dimension.While it may be reasonable to assume a known graph in some situations, one often encounters the situation where the graph is unknown. If one assumes that the graph G is unknown, but that G lies in some subset of graphs whose maximum graph resilience is bounded above by some value r then it is still possible to achieve a rate of O(n -1/(r+2) ). Theorem 3.2. Let G be the set of all graphs whose number of vertices is d and resilience is r. Let L ≥ 0. For any 0 < ε < 1, there exists an algorithm that takesn = Ω rd r/2+1 L r ε r+2 log( dL ε ) + log(1/δ) ε 2i.i.d. samples drawn from any p ∈ G∈G D L (G) and returns a distribution q such that ∥p -q∥ 1 ≤ ε with probability at least 1 -δ 3 .We show in Appendix D that these rates are optimal (up to a polylogarithmic factor) for all dimensions d and resiliences r. However, it's worth noting that these rates are not optimal for all graphs G. For instance, for the special case of trees see Györfi et al. (2022) , where better rates can be achieved. The case of general graphs G is an open problem.We will outline our proof techniques and demonstrate their relation to practically implementable estimators. Our theorem proofs employ disintegrations to construct a class of densities that closely approximate those with the given MRF. This class contains densities that take the form of histograms, i.e., piecewise constant densities on a grid. The remainder of the argument is relatively standard: A finite collection of the aforementioned class is found to cover the space, from which our estimate is chosen using a method akin to Scheffé tournaments (Scheffe, 1947; Yatracos, 1985; Devroye and Lugosi, 2001; Ashtiani et al., 2018) . Disintegrations are the core novel aspect of this work, characterizing a class of histograms much smaller than the full set, thereby reducing its metric entropy and enhancing the sample efficiency of our selection. 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 in Figure 3 .4 corresponds to first estimating a histogram for X 2 , and then, for each bin b of the X 2 histogram, estimating a histogram forX 1 |X 2 ∈ 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, which is effective due to the following inequalityd i=1 p i - d j=1 q j 1 ≤ d i=1∥p i -q i ∥ 1 for any probability densities p 1 , . . . , p d , q 1 , . . . , q d .Thus a disintegration can be thought of as a "meta-algorithm" providing an ordering for estimating conditional densities. In practice, it would be up to the implementation to determine how to handle the one-dimensional and conditional density estimation. 
graph resilience examples: 
 Theorems 3.1 and 3.2 demonstrate that the graph resilience acts as the effective dimension of a nonparametric estimation problem, however, graph resilience is still somewhat of an opaque property.In this section we will go over basic properties of graph resilience and describe graph resiliences for some graphs that reflect real-world settings.Here we present some basic results regarding graph resilience. We first introduce two very basic lemmas outlining the most fundamental properties of graph resilience. The first lemma shows how graph resilience behaves with disjoint graph union. Graph G Resilience r = r(G) Sample complexity n Trees (depth k) ≤ k ε -(k+2) Trees (general) O(log(d)) ∼ ε -(log(d)+2) Paths O(log(d)) ∼ ε -(log(d)+2) Grid O( √ d) ∼ ε -( √ d+2) Complete graph d ε -(d+2)m i=1 G i ) = max i r(G i ).This lemma encapsulates the notion that estimating joint density for a collection of independent random vectors, e.g., (Y 1 , . . . , Y m ) ∼ m i=1 µ i , from a collection of samples is no more difficult than estimating each independent vector individually, µ i ≈ µ i , and taking the product measure,m i=1 µ i ≈ m i=1 µ i .The second lemma demonstrates the behavior of graph resilience upon vertex removal.Lemma 4.2. Let G = (V, E) be a graph and letV ′ ⊂ V , then r(G) ≤ r(G \ V ′ ) + |V ′ |.This corresponds to conditioning the random variables in V \ V ′ on the |V ′ |-dimensional random vector corresponding to V ′ . Simpler graphs, in terms of number of edges and vertices, tend to have smaller graph resilience. The following lemma shows that adding edges to a graph will, at most, increase its resilience by the number of edges added.Lemma 4.3. Let G = (V, E) be a graph, let E ′ be a set of edges for vertices V , and letG ′ = (V, E ∪ E ′ ), then r(G ′ ) ≤ r(G) + |E ′ |.For a pair of graphs G, G ′ , let the relation G ′ ≤ G denote that G ′ is isomorphic to some subgraph of G. The following lemma demonstrates that removing random variables and dependencies between random variables can only reduce graph resilience.Lemma 4.4. For a pair of graphs G andG ′ , if G ′ ≤ G, then r(G ′ ) ≤ r(G).The following corollary follows directly from the previous Lemma 4.4 and Lemma 4.6, which we present later.Corollary 4.5. Let G be a graph whose largest clique contains k vertices, then r(G) ≥ k.From these properties of graph resilience we can derive the graph resilience of some example graphs. Some results from this section are summarized in Table 1 . We begin with a couple of simple cases.The following lemma demonstrates the surprising fact that, if even a single edge is missing from the graph, then the effective dimension of the estimation problem is strictly smaller than the ambient dimension d. The star graph is an example of a connected graph whose resilience is very small. Recall that a star graph S d is a graph with a single central vertex connected to every other node, i.e. E = {(i, j) : j ̸ = i}. Equivalently, it is (a) a complete bipartite graph with a single vertex in one partition or (b) a tree of depth one with a single root.Lemma 4.8. r(S d ) ≤ 2.In the remainder of this section, we describe additional examples of graphs whose resilience can be bounded. We focus on four broad classes of graphs, categorized by the application of interest: Hierarchical data (e.g. language, biology, phylogeny), sequential data (e.g. audio, video, language), spatial data (e.g. images, vision, signal processing), and clustered data (e.g. genetics, ecology, medicine). See Figure 1 for a guide to these classes of graphs.The following definition will be helpful for analyzing graphs that have a linear or grid shape. Definition 4.1. For a graph G and n ∈ N, the power graph G n , is the graph which inherits its vertices from G and a pair of vertices in G n are adjacent when their distance in G is at most n.Hierarchical data arises from distributions that have a tree-like structure, i.e. G is tree. In the worst-case, the resilience of a tree can scale at most logarithmically with d, however, in practical applications where the tree has bounded depth the resilience is also bounded. Lemma 4.9. Let G be a k-ary tree with depth m, then r(G) ≤ m.Lemma 4.10. Let G be a tree with d vertices, then r(G) ≤ log 2 (d) + 1.A path graph naturally represents sequential data. For a more realistic model one may assume that a vertex in a path graph is connected to all vertices within a given distance, so that nearby vertices are highly dependent, but far away indices are less dependent. Even with this assumption we see that, like tree graphs, the path graph's resilience only grows at rate O(log d). Here, L t t(2 s -1) is the power graph of L t(2 s -1) as defined in Definition 4.1.This, along with Lemma 4.4, yields the following rate on graph resilience for path graphs. Corollary 4.12. For any d ∈ N and any constant t ∈ N, we haver(L t d ) = O(t log d).Image data is naturally represented via a grid graph. The following graph describes a k × k ′ grid of vertices with every vertex connected connected to its vertical, horizontal, and diagonal, neighbors. Definition 4.3. The grid graph of shape k×k ′ , denoted L k×k ′ , is the graph(V, E) with V = [k]×[k ′ ] and E = {{(i, j), (i ′ , j ′ )} | (i, j) ̸ = (i ′ , j ′ ), |i -i ′ | ≤ 1, |j -j ′ | ≤ 1}.Proposition 4.13. Recall that L k×k be the grid graph of shape k × k as defined in Definition 4.3. For any s, t ∈ N, we haver(L t t(2 s -1)×t(2 s -1) ) ≤ 4t 2 2 s .Here, L t t(2 s -1)×t(2 s -1) is the power graph of L t(2 s -1)×t(2 s -1) as defined in Definition 4.1.Examples of a grid graph and its power can be found in Figure 5 in the appendix. The previous proposition gives us a general rate of √ d for grid graphs.Corollary 4.14. For any k ∈ N and any constant t ∈ N, we haver(L t k×k ) = O(t 2 √ d) where d = k 2 .Note that the graph L t k×k has d vertices.Another common type of structured data exhibits clusters: Variables in the same cluster are dependent, while variables in different clusters are independent. This type of structure can be modeled with disjoint cliques, where each clique represents a cluster or community. Let V i ⊂ V denote each cluster, withV i ∩ V j = ∅ and V = V 1 ∪ • • • ∪ V m (i.e. {V i } is a partition of V ). Let d i ≜ |V i |, G i ≜ K di be a clique (complete graph) on V i , and G = i G i .Then it follows from Lemmas 4.6 and 4.1 that r(G) = max i d i . In particular, if d i = O(1), then r(G) = O(1). Of course, this simply recovers the well-known result that a density that factorizes into a product of densities can be estimated at a rate that depends only on the largest factor. Using our graph resilience analysis we have that, for a stochastic block model, the graph resilience is bounded by the size of the blocks times the graph that encapsulates dependencies between the blocks. Lemma 4.15.Let G ′ = ([k], E ′ ) be a graph. Let G = (V, E) be a graph, such that there is a partition of V = k i=1 V i , where, if {v, v ′ } ∈ E it follows that v ∈ V i and v ′ ∈ V j where i = j or i and j are adjacent in G ′ . Then r(G) ≤ r(G ′ ) max i∈[k] |V i |.This has the useful interpretation that the effect of additional dependencies between clusters does not interact with the clusters themselves. For example, if we allow for noisy interactions between clusters (e.g. as in a stochastic block model), the complexity scales separately with the noise and the size of the largest cluster.The examples in the previous section can be used to show that the classical graphical properties that one might expect to govern the sample complexity surprisingly fail to capture the sample complexity.Degree The first and most obvious is the maximum degree of G. The star graph S d is an example where the resilience is O(1), and hence the sample complexity is (1/ε) O( 1) , but the maximum degree is Ω(d). Thus, the degree cannot properly capture the sample complexity. Moreover, the path graph shows the reverse: The maximum degree can be O(1) while the resilience is Ω(log d).Diameter The diameter diam(G) of a graph G is the length of its longest geodesic path. A clique K d thus has diam(K d ) = 1 (since every node is connected to every other node), but r(K d ) = d. It is clear even from classical results that a clique cannot be estimated any faster than (1/ε) d . Thus, the diameter also cannot capture the sample complexity.Sparsity Call a density p on d variables s-sparse if p(x) = q(x S ), where S ⊂ [d] with |S| = s. Now suppose p is s-sparse and q is Markov to a star graph S s on s vertices. Then Theorem 3.1 implies that p can be estimated with (1/ε) O( 1) samples (since r(G) = O(1)). Thus, taking s → ∞, it follows that the sparsity s cannot properly capture the sample complexity.In other words, not only does the graph resilience properly capture the sample complexity of structured density estimation, it is also not simply a proxy for commonly used graphical properties. 
conclusion: 
 This work has introduced a new concept, graph resilience, and demonstrated that it controls the complexity of estimating densities satisfying the Markov property. This characterization has shown that estimating such densities can be significantly easier than previous works have indicated. This finding contributes to the broader understanding of graph theoretical properties in statistical estimation and, more generally, to nonparametric estimation. The concept of resilience is a new and unexplored property with significant potential for discovering graphs that yield good estimation properties.2 grant MOE-T2EP20122-0001. B.A. was supported by NSF IIS-1956330, NIH R01GM140467, and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business.  
 
 Appendix: We begin by introducing some objects and notation that will be essential for proving the main theorems.Let N = {1, 2, . . .}. For any m ∈ N, let [m] ≜ {1, 2, . . . , m}. For any b ∈ N, let ∆ b be the simplex in R b , i.e. ∆ b =    v ∈ R b : i∈[b] v i =Λ d,b,A = d i=1 A i -1 b , A i b and Λ d,b = {Λ d,b,A | A ∈ [b] d }.For any d, b ∈ N, let H d,b be the set of all histograms with the bins from Λ d,b , i.e. In this work we will use the following version of the Markov property: for I, J ⊂ V , with I and J not intersecting or adjacent, X I ⊥ ⊥ X J | X V \I∪J . Note that this property is satisfied when the "global" Markov property is satisfied.H d,b =    f : [0, 1) d → R | f = A∈[b] d b d T A • χ Λ d,Lemma B.1 (Lemma 3.3.7 from Reiss (1989) ). For probability measures Vandermeulen and Ledent (2021) ). For all b and 0t i=1 µ i - t i=1 ν i 1 ≤ t i=1 ∥µ i -ν i ∥ 1 . Lemma B.2 (Lemma A.1 from< ε ≤ 1, N ∆ b , ε ≤ (2b/ε) b .Lemma B.3 (Theorem 3.4 page 7 of Ashtiani et al. (2018) , Theorem 3.6 page 54 of Devroye and Lugosi (2001) ). There exists a deterministic algorithm that, given a collection of distributions p 1 , . . . , p M , a parameter ε > 0 and at leastlog(3M 2 /δ) 2ε 2iid samples from an unknown distribution p, outputs an index j ∈ [M ] such that∥p j -p∥ 1 ≤ 3 min i∈[M ] ∥p i -p∥ 1 + 4εwith probability at least 1 -δ 3 .This section contains intermediate technical results which will aid in proving more core results. Lemma B.4. For any 0 < ε < 1, any b, t ∈ N and any graph G i for i ∈ [t], we haveN T b t i=1 G i , ε ≤ t i=1 N (T b (G i ) , ε/t) . Proof of Lemma B.4. Let C i be any (ε/t)-cover for T b (G i ) such that N (T b (G i ) , ε/t) = |C i | for all i ∈ [t].If we manage to argue that the setC = {T 1 × • • • × T t | T i ∈ C i for all i ∈ [t]} is an ε-cover of T b t i=1G i , then we immediately show the statement sinceN T b t i=1 G i , ε ≤ |C| = t i=1 |C i | = t i=1 N (T b (G i ) , ε/t) .Now, to show that C is an ε-cover, we observe that anyT ∈ T b t i=1 G i has the form of T 1 × • • • × T t where T i ∈ T b (G i ) for all i ∈ [t] since we recall that t i=1 G iis simply a union of the graphs with no edges across different connected components which implies the vertices in different connected components are independent. Since C i is an(ε/t)-cover of T b (G i ), there is a T i ∈ C i such that ∥ T i -T i ∥ 1 ≤ ε/t. By taking T = T 1 × • • • × T t ∈ C, there exists a T ∈ C such that, by Lemma B.1, we have ∥ T -T ∥ 1 ≤ t i=1 (ε/t) = ε.Lemma B.5. For any 0 < α < 1, any 0 < ε < 1, any b ∈ N, any graph G and any vertex v in G, we haveN (T b (G), ε) ≤ N (T 1,b , αε) • N (T b (G \ {v}) , (1 -α)ε) b .Proof of Lemma B.5. Without loss of generality, we assume v = 1. Suppose the graph G has d vertices. Let C 0 be any(1 -α)ε-cover of T b (G \ {1}) such that N (T b (G \ {1}) , (1 -α)ε) = |C 0 |Base case r = 1: Note that the graph G is a graph with only one vertex. By Lemma B.2, we havelog N (T b (G), ε) ≤ log N (∆ b , ε) ≤ b log 2b ε = 1 • b 1 log 2 • 1 1 • b ε ,thereby satisfying (5).Inductive step r > 1: Let v be the vertex selected in the first disintegration step of the rdisintegration and G 1 , . . . , G t be the connected components after removing v from G. Also, for all i ∈ [t], let r i = r(G i ) and d i be the number of vertices in G i . By Lemma B.5, we first haveEQUATIONBy Lemma B.4, we further haveEQUATIONNote that the resilience of each G i is at most r -1 (i.e. r i ≤ r -1) and hence we invoke the inductive assumption. We havelog N T b (G i ), ε t + 1 ≤ d i • b ri • log 2(t + 1)d ri i b εby the induction assumptionEQUATIONBy plugging ( 8) into ( 7) and ( 6), we havelog N (T b (G), ε) ≤ b log 2(t + 1)b ε + b • t i=1 d i • b r-1 • log 2d r b ε ≤ b r log 2d r b ε • 1 + t i=1 d i since t + 1 ≤ d r = db r log 2d r b ε since 1 + t i=1 d i = d.Now, we remove the assumption of G being connected. Suppose G has t connected components, G 1 , . . . , G t whose number of vertices is d i and resilience is r i . We havelog N (T b (G), ε) ≤ t i=1 log N T b (G i ), ε t by Lemma B.4 ≤ t i=1 d i b ri log 2td ri i b ε from the case of G being connected ≤ db r log 2d r+1 b ε since d i ≤ t i=1 d i = d, r i ≤ r and t ≤ d.Theorem B.7. For any d, b ∈ N, any L > 0, any graph G and any p ∈ D L (G), we havemin p ′ ∈U d,b (T b (G)) ∥p -p ′ ∥ 1 ≤ √ dL/b. Proof of Theorem B.7. For any d, b ∈ N and A ∈ [b] d , recall that Λ d,b,A = d i=1 Ai-1 b , Ai b . Let λ A be the centroid of Λ d,b,A . We define p ′ = A∈[b] d p (λ A ) χ Λ d,b,A and p = p ′ /Z if Z ̸ = 0 (9) where χ Λ d,b,A is the indicator, i.e. χ Λ d,b,A (x) = 1 if x ∈ Λ d,b,A 0 if x / ∈ Λ d,b,Aand Z is the normalizing factor, i.e. Z = x∈[0,1) d p ′ (x)dx.Since the construction requires Z ̸ = 0, we now first show that when Z = 0 the statement holds trivially. When Z = 0, we havep(λ A ) = 0 for all A ∈ [b] d which implies p(x) ≤ L • ∥x -λ A ∥ 2 ≤ L √ d/(2b) since p ∈ D L (G).Hence, we further have1 = x∈[0,1) d p(x)dx = A∈[b] d x∈Λ d,b,A p(x)dx ≤ A∈[b] d x∈Λ d,b,A L √ d/(2b)dx = L √ d/(2b).Namely, L √ d/b ≥ 2 and therefore the statement holds for anyp ′ ∈ U d,b (T b (G)).Now, we assume that Z ̸ = 0. We will prove the statement by arguing 1)p ∈ U d,b (T b (G)) and 2) ∥p -p∥ 1 ≤ √ dL/b. To prove 1) p ∈ U d,b (T b (G)): For any partition V 0 ∪ V 1 ∪ V 2 of the vertex set of G such that V 0 separates V 1 and V 2 ,we would like to show, for any x * ∈ [0, 1) d (without loss of generality, we reorder the indices such that x = (x V1 , x V2 , x V0 ))p(x * V1 , x * V2 , x * V0 ) p( : , : , x * V0 ) = p(x * V1 , : , x * V0 ) p( : , : , x * V0 ) • p( : , x * V2 , x * V0 ) p( : , : , x * V0 ) if p( : , : , x * V0 ) ̸ = 0where we use : to indicate integrating with respect to the corresponding variables, i.e.p( : , :EQUATIONWe now analyze each of p(x * V1 , x * V2 , x * V0 ), p( : , : , x * V0 ), p(x * V1 , : , x * V0 ), p( : , x * V2 , x * V0 ). Let λ (resp. λ * ) be the closest centroid to x for any x ∈ [0, 1) d (resp. x * ). For p ′ (x * V1 , x * V2 , x * V0 ), we haveEQUATIONHere, recall that we use : to indicate integrating with respect to the corresponding variables, i.e., for any centroid λ including λ * ,p(λ V1 , : , λ V0 ) = x V 2 ∈[0,1) d 2 p(λ V1 , x V2 , λ V0 )dx V2 p( : , λ V2 , λ V0 ) = x V 1 ∈[0,1) d 1 p(x V1 , λ V2 , λ V0 )dx V1 p( : , : , λ V0 ) = (x V 1 ,x V 2 )∈[0,1) d 1 +d 2 p(x V1 , x V2 , λ V0 )d(x V1 , x V2 ).For p ′ ( : , : , x * V0 ), we have 9), we havep( : , : , x * V0 ) = (x V 1 ,x V 2 )∈[0,1) d 1 +d 2 p(x V1 , x V2 , x * V0 )d(x V1 , x V2 ) = 1 Z (x V 1 ,x V 2 )∈[0,1) d 1 +d 2 p ′ (x V1 , x V2 , x * V0 )d(x V1 , x V2 ) Since, for any A ∈ [b] d , p ′ (x V1 , x V2 , x * V0 ) = p(λ V1 , λ V2 , λ * V0 ) for all (x V1 , x V2 , x * V0 ) ∈ Λ d,b,A by ((x V 1 ,x V 2 )∈Λ d,b,A p ′ (x V1 , x V2 , x * V0 )d(x V1 , x V2 ) = 1 b d1+d2 p(λ V1 , λ V2 , λ * V0 ).By plugging it into the equation for p( : , : , x * V0 ), we haveEQUATIONFor p ′ (x * V1 , : , x * V0 ), we haveEQUATIONSimilarly, for p ′ ( : , x * V2 , x * V0 ), we haveEQUATION)By using ( 11), ( 12), ( 13) and ( 14), we can conclude (10).To prove 2) ∥p -EQUATION)Note that p ′ may not be a probability density.For the first term ∥p -p ′ ∥ 1 , we haveEQUATIONFor any x ∈ Λ d,b,A , we have p ′ (x) = p(λ A ) by the definition of p ′ . Also, since p ∈ D L (G), p satisfies the L-Lipschitz condition which impliesEQUATIONBy plugging ( 17) into ( 16), we haveEQUATIONFor the second term ∥ p ′ -p∥ 1 , we observe that p is simply a scaled version of p ′ by a factor of 1/Z. Namely, we have ∥ p ′ ∥ 1 = Z and ∥ p ′ -p∥ 1 = |Z -1| since ∥ p∥ 1 = 1. By ( 18) and the fact of ∥p∥ 1 = 1, we further haveEQUATION) By plugging ( 18) and ( 19) into (15), we have ∥p -p∥ 1 ≤ L √ d/(2b) + L √ d/(2b) = L √ d/b.With the previous results established we can now prove the core sample complexity results of this work.Proof of Theorem 3.1. Recall that Lemma B.3 states the following. There is a deterministic algorithm that, given a collection of M distributions C = {p 1 , . . . , p M }, any 0 < ε < 1 and at least log(3M 2 /δ)2ε 2i.i.d. samples drawn from an unknown distribution p, outputs an index j ∈ [M ] such that∥p j -p∥ 1 ≤ 3 min i∈[M ]∥p i -p∥ 1 + 4ε with probability at least 1 -δ 3 .We -p ′′ ∥ 1 ≤ ∥p -p ′ ∥ 1 + ∥p ′ -p ′′ ∥ 1 ≤ √ dL b + ε.Namely, whenever n ≥ . In particular, when r = 1, we have |G| = 1. Hence, we havedb r log( 2d r+1 b ε ) ε 2 + log(3/δ)log M ≤ db r log( 2d r+1 b ε ) + d 2 if r > 1 db log( 2d 2 b ε )if r = 1 and we can conclude the desired result by following the rest of the proof in Theorem 3.1. Now, we remove v * in the first step and all the connected components, G 1 , . . . , G t , has at most ⌊ d 2 ⌋ vertices. By induction, we have r(G) ≤ r(G \ {v * }) + 1 by Lemma 4.2 = r( i∈[t] G i ) + 1 = max i∈[t] r(G i ) + 1 by Lemma 4.1 ≤ log 2 (⌊ d 2 ⌋) + 1 + 1 by the inductive assumption = log 2 (d) + 1.Proof of Proposition 4.11. We will prove the statement by induction on s.Base case s = 1: When s = 1, we observe that L t t(2 1 -1) = L t t is a complete graph with t vertices. By Lemma 4.6, we have r(Lt t ) = t ≤ 1 • t. Inductive step s > 1: Let V ′ ⊂ V be {t(2 s-1 -1) + i | i ∈ [t]}. Note that |V ′ | = t. By Lemma 4.2, we have r(L t t(2 s -1) ) ≤ r(L t t(2 s -1) \ V ′ ) + t.In other words, we first remove the "middle" t vertices from the graph. By the definition of path graphs (Definition 4.2), it is easy to check that there is no edge between i and j for i = 1, . . . , t(2 s-1 -1) and j = t(2 s-1 -1) + t + 1, . . . , t(2 s -1). Therefore, there are two connected components and clearly each of them is isomorphic to Proof of Proposition 4.13 . We will prove the statement by induction on s.L t t(2 s-1 -1) . Let G 1 and G 2 be the two connected components, i.e. L t(2 s -1) \ V ′ = G 1 ⊕ G 2 . Then, we have r(L t t(2 s -1) ) ≤ r(G 1 ⊕ G 2 ) + t = max{r(G 1 ),Base case s = 1: When s = 1, we observe that L t t(2 1 -1)×t(2 1 -1) = L t t×t is a complete graph with t 2 vertices. By Lemma 4.6, we have r(Lt t×t ) = t 2 ≤ 4t 2 2 1 . Inductive step s > 1: Let d ′ be t(2 s-1 -1). Let V ′ ⊂ V be V ′ ≜ {(d ′ + i, j) | i ∈ [t], j ∈ [t(2 s -1)]} ∪ {(i, d ′ + j) | i ∈ [t(2 s -1)], j ∈ [t]}. Note that |V ′ | = t 2 + 4t 2 d ′ ≤ 4t 2 2 s-1 . By Lemma 4.2, we have r(L t t(2 s -1)×t(2 s -1) ) ≤ r(L t t(2 s -1)×t(2 s -1) \ V ′ ) + 4t 2 2 s-1 .In other words, we first remove the vertical and horizontal "middle" stripes from the graph. By the definition of grid graphs (Definition 4.3), it is easy to check that there is no edge between (i 1 , j 1 ) and (i 2 , j 2 ) if one of the followings happens:EQUATIONin the proof of Proposition 4.13• i 1 = 1, . . . , t(2 s-1 -1) and i 2 = t(2 s-1 -1) + t + 1, . . . , t(2 s -1)• j 1 = 1, . . . , t(2 s-1 -1) and j 2 = t(2 s-1 -1) + t + 1, . . . , t(2 s -1).Therefore, there are four connected components and clearly each of them is isomorphic to 6 for the graphical illustration. Then, we have L t t(2 s-1 -1)×t(2 s-1 -1) . Let G 1 , G 2 , G 3 , G 4 be the four connected components, i.e. L t t(2 s -1)×t(2 s -1) \ V ′ = G 1 ⊕ G 2 ⊕ G 3 ⊕ G 4 . See figurer(L t t(2 s -1)×t(2 s -1) ) ≤ r(G 1 ⊕ G 2 ⊕ G 3 ⊕ G 4 ) + 4t 2 2 s-1 ≤ max{r(G 1 ), r(G 2 ), r(G 3 ), r(G 4 )} + 4t 2 2 s-1 by Lemma 4.1 ≤ 4t 2 2 s-1 + 4t= O(t 2 k) = O(t 2 √ d).Proof of Lemma 4.15. We will assume V 1 , . . . , V k all contain m vertices and for all i for all v, v ′ ∈ V i , v is adjacent to v ′ (all of the blocks are fully connected). We will prove the lemma for this case, the lemma statement then follows from application of Lemma 4.4.We will denote the vertices of V i as v i,1 , . . . , v i,m . Let D ′ be a t-disintegration of G ′ . Let D be a t × m-tuple, where D i,j = {v i,j | i ∈ D i , j = j}. If one considers D in lexicographical order, then it is clearly a pre-disintegration of G with length mt. This case then follows from Lemma C.1.Consider a fixed dimension d and resilience r. Let G be a graph where vertices 1, . . . , r form a complete subgraph, and vertices r + 1, . . . , d are isolated (not adjacent to any other vertex). Let L > 0, and suppose we have an estimator that can estimate densities in D L (G) at rate O(n -1/(2+r-ε) ) for some ε > 0. Let p ∈ D r,L and X 1 , . . . , X r ∼ p. We will construct an estimator for p using the aforementioned estimator. Define X 1 , . . . , X d ∼ p as follows:( X 1 , . . . , X r ) d = (X 1 , . . . , X r ), X r+1 , . . . , X d iid ∼ Unif([0, 1]),where ( X 1 , . . . , X r ) and ( X r+1 , . . . , X d ) are independent.Note that p ∈ D L (G). Let p be an estimator for p such that -ε) .∥ p -p∥ 1 ∈ O n -1/(r+2Let L denote the law of a random vector. It is well known that for any function f from one Euclidean space to another, ∥L(f (X)) -L(f (Y ))∥ 1 ≤ ∥L(X) -L(Y )∥ 1 (see Devroye and Lugosi (2001) , Section 5.4). We will use f : (x 1 , . . . , -ε) ).This shows we can estimate all densities in D r,L at rate O n -1/(r+2-ε) , while the known optimal rate is O n -1/(r+2) . Thus, for any r and d, there exists a graph with d vertices and resilience r such that estimation of densities in D L (G) can be no faster than O n -1/(r+2) .Answer: [NA] Justification: Our paper does not release new assets. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 


Decision: This is a theory orientated paper on graphical models (i.e., high dimensional distributions whose independence structure is captured by a graph G). The paper shows that the sample complexity of learning such distributions is characterized by a novel “resilience” property of the underlying graph, which is a much richer property than previously considered properties like graph sparsity. The reviewer agreed that the paper was very well-written, and felt that the resilience property was both novel and has potential for impact on future work, especially given how well-studied graphical models are. There are ways to strengthen the paper, for example, with experiments validating the theoretical results. Nevertheless, we recommend to accept the paper on its theoretical merits alone.

Reviews: review: paper_summary: paper_summary: The authors, through the formalism of graph models for probability density functions, identify the “graph resilience” as a key quantity to estimate the sample complexity of computing the density.
strength_weakness: strength_weakness: 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.    

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.  

No practical applications are shown.  

From certain point of view, the novelty is not high: The authors shown that, for structured data, the Markov property is enough to simplify the complexity of density estimation. 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.
questions: questions: Why is the manifold assumption violated in structured data if the effective dimension is lower than the embedding dimension? 

Are you willing to provide a code that allows to use your findings in practical data?
limitations: limitations: No limitations are discussed. Aspects like the limited application field and the difficulties when trying to use the findings in real data should be addressed.
paper_summary: paper_summary: The paper studies the problem of estimating a multivariate density, assuming that the density is Markov w.r.t an underlying undirected graph $G$. It is shown that the sample complexity for estimating such a density scales with the resilience of the graph, as opposed to  the dimension d. Several examples of G are provided for which the resilience can be exactly computed or bounded.
strength_weakness: strength_weakness: 1. It would have been helpful to provide a proof-sketch of the main theorems in the main text, this is particularly relevant here given that this is a theoretical paper. Moreover, I think it is important to outline the algorithm in the main text and not relegate it to the appendix. To handle space constraints, I think parts of Section 4 could be moved to the appendix as they are relatively less important as opposed to the aforementioned details.

2. It would have also been useful to provide some simulation results on synthetic data as this would have helped empirically validate the theoretical results.
questions: questions: 1. What is the running time of the algorithm w.r.t n, d and r? This is important to discuss in the main text and is related to the point I had raised earlier.

2. 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)?

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

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

Minor remarks:

- I think there is a typo towards the end of line 182. Another typos in line 252 ("... tend to have ...")

- In the statement of Theorem 3.1, it might be good to specify that $G$ is known.
limitations: limitations: I do not see a dicussion on limitations in the main text.
paper_summary: paper_summary: This paper proposed a new summary of graph, called graph resilience, which measures the complexity of density estimation. This concept is different from more its well-known counterparts, including rank, sparsity, manifold dimension etc. Quite a few concrete examples of graph along with their resilience are given. Both the concept and the theory are sound, the contribution to the literature of density estimation is solid.
strength_weakness: strength_weakness: More intuitions are expected, to define $r$. 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?
questions: questions: 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.
limitations: limitations: Can the authors discuss some possible extensions? For example, what does the resilience look like for directed graphs, or for non-Markovian graphs?

Comments: title: Response to Reviewer P9wL comment: On practical applications
Response to Reviewer yapz comment: On calculating graph resilience
Read authors response
Follow up
comment: Thanks for the clarification. I suggest the authors to clarify this computational aspect somewhere in the paper, even in the appendix. I'll keep my (positive) score.
__”Is there a practical way to take advantage of resilience to compute densities? Can you show that in a real case?”__

Yes, there is a practical way to take advantage of this. This is related to our explanation of graph resilience in our rebuttal to yapz. Graph resilience essentially gives the most efficient disintegration of a graph, and can be thought of as a sort of “meta-algorithm.” The disintegration gives an ordering as to how to estimate conditional densities, however it would be up to a practitioner to decide how to take care of the one-dimensional and conditional density estimation, which are themselves structured in an inductive way. 

More precisely, a disintegration outlines a way to inductively condition 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 $p_{X_2}$, and then, for each $x$, estimating the density $p_{X_1|X_2=x}$. The Lipschitz condition tells us that $p_{X_1|X_2=x}$ doesn’t change drastically as $x$ changes, thus making the problem tractable.

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 which is justified due to the following 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$

For a concrete example, consider the graph $(X)-(Y)-(Z)$, with the disintegration 

 $(X)-(Y)-(Z) \Rightarrow  (X)\quad (Z)   \Rightarrow \emptyset$.

This corresponds to estimating $p_Y$, then estimating $p_{X,Z| Y}$ utilizing the fact that $X$ and $Z$ are independent given $Y$ so $p_{X,Z| Y}(x,z) = p_{X| Y}(x)p_{Z| Y}(z)$ thus instead of having to estimate  a two dimensional conditional density, one can simply estimate two one dimensional conditional densities and take the product, thereby avoiding the curse of dimensionality. This example only contains one simple instance of taking advantage of the product structure, but there may be layers of product structure, which is exemplified in our result that the graph resilience of a linear Markov graph grows only logarithmically in dimension. One also need not know the disintegration corresponding to the graph resilience in order to apply this. The resilience simply characterizes the best possible disintegration. 

While disintegrations are based on estimating many one-dimensional conditional distributions, one could instead estimate low-dimensional distributions. We would be happy to add an appendix (based on this discussion) outlining how a practitioner can take advantage of the disintegration structure in a more practical and readable way.
__”Can I understand your answer as "we don't have a principled way to exactly calculate it, and we don't know the cost"?”__

Correct, we don’t have a general way to calculate it exactly, and we stress that part of our contribution is to emphasize the relevance of this new quantity, so as to inspire future investigations that might provide principled algorithms. We suspect, for example, that greedy methods may work well and give useful bounds. An example of this could be greedily removing the most central vertex in each graph component according to some vertex centrality measure (e.g. vertex degree).
Thank you for the clarifications, I am satisfied with them. I am not insistent on the simulations, although I do think it would have strengthened the paper. But adding a proof sketch in the main text is more important given that this is a theory paper. 

I am increasing my score to 6.
I thank the authors for the reply, now things are more clear. 
Regarding practical applications, I'm still not convinced that a paper with no practical applications is worth publication in Neurips, but before deciding to maintain or raise my score I would like to have a clear reply from the authors. Is there a practical way to take advantage of resilience to compute densities? Can you show that in a real case?
Thanks for the response. The intuition is helpful to understand the concept. For the calculation, I understand it's not necessary to calculate it exactly for certain purpose. I asked this question because I'd like to understand the concept deeper, not for any specific (practical) purpose. Can I understand your answer as "we don't have a principled way to exactly calculate it, and we don't know the cost"?