Stability of the Monge Map in Semi-Dual Optimal Transport

Technische Samenvatting: Stabiliteit van de Monge-afbeelding in Semi-Duale Optimale Transport

Probleemstelling
Optimale Transport (OT) is een fundamenteel instrument geworden in het machine learning, dat generatieve modellen zoals GANs, VAEs en diffusiemodellen ondersteunt. Een aanzienlijke klasse van algoritmen, waaronder Neural Optimal Transport (NOT), vertrouwt op de semi-duale formulering van het OT-probleem in combinatie met geamortiseerde optimalisatie. Hoewel deze methoden gebruikmaken van het bestaan en de uniciteit van optimale transportafbeeldingen (Monge-afbeeldingen) onder specifieke voorwaarden, missen ze vaak rigoureuze convergentiegaranties voor de geleerde afbeeldingen. Bestaande literatuur gaat er frequent van uit dat er een optimale afbeelding bestaat en dat het optimalisatieprobleem goed gesteld is, doch deze aannames kunnen in de praktijk falen. Bovendien suggereren empirische waarnemingen dat numerieke algoritmen aanzienlijk meer iteraties vereisen om de transportafbeelding ($t$) bij te werken dan het duale potentiaal ($\psi$), een fenomeen dat eerder ontbeerde aan een theoretische verklaring.

Methodologie en Theoretisch Kader
De auteurs analyseren de semi-duale formulering van het OT-probleem, met name met focus op de zadelpuntstructuur van de objectieve functionaal. De studie veronderstelt dat $X$ en $Y$ compacte deelverzamelingen zijn van $\mathbb{R}^n$ met kansmaten $\mu$ en $\nu$ die absoluut continu zijn ten opzichte van de Lebesgue-maat.

1. Zadelpuntanalyse: Het artikel herformuleert het semi-duale probleem als een minimax-probleem dat een transportafbeelding $t$ en een potentiaal $\psi$ omvat. De objectieve functionaal wordt gedefinieerd als:
   $$F(\psi, t) = \int_X c(x, t(x)) d\mu + \int_Y \psi(y) d(\nu - t_\sharp \mu)$$
   De auteurs demonstreren dat deze formulering een gedegenereerde zadelpuntstructuur bezit. Specifiek wordt bij de optimale transportafbeelding $T^\star$ de waarde van de functionaal $F(\psi, T^\star)$ onafhankelijk van de potentiaal $\psi$. Deze "vlakheid" impliceert dat zodra de transportafbeelding dicht bij optimaal is, de potentiaal $\psi$ niet langer uniek wordt bepaald door de objectieve, zelfs niet als de afbeelding nog niet perfect optimaal is.

2. Convergentievoorwaarden: In tegenstelling tot eerdere werken die vertrouwen op de optimaliteit van de duale potentiaal om convergentie van de afbeelding te bewijzen, leidt dit artikel noodzakelijke en voldoende voorwaarden af voor de convergentie van Monge-afbeeldingen die niet vereisen dat $\psi$ optimaal is. De auteurs stellen een foutgrens vast voor de transportafbeelding $t$ in de $L^2$-norm:
   $$\|t - T^\star\|_{L^2}^2 \lesssim |F(t, \psi) - W_2(\mu, \nu)^2| + d_{KR}(t_\sharp \mu, \nu)$$
   Deze schatting toont aan dat de afstand tot de optimale afbeelding afhangt van de kloof in de objectieve waarde en de Kantorovich-Rubinstein-afstand tussen de push-forward-maat en het doel, in plaats van de nabijheid van $\psi$ tot de optimale potentiaal.

3. Interpretatie als Dynamisch Systeem: Het artikel interpreteert de trainingsdynamiek van NOT-algoritmen als een continu-tijd dynamisch systeem met twee tijdschalen. De analyse onthult dat de constraint $t_\sharp \mu = \nu$ niet wordt voldaan tijdens tussenliggende trainingsstappen, waardoor de maximalisatie over $\psi$ onbegrensd wordt zonder een herstellende kracht. Om het systeem te stabiliseren, moet de prale variabele $t$ evolueren op een snellere tijdschaal dan de duale variabele $\psi$. Dit biedt een theoretische rechtvaardiging voor de empirische praktijk om meerdere gradientdalingstappen uit te voeren op de transportafbeelding voor elke enkele gradiëntopwaartse stap op de potentiaal.

Belangrijkste Bijdragen en Resultaten

• Identificatie van Degeneratie: Het artikel identificeert expliciet de gedegenereerde zadelpuntstructuur in de semi-duale OT-formulering, waarbij de objectieve onafhankelijk wordt van de potentiaal bij de optimale afbeelding. Dit verklaart waarom de potentiaal kan divergeren of kan falen om te convergeren, zelfs terwijl de transportafbeelding convergeert.
• Convergentieschatting Onafhankelijk van Potentiaal: De auteurs leveren een convergentieschatting (Vergelijking 17) die de fout van de transportafbeelding begrenst zonder de optimaliteit van de duale potentiaal aan te nemen. Dit daagt eerdere aannames in de literatuur uit die convergentie van de afbeelding direct koppelen aan convergentie van de potentiaal.
• Verklaring van Twee-Tijdschaal Updates: Het artikel valideert theoretisch de "twee-tijdschaal" update-regel die wordt gebruikt in NOT en gerelateerde WGAN-formuleringen. Het toont aan dat het bijwerken van de afbeelding $t$ meerdere keren per potentiaal-update ($K \eta_t / \eta_\psi$) noodzakelijk is om het systeem te stabiliseren en constraint-overtredingen te verminderen voordat de potentiaal wordt bijgewerkt.
• Experimentele Validatie: Numerieke experimenten op Gaussische verdelingen bevestigen dat de transportafbeelding kan convergeren naar de optimale oplossing terwijl de potentiaal ver weg blijft van optimaal. De resultaten tonen aan dat de verhouding van update-stappen ($K$) en leersnelheden ($\eta_t/\eta_\psi$) kritiek beïnvloedt of de afbeelding of de potentiaal nauwkeuriger wordt geleerd.

Betekenis en Claims
Het artikel claimt een theoretische verklaring te bieden voor het praktische gedrag van neurale optimale transport-algoritmen, specifiek waarom ze vaak meer iteraties vereisen voor de afbeelding dan voor de potentiaal. Door het semi-duale probleem te karakteriseren als een geconstrueerd optimalisatietaken met een gedegenereerd zadelpunt, verduidelijken de auteurs waarom standaard convergentiegaranties gebaseerd op potentiaaloptimaliteit ontoereikend zijn.

De auteurs benadrukken dat het bestaan van een infimum in het semi-duale probleem geen garantie biedt voor het bestaan van een minimizer voor de potentiaal, een onderscheid dat heeft geleid tot onjuiste claims in eerdere literatuur. Zij betogen dat "spurious oplossingen" en gradiëntafwijkingen die in de praktijk worden waargenomen, voortkomen uit deze degeneratie, waarbij verschillende potentialen verschillende gradiënten opleveren nabij de optimale afbeelding. Derhalve suggereert het artikel dat het opleggen van structurele constraints (zoals convexiteit) aan de potentiaal de degeneratie kan verminderen, maar een benaderingsbias introduceert, terwijl onbeperkte parametriseringen beter kunnen presteren ondanks het ontbreken van strikte zadelpunt-eigenschappen.

Het werk concludeert dat de stabiliteit van de Monge-afbeelding in semi-duale OT afhankelijk is van de relatieve tijdschalen van de afbeelding- en potentiaal-updates, en dat convergentie van de afbeelding niet impliceert convergentie van de potentiaal.