The Wasserstein Proximal Gradient Algorithm

• URL: http://arxiv.org/abs/2002.03035v3
• Date: Sun, 21 Feb 2021 13:57:47 GMT
• Title: The Wasserstein Proximal Gradient Algorithm
• Authors: Adil Salim, Anna Korba, Giulia Luise
• Abstract summary: Wasserstein gradient flows are continuous time dynamics that define curves of steepest descent to minimize an objective function over the space of probability measures. We propose a Forward Backward (FB) discretization scheme that can tackle the case where the objective function is the sum of a smooth and a nonsmooth geodesically convex terms.
• Score: 23.143814848127295
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Wasserstein gradient flows are continuous time dynamics that define curves of steepest descent to minimize an objective function over the space of probability measures (i.e., the Wasserstein space). This objective is typically a divergence w.r.t. a fixed target distribution. In recent years, these continuous time dynamics have been used to study the convergence of machine learning algorithms aiming at approximating a probability distribution. However, the discrete-time behavior of these algorithms might differ from the continuous time dynamics. Besides, although discretized gradient flows have been proposed in the literature, little is known about their minimization power. In this work, we propose a Forward Backward (FB) discretization scheme that can tackle the case where the objective function is the sum of a smooth and a nonsmooth geodesically convex terms. Using techniques from convex optimization and optimal transport, we analyze the FB scheme as a minimization algorithm on the Wasserstein space. More precisely, we show under mild assumptions that the FB scheme has convergence guarantees similar to the proximal gradient algorithm in Euclidean spaces.

Related papers

• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Continuous-time Riemannian SGD and SVRG Flows on Wasserstein Probabilistic Space [17.13355049019388]
  We extend the gradient flow on Wasserstein space into the gradient descent (SGD) flow and variance reduction (SVRG) flow. By leveraging the property of Wasserstein space, we construct differential equations to approximate the corresponding discrete dynamics in Euclidean space. Our results are proven, which match the results in Euclidean space.
  arXiv  Detail & Related papers  (2024-01-24T15:35:44Z)
• A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization [10.820943271350442]
  We present a convex gradient algorithm for minimizing a smooth objective function that is an expectation over noisy cost samples. We also show that our algorithm avoids the ratelibria, implying convergence to local minima.
  arXiv  Detail & Related papers  (2022-07-30T18:50:36Z)
• Variational Wasserstein gradient flow [9.901677207027806]
  We propose a scalable proximal gradient type algorithm for Wasserstein gradient flow. Our framework covers all the classical Wasserstein gradient flows including the heat equation and the porous medium equation.
  arXiv  Detail & Related papers  (2021-12-04T20:27:31Z)
• 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)
• Sliced-Wasserstein Gradient Flows [15.048733056992855]
  Minimizing functionals in the space of probability distributions can be done with Wasserstein gradient flows. This work proposes to use gradient flows in the space of probability measures endowed with the sliced-Wasserstein distance.
  arXiv  Detail & Related papers  (2021-10-21T08:34:26Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• 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)
• A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
  We propose a novel numerical scheme to optimize the gradient flows for learning energy-based models (EBMs) We derive a second-order Wasserstein gradient flow of the global relative entropy from Fokker-Planck equation. Compared with existing schemes, Wasserstein gradient flow is a smoother and near-optimal numerical scheme to approximate real data densities.
  arXiv  Detail & Related papers  (2019-10-31T02:26:20Z)

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.