Sample complexity of unbalanced entropic OT

Technische Samenvatting: Steekproefcomplexiteit van Ongebalanceerde Entropische OT

Probleemstelling
Optimale Transport (OT) biedt een geometisch kader voor het vergelijken van waarschijnlijkheidsmaten, maar klassieke gebalanceerde OT kampt met twee belangrijke beperkingen in machine learning-toepassingen: (1) de rigiditeit van harde behoudswetten voor massa, wat ongeschikt is voor data met ontbrekende of gecreëerde massa, en (2) een ongunstige hoge-dimensie steekproefcomplexiteit (de "vloek van dimensionaliteit"), waarbij de empirische convergentiesnelheden verslechteren met de omgevingsdimensie.

Hoewel entropische regularisatie en ongebalanceerde relaxaties (met behulp van $\phi$-divergenties) zijn ontwikkeld om deze problemen afzonderlijk aan te pakken, zijn de bestaande statistische garanties voor ongebalanceerde entropische OT primair beperkt tot de scalaire transportwaarde (de objectieve functie). Er is een gebrek aan statistische garanties met hoge waarschijnlijkheid voor de optimale koppeling (transportplan) zelf. Deze kloof is cruciaal omdat de koppeling in toepassingen zoals generatieve modellering of trajectinferentie het object van belang is voor voorspelling en interpolatie, niet enkel de kostenwaarde.

Methodologie
Het artikel ontwikkelt een statistische analyse van ongebalanceerde entropische OT door zich te richten op de geometrische eigenschappen van het duale probleem. De kern van de methodologische innovatie is de introductie van een translatie-invariante envelop-formulering om het verlies van gauge-invariantie dat inherent is aan ongebalanceerde settings te behandelen.

1. Duale Formulering en Envelopconstructie:
   In tegen tegenstelling tot gebalanceerde OT, waarbij de duale doelfunctie invariant is onder additieve translaties van de Kantorovich-potentialen ($f \to f+\lambda, g \to g-\lambda$), verbreekt ongebalanceerde OT deze symmetrie door marginale divergentiestrafpunten die afhangen van de absolute potentiaalniveaus. De auteurs definiëren een translatie-invariante envelop $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$. Deze constructie scheidt expliciet de intrinsieke vrijheidsgraden van de duale vorm van de spurieuze translatierichting.

2. Geometrische Analyse (Compactheid en Sterke Convexiteit):
   De auteurs bewijzen dat deze envelop-functioneel onder milde aannames (compacte ruimtes, Lipschitz-kosten) een compact verankerd minimalisatiedomein ($P_{\alpha, \beta}^0$) toelaat waar de potentialen worden vastgezet met een gemiddelde van nul ten opzichte van de bronmaat. Cruciaal is dat de envelop op dit domein uniform sterk convex is met betrekking tot een gewogen $L^2$-norm. Hiermee wordt de gunstige geometrische structuur hersteld die verloren gaat in de standaard ongebalanceerde duale vorm.

3. Controle van de Translatieparameter:
   Hoewel de envelop de noodzaak voor willekeurige gauge-fixing wegneemt, introduceert het een optimalisatie over een translatieparameter $\lambda$. Het artikel stelt vast dat onder een milde domeinvoorwaarde op de divergentiegeneratoren (Aanname A2), de optimale $\lambda$ wordt beperkt tot een uniform begrensd interval $[-R, R]$. Dit maakt uniforme $L^\infty$-bounds op de duale potentialen mogelijk.

4. Statistische Stabiliteit:
   Door gebruik te maken van de sterke convexiteit van de verankerde envelop en de begrensdheid van de translatieparameter, leiden de auteurs stabiliteitsschattingen af. Ze tonen aan dat de empirische duale potentialen uniform convergeren naar de populatie-potentialen. Deze duale convergentiesnelheden worden vervolgens overgedragen naar het primaire transportplan via de exponentiële schaleringsrelatie ($d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$).

Belangrijkste Bijdragen

• Translatie-invariante Duale Formulering: Het artikel introduceert een rigoureuze duale formulering die sterke convexiteit voor ongebalanceerde entropische OT herstelt door de translatierichting te quotienteren, een eigenschap die eerder alleen werd gebruikt voor algoritmische stabiliteit in Sinkhorn-iteraties.
• Steekproefcomplexiteit op Planniveau: De primaire bijdrage is de afleiding van hoog-waarschijnlijkheid eindige-steekproefgrenzen voor de optimale koppeling (het transportplan) in de ongebalanceerde setting, in plaats van alleen voor de objectieve waarde.
• Algemene Toepasbaarheid van Divergenties: De resultaten zijn van toepassing op een brede klasse van $\phi$-divergenties (inclusief KL, $\chi^2$, Hellinger, Jensen–Shannon en $\alpha$-divergenties) zonder dat divergentie-specifieke bewijzen nodig zijn, door vertrouwen op algemene convexiteits- en compactheidsargumenten.
• Expliciete Constanten: Het artikel voorziet in expliciete constanten voor de grenzen op de translatieparameter en de resulterende steekproefcomplexiteit, waardoor de afhankelijkheid van de entropieparameter $\eta$, de kostenfunctie en de divergentie-eigenschappen wordt verduidelijkt.

Hoofdresultaten
Het artikel stelt vast dat voor empirische maten $\alpha_n, \beta_n$ afgeleid van $n$ steekproeven, de afwijking tussen het empirische optimale plan $\pi_n$ en het populatieplan $\pi^\star$ een hoog-waarschijnlijkheid grens voldoet van de vorm:
$$|\langle h, \pi^\star - \pi_n \rangle| \lesssim C \cdot e^{C(M + \|c\|_\infty)/\eta} \|h\|_\infty \sqrt{\frac{m_\alpha m_\beta (\log n + t)}{n}}$$
waarbij $M$ een uniforme grens is op de duale potentialen, $h$ een testfunctie is, en de constanten afhangen van de geometrie van het probleem en de divergentieparameters. Opvallend genoeg, als de steekproefverdeling overeenkomt met het product van de marginalen, kan de $\log n$ factor worden verwijderd.

Betekenis en Claims
Het artikel claimt dat deze resultaten de praktische noodzaak van regularisatie in machine learning-toepassingen van OT verhelderen. Specifiek:

• Mitigeren van Dimensionaliteit: Regularisatie verzacht de vloek van dimensionaliteit, waardoor er minder steekproeven nodig zijn voor stabiele transportschattingen.
• Algoritmische Compatibiliteit: De resulterende schatters blijven compatibel met schaalbare Sinkhorn-achtige solvers, waardoor de kloof tussen statistische theorie en computationele praktijk wordt overbrugd.
• Stabiliteit voor Inverse Problemen: De voorwaartse stabiliteitsschattingen die worden geleverd, zijn essentieel voor begeleidende inverse-probleemanalyse (bijv. het terugwinnen van kosten uit steekproeven), zoals vermeld in gerelateerd werk [1].

De auteurs benadrukken dat hun analyse steunt op "zeer milde en grotendeels divergentie-agnostische aannames", wat het theoretische kader robuust en toepasbaar maakt voor de standaardmodellen die in de praktijk worden gebruikt. Zij beweren niet de vloek van dimensionaliteit volledig op te lossen, maar demonstreren hoe entropische ongebalanceerde OT een statistisch hanteerbaar alternatief biedt voor ongeregulariseerde Wasserstein-afstanden in hoog-dimensionale settings.