Non-geodesically-convex optimization in the Wasserstein space
Authors: Hoang Phuc Hau Luu
Hanlin Yu
Bernardo Williams
Petrus Mikkola
Marcelo Hartmann
Kai Puolamäki
Arto Klami
Venue: NeurIPS 2024 poster (2024)
Keywords: Wasserstein space
DC programming
nonconvex optimization
KL divergence
Primary area: optimization

Abstract: We study a class of optimization problems in the Wasserstein space (the space of probability measures) where the objective function is nonconvex along generalized geodesics. Specifically, the objective exhibits some difference-of-convex structure along these geodesics. The setting also encompasses sampling problems where the logarithm of the target distribution is difference-of-convex. We derive multiple convergence insights for a novel semi Forward-Backward Euler scheme under several nonconvex (and possibly nonsmooth) regimes. Notably, the semi Forward-Backward Euler is just a slight modification of the Forward-Backward Euler whose convergence is---to our knowledge---still unknown in our very general non-geodesically-convex setting.

Non-geodesically-connex optimization in the Wasserstein space
Hoang Phuc Hau Luu
Hanlin Yu
Bernardo Williams
Petrus Mikkola
Marcelo Hartmann
Kai Puolamäki
Arto Klami
Department of Computer Science, University of Helsinki
Abstract
We study a class of optimization problems in the Wasserstein space (the space of probability measures) where the objective function is nonconvex along generalized geodesics. Specifically, the objective exhibits some difference-of-comee along these geodesics. The setting also encompasses sampling problems where the logarithm of the target distribution is biffereence-o-convee We derive multiple convergence insights for novel semi Forward- Backward Euler scheme under several nonconvex (and possibly nonsmooth) regimes. Notably, the semi Forward- Backward Euler is just slight modification of the to our knowledge- still unknown in our very general non-geodesicallyy-oom setting.
structure
Euler
whose convergence to
1 Introduction
Sampling and optimization are intertwined. For example, the (overdamped) Langevin dynamies, typically considered sampling algorithm, can be considered as gradient descent optimization where a suitable amount Gaussian noise is injected at each step. There are also deeper connections. At the limit of infinitesimal stepsize, the law of the Langevin dynamics is governed by the Tokker-Planch equation describing a diffusion over time of probability measures. In the seminal paper [39], Jordan, Kinderlehrer, and Otto reinterpreted the Fokker-Plande equation the gradient flow of the functional relative entropy, a.k.a. Kullback-Leible (KL) divergence, in the (Wasserstein) space of finite second- moment probability measures equipped with the Wasserstein metric. The discovery connects the two fields and encourages optimization in the Wasserstein space, even conceptually, as it directly gives insight into the sampling context. Studies in continuous-time dynamics [1 12
natural and enjoy nice theoretical properties without discretization errors. Another line of research studies discretization of Wasserstein gradient flow by either quantifying the discretization emror between the 28 or viewing discrete-time flows as
66 30
continuous-ing flow and the discrete-time flow [39 67
27
23
iterative optimization schemes in the Wasserstein space 65
26 70 where the primary focus is
on (geodesically) conver optimization problems.
Nonconvex, nonsmooth optimization is challenging, [63] "In fact the great watershed in optimization isn 't between linearity and nonlinearity, but convexity and nonconvexity." The landscape of nonconvex problems is mostly underexplored in the Wasserstein space. In the sampling language, amounts to sampling from a non-log-concave and possibly non-log-Lipschirz. Limoshhit--smoooth target distribution. Recently, Balasubramanian al. O advocated the need for a sound theory for unadjusted Langevin algorithm (ULA) in sampling from log-smooth HLipschit/HHölder smooth) densities. These results are preliminary for the ULA (and its variants) with specific class of densities (smooth). Theoretical understandings of other classes of algorithms and densities needed.
in Euclidean space, quoting Rockafellar
sampling and provided some guarantees for the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We approach the subject through the lens of nonconvex optimization in the space of probability distributions and pose discretized Wasserstein gradient flows as iterative minimization algorithms. This allows to, on the one hand, use and extend tools from classical nonconvex optimization and, on the other hand, derive more connections between sampling and optimization.
We study the following non non-geodesicall-coweee optimization problem defined over the space (x( of probability measures μ over X = I2d with finite second moment, i.e. f [[=]]dp((x) < +o0,
min F(u) == (1) + (1) == (1) + (1) (EP:(X)
where F: + I is a nonconvex function which can be represented as a difference of two convex functions G and H, Ep(p) == ((z)dp(z)) is the potential energy, and A P2((X) - R U [+oo] plays a role as the regularizer which is assumed to be a convex function along generalized geodesics.
Why difference-of-conve structure? Nonconvexity lies at the difference-of-comee
(DC) structure
F = G - H, where G and H are called the first and second DC components, respectively. F being nonconvex implies Er being non-geoden tt--geddsiicaly-comeee
in general. First, the class of DC functions is very rich, and DC structures are present everywhere in real-world applications [60 46 47 22 56 58). Weakly convex and Lipschitz smooth (L-smooth or simply smooth) functions are two subclasses of DC functions. Furthermore, any continuous function can be approximated by a sequence of DC functions over a compact, convex domain 8 We also remark that many nonconvex functions admit quite natural DC decompositions, for example, an L-smooth function F has the following splittings: F(x)= = al |||a|| (a [=]|2 - F(r)) and F(x) = (Frx) + al|==|?²) a ai|[z||? whenever a 2 L/2. Second, DC functions preserve enough structure to extend convex analysis. Such structure key in classic DC programming [60] and in our Wasserstein space analysis with optimal transport tools.
Context Many problems in machine learning and sampling fall into the spectrum of problem (1)
For example, refer to a discussion in [65] that inspired our work. The regularizer H can be the internal energy 4 Sect. 10.4.3]. Under McCann's condition, the internal energy is convex along generalized geodesics Prop. 9.3.9]. In particular, the negative entropy, (1) = flg(((()) (d)(((()))(() if absolutely continuous w.r.t. Lebesgue measure, +o0 otherwise, is special case of internal energy satisfying McCann's condition. In the latter case, F(u) = DKL
( (pll + const where 4 (z(z) x ex:(-F(x:)). the optimization problem reduces to a sampling problem with log-DC target distribution. In Bayesian inference, the posterior structure depends on both the prior and likelihood. If the likelihood is log-smooth, it exhibits the aforementioned DC splittings. Log- priors, often nonsmooth to capture sparsity or low rank, typically also have explicit DC structures In the context of infinitely wide one-layer neural networks and Maximum Mean Discrepancy [51 7 21 let 2² be the optimal distribution over network's parameters, k be given kernel, the regularizer is then the interaction energy (n) = Iʃ k(z; y)du(z)dd(()) and F(x) = -2 f k<x,, y)d (y). In general, H is not convex along generalized geodesies and F is nonconvex but not necessarily DC. When the kernel has Lipschitz gradient, we can adjust both H and F as (1) = [[ k(z y) + +|+==|+++ yll dp(x)d)()))) and F(x) 2 f ka,,,,, y) y)dz (y) 2a||=r| for some > 0 making Hl generalized geodesically convex and F concave (hence DC); Appx. A.2
48 32
25
Our idea is minimize ( in the space of probability distributions by discretization of the gradient flow of F, leveraging on the JKO (Jordan, Kinderlehrer, and Otto) operator (2). In the previous work 70), this has been done with the Forward-Backward (FB) Euler discretization, but it lacks convergence analysis. Recently, Salim et al. (65] did some study on FB Euler, but their results do not apply here because F' is nonconvex and possibly nonsmooth. Further leveraging on the DC structure of F and inspired by classical DC programming literature [60]. we subtly modify the FB Euler to give rise to a scheme named semi FB Euler that enjoys major theoretical advantages as we can provide a wide range of convergence analysis. Regarding the name, "semi" addresses the splitting of the potential energy. The scheme can be nevertheless reinterpreted as FB Euler.
To our knowledge, no prior work studies problem ① when F is DC. Therefore, most of the derived results in this paper are novel. We propose and analyze the semi FB Fuler (4) leveraging on the classic DC optimization proof template [60] 45 46) with a substantial accommodation of Wasserstein geometry and derive the following set of new insights:
Contributions
Thm. We show that if the H is continuously differentiable, every cluster point of the sequence of distributions {Mn JeE generated by semi FB Euler is a critical point to F. Note that

---

criticality is notion from the DC programming literature 60) and it is necessary condition for local optimality: See Sect. 3.3
Thm. We provide convergence rate of !(N in terms of Wasserstein (sub)gradient mapping in the general nonsmooth setting. The notion of gradient mapping [39 38 55 is from the context of proximal algorithms in Euclidean space that is applicable to nonconvex programs where the notion of distance to global solution is-in general-ni not possible to work out.
Thm. Under the extra assumption that H is continuously twice differentiable and has bounded Hessian, we provide convergence rate of O(N-)) terms of distance of to the Fréchet subdifferential of F. One can think of this as convergence rate to Fréchet stationarity, i.c., if μ² is a Fréchet stationary point of F. then, by definition, is in the Fréchet subdifferential of F at jt". Fréchet stationarity is a relatively sharp necessary condition for local optimality,
Thm.
Under the assumptions of Thm. 3 and additionally FF satisfying the Lojasciewicz-yy inequality for some Lojasciewicz exponent of 0 E [o, 1). we show that (no [unteNN MNN is Cauchy sequence under Wasserstein topology, and thanks to the completeness of the Wasserstein space, the whole sequence {ja hne converges to some μ³" We show that J is in fact a global minimizer to F. Furthermore, we provide convergence rate of un, - u in three different regimes (W₂ denotes the Wasserstein metric): (1) if 8 = 0, W2(pnn y converges to 0 after finite number of steps; (2) if E (0, 1/2]. both F(Un) F(u²) and (2( R²) converges to O exponentially fast; (3) if E (1/2, 1). both F((m)) - F F(u") and W2(m'n v²) converges sublinearly to with rates (n-==> - and n 20-1
respectively. When
H is the negative entropy, F(pn) - F(1²)= = DKL (An Ip=";; Therefore, in the sampling context, we provide convergence guarantees in both Wasserstein and KL distances. See Sect. 4.3 for additional observations and implications.
2 Preliminaries
2.1 Notations and basic results in measure theory and functional analysis
We denote by X = RRd ((X) the Borel o-algebra over X, and Ldd the Lebesgue measure X. P(X) is the set of Borel probability measures on X. For ja E P(X), we denote its second-order moment by m2 (p) := Jx |== du(x), where m²(μ) can be infinity. P2(X) C (XX) denotes a set of finite second-order moment probability measures. P2, (X) (x is the set of measures that are absolutely continuous w.r.t. Ldd Here μ-a.e. stands for almost every wverywhere w.r.t. μ.
Let (x))). (X), (X),C,(X) be the classes of p-time continuously differentiable functions, infinitely differentiable functions with compact support, bounded and continuous functions, respectively.
From functional analysis 20), for each p 2 1, L*(X, (4) denotes the Banach space of measur- able (where measurable is understood as Borel measurable from now on) functions f such that Sx (=(())))P((()) dd((x) < +oo. We shall consider an element of LP ()) an equivalent class of functions that agree μ-a.e. on X rather than sole function. The norm of f E LP μ) is [Illle)(x.) (fx (())) When p 2, I j.) is actually Hilbert space with the inner product (f, ()) = Jx (=)gg(x))(((() which induces the mentioned norm. These results can be extended to vector-valued functions. In particular, we denote by L² X. space of & X + X in which ||]|| (X, v).. The norm || := (Sx [d(()))))
pt) the Hilbert
We say that X + I has quadratic growth if there exists >> 0 such that [x(x) < a(||=112 + 1) for all x E X. It is clear that if f has quadratic growth and E P2(X), then f E L ()).
The pushforward of a measure P(X) through a Borel map T X + Rm, denoted by T is defined by (T (A) = ( (A)) for every Borel sets A C I
2.2 Optimal transport 4
69 68
Given μ. V.V E P(X), the principal problem in optimal transport is to find a transport map T pushing şu v, i.e., T# v, in the most cost-efficient way, i.c., minimizing || - T[)) μ-average. Monge's formulation for this problem is infr:Tgeew Jx ||x (dx)), where the optimal
3

---

solution, if exists, is denoted by Ty and called the optimal (Monge) map. Monge's ' problem can be ill-posed, e.g., no such Tj exists when j Dirac mass and is absolutely continuous [5].
By relaxing Monge's formulation, Kantorovich considers min fxxx || - yy, y). where T(u, v) denotes the set of probabilities over X x X whose marginals are μ and v, i.e, Y T(,, 2) iff proji# Y = μ4, 7 where proji. proj2 are the projections onto the first X space and the second X space, respectively. Such y is called plan, Kantorovich's 's formulation is well-posed because [(,, 2) is non-empty (at least μ x E [ v)) and the arg min element actually exists (see [5] Sect. 2.2]). The set of optimal plans between and is denoted by I [u, v). In terms of random variables, any pairs (X, Y) where X ~ μ4, Y ~ v is called a coupling of μ and v while is called an optimal coupling if the joint law of X and Y is in (J,
In (X))), the min value in Kantorovich's problem specifies valid metrie referred to as Wasserstein distance, W2(u, v) = (fxx x || - y/l (x) for some, and thus all, 7 E L'(,,,) v). The metric is then called the Wasserstein space. In P2(X), beside the convergence notion induced by the Wasserstein metric, there is a weaker notion of convergence called narrow convergence: we say a sequence {1x JnnI C P2(X) converges narrowly to μ E P2(X) fx ((x)du, (x) > Jx ((x)dp(<z) for all Φ E (X). Convergence in the Wasserstein metric implies narrow convergence but the converse is not necessarily true. The extra condition to make it true is ma m2(ux) + m2(u). We
space (X2( W2)
denote Wasserstein and narrow convergence by Wass
and
Basrow
respectively.
If Ja E P2.abx()) v E P2(X), Monge's formulation is well-posed and the unique (μ-a.e.) solution exists, and in this case, it is safe to talk about (and use) the optimal transport map TV. Moreover, there exists some convex function f such that TV = Vf μ-a.e. Kantorovich's ' problem also has a unique solution y and it is given by 7 = (1,TW)+ #1 where is the identity map. This is known as Brenier theorem polar factorization theorem (1]
2.3 Subdifferential calculus in the Wasserstein space
Apart from being a metric space, (P2(X), W2) also enjoys some pre-Riemannial structure making subdifferential calculus on it possible. Let have a pieture of a manifold in mind. Firstly, the tangent
space of P2(X) at μ is Tan, P2( == (Veh: vf E (x)) (x(xx.x,)) where the closure is w.r.t. the 2 X. p)) -topoloy. Intuitively, for eh e CC + eV is an optimal transport map i > 0 is small enough (43), so V plays a role as "tangent vector".
Let Ø Px) [U (oo0), we denote dom(o) {u P2(X): ó(μ) < +oo Let μ dom(ø). we say that a map E L²(X, X, u) belongs to the Fréchet subdifferential [1 43) 87b(u) if Φ(v) (())= 2 sup,er,(H.)) Sxxx (E(z), z)d7(z, 3) + +o(Ws(H, for all v E P2(X), where the little-o notation means lim (s) 0. If (())) + 9. we say Φ is Fréchet subdifferentiable at μ. We also denote dom(0 {u E P2(X) 0p)()) 00.
Similarly, we say that & E [2 X 11) belongs to the (Fréchet) superdifferential (+)( of if - (m) In other words, 0, (m))(z) -F
We say ø is Wassertein differentiable 15 4 at μ E dom(ø) if Opp(p) n ( + 0. We call an element of the intersection, denoted by V Vwo( a Wasserstein gradient of Φ at μ., and holds Φ(v) -(()) fxxx (Vwo())(<z) y d>y v) + o(W2(u, for all Px(X) and any 7 (p, v). The Wasserstein gradient is not unique in general, but its parallel component in Tan, P2(X) is unique, and this parallel component is again a valid Wasserstein gradient as the orthogonal component plays no role in the above definitions, i.e., if g- E Tan, P2(X)+ it holds xxxx(5-(x)) x))d((r y) = 0 for any v E (X( and 7 E [ v) [43 Prop. 2.5]. We may refer to this parallel component as the unique Wasserstein gradient of Φ at J.
2.4 Optimization in the Wasserstein space
function ő :P((X) IR U {+00} is called proper if dom()) + 0. while it is called lower semicontinuous (I.s.c) if for any sequence pn Wass, μ, it holds lim inf, d(un) (()).

---

We next recall (a simplified version of) generalized geodesic convexity.
Definition 1. 165) Let ø P2(X) - R U (+oo). We say o is convex along generalized geodesics if VU, E P2()), , Vv E P2,abs (X), ( + (1 #V) S tØ(p) + (1 t))(T). Vt E [0, 1].
The curve t + (fT + (1 - t)TT)) # (called a generalized geodesic) interpolates from π to f as t runs from 0 to 1. The definition says that Φ is convex along these curves. If μ E P2, (X) and v = μ. the curve is geodesic in (P2(X), W2). If the definition is relaxed to the class of geodesics only, say that @ is convex along geodesics.
An important characterization of Fréchet subdifferential of a geodesically convex function is that we can drop the little-o notation in its definition in Sect. 2.3 Sect 10.1.1]. As convention, for geodesically convex function di the Fréchet subdifferential Op will be simply written as θ
First-order optimality conditions d (x) - RRU [o)) be a proper function. jr" E P2(
is global minimizer of if o(n²) 6(u), 8/2 E (x) For local optimality, we shall use the
Wasserstein metric to define neighborhoods. 1 E P2( is a local minimizer if there exists r > 0 such that o(x") < (()) for all μ W2,u,, < r. We shall denote B(4", .r) == {n P2(X):
W2(n, μ²) < rJ the (open) Wasserstein ball centered at n² with radius r. If we replace < by S we obtain the notion of closed Wasserstein ball.
We call 14" a Fréchet stationary point of ø if 0 E OFO(P"). Fréchet stationarity is a necessary condition for local optimality. In other words, if u² is a local minimizer, it is Fréchet stationary point (Lem. in Appendix). In addition, if Φ is Wasserstein differentiable at μ²" Two()"(xx) = na-a.ee [43 When @ is geodesically convex, Fréchet stationarity is sufficient condition for global optimality (Lem. in Appendix).
3 Semi Forward-Backwand Euler for difference-of-convex structures
3.1 Wasserstein gradient flows: different types of discretizations
To neatly present the idea of minimizing F via discretized gradient flow, we first assume for moment that F is infinitely differentiable and H is the negative entropy. See also a discussion in [65]
We wish to minimize ① in the space of probability distributions. A natural idea is to apply discretiza- tions of the gradient flow of F. where the gradient flow is defined (under some technical assumptions (3I) as the limit 17 - 0+ of the following scheme with some simple time- intepptteroolttion
Ma+1 E JKO,, (KO,,F(M)))) where JKO,, , (1) == arg min F(v) + 1 (v, 21j
xEPa(X)
Straightforwardly, given fixed > 0. 2 gives back a discretization for this flow known as Backward Fuler. On the other hand, if J is Wasserstein differentiable (Sect. (2.2). the Forward Euler discretization reads 770 fn++1 (I 7/ F(wn) which is reinterpreted gradient descent in the space of probability distributions. These are optimization methods that work directly the objective function F itself. However, the composite structure of F (a sum of several terms) can also be exploited. One such scheme is the unadjusted Langevin algorithm (ULA), where it first takes a gradient step w.r.t. the potential part, then follows the heat flow corresponding to the entropy part [70]: Va+1 = (I - v/ F) #n, and #4++1 = (0, 2nI) * Vn++1, where is the convolution. This ULA is "viewed" in the space of distributions (Eulerian approach). more familiar and equivalent form of the ULA from the particle perspective (Lagrangian approach) goes like Fn+1 2. V) + /2ijzz where Σ₁. NO0 7). The ULA is known to be asymptotically process). To correct this bias, the
doing
biased even for Gaussian target measure (Ornstein-Uhlenber Satropolis-Hasting accept-reject step 662 is sometimes introduced.
Cetrroolis-Hasstin algorithm [3] is a much more general framework that works with quite any proposal (e.g.. random walk) whose convergence analysis is based on the Markov kernel satisfying the detailed balance condition. This convergence framework is different from what is considered in this work: we are more interested in the underlying dynamics of the chain. Metropolis- Hasting algorithm is indeed another story.
In optimization, for composite structure, Forward- Backward (FB) Euler and its variants are methods of choice [59] 10) The corresponding FB Euler for F will take the gradient step (forward) according to the potential, and JKO step (backward) w.r.t. the negative entropy
(FB Euler)
Vn+1 (I (I-N) F) #Hn; and Mx+1 E JKO n (1
(3)
5

---

This scheme appears in [70] without convergence analysis, and later on [65 derives non-asympiotic convergence guarantees under the assumption F being convex and Lipschitz smooth.
In this work, as F is nonconvex and nonsmooth, the theory in 655 does not apply, and the conver- gence (if any) of (3) remains mysterious. The DC structure of F can be further exploited. In DC programming [60]. the forward step should be applied to the concave part, while the backward step
should be applied the convex part. We hence propose the following semi FB Buler
(semi FB Euler) Vn+1 (I H) #/nn and Mn+1 E JKO +())+
for which can provide convergence guarantees. Apparently, the difference between semi FB Buler and FB Euler is subtle: while FB Euler does forward on EG-H = &g EH and backward on H. semi FB Buler does forward on EE and backward H + &gi recall that J &g Eh H..
Theoretically, semi FB Euler enjoys some advantages compared to FB Euler. Thanks to Brenier theorem (Sect. 2.2 the pushing step in semi FB Euler is optimal since H is convex; Meanwhile, the pushing in FB Euler is non-optimal whose optimal Monge map is not identifiable in general. The convergence of FB Euler is still an open question, we can provide a solid theoretical guarantee for semi FB Euler, especially when is differentiable. Additionally, we also offer convergence guarantees when H is nonsmooth.
when F is (DC) differentiable. In contrast,
3.2 Problem setting
Our goal is to minimize the non non-geonoeene www.geeeeelllyyoooee convvxx functional F(U) = {F(μ) (5)++(++)))) + (p) over Px(X).
where F = G H is DC function. We make Assumption ! throoughut the paper:
Assumption 1. (i) The objective function F is bounded below.
(ii) G, : - TR are convex functions and have quadratic growth.
(iii) H P2(X) U (+o0 is proper, Ls.., and convex along generalized geodesics in (P2(X), and dom (x)) C P2,abe(X)
(iv) There exists noo > 0 such that Vn E no). JKO (E)+ + 0 for every μ E P2((X.
Note that Assumption Tiv) is commonly-used assumption to simplify technical complication when working with the JKO operator
15 65). Assumption T implies &g and Eι continuous w.r.t.
Wasserstein topology
3 Prop. 2.4] (G, are continuous
54
Cor. 2.27] and have quadratic growth).
3.3 Optimality charactizations
First, it follows from Assumption Dii). dom(F) C P2aba( (X). By analogy to DC programming in Euclidean space, we call n² dJm(F) a critical point of F = H &g En if H( + Eo)((²) n (E & G. Criticality is necessary condition for local optimality (Lem. 7 Moreover, if En is Wasserstein differentiable μ², criticality becomes Fréchet stationarity (Lem.
3.4 Semi FB Euler: general setting
We allow H/ to be non-differentiable in some derivations, meaning that 0H (convex subdifferential (54) contains multiple elements in general. We first pick selector S of dH, i.e., S
X, such that S(x) E (x). By the axiom of choice (Zermelo, 1904, see, e.g., (37). such selection always exists. However, arbitrary selector can behave badly, e.g., not measurable. We shall first restrict ourselves to the class of Borel measurable selectors (see Appx. A.] for an existence discussion). Assumption (Measurability). The selector S is Borel measurable.
We recall the semi FB scheme 4 but for nonsmooth F as follows: start with an initial distribution #o E a2, (XX), given discretization stepsize 0 < 17 < 1Jo, repeat the following two steps:
Pn+1 (I 4 push forward step; Pn+1 1KO0(eeo+.e (Pa+1)
JKO step.
Well-definiteness and properties: Given μh, E P2(X), it follows from Lem. 4 that 1n+1 E Pa (X). The two generated sequences are then in (2(X). Moreover, follows from Assumption that {un Junlee are in P2.aus (X), so are (2,, INEN using Lem. 9 by noting that I + S is subgradient of strongly convex function (I/2)][=[| (x).

---

Convergence analysis
4.1 Asymptotic analysis
Lemma (Descent lemma). Under Assumptions 7 and 2 let (un) be the sequence of distribu-
tions produced by semi FB Euler starting from some 140 P aaa (X) with 0 < nf < 1/- Then it holds
F(ua+1) S F(um)= + Jx [T (2) Tu 1 (x) dv (x), Vn E.
Lem. shoows that the objective does not increase along semi FB Euler's iterates. Proof of Lem. Iis in Appx. A.3 By using Lem.
!| we establish asymptotic convergence for semi FB Euler as follows.
For the asymptotic convergence analysis, we need the following assumption on H. Assumption 3. H contimuously differentiable.
Theorem 1 (Asymptotic convergence). Under Assumptions 7 let {unt IneN and {V IneN be sequences produced by semi FB Euler starting from some pin E P2, (X) with < 1) < 9o0- If neN is relatively compact with respect the Wasserstein topology and suPnen H (vn) t00, then every cluster point of {Un is critical point of
Proof of Thm is in Appx. A.4 Thm. T does not ensure convergence of the whole sequence (Fa Innn; Rather, it guarantees subsequential convergence to critical points of F.
Remark In the Euclidean space, the compactness assumption of the generated sequence usually enforced via the coercivity assumption: f(x) too whenever ||=||| + +oc. A striking difference in the Wasserstein space is that closed Wasserstein balls are not compact in the Wasserstein topology 443 Prop. 4.2], making coercivity not sufficient to induce ( (Wasserstein) compactness. For Thm.
we simply assume the sequence (Ja)net to be relatively compact.
4.2 Non asymptotic analysis
To measure how fast the algorithm converges, we need some convergence measurement. First, for proximal-type algorithms in Euclidean space, the notion of gradient mapping G,( is usually used (see, c.g., 33 155 and (38 Eq. (5)]) and we measure the rate [I,)(1,)] + 0. In analogy
as in Euclidean space, we define the Wasserstein suub)rrdieent mapping as follows G,(H) ==
T -=
and we measure the rate of (IC,,(())1222xxxxx
+ 0.
Theorem (Convergence rate: Wasserstein (sub)gradient mapping). Under Assumptions le {Na IeEN be the sequence of distributions produced by semi FB Euler starting from some μuu E Pz.be (X) with 0 < rj < no- Then it holds min,-i,x [19,, ll:a ONN-
Proof of Thm. is in Appx. A.5 This theorem holds without requiring G and H be differentiable.
Next, if H is twice differentiable with uniformly bounded Hessian, we can derive a stronger conver- gence guarantee based Fréchet stationarity (see Sect. 2.4). In other words, evaluate the rate of dist (0, F(r,)) = inf (E8g [lEll + U.
Assumption 4. H E (x) whose Hessian is bounded uniformly (H is then Lg-smooth).
Theorem (Convergence rate: Fréchet subdifferentials). Under Assumptions 7 4 let {Pa JnEN be
the sequence of distributions produced by semi FB Euler starting from some E P2,abaaX with
0 < n < To. then min I dist (0, F(u,)) 0 ( (N-2)
Proof of Thm. is in Appx. A.6
4.3
Fast convergence under isoperimetry and beyond
Fast convergence can be obtained under isoperimetry, e.g., log--ooolevv inequality (LSI). There are certain connections between LSI in sampling and the Lojasiewicz condition in optimization allowing linear convergence. In nonconvex optimization Euclidean space, analytic and subanalytic functions are a large class satisfying łojasiewicz condition 44 [4]. Subanalytic DC programs are studied in 45). In the infiiteediimensionall setting of the Wasserstein space, the Lojasiewicz condition should be regarded as functional incqualities [12].
7

---

Assumption 5 (Lojasiewicz condition in the Wasserstein space), Assume that F is the optimal value [0, and e > 0 such that for all μ E P2(X), F(u) - F < To + e (F(()) -F I inf [l[l[] : E OEFF(()) where the conventions 0º = 0 and inf () = +oo are used. We call 0 E [0, 1) the Lojasiewicz exponent of F at optimality.
of F, and assume there exist To E (F", +30],
Remark 2. If H is the is negative entropy, F E (X) whose Hessian is bounded uniformly, then F is Wasserstein differentiable at μ P2,,be (X) with gradient V F(u) Ye + VF provided that all terms are well-defined [43 Prop. 2.12, E.g. 2.3J. We have F
|| dx, where μe exp(-F). On the other hand, F(u)-F F = (KL(H)))") The log-Sobolev inequality with parameter > 0 inequality pla) ll dx, where FI(ullu²)) is the
I|I ( + +V((=)] du(x)= S((x) Vlog log ula) M(a)
reads 157) DKL (Kll)) S
1 FIGHl)H") == 2a [uxz) || VVog log (x)
20
relative Fisher information of μs w.E.. μ², Therefore, log-Sobolev inequality is special case of Lojasiewicz condition with 0 = 1/2. In another case, when the objective function the Maximum Mean Discrepancy, under some regularity assumption of the kernel, it holds 17)
2(F(() - F(())) & 11 pll x IIV
where "| - (4) the weighted negative Sobolev distance. This is "nearly" the Lojasiewicz condition, with a caveat that ||"" - - may be unbounded. Nevertheless, assuming the boundedness of this term along the algorithm's 's iterates is sufficient for convergence.
Theorem 4. Under Assumptions 1 4 and Assumption 5 with parameters (ro, c, 0). Let (UnJDeN be the sequence of distributions produced by semi FB Euler starting from some sufficiently warm-up No E P2, (X) such that F(Ho) ro and with stepsize O < < 17,, then
(i) if0 F(pn)= F converges to 0 in a finite number of steps;
(ii) if E (0, F(um) - F' F- ((MM))) where M 2(n2 Lop2Lyy
13y+1);
o21
(iii) i00 E (1/2,1), F(um) F converges sublinearly to ie. F(pn) - ( (n(tsot)))
=F=
=0
Proof of Thm. 4 in Appx. A.7
Remark 3. In the usual sampling case, i.e., H is the negative entropy, and under log-Sobolev condition, ro +00. Therefore, Pg0 can be arbitrarily in (2)aba()). In the general case, however, a good enough starting point (i.e., F(Po) < To) is needed to guarantee we are in the region where tojasiewicz condition comes into play. In such a case, F(um)_ = -KI DDI((pnlle
where A Aprovides convergence rate of {umINEN to μ* in terms of KL divergence and this convergence is exponentially fast if (0, 1/2]. Theorem 5. Under the same set of assumptions as in Thm. 4 the sequence {HnIner is a Cauchy sequence under Wasserstein lopology. Furthermore, as the Wasserstein space (P2(X) W2) is complete 15)
1²" (xx) ix exp(-F((s
( FF()) is the target distribution (see Rmk.
2 so Thm.
Thm. 2.2], every Cauchy sequence is convergent, i.e., there exists p² E P2(X) such
Wass μ² The limit distribution nº' is indeed the global minimizer of F. In addition:
that pm.
(i) if = 0, W2(Un, n²) converges to O in a finite number of steps;
(ii) 0 E (0, 1/2), W2(Un; 11*) (0)=;;"))== (
M
)))
where M 11 (2(1) Li +1))
M+I
(1-0)y c
(iii) i E (1/2,1), W2(pn, ((()),)() =
20-1
Proof of Thm. is in Appx. A.8 This theorem provides convergence to optimality in terms of Wasserstein distance.
Remark 4. If He is the negative entropy and 0 = 1/2, under some technical assumptions on F (e.g., continuously twice differentiable). LSI implies Talagrand inequality (57) (in optimization, known as tojasiewicz implies quadratic growth (40)), meaning that KI. divergence controls squared Wasserstein distance, so fast convergence under KI. divergence implies fast convergence under Wasserstein distance.
8

---

Practical implementations
The push-forward step Mn+1 (1 + + is rather straightforward: if Z are samples from Nn then Z + (2) are samples from Vn+1. On the other hand, to move from Pn+1 to Mx+1 we have to work out the JKO operator. Recent advances [53 2 propose using the gradient of an input-convex neural network (ICNN) [6] to approximate the optimal Monge map pushing Vn+1 to Mx+11 which we briefly describe as follows. This approach is inspired by Brenier theorem asserting that optimal Monge map has to be the (sub)gradient field of some convex function. Therefore, one can "parametrize" ja E P2,abs () as μ = Vipyy Pn+1 for some convex function th. We then write the JKO objective as
H (VVVat+))++ / ((V(())ddenn1()))) +
1 2m / 11~ (V(
(5)
While the two last terms (potential energy and squared Wasserstein distance) in (5) can be handled ef- ficiently by the Monte Carlo method using samples from U2+1, the first term H might be complicated as it possibly involves the (unavailable) density of Mx+1- We remark that the easy case would be % being another potential energy or an interaction energy. In such a case, Monte Carlo approximations are again readily applicable. The tricky case would be H being the negative entropy that requires the density of Vn+1- Fortunately, we have the following change of entropy formula: for any T X + X diffeomorphic, any E P2,,aa (X). it holds -X (Txp)) = - (p) + Sx log det (T())))((r). Therefore, (5) can be written (up to a constant that does not depend on (5)
[ log det (=)())) G(Vv(x))
2n || v=)(2)) du dv)-1(x).
Note that this entropy formula can be extended naturally to the case of general internal energy 2 which means can also handle this general case. Let
consider the entropy case for simplicity. We can leverage on a class of input convex neural networks [6] the (xx)
( (0 is the neural network's 's parameters, the input) in which + (x)()) convex. Optimizing over 0 can then be solved effectively by standard deep learning optimizers (e.g. Adam). The complete scheme is given in Alg. 1. We also remark that (2] further proposes fast approximation for log det V and [1 leverages on the variational formula of the KL to propose an even faster scheme. Nevertheless, these schemes are generally expensive. For illustrative purposes, we adopt the vanilla version of [53]. The iteration complexity is thus cubic in d, linear in the size of the ICNN, and linear in the iteration count k 533
Algorithm 1 Semi FB Euler for sampling
Input: Initial measure 140 (X), discretization step size 0, number of steps K > 0, batch size B. for A 1 to K do
for i = 1,2..... do
Draw a batch of samples Z no of size B;
....o < (T H/HH V V.Vo, o + H o o... (T.
W3 < 1
B Eşe= V (E) - E
07 +- 1 EeEz G 2 the (E)):
A.W. + - Σ CE log det (2))
L - 1 W3 + + A.H. 21
Apply an optimization step (e.g., Adam) over f using VoL.
end for
0z+1 f- 0.
end for
6 Numerical illustrations
We perform numerical sampling experiments from non-log-concave distributions: the Gaussian mixture distribution and the distance-to-ssttrrior [61] relaxed von Mises-Fisher distribution. Both

---

are log-DC and the latter has non-diferentiable logarithmic probability density (see Appx. C presents the sampling results. Experiment details are Appx. B and Appx.
Fig.
19
UIA
(a)
(b)
(d)
Figure 1: (a) and (b): Mixture of Gaussians. (a) shows samples obtained from semi FB Euler at iteration 40 and (b) shows KL divergence along the training process: semi FB Euler with sound theory is as fast as FB Euler. We also show the ULA's final result as a horizontal line for reference; (c) and (d): Relaxed von Mises-Fisher. (c) shows true probability density, and (d) shows the sample histogram obtained from semi FB Euler. In this experiment, FB Euler fails to work, attributed to the high curvature of the relaxed von Mises-Fisher.
7 Discussion and related work
We first narrow down our discussion on FB Euler and its variants in the Wasserstein space. When H is the negative entropy, Wibisono (70] provides some insightful discussion on how FB Euler should consistent (no asymptotic bias) because the backward step is adjoint to the forward step, hence preserves stationarity. However, Wasserstein space in 77).. Recently, Salim et al. [65] provide convergence guarantee for FB Euler within the following setting: H is convex along generalized geodesics, F is Lipschitz smooth and convex/strongly convex. This setting remains a "convex + convex" structure, while ours has "convex concave" structure. A natural extension of our work would be full-fledged study of DC programming in the Wasserstein space F و H where 9 and H convex along generalized geodesics and H. is not necessarily potential energy En. This problem possesses another implementation challenge regarding the Wasserstein gradient of H.
convergence theory is presented for FB Euler in the
Other works that bear tangential relation to ours involve the use of forward-only Fuler and UL.A. Arbel et al. 7 study Wasserstein gradient flows with forward Euler for maximum mean discrepancy. This objective function is also nonconvex (specifically, weakly convex). Durmus et al. [26) analyze the ULA from the convex optimization perspective. Vempala al. [67 show that LSI and Hessian boundedness suffice for fast convergence of the ULA where "fast" understood as fast to the biased target since ULA is biased algorithm. Balasubramanian et al. [9] analyze the ULA under quite mild conditions: log-density is Lipschitz/Hölder smooth. Bernton [I]] studies the proximal- -ULA also under the convex assumption, where the difference to the ULA is the first step: gradient descent replaced by the proximal operator. Similar to ULA, proximal-ULA is asymptotically biased. To address nonsmoothness, another line of research utilizes Moreau- Yosida envelopes create smooth approximations the ULA dynamics [29 [50]. This approach also applicable to certain classes of non-log-coneave distributions (50) and is more of flavour of discretization error quantification.
Conclusion
We propose a new semi FB Euler scheme as discretization Wasserstein gradient flow and show that it has favourably theoretical guarantees that the commonly used FB Euler does not yet have if the objective function is not convex along generalized geodesics. Our theoretical analysis opens up interesting avenues for future work. Given the ubiquity of nonconvexity, we hope that the idea can reused in various contexts, such as with different optimal transport cost functions, different base spaces in the Wasserstein space 42 or submanifolds of the Wasserstein space (e.g..
Bures- Wasserstein 42 24
OUr code is available httttttss//gthhii com/MCS-hub/OWa
10

---

Acknowledgments and Disclosure of Funding
This work supported by the Research Council of Finland's Flagship programme: Finnish Center for Artificial Intelligence (FCAT), and additionally by grants 345811, 348952, and 346376 (VILMA: Virtual Laboratory for Molecular Level Amoopheric Transformations). The authors wish to thank the Finnish Computing Competence Infrastructure (FCCI) for supporting this project with computational and data storage resources. We thank the anonymous reviewers for their insightful comments and suggestions. H.P.H. Luu specifically thanks Michel Ledoux, Luigi Ambrosio, Alain Durmus, and Shuailong Zhu for helpful information.
References
[1] M. Ahn, J.-S. Pang, and Xin. Difference-of-convex learning: directional stationarity, optimal- ity, and sparsity. SIAM Journal on Optimization, 27(3):1637-1665 2017.
[2] D. Alvarez-Melis, Y. Schiff, and Y. Mroueh. Optimizing functionals on the space of probabilities with input convex neural networks. Transactions on Machine Learning Research, 2022.
[3] L. Ambrosio, A. Bressan, D. Helbing, A. Klar, E. Zuazua, L. Ambrosio, and N. Gigli. A user's guide optimal transport. Modelling and Optimisation of Flows on Networks: Cetraro, Italy 2009, Editors: Benedetto Piccoli, Michel Rascle, pages 1-155, 2013.
[4] L. Ambrosio, N. Gigli, and G. Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
[5] L. Ambrosio and G. Savaré. Gradient flows of probability measures. Handbook of differential equations: evolutionary equations, 3:1-136, 2006.
[6] B. Amos, L. Xu, and J. Kolter. Input convex neural networks. International Conference on Machine Learning, pages 146-155, PMLR, 2017.
[7] M. Arbel, A. Korba, A. Salim, and Gretton. Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems, 32, 2019.
[8] M. Bačák and J. M. Borwein. On difference convexity of locally Lipschitz functions. Optimiza- tion, 60(8-9):961-976 2011.
[9] K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and S. Zhang. Towards a theory of non-log-concave sampling: first-order stationarity guarantees for Langevin Monte Carlo. In Conference on Learning Theory, pages 2896-2923. PMLR, 2022.
[10] A. Beck and M. Teboulle. A fast iterative shrinkage-threshooding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
[11] E. Bernton. Langevin Monte Carlo and JKO splitting. In Conference on learning theory, pages 1777-1798. PMLR, 2018.
[12] A. Blanchet and J. Bolte. family of functional inequalities: łojasiewicz inequalities and displacement convex functions. Journal of Functional Analysis, 275(7):1650-1673 2018.
[13] V. I. Bogachev and M. A. S. Ruas. Measure theory, volume 2. Springer, 2007.
[14] Bolte, A. Daniilidis, and A. Lewis. The tojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4):1205-12233 1223, 2007.
control problems. ESAIM: Control, Optimisation and Calculus of Variations, 25:52, 2019. [15] B. Bonnet. A Pontryagin maximum principle in Wasserstein spaces for constrained optimal
[16] Borwein and A. Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, 2006.
[17] G. E. Bredon. Topology and geometry, volume 139. Springer Science & Business Media, 2013.

---

[18] Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Com-
munications on pure and applied mathematics, 44(4):375-417, 1991.
[19] brett1479
http://tw....ceccccoooooo/oo//// sigma algebra of one point compactification.
Borel
Mathematics Stack Exchange.
(version: 2020-02-03).
[20] H. Brézis. Functional analysis, Sobolev spaces and partial differential equations, volume 2.
Springer, 2011.
[21] L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterizeed models using optimal transport. Advances in neural information processing systems, 31, 2018.
[22] Y. Cui, J.-S. Pang, and B. Sen. Composite difference-mas programs for modern statistical estimation problems. SIAM Journal on Optimization, 28(4):334443374 2018.
[23] A. S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(3):651- 676, 2017.
[24] M. Z. Diao, K. Balasubramanian, S. Chewi, and A. Salim. Forward-backward gaussian variational inference via iko in the burss-wasserstein space. In International Conference on Machine Learning, pages 7960-7991. PMLR, 2023.
[25] X. V. Doan and S. Vavasis. Low-rank matrix recovery with Ky Fan 2-k-norm. Journal of Global Optimization, 82(4):727-751, 2022.
[26] A. Durmus, S. Majewski, and B. Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. Journal of Machine Learning Research, 20(73) 2019.
[27] A. Durmus and É. Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1551 1587, 2017.
[28] A. Durmus and É. Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25(4A):2854 2882, 2019.
[29] A. Durmus, E. Moulines, and M. Pereyra. Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau. SIAM Journal on Imaging Sciences, 11(1):43-506, 2018
[30] M. Erbar. The heat equation on manifolds as a gradient flow in the Wasserstein space. In Annales de I'IHP Probabilités et statistiques, volume 46, pages 1-23, 2010.
[31] J. Fan, Q Zhang, A. Taghvaei, and Y. Chen. Variational Wasserstein gradient flow. In Proceed- ings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6185-6215. PMLR, 2022.
[32] J. Geng, L. Wang, and Wang. non-convex algorithm framework based on DC programming and DCA for matrix completion. Numerical Algorithms, 14:903-921. 2015.
[33] Ghadimi, G. Lan, and H. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1):267-305, 2016.
[34] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[35] Hajlasz. Is there Borel measurable f _ + gd such that f(x) E 0p((x) for all x? (version: 2023-12-02).
MathOverflow. htthtp/s//naahooerrloow.////////
[36] W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. 1970.
[37] H. Herrlich. Axiom of choice, volume 1876. Springer, 2006.
12

---

[38] S. Reddi, S. Sra, B. Poczos, and A. J. Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016.
[39] R. Jordan, D. Kinderlehrer, and F. Otto. The variational formulation of the Bakker-Plandee equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
[40] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak-tojasiewicz condition. In Machine Learning and Knowledge Discov- ery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795 9058811.2 Springer, 2016.
[41] A. Korotin, Egiazarian, A. Asadulaev, A. Safin, and E. Burnaev. Wasserstein-2 generative networks. In International Conference Learning Representations, 2021.
[42] M. Lambert, S. Chewi, F. Bach, S. Bonnabel, and P. Rigollet. Variational inference via wasserstein gradient flows. Advances in Neural Information Processing Systems, 35:14434- 14447, 2022.
[43] N. Lanzetti, S. Bolognani, and F. Dörfler. First-order conditions for optimization in the Wasserstein space. arXiv preprint wrXivv2209.12199 2022.
[44] S. law Lojasiewicz. Ensembles comi-analytiques IHES notes, page 220, 1965.
[45] H. A. Le Thi, V. N. Huynh, and T. Pham Dinh. Convergence analysis of difference-of-convee algorithm with subanalytic data. Journal of Optimization Theory and Applications, 179(1):103- 126. 2018.
[46] H. A. Le Thi, V. N. Huynh, T. Pham Dinh, and H. H. Luu. Stochastic difference-of- soveexffncciion algorithms for nonconvex programming. SIAM Journal on Optimization, 32(3)22233-2933, 2022.
[47] H. A. Le Thi and T. Pham Dinh. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of operations research, 133:23-46, 2005.
[48] H. A. Le Thi, T. Pham Dinh, H. M. Le, and X. T. Vo. De approximation approaches for sparse optimization. European Journal of Operational Research, 244(1):26 46, 2015.
[49] M. Lec. Smooth Manifolds. In Introduction to Smooth Manifolds, pages 1-31. Springer.
[50] T. D. Luu, J. Fadili, and C. Chesneau. Sampling from non-smooth distributions through Langevin diffusion. Methodology and Computing in Applied Probability, 23:1 2021.
[51] Mei, T. Misiakiewicz, and A. Montanari. Mean-field theory two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
[52] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and Teller, Equation of state calculations by fast computing machines. The journal of chemical physics, 2166):088-1102, 1953.
[53] P. Mokrov, A. Korotin, L. Li, A. Genevay, J. M. Solomon, and E. Burnaev. Large-scale Wasserstein gradient flows. Advances in Neural Information Processing Systems, 34:15243- 15256, 2021.
[54] B. Mordukhovich and M. N. Nguyen. An easy path to convex analysis and applications. Springer Nature, 2023.
[55] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science Business Media, 2013.
[56] M. Nouiehed, J.-S. Pang, and M. Razaviyayn. On the pervasiveness of difference-convexity in optimization and statistics. Mathematical Programming, 17522):19-222,, 2019.
13

---

[57] F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Funetional Analysis, 173(2)3611440, 2000.
[58] J.-. Pang, M. Razaviyayn, and A. Alvarado. Computing B-stationary points of nonsmooth DC programs. Mathematics of Operations Research, 42(1):95-118, 2017.
[59] N. Parikh, S. Boyd, et al. Proximal algorithms. Foundations and trends@) in Optimization,
1 13)::127-339 2014.
[60] T. Pham Dinh and H. A. Le Thi. Convex analysis approach to DC programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1):289-355, 1997.
[61] R. Presman and Xu. Distance-to-ses priors and constrained Bayesian inference. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 2310-2326. PMLR, 2023.
[62] G. O. Roberts and R. L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996.
[63] R. Rockafellar. Lagrange multipliers and optimality. SIAM review, 35(2):183-233) 1993.
[64] R. T. Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
[65] A. Salim, A. Korba, and G. Luise. The Wasserstein proximal gradient algorithm. Advances in Neural Information Processing Systems, 33:12356 12366, 2020.
[66] A. Taghvaei and Mehta. Accelerated flow for probability distributions. International conference machine learning, pages 6076-6085. PMLR, 2019.
[67] S. Vempala and A. Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[68] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[69] C. Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
[70] A. Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as
composite optimization problem. Conference on Learning Theory, pages 2093-3027. PMLR, 2018.
[71] H. Zhang and Y.-S. Niu. A Boosted-DCA. with power-sum-De decomposition for linearly constrained polynomial programs. Journal of Optimization Theory and Applications, pages 1-40, 2024.
[72] X. Zhou. On the Fenchel duality between strong convexity and Lipschitz continuous gradient. arXiv preprint a 06573, 2018
14

---

A Theory
Lemma (Transfer lemma). 1 Sect. Let T IR Rh a measurable map, and μr E P(RR)) then T# E )((R") and f (())d((+))(x) = ()(r)d(())) for every measurable function f: IR" + R, where the above identity has be understood that: one of the integrals exits (potentially =oo) iff the other one exists, and in such case they are equal. Consequently, for bounded function J. the above integrals exist as real numbers that are equal.
Lemma 3. 4 Rmk. 6.2.11] | Let μ. V E P2,abs then T. o Tp p.a.e. and T3 o Tリ I v-a.e. Theorem 6 (Characterization of Fréchet subdifferential for geodesically convex functions). H Section 10.1] Suppose Φ P2(X) + R U (+00) is proper, l.s.c. convex on geodesics. Let μ E dom(06) (3)) P2.abe (X)) then vector & L Xx, belongs the Fréchet subdifferential of á at if and only if
/ (E(x). x)dp(x)) Vv E dom(
Φ(V) 6(1) 2
Lemma 4. Let H X + R be convex function having quadratic growth and & be measurable selector of 0H, i.e. E(x) 0H (x) for all x E X. Then, for all E P2(X).
f [1((=)))<p(()) < t00.
(6)
In other words, g (X, X, for all E P2().
Proof. Since E(x) E (x), by tangent inequality for convex functions, we have H(y) 2 H(x) (E(x). x), Vy X.
By picking y = (x) for some 0, we get
H(r + <f(x)) H(s) 2 (E(x),<E(x) <|(E(>))12
(7)
Since H has quadratic growth, for some 0,
+ H(x+<((x)) H(x) < | + <((x)) [+(x)
<a <a<
a(|==|+ 1)
s 2a +
s 2a + 20ll
2a + 3a||=|| 2a
Combining with (7) holds
c(1 2ac) 2a
22 3/112112.
By choosing 0 <<< 1/(2a), obtain
2a
3a
|E(x))] < c(1 2ac)
+
||
c(1
2ac)
Therefore, [| has quadratic growth and consequence holds for any μ P2(X).
Lemma 5. Let Φb P2(X) TR U (+00) be proper function. Let μ¹ be local minimizer of o. then μe' is a Fréchet stationary point ob
Proof. There exists such that x(p)) S 6(p) for all μ E P2(X) We(p, <r. It follows that
inf Φ(1) o(w²) W2(u, w*)
0,
so 0 OFp(""), n² is Fréchet stationary point of o.
15

---

Lemma 6. Let P2(X) + {+oo) be a proper, l.s.c, geodesically convex function. Suppose that μº (X) is a Fréchet stationary point of o. Then, μ² a global minimizer of Φ.
Proof. By definition Fréchet stationarity, E @D()") By characterization of subdifferential of geodesically convex functions (Thm. 6 it holds ((u) 2 <(n") for all μ E dom( or μ is globall minimizer of p.
Lemma 7. Under Assumption 7 let μº E (Fm(F) be local minimizer of F, then p² is critical point of F, i.e., HHH + (u) n (dE + 0.
Proof. Since j² a local minimizer of F, there exists > such that
F(p²) S F(1), Vu E Px()) W2(u; (*)) <.
(8)
Let be a measurable selector of 0H. Thanks to Lemma E E (2 X, n²). According to Prop. 4.13), (p") It follows from Thm. that
[5]
(H( 2 En(U²) / (E(=), TH (x) (x))))d(( x)),((z), VA P2()).
(9)
From 8 and 9 for μ E B(w",r)
H()) Ed(n) 2 (((") ) + Ea(n") + / (E(x), z)dp"(1)
Therefore, E 0 + (x) since He Eg is geodesically convex. It follows that ja" is a critical point of F.
Lemma 8. Let : P2(X) + [oo). Assume that U and V are Fréchet subdifferentiable at fs, the following statements hold
0F ())+ 0P((H) (())
b. Vf is Wasserstein differentiable of p. then
+ = 01((1) + VwV(u).
(10)
Proof. Item is trivial from the definition of Fréchet subdifferential. For item b., from item a., first see that,
0u + V)(x) > 0F4((4) + Vw On the other hand, we apply item a. for 21 + and -v to obtain
(11)
0FU(1)) P 07 V)( (=(-))(m).
Since V Vw (n), it follows that 0F4(m)) 5 (p + V)(x) - Vwn(
(12)
From
and 12 we derive 10
Lemma 9. Let < Ld, and is a strongly convex function. Then V < Ld
Proof. Let - fa: (z) exists), then S (2) .2) (Aleksandrov, see, e.g., Thm. 5.5.4]). Since g is strongly convex, Vg is injective on l and det 42 on Ω. By applying Lemma 5.5.3
Vgau << god
Lemma 10. 655 Let G: P2(X) - [U(+))) be proper and l.s.c. Suppose that & is convex along generalized geodesics. Let v E Pzabe (X), p. E P2(X). Ifß E ag(μ), then
{ 16 o (x) (x)x) - (x)) g(x) g(n).
16

---

A.1 Existence of Borel measurable selector of the subdifferential of a convex function
Given a convex function H X + R. we prove that there exists a Borel measurable selector S(z) E (z). Although this problem is of natural interest, we are not aware of it as well as its proof least standard textbooks in convex analysis. Credits go to quite recent MathOverflow thread (35, from which we give detailed proof as follows.
Firstly, we recall Alexandroff's s compactification of topological space (X, From set theory, X is strictly smaller than 2x which is the set of all subsets of X, i.e., there is no bijection from to 2x So 2 cannot be contained in X. So, there is an element named oo that is not in X. We denote X = x [oo).. One-point Alexandroff compactification states that (I) there exists a topology T in X accepting X as topological subspace, i.e., the original topology in X is inherited from Th, and (2) (Xx* r is compact.
The topology n can be specifically described follows: open sets of T are either open sets of or the complements of the form (X \ ()) U {oo} where S are closed compact subsets of X.
In our case, X _ and is the standard Euclidean topology, the Alexandroff compactification of X is also metrizable [7 Thm. 12. It is, in fact, homeomorphic to the sphere S whose topology inherited from the ambient space IR Rd+11 Moreover, the mentioned metric the Riemannian metric of gd 44 Thm. 13.29].
Secondly, since vixx) == (x) + (1/2)||=|| is 1-strongly convex, its Fenchel conjugate y (1) defined as
6- (v) sup (z. v) (x)) =ERd
is I-smooth [72 Thm. 1].
By 64 Cor. 23.5.1], I,, (0o)-1 = V 60 in the sense that
y E (Vb"" (y)) Vy Rdd
(13)
On the other hand, Ob is strongly monotone [54, Ex. 3.9] in the following sense,
(I2 - x1, yn) 2 || - x 1
(14)
for all vi, 22 E Rd and E Ob(()) y22 E (x2)))
We see that Ve* is subjective. Indeed we show that for every x E Rdd, there exists y E Rdd such that V (v) = x. We show that relation holds for any y E (v(x)). ). By contradiction, suppose that
V (y) * x. From the strong monotonicity of Oe in 14. Oup(Ve (v)) n (v)
However, from 113 and by the choice of y, it holds y E O.p( (V o (v)) n (x). This is a contradiction.
Thirdly, we recall a fundamental result on the compactness of the subdifferential of convex function: if C' is compact, then (C" is compact 64 Thm. 24.7].
Fourthly, need the Sederer-Morse theorem
as follows:
Theorem 7. Let Z be compact metric space, Y be Hausdorff topological space and f Z - Y be a continuous mapping. Then, there exists Borel set B C Z such that fB) f(Z) and f is injective on B. Furtheremore, f-1 f [(Z) + B is Borel.
Now we observe that Vv² + oo was x - oo. Otherwise, by using the compactness of Oyp and (13), we will get contradiction immediately. We then can extend Vi²" in continuous way in the Alexandorff compactification space X = Rd U {co} by simply putting V (oc) = c0. We shall show that this extension of V v is continuous from (X', to (X ) ). (Vo**)-(( for all V E 700 Recall that, by construction, open sets of 70 are either open sets of or the complements of the form (X \. S) U [oo} where S are compact subsets of X. The former type of open sets is handled easily since V is already continuous in (X, r). For the latter type, let U (v ((X) \ S) U (co))
E soe
\ 8) foo) (X (Vb")- (S)) U (oc) for compact set S. Proving U open boils down to proving (V (S) compact. Indeed, it is closed since S is closed. It is bounded. Otherwise, it will be contradictory to Vib" (x) - xc as x co.
(V
We now can apply the Federer-Morse theorem for = = (X"0 70) by noting that (X*, 70) metrizable and metric space is Hausdorff space, and for f = V there exists Borel set B C
17

---

X such that V B - X is a bijection and the inverse mapping (< x + B is Borel measurable (here Borel set/meeauraaiiliy are with respect T not yet r). This the Borel (w.r.t. 72) selector of Oyp.
Finally, need convert Borel measurability w.r.t. 7 Borel measurability w.r.t. т. In terms of mapping, oo is mapped to oo either way around. So we only need to show: (V 7 (B) : X - X is Borel measurable w.r.t. т. Take any Borel set (w.r.t. E X, (V (B) E) is Borel set w.r.t. 7he and does not contain co. We shall prove (Ve*lB) (B) n E) is a Borel set w.r.t. т. This follows directly from the following claim, which from another Mathematics Stack Exchange thread [9].
Claim 19
= (oo)) = a(r) (V V VEa(T))
(15)
A sketch of the claim proof goes follows. For the first equality in (15). first we have ( c
(+20) because (1) C - and (2) [oo] = Xx \ E a(T>) as X, X E T On the other
hand, (17%) Co(TU (oo)) because, again, of the construction of T let U E 7 if r then U E (T U {oo)), otherwise U (X \ {oo} for some compact set S C C. As X = R S closed, so (S) E implying U E (
U (oo)) For the second equality in (15), is straight
forward to verify that 4 == (T)) {V foo) V a(r)} is sigma-algebra in X². Since
r U fooo
C. 9, holds ((oo)) C G. Conversely, as (T) C C {oo}) and consequently.
VU (co) E ( U (coo) for all V E a (T), it holds y C Ca(T (oo)).
We conclude that (V**'B)~
X - is Borel (w.r.t 7) selector of op. As consequence, S = (Vi) (Vo*lB) [B) - / is Borel measurable selector of 0H.
A.2
Maximum Mean Discrepancy
A.2.1
Definition
The notion Maximum Mcan Discrepancy (MMD) between two distributions is introduced in 34 Given a kernel k: X x X + IR and denote by K. its reproducing kernel Hilbert space. Given two distributions f and v, the maximum mean discrepancy between them are defined
DMML (1, v) = I[feells, where fum(2) = / x)dx()) - 2ddx(),,( Vz 1 EX,
where fa. is called the witness function. Given some target (or optimal) distribution μt, we seek to optimize F(H) DMMLL (²) Note that F(u) admits the following free-energy expression 7
F(n) / F(x)))(() - _/2 Mx,, (la,z'ddpe ((ppo)))p()))) C
where
F(x) - -000=-/oo - ((x,'')dx'''') C= C=
1 Max, x')dy" (x)))((
In general, F is not convex along generalized geodesics. Rather, it exhibits some weakly convex structure 77 that falls within the DC spectrum as detailed in Subsection A.2.3
A.2.2
Connection with infinite-width one hidden layer neural networks
See also
65
include the discussion here for completeness.
Consider one-hidden- neural network
f(x) = (b 23)
where (xx, wya 0,)), 2, = (0,, wx) E the parameters (in and out) associated with i-th hidden neuron, is the number of hidden neurons, is the activation function.
18

---

When the number of hidden neurons tends to infinity, f can be written as f(x)) (xx =)dp(z) for some distribution μ over the parameter space Z. Given data (æ, v) p(z, y) and assuming quadratic loss, the optimization problem reads
D(1) == B(a.e))p(aa)) (u- ((rr))du(z))
min (2)
We assume that the model is well-specified, i.e., there exists u¹ E P2) such that
E Ey-p(sla) = = (1 2)d,")"
(16)
Expanding L, we get
[(N) -2 / Sta.))-pta. 2)) + /I Bemp(on (1,
2)0(2, (ddx2)))p(()) + C
where C does not depend on Jr.
Naturally, we define the kernel
M(2, = Euwp(t)) (1) =)x(z,,))) Vz E Z.
Using the assumption that the model is well-specified [6
we obtain
J k(z, 2')dx(((("")
/ Bewpta 2)0(2, dd)
Eppp(a) (ʃ (/ 2) zd)dn"( (2')
= Erup(() ((x,2) /
s02 2')dp" (o4p"(?" (2')
Bawp(a) (1b(1, 2) =)Bypp(ol))()) ~((,s) (yb(a, z))
Therefore, L can be written as
du(z)+ + If k(e,2))du())dd(() + ((N) -2 M(ee (x)) (c))d)()++
This is exactly the MMD setting in Sect. A.2.I
A.2.3 DC structure
Let be a kernel whose gradient Lipschitz continuous, i.c., for some L > 0,
VV((,,)) Vh(a', w/)ll s (1|æ 2' l1 v1 Vr,,', e X,
which can be expressed equivalently
[V y) v='(''''')11 + [V,A(z,,) - vyk(a', w/11 < L2 (1|= - x' + l1 - of 3/13).
Let μ² be some target distribution and consider the free-energy functional
F(H) = // k( MZx, (dd - //
k( k(x, v)d (v)dp(x).
Let a > O, we can rewrite F as follows
F(n) = /ʃ [a||>|| + allyl + k(.. v)] du(x))d(w)) - / |alla|12+ h1, ((), du(x).
19

---

As is Lipschitz smooth w.r.t (z. v). x + I kxx, (dpp) ) is also Lipschitz smooth. Indeed,
V ((r, v. k(z',y)du"
// (Vak(o,)) Vak(o', ,)), (w))
- [ Vak(z', F dyc(())
S T. (f ||0 ||0- s''1 du du)(w)) (u)
T.|1x: x'1l-
Next, as a standard result, f is an L-smooth function, x + (a/2)||>||2 + f(x) are convex whenever 2 L. Therefore, for L. (z, a a||=||| + ailyil? <kx, is convex and F(x) - [a||==|| + Jx k(x, v)du" (v) is concave. From 4 Prop. 9.3.5], the interaction energy
corresponding to W is generalized geodesically convex.
A.3 Proof of Lemma
Since + 7 is subgradient selector of a convex function, the optimal transport between An and Un+1 is given by
Tha+1 + n/S.
(17)
and between Mn+1 and Pn+1
4 Lem. 10.1.2]
Th E I + 110 (Eg + H²) (pn+1).
(18)
Since En is convex along generalized geodesics [4. Prop. 9.3.2] and S subgradient of En at pm [5] Proposition 4.13), by Lem. 10 it holds, for any E (2,ab((X))
E (Pn+2) 2 (um) + / (S TV. (x),
(x), Th (x) TV" (z))dv(xx).
By choosing v = Vn+i (note that Uat1 P2,ab(())
(n(4))1) 2 (n((n) +
o (I), Thit1 (x) Thto (x)) (x))) (x)
xx
=En(un) + / ((TWa+) - 1) Tha Untt (x), THa-l (x) - buts (x)))dnnt
E /
Titn Unti
(z),
The (x) The (x))
(19)
x
where the second equality uses 17 and the last one uses Lem.
On the other hand, since &g + H is convex along generalized geodesics, by applying Lem. for Eg + H at pn+1 with subgradient 17 (T I) E Ö(EG + H (pn+1) (from (18).
(Eg + H (mn)
> (Eg + Ht (kn+1) + /
(Teb+t - I) Bull
Tmuil (I), THkn (x) Thant (x) (denti(e)) Matt
fx
= -EG + H H) (1m+1) + 77 x
/ (x Tunti (z), TH (x) - Thun (x)
(x) ddn+)(()
(20)
where the last equality uses Lem. 3
By adding
20 and 19 side by side,
F(um) 2 F(un+1) + =
|| Dan (x) - Thunti de))()))+++()))
(21)
17
20

---

A.4 Proof of Theorem
Let v² E (2(X) be cluster point of InEN. There exists a subsequence Umu
Wass
p It holds
lim inf F(jm,,
inf (1eme) ) + Er(Hn)))
k-+00
k-000
lim inf H (Umu) + Ep(H))
100
2 H (1") Er(u"),
since H I.s.c. and EF is continuous w.r.t Wasserstein topology. Therefore, (x²) to0, which further implies that μ E (X).
We have
/x
/ |T (2) Thaat
1 knls (2) - Th (1)
# Hn (z()
Mm
/ ||x - Va4s
Tha-t
(x) (x))(p())))))
(22)
We observe that Te T is a (possibly non-optimal) transport pushing pn to un+1 by the optimality of Titxt.
{
|1 Th T (x)n) 2 / 1| -htn+t (x))12 = W2 Mo+1).
(23)
Pm
By Lem. Tand (22p.
F(um) 2 F(un+1) + W3 (Mu pa+1).
(24)
Note that F is bounded below (Assumption
1. telescoping 24 gives
(p +00.
(25)
In particular, W2(Un; (n+1) 1) + 0. This together with Pau
Wass 4² implies Un++1
Wass
Under Assumption S = V and S is continuous. Next, recall Un (I + n) Mrx we show
Png+1
narrow
v² (I n) n² as k +00
(26)
Thus, let f be continuous and bounded test functional in X, by using transfer lemma
lim / f(x)d(I + 118) Umn (x) k-t00 / f(z)dvm(+1(x))
lim k-
lim ((()))(z))ddmal k0000
(27)
[(x [(++n((z))dd
f f(z)dv(<x)
(28)
since S is continuous. So +1 V²" We go one step further and prove that +1 actually converges to v" in the Wasserstein metric. This boils down to showing convergence in second-order moments, i.e.,
narTOW
(2 m2(1"),
which is equivalent to showing that
{ || + n](x)) (x) (I) + / || nS(x))l
21

---

On the other hand, (xx)) :- (x))] has quadratic growth (follows from Lem. and Pnz + 1c in the Wasserstein metric, so [ Prop. 2.4]
lim 40000
|| [z)) (x))
||0 n)((x)) (x)
Therefore, V1 + D² in Wasserstein metric.
To proceed further, we need the following theorem stating that the graph of the subdifferential of a geodesically convex function is closed under the product of Wasserstein and weak topologies.
Theorem 8 (Closedness of subdifferential graph). M Lemma 10.1.3] Let & be geodesically convex functional satisfying (D6) Px,aba(X)). Let (Un be a sequence converging in Wasserstein metric to E dom(()) 6). Let En E @Ō(un) ) be satisfying
sup
< t00,
(29)
nEN X
and converging weakly to & E (X, X, n) the following sense:
lim / (z) = J (()))())dp(x)) (X))). 10000
(30)
Then & E d0(p).
As side note, need the notion of weak convergence in the above theorem because unlike subdifferentials in flat Euclidean space - each E. lives in its own L22(X, X, (n,) space.
Back to our proof, for item 29 we show that
sup nEN X
TTe (ar) ar12 dpp (x) +00.
(31)
We proceed as follows to prove (31) We first show that suPnen ma(un) 400, By contradiction, by assuming SuPnEN ma (ft) = +00 we can extract a subsequence [Mng JAEN such that
lim m2(mnr) k-
+o0.
(32)
By compactness assumption, there further exists a subsequence {Ma heN such that fon, converges (in Wasserstein metric) to some nx" E P2().. implying that lim, my m2(Pna,) = m2(n")) which contradicts (32). Therefore, SUPREN ma (14)) < +oc. We next show that suPMEN ma (2 < +o0.
Indeed, as || has quadratic growth,
||(())]1 z c2(1=]12 + 1)
for some 0. So
m2 (v
|/=1Pp((TT + #)))))))z)))))
x
/ ||
< 2 ||0|/=dpm (x) + 217² [1((z))ldp,,(1))
x
< (2 + 207j² )m 2r7²c.
implying that sN ma m2(un)
< +oo. This in conjunction with having quadratic growth
plies that supwEn (G(u,) +oo. Furthermore, inf, (Eg + +x) (H,)) -x otherwise by lower
semicontinuity of H and compactness of (um JeE we get a contradiction.
Now, as (T - 1) E 2 (Ec + H) (Mx+1) and &g + HH is geodesically convex, by applying Thm. 6 holds
1
(Eg (C)++)(vx+1)) 2 (Eo + H (un+1) +
[ (2)) x112 =x)ddun+1(())
(33)
71
22

---

The finiteness as in 31 then follows from suPnen (Eo(k,)] < +oo, supnen - (Eg + HPn) < too as proved and suPner (v,) too assumed.
We next prove that there a subsequence of {Mmn kEN such that
Mok, +1 Tpeiy +1 + Tw- weakly.
(34)
We consider the sequence of optimal plans between pn and Vn as follows
Pn (1, (Mn #M
Vn N.
We observe that
du, (v) < +oc, m2(pm) = f |xxx (1|=]1²+ + Ilpl3) (p. = 1/x 11x11/dppnn0) + / dlvl
so E P2(XxX) for all n E N. Since supneN (2() < +o0 as proved, and as Wasserstein ball relatively compact under narrow topology, {Un JNEN relatively compact under narrow topology. The same property holds for {pa JnEN. According to Prokhorov 3 Theorem 1.3], {Uo JaEN and
fun fnnineN are tight. By B Remark 1.4]. JpnN also tight, hence relatively compact under narrow topology in (2 x X). Consequently, {pr+t1 admits a subsequence converging narrowly to
some p* E P(X X). Let's say
Pmu, +1
NATTOR p" as + 00.
(35)
We can that proj1 1e, projz V². We further show that p" P2(X X). or equivalently,
Jxxx 11ll v) to0.
(36)
Let C E N, thanks to the narrow convergence in (35) we have
Sxex xxx
min + Cidpm, +1 + f xxx
min + Cldp Cydp'
Furthermore,
m 11 CPP,,Cdd,,,, +1 (x, sup m2 + sup m2 == M +00. neN
Jxxx
neN
Passing to the limit, get
fxxx min[1] + (x, S. M
for all C N. Sending C' to co and applying Monotone Convergence Theorem we derive (36).
Back to the main proof, since tieeN is sequence of optimal plans, its limit, p² is also optimal 3, Proposition 2.5]. Therefore.
p" (I,TT=) )
Moreover, as
m2(pon.+1) m2(Unn,+1) + mz(Unn, +1) mz(u²) + m2((²) m2(pp))
have
Poz, +1
Wass
p" as i 00.
Now let's take any test function & (X), we show
Pnc, (z) (c)dpmne-111) = / (x)d
lim j
((x)Tame)
(x).
(37)
23

---

Indeed, (z, + ((x) (v) where proj; is the projection into the i-th coordinate is continuous and has quadratic growth since ((x) is bounded and proj: is linear.
Since Prxy +1
Wass p. it holds: for each E [d].
Many tt +1 (x) dymne +1(x) lim / ((x) proj: (Immny 5
/ ((x) proj Tuney
Mann t1 Honn + (20, v)
lim
1-000
/ ((x) proj, (roj. (w) (1,
lim
/ ((x) (roj (2,y)
/ ((x) (roji T D41" (x,u)
x
((x) proj (T (x))du"
SO holds. Consequently, 34 also holds by noticing that
J
x<( ((())d + (x) - / (x) as +
By the closedness of subdifferential graph of 0(Ea + H) (Thm. 8
we obtain
T
E EEE + H (1²))
(38)
11
On the other hand, by the definition of n² in (6). get T I + nSS. Together with (38).
S 0(EG (w"). Noting that S H (H²*), holds S a(Ec + (2²) n dE (4*) and conclude μ is a critical point of F.
A.5
Proof of Theorem
We see that
/
JKO aee so) (((+))))++))))))))))))) (00) dx)(()
(9,(
=
x Tp
172
1
W22 (pn, JKn 1KO0(EE++ee ((I (I+ #)m))
1/2
W2 (pas (n-1).
1/
On the other hand, it follows from
25 of the proof of Thm. thatt
min (M Mn+1) O(N-1)
1
A.6 Proof of Theorem
H has uniformly bounded Hessian, by 43 Prop. 2.12], En Wasserstein differentiable and V En()) = AH for all μ E P2(X). According to Lem. and (8)).
2. puti
- V
Flunt)) a(Ea (Un+1)) GHG
(39)
n
24

---

We then have the following evaluations:
dist (0, F(
inf || (1(1
Thut -I VH
3
putl (2r) - -VH(( d()n=(()) (
1
1
(2) x (VH((())(2dppttx))
(40)
By transfer lemma 2
The (x) - -x - 1>--(((2 (z) dppnzaa))
X
= / Tiatt (1) - (x) dT Un+1 (2)
/ | o T (x) (I + nVH Tout (x) dv)+i(x)
f |12 | (I+ o Tuat (ar) ||
den+1(a).
(41)
On the other hand, by using the trivial identity
(T ( - VH
we compute,
WH Unts (x)) VH(T (1))) dz))1())
(1 + HV) The (x) Vo-l (x) (I+nVH) That (x) Tohat (x))
2
(v)+1
r72 J 1|-- Tkn t (x) (T + H) Tuaat (x) + THa-! (z)) denta(z).
(42)
where the last equality uses (I + VH) Pat1 = Va+1 a.c.
The Hessian of H is bounded uniformly, V Lipschitz, let's say (()())(((()) S LH||z-v| for all x, y E X. We continue evaluating 41 as follows
f |x (I + VH) o Moni
1 (d))[ (1))
[| - TT (I) (I + H) Thnts (x) + Th (x) + THtn (x) - -h (z))l) du (x)
x
2 x
x Thin (x) - (T + // V) o Thutt (x) + Thut (x) denti(z)
+
11225 (x) - -Thnti (x) du (x)
/ |T (x)) (T (z)) dv +2 / 11THn (x) -Thot1 (x)) dd)) (x)
2n²²
/ |[T Vazz (x) Thiy (x) (x)
S 2(1 D3 + 1)
(43)
where the third equality uses 42
25

---

From 40
and 43
we derive
v2 Li 1)
| 1 (5) Tunt (w))Pdeent(00)) (44)
dist (0, F(m 2
7
On the other hand, by telescoping Lem.
we obtain
Σ
| Mats
(x) Thaat denti < +00.
==1
Therefore,
dist (0, 0t F(put1))
==0
22 2 L 1)
N-1
Σ
[ (x) - Thutt
( (1) (x)) dun (()))t)))))))))
7
n=0
2 Li +1)
N
Σ
[T Ma- (x) That (du (2))
1
211 L3 + I1N
+oc Σ
T Muts
(x) -hhnt (x))l
n==
We derive
min dist (0, of F(un)) =0 ( n=I,N
1
VN
A.7
Proof of Theorem
Convergence in terms of objective values
Since H E (x) whose Hessian is uniformly bounded, recall from
39 that
Thl+t
F( A(EG + H ()(++) V
VH.
7
Since F(Ha)- -F < ro and the sequence (F(pz) not increasing (Lem. 1. F(Hx) F < <r for all n E N. Lojasiewicz condition implies
((F(m+1)) - FF <
VH
T (x) v(((z) dppzi(())
/ 22 L2 1)
(
| Duts (x) - -Thnt (2)]
(45)
where the last inequality follows from Combining with Lem.
41 and (43) and Lu is the Lipschitz constant of H..
D we derive
2(1 +
c (F(untt) - <
(F(un) - F(un+1))
or
((In41)-Ftt) < 2(n 2 + +) 2n
((F(u)) -(F((((+)))
-
(46)
We then use the following lemma [7] Lem. 4].
26

---

Lemma 11. Let SkEK be nonincreasing and nonnegative real sequence. Assume that there exist and B > O such that for all sufficiently large k.
k+1 S 8(s 8k+1).
(47)
Then
(i) ifa 0, the sequence {Sk converges to 0 in a finite number of steps;
(ii) a E (0, 11, the sequence {Su]KeN converges linearly to 0 with rate
(iii) if 1, the sequence {8k converges sublinearly to 0, ie., there exists 0:
S TK
for sufficiently large k.
Compared to 771, Lem. 4], we have dropped the assumption 8t. - 0 in Lem.
because this
assumption is vacuous, i.e., can be induced by (47) and nonnegativity of {sy hee.
We now apply Lem. 11 for 8k = F(ua) F using 466 to derive the followings
(i i F(um) F= converges in a finite number of steps;
(ii) i E (0,1/2), F(um) F converges to 0 linearly (exponentially fast) with rate
(++1)) where M 2 + 1).
M
F(un) - F o M M111
221)
(iii if (1/2,1), F(mm) F converges sublinearly to 0, i.e..
F(um) - F ===0= (0 (-
A.8 Proof of Theorem
Cauchy sequence.
By replacing 1 in 45 and rearranging
L + 1)
3 ( || (x) The (x) Pdee (F(un) - -F (48)
15 follows from Lem.
on
anddd (88) that
1 (x) Thltt (x)] dv S ((F(Hn) - F(un+1))
Vu+1
x
2m 1 + 1)
( |[TH ( (x) T (z) (2))( (F(m))FFF) (F(un) - -Fun+1))
$
(49)
Since the function s: R+ + RR, s(t) 11-0 is concave if 0 E [0, 1), tangent inequality holds s (a) b) s s(a) s(b).
Note that s'(t) = (1 - 0)t-0, the above inequality further implies
(1 - (1- - 8
"") (F(pn) - F(pnt1)) S (F(Hu) - Fry1-0 (
(50)
From 49 and 50
| (x) - Thut (x) (2) < 2( L2 +1)
(f
| (x) - TWi (2)
(1 -0)c
[[((um) - F (F(unt1) - 1-0
27

---

or equivalently,
Ix 1T (x) T 1 (x)xl du n (2)
Fa
v Vn-1
(Jx 1Thh (x) Tha (x) (x)]l=dun(()) (x))
2( 1.f1 +1)
[F(())) - -F:)1-0 (F(mn-1) (51)
-8)c
where vn = fx 11 (a) Teati dv)+i
By telescoping 51 from +00 obtain
+00
In
< 400.
Tn-1
n=1
On the other hand
Vn-1 Tn-1 2
(52)
we derive Ete Vn < +00. From obtain
(23 of the proof of Thm. In 2 (Ken Mn+1), we
toc
W2 (n-1))nn))) < +o0.
n=0
or, in other words, {Ur JeEN is Cauchy sequence under Wasserstein topology. The Wasserstein
space (P2(X), W2) is complete [5] Thm. 2.2]. every Cauchy sequence convergent, i.c., there exists
μ² E P2() such that j4n
Wass
We prove that 1 is actually an optimal solution of F by showing F(u") = Indeed, firstly, as G and H have quadratic growth, it holds
Eα(Un) Ea(u"), (n En(""))
On the other hand,
F lim F(un) lim (()) lim inf H (Mm) + Ea(μ") - EEH(m") n+00
120000
n
2 H (p²) EG(P") (p²) F(μ²)
since H is l.s.c. The equality has to occur, i.e., F F(u²). due the optimality of J Convergence rate of {un
(i) 0 0
From item (i) of Thm. 4 there exists no E N such that F(uz) F for all n 2 no- then follows from 24 that Png Mnot1 Ung+2 which further implies that pnn = 4 for all n 2 no.
(ii) I (0.1
Let 8; = Em VTn We have
Wa(pa,Pot1) 2 W2(us,
(53)
num
where the last inequality uses triangle inequality
N-1
We(ps p²) S
Velpn:sattl W2(PN.
and lets N + oo with notice that JN
From 51 and 52
22 +1)
WT S Vrn-1* +
[((un) - - (F(unt1) - -F
(54)
(1e
28

---

Telescope
54 for = to +00,
2 Li (F(m.) F Vri-i+ (2 + 1)) 1-0 (1 0)n 1 ct
5 S Vr--i
Ti-1
(55)
(1 (1-0)e 0)e
where the last incquality uses (45) Since T3 + 0 as + oe, rs < 1 for i sufficiently large. It follows from (55)
that: for i sufficiently large
8, S M 1
where
M M=14 1+ (2(12 + (1))
(56)
(1 (1-0) 0)1 : cb
M M41 8i-1, we derive W2(ns, 1²) = 0 (( M ))
Rewriting as S
(f 1f0 E 11)
55
implies: for all i sufficiently large,
S Mr 1-1 = M(;s - -;) 1
where M is the same as in (56).
Applying Lem. iiii), s, O i 30 1) which implies (by 53 W2(Hi, = ==(()))))=((( (i
B
Implementation of FB Euler
Following a similar approach to the semi FB Fuler's implementation outlined in Alg. practical implementation of FB Fuler for the sampling context in Alg. 2
| we present
Algorithm 2 FB Euler for sampling
Input: Initial measure po E (X),, discretization stepsize 7) number of steps K >
batch size B.
for k 1 to K do
for i = 1,2.... do
Draw a batch of samples Z po of size B:
o... E - (I F)V o V the o (I F)) V o.. -1
7 + EçE= ( - E|l?:
A. - Eeez log det (o))
E- 1 2n W3 + A.H.
Apply an optimization step (e.g., Adam) over using VoC. end for
0++1 0. end for
C Numerical illustrations
perform numerical experiments a high-performance computing cluster with GPU support. We use Python version 3.8.0. We allocate 8G memory for the experiments. The total running time for all experiments is couple of hours. Our implementation based on the code of 53 (MIT license) with the DenseICNN architecture 41).
29

---

C.1 Gaussian mixture
Consider target Gaussian mixture of the following form:
K
(-1=--
-
I
rzl
<(x & exp(-F(x))) = 4 exp
Σ
0²
We write
K
|| - xz 12
F(x) = - log
Ti cxp
o²
K
||:|| +
|| 1// (xr mia)
- log
exp
σ²
||:||
(- ||::|12 - 2(x,, Uis)
log
Ty exp
exp
0²
|
||2||]
2(x,, xi))
log
my exp
2²
G²
which is DC. Note that the convexity of the second component is thanks to (a) log-sum-exp is convex and (b) the composite of convex function and an affine function convex.
Experiment details We set K 5 and randomly generate I1, 22.... UG E R2 We set 1. The initial distribution μм = (0, 16/). We use 1 = 0.1 for both FB Euler and semi FB Buler. We train both algorithms for 40 iterations using Adam optimizer with a batch size of 512 in which the first 20 iterations use learning rate x 10-3 while latter 20 iterations use 2 x 10-3, For baseline ULA, we run 10000 chains in parallel for 4000 iterations with a learning rate of 10
We run the above experiment 5 times where Tı, Z2....... ..... 2y are randomly generated each time. Fig. (b) reports the KI. divergence along the training process where the mean curves are in bold and individual curves are displayed in a faded style. The final KL divergence (averaged across runs) of the ULA is reported as horizontal line.
C.2 Distance-to-set prior
Let be the original prior, be the constraint set that we want impose, and the distance-to-set prior [61] is defined by, for some > 0,
(0) x (0) exp (-
that penalize exponentially 0 deviating from the constraint set.
Given data y, using the this distance-to-se prior, the posterior reads
(0ly) L(fly) exp (- d(0, d_.(00)))
where L(O)g) is the likelihood.
The structure of (0ly) depends on three separate components: the original prior, the likelihood, and the constraint set θ In the ideal case, x (0) and L(Oly) are given in nice forms (e.g., log-concave), and θ a convex set. As a fact,
is convex set, + d(0, 0)² is convex, making the whole posterior log-concave. If θ is additionally closed, d(0, Y 2 is L-smooth.
nonconvex, the function 0 + d0,,0)² is not continuously differentiable. This is induced by the Motzkin-Bunt theorem [16] Thm. 9.2.5] asserting that any Chebyshev set (a set S C X is called Chebyshev every point X has unique nearest point in S) has to be closed and convex.
However, whenever
30

---

On the other hand, d(e, 6) is always DC regardless the geometric structure of e:
d(0, d)0 inf |10 x
inf (I|@)] + ||=|| - 2(z, 0)) =ee
||011 inf (1|=]1 2/zr, 0))
=ee
|10|] sup (-1|=|| + 2(x,, 8))
(57)
=
Note that the supremum of an arbitary family of affine functions is convex.
Therefore, the log-DC structure of the whole posterior only depends whether the original prior and the likelihood are log-DC, which is likely to be the case.
Distance-to-sel prior relaxed von Mises-Fisher In directional statistics, the von Mises-Fisher distribution is distribution over unit-length vectors (unit sphere). It can described as a restriction of Gaussian distribution in sphere. By using the distance-to prior, relax the spherical constraint as
T()) & exp(-F(0)) == exp (-x (0
(0) 14)
exp (-2 (0, S)²))
2
where S denote the unit sphere in some I2 space. By the DC structure (57 of the distance function, F is DC with the following composition
10 nll2
F(O)=
611013)
sup xES
(-||=]| + +2(x,,0 07)
G(0) H
We also note that H is not continuously differentiable because S is nonconvex. Furthermore, p0) (0) where p0) is the projection onto S, which can be computed explicitly in this case.
Experiment details We consider a unit circle in R2 with centre μ = (1, 1.5). We set x = 1 and 100. The initial distribution is 44 (0, 167). We use n = 0.1 for both FB Euler and semi FB Euler. We train both algorithms for 40 iterations using Adam optimizer with a batch size of 512 in which the first 20 iterations learning rate of x 10-3 while the latter 20 iterations use 2 10-3
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We briefly mention our contribution the abstract (propose a new scheme named semi Forward- Backward Euler and derive multiple convergence insights) and provide a detailed contribution paragraph Sect. T where each claim pointed to the corresponding theorem.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mentioned the expensiveness of the method, especially since the JKO operator not scalable at least for now. See Sect.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
32

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide full set of assumptions used in each theorem/claim, see Sect. 3.2 for the problem setting and Sect. for the convergence theorems. Proofs for all theorems are provided in the Appendix A with strong mathematical rigour.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide a detailed implementation of the proposed method in Sect. and Appendix B and the experiment setting/parameters in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
33

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide our code/results in a GitHub repo mentioned in Sect. 6 We also instruct how to reproduce our experiments README md.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc.
public/guides/Come Stteuueeee/eeeuuiiisssssss www.eesubbissioooococcyy. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. //nips.ccppubtet wwtpccppwwpcpcudeeseessppppppppe http://uudddde/ooouubbbmmiiiaa sondesuumisssioPoll11e
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetalls
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify all the training details in Appendix C initial distribution, target distribution, discretization stepsize, learning rate, minibatch size, optimizer, etc.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report in the Numerical illustration section 6 the eurves in bold and individual run curves shown faintly in the background playing the same role as error bars. We provide sufficient information in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
34

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide resource information in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This is standard machine learning research without any sensitive or human- related data. We do not see any negative impact the society.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdictio).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical research on an optimization problem defined in the Wasser- stein space. We do not see any societal impact that our work may bring about.
35

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., denloymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: the paper poses no such risks. It is a theoretical paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We explicitly mention in Sect. that use the deep learning approach proposed in (53] to compute the JKO. We also acknowledge that we leverage the code from [53] in Section C and in README md in the GitHub repo; the license information is explicitly
mentioned Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
36

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: the detailed description of the algorithms in Sect. 5 We also include LICENSE. txt in the GitHub repo.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
37

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "EXi9SG0Q6z", "reviewer": "Reviewer_7EW7", "summary": "This paper studies minimization algorithms for functionals on the Wasserstein space with the following difference of convex functions (DC) structure:\n$$\n\\min_{\\mu \\in \\mathcal{P}_2(X)} \\mathcal{F}(\\mu) := \\int (G(x) - H(x)) d\\mu(x) + \\mathcal{H}(\\mu),\n$$ where $G$ and $H$ are convex functions and $\\mathcal{H}$ is convex along (generalized) geodesics in the Wasserstein space. The main motivation for this problem is that it is the sampling analog to difference of convex functions problems in optimization, giving a problem of intermediate difficulty between convex and true non-convex. The authors also mention an application to maximum mean discrepancy.\n\nThey study a modified forward Euler sceme which they refer to as \"semi FB Euler\", where given a current iterate $\\mu_n$ they update as\n$$\n\\mu_{n + 1/2} := (I + \\gamma \\nabla H) \\mu_n,\n$$ and then\n$$\n\\mu_{n + 1} := JKO_{\\gamma(H+ E_G)}(\\mu_{n + 1/2}).\n$$ A similar scheme was considered in [1,2] but with the difference that the function $G$ was included in the first step but not in the second; the motivation for this difference is that it more closely aligns with DC programming. One benefit of this modification is that $\\mu_{n + 1/2}$ is pushed forward by an optimal transport map, which makes the problem more tractable. \n\nThe main focus of the work are various convergence results for the above scheme, including an asymptotic result as well as results on the norm of a gradient analog and the distance between $0$ and the sub-differential. The authors also consider convergence under a gradient domination condition, and conclude with some numerics. \n\n[1] Wibisono, Andre. \"Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem.\" Conference on Learning Theory. PMLR, 2018.\n\n[2] Salim, Adil, Anna Korba, and Giulia Luise. \"The Wasserstein proximal gradient algorithm.\" Advances in Neural Information Processing Systems 33 (2020): 12356-12366.", "questions": "- The thorough introduction to Wasserstein space is much appreciated, but perhaps it could be largely moved to an appendix so that more space is left in the main text for more discussion of applications and high-level ideas of the proofs.\n\n- Please give more space to the connection to two-layer neural networks mentioned in the \"Context\" section on page 2.\n\n- Since it is a general fact (see, e.g. [1]) that a gradient domination condition implies that $d(x, x*)^2 <= C(F(x) - F(x*))$, I feel that Theorem 5 should either be removed, or stated as a corollary in an appendix and just mentioned as a brief remark in the main text. \n\n[1] Otto, Felix, and Cédric Villani. \"Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality.\" Journal of Functional Analysis 173.2 (2000): 361-400.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is, to my knowledge, the first to consider the difference of convex functions setting.\n\n- The above bullet leads the authors to propose a modified algorithm compared to previous literature, and means that their convergence results are generally novel.\n\n- The work is rigorous and quite mathematically clear.", "weaknesses": "- The Łojasiewicz condition is not verified to hold in any settings other than their the standard case of KL minimization.\n\n- The problem is somewhat far from practice, firstly because the JKO step is very challenging to implement in practice, and secondly because the setting the authors study is only motivated by one application, to maximum mean discrepancy functionals. They do mention a connection to two-layer neural networks in the \"Context\" section on page 2 but this was impossible to understand from the little they wrote.\n\n- The proofs don't yield explict constants in their results, which is important because there could be hidden dimension-dependence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and positive comments on our work.\n\n**Weaknesses**\n\n***$\\bullet$ \"The Lojasiewicz condition...\"***: We agree that the Lojasiewicz condition is usually used in the case of KL divergence. However, the condition also almost holds for the case of Maximum Mean Discrepancy (MMD) (under mild assumptions). Recall that MMD involves the interaction energy:\n\n\\begin{align*}\n    \\mathcal{F}(\\mu) = \\dfrac{1}{2} D_{\\text{MMD}}(\\mu^*,\\mu)^2:=\\dfrac{1}{2} \\int \\int k(x,y) d\\mu(x) d\\mu(y) + \\int{F(x)} d\\mu(x) + C\n\\end{align*}\nwhere $D_{\\text{MMD}}$ is the MMD distance, $F(x)=-\\int{k(x,y)}d\\mu^*(y)$, $C$ does not depend on $\\mu$ and $k$ is a stationary kernel, i.e., $k(x,y) = W(x-y)$ for some $W$. The Wasserstein gradient of $\\mathcal{F}$ is given by \n\\begin{align*}\n    \\nabla_W \\mathcal{F}(\\mu) = \\nabla F + \\nabla W * \\mu\n\\end{align*}\nwhere * denotes the convolution. Under some regularity conditions of the kernel, it is known that (inequality (62) in [Arbel19] with some notational change)\n\\begin{align*}\n    2(\\mathcal{F}(\\mu)-\\mathcal{F}(\\mu^*)) \\leq \\Vert \\mu^*-\\mu\\Vert_{\\dot{H}^{-1}(\\mu)} \\times \\int{\\Vert \\nabla_W \\mathcal{F}(\\mu) \\Vert^2} d\\mu(x)\n\\end{align*}\nwhere $\\Vert \\mu^*-\\mu\\Vert_{\\dot{H}^{-1}(\\mu)}$ is the weighted negative Sobolev distance. This is almost the Lojasiewicz condition for $\\mathcal{F}$. The only requirement to make it real Lojasiewicz is that $\\Vert \\mu-\\mu^*\\Vert_{\\dot{H}^{-1}(\\mu)}$ is bounded uniformly for all $\\mu$. However, this is tricky. Nevertheless, the point is that we only use the Lojasiewicz condition for the generated sequence {$\\mu_k$}, so all we need is the above quantity to be bounded along that sequence, and this boundedness seems natural and is usually **assumed** (as in [Prop.7, Arbel19]). We will add this discussion in the revised version.\n\n*[Arbel19] Arbel, M., Korba, A., Salim, A., & Gretton, A. (2019). Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems, 32.*\n\n***$\\bullet$ \"JKO step is very challenging\"***: The bottleneck of the JKO computation using [Mokrov21] is the logdet(Hessian), (scales cubically w.r.t. data dimension) and training an NN at each step. If we trade some accuracy for scalability, we can use stochastic log determinant estimators as in [A-Melis22], leading to quadratic complexity. We are also aware of a recent work that replaces the gradient of ICNN by a residual neural network, leading to remarkable speeding [Fan22]. Therefore, we believe the scalability issue of the JKO and hence our proposed method can be resolved shortly. \n\n*[Mokrov21] Mokrov, P., Korotin, A., Li, L., Genevay, A., Solomon, J. M., & Burnaev, E. (2021). Large-scale Wasserstein gradient flows. Advances in Neural Information Processing Systems, 34, 15243-15256.*\n\n*[A-Melis22] Alvarez-Melis, D., Schiff, Y., & Mroueh, Y. (2022). Optimizing functionals on the space of probabilities with input convex neural networks. Transactions on Machine Learning Research.*\n\n*[Fan22] Fan, J., Zhang, Q., Taghvaei, A., & Chen, Y. (2022). Variational Wasserstein gradient flow. ICML.*\n\n***--``only motivated by one application, to maximum mean discrepancy functionals\"***: our work is not only motivated by maximum mean discrepancy but also (and mainly) by sampling from log-DC densities, which existing samplers fail to address. This is a very rich class of (nonconvex) densities and it would be helpful to have another independent survey on DC structures of commonly-used densities.\n\n***--\"connection to two-layer neural networks\"***: The connection between MMD and the problem of infinite-width one hidden layer neural network is briefly mentioned in [Salim20, Appendix B.2]. We can add a pointer to that and can even briefly present it for completeness.\n\n*[Salim20] Salim, A., Korba, A., & Luise, G. (2020). The Wasserstein proximal gradient algorithm. Advances in Neural Information Processing Systems, 33, 12356-12366.*\n\n***$\\bullet$``The proofs don't yield explicit constants\"***: we can discuss the complexity w.r.t. dimensionality (to some extent). However, yielding explicit dimension-constant is very tricky, especially since the ICNN family is only a subfamily of convex functions, and we do not know how close the solution given by ICNN is to the true optimal transport map. So, obtaining the overall complexity that includes the JKO computation is probably impossible in practice.\n\n**Question** \n\n***$\\bullet$ ``The thorough introduction...\"***: Thanks for the suggestion. However, we think it would be beneficial for the readers to have Wasserstein's geometry background in the main text, and we also need all those notions to present our results precisely, so moving them to the appendix is a bit difficult. In the final version with one page extra, we will extend the experiment section, e.g., move the practical scheme in the appendix to the main text.\n\n***$\\bullet$``Please give more space...\"***: as answered above, we can add a pointer to [Salim20, Appendix B.2] or can briefly discuss it for completeness.\n    \n***$\\bullet$ ``Since it is a general fact...\"***: It is known that Log-Sobolev implies Talagrand [Otto00]; consequently, KL divergence controls Wasserstein distance in such a case. We can discuss this connection in our paper. However, Theorem 5 is much more general than that and cannot use the above implication. First, we work with a general regularizer $\\mathscr{H}$, so the objective is not KL divergence. Second, even when $\\mathscr{H}$ is the negative entropy, resulting in KL divergence, we consider the general Lojasiewicz exponent $\\theta \\in [0,1)$. At the same time, the above implication applies only for $\\theta=1/2$ (the case of Log-Sobolev inequality). Therefore, Theorem 5 is not simply a corollary of Theorem 4.\n\n*[Otto00] Otto Felix and Cédric Villani. \"Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality.\" Journal of Functional Analysis 173.2 (2000): 361-400*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4KdshHyNCg", "reviewer": "Reviewer_TQTP", "summary": "This work focuses on the optimization in the Wasserstein space of a functional which is a sum of an internal energy (convex along a generalized geodesic) and of a potential energy, whose potential is a difference of convex functions. To solve such problem, the authors propose to generalize the semi Forward-Backard Euler scheme to the Wasserstein space, and study it theoretically, showing the convergence in general settings. Finally, they demonstrate the convergence of the algorithm on two toy objectives.", "questions": "The focus of the paper is on functionals obtained as a sum of a potential and an internal energy. Could the analysis be done with more general DC functionals (e.g. with interaction energies.). I guess yes since the MMD is presented in the introduction as being such a functional. It would also have been nice to test the semi Forward-Backward scheme on the MMD, as it is not geodesically convex, and does not converge well without tricks such as adding noise (e.g. for Gaussian kernel).\nAssumption 2 supposes that the sublevel sets are compact w.r.t the Wasserstein topology. Are there easy examples of functionals which satisfy this (e.g. those used in the experiment section)?\n\nTypos:\n- In the abstract, I found the sentence line 3 \"When the regularization term is the negative entropy, the optimization problem becomes a sampling problem where it minimizes the Kullback-Leibler divergence between a probability measure (optimization variable) and a target probability measure whose logarithmic probability density is a nonconvex function.\" weird as it is not specified that the objective function is a potential.\n- Line 14: \"can be considered gradient descent\": lack a word?\nRating: 7", "limitations": "The authors have acknowledged the limitations in the main text", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well written and clear. \n- To minimize functionals obtained as difference of convex functionals, it introduces the semi-forward backward Euler scheme, and it shows its convergence under different reasonable assumptions. \n- The theoretical analysis seems rigorous and complete, as it shows the convergence in different settings and under different criteria (e.g. the paper provides a descent lemma, convergence of a subsequence towards a critical point, convergence in gradient, and convergence to the minimum under PL inequality).", "weaknesses": "This is mainly a theoretical work. Thus, the following weaknesses on the experiment section and on the method are minor in my opinion.\n- As underlined in the experiment section, the scheme involves to compute the JKO operator, which is computationally costly as it requires neural networks to solve it\n- The experiments focus on 2D toy examples", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive and positive comments on our work. \n\n**Weaknesses**\n\n***the scheme involves to compute the JKO operator, which is computationally costly..., toy examples***: Please also refer to our reply to reviewer 7EW7. Since we use [Mokrov21] in our JKO step, our work is equally costly. There are some recent works [A-Melis22, Fan22] that propose new strategies to compute the JKO that scale better. \n\n*[Mokrov21] Mokrov, P., Korotin, A., Li, L., Genevay, A., Solomon, J. M., & Burnaev, E. (2021). Large-scale Wasserstein gradient flows. Advances in Neural Information Processing Systems, 34, 15243-15256.*\n\n*[A-Melis22] Alvarez-Melis, D., Schiff, Y., & Mroueh, Y. (2022). Optimizing functionals on the space of probabilities with input convex neural networks. Transactions on Machine Learning Research.*\n\n*[Fan22] Fan, J., Zhang, Q., Taghvaei, A., & Chen, Y. (2022). Variational Wasserstein gradient flow. International Conference on Machine Learning.*\n\n**Question**\n\n***``Could the analysis be done with more general DC functionals\"***: Yes, our framework can handle interaction energies (e.g., MMD) as discussed in the context paragraph and Appendix A.2. Applying semi-FB Euler to MMD as suggested is a good research direction which we can consider in the near future. \n\n***``Assumption 2 supposes that the sublevel sets are compact...\"***: As far as we know, there is no easy check for it when the base space for the Wasserstein space is $\\mathbb{R}^n$. If the base space is instead compact ($X \\subset  \\mathbb{R}^n$, $X$ is compact, the Wasserstein space is the space of all finite 2nd-moment probability distributions whose supports are contained in $X$), the compactness of sublevel sets would be easier to verify since the coercivity of $\\mathcal{F}$ is a sufficient condition. In turn, to check coercivity, one sufficient condition is that the potential grows fast enough at infinity, e.g., if $\\mathscr{H}$ is the entropy, we need $F(x) \\gtrsim c \\Vert x \\Vert^2$. Nevertheless, this is not the case here since we wanted to consider $\\mathbb{R}^n$ but not $X$. \n\nNote, however, that the compactness assumption is only used for Theorem 1. In fact, we only need the compactness of the generated sequence {$\\mu_n$} in the proof. Therefore, in the final version, we will remove Assumption 2 and instead assume that the sequence {$\\mu_n$}  is compact inside Theorem 1. \n\n***Typos***: We will proofread the paper and correct the typos as suggested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XlD6798pE7", "reviewer": "Reviewer_b2tW", "summary": "This work, of a theoretical nature, considers the problem of minimizing a functional $$\\mathcal{F}$$ over the space of probability measures of the form\n\n$$\\mathcal{F}(\\mu) = \\int (G(x) - H(x)) d\\mu(x) + \\mathcal{H}(\\mu)$$\n\nwhere $G,H$ are **convex** potentials and $\\mathcal{H}$ is (typically) the negative entropy (the work actually extends to functionals $\\mathcal{H}$ that are convex along generalized geodesics). \n\nThis setting substantially differs from standard optimization in the space of probability measure in that $\\mathcal{F}$ is not convex along generalized geodesics, the standard assumption to establish convergence of gradient flows in this spaces, following the seminal work of Ambrosio, Gigli and Savaré. Nonetheless, the \"difference of convex functions\" (DC) structure enables the derivation of a two-step scheme to minimize $\\mathcal{F}$. Namely, given a current iterate $\\mu_n$, one first computes $\\nu_{n+1}$ using a **forward** (explicit) Euler scheme _using only the concave term_ $-H$, then obtain $\\mu_{n+1}$ using a **backward** (implicit) iterate on the convex (along generalized geodesics) term $\\mu \\mapsto \\braket{G,\\mu} + \\mathcal{H}(\\mu)$. \n\nThis approach is referred to as a _semi_ forward-backward (FB) Euler scheme, seen as a variation of the known FB scheme (which would process similarly, but performing an explicit iterate on $G-H$ and an implicit iterate on $\\mathcal{H}$). \n\nIn contrast to the standard FB scheme, this semi-FB scheme that leverages the DC structure enables the derivation of strong theoretical guarantees: existence of accumulation points that are critical points of $\\mathcal{F}$, and under additional standard assumptions ($\\sim$ PL inequality), convergence rate toward the global minimum of $\\mathcal{F}$.", "questions": "1. Genuine question: is there any convergence in the regime $\\gamma \\to 0$ toward a limit curve $(\\mu_t)_t$, and if so does it coincides with the usual Wasserstein gradient flow of $\\mathcal{F}$? Said differently, is it true that the (time-continuous) Wasserstein gradient flow of the KL for a log-DC target distribution converges globally? (As a consequence of the fact that the sequence $(\\mu_n)_n$ you build do converge globally in that case)", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The presentation of the work is extremely clear. It is exposed in a pedagogical way, motivations are clear and results are stated formally. \n\nThe authors obtain strong theoretical guarantees in a scope more general than the restricted _convex along generalized geodesics_ one. The DC framework in the context of Wasserstein-based optimization seems to be a promising playground for further research. \n\nThe proposed approach is elegant to me, in that it is simple yet seems very powerful, and seems reasonably usable in practice.", "weaknesses": "1. While I understand that the paper is mostly theoretical, the \"from theory to numeric\" side may be enhanced (typically, putting some of the material of Part B, in particular Algorithm 2, to the main body). \n\n2. Still targeting numerical applications, the approach seems somewhat limited in that the numerical experiments, according to the appendix, have been run on a fairly powerful hardware and yet took a couple of hours to run, while they remain at the proof-of-concept level on toy datasets. \n\n3. Though this does not diminishes the intrinsic quality of the paper, the paper relies on technical proofs deferred to the appendix and I could not proofread all of them. I read the proof of Lemma 1 and Theorem 1, which seem correct to me, and quickly check other proofs but cannot guarantee the correctness of the theorems (though they look sounded)---which are nonetheless the main (if not unique) contributions of the work. I understand that this is not the authors fault, but I wanted to stress that point in my review. \n\n**Minor aspects:**\n- It may be better to use $\\tau$ instead of $\\gamma$ to denote the step-size in JKO schemes, since $\\gamma$ is often used to denote a transport plan. \n- I believe it's better to avoid starting sentences with mathematical symbol. That makes the document a bit easier to read. See for instance line 117 \"continuous w.r.t. $\\mathcal{L}^d$. $\\mu$-a.e. stands...\" is a bit confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive comments on our work.\n\n**Weaknesses**\n\n***[1.]*** We will put some material from Part B (discussion on the ICNN approach for the JKO as well as Algorithm 2) into the main text as suggested when we have some extra space.\n\n***[2.]*** We agree with this limitation. Please see also our reply to reviewer 7EW7. As answered to reviewer 7EW7, there are some recent works [A-Melis22, Fan22] proposing new strategies to compute the JKO that scale better.\n\n*[A-Melis22] Alvarez-Melis, D., Schiff, Y., & Mroueh, Y. (2022). Optimizing functionals on the space of probabilities with input convex neural networks. Transactions on Machine Learning Research.*\n\n*[Fan22] Fan, J., Zhang, Q., Taghvaei, A., & Chen, Y. (2022). Variational Wasserstein gradient flow. International Conference on Machine Learning.*\n    \n***[3.]*** As authors, we also try our best to ensure everything is mathematically correct.\n\n\n***Minor aspect.*** Thanks for the suggestion. We will replace $\\gamma$ with some other symbol and also revise all the sentences carefully.\n\n***Question.*** It is sensible to expect such behaviours of the time-continuous limit of semi-FB-Euler. We think the hypotheses raised by the reviewers are very likely to hold because the semi-FB-Euler is stable and has sufficient regularity. However, we have not really studied that limit and it is not necessarily easy to prove such hypotheses. This could be an interesting future research avenue.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HnxVGfQPq4", "reviewer": "Reviewer_7Mmt", "summary": "This paper introduces and analyzes an optimization scheme, termed \"semi-FB Euler\", for a particular minimization problem over the Wasserstein space $P_2(R^d)$: $\\min_\\mu \\mathcal{F}(\\mu) = \\int (G-H) d\\mu + \\mathcal{H}(\\mu)$, where $G$ and $H$ are convex functions over $R^d$ and $\\mathcal{H}$ is a functional that is convex over generalized geodesics. Namely, \"semi-FB Euler\" is defined by equation (4) of the paper: starting from some $\\mu_0$,\n$$\\begin{cases}\n\\nu\\_{n+1} = (I + \\gamma \\nabla H)\\_{\\sharp} \\mu_n, \\\\\\\\\n\\mu\\_{n+1} \\in \\arg\\min\\_{P\\_2(R^d)} \\int G d\\mu + \\mathcal{H}(\\mu) + \\frac{1}{2\\gamma} W\\_2^2(\\cdot, \\nu\\_{n+1}).\n\\end{cases}$$\n\n(The second step, called a JKO step, is assumed solvable for the theoretical parts of the paper.)\nConvergence to critical points of $\\mathcal{F}$ is established under mild regularity assumptions, both asymptotically (Theorem 1) and with non-asymptotic rates (Theorems 2, 3). Under a Lojasiewicz inequality assumption, convergence to a minimizer is established with non-asymptotic rates (Theorems 4, 5).\n\nNumerical illustrations with synthetic data are provided, in which an input-convex neural network is used to implement the JKO step.", "questions": "- Please address the points in \"Weaknesses\".\n- The items 1.-4. in \"Weaknesses can also be guaranteed if, instead of $-H$ concave, one assumes $H$ is smooth (which is Assumption 5) and $\\gamma$ is small enough (see [56, Thm 5] for item 2 and [56, Lemma 2] for item 4). Could your results be extended to the case where $H$ is smooth instead of convex? If yes, then this could be another way to show theoretical guarantees for forward-backward schemes outside of the convex case (in the spirit of your conclusion, line 393).\n- What are the \"interesting avenues for future work\" mentioned in the conclusion?", "limitations": "The authors adequately addressed the limitations.", "rating": 3, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "This work provides mathematically rigorous grounding for an infinite-dimensional optimization scheme, by working out explicit regularity conditions that ensure well-definedness and asymptotic convergence. The precision and attention to rigor are appreciable. \n\nThe paper is clearly written and well-structured. It also provides an appropriate level of background information on the Wasserstein geometry.\n\nCompared to the closely related work \"The Wasserstein proximal gradient algorithm\" ([56] Salim, Korba, Luise, 2020), numerical experiments using input-convex neural networks (following [44] Morkov et al., 2021) illustrate that the JKO step can indeed be implemented in general, although computational costs are not discussed.", "weaknesses": "The proposed \"semi-FB Euler\" corresponds to a forward-backward splitting scheme of $\\mathcal{F}$ into $\\mathcal{F}_1(\\mu) = \\int (-H) d\\mu$ and $\\mathcal{F}_2(\\mu) = \\int G d\\mu + \\mathcal{H}(\\mu)$ in the Wasserstein optimization geometry. (Incidentally, the name \"semi-FB Euler\" can be misleading, as it is really a forward-backward scheme.)\nSo the setting considered in this paper is very similar to that of \"The Wasserstein proximal gradient algorithm\" ([56] Salim, Korba, Luise, 2020), which corresponds to the case where $H$ is concave and $G=0$. In fact, it seems that the only way that convexity of $G$ comes into play in the proofs, is to ensure convexity of $\\mathcal{F}_2$ over generalized geodesics. (Please do correct me if this is incorrect.)\n\nWith this in mind, the contributions of this paper are to study what happens when $-H$ is concave in $\\mathcal{F}_1(\\mu) = \\int (-H) d\\mu$, as opposed to convex in [56]. It seems that concavity of $-H$ is used for:\n1. the existence of a Borel measurable selector $S$ for the subdifferential $\\partial H$ (section A.1), but it is not essential to the paper;\n2. the descent lemma (Lemma 1);\n3. quadratic growth of $\\|S\\|^2$ under quadratic growth of $H$ (Lemma 4 and proof of Thm 1 line 706);\n4. it seems that convexity of $H$ is implicity used in the very last step of the proof of Thm 1 (line 735). (Incidentally, please make the last step of the proof of Thm 1 more explicit.)\n\nIn summary, compared to the setting of [56], which corresponds to $-H$ being smooth and convex, this work shows that if $-H$ is concave, then the forward-backward algorithm (with a good choice of the selector $S$ when $H$ is non-differentiable) converges for any choice of step-size $\\gamma$.\n\nI find this theoretical contribution interesting, but I am not sure if it is sufficiently significant. Besides, there is also the weakness, acknowledged by the authors (line 362) that the proposed algorithm relies on a JKO step which is computationally expensive. Hence my overall rating for this submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments on our work. We hope the reply below can highlight our contribution.\n\n**Strengths**\n\n***\"Computational cost...\"***: as the answer to reviewer 7EW7, we will discuss the computational cost of the JKO in the revised version.\n\n**Weaknesses**\n\n***``the setting considered in this paper is very similar to\"***: our problem setting is much more general than that of ([56], Salim, Korba, Luise - NeurIPS2020). Having some concavity looks simple yet the whole objective structure becomes much more expressive. The expressivity can be acknowledged from the following result: **any continuous function can be approximated by a sequence of DC functions over a compact, convex domain [Bačák11]**.\n\n*[Bačák11] Bačák, M., & Borwein, J. M. (2011). On difference convexity of locally Lipschitz functions. Optimization, 60(8-9), 961-978.*\n\nBy that, we mean that the structure is semantically simple but powerful mathematically.\n\nSaying that the convexity in [56] is replaced by the concavity in our work does not entirely reflect our framework, hence the contribution. We should look at the whole landscape of the objective function (potential energy + internal/interaction energy), and it would be more complete to say that our work replaces the geodesic convexity in [56] by geodesic difference-of-convexity.\n\nApart from the theoretical contribution mentioned by the reviewer, we think there are two more elegant contributions:\n\n  (1) The use of the DC function for the potential energy already allows us to tackle sampling from log-DC density -- which is a large class of densities (instead of log-concave \"and\" log-smooth density as in ([56] Salim, Korba, Luise, 2020)). \n    \n   (2) The way we separate $\\mathcal{E}_G$ into the JKO part and leave $\\mathcal{E}_H$ for the push-forward is non-trivial and is already a contribution (in our opinion). It differs from the common mindset of applying forward to the potential and backward to the internal energy. Our approach makes both steps tractable, i.e., the optimal map of the forward is computable and the optimal map of the backward is characterizable. Moreover, if we started from [56] with the old mindset and with a mere curiosity of what happens if we replace convex $H$ with concave $-H$, we would not do so in the first place and rather abandon the idea because there are not so many ``log-convex\" distributions out there. \n\nFor these reasons, we also would like to retain the name \"semi-FB Euler\" to address its non-triviality and distinguish it from [56].\n\nIn terms of theory, the use of the concave $-H$ is correctly mentioned by the reviewer. However, we think the existence of $S$ is actually essential because it allows us to work with non-differentiable $H$ (as in Theorem 2). Without this concavity, we have to use more sophisticated subdifferential notions for $H$ like Clarke or Frechet [Clarke90] in the non-differentiability realm. These notions are difficult to work with, and they can be ill-posed (the subdifferential set is empty).\n\n*[Clarke90] Clarke, F. H. (1990). Optimization and nonsmooth analysis. Society for Industrial and Applied Mathematics.*\n\n\n***``Please make the last step of the proof of Thm 1 more explicit\"***: the equation between lines 734 and 735: $\\gamma^{-1}(T_{\\mu_*}^{\\nu_*} - I) \\in \\partial (\\mathcal{E}_G + \\mathscr{H})(\\mu^*)$.  \n\nBy the definition of $\\nu^*$ in line 678, $\\nu^* := (I+\\gamma S)$#$\\mu^*$, and since $S$ is the gradient field of a convex function $H$, that push-forward is optimal, i.e., $T_{\\mu^*}^{\\nu^*} = I + \\gamma S$. Plug this in the above formula, we get $S \\in \\partial(\\mathcal{E}_G + \\mathscr{H})(\\mu^*)$. On the other hand, since $H$ is convex, $S \\in \\partial \\mathcal{E}_H(\\mu^*)$ [4, Proposition 4.13].  We will add these explanations in the revised version.\n\n\nAbout the computational challenge of the JKO, please refer to our answer to reviewer 7EW7.\n\n\n**Questions**\n\n***``Could your results be extended ...\"***: We think our results are totally applicable for $L$-smooth potentials with small $\\gamma$ as suggested. Note that, any $L$-smooth function is a DC function (see our paragraph **Why difference-of-convex structure**).  Therefore, while the suggestion is nice, it does not extend our work any further. The true extension could be that instead of geodesically-concave potential $-\\mathcal{E}_H(\\mu)$, we can consider a more general geodesic concavity not necessarily given in the form of potential energy. \n\n***What are the \"interesting avenues for future work\"***: Those include, for example, the extension mentioned in the previous answer. Moreover, we can also investigate non-geodesically-convex problems in different Wasserstein spaces (either with different base space than $\\mathbb{R}^d$, or different cost functions instead of squared Euclidean distance). For example, in [Section 5, Lambert2022], in the case of mixture of Gaussian Variational Inference, the base space for the Wasserstein space is $BW(\\mathbb{R}^d)$ (Bures–Wasserstein space) instead of $\\mathbb{R}^d$, i.e., we are minimizing over $\\mathcal{P}_2(BW(\\mathbb{R}^d))$ (Wasserstein space over Bures–Wasserstein space). This adds one layer of complexity and, as a consequence, convexity is lost in that space and, quoting from page 9 [Lambert2022], ``we lose many of the theoretical guarantees\". We can extend the discussion when we have one page extra for the final version. \n\n*[Lambert2022] Lambert, M., Chewi, S., Bach, F., Bonnabel, S., & Rigollet, P. (2022). Variational inference via Wasserstein gradient flows. Advances in Neural Information Processing Systems, 35, 14434-14447.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their thoughtful, constructive, and high-quality reviews. We reply to each reviewer in their comment section.

Meta-review: The paper takes a stab at DC optimization in the Wasserstein space and proposes a semi Forward-Backard Euler scheme (section 3, equation 4). All the reviewers like the work especially as it offers a fresh perspective on the problem. Hence, we have decided to accept the work. Please incorporate all the asked changes. 

One reviewer had comments on whether the developments are complete and suggested some explorations. Although it would not be possible to accommodate such detailed explorations in the final version, I would still encourage the authors to provide a short commentary on the future directions / limitations.
Decision: Accept (poster)