  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 $O\left(\tfrac{d^{1/3}}{(KT)^{1/6}}\right)$ 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 $\mathsf{T}_1$)
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.
