Inexact JKO and proximal-gradient algorithms in the Wasserstein space

Simone Di Marino, Emanuele Naldi, Silvia VillaarXiv 2025 · DOI · arXiv

TL;DR

This paper provides the first rigorous convergence analysis for inexact Jordan-Kinderlehrer-Otto (JKO) and proximal-gradient algorithms in Wasserstein spaces. By establishing new discrete Evolution Variational Inequalities (EVI), the authors prove that these algorithms still converge to global minimizers even when the iterative subproblems are solved only approximately, provided the errors are sufficiently controlled.

What Problem Does This Paper Address?

Gradient flows in the Wasserstein space—the space of probability measures—are a powerful tool for modeling diffusion processes, solving certain partial differential equations (PDEs), and training machine learning models (e.g., via Langevin dynamics). The standard way to discretize these flows is the JKO scheme, which is essentially a Proximal Point Algorithm for measures.

In theory, the JKO scheme assumes that at each step, we can exactly solve a minimization problem involving an energy functional and a squared Wasserstein distance. In practice, this is almost never possible. Numerical solvers (like those based on entropic regularization or ADMM) only provide approximate solutions.

Until now, most theoretical guarantees for JKO assumed exact steps. This paper closes the gap between theory and practice by asking: If we only solve the JKO steps approximately, does the algorithm still converge? And if so, how fast?

Methods

The authors analyze two distinct types of "inexactness" that occur in real-world computations:

  1. Distance-type error: The approximate measure is close to the true minimizer in terms of the Wasserstein distance ($W_2$).
  2. Variational-type error: The approximate measure achieves an energy value close to the minimum of the proximal objective function.

To prove convergence, the authors rely on Discrete Evolution Variational Inequalities (EVI). Because Wasserstein space is not a Hilbert space, standard optimization proofs (which rely on the non-expansivity of proximal operators) do not directly apply. The authors develop a "finer" version of the discrete EVI specifically for the proximal-gradient setting to handle the lack of Lipschitz continuity in the projection maps of Wasserstein space.

The analysis covers both the standard JKO scheme and the more general proximal-gradient (forward-backward) algorithm, which is used to minimize composite functionals (e.g., a smooth potential energy plus a non-smooth entropy term).

Datasets

Not discussed in the paper. This is a theoretical mathematical work focused on proving convergence theorems and rates. No empirical datasets or benchmarks were used.

Key Insights and Ideas

  • The Non-Expansivity Hurdle: In Euclidean spaces, the proximal map is a contraction (non-expansive). The authors highlight that this is not guaranteed in Wasserstein space. They provide a striking example (Figure 1) where projecting nearby Gaussians onto a convex set of measures results in significantly different outputs, proving the projection map isn't Lipschitz. This necessitates a more sophisticated proof strategy than what is used in classical optimization.
  • Summability of Errors: Convergence isn't free. The errors at each step must be "summable" in a specific way relative to the step sizes ($\tau_n$). Specifically, for the variational error $\epsilon_n$, the condition $\sum \frac{\sigma_n}{\tau_n} \epsilon_n^2 < \infty$ (where $\sigma_n$ is the sum of step sizes) ensures the algorithm doesn't drift away from the optimum.
  • Variational vs. Distance Errors: The paper notes that variational errors are often more "practically significant." In a real algorithm, you can monitor the value of the objective function, but you rarely know the distance to the true (unknown) minimizer. Proving convergence under variational error makes the theory much more applicable to actual software implementations.

Key Results

  • Convergence Rates: For both inexact JKO and proximal-gradient schemes, the authors establish a convergence rate of $O(1/\sigma_n)$ for the objective functional, where $\sigma_n$ is the cumulative sum of the step sizes.
  • Weak Convergence: Under the specified error conditions, the sequence of measures $\{\mu_n\}$ is proven to converge weakly (specifically, in the $\tau_{w,2}$ topology) to a global minimizer of the functional.
  • Variable Stepsizes: The results hold for variable stepsize sequences $\{\tau_n\}$, providing flexibility for practitioners who might want to use decaying or adaptive stepsizes to "adjust" algorithms like the Unadjusted Langevin Algorithm (ULA).

Limitations and Future Work

  • Regularity Assumptions: The analysis for the proximal-gradient algorithm requires a specific regularity assumption (A3) on the domain of the functional. The authors conjecture this might be weakened or removed in future work by using more general subdifferential calculus.
  • Specific Solver Bounds: While the paper provides the "budget" for how much error is allowed, it does not calculate the error produced by specific popular solvers (like the "ALG2" ADMM scheme). A promising next step is to quantify the inexactness of these specific numerical methods to see if they satisfy the paper's summability conditions.
  • Strong Convexity: The paper primarily focuses on the convex case. While they mention that strong convexity could lead to faster (linear) convergence, they note that the presence of constant errors $\epsilon_n$ usually prevents improving the rate without further assumptions on the error decay.

Summary updated

Abstract

This paper studies the convergence properties of the inexact Jordan-Kinderlehrer-Otto (JKO) scheme and proximal-gradient algorithm in the context of Wasserstein spaces. The JKO scheme, a widely-used method for approximating solutions to gradient flows in Wasserstein spaces, typically assumes exact solutions to iterative minimization problems. However, practical applications often require approximate solutions due to computational limitations. This work focuses on the convergence of the scheme to minimizers for the underlying functional and addresses these challenges by analyzing two types of inexactness: errors in Wasserstein distance and errors in energy functional evaluations. The paper provides rigorous convergence guarantees under controlled error conditions, demonstrating that weak convergence can still be achieved with inexact steps. The analysis is further extended to proximal-gradient algorithms, showing that convergence is preserved under inexact evaluations.
BibTeX
@misc{marino2025inexact,
  author = {Simone Di Marino and Emanuele Naldi and Silvia Villa},
  title = {{Inexact JKO and proximal-gradient algorithms in the Wasserstein space}},
  year = {2025},
  eprint = {2505.23517},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.23517},
  howpublished = {arXiv},
}
Figure