Research map / Optimization / Optimizers
Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives finite-particle SVGD convergence rates in KSD (O(1/sqrt N), continuous and discrete time) via relative entropy of the joint particle density, and Wasserstein-2 rates for bilinear + Matérn kernels.
Problem
Finite-particle convergence rates for deterministic Stein Variational Gradient Descent (SVGD) in KSD and Wasserstein-2 metrics, previously known only with double-exponential or slow (1/sqrt(log log N)) rates.
Approach
Track the relative entropy of the joint density of N particle locations against the N-fold product target; its time derivative splits into a dominant negative part equal to -N times expected KSD^2 of the empirical measure plus a controllable positive part, yielding O(1/sqrt N) KSD bounds without gradient-flow structure or added noise.
Key results
- Continuous-time SVGD time-averaged KSD bounded by O(1/sqrt N), a double-exponential improvement over the prior 1/sqrt(log log N) rate.
- Discrete-time SVGD achieves E[average KSD^2] <= b d (d^{(1+alpha)/(2(1-alpha))} + sqrt(d) K^alpha + d)/N with T = N^{(2-alpha)/(1-2alpha)} iterations.
- For bilinear + Matérn kernels, W2 convergence rate O(1/N^{alpha/d})-type with curse of dimensionality r(d) ~ 1/(18d) for large d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Track joint-particle relative entropy to obtain a finite-particle KSD bound | Continuous-time SVGD · Time-averaged empirical measure | expected KSD: 1/\sqrt{\log \log N} to O(1/\sqrt{N}) | Helped |
| Use bilinear + Matérn kernel | Finite-particle SVGD · Time-averaged empirical measure | Wasserstein-2: O(1/N^{\alpha/d}) | Helped |
| Use bilinear + Matérn kernel for Wasserstein convergence | Finite-particle SVGD · Time-averaged empirical measure | Wasserstein-2: r(d) \approx \frac{1}{18 d} | Mixed |
| Average particle trajectories over [0,N] | Finite-particle SVGD · Time-averaged particle marginal | weak convergence | Helped |
Surprising findings
- KSD rates are dimension-friendly (linear in d) while W2 rates suffer a curse of dimensionality.
Limitations
- Continuous-time analysis is the main result; discrete-time Wasserstein results deferred to future work.
- Discrete-time bounds require strong assumptions (bounded kernel derivatives, growth on potential, Laplacian bound) and step-size tuning with alpha.
- Wasserstein rates for Matérn kernels exhibit curse of dimensionality in d.
Experimental setup
Metrics: KSD Wasserstein-2 distance
Baselines: Shi and Mackey 2024 finite-particle SVGD rate (1/sqrt(log log N)) SVGD with virtual particles Langevin-regularized SVGD
Builds on: Stein Variational Gradient Descent Kernelized Stein Discrepancy Liouville equation Wasserstein-2 convergence via KSD (Gorham et al.)
Closest papers by meaning
- A Finite-Particle Convergence Rate for Stein Variational Gradient Descent (NeurIPS 2023 · similarity 0.96)
- A Non-Asymptotic Analysis for Stein Variational Gradient Descent (NeurIPS 2020 · similarity 0.94)
- Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation (NeurIPS 2023 · similarity 0.92)
- Stein Variational Gradient Descent as Gradient Flow (NeurIPS 2017 · similarity 0.92)
- Long-time asymptotics of noisy SVGD outside the population limit (ICLR 2025 · similarity 0.90)
- ELBOing Stein: Variational Bayes with Stein Mixture Inference (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.