Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization

Abstract

We consider the optimization problem of minimizing a functional defined over a family of probability distributions, where the objective functional is assumed to possess a variational form. Such a distributional optimization problem arises widely in machine learning and statistics, with Monte-Carlo sampling, variational inference, policy optimization, and generative adversarial network as examples. For this problem, we propose a novel particle-based algorithm, dubbed as variational transport, which approximately performs Wasserstein gradient descent over the manifold of probability distributions via iteratively pushing a set of particles. Specifically, we prove that moving along the geodesic in the direction of functional gradient with respect to the second-order Wasserstein distance is equivalent to applying a pushforward mapping to a probability distribution, which can be approximated accurately by pushing a set of particles. Specifically, in each iteration of variational transport, we first solve the variational problem associated with the objective functional using the particles, whose solution yields the Wasserstein gradient direction. Then we update the current distribution by pushing each particle along the direction specified by such a solution. By characterizing both the statistical error incurred in estimating the Wasserstein gradient and the progress of the optimization algorithm, we prove that when the objective function satisfies a functional version of the Polyak-Łojasiewicz (PL) (Polyak, 1963) and smoothness conditions, variational transport converges linearly to the global minimum of the objective functional up to a certain statistical error, which decays to zero sublinearly as the number of particles goes to infinity.

58 pages, add acknowledgement

References in corpus (27)

• Auto-Encoding Variational Bayes
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Stochastic Gradient Hamiltonian Monte Carlo
• MMD GAN: Towards Deeper Understanding of Moment Matching Network
• Equivalence Between Policy Gradients and Soft Q-Learning
• Sampling Can Be Faster Than Optimization
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Stein Variational Gradient Descent as Gradient Flow
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Approximate volume and integration for basic semi-algebraic sets
• Convergence of Langevin MCMC in KL-divergence
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Understanding and Accelerating Particle-Based Variational Inference
• A Selective Overview of Deep Learning
• Is There an Analog of Nesterov Acceleration for MCMC?
• On the geometry of Stein variational gradient descent
• A Non-Asymptotic Analysis for Stein Variational Gradient Descent
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Stein Variational Gradient Descent Without Gradient
• Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Approximate inference with Wasserstein gradient flows
• Probability Functional Descent: A Unifying Perspective on GANs, Variational Inference, and Reinforcement Learning
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Stein Self-Repulsive Dynamics: Benefits From Past Samples