← All setups

Wasserstein Smooth Composite Minimization

Descriptions may be stale. Consult the linked Lean sources.

Wasserstein Smooth Composite Minimization

We minimize F(μ)=∫Vdμ+H(μ) over a set Q of absolutely continuous probability measures on Rd with finite second moments, where d≥0 is an integer. The potential V:Rd→R is convex with L-Lipschitz gradient, L>0, and H is convex along generalized Wasserstein geodesics in Q. A given μ0∈Q is within Wasserstein distance R≥0 of a minimizer μ⋆∈Q. The oracle returns gradient pushforwards, proximal minimizers of H, and optimal transport maps. For ε>0, the goal is μ¯∈Q with F(μ¯)−F(μ⋆)≤ε, almost surely under the joint law of algorithm and oracle randomness.

Write P2(Rd) for the Borel probability measures with finite second moments, and use the Euclidean norm on Rd. For μ,ν∈P2(Rd), let Π(μ,ν) be their probability couplings and define W22(μ,ν)=infπ∈Π(μ,ν)∫∥x−y∥2dπ(x,y). All these coupling costs are finite. For a measurable map T, the notation T#μ denotes its pushforward. The objective and optimization problem are F(μ)=∫RdV(x)dμ(x)+H(μ),minμ∈QF(μ), where H:P2(Rd)→R. The algorithm receives d,L,R,ε, and μ0; the functions V,H, the set Q, and the minimizer are accessed only through the specified oracle.

Our assumptions:

Assumption 1 (Convex smooth potential). The function V is differentiable everywhere, and for all x,y∈Rd and t∈[0,1], V((1−t)x+ty)≤(1−t)V(x)+tV(y),∥∇V(x)−∇V(y)∥≤L∥x−y∥.

Assumption 2 (Generalized geodesic convexity). Every μ∈Q is absolutely continuous with respect to Lebesgue measure. For every base measure β∈P2(Rd) and every μ,ν∈Q, there exists a probability measure γ on (Rd)3, with respective marginals β,μ,ν, such that ∫∥z−x∥2dγ(z,x,y)=W22(β,μ),∫∥z−y∥2dγ(z,x,y)=W22(β,ν). For this same γ, every t∈[0,1] gives a measure ρt=((z,x,y)↦(1−t)x+ty)#γ that satisfies ρt∈Q,H(ρt)≤(1−t)H(μ)+tH(ν).

Assumption 3 (Minimizer and initial distance). The given initial measure and a minimizer satisfy μ0,μ⋆∈Q and F(μ⋆)≤F(μ)for every μ∈Q,W22(μ0,μ⋆)≤R2.

The oracle supports three kinds of queries. A forward query at any h∈R and μ∈P2(Rd) returns the distribution b=(x↦x−h∇V(x))#μ. A proximal query at h>0 and b∈P2(Rd) returns u∈Q satisfying 2hH(u)+W22(b,u)≤2hH(ρ)+W22(b,ρ),ρ∈Q. There is no correctness requirement for proximal queries with h≤0.

A transport query at μ∈Q and any ν∈P2(Rd) returns a measurable map T:Rd→Rd such that T#μ=ν, the function x↦∥x−T(x)∥2 is integrable under μ, and ∫∥x−T(x)∥2dμ(x)≤∫∥x−y∥2dπ(x,y),π∈Π(μ,ν). There is no correctness requirement for transport queries whose first argument lies outside Q. Each query of any of the three kinds counts toward a single oracle-call budget. These reply conditions hold for every query history and every realization of oracle randomness; different valid proximal minimizers or transport maps may be returned.

After the allotted calls, the output distribution must satisfy μ¯∈Q,F(μ¯)−F(μ⋆)≤εP-a.s., where P is the joint law of the algorithm’s randomness and the oracle’s randomness, which are independent.

Results

Minimize G(μ)=∫Vdμ+H(μ) over Q⊂P2(Rd) consisting of absolutely continuous measures. The potential V is convex with L-Lipschitz gradient, L>0; Q,H are convex along generalized geodesics at every base. A minimizer μ⋆∈Q exists, μ0∈Q, and W2(μ0,μ⋆)≤R. Exact forward pushforward, constrained JKO steps of H, and optimal transport maps are supplied. Target: feasible output μ with G(μ)−G(μ⋆)≤ε, ε>0, almost surely (the constructed result holds for every seed).

Comparison for WassersteinSmoothComposite.
Result Oracle complexity Novelty Limitations
(1) WassersteinAcceleratedProximal (Ours) (⋆⋆) (review) O(1+RL/ε) total forward, JKO(H), and OT-map calls.
(2) Proximal gradient (Salim et al. 2021), Cor. 10 O(1+LR2/ε) total forward and JKO(H) calls; γ=Θ(1/L)<1/L in the proximal-existence range; lower semicontinuous H+ιQ. (1): Rate improves from O(1+T) to O(1+T); unit-cost savings for large T (reported crossover T≳36). Lower semicontinuity replaced by supplied minimizers. (1) adds an exact OT-map solve per iteration.
(3) Wasserstein FISTA (Ushiyama et al. 2026), Thm. 8 (m=0) O(1+RL/ε) total lifted-gradient and fixed-reference cone-prox calls; lower semicontinuous regularizer and closed convex lifted feasible set. (1) matches the accelerated order on the common potential-energy setup, via a new ordinary-JKO forward–backward analysis. JKO plus inter-iterate OT replaces cone prox; no oracle ordering established. (1) covers potential energies only; requires generalized-geodesic convexity at every base rather than one fixed reference; worse leading constant.
(4) Accelerated JKO (Chang et al., n.d.), Thm. 8 O(1+R/γε) whole-G JKO and OT-map calls; arbitrary γ>0; lower semicontinuous, generalized-geodesically convex G with absolutely continuous domain. (1) uses split forward and JKO(H) operations instead of whole-G proximal access. Costs are not comparable: (4) allows arbitrarily large γ.

Abbr: P2: probability measures with finite second moment; W2: quadratic Wasserstein distance; R≥0: initial-distance bound; T=LR2/ε; OT: optimal transport; JKO(H): exact minimization of H(ρ)+W22(b,ρ)/(2h) over ρ∈Q; ιQ: indicator of Q; cone prox: proximal operation over optimal maps from a fixed measure in L2; γ: prior method’s proximal step. Each oracle operation counts as one call.

Chang, William, Taro Iyadomi, and Tianyu Wang. n.d. Accelerated Proximal Optimization in Wasserstein and Sobolev Spaces. Author preprint. https://taroiyadomi.netlify.app/pdfs/Accelerated_Proximal_Optimization_in_Wasserstein_and_Sobolev_Spaces.pdf.
Salim, Adil, Anna Korba, and Giulia Luise. 2021. The Wasserstein Proximal Gradient Algorithm. https://doi.org/10.48550/arXiv.2002.03035.
Ushiyama, Kansei, Yi Feng, Kaito Fujii, Yuma Fujimoto, and Noboru Isobe. 2026. Wasserstein Accelerated Proximal Gradient Algorithms. https://arxiv.org/abs/2611.03524v1.

Lean setup