← All setups

Wasserstein Accelerated Proximal — Wasserstein Smooth Composite Minimization

Descriptions may be stale. Consult the linked Lean sources.

Wasserstein Smooth Composite Minimization · Lean proof

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.

Proved result

2+3⋅⌈2⋅R⋅Lε⌉+

OracleTemplate.Convergence LongTails.Setups.WassersteinSmoothComposite.spec
  LongTails.Theorems.WassersteinAcceleratedProximal.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.