Breaking the curse of dimensionality in structured density estimation
Authors: Robert A. Vandermeulen
Wai Ming Tai
Bryon Aragam
Venue: NeurIPS 2024 poster (2024)
Keywords: nonparametric statistics
density estimation
graphical models
sample complexity
curse of dimensionality
Primary area: learning_theory
TL;DR: This work presents a new graphical quantity and shows that, when one assumes the Markov property over this graph, it leads to much faster rates for nonparametric density estimation.

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.

Breaking the curse of dimensionality in structured density estimation
Robert A. Vandermeulen'
Wai Ming Tait
Bryon Aragam
Abstract
We consider the problem of estimating structured multivariate density, subject Markov conditions implied by an undirected graph. 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 foeus on sparsity or manifold assumptions, we introduce new graphical quantity called "graph resilience" and show how it controls the 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 circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data.
Introduction
Density estimation 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 notoriously difficult problem in dige-dimesssons, known to suffer from the so-called curse dimensionality. When the density depends only few variables more generally, is supported known that the curse of dimensionality can be circumvented by substituting the ambient dimension with the effective dimension (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?
now-dimensional manifold, it is
Three representative examples are given 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 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 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 example of this.
These examples are particularly appealing applications, however, we emphasize that our problem setting is considerably more general, and applies to general dependence structures given by any
Much of this work was conducted the Berlin Institute Foundations Learning and Data (BIFOLD). Technische Universität Berlin. Contact: robert. anton. vandermeul wtt.mmeeenneemaamlemmmmmmmmmaalm com
Thee work done when the author
Nanyang Technological University.
Contact:
taivaiming220300maa1... com University of Chicago. Contact: bryon@chticagoboothcc edu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Path (sequential data)
Tree (hierarchical data)
Grid (spatial data)
Graph resilience: = (log d) Samples: n 2 (1/e) (loge)
Graph resilience: == O(1)
Graph resilience: o(d) Samples: n 2 (1/e)old)
Samples: 2 (1/e)o()
Figure 1: Examples of common structures that yield improvements in density estimation. As indicated by the path example on the left, which also a tree, the worst-case resilience of any tree is r = (log d), but for bounded-depp -eeth trees, r = (1).
Markov random field. Since real data is expected to (approximately) exhibit these types of structures, reasonable question to ask is whether or not the curse of dimensionality persists in such structured settings.
Structured density estimation To formalize the notion of structured dependencies in a high- dimensional, multivariate distribution, we adopt the framework of undirected graphical models, also known Markov random fields (MRFs). In this setting, we given samples from unknown distribution P, with density p, over the random vector X = (X1.... Xa). and it is assumed that P Markov to some undirected graph G (see Section 3.1 for definitions). We treat both cases where G is a priori known, and where 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 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 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 functional restrictions on 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 density- for arbitrary graphs G-in total variation (TV) distance: is approximately (1/2)*+2, where r < is novel graphical parameter call graph resilience that depends only on G. Roughly, r is measure of how connected the graph is; the easier it is to disconnect G, the smaller r will be. The examples
in Figure I illustrate a range of values from constant r = O(1) to sublinear r = O(v d = o(d). In the former case, this leads nonparametric sample complexity of (1/e)d.
exponential improvement in the sample complexity over the usual
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: 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 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 low- dimensional embeddings (e.g. manifold hypothesis). Instead, we impose no explicil restrictions on the functional form (although certain restrictions are implicit through the Markov assumption). In practice, empirical evidence points to combination of these properties prevailing in real-world data,

---

Correlation
Cord Correlation
10
0.
20
20
04
10
10
0-
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 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 (Detinition 3.2), which approximately quantifies the connectivity an undirected graph. Resilience 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 density p that is Markov to any undirected graph G scales with the resilience r = r(),, as opposed to the dimension d (Theorem 3.1). We also provide examples to show that other metries such as degree, diameter, and sparsity cannot properly capture the sample complexity (Section 4.3). 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 bounded. These examples include familiar graphs such as trees (including paths for sequential data), cliques, and grids (also known as lattice graphs), and represent 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 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 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 dimension- independent (i.e. O(1)), in which case the curse of dimensionality is circumvented completely, to dimension-deppendet with nontrivial savings (e.g. r r= (d)).
Related work
We begin by recalling classical rates and results density estimation. The standard nonparametric rate for estimating an T.-Lipschitz density p in dimensions in TV distance is n -1/(d42); see Devroye and Gyorfi (1985); Tsybakov (2009); Giné and Nickl (2015) for more details. This rate ignores dimension-dependeen constants that affect finite-sample rates, and more refined bound on the sample

---

complexity (ignoring cog-factors) is given in McDonald (2017):
dd
n 2
ed+2
See also Ghorbani et al. (2020); Jiao al. (2023). For comparison, our main result is that only
rd
ex
samples are needed (again up to fag-factors) when is Markov to an undirected graph G with resilience r = r(G), and this rate cannot be improved among graphs whose resilience 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-dependen 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 (I) with some s < d, where 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 = is the graph resilience.
Recently, there has been 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.
2.1 Density estimation
As noted in the introduction, density estimation is a classical problem with a literature dating back more than 50 years. Notably, Stone (1980, 1982) established minimax rates for nonparametric esti- mation problems including density estimation and regression. These papers derived the now-classical nonparametric rate n d)/(28+d for 3-smooth densities, which implies the curse of dimensionality. i.e. unless p is very smooth, then the sample complexity of estimating 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 P6czos, 2018; Uppal et al., 2019, 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, 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 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, 201 I); 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. (201 1) 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 tree-structured density, which is notably dimension-indepeeee 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 I 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 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.

---

