# Is there an equivalent to VC-dimension for density estimation as opposed to classification?

VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute the capacity of a mixture of N Gaussians, etc? And if so, are there corresponding theorems showing that this capacity-measure can be used to bound the generalization error for density estimation, or used for structural risk minimization (analogous to the classification setting)?

I did find this article which seems like it might come pretty close to answering my question, since they apply structural risk minimization (SRM) to gaussian mixture models, and it looks like they estimate the capacity using "annealed entropy" applied to a class of threshold-based indicator functions associated with the log-likelihood function. However, they don't provide references to theorems/bounds to show whether this is a principled way to assess the capacity of a probability density, but perhaps there is some known theorem that justifies this approach which they assume the reader already knows about? They reference Vapnik's book for more details on annealed entropy.

Also, my understanding is that fat-shattering or pseudo-dimension can be used as a generalization of VC-dimension to the regression context, but I'm unclear whether these are applicable to density estimation. And it looks like the paper linked above used annealed entropy rather than these regression-based capacity measures.

• This paper (Kearns et al., On the learnability of discrete distributions) considers the related problem of PAC learning for distributions dl.acm.org/doi/pdf/10.1145/… This paper considers the sample complexity of learning a mixture of gaussians, which can be thought of as a measure of the capacity: papers.nips.cc/paper/… Oct 22, 2020 at 18:28

For distributions with finite support of size $$d$$, when the error metric is the $$\ell_1$$ distance, the analogue of VC dimension is exactly $$d$$. (In fact, it's pretty much the VC dimension -- since to estimate a distribution over $$d$$ in $$\ell_1$$ is equivalent to agnostically PAC-learning the concept class $$2^{[d]}$$).

For discrete distributions with infinite support, no PAC-type result can be given. Perhaps somewhat surprisingly, a fully empirical (and nearly optimal!) sample-dependent bound on the $$\ell_1$$ distance between the empirical and true distributions can be given, see: https://arxiv.org/abs/2004.12680 (to appear in NIPS 2020).

For continuous distributions, the situation is more subtle. You basically can't estimate anything without some absolute continuity and smoothness assumptions; see, for example the impossibility results: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=139691 https://www.sciencedirect.com/science/article/abs/pii/S0167715298002466 https://www.jstor.org/stable/2242068?seq=1

What's typically done is that we define a class of distributions with certain smoothness properties (Lipschitz, Hölder, Sobolev, Besov) and then design an algorithm that achieves a certain rate for this class, and then argue that no algorithm can achieve a better rate (making our algorithm "minimax" for that class).

• Thanks, do you have a sense for where the linked "annealed entropy" based SRM fits into this? Or is that approach not rigorously justified?
– Andy
Oct 18, 2020 at 21:52
• Well, Gaussian mixtures are a parametric class -- the difficulties there are mainly computational, not statistical. I think if computational limitations were not an issue and you could maximize the likelihood (or solve the polynomial system of equations implied by method of moments) -- you'd get convergence in parameter space at the rate of $1/\sqrt n$. In my note, I discussed non-parametric classes. Oct 18, 2020 at 21:58
• Are you saying this is true with a fixed N number of gaussians, or even if doing SRM with no bound on the number of allowed gaussians?
– Andy
Oct 18, 2020 at 22:02
• @Andy From a cursory reading, it appears that the paper is doing something unsound. It is applying a risk bound developed for binary classes ("indicator functions") to a risk defined with respect to a logarithmic loss, which is not only continuous, but also unbounded. Covering numbers for unbounded classes are much trickier to bound. We just wrote a paper that hit against this barrier, and resorted to an adaptive truncation scheme to circumvent it (write to me privately if curious). Oct 19, 2020 at 10:33
• But in any case, even if the paper were correct, it would be doing something like kernel density estimation -- which, like all other approaches, cannot get away from the impossibility results I quoted earlier. Oct 19, 2020 at 10:34