Optimal Gromov–Wasserstein couplings

The Gromov–Wasserstein distance TauCeti.gromovWassersteinEDist p μ ωX ν ωY is an infimum of distortions over the couplings of μ and ν. This file proves that the infimum is attained when X and Y are Polish and μ and ν are Borel probability measures: some coupling has distortion equal to the distance. The kernels ωX and ωY are only assumed almost-everywhere strongly measurable, with values in an arbitrary pseudo-extended-metric space Z; no continuity, no lower semicontinuity, and no separability or completeness of Z is needed, and every exponent p : ℝ≥0∞ is allowed, including p = ∞. No integrability is assumed either: the optimal value may be ∞.

The proof is the direct method. The couplings form a nonempty weakly compact set (TauCeti.isCompact_setOfPred_isCoupling), so it suffices that the distortion is weakly lower semicontinuous on it (TauCeti.lowerSemicontinuousOn_gromovWassersteinDistortion). The distortion integrates the discrepancy edist (ωX (x, x')) (ωY (y, y')) against the square π ⊗ π, and this integrand is not lower semicontinuous when the kernels are merely measurable. It is continuous, however, on a closed set carrying all but an arbitrarily small part of the mass of π ⊗ π, uniformly in the coupling π: by Lusin's theorem ωX is continuous on a closed set K ⊆ X × X with (μ ⊗ μ) Kᶜ small, ωY on a closed L ⊆ Y × Y with (ν ⊗ ν) Lᶜ small, and the image of π ⊗ π on X × X is μ ⊗ μ and on Y × Y is ν ⊗ ν whatever π is. That uniformity is exactly the hypothesis of TauCeti.lowerSemicontinuousOn_lintegral_comp. For p = ∞ the same argument is applied to the indicator of {edist > c}, whose integral is positive exactly when the essential supremum exceeds c.

Main statements

• TauCeti.lowerSemicontinuousOn_gromovWassersteinDistortion — the distortion is weakly lower semicontinuous on the couplings of two fixed finite measures, on second-countable pseudometrizable carriers;
• TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq — existence of an optimal Gromov–Wasserstein coupling on Polish carriers, the specialization of TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq_of_isTightMeasureSet for tight marginals on second-countable metrizable carriers;
• TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq_of_standardBorelSpace — the same conclusion on standard Borel carriers, through a compatible Polish topology on each;
• TauCeti.exists_isCoupling_gromovWassersteinDistortion_dist_eq — the specialization of the Polish theorem to distance kernels on pseudometric spaces with Polish topologies; the chosen distances need not be complete.

References

• M. Bauer, F. Mémoli, T. Needham and M. Nishino, The Z-Gromov–Wasserstein distance, J. Mach. Learn. Res. 26 (2025), Theorem 26, the existence of optimal couplings for measurable kernels with values in a metric space.
• F. Mémoli, Gromov–Wasserstein distances and the metric approach to object matching, Found. Comput. Math. 11 (2011), where optimal couplings are shown to exist for compact metric-measure spaces.

theorem TauCeti.lowerSemicontinuousOn_gromovWassersteinDistortion {X : Type u_1} {Y : Type u_2} {Z : Type u_3} [TopologicalSpace X] [TopologicalSpace.PseudoMetrizableSpace X] [SecondCountableTopology X] [MeasurableSpace X] [BorelSpace X] [TopologicalSpace Y] [TopologicalSpace.PseudoMetrizableSpace Y] [SecondCountableTopology Y] [MeasurableSpace Y] [BorelSpace Y] [PseudoEMetricSpace Z] {μ : MeasureTheory.Measure X} [MeasureTheory.IsFiniteMeasure μ] {ν : MeasureTheory.Measure Y} [MeasureTheory.IsFiniteMeasure ν] {ωX : X × X → Z} {ωY : Y × Y → Z} (hωX : MeasureTheory.AEStronglyMeasurable ωX (μ.prod μ)) (hωY : MeasureTheory.AEStronglyMeasurable ωY (ν.prod ν)) (p : ENNReal) : LowerSemicontinuousOn (fun (π : MeasureTheory.ProbabilityMeasure (X × Y)) => gromovWassersteinDistortion p ωX ωY ↑π) {π : MeasureTheory.ProbabilityMeasure (X × Y) | IsCoupling (↑π) μ ν}

Lower semicontinuity of the distortion. On second-countable pseudometrizable carriers, the p-distortion of a coupling of two fixed finite measures is weakly lower semicontinuous in the coupling, for almost-everywhere strongly measurable kernels and every exponent p.

