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

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 (which is conceptually elegant) and GB-SVGD (which is empirically effective), both of which exhibit provably fast finite-particle convergence rates. By introducing the concept of virtual particles, we develop novel stochastic approximations of population-limit SVGD dynamics in the space of probability measures, which are exactly implementable using only 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( d 1/3 /(KT ) 1/6 ) 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 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, thereby completely eliminating the curse of dimensionality exhibited by previously known finite-particle rates. Result Algorithm Assumption Rate Oracle Complexity Korba et al. [25] Population Limit SVGD Uniformly Bounded KSD π ⋆ (μ t ||π ⋆ ) poly(d) √ T Not Implementable Salim et al. [41] Population Limit SVGD Sub-gaussian π ⋆ d 3 /2 √ T Not Implementable Shi and Mackey [42] SVGD Sub-gaussian π ⋆ poly(d) √ log log n Θ( 1 /d) poly(d) ϵ 2 e Θ(de poly(d) /ϵ 2 ) Ours, Corollary 1 VP-SVGD Sub-gaussian π ⋆ ( d /n) 1 /4 + ( d /n) 1 /2 d 4 /ϵ 12 Ours, Corollary 2 GB-SVGD Sub-gaussian π ⋆ d 1 /3 /n 1 /12 + ( d /n) 1 /2 d 6 /ϵ 18 Ours, Corollary 1 VP-SVGD Sub-exponential π ⋆ d 1 /3 n 1 /6 + d n 1 /2 d 6 /ϵ 16 Ours, Corollary 2 GB-SVGD Sub-exponential π ⋆ d 3 /8 n 1 /16 + d n 1 /2 d 9 /ϵ 24