Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition

• URL: http://arxiv.org/abs/2206.00508v1
• Date: Wed, 1 Jun 2022 14:08:35 GMT
• Title: Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition
• Authors: Lukang Sun, Avetik Karagulyan and Peter Richtarik
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stein Variational Gradient Descent (SVGD) is an important alternative to the Langevin-type algorithms for sampling from probability distributions of the form $\pi(x) \propto \exp(-V(x))$. In the existing theory of Langevin-type algorithms and SVGD, the potential function $V$ is often assumed to be $L$-smooth. However, this restrictive condition excludes a large class of potential functions such as polynomials of degree greater than $2$. Our paper studies the convergence of the SVGD algorithm for distributions with $(L_0,L_1)$-smooth potentials. This relaxed smoothness assumption was introduced by Zhang et al. [2019a] for the analysis of gradient clipping algorithms. With the help of trajectory-independent auxiliary conditions, we provide a descent lemma establishing that the algorithm decreases the $\mathrm{KL}$ divergence at each iteration and prove a complexity bound for SVGD in the population limit in terms of the Stein Fisher information.

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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Improved Stein Variational Gradient Descent with Importance Weights [0.0]
  Stein Variational Gradient Descent (SVGD) is a popular sampling algorithm used in various machine learning tasks. We propose to enhance SVGD via the introduction of importance weights, which leads to a new method for which we coin the name $beta$-SVGD.
  arXiv  Detail & Related papers  (2022-10-02T08:42:44Z)
• A Note on the Convergence of Mirrored Stein Variational Gradient Descent under $(L_0,L_1)-$Smoothness Condition [0.0]
  We establish a descent lemma for the population limit Mirrored Stein Variational Gradient Method(MSVGD) This descent lemma does not rely on the path information of MSVGD but rather on a simple assumption for the mirrored distribution $nablaPsi_#piproptoexp(-V)$.
  arXiv  Detail & Related papers  (2022-06-20T11:04:18Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity. We proposed a method to solve problems master to agents' communication and local calls. The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
  arXiv  Detail & Related papers  (2022-05-30T14:28:02Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Complexity Analysis of Stein Variational Gradient Descent Under Talagrand's Inequality T1 [12.848239550098697]
  We study the complexity of Stein Variational Gradient Descent (SVGD), which is an algorithm to sample from $pi(x) propto exp(-Fx)) Our key assumption is that the target distribution satisfies the inequality's inequality T1.
  arXiv  Detail & Related papers  (2021-06-06T09:51:32Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• A Non-Asymptotic Analysis for Stein Variational Gradient Descent [44.30569261307296]
  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.
  arXiv  Detail & Related papers  (2020-06-17T12:01:33Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23: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.