A Non-Asymptotic Analysis for Stein Variational Gradient Descent

• URL: http://arxiv.org/abs/2006.09797v4
• Date: Sun, 3 Jan 2021 11:36:09 GMT
• Title: A Non-Asymptotic Analysis for Stein Variational Gradient Descent
• Authors: Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, Arthur Gretton
• Abstract summary: We provide a novel finite time analysis for the Stein Variational Gradient Descent algorithm. We provide a descent lemma establishing that the algorithm decreases the objective at each iteration. We also provide a convergence result of the finite particle system corresponding to the practical implementation of SVGD to its population version.
• Score: 44.30569261307296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Stein Variational Gradient Descent (SVGD) algorithm, which optimises a set of particles to approximate a target probability distribution $\pi\propto e^{-V}$ on $\mathbb{R}^d$. In the population limit, SVGD performs gradient descent in the space of probability distributions on the KL divergence with respect to $\pi$, where the gradient is smoothed through a kernel integral operator. In this paper, we provide a novel finite time analysis for the SVGD algorithm. We provide a descent lemma establishing that the algorithm decreases the objective at each iteration, and rates of convergence for the average Stein Fisher divergence (also referred to as Kernel Stein Discrepancy). We also provide a convergence result of the finite particle system corresponding to the practical implementation of SVGD to its population version.

Related papers

• Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation [9.065034043031668]
  Stein Variational Gradient Descent (SVGD) is a popular variational inference which simulates an interacting particle system to approximately sample from a target distribution. We introduce the notion of virtual particles and develop novel approximations of population-limit dynamics in the space of probability measures. We show that the $n$ particles output by VP-SVGD and GB-SVGD, run for $T$ steps with batch-size $K$, are as good as i.i.i.d samples from a distribution whose Kernel Stein Discrepancy to the target is at most $Oleft(tfrac
  arXiv  Detail & Related papers  (2023-05-27T19:21:28Z)
• Towards Understanding the Dynamics of Gaussian-Stein Variational Gradient Descent [16.16051064618816]
  Stein Variational Gradient Descent (SVGD) is a nonparametric particle-based deterministic sampling algorithm. We study the dynamics of the Gaussian-SVGD projected to the family of Gaussian distributions via the bilinear kernel. We propose a density-based and a particle-based implementation of the Gaussian-SVGD, and show that several recent algorithms for GVI, proposed from different perspectives, emerge as special cases of our unified framework.
  arXiv  Detail & Related papers  (2023-05-23T13:55:47Z)
• Augmented Message Passing Stein Variational Gradient Descent [3.5788754401889014]
  We study the isotropy property of finite particles during the convergence process. All particles tend to cluster around the particle center within a certain range. Our algorithm achieves satisfactory accuracy and overcomes the variance collapse problem in various benchmark problems.
  arXiv  Detail & Related papers  (2023-05-18T01:13:04Z)
• A Finite-Particle Convergence Rate for Stein Variational Gradient Descent [47.6818454221125]
  We provide the first finite-particle convergence rate for Stein variational descent gradient (SVGD) Our explicit, non-asymptotic proof strategy will serve as a template for future refinements.
  arXiv  Detail & Related papers  (2022-11-17T17:50:39Z)
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition [0.0]
  Stein Variational Gradient Descent (SVGD) is an important alternative to the Langevin-type algorithms for sampling from probability distributions. In the existing theory of Langevin-type algorithms and SVGD, the potential function $V$ is often assumed to be $L$-smooth.
  arXiv  Detail & Related papers  (2022-06-01T14:08:35Z)
• Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
  The StochAstic Recursive grAdientritHm (SARAH) algorithm is a variance reduced variant of the Gradient Descent (SGD) algorithm. In this paper, we remove the necessity of a full gradient. The aggregated gradients serve as an estimate of a full gradient in the SARAH algorithm.
  arXiv  Detail & Related papers  (2021-11-26T06:00:44Z)
• Large-Scale Wasserstein Gradient Flows [84.73670288608025]
  We introduce a scalable scheme to approximate Wasserstein gradient flows. Our approach relies on input neural networks (ICNNs) to discretize the JKO steps. As a result, we can sample from the measure at each step of the gradient diffusion and compute its density.
  arXiv  Detail & Related papers  (2021-06-01T19:21:48Z)
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization [106.70006655990176]
  A distributional optimization problem arises widely in machine learning and statistics. We propose a novel particle-based algorithm, dubbed as variational transport, which approximately performs Wasserstein gradient descent. We prove that when the objective function satisfies a functional version of the Polyak-Lojasiewicz (PL) (Polyak, 1963) and smoothness conditions, variational transport converges linearly.
  arXiv  Detail & Related papers  (2020-12-21T18:33:13Z)
• Kernel Stein Generative Modeling [68.03537693810972]
  Gradient Langevin Dynamics (SGLD) demonstrates impressive results with energy-based models on high-dimensional and complex data distributions. Stein Variational Gradient Descent (SVGD) is a deterministic sampling algorithm that iteratively transports a set of particles to approximate a given distribution. We propose noise conditional kernel SVGD (NCK-SVGD), that works in tandem with the recently introduced Noise Conditional Score Network estimator.
  arXiv  Detail & Related papers  (2020-07-06T21:26:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.