Linear convergence of proximal descent schemes on the Wasserstein space

• URL: http://arxiv.org/abs/2411.15067v1
• Date: Fri, 22 Nov 2024 16:56:12 GMT
• Title: Linear convergence of proximal descent schemes on the Wasserstein space
• Abstract summary: We prove that the relative entropy $operatornameKL(cdot|pi)$ has a unique Wasserstein sub-gradient, and that the relative Fisher information is indeed finite. We use a uniform logarithmic Sobolev inequality (LSI) and the entropy "sandwich" lemma, extending the analysis from arXiv:2201.10469 and arXiv:2202.01009.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate proximal descent methods, inspired by the minimizing movement scheme introduced by Jordan, Kinderlehrer and Otto, for optimizing entropy-regularized functionals on the Wasserstein space. We establish linear convergence under flat convexity assumptions, thereby relaxing the common reliance on geodesic convexity. Our analysis circumvents the need for discrete-time adaptations of the Evolution Variational Inequality (EVI). Instead, we leverage a uniform logarithmic Sobolev inequality (LSI) and the entropy "sandwich" lemma, extending the analysis from arXiv:2201.10469 and arXiv:2202.01009. The major challenge in the proof via LSI is to show that the relative Fisher information $I(\cdot|\pi)$ is well-defined at every step of the scheme. Since the relative entropy is not Wasserstein differentiable, we prove that along the scheme the iterates belong to a certain class of Sobolev regularity, and hence the relative entropy $\operatorname{KL}(\cdot|\pi)$ has a unique Wasserstein sub-gradient, and that the relative Fisher information is indeed finite.

Related papers

• Error estimates for tamed Euler and Randomized Euler schemes for SDEs with locally Lipschitz drift with applications to non-logconcave sampling and optimization [0.0]
  We tame the numerical discretization of differential equations with locally Lipschitz, super-optimally growing drift, and the resulting implications for sampling from non-log-concave distributions satisfying a Sobolev inequality.<n>We establish, for the first time, a non-asymotic guarantee in total variation for a tamed randomized Langevin scheme under superlinear growth.
  arXiv  Detail & Related papers  (2026-05-24T08:35:24Z)
• A note on convergence of Wasserstein policy optimization [1.4576165959001435]
  Wasserstein Policy Optimization (WPO) is a proposed reinforcement learning algorithm that leverages Wasserstein gradient flows to optimize policies in continuous action spaces.<n>We argue that WPO within the framework of entropy-regularised Markov Decision Processes converges linearly.
  arXiv  Detail & Related papers  (2026-05-21T15:32:39Z)
• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• Axiomatic On-Manifold Shapley via Optimal Generative Flows [9.595059073171269]
  Shapley-based attribution is critical for post-hoc XAI but suffers from off-manifold artifacts due to baselines.<n>We propose a formal theory of on-manifold Aumann-Shapley attributions driven by optimal generative flows.
  arXiv  Detail & Related papers  (2026-03-05T12:05:20Z)
• Finite-Particle Rates for Regularized Stein Variational Gradient Descent [9.824622287505454]
  We derive finite-particle rates for the regularized Stein variational descent gradient (R-SVGD) algorithm introduced by He et al.<n>For the resulting interacting $N$-particle system, we establish explicit non-asymptotic bounds for time-averaged (annealed) empirical measures.<n>Our analysis covers both continuous- and discrete-time dynamics and yields principled tuning rules for the regularization parameter, step size, and averaging horizon.
  arXiv  Detail & Related papers  (2026-02-05T01:00:00Z)
• Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation [6.800624963330628]
  We derive non-asymptotic error bounds for nonlinear approximation algorithms in the Wasserstein-$p$ distance.<n>We show that the normalized last iterates converge to a Gaussian distribution in the $p$-Wasserstein distance at a rate of order $_n1/6$, where $_n$ is the step size.<n>These distributional guarantees imply high-probability concentration inequalities that improve upon those derived from moment bounds and Markovs inequality.
  arXiv  Detail & Related papers  (2026-02-02T18:41:06Z)
• Sequential Monte Carlo approximations of Wasserstein--Fisher--Rao gradient flows [0.0]
  We consider several partial differential equations whose solution is a minimiser of the Kullback--Leibler divergence from $pi$.<n>We propose a novel algorithm to approximate the Wasserstein--Fisher--Rao flow of the Kullback--Leibler divergence.
  arXiv  Detail & Related papers  (2025-06-06T09:24:46Z)
• Wasserstein Bounds for generative diffusion models with Gaussian tail targets [0.0]
  We present an estimate of the Wasserstein distance between the data distribution and the generation of score-based generative models. The complexity bound in dimension is $O(sqrtd)$, with a logarithmic constant.
  arXiv  Detail & Related papers  (2024-12-15T17:20:42Z)
• 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)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
  A deep equilibrium model (DEQ) is implicitly defined through an equilibrium point of an infinite-depth weight-tied model with an input-injection. Instead of infinite computations, it solves an equilibrium point directly with root-finding and computes gradients with implicit differentiation. We propose a novel probabilistic framework to overcome the technical difficulty in the non-asymptotic analysis of infinite-depth weight-tied models.
  arXiv  Detail & Related papers  (2022-05-27T08:00:13Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Non-asymptotic convergence bounds for Wasserstein approximation using point clouds [0.0]
  We show how to generate discrete data as if sampled from a model probability distribution. We provide explicit upper bounds for the convergence-type algorithm.
  arXiv  Detail & Related papers  (2021-06-15T06:53:08Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)
• 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)
• Debiased Sinkhorn barycenters [110.79706180350507]
  Entropy regularization in optimal transport (OT) has been the driver of many recent interests for Wasserstein metrics and barycenters in machine learning. We show how this bias is tightly linked to the reference measure that defines the entropy regularizer. We propose debiased Wasserstein barycenters that preserve the best of both worlds: fast Sinkhorn-like iterations without entropy smoothing.
  arXiv  Detail & Related papers  (2020-06-03T23:06:02Z)
• The Wasserstein Proximal Gradient Algorithm [23.143814848127295]
  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.
  arXiv  Detail & Related papers  (2020-02-07T22:19:32Z)
• 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.