Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization

Zhuoran Yang, Yufeng Zhang, Yongxin Chen, Zhaoran Wang

TL;DR

This paper introduces "Variational Transport," a novel particle-based algorithm for optimizing probability distributions. It tackles complex optimization problems common in machine learning by performing Wasserstein gradient descent using particles, offering theoretical guarantees of convergence to the global minimum.

What Problem Does This Paper Address?

Many machine learning and statistics problems involve optimizing over probability distributions, such as in Bayesian inference, robust optimization, and generative models. These problems are challenging because probability distributions live in an infinite-dimensional space. Traditional approaches often involve parameterizing distributions with a finite number of variables, which can introduce approximation biases and lead to non-convex optimization landscapes. This paper addresses the need for a method that can directly optimize distributions in an infinite-dimensional setting, avoiding these pitfalls and providing theoretical guarantees.

Methods

The core of the proposed method, "Variational Transport," is to approximate Wasserstein gradient descent on the space of probability distributions. The authors leverage the fact that moving along a geodesic in the Wasserstein space (which represents the "distance" between distributions) is equivalent to a pushforward mapping. Their algorithm iteratively:

  1. Solves a variational problem: This problem, associated with the objective functional, helps estimate the Wasserstein gradient direction.
  2. Pushes particles: Each particle representing the current distribution is moved along the estimated gradient direction. This particle movement approximates the pushforward mapping.

The authors also establish theoretical connections between the Wasserstein gradient and functional derivatives, and between the exponential map in the Wasserstein space and particle pushforward operations. They provide convergence guarantees under specific conditions (Polyak-Łojasiewicz and smoothness conditions on the objective functional).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Wasserstein Geometry as a Solution: The paper highlights that the space of probability distributions equipped with the Wasserstein distance forms a Riemannian manifold. Optimizing on this manifold using geodesic paths (Wasserstein gradient descent) is a natural and powerful approach.
  • Particles as Distribution Representatives: Using a set of particles to represent a probability distribution is a practical and computationally tractable way to handle infinite-dimensional optimization. The algorithm's updates are performed by moving these particles.
  • Variational Form is Key: The objective functional being expressible in a variational form is crucial. This allows for the estimation of the Wasserstein gradient by solving an auxiliary optimization problem, which can be done using standard machine learning techniques.
  • Bridging Theory and Practice: The paper provides a rigorous theoretical framework for a particle-based optimization method, offering convergence guarantees that are often missing in practical machine learning algorithms.

Key Results

  • Convergent Algorithm: Variational Transport is shown to converge linearly to the global minimum of the objective functional under certain conditions (functional PL and smoothness).
  • Statistical Error Decay: The statistical error incurred in estimating the Wasserstein gradient (due to finite particles) decays sublinearly as the number of particles increases.
  • Practical Implementation: The algorithm is designed to be implementable, leveraging particle-based methods and potentially deep learning for solving the inner variational problems.

Limitations and Future Work

  • Assumptions: The theoretical convergence guarantees rely on specific assumptions about the objective functional (e.g., functional PL condition, smoothness) and the properties of the RKHS used for estimating the gradient.
  • Computational Cost: While particle-based, solving the inner variational problem in each iteration can still be computationally intensive, especially with a large number of particles or complex objective functions.
  • Future Directions: The authors suggest that their framework can be extended to other integral probability metrics beyond the Wasserstein distance and applied to a broader range of distributional optimization problems. Further exploration of practical implementations and extensions to more complex scenarios is also implied.

Summary updated

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-\L{}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.
BibTeX
@misc{yang2020variational,
  author = {Zhuoran Yang and Yufeng Zhang and Yongxin Chen and Zhaoran Wang},
  title = {{Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization}},
  year = {2020},
  eprint = {2012.11554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.11554},
}
Figure