<p>For distributions with finite support of size <span class="math-container">$d$</span>, when the error metric is the <span class="math-container">$\ell_1$</span> distance, the analogue of VC dimension is exactly <span class="math-container">$d$</span>. (In fact, it's pretty much <em>the</em> VC dimension -- since to estimate a distribution over <span class="math-container">$d$</span> in <span class="math-container">$\ell_1$</span> is equivalent to agnostically PAC-learning the concept class <span class="math-container">$2^{[d]}$</span>).</p>
<p>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 <span class="math-container">$\ell_1$</span> distance between the empirical and true distributions can be given, see:
<a href="https://arxiv.org/abs/2004.12680" rel="nofollow noreferrer">https://arxiv.org/abs/2004.12680</a>
(to appear in NIPS 2020).</p>
<p>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:
<a href="https://papers.ssrn.com/sol3/papers.cfm?abstract_id=139691" rel="nofollow noreferrer">https://papers.ssrn.com/sol3/papers.cfm?abstract_id=139691</a>
<a href="https://www.sciencedirect.com/science/article/abs/pii/S0167715298002466" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/abs/pii/S0167715298002466</a>
<a href="https://www.jstor.org/stable/2242068?seq=1" rel="nofollow noreferrer">https://www.jstor.org/stable/2242068?seq=1</a></p>
<p>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 &quot;minimax&quot; for that class).</p>

CC BY-SA 4.0
2020-10-18T21:52:25.240Z
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
CC BY-SA 4.0
2020-10-18T21:58:20.063Z
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.
Aryeh
CC BY-SA 4.0
2020-10-18T22:02:55.473Z
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
CC BY-SA 4.0
2020-10-18T22:05:00.810Z
I was referring to a fixed number of Gaussians. If the number is allowed to grow with sample size, we're in kernel method territory (non-parametric). Then you need smoothness assumptions on the sampling distribution.
Aryeh
CC BY-SA 4.0
2020-10-19T01:13:04.923Z
I see, but the linked article claims to support SRM (with "unknown" #s of components), based on a finite sample risk bound in terms of "annealed entropy" capacity (eqn 2), not specific to GMMs.  So are you saying this isn't actually possible (as I've interpreted it), or just that there must be some unstated smoothness assumptions implicit in the claim that SRM converges in this case?
Andy
CC BY-SA 4.0
2020-10-19T10:33:59.463Z
@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).
Aryeh
CC BY-SA 4.0
2020-10-19T10:34:53.770Z
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.
Aryeh
CC BY-SA 4.0
2020-10-22T18:36:35.563Z
It makes more sense to ask about the VC dimension of a parametric family (like a mixture of gaussians) as naturally it is infinite for the set of "all" distributions. I think the original question is referring to parametric families (as that is what also makes sense for classification).
Holden Lee
CC BY-SA 4.0
2020-10-23T18:16:58.967Z
@HoldenLee My question was about both, i.e. in the parametric case I wanted to know if there were any capacity measures for densities (analogous to VC for classification), and in the non-parametric case I wanted to know if structural risk minimization could be applied using that capacity measure (again analogous to classification).  It sounds like Aryeh's answer is that probably neither really make sense for densities, but I don't fully understand the reasons yet.
Andy
CC BY-SA 4.0
2020-10-24T17:38:17.497Z
@HoldenLee For a parametric family, the number of parameters is typically the appopriate complexity measure.
Aryeh
CC BY-SA 4.0
2020-10-18T21:37:22.537Z
2020-10-20T11:05:15.363Z
2020-10-20T11:05:15.363Z
Aryeh
<p>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)?</p>
<p>I did find <a href="https://ieeexplore.ieee.org/document/1527798" rel="nofollow noreferrer">this article</a> 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 &quot;annealed entropy&quot; 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 <a href="https://rads.stackoverflow.com/amzn/click/com/0471030031" rel="nofollow noreferrer" rel="nofollow noreferrer">Vapnik's book</a> for more details on annealed entropy.</p>
<p>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.</p>

CC BY-SA 4.0
2020-10-22T18:28:58.640Z
This paper (Kearns et al., On the learnability of discrete distributions) considers the related problem of PAC learning for distributions https://dl.acm.org/doi/pdf/10.1145/195058.195155?casa_token=_uwWtzH86NQAAAAA%3AFo21PmO9IVwixG-LRJT6ba4TIfboQEIfv2d1FGDkB0LS7qEQyQ3fKawSlZjw8MprNfR_hZm9VCOj
This paper considers the sample complexity of learning a mixture of gaussians, which can be thought of as a measure of the capacity: http://papers.nips.cc/paper/7601-nearly-tight-sample-complexity-bounds-for-learning-mixtures-of-gaussians-via-sample-compression-schemes
Holden Lee
<machine-learning><lg.learning><st.statistics><vc-dimension>
Is there an equivalent to VC-dimension for density estimation as opposed to classification?
Andy
# Is there an equivalent to VC-dimension for density estimation as opposed to classification?

(Asked by: username_0 on 2020-10-18)

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](https://ieeexplore.ieee.org/document/1527798) 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](https://rads.stackoverflow.com/amzn/click/com/0471030031) 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.

**Tags:** machine-learning, lg.learning, st.statistics, vc-dimension

> **Comments:**
> **username_1**: This paper (Kearns et al., On the learnability of discrete distributions) considers the related problem of PAC learning for distributions https://dl.acm.org/doi/pdf/10.1145/195058.195155?casa_token=_uwWtzH86NQAAAAA%3AFo21PmO9IVwixG-LRJT6ba4TIfboQEIfv2d1FGDkB0LS7qEQyQ3fKawSlZjw8MprNfR_hZm9VCOj This paper considers the sample complexity of learning a mixture of gaussians, which can be thought of as a measure of the capacity: http://papers.nips.cc/paper/7601-nearly-tight-sample-complexity-bounds-for-learning-mixtures-of-gaussians-via-sample-compression-schemes  

---

## 1 answers

### Answer by username_2 on 2020-10-18. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks, do you have a sense for where the linked "annealed entropy" based SRM fits into this?  Or is that approach not rigorously justified?  
> **username_2**: 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.  
> **username_0**: 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?  
> **username_2**: I was referring to a fixed number of Gaussians. If the number is allowed to grow with sample size, we're in kernel method territory (non-parametric). Then you need smoothness assumptions on the sampling distribution.  
> **username_0**: I see, but the linked article claims to support SRM (with "unknown" #s of components), based on a finite sample risk bound in terms of "annealed entropy" capacity (eqn 2), not specific to GMMs.  So are you saying this isn't actually possible (as I've interpreted it), or just that there must be some unstated smoothness assumptions implicit in the claim that SRM converges in this case?  
> **username_2**: @username_0 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).  
> **username_2**: 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.  
> **username_1**: It makes more sense to ask about the VC dimension of a parametric family (like a mixture of gaussians) as naturally it is infinite for the set of "all" distributions. I think the original question is referring to parametric families (as that is what also makes sense for classification).  
> **username_0**: @HoldenLee My question was about both, i.e. in the parametric case I wanted to know if there were any capacity measures for densities (analogous to VC for classification), and in the non-parametric case I wanted to know if structural risk minimization could be applied using that capacity measure (again analogous to classification).  It sounds like username_2's answer is that probably neither really make sense for densities, but I don't fully understand the reasons yet.  
> **username_2**: @HoldenLee For a parametric family, the number of parameters is typically the appopriate complexity measure.  

---