2.2 Curse of dimensionality
There is 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 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-Hieher 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 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 con-coopositional (we consider arbitrary continuous densities), and are not supported on any lower-dimensional manifold, but that are Markov to given graph G.
3
Main Results
Before presenting the main results of this paper we must present some basic background.
3.1
Background Definitions and Notation
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= (4) and d = dim(X). ). To avoid technical complications, we assume compact support with X "X_,...... X2) E [0. 1jd. Two disjoint subsets A, B C V are said to be separated by C' if all paths connecting A to B intersect C: equivalently, the subgraph over (A B) C is disconnected.
The distribution P is called Markov with respect to G
A is separated from B by C = AI
where IL 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 of G (sometimes called a connected component) if is a maximal connected subgraph of G. A path in G is sequence of vertices (No, Ui,-... U&) such that ey- Di-1 1 in G (i.e. i 1) E 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 (vo, UI.... U&) 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 and G'. For a graph G (V, E), for V V. the graph \ V denotes the graph with vertices V V and the edges {i,j} E E where { EVV..
For any d E N and L 2 O, let D& be the set of densities on [0, 1] and Da. C Da be those densities which are L-Lipschitz continuous. For any graph G with d vertices, we define D(G) C Da. such that, for p E D(G) and (XI...., X2) ~ p, the entries of the random variable, XI...., X2x satisfy the global Markov property with respect to the graph G. Finally let (G) & D(G) n Da,L- When estimating these densities
will sometimes use the term sample complexity. This refers to the number of samples necessary to estimate a density to within e error in total variation distance. For functions, f on (0, 1|d we define [|f[] [=) this is the total variation distance.
3.2 Graph Resilience
The key concept in this work, which characterizes the difficulty of estimating densities in D(G), what we term the graph resilience G. Graph resilience is based process we call disintegration.
5

---

5
2
3
null graph
7
Figure 3: Visual representation of the steps of the 3-disintegration ((1,6), (3,5, 7), (2,4)). In each step of the disintegration, one vertex 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 (Vi...,, V,) with V22 C V called disintegra- tion of G if:
1. (Vi is partition of V;
2. The elements of V1 all lie in different components of G;
3. Vi is equal to the number of components in G;
4. For all i E {r 1] the elements of Vi+1 lie in different components of G (U; Vj;
5. Vi+1/ is equal to the number of components in G G Vj.
The length a disintegration is the value r in the above definition. disintegration of length r will be called r-disintegration.
The first disintegration step. V1 above, can be thought of as the process of picking one vertex from each component in G' and removing it. The next step of disintegration, V2 above, then selects and removes one vertex from each component the resultant graph. An r-disintegration a sequence of such steps until one is left with the null graph. It is possible for graph to admit many different disintegrations of different lengths. visual representation of the steps of graph disintegration can be found in Figure 3.
The resilience of graph describes the length of the shortest possible disintegration of G.
Definition 3.2. For graph G, the resilience of G, denoted rG),, is the smallest such that there exists a r-disintegration of G.
We elaborate more on some properties graph resilience in Section 4, including upper bounds for the graph resilience of several graphs corresponding image sequence data. First, we need to establish that graph resilience is the right metric for quantifying the sample complexity of density estimation.
3.3 Sample complexity
The following theorem characterizes the difficulty of estimating a density which is known to satisfy the Markov property in terms its graph. All proofs are deferred the appendix.
Theorem 3.1. Let be a (known) graph whose number of vertices d and resilience is r. Let L 2 For any 0 1, there exists algorithm that takes samples drawn from any (G) and returns a distribution q such that
p00/2+1 log( ) los(2/6) ii.d
5
|p all s with probability at least 1
3"
This corresponds to convergence rate of (1((+(()))) and is uniform over (G). For comparison, the rate (nn-1/(44)) is known to be optimal for estimating densities in Da in the total variation norm (e.g. Beirlant and Gyorfi, 1998). Consequently the rate O(n -1/(++)) indicates that the rate of convergence when estimating densities in Dr, (G) is akin estimating densities in D,,,. We will see in Section 4.2 that, for graphs typically used to represent audio image data, the effective dimension for estimating densities be drastically, even exponentially, smaller than the ambient dimension.

---

While it may be reasonable to assume 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 rate of (n
Theorem 3.2. Let G be the set of all graphs whose number of vertices d and resilience is Let I. For any 0 < < 1, there exists an algorithm that takes i.d. samples drawn from any E UGeg Dr.(G) and returns distribution q such that
ydd/2+111
log( d.L,) log(1/8)
e
8
Pp 9|l1 S with probability at least 1
3
We show in Appendix D that these rates are optimal (up to polylogarithmic factor) for all dimensions 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örf et al. (2022), where better rates can be achieved. The case of general graphs G is an open problem.
3.4 Proof Outline and Practical Consequences
We will outline our proof techniques and demonstrate their relation to practically implementable estimators. Our theorem proofs employ disintegrations to construct class of densities that closely approximate those with the given MRF. This class contains densities that take the form of histograms, ie., piecewise constant densities finite collection of the aforementioned class is found to cover the space, from which our estimate is chosen using 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 class of histograms much smaller than the full set, thereby reducing its metric entropy and enhancing the sample efficiency of our selection.
grid. The remainder of the argument is relatively standard: A
At high level, disintegration outlines method to estimate density by inductively conditioning out the entries of a random vector. For instance, consider random vector (X1, X2]. The disintegration in Figure 3.4 corresponds to first estimating a histogram for X2, and then, for each bin b of the X2 histogram, estimating a histogram for X, |X, E b. The resilience of a graph simply characterizes the shortest disintegration, i.c. the most efficient decomposition of 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 nigh-dimensional joint density of all vertices in the graph. Instead, we can estimate the low-dimensional components individually and take their product, which effective due to the following inequality
null graph
Figure 4: A simple disintegra- tion example.
d 11 P. [[g
9
P. - for any probability densities Pi....,Pd: 91 ................................ qd-
Thus disintegration can be thought of as a "meta-algorithm" providing an ordering for estimating conditional densities. practice, would be up to the implementation determine how handle the one-dimensional and conditional density estimation.
4 Graph Resilience Examples
Theorems 3.1 and 3.2 demonstrate that the graph resilience acts the effective dimension of 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.
4.1 Graph Resilience Properties
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.
7

---

Graph G
Resilience = r(G)
Sample complexity n
Trees (depth k))
S k (log(d)) (llg(dd) d
(k++)
Trees (general)
(1)g(d)+2)
Paths
e (log(d)+2)
Grid
O(vd)
(V
Complete graph
e (d+2)
Table 1: Example graph resiliences and corresponding sample complexities
Lemma 4.1. Let GI..... ,.......m... Gm be graphs, then r( G.) max; r(.)).
This lemma encapsulates the notion that estimating joint density for a collection of independent random vectors, e-g., .Y,,..,, Ym)
I Ps,, from collection of samples is no more difficult than estimating each independent vector individually, f z pi. and taking the product measure, IT (4 II P4:
The second lemma demonstrates the behavior of graph resilience upon vertex removal.
Lemma 4.2. Let = EV, be a graph and let c. V, then r(G) S r(G') V*) + +VV
This corresponds to conditioning the random variables in AAV V on the VV dimeennnnlll random vector corresponding to V"
Simpler graphs, in terms of number of edges and vertices, tend 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 EV be graph, let E' be of edges for vertices V, and let G' (V, EVEUB E"), then r(G') S r(G) + EE
For a pair of graphs G, G", let the relation G' < G denote that G' 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 and G', Gf G, then r(G' S 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 graph whose largest clique contains k vertices, then r r(G) 2 k.
4.2 Example Graph Resiliences
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 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 strietly smaller than the ambient dimension d.
Lemma 4.6. For graph G = EV, r(G) = [V] if and only G is complete graph.
Analogously, a graph can only have resilience 1 if is the empty graph. Lemma 4.7. For a graph G = (V, E), r(G) = 1 if and only if E 0.
The star graph is an example of connected graph whose resilience very small. Recall that star graph Sa is graph with a single central vertex connected to every other node, i.e. E {(i,) j) # i). Equivalently, is (a) a complete bipartite graph with a single vertex in one partition (b) a tree of depth one with single root.
Lemma 4.8. r(Sa) < 2.

---

In the remainder of this section, we describe additional examples of graphs whose resilience can be bounded. We focus on four broad classes 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 for guide to these classes of graphs.
The following definition will be helpful for analyzing graphs that have linear grid shape.
Definition 4.1. For graph G and N, the power graph G", is the graph which inherits its vertices from G and a pair of vertices in G are adjacent when their distance G is at most n.
4.2.1 Hierarchical Data
Hierarchical data arises from distributions that have a tree-like structure, i.e. G 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 be a a-a tree with depth m, then rG) S m Lemma 4.10. Let G be a free with d vertices, then r(G) logg (d)
4.2.2 Sequential Data
A path graph naturally represents sequential data. For more realistic model one may assume that vertex in a path graph is connected to all vertices within given distance, so that nearby vertices are highly dependent, but far away indices are less dependent. Even with this assumption see that, like tree graphs, the path graph's 's resilience only grows at rate Oloo d).
Definition 4.2. The path graph of length d, denoted Lad is the graph (V, F) with [d] and
E = {{ }} j ===]] 11.
Proposition 4.11. Recall that La is the path graph of length d as defined in Definition 4.2. For any s, N, we have
r(L S st.
Here, -1 is the power graph of 11( 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 E N and any constant E N, have
r(L') Ollld))
4.2.3 Spatial Data
Image data is naturally represented via grid graph. The following graph describes a k x 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 LA*Ks is the graph (V, with V [k] [M]] and E = (((i,)), (?',5") (i.5) # (i' ((',j'), - i'l s 1, - j < 1}.
Proposition 4.13. Recall that Luxk be the grid graph of shape k x k as defined in Definition 4.3. For any s, E we have
412
Here, -1 is the power graph of Lug -1) defined in Desinition 4.1.
Examples of grid graph and its power be found in Figure 5 in the appendix. The previous proposition gives us general rate of Vd for grid graphs.
Corollary 4.14. For any l E N and any constant E N, we have
r(Tkx))= O(22 where d = k22
Note that the graph Lixk has d vertices.

---

4.2.4 Clustered Data
Another common type of structured data exhibits clusters: Variables in the same cluster dependent, while variables in different clusters are independent. This type of structure can be modeled with disjoint cliques, where each clique represents cluster community. Let V2 V denote each cluster, with V, VV 0 and V Ví U... U V.,. (i.e. (V:) is partition of V). Let d; - [Vi]. G. - Kd, he a clique (complete graph) on V,, and G = θ G, Then it follows from Lemmas 4.6 and 4.1 that r(G) max; d, In partieular, if d; = O(1), then r(G) O(1). Of course, this simply recovers the well-known result that a density that factorizes into 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 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 graph. Ler (V, be a graph, such that there partition of = i-1 Vi where, if {u. v') E E follows that u E Vi and v' E VV where = j or i and j are adjacent G'. Then r(G) S r(G") max4e[K] [Vi].
=
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.
4.3 Comparison to other graphical properties
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 capture the sample complexity.
Degree The first and most obvious the maximum degree of G. The star graph Sa is an example where the resilience is O(), and hence the sample complexity is (1/s)0(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 (1) while the resilience 22 d).
Diameter The diameter diam (G) of graph G the length of its longest geodesic path. clique Ka thus has diam K2) (since every node is connected to every other node), but r(Ka) d. It is clear even from classical results that clique cannot be estimated any faster than (1/=)². Thus, the diameter also cannot capture the sample complexity.
Sparsity Call density p on d variables s-sparse if p(x) q(xs), where S C [d] with |S| s. Now suppose p is s-sparse and is Markov to a star graph S, on vertices. Then Theorem 3.1 implies that can be estimated with (1/=)0(1) samples (since r(G) O(1)). Thus, taking s - oc, follows that the sparsity cannot properly capture the sample complexity.
In other words, not only does the graph resilience properly capture the sample complexity of structured density estimation, is also not simply proxy for commonly used graphical properties.
5 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. Although our approach sheds light on the intrinsic possibilities and barriers to breaking the curse of dimensionality, the development of practical methods remains an important open problem. For example, can neural networks achieve these rates? Recent concurrent work has provided insight into the use of neural density estimators, see e.g. Bos and Schmidt-Hieber (2023); Cole and Lu (2024); Vandermeulen et al. (2024). Finally, the concept of resilience is a new and unexplored property with significant potential for discovering graphs that yield good estimation properties.
10

---

Acknowledgments and Disclosure of Funding
Robert A. Vandermeulen was supported by German Federal Ministry of Education and Research (BMBF) grants BIFOLD23B and BIFOLD24B. Wai Ming Tai was supported by Singapore AcRF Tier grant MOE-T2EP20112-0002 the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business.
B.A. was supported by NSF IIS- 1956330, NIH R01GM140467, and
References
Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Sample-optimal density estima- tion nearly-linear time. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1278-1289) SIAM, 2017.
Jayadev Acharya, Clement Canonne, Aditya Vikram Singh, and Himanshu Tyagi. Optimal rates for nonparametric density estimation under communication constraints. Advances in Neural Information Processing Systems, 01-26754-26666 2021.
Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Low-rank characteristic tensor density estimation part I: Foundations. JEEE Transactions on Signal Processing, 70:2654- 2022a. doi: 10.11099/PP22222315556..
Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Low-rank characteristic tensor density estimation part II: Compression and latent density estimation. Trans. Sig. Proc., 70: 2669-2680, January 2022b. ISSN 1053-587X. doi: 10. 10.11099TSP.00222315548848 URL https: //doi.org/10 1109
/TSP wtt..s........................ 3158422.
Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- cesa-Bianchi, and Garnett, editors, Advances in Neural Information Processing Systems 31, pages 3412-3421. Curran Associates, Inc., 2018.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017.
Benedikt Bauer and Michael Kohler. On deep learning as remedy for the curse of dimensionality in nonparametric regression. Annals of Statistics, 47(4):2261-22) -285,, 2019.
J. Beirlant and L. Gyorfi. On the L'-error histogram density estimation: The multidimensional case. Journal of Nonparametric Statistics, 197) 1998. doi: 10.1080000445229988833777.
URL httph:tppo.. / //t.///o../oo org/10. 10800/1445259808888333
Clément Berenfeld, Paul Rosa, and Judith Rousseau. Estimating density near an unknown manifold: bayesian nonparametric approach. arXiv preprint arXiv:2205.15717, 2022.
Thijs Bos and Johannes Schmidt-Hieber. A supervised deep learning method for nonparametric density estimation. arXiv e-prints, art. LcXiv:2306.1041,, June 2023. doi: 10.4 10471.
Siu On Chan, Ilias Diakonikolas, Rocco A Servedio, and Xiaorui Sun. Near-optimal density estimation in near-linear time using variable-width histograms. Advances in neural information processing systems, 27, 2014.
Asic Chen, Ruian Ian Shi, Xiang Gao, Ricardo Baptista, and Rahul G Krishnan. Structured neural networks for density estimation and causal inference. Advances in Neural Information Processing Systems, 36, 2024.
Frank Cole and Yulong Lu. Score-based generative models break the curse of dimensionality in learning family of sub-gaussian probability distributions. arXiv preprint 24Xiv:2402.08082 2024.
I. Devroye and I.. Gyorfi. Nonparametric Density Estimation: The T, View. Wiley Interscience Series in Discrete Mathematics. Wiley, 1985. ISBN 9780471816461

---

L. Devroye and G. Lugosi. Combinatorial Methods in Density Estimation. Springer, New York, 2001.
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made: Masked autoencoder for distribution estimation. In International Conference Machine Learning, pages 881-889 PMLR, 2015.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Discussion of: "nonparametric regression using deep neural networks with ReLU activation function". The Annals of Statistics, 48(4):1898 - 1901, 2020. doi: 10.1214/1--0SS1900 URL https: //doi.org/10 1214/19199 A00190001100..1
Evarist Giné and Richard Nickl. Mathematical Foundations of Iefinite--imensionue Statistical Models. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2015.
László Györfi, Aryeh Kontorovich, and Roi Weiss. Tree density estimation. IEEE Transactions Information Theory, (992):1168-1111 2022.
Peter Hall and Xiao-Hua Zhou. Nonparametric estimation of component distributions in a multivariate mixture. Annals of Statistics, pages 201-224 2003.
Peter Hall, JS Marron, and Amnon Neeman. Geometric representation of high dimension, low sample size data. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(3):
427-444, 2005.
Joel Horowitz and Enno Mammen. Rate-optimes estimation for a general class of nonparametric regression models with unknown link functions. Annals of Statistics, 35(6):2589-2619 2007.
Heinrich Jiang. Uniform convergence rates for kernel density estimation. In International Conference on Machine Learning, pages 1694-1703, 2017.
Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonparametric regression on approximate manifolds: Nonasymptotic error bounds with polynomial prefactors. The Annals of Statistics, 51(2):691-716, 2023.
Matthew Johnson, David K Duvenaud, Alex Wiltschko, Ryan P Adams, and Sandeep R Datta. Composing graphical models with neural networks for structured representations and fast inference. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 2946-2954. Curran Associates, Inc., 2016.
Anatoli B. Juditsky, Oleg V. Lepski, and Alexandre B. Tsybakov. Nonparametric estimation of composite functions. The Annals of Statistics. 37(3):1360- 1404, 2009. doi: J0.121400-AAO61..
0004/08--A06.... URL https: /ttp://o...aaa/////// org/10.
Robert W. Keener. Bayesian Inference: Modeling and Computation, pages 301-318. Springer New York, New York, NY, 2010. ISBN 978-0-387-93883994, doi: 10.10077978--0388--98899-999 URL https://doi. org/ 10. 10000000-0000 -11-5-0---8----0 93839-4-831
Ilyes Khemakhem, Ricardo Monti, Robert Leech, and Aapo Hyvarinen. Causal autoregressive flows. In International Conference on Artificial Intelligence and statistics, pages 3520-3528. PMLR.
2021.
Michael Kohler and Adam Krzyžak. Nonparametric regression based on hierarchical interaction models. IEEE Transactions on Information Theory, 63(3):1620-1633) 2017.
Michael Kohler and Sophie Langer. On the rate of convergence of fully connected deep neural network regression estimates. The Annals of Statistics, (9(4))2231-22444 2021.
Hyeok Kyu Kwon and Minwoo Chae. Minimax optimal density estimation using shallow generative model with a one-dimensional latent variable. In International Conference on Artificial Intelligence and Statisties, pages 469 477. PMLR, 2024.
John Lafferty and Larry Wasserman. Rodeo: sparse, greedy nonparametric regression. Annals of Statistics, :6(1))28-44 63,, 2008.
12

---

Steffen L Lauritzen. Graphical models. Oxford University Press, 1996.
Tengyuan Liang. How well can generative adversarial networks (GAN) learn densities: A nonpara- metric view. arXiv preprint arXiv:1712.08244, 2017.
Han Liu, John Lafferty, and Larry Wasserman. Sparse nonparametric density estimation in high dimensions using the rodeo. In Artificial Intelligence and Statistics, pages 283-290.. PMLR, 2007.
Han Liu, John Lafferty, and Larry Wasserman. The nonparanormal: Semiparametric estimation of high dimensional undirected graphs. Journal of Machine Learning Research, 10(0ct):2295-2328. 2009.
Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, and Larry Wasserman. Forest density estimation. The Journal of Machine Learning Research, 12:907-951, 2011.
Daniel McDonald. Minimax density estimation for growing dimension. In Artificial Intelligence and Statistics, pages
PMLR, 2017.
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1-38, 2020.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution estimators. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26517-26582 PMLR, 23-29 Jul 2023. URL /tttps://procee .mlr...mmmimmm....m...mm.m.rm... prwps/ wttpss//v22/keeee ok02aa. html.
Arkadas Ozakin and Alexander Gray. Submanifold density estimation. In Y. Bengio, D. Schuurmans, Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL https//t///rrocceiiinngg paper http:///pppp/.o/oo///ccc///////0
neurips.er cc/ Paper pdf.
Bruno Pelletier Kernel density estimation on riemannian manifolds. Statistics & probability letters, 73(3)2997-344, 2005.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of machine learning research, 13(2), 2012.
R.D. Reiss. Approximate distributions of order statistics: with applications to nonparametric statistics. Springer series in statistics. Springer, 1989. ISBN 9783540968511. URL https: //books, . google. e httpbookssdd-Dxvv.abaee
Henry Scheffe. A Useful Convergence Theorem for Probability Distributions. The Annals of Mathematical Statisties, 18(3):334-44 438, 1947. doi: 10. /0.211//0mm/11777333999 URL https: //doi. 10. 1e14/ homs/117773039.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation function. arXiv preprint arXiv: 06633,, 2017.
Johannes Schmidt-Hieber Deep ReLU network approximation of functions on a manifold. arXiv preprint arXiv:1908.0 00695, 2019.
Guohao Shen, Yuling Jiao, Yuanyuan Lin, Joel L. Horowitz, and Jian Huang. Deep quantile regression: Mitigating the curse of dimensionality through composition. arXiv preprint arXiv:2107.04900 044004 2021.
Shashank Singh and Barnabás Póczos. Minimax distribution estimation in Wasserstein distance. arXiv e-prints, art.
February 2018. doi: 10.48550/arXiv. 11..50/aXiv...02.08383333 1802.08855.
Shashank Singh, Ananya Uppal, Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnabás Póczos. Nonparametric density estimation under adversarial losses. Advances in Neural Information Processing Systems, 31, 2018.
13

---

Le Song and Bo Dai. Robust low rank kernel embeddings of multivariate distributions. In C.J. Burges, L. Bottou, M. Welling. Z. Ghahramani, and K.Q. Weinberger, edi- tors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https::/ wew.eeedddinnnnnnnnnnnee...e neurips cwterris.cccpappppee 45955499602655001154446622-----3 Pap.r..ddf.
Terence P Speed and Harri T Kiiveri. Gaussian Markov distributions over finite graphs. The Annals of Statistics, pages 138-150, 1986.
Charles Stone. Optimal rates of convergence for nonparametric estimators. The Annals of Statistics, 8(6):1348-1360, 1980.
Charles J Stone. Optimal global rates of convergence for nonparametric regression. The annals of statistics, pages 1040-1053, 1982.
Charles Stone. Additive regression and other nonparametric models. Ann. Statist,, 13(1):689-705 1985.
Rong Tang and Yun Yang. On empirical bayes variational autoencoder: An excess risk bound. In Conference Learning Theory, pages 4068-4125. PMLR, 2021.
Rong Tang and Yun Yang. Adaptivity of diffusion models manifold structures. In International Conference on Artificial Intelligence and Statistics, pages 1648-1656. PMLR, 2024.
A.B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics, New York, page 214, 2009. cited By
Ananya Uppal, Shashank Singh, and Barnabás Póezos. Nonparametric density estimation & con- vergence rates for GANs under Besov IPM losses. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Ad- Neural Informa- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9097,9997, 2019. URL https: ptttpps:/prroee /ttp://ppoeee.....//ee/e/ee/s.se wwweeedinnnnnnuriiiie...e.e nwwrine www.iip..cpppapeeeeeeeeeeeeeeeee httpppppp///11///eeeeeeeeee 0009444614004400001144444ddaddd1 www.4bbbo22de2220aarrreaatatat.. Abstract html.
vances in Neural Information Processing Systems 32: Annual Conference
Ananya Uppal, Shashank Singh, and Barnabas Poczos. Robust density estimation under Besov IPM losses. Advances in Neural Information Processing Systems, 33:5345-5355, 2020.
Robert A Vandermeulen. Sample complexity using infinite multiview models. arXiv preprint arXiv:2302.04292. 2023.
Robert A Vandermeulen and Antoine Ledent. Beyond smoothness: Incorporating low-rank analysis into nonparametric density estimation. Advances Neural Information Processing Systems, 34: 12180-12193, 2021.
Robert A Vandermeulen, Wai Ming Tai, and Bryon Aragam. Dimension innepeeninnnnndeedeeeete rates for structured neural density estimation. arXiv preprint arXiv:2411.15093 2024.
Antoine Wehenkel and Gilles Louppe. Graphical normalizing flows. In International Conference on Artificial Intelligence and Statistics, pages 37-45, PMLR, 2021.
Yun Yang and Surya T Tokdar. Minimax-optimal nonparametric regression in high dimensions. Annals of Statistics, 43(2):652-674, 2015.
Yannis G. Yatracos. Rates of Convergence of Minimum Distance Estimators and Kolmogorov's Entropy. The Annals of Statistics, 13(2):668 774, 1985. doi: 10. (0.12114/o//1176645553. URL htttps://diis org/10 10 2214/aas aos/ 1176349553.
Kaihong Zhang, Heqi Yin, Feng Liang, and Jingbo Liu. Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. arXiv preprint arXiv:2402.15602, 2024.
14

---

A
Grid Figure
Figure 5: Comparison of Tax3 (left) and 1x (right).
B Proofs on Density Estimation
We begin by introducing some objects and notation that will be essential for proving the main theorems.
For any E N, A be simplex Let = (1,2....) For any m N, let [m]] - (1, m... in R2 i.c.
A
E
R
1 and 0i O for any i E [6]
For any d, b N, let Tap be the set of probability tensors in H This can be thought of as the joint probability tables over variables with states [6]. For any d, b and T Ta, we say a random variable X ~ if
P(X A) TA
for all A E [b]d.
For any graph G with vertices, let (G) C Ta.., such that, for 7' E TT(G) and (X,,..., Xa) T, then X X...... Xa satisfies the Markov property with respect the graph G. We consider the domain [0, 1)d and split it into bins per dimension, i.e. there are l bins in total. For any d, b e N and multi-index E [b]d let Ad,.AA be the bin indexed at A and Ad, be the set of all bins, i.e.
4 -
Ai
A4A.A
II
and Adp (AaE. IAE [6]d]
b
For any d,b b N, let Ha,b be the set of all histograms with the bins from Ag,b, i.e.
Hdg { f: +
Σ bT XAaasa where x is the indicator and T Tabb
AE[B]
Let Ua,b Ta. > Ha.b be the natural L linear isometry between the spaces.
For any d N and 0, let Da be the set of densities on [0, 1)d and Da.L C Da be those densities which are L-Lipschitz continuous.
Definition B.I. For A, some subset of a Euclidean tensor space or L function space, we define
N (A,e)
min [C] CCA
such that, for all A, there exists E C' where ||a c|]ı 5
15

---

In this work we will use the following version of the Markov property: for I, C V, with I and intersecting or adjacent, X, TL X, Xvyros- Note that this property is satisfied when the "global" Markov property is satisfied.
Lemma B.1 (Lemma 3.3.7 from Reiss (1989)), For probability measures
Ii-
Ii v// s
Eis ||; - v-ll--
Lemma B.2 (Lemma A.1 from Vandermeulen and Ledent (2021)). all b and 0 e S
N (At,s) - (26/a)".
Lemma B.3 (Theorem 3.4 page of Ashtiani al. (2018), Theorem 3.6 page of Devroye and Lugosi (2001)). There exists deterministic algorithm that, given a collection of distributions
Pi..... PM, parameter E 0 and least (3g(3M+16) iid samples from an unknown distribution outputs an index j E [M] such that
Ip, pll S 3
min Ipp - pll + 4E M
with probability at least - 3
B.1 Preliminary Technical Results
This section contains intermediate technical results which will aid in proving more core results.
Lemma B.4, For any < E < 1, any b, t E N and any graph for i [t], we have
N
To
G
N (Th
i=1
i=1
Proof of Lemma B.4. Let C₁ be any (s/t)-cover for To (G:) such that N (To (G:) = =[c for all [6.. we manage to argue that the set
(T1 x T. E C, for all i [f]
then we immediately show the statement since ( i= G.),
is an E-cover of To
N
To
Gi e s S|
II C. CI II (Th (G.),
Now, to show that C' is an E-cover, we observe that any T E To (+) has the form of Ti x ..... x T₁ where 7, E To (G:) for all i [4] since we recall that + G; is simply union of the graphs with no edges across different connected components which implies the vertices in different connected components are independent. Since C, is an (e/t)-cover of (G.). there is a T; e C; such that IT; Tilla S e/t. By taking 7 = Ti ... x T₁ E C, there exists T C such that, by Lemma 1, we have
T Th S Σ
(s/t)= =E.
Lemma B.5. For any 0 < 1, any any b E N, any graph G and any vertex in G, we have
(T(()), < N (T,,, N (T& (G
Proof of Lemma B.5. Without loss of generality, we assume v = 1. Suppose the graph G has vertices. Let Co be any (1 a)s-cover of (TGG) (1}) such that N (To (G) (1)), a)s) (Co]
16

---

and C1 be any aoveover of T.. such that N (71,6, aε) = |C1/- We now construct set C' E TG(G) as follows.
C {T] TΛ 8Λ,
T((A)) AA)
for any [6] where T ..... T Co and 8 Ci}.
If we manage argue that the set C' is E-cover of To(G), then we immediately show the statement since
N (Tb(G), [C] = |Ci|
|Col (7i,6, as) N (T6 (G) \. (1)),11-00 (1-a)e)"
Now, to show that C is an E-COVer, we observe that, for any T E (G( and A E [6]", we can express T
Ta 8A. Ag) for some T'.,...,T?" To(G' \ {1}) and E Ti.b.
(1)
Since Co (resp. C1) is an (1 aree-cover of Te(G \ (1)) (resp. an ag-cover of Ti,)), there exist
T()) (h) E Co and 8 C1 such that
| (1) 1 1 (1 - a)e for all i E [b] and |āō 5|11 S ae.
(4)
Then, we take T E C' where
TA JA. -(Ai) (Ag...As))
for any A [6]d
and we have
1 - Th = Σ
|, T(Ai) - 5A ((Ai))11
A1=1
b
| T((i)) 8A.
T(Ai)l12
11 -(Ai)) -SA, -T(i)) 1|1.
11=1
11
By using (4), we further bound each term
Tō ((1)) 5A -((11)11111 jā 3511-117(A11111 1 -|0-11111
1 S ar
and
b
Σ | T(Ai) 5A (((i)) Σ 8Λ (17(1)) - -((ii)) < A==1
Σ
da (1 - a)e (1 a.e.
A==1
A==1
Combining these two inequalities. we conclude that, for any T (G(),, there exists T E Cuch that | - T & ae + (1 - a)s =c.
B.2
Controlling Bias and Variance
Like many the analysis of many estimators this proof has two pain parts, analysis of the bias, and the analysis of the variance.
B.2.1 Variance
To control the variance we will use the follow bound on covering numbers Proposition B.6. For any b N, any 1 and any graph G whose number of vertices is d and resilience is r, we have
22d
log N (Ta(G), < db" log
Proof of Proposition B.6. We first assume that G a connected graph and prove that
2d
log N (To(G), < db" log
(5)
Note that the exponent in the factor d' r as opposed to r + 1 the original statment. We will prove the statement by induction on
17

---

Base case r = 1:
Note that the graph G is graph with only one vertex. By Lemma B.2, we have
2b
2 2.1'-8
log (TT(G))) & log (( s blog
b- log
thereby satisfying (5).
Inductive step >> 1: Let v be the vertex selected in the first disintegration step of the 7- disintegration and Gi.--. -.....; Gt be the connected components after removing from G. Also, for all i E [4) let r; = r(,,) and de be the number of vertices in G.. By Lemma B.5, we first have
to
log N (To(G), - log N
(T.b, t+ ++1)
b.olog + log N
To(G)) (1l))(u) fu)) ++11
2(t + 1)b
to +b. log (TolG) fu)), t+1
I blog
(6)
by Lemma
By Lemma B.4, further have
Le log N (To( (u)),
log N To(G.), 1+1
t ++
i=1
Note that the resilience of each G; is at most r assumption. We have
(i.e. ri & r- 1) and hence we invoke the inductive
log (Tl(C.), ++1
2(1 + (2(++1)d])
S di b" . llog
by the induction assumption
E bd
11 log
since ri Sr- and + 1, 1. S d. (8)
By plugging (8) into (7) and (6), we have
2(1 + 1)b
2dd'b
log N (To(G), < blog
+ Σ
br log
1=1
bd"bb
< 6" log
1+
d;
since + 1 S d"
1=1
b
db" log
since +
d. Σd 1=1
d.
Now, remove the assumption of G being connected. Suppose G has connected components, G1,..., G. whose number of vertices is d, and resilience is r.. We have
log N (To(Gr), 9)
log N(T((G),E) &
by Lemma B.4
2td
d log
from the case of G being connected
1=1
2d
< db log
since d, < Σdd di d, and t d.
B.2.2 Analysis Bias
Theorem B.7. For any d, E N, any 0, any graph G and any p E DL(G), we have
min p'Uaaa(T((G)
||p - p'l p'l11 S Vdl./b.
18

---

Proof of Theorem B.7. For any d, b E N and A E [6]. recall that Ad,b,A AA be the centroid of A. We define
II==
A 4.). Let
p'
Σ ((A))
XAaaA and p= 1/Z #
(9)
AElbaa
(1 i Add and Z is the normalizing factor, 00 if Aas,
where XAaa,a is the indicator, i.e. XAa (x)
i.e. = Leepo (x))x..
Since the construction requires Z + O, we now first show that when Z 0 the statement holds trivially. When Z = 0, we have
p(AA) = for all A E [b]
which implies
p(x) S L. 11xx -Alla S LVd/(2b) since p E DL(G).
Hence, we further have
/ x)
= Σ S plx)dx S Σ E
p(a)d==
LVd/(2b)dz LVd/(2b).
AEA ZEAL...
AE[DJ DEAGNA
Namely, Lvd/b 2 2 and therefore the statement holds for any p' E Ua, (To(G)).
Now, we assume that Z + O. We will prove the statement by arguing Ua. (T)(G) and 2) [pp ~11 S VdT./b.
To prove 1) 5 E ULP. (Tx(G)): For any partition Vo V U V/ of the vertex set of G such that Vo separates V1 and V2, we would like to show, for any x E [o, 1)d (without loss of generality, we reorder the indices such that (Iv, 2V,,
M(an Ti, vin) ; p(:,; 2
p(: 70 %%)
if ;, # 0
p(: x
;
where we use to indicate integrating with respect to the corresponding variables, i.e.
pl::: (x%)
- (v3) (av, Tv, ( )d(ays, vv2)
01: = =/n, E(0.)41 plzvi vig oi )drv
p(ai;:: .2%))=
pla ay,, v. ddrv.
and di (resp. d2) is the size of Vi (resp. V2). It equivalent show
p iis vto) pl: : v = p(ri; : .i:) p(: at 216).
(10)
We now analyze each of p(r .i, mt p(: v. PZ ..% P(: 2t oy Let À (resp. X²) be the closest centroid to x for any x E [0, d)d (resp. x²). For (2 my v% we have
p(ay, Ni, xV,)= z p((>i Nis, X1,)
p(Nig: ; :.i%) :p(: Mig11i
since E DG and Vo separates V and Vg.
Zp(: )ir))
(11)
19

---

Here, recall that we use to indicate integrating with respect to the corresponding variables, i.e., for any centroid À including X*
p(Av: :vo) L 22,
,Vv Avo dovv
p(: Av,
plrv, \v, Xv ddnii
E(0.1)
Seev (ww plan, FVn, Nvo ;V))
p(: ;(;;;A\v)) (v6)
For ; have
)
[ (avy :1g))_))
p(: v5o)
plan, V vv )ov
1
Z (ov ,V,
3V,, D vva))
Since, for any E [6] 7l (zv, 2V2, = p(\vi \v, 1t. for all (IV, IV, E Adsb by (9), we have
J Jovv av,
f'( IV,, -ig zVa)
bd p(>v, Av.: Avo))
By plugging it into the equation for p(: voVo),, we have
Σ
Zhd, +d p (vi, Avz \in)
1
centroid : Av,
Aio
p(Avi;: \ir :p(: Avg 2i1o
Σ
(12)
2bd do dopp: , \ix)
centroid A Avo
A
For 7' (x ;, ,,,)). we have
p(z (22))
Σ
Zbda p(x 11o)
centroid (Avg.Av)) (Ai Airo)
p(Ai : ~11)) -p(: ,3V3, 15r)
Σ
(13)
7bdap(: -11))
centroid A (Avg Avo) Ni00
Similarly, for (:: aty; ), we have
p(: \ix; :p))..((())) :p(Av; ;, ;W1)
p(: A.
Σ
(14)
Zbdpp( 2.v))
centroid A (Avg Avg)
(M Ni,)
By using (11), (12), (13) and (14), we can conclude (10).
To prove 2) |pp - 1 S VdL/b: We first express
||p p < |pp p' 1 + 17 - Pll
by triangle inequality.
(15)
Note that / may not be probability density.
For the first term ||p 77 1l. we have
1l11 = [ J (p(x) - (Mx) (x)
Σ E - (x))dd.
1pp
(16)
AE(Diu ZEAA,
For any & E Ad we have 7'(x) = p(Aa) by the definition of P.. Also, since E Dr. satisfies the T- T-LLipschizz condition which implies
p(x) - (x) = 1p(x) p(Ax) & L. 1| - >all2 $ LVd/(2b).
(17)
20

---

By plugging (17) into (16), we have
lp p' -
Σ AE(ble ZEAaS,A
LVd/(2b)dr (2b)
(18)
For the second term 11 p 1, we observe that p is simply scaled version of 5/ by factor of 1/Z. Namely, we have
|P'11 = Z and 1 1z -1 since |i 1.
By (18) and the fact of ||p|| 1, we further have
2 - 1| | 1 - llp 1/11 s Lvd/(2b) which implies
1 - -P1 I LVd/(2b)
(19)
By plugging (18) and (19) into (15), we have
lp - 1|1 E Lvdd((2)) + IVd/(2b) LVaab.
B.3 Proof of Main Theorems
With the previous results established we can now prove the core sample complexity results this work.
Proof of Theorem 3.1. Recall that Lemma B.3 states the following. There is a deterministic algorithm that, given collection of M distributions C = .P1.....PM.
(M)), ). any 0 < 1 and at least log /8)
2za
i..d. samples drawn from an unknown distribution outputs an index j E [M] such that
lpj plla 3 min ||p pll + 4 with probability at least 1 3
iE(M]
We will the algorithm from Lemma B.3 by taking the collection C to be the e-cover for (G)
Here, we determine E N later. By Proposition B.6, we have
log M log Cl S db" log( 2d
and, by Theorem B.7, there exists a E Ua.((T(GG) such that
VdL lp 1p-p'li < b
which implies there exists p" E such that
VaL +e.
|pp p"1l1 S llp - p'll2 11 p"1l1 S
Namely, whenever n 2 returned by the algorithm in Lemma B.3 satisfies
log( 2
+ log(3/6) 20
i.i.d. samples are drawn from the distribution
22
1/ p/1 VdL
3VdL
5 with probability at least
+
4
+
3
Now, by picking = 0 vdL) ), the desired result follows.
Proof of Theorem 3.2. The proof is the same in Theorem 3.1 except that need to another g-cover for UGes (G). For any G g, let Ca be the E-cover for (G). By taking Uses Ca to be the s-cover for Uceg TG(G), we have
log M logl Cl log (aal)
GeG
By Proposition B.6, each of |Cal is bounded above by (2 ydb" and, by considering all possible graphs, |g] bounded above by 2dh In particular, when 1, we have [g] Hence, we have
log M < dbb log( 2d 11
+ d²
ifr 1
dbb log( 2d2
if
and we conclude the desired result by following the rest of the proof in Theorem 3.1.
21

---

C Proofs on Graph Resilience
For proofs in this section it will be implicit that graphs with a subscript, G,, are equal to (V,, E,). For proofs in this section we will introduce a useful concept we term pre-disintegration of a graph. Definition C.I. For any graph G (V, E), we define pre-disintegraatinn of G to be tuple of subsets of V which satisfies the properties 1, 2, and, in Definition 3.1 of disintegration, noting that some entries of pre-disintegration may be the empty set, including the first entry.
In other words, the only difference between pre-disintegration and disintegration is that, in each step. we do not have to select a vertex every connected component. The length of pre-disinfegration, D, is defined to be the largest such that D, is nonempty and we call such pre-disinteeration a preeddiinteegationn. We now have the following lemma on pre-disintegrations.
Lemma C.1. For any graph G, if there is a E-pre-disinteerraton of G. then r(G) S
Proof of Lemma C.I. Let be the set of all pre-disintegration of G. For any D D and any vertex E V where V is the vertex set of G, we define D to be a function from V to N such that (v) is the index i where 8 E Dj. We will now define a partial order on D. For any D and D' in D, we say D S D' (v) & (w) for all v E V. Namely, every vertex v appears no later in D than in D'. From the assumption, there exists a e-rre-disinterration of G. D. Similarly to the definition of the length a pre-disintegration, trailing empty sets are simply ignored to satisfy the antisymmetry property for a partial order. Hence, the set {D E D D < D is finite and there must exist minimal element, D By removing trailing empty sets from D", the length of D' is no larger than L.
Now, we need to show D is a disintegration. Since D' is a pre- pre-disintegratinn, it satisfies the properties 1, 2, and, 4 in Definition 3.1. Namely, we need to check the properties 3 and 5. For 3, we prove by contradiction. When D* violates 3, there is connected component G' of G such that no V E V", where V is the vertex set of G", is in Dj. Let o' be arg mingev Dv" and i' be D (o'), i.e. the earliest vertex in V' appears in D We construct a new pre-disintegration D by setting D = D* except that Di = Dÿ U (v/} and Dü- D2 {e/), i.e. we move v' to the first step. Hence, we have 5 < D and D * D" which contradicts the minimality of D We can perform the identical argument to show 5.
Equipped with Lemma C.I, we can now commence with the proofs from the main text.
Proof of Lemma 4.1. We will assume Vi,..., Vm contain distinct elements for convenience. We now prove the statement by showing the following two inequalities: 1) max4e[m] r(G.) 2 r(Diemm) G.) and 2) [mx r(G))= I r(( (E(m) G.).
For 1) [mx rG,)) 2 r(4 kE(m) G.): Let r be the maximum of the graph resilience of G,, i.c. maxie[m] (G:), and ( be r (G..)-disnttggrationn for i E [m]]. We construct a r-tuple D by setting the j-th step to be D, = Usemm] D.0) It is easy to check that D satisfies Definition 3.1 and hence D is r-disintegration of + (eemm G. By Definition 3.2, the inequality 2 r(D.e(m) G.) follows.
r r(( sejm) G:): Let be the graph resilience of + iiemm G i.c. r( ① ie(m) G.), and be a r-disintegration by setting
For 2) max4emm] r(G.)
b of Die(m) G,. We construct m tuples ((1) ((m)
= (oEVVVV
for all j E [m]] and i E [r].
It is easy to check that, for each [m]] D satisfies Definition C. and hence DV) is r-pre- disintegration of Gj. By Definition 3.2 and Lemma C.I, we have r(G:) S r for all i E [m] and
hence the inequality maxi[(m] r(G.) I r follows.
22

---

Proof of Lemma 4.2. We will prove for the case where |V = 1. Note that the lemma statement follows from repeated application of this case,
We will proceed by contradiction. Suppose there exists G and v such r(G) 2 r(G \ {o}) + Let D be a rG {v)) ddiiinteggaatonnn of G \. {e}. If we define a tuple D with D1 = o and Di+1 = D, for of G. The contradiction follows from
all i, it is clear that D is (r(G) \ {u}) + the application of Lemma C.I.
Proof of Lemma 4.3. We will prove for the case where |E 1, the lemma follows from repeated
application of this case. Without loss of generality let E" = (1, 2). Let D be an r r-disintegration of G. Let D be (r tuple with Dj {1) and D; D;-1 {1) for E (2....,
r + 1}. Then D is an pre- pre-disnttegration G' with length r + 1. This case follows from Lemma C.1.
Proof of Lemmn 4.4. Let D be ar r(C))-disittegration Let D be the sequence of subsets of V" when one removes the elements of in V \ V' from D. Clearly, D is pre-disintegration of G", with length at most r(G). The lemma follows from application of Lemma C.I.
Proof of Lemma 4.6. is clear that when with dl vertices a complete graph that r(G) d. For the reverse direction, suppose that G is graph with V [d] with no edge between d - 1 and d. We can define a pre-disintegration where D, = {i} for i E [d 2] and Da-1 = {d 1, d). The lemma follows from application of Lemma C.I.
Proof of Lemma 4.7. When E = clearly D1 = V is a disintegration.
If E * 0 then there must exist two vertices in some component D1 V does not satisfy the component property of disintegration, thus D2 * for any disintegration of G.
Proof of Lemma 4.8. One can simply choose the center vertex as the first entry of a disintegration and the remaining vertices as the rest.
Proof of Lemma 4.9. We construct a rttple D as follows. For all i E [r]. set D; to be the set of all tree vertices at the i-th level in G. Here, we define the root node to be at the first level. It is easy to check that D a r-disintegration. By Definition 3.2, we have r(G) S r.
Proof of Lemma 4.10. Let V be the vertex set. For any vertex U V, let ai be the maximum number of vertices in the connected components after removing v. We would like to show that there exists a vertex 8" such that a,,- I 1 We prove it by contradiction. Let v' be arg min a, and Vi,..., Vee be the vertex sets of the connected components after removing v'. We have ag > [a_ which means that there is connected component whose number of vertices is strictly larger than [ Note that there is only one such component since the sum of the number of vertices of other components strictly less than d 1 - l WLOG, let V1 be the vertex set of that component. Let r be the vertex in V1 sharing an edge with v'. We want to argue that ag" < a,r which contradicts the definition of v'. To see this, examine the number of vertices in the connected components after removing v". We use the fact that G is tree. For the component whose vertex set is U/ V, (v'). the size is strictly less than (d - [5] = d - 1 S ag. For any component inside Vi, the d 1 < aw., Namely, we have an < aw. Therefore, there exists a vertex v*
size is less than
[
such that ag- < 1
23

---

Now, we remove e" in the first step and all the connected components, GI...., C1, has at most vertices. By induction, we have
r(G) S r(G) \ {e))) +1 by Lemma 4.2
= D G +1
max r(G,) +1 sE[(]
by Lemma 4.1
I (1og2(15.) d
+ 1) +1 by the inductive assumption
= (d) +
Proof of Proposition 4./1. We will prove the statement by induction on 8.
Base case s = 1: When 8 1, we observe that -1) L, is complete graph with t vertices.
By Lemma 4.6, we have r r(T.)) = 1.
Inductive step s> 1: Let V c CV be [t(20-1 + + i [t]] Note that [V = t. By Lemma 4.2, we have
r(L1(2--)) S ((L V\) +t.
In other words, we first remove the "middle" vertices from the graph. By the definition of path graphs (Definition 4.2), it is easy to check that there is edge between and j for i ,,....,((2... t(2.-11221 1) and j = f(2--1 - 1) + I,...,tt ,(2" - 1). Therefore, there are two connected components and clearly each of them is isomorphic to L (12--111) Let G1 and G2 be the two connected components, i.e. -1) \ V G1 @ G2. Then, we have
r(L & r(1 @ +t
max (G2)) + by Lemma 4.1 (s 1)6 I. by the inductive assumption
sl.
Proof of Corollary 4.12. Let s be [log. d + 1)]. By the definition of path graphs (Definition 4.2), we have L2 & -1) (recall that S means being isomorphic to a subgraph). Hence, we have r(Lt) I r (()) by Lemma 4.4
s by Proposition 4.11
Otgg
Proof of Proposition 4.13. We will prove the statement by induction on s.
Base case = 1: When 1, we observe that LE -1x22-1))))-- Lixe is complete graph with (2 vertices. By Lemma 4.6, we have r(Lixe) = 12 < 41221
Inductive step > 1: Let d' be 1(28-1 1). Let V be
V' A (ld' +i,)) i [t]. [t(2" 1)]} U ((i, d' +5) lie [t(2" 1)], e [t]. Note that [V 12 412dd < 41 By Lemma 4.2, have
- < - \ V') 2
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 easy to check that there is no edge between (11.f) and (iz, j2) if one of the followings happens:
24

---

d' t(2 1
-1)
b
t(2 -1)
d' = 1(2
G1
V
G2
V
V
W
d' = f(2
G3
V
G4
Figure 6: Illustration of V G1, G2, G3, G2 in the proof of Proposition 4.13
1 1, 1.....,,(20 ,t(2-=1 1) and 1n = t(2 - 1) + t 1. t(2" - 1) j1 1, ......,((2-- 1) and j2 t(2 1) + I,...,.112 t(2" 1).
Therefore, there are four connected components and clearly each of them is isomorphic to L -1x Let G1. G2, G3, G₃ be the four connected components, i.c. -1)0-
V' G. 2 G2 o Gs @ G4. See figure 6 for the graphical illustration. Then, have
r(L1 1)) r(Gi G2 @ G3 @ G4) 4/22-1 rGaa), ((44) + 4122-11 by Lemma 4.1
<
4122-11 + 2 by the inductive assumption
21.22a
Proof of Corollary 4.14. Let s be flog2(# + 1)]. By the definition of grid graphs (Definition 4.3), we have Eixt & T2 11x (recall that < means being isomorphic to a subgraph). Hence, we have
r(T)ex)) - r (T -1)((=1))) by Lemma 4.4
$ 4f22" by Proposition 4.13
= O(f = Vd)
Proof of Lemma 4. 15. We will assume Vi....,
., V& all contain m vertices and for all for all v, of E V,, is adjacent to o' (all of the blocks fully connected). We will prove the lemma for this case, the lemma statement then follows from application Lemma 4.4.
We will denote the vertices of V; as Ui,,,.... Vi.m- Let D' be I-disintegration of G'. Let D be t m-tuple, where D.,, = {vr, E D = = j). If one considers in lexicographical order, then it is clearly pre-disintegration of G with length mt. This case then follows from Lemma C.I. D
25

---

D Optimality of Rates with Respect to d and r
Consider a fixed dimension d and resilience r. Let G be graph where vertices I,..., form complete subgraph, and vertices r 1,...,d d are isolated (not adjacent to any other vertex). Let L > O, and suppose we have an estimator that can estimate densities in (G. at rate OO -(11/(2+-)) for some 0. Letp E D,, r. and X X,,...,4 X, p. We will construct an estimator for p using the aforementioned estimator. Define X,,..., Xa ~ p as follows:
(X...... X,) (X,....,,
, Xa sid Unif([o, 1)),
where Xr) and (Xr+I..... Xx) are independent. Note that ý E (G). Let á be an estimator for p such that
1 1l1 E ( (n-1/(r+2-o))
Let L denote the law of random vector. It is well known that for any function f from one Euclidean space to another, [I{(((()) (((())) [|((X) L(Y) (see Devroye and Lugosi (2001), Section 5.4). We will use f (x1,-.., Ta) 4 (x1,..., x,). Let Yi...., Va ~ p. Using L((Y1, ((((),.-..) Yx)) estimator for p, we have:
|C((() Y.)) p|l ||((()) Y,)) C((X) XI))l
I [C((()...... Ya)) - (.a))
|/ Pll1
((n-1/(r-2-5))
This shows we can estimate all densities in D,, at rate (n 11((t2+2--)) while the known optimal rate is O (n ()(++)))) Thus, for any and d, there exists graph with d vertices and resilience such that estimation of densities in (G) can be no faster than O (n (n-1/(++2)).
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction reflect the paper's contribu- tions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification:
We have provided the full proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer:
[NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececccccccccct httpa//gggiieee/eeeuuuuiiiiiiiii
/CodeSubmic ssionnollll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp///eerrpp.ee/ee//ee cc httpbiic/eeiicctudeeeeeneeeeeeee
Answer: [Yes]
Justification: Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our result is theoretical result.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
30

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
31

---

Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere 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.
32


Reviews:
[{"review_id": "9JUqUdf0Mi", "reviewer": "Reviewer_P9wL", "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.", "questions": "Why is the manifold assumption violated in structured data if the effective dimension is lower than the embedding dimension? \n\nAre you willing to provide a code that allows to use your findings in practical data?", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The work is original and technically sound, claims are generally well supported (with one exception that I will mention later on). \n\nThe ideas of graphs resilience and disintegration are interesting and are nicely defined.", "weaknesses": "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.    \n\nThe 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.  \n\nNo practical applications are shown.  \n\nFrom 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__“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.”__\n\n__”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.”__\n\nThe 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. \n\nA 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. \n\n\nAs 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.\n\nIt'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.\n\n__”Are you willing to provide a code that allows to use your findings in practical data?”__\n\n__”No practical applications are shown.”__\n\nPlease see the General Author Response.\n\n__”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.”__\n\nKernel 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pXJX5yXyv7", "reviewer": "Reviewer_HdwX", "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.", "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.\n\n2. 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)?\n\n3. Can something be said about the optimality of the bounds? In particular, is the graph resilience the right quantity for this problem? \n\n4. In Corollary 4.12, why not show the dependence on t explicitly in the bound?\n\nMinor remarks:\n\n- I think there is a typo towards the end of line 182. Another typos in line 252 (\"... tend to have ...\")\n\n- In the statement of Theorem 3.1, it might be good to specify that $G$ is known.", "limitations": "I do not see a dicussion on limitations in the main text.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. The paper is written very well with a clear exposition which makes it easy to follow. The problem is well defined and motivated, along with clear notation throughout. The related work is also thorough and provides a good overview of the literature.\n\n2. The results are to my knowledge novel, I am not aware of similar results for this problem setting. I believe the paper would be of interest for researchers in high dimensional statistics, and related problems.", "weaknesses": "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.\n\n2. It would have also been useful to provide some simulation results on synthetic data as this would have helped empirically validate the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__”It would have been helpful to provide a proof-sketch of the main theorems in the main text…”__\n\nWe are happy to incorporate this into the final draft.\n\n__”It would have also been useful to provide some simulation results on synthetic data as this would have helped empirically validate the theoretical results.”__\n\n__”What is the running time of the algorithm w.r.t n, d and r?”__\n\nPlease see the General Author Response.\n\n__”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)?”__\n\nThis 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.\n\n__”Can something be said about the optimality of the bounds? In particular, is the graph resilience the right quantity for this problem?\"__\n\nAs 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. \n\nWe _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. \n\n__”In Corollary 4.12, why not show the dependence on t explicitly in the bound?”__\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CTxDq43Frh", "reviewer": "Reviewer_yapz", "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.", "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": "Can the authors discuss some possible extensions? For example, what does the resilience look like for directed graphs, or for non-Markovian graphs?", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The concept of resilience is novel. The definition is clear, esp Figure 3. \nSection 4 is very well-written, which helps the audience a lot to understand the concept of resilience.", "weaknesses": "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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__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?__\n\nAt 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.\n\nRemoving 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:\n$\\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$\n\n__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.__\n\n\nWe 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!\n\n\nMoreover, 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.\n\n__Can the authors discuss some possible extensions? For example, what does the resilience look like for directed graphs, or for non-Markovian graphs?__\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# General Author Response
We thank the reviewers for their thoughtful reviews.

Overall the response from the reviewers was quite positive:

__Presentation:__

* HdwX: "The paper is written very well with a clear exposition which makes it easy to follow." 
* yaps: "The definition is clear, esp Figure 3. Section 4 is very well-written, which helps the audience a lot to understand the concept of resilience."
* HdwX & yaps: Rated presentation "4: Excellent"

__Novelty and Significance:__
* P9wl: "The ideas of graphs resilience and disintegration are interesting and are nicely defined."
* HdwX: "The results are to my knowledge novel, I am not aware of similar results for this problem setting. I believe the paper would be of interest for researchers in high dimensional statistics, and related problems."
* yapz: "This concept is different from more its well-known counterparts.... Both the concept and the theory are sound, the contribution to the literature of density estimation is solid."
* yapz: " The concept is beautiful..."

Two of the reviewers had comments regarding the algorithm in our theorems, we will address that below.

# Algorithm

__Reviewer P9wL: “Are you willing to provide a code that allows to use your findings in practical data?”__

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

__Reviewer HwdX: “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.”__


As with most theory papers in NeurIPS, our main contribution is not a practical implementation or application to real data. Our main contribution is a novel and nontrivial analysis of the structured density estimation problem, and the introduction of a new graphical parameter that shows how the curse of dimensionality can be broken.

That being said, the algorithm in our main theorem is based on the “Scheffé tournament” estimator, which is a classical algorithm in learning theory. For example, this algorithm was also used in the recent theory paper “Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes,” which was awarded “best paper” at NeurIPS 2018 (which also did not include algorithmic details or runtime analysis). We stress that our main contribution is not this algorithm (obviously, it has been used previously), but the analysis of its performance in structured density estimation, and the surprising result that it can evade the curse of dimensionality. While the algorithm can be implemented in principle, this is not its main appeal.

Per HdwX’s suggestion we will include some discussion on the proof techniques which will help convey the computational aspect.

Meta-review: 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.
Decision: Accept (poster)