Novel Algorithms for Optimal Transport via Splitting Methods

QC 20231123

Abstract

Denna avhandling behandlar hur Douglas–Rachford-splittning kan tillämpas för skalbara beräkningar av optimal transport (OT). Genom en noggrann splittning av problemet härleder vi en algoritm med flera fördelar. För det första åtnjuter algoritmen en global konvergenshastighet som är jämförbara med populära OT-lösare, samtidigt som den drar nytta av accelererade lokalahastigheter. Till skillnad från andra metoder är den inte beroende av hyperparametrar som kan orsaka numerisk instabilitet. Den här egenskapen är särskilt fördelaktig när lågprecisionsaritmetik används eller när data innehåller mycket brus. Uppdateringarna som algoritmen baseras på kan effektivt utföras på GPU:er och dra nytta av dess parallellberäkningar. Vi visar också att algoritmen kan utökas för att hantera en rad regulariseriseringar och bivillkor samtidigt som den åtnjuter liknande teoretiska och numeriska egenskaper. Tillsammans resulterar dessa faktorer i en snabb algoritm som kan tillämpas på storskaliga OT-problem samt flera av dess regulariserade varianter, vilket vi visar i flera numeriska experiment.

I den första delen av avhandlingen presenterar vi hur Douglas-Rachford-splittning kan anpassas för det oregulariserade OT-problemet för att härleda en snabb algoritm. För den resulterande algoritmen presenterar vi två globala konvergensgarantier: en 1/k-ergodisk och en linjär konvergenshastighet. Vi presenterar också hur stoppkriterierna för algoritmen kan beräknas utan vidare extra kostnader. Dessutom specificerar vi hur en GPU-kärna kan implementeras för att effektivt utföra de operationer som algoritmen baseras på. För att visa att algoritmen är snabb, exakt och robust utför vi ett flertal numeriska experiment som påvisar flera fördelar över jämförbara algoritmer. Därefter utökar vi algoritmen för att hantera regulariserad OT med s.k. sparsity-promoting regularizers. Den generaliserade algoritmen åtnjuter samma sublinjära konvergenshastighet som härleddes för den oregulariserade fallet. Vi kompletterar också garantierna genom att tillhandahålla lokala garantier genom att fastställa att givet svaga antaganden om lösningen kommer algoritmen att identifiera den korrekta lösningens gleshetsstuktur inom ett begränsat antal iterationer. När glesheten identifierats dominerar typiskt sett en snabbare linjär konvergenshastighet. Vi specificerar också hur man utökar till GPU-kärnan och resultaten av stoppkriterierna för att hantera regulariserad OT, och vi specificerar sedan hur man differentiera genom lösaren. Vi avslutar den här delen av avhandlingen genom att presentera några numeriska resultat för kvadratiskt reglerad OT och group Lasso-reglerad OT för domänanpassning, vilket visar en betydande förbättring jämfört med de mest populära metoderna för dessa tillämpningar.

I den sista delen av avhandlingen ger vi en mer detaljerad analys av algoritmens lokala beteende när den tillämpas på oregulerisad OT och kvadratiskt reglerad OT. Vi föreslår även sätt att studera flera andra fallet. I de två första fallen visar vi att uppdateringen som utgör algoritmen konvergerar till en linjär operator inom ett begränsat antal iterationer. Genom att analysera de spektrala egenskaperna hos dessa linjära operatorer får vi ytterligare insikter i algoritmens lokala beteende, och specifikt indikerar dessa resultat hur man kan justera steglängden för att uppnå ännu bättre konvergenshastigheter.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-339965