mlsanityData to 7 Oct 2026

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

arXiv 2305.17558 ↗First posted 27 May 2023stat.ML cs.LG math.STcited by 6

Not on the map. Why?

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.

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

Builds on

33 of 63 references.

References · 33

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  3. 2016Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithmcited by 498
  4. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  5. 2016A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluationcited by 236
  6. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  7. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  8. 2017Stein Variational Gradient Descent as Gradient Flowcited by 149
  9. 2016A Kernel Test of Goodness of Fitcited by 143
  10. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  11. 2019On the geometry of Stein variational gradient descentcited by 82
  12. 2020SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergencecited by 64
21 more
  1. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  2. 2020A Non-Asymptotic Analysis for Stein Variational Gradient Descentcited by 61
  3. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  4. 2017Message Passing Stein Variational Gradient Descentcited by 47
  5. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  6. 2017Stein Variational Policy Gradientcited by 42
  7. 2018Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spacescited by 41
  8. 2018Scaling limit of the Stein variational gradient descent: the mean field regimecited by 35
  9. 2020Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Samplingcited by 32
  10. 2020Stochastic Stein Discrepanciescited by 30
  11. 2022A Finite-Particle Convergence Rate for Stein Variational Gradient Descentcited by 22
  12. 2016Learning to Draw Samples: With Application to Amortized MLE for Generative Adversarial Learningcited by 21
  13. 2021A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1cited by 21
  14. 2022Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimizationcited by 16
  15. 2022Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Conditioncited by 16
  16. 2021Stein Variational Gradient Descent: many-particle and long-time asymptoticscited by 15
  17. 2023Towards Understanding the Dynamics of Gaussian-Stein Variational Gradient Descentcited by 13
  18. 2019A stochastic version of Stein Variational Gradient Descent for efficient samplingcited by 10
  19. 2021Learning Equivariant Energy Based Models with Equivariant Stein Variational Gradient Descentcited by 10
  20. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  21. 2022Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithmscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 1.

6 papers.

  1. 2024Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descentcited by 13
  2. 2025Learning of Population Dynamics: Inverse Optimization Meets JKO Schemecited by 6
  3. 2024Long-time asymptotics of noisy SVGD outside the population limitcited by 2
  4. 2025Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimizationcited by 1
  5. 2026To discretize continually: Mean shift interacting particle systems for Bayesian inferencecited by 1
  6. 2024A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible foodcited by 0