Breaking the curse of dimensionality in structured density estimation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909344223723520 |
|---|---|
| author | Vandermeulen, Robert A. Tai, Wai Ming Aragam, Bryon |
| author_facet | Vandermeulen, Robert A. Tai, Wai Ming Aragam, Bryon |
| contents | 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 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 be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07685 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Breaking the curse of dimensionality in structured density estimation Vandermeulen, Robert A. Tai, Wai Ming Aragam, Bryon Machine Learning Computer Vision and Pattern Recognition Statistics Theory 62G05, 62G07, 62A09, 62M05, 62M40, 60J10, 60J20 G.3; I.5.1 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 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 be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data. |
| title | Breaking the curse of dimensionality in structured density estimation |
| topic | Machine Learning Computer Vision and Pattern Recognition Statistics Theory 62G05, 62G07, 62A09, 62M05, 62M40, 60J10, 60J20 G.3; I.5.1 |
| url | https://arxiv.org/abs/2410.07685 |