theorem TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq_of_isTightMeasureSet {Z : Type u_3} [PseudoEMetricSpace Z] {X : Type u_4} {Y : Type u_5} [TopologicalSpace X] [TopologicalSpace.MetrizableSpace X] [SecondCountableTopology X] [MeasurableSpace X] [BorelSpace X] [TopologicalSpace Y] [TopologicalSpace.MetrizableSpace Y] [SecondCountableTopology Y] [MeasurableSpace Y] [BorelSpace Y] {μ : MeasureTheory.Measure X} [MeasureTheory.IsProbabilityMeasure μ] {ν : MeasureTheory.Measure Y} [MeasureTheory.IsProbabilityMeasure ν] (hμ : MeasureTheory.IsTightMeasureSet {μ}) (hν : MeasureTheory.IsTightMeasureSet {ν}) {ωX : X × X → Z} {ωY : Y × Y → Z} (hωX : MeasureTheory.AEStronglyMeasurable ωX (μ.prod μ)) (hωY : MeasureTheory.AEStronglyMeasurable ωY (ν.prod ν)) (p : ENNReal) : ∃ (π : MeasureTheory.Measure (X × Y)), IsCoupling π μ ν ∧ gromovWassersteinDistortion p ωX ωY π = gromovWassersteinEDist p μ ωX ν ωY

Existence of an optimal Gromov–Wasserstein coupling for tight marginals. For tight Borel probability measures μ and ν on second-countable metrizable spaces and almost-everywhere strongly measurable kernels ωX and ωY with values in any pseudo-extended-metric space, some coupling of μ and ν has distortion equal to the p-Gromov–Wasserstein distance, for every exponent p. The common value may be ∞.

theorem TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq {Z : Type u_3} [PseudoEMetricSpace Z] {X : Type u_4} {Y : Type u_5} [TopologicalSpace X] [PolishSpace X] [MeasurableSpace X] [BorelSpace X] [TopologicalSpace Y] [PolishSpace Y] [MeasurableSpace Y] [BorelSpace Y] (μ : MeasureTheory.Measure X) [MeasureTheory.IsProbabilityMeasure μ] (ν : MeasureTheory.Measure Y) [MeasureTheory.IsProbabilityMeasure ν] {ωX : X × X → Z} {ωY : Y × Y → Z} (hωX : MeasureTheory.AEStronglyMeasurable ωX (μ.prod μ)) (hωY : MeasureTheory.AEStronglyMeasurable ωY (ν.prod ν)) (p : ENNReal) : ∃ (π : MeasureTheory.Measure (X × Y)), IsCoupling π μ ν ∧ gromovWassersteinDistortion p ωX ωY π = gromovWassersteinEDist p μ ωX ν ωY

Existence of an optimal Gromov–Wasserstein coupling. For Borel probability measures μ and ν on Polish spaces and almost-everywhere strongly measurable kernels ωX and ωY with values in any pseudo-extended-metric space, some coupling of μ and ν has distortion equal to the p-Gromov–Wasserstein distance, for every exponent p. The common value may be ∞.

theorem TauCeti.exists_isCoupling_gromovWassersteinDistortion_eq_of_standardBorelSpace {Z : Type u_3} [PseudoEMetricSpace Z] {X : Type u_4} {Y : Type u_5} [MeasurableSpace X] [StandardBorelSpace X] [MeasurableSpace Y] [StandardBorelSpace Y] (μ : MeasureTheory.Measure X) [MeasureTheory.IsProbabilityMeasure μ] (ν : MeasureTheory.Measure Y) [MeasureTheory.IsProbabilityMeasure ν] {ωX : X × X → Z} {ωY : Y × Y → Z} (hωX : MeasureTheory.AEStronglyMeasurable ωX (μ.prod μ)) (hωY : MeasureTheory.AEStronglyMeasurable ωY (ν.prod ν)) (p : ENNReal) : ∃ (π : MeasureTheory.Measure (X × Y)), IsCoupling π μ ν ∧ gromovWassersteinDistortion p ωX ωY π = gromovWassersteinEDist p μ ωX ν ωY

Optimal Gromov–Wasserstein couplings on standard Borel carriers. For probability measures on standard Borel spaces and almost-everywhere strongly measurable kernels with values in any pseudo-extended-metric space, some coupling has distortion equal to the p-Gromov–Wasserstein distance, for every exponent p. The common value may be ∞.

theorem TauCeti.exists_isCoupling_gromovWassersteinDistortion_dist_eq {X : Type u_4} {Y : Type u_5} [PseudoMetricSpace X] [PolishSpace X] [MeasurableSpace X] [BorelSpace X] [PseudoMetricSpace Y] [PolishSpace Y] [MeasurableSpace Y] [BorelSpace Y] (μ : MeasureTheory.Measure X) [MeasureTheory.IsProbabilityMeasure μ] (ν : MeasureTheory.Measure Y) [MeasureTheory.IsProbabilityMeasure ν] (p : ENNReal) : ∃ (π : MeasureTheory.Measure (X × Y)), IsCoupling π μ ν ∧ gromovWassersteinDistortion p (fun (x : X × X) => dist x.1 x.2) (fun (y : Y × Y) => dist y.1 y.2) π = gromovWassersteinEDist p μ (fun (x : X × X) => dist x.1 x.2) ν fun (y : Y × Y) => dist y.1 y.2

Optimal Gromov–Wasserstein couplings for distance kernels. For Borel probability measures on pseudometric spaces with Polish topologies, with the distance functions as kernels, the p-Gromov–Wasserstein distance is attained by some coupling. The chosen distances need not be complete.