arXiv:2607.06644stat.MLcs.LG2026-07

提出在复杂空间上快速确定性采样方法,提升数据代表性。

Fast determinantal sampling on general spaces and diffusion geometry

论文配图:Fast determinantal sampling on general spaces and diffusion geometry
图 1 · 摘自论文原文
  • 基于谱核与扩散几何,实现通用空间下的高效采样。
  • 采样精度随内在维度提升,达到欧氏空间最优速率。
  • 适用于流形与加权网络,适合大规模数据压缩场景。

确定性点过程(DPP)作为独立同分布采样的替代方法,近年来被用于构建高效的小批量、核心集等大规模数据的紧凑表示。与传统独立采样相比,基于DPP的采样机制在近似性能上表现更优,即使在指数规模下仍具优势。其关键优势在于可应用于极广泛的抽象空间,而传统非独立采样方法通常仅限于欧氏空间等结构化环境。本文针对超出已知欧氏设定的广义空间,建立确定性采样的显式收敛速率保证,聚焦由关联拉普拉斯算子及马尔可夫扩散算子特征空间导出的谱核。涵盖黎曼流形与加权网络等情形。在紧致黎曼流形上的确定性采样中,采样速率能自动捕捉数据的内在维度 $d_{\text{int}}$;在图结构中,研究了著名的k近邻图和加权随机几何图上的DPP采样,并展现出对内在维度的类似改进依赖关系。总体上,我们的方法实现了 $ig(\text{样本量}\big)^{-\frac{1}{2}-\frac{1}{2d_{\text{int}}}}$ 的保证,与同维度欧氏空间已知速率一致。技术上,我们关联了流形谱的著名Weyl定律,结合马尔可夫扩散理论、狄利克雷形式以及伪微分算子的部分工具,这些方法本身亦可能具有独立研究价值。

原文摘要 · Abstract (English)

Determinantal point processes have recently emerged as a kernel-based alternative to standard independent sampling for constructing efficient minibatches, coresets, and other compact representations of large-scale datasets. In particular, sampling mechanisms based on DPPs are believed to demonstrate better approximation properties compared to classical i.i.d. samplers, even at the scale of the exponent. One of the key strengths of DPP based samplers is that they can be deployed over very general spaces, in contrast to more classical sampling methods beyond i.i.d. which tend to work in very well-structured settings, principally Euclidean spaces. In this work, we establish explicit rate guarantees for determinantal sampling in spaces that extend far beyond known Euclidean setups, focusing on spectral kernels obtained from eigenspaces of naturally associated Laplacian and other Markov diffusion operators. This includes, in particular, Riemannian manifolds and weighted networks. In determinantal sampling from compact Riemannian manifolds, we establish sampling rates that automatically pick up the intrinsic dimensionality $d_{\text{int}}$ of the underlying manifold. In the setting of networks, we investigate DPP-based samplers on the celebrated k-nearest neighbour graphs, as well as weighted random geometric graphs, and demonstrate a similar improved dependence on the intrinsic dimensionality of the data. Overall, our approach achieves guarantees of $\big(\text{sample size}\big)^{-\frac{1}{2}-\frac{1}{2d_{\text{int}}}}$ that match known rates on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for manifold spectra, and leverage tools from the theory of Markov diffusions and Dirichlet forms as well as certain ingredients from the theory of pseudodifferential operators, which could be of independent interest in this area.

采样算法扩散几何流形学习概率模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。