# Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation

arXiv: https://arxiv.org/abs/2305.17558 · HTML: https://mlsanity.com/paper/2305.17558/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 63 references that are in the map.
- First posted on arXiv 27 May 2023.

## Builds on (most cited first, 30 of 33)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Stein Variational Gradient Descent as Gradient Flow](https://mlsanity.com/paper/1704.07520/) (2017)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [On the geometry of Stein variational gradient descent](https://mlsanity.com/paper/1912.00894/) (2019)
- [SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence](https://mlsanity.com/paper/2006.02509/) (2020)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [A Non-Asymptotic Analysis for Stein Variational Gradient Descent](https://mlsanity.com/paper/2006.09797/) (2020)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Message Passing Stein Variational Gradient Descent](https://mlsanity.com/paper/1711.04425/) (2017)
- [Stein Variational Policy Gradient](https://mlsanity.com/paper/1704.02399/) (2017)
- [Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces](https://mlsanity.com/paper/1804.10556/) (2018)
- [Scaling limit of the Stein variational gradient descent: the mean field regime](https://mlsanity.com/paper/1805.04035/) (2018)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Stochastic Stein Discrepancies](https://mlsanity.com/paper/2007.02857/) (2020)
- [A Finite-Particle Convergence Rate for Stein Variational Gradient Descent](https://mlsanity.com/paper/2211.09721/) (2022)
- [Learning to Draw Samples: With Application to Amortized MLE for Generative Adversarial Learning](https://mlsanity.com/paper/1611.01722/) (2016)
- [A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1](https://mlsanity.com/paper/2106.03076/) (2021)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [Stein Variational Gradient Descent: many-particle and long-time asymptotics](https://mlsanity.com/paper/2102.12956/) (2021)
- [Towards Understanding the Dynamics of Gaussian-Stein Variational Gradient Descent](https://mlsanity.com/paper/2305.14076/) (2023)
- [A stochastic version of Stein Variational Gradient Descent for efficient sampling](https://mlsanity.com/paper/1902.03394/) (2019)

## Built on by (most cited first, 6 of 6)

- [Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent](https://mlsanity.com/paper/2409.08469/) (2024)
- [Learning of Population Dynamics: Inverse Optimization Meets JKO Scheme](https://mlsanity.com/paper/2506.01502/) (2025)
- [Long-time asymptotics of noisy SVGD outside the population limit](https://mlsanity.com/paper/2406.11929/) (2024)
- [To discretize continually: Mean shift interacting particle systems for Bayesian inference](https://mlsanity.com/paper/2605.14142/) (2026)
- [Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimization](https://mlsanity.com/paper/2503.13115/) (2025)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)

## Abstract (arXiv)

Stein Variational Gradient Descent (SVGD) is a popular variational inference algorithm which simulates an interacting particle system to approximately sample from a target distribution, with impressive empirical performance across various domains. Theoretically, its population (i.e, infinite-particle) limit dynamics is well studied but the behavior of SVGD in the finite-particle regime is much less understood. In this work, we design two computationally efficient variants of SVGD, namely VP-SVGD and GB-SVGD, with provably fast finite-particle convergence rates. We introduce the notion of virtual particles and develop novel stochastic approximations of population-limit SVGD dynamics in the space of probability measures, which are exactly implementable using a finite number of particles. Our algorithms can be viewed as specific random-batch approximations of SVGD, which are computationally more efficient than ordinary SVGD. We show that the n particles output by VP-SVGD and GB-SVGD, run for T steps with batch-size K, are at-least as good as i.i.d samples from a distribution whose Kernel Stein Discrepancy to the target is at most Oleft(tfracd1/3(KT)1/6right) under standard assumptions. Our results also hold under a mild growth condition on the potential function, which is much weaker than the isoperimetric (e.g. Poincare Inequality) or information-transport conditions (e.g. Talagrand's Inequality mathsfT1) generally considered in prior works. As a corollary, we consider the convergence of the empirical measure (of the particles output by VP-SVGD and GB-SVGD) to the target distribution and demonstrate a double exponential improvement over the best known finite-particle analysis of SVGD. Beyond this, our results present the first known oracle complexities for this setting with polynomial dimension dependence.