通过图鲁棒性突破高维密度估计的维度诅咒
Breaking the curse of dimensionality in structured density estimation
- 引入图鲁棒性新指标，替代度数控制样本复杂度
- 在任意图结构下实现低维化密度估计，无需稀疏或流形假设
- 适用于序列、层次和空间数据，显著提升估计效率
我们研究在无向图诱导的马尔可夫条件下进行多变量密度估计的问题。在最坏情况下，若无马尔可夫假设，该问题会遭受维度诅咒。本文主要结果表明，在马尔可夫性质下，维度诅咒可被避免或大幅缓解，且适用于任意图结构。现有工作多依赖稀疏性或流形假设，而本文提出新的图结构度量——图鲁棒性，并证明其能控制样本复杂度。令人惊讶的是，样本复杂度并不随局部图参数（如节点度数）增长，而是由图鲁棒性决定。通过具体例子，我们推导出一致偏差界，展示了如何绕过高维密度估计中的维度诅咒。在序列、层次和空间数据等典型场景中，估计速率得到显著提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。