Response to Reviewer P9wL comment: On practical applications
__”Is there a practical way to take advantage of resilience to compute densities? Can you show that in a real case?”__
Yes, there is a practical way to take advantage of this. This is related to our explanation of graph resilience in our rebuttal to yapz. Graph resilience essentially gives the most efficient disintegration of a graph, and can be thought of as a sort of “meta-algorithm.” The disintegration gives an ordering as to how to estimate conditional densities, however it would be up to a practitioner to decide how to take care of the one-dimensional and conditional density estimation, which are themselves structured in an inductive way.
More precisely, a disintegration outlines a way to inductively condition out the entries of a random vector. For instance, consider a random vector $[X_1,X_2]$. The disintegration $(X_1)-(X_2) \Rightarrow (X_1) \Rightarrow \emptyset$ corresponds to first estimating $p_{X_2}$, and then, for each $x$, estimating the density $p_{X_1|X_2=x}$. The Lipschitz condition tells us that $p_{X_1|X_2=x}$ doesn’t change drastically as $x$ changes, thus making the problem tractable.
Removing one vertex from __each__ component of a graph captures the idea that, after sufficient conditioning, these components become independent. This allows us to avoid estimating the high-dimensional joint density of all vertices in the graph. Instead, we can estimate the low-dimensional components individually and take their product which is justified due to the following inequality:
$\Vert\prod_{i=1}^d p_i - \prod_{j=1}^d q_j \Vert_1 \le \sum_{i=1}^d \Vert p_i - q_i \Vert_1$
For a concrete example, consider the graph $(X)-(Y)-(Z)$, with the disintegration
$(X)-(Y)-(Z) \Rightarrow (X)\quad (Z) \Rightarrow \emptyset$.
This corresponds to estimating $p_Y$, then estimating $p_{X,Z| Y}$ utilizing the fact that $X$ and $Z$ are independent given $Y$ so $p_{X,Z| Y}(x,z) = p_{X| Y}(x)p_{Z| Y}(z)$ thus instead of having to estimate a two dimensional conditional density, one can simply estimate two one dimensional conditional densities and take the product, thereby avoiding the curse of dimensionality. This example only contains one simple instance of taking advantage of the product structure, but there may be layers of product structure, which is exemplified in our result that the graph resilience of a linear Markov graph grows only logarithmically in dimension. One also need not know the disintegration corresponding to the graph resilience in order to apply this. The resilience simply characterizes the best possible disintegration.
While disintegrations are based on estimating many one-dimensional conditional distributions, one could instead estimate low-dimensional distributions. We would be happy to add an appendix (based on this discussion) outlining how a practitioner can take advantage of the disintegration structure in a more practical and readable way.