Skip to main navigation Skip to search Skip to main content

Accurate Quantization of Measures via Interacting Particle-based Optimization

  • Carnegie Mellon University
  • ENSAE

Research output: Contribution to journal › Conference article › peer-review

12 Citations (Scopus)

Abstract

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 interacting particle systems, whose stationary states define an empirical measure approximating the target distribution. This approach has been popularized 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.

Original languageEnglish
Pages (from-to)24576-24595
Number of pages20
JournalProceedings of Machine Learning Research
Volume162
Publication statusPublished - 1 Jan 2022
Externally publishedYes
Event39th International Conference on Machine Learning, ICML 2022 - Baltimore, United States
Duration: 17 Jul 2022 → 23 Jul 2022

Fingerprint

Dive into the research topics of 'Accurate Quantization of Measures via Interacting Particle-based Optimization'. Together they form a unique fingerprint.

Cite this