Complexity Analysis of Stein Variational Gradient Descent Under Talagrand's Inequality T1

• URL: http://arxiv.org/abs/2106.03076v1
• Date: Sun, 6 Jun 2021 09:51:32 GMT
• Title: Complexity Analysis of Stein Variational Gradient Descent Under Talagrand's Inequality T1
• Authors: Adil Salim and Lukang Sun and Peter Richt\'arik
• Abstract summary: 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.
• Score: 12.848239550098697
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of Stein Variational Gradient Descent (SVGD), which is an algorithm to sample from $\pi(x) \propto \exp(-F(x))$ where $F$ smooth and nonconvex. We provide a clean complexity bound for SVGD in the population limit in terms of the Stein Fisher Information (or squared Kernelized Stein Discrepancy), as a function of the dimension of the problem $d$ and the desired accuracy $\varepsilon$. Unlike existing work, we do not make any assumption on the trajectory of the algorithm. Instead, our key assumption is that the target distribution satisfies Talagrand's inequality T1.

Related papers

• Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization [28.497079108813924]
  We study differentially private (DP) optimization algorithms for and empirical objectives which are neither smooth nor convex. We provide a single-pass $(alpha,beta)$-DP algorithm that returns an $widetildeOmegaleft (1/alphabeta3+d/epsilonalphabeta2+d3/4/epsilonalpha1/2beta3/2right)$. We then provide a multi-pass time algorithm which further improves the sample complexity to $widetildeOmegaleft(
  arXiv  Detail & Related papers  (2024-10-08T10:15:49Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• 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)
• 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)
• 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)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  We present a novel gradient estimator based on two function evaluation and randomization. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem.
  arXiv  Detail & Related papers  (2022-05-27T11:23:57Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. We prove that the zigzag sampling algorithm achieves $varepsilon$ error in chi-square divergence with a computational cost equivalent to $Obigl.
  arXiv  Detail & Related papers  (2020-12-21T03:10:21Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• 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)
• A diffusion approach to Stein's method on Riemannian manifolds [65.36007959755302]
  We exploit the relationship between the generator of a diffusion on $mathbf M$ with target invariant measure and its characterising Stein operator. We derive Stein factors, which bound the solution to the Stein equation and its derivatives. We imply that the bounds for $mathbb Rm$ remain valid when $mathbf M$ is a flat manifold.
  arXiv  Detail & Related papers  (2020-03-25T17:03:58Z)

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.