提出高效构造光滑散度核心集的新算法，可大幅减少数据量仍保持精度。
Coreset selection for the Sinkhorn divergence and generic smooth divergences
- 利用函数泰勒展开将核心集问题转化为均值差异最小化
- 对Sinkhorn散度只需亚对数级数据点即可达到随机采样的近似效果
- 连接核心集与核求积，适用于图像子采样等实际场景
我们提出CO2算法，用于在通用光滑散度下生成凸加权核心集。通过函数泰勒展开，证明了充分光滑损失与其二阶近似在局部具有等价性，从而将核心集选择问题简化为最大均值差异最小化。该方法应用于Sinkhorn散度，提供一种新采样流程：仅需亚对数级数据点即可实现与随机采样相当的近似保证。为此，我们还验证了熵正则最优传输的若干新正则性质，具有独立研究价值。本方法建立了核心集选择与核求积之间的新视角，链接至经典统计方法如矩匹配和得分匹配。我们在图像数据子采样中展示了其实际应用，并指出了提升算法效率与理论保证的关键方向。
原文摘要 · Abstract (English)
We introduce CO2, an efficient algorithm to produce convexly-weighted coresets with respect to generic smooth divergences. By employing a functional Taylor expansion, we show a local equivalence between sufficiently regular losses and their second order approximations, reducing the coreset selection problem to maximum mean discrepancy minimization. We apply CO2 to the Sinkhorn divergence, providing a novel sampling procedure that requires poly-logarithmically many data points to match the approximation guarantees of random sampling. To show this, we additionally verify several new regularity properties for entropically regularized optimal transport of independent interest. Our approach leads to a new perspective linking coreset selection and kernel quadrature to classical statistical methods such as moment and score matching. We showcase this method with a practical application of subsampling image data, and highlight key directions to explore for improved algorithmic efficiency and theoretical guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。