Accurate Quantization of Measures via Interacting Particle-based Optimization
Accurate Quantization of Measures via Interacting Particle-based Optimization
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Lantian Xu;Anna Korba;D. Slepčev
中科院分区：
文献类型：
--
作者：
Lantian Xu;Anna Korba;D. Slepčev
近似目标概率分布可以归结为一个优化问题，其中目标函数衡量目标与目标的不同程度。这种优化可以通过近似Wasserstein和相关的梯度流来解决。在实践中，这些都是由相互作用的粒子系统模拟的，其静止状态定义了一个近似目标分布的经验度量。这种方法最近已被推广到设计采样算法，如Stein变分梯度下降，或通过最小化最大均值或核Stein差异。然而，人们对这些方法的量化特性知之甚少，即有限个粒子对目标的逼近效果如何。我们从理论上和数值上研究了这个问题。特别地，我们证明了MMD和KSD在显著优于I.I.D.量化的速率下的量化误差的一般上界。样本。我们进行的实验表明，所研究的粒子系统在实践中达到了较快的速度，并且显著优于贪婪算法，如核羊群算法。我们比较了不同的梯度流，并突出了它们的量化率。此外，我们引入了归一化的Stein变分梯度下降，并支持自适应核，它表现出更快的收敛速度。最后，我们比较了高斯核和拉普拉斯核，认为拉普拉斯核提供了更稳健的量子化。
Approximating a target probability distribution can be cast as an optimization problem where the objective functional measures the dissimilarity to the target. This optimization can be addressed by approximating Wasserstein and related gradient flows. In practice, these are simulated by inter-acting particle systems, whose stationary states define an empirical measure approximating the target distribution. This approach has been pop-ularized recently to design sampling algorithms, e.g. Stein Variational Gradient Descent, or by minimizing the Maximum Mean or Kernel Stein Discrepancy. However, little is known about quantization properties of these approaches, i.e. how well is the target approximated by a finite number particles. We investigate this question theoretically and numerically. In particular, we prove general upper bounds on the quantization error of MMD and KSD at rates which significantly outperform quantization by i.i.d. samples. We conduct experiments which show that the particle systems at study achieve fast rates in practice, and notably outperform greedy algorithms, such as kernel herding. We compare different gradient flows and highlight their quantization rates. Furthermore we introduce a Normalized Stein Variational Gradient Descent and argue in favor of adaptive kernels, which exhibit faster convergence. Finally we compare the Gaussian and Laplace kernels and argue that the Laplace kernel provides a more robust quantization.