Computational Optimal Transport via Operator Splitting — Analysis, Implementation, and Applications

QC 20250918

Abstract

This thesis develops scalable and theoretically grounded algorithms for optimal transport (OT) using operator splitting. The central theme is to exploit the structural properties of OT and the constraints imposed by modern hardware to derive algorithms that mitigate key implementation bottlenecks in large-scale applications. The thesis is based on four main works. 

First, the Douglas–Rachford splitting method is applied to unregularized OT. Through careful splitting design, we obtain an algorithm that combines favorable global convergence rates while being well-suited for GPU computations. Moreover, the approach avoids hyperparameters that often cause numerical instability in other OT methods, and is particularly well-suited for low-precision arithmetic, now ubiquitous in machine learning applications. The theoretical guarantees are complemented by numerical benchmarks, demonstrating that the algorithm is faster than the state-of-the-art on a range of problem instances. 

Second, we extend this framework to handle a broad class of regularizers, including group lasso and quadratic regularization. The algorithm derived in the first work is readily adapted to this class, and we show that the analysis and the GPU implementation generalize to this setting. Additional tight local convergence guarantees are also added. Numerical experiments confirm the efficiency of the algorithm, achieving 10–100x faster computation times than the state-of-the-art for a wide range of problem instances. 

Third, we introduce an asynchronous three-operator splitting scheme for trans- portation problems with nonlinear but differentiable costs, with the Gromov–Wasserstein problem as a special case. This algorithm removes synchronization bottlenecks by reusing gradients—a feature particularly useful when gradient evaluations dominate overall complexity. Its analysis extends classical operator-splitting theory to asynchronous settings in a novel manner, and these results are complemented by guarantees for the non-convex case. Applying the resulting algorithm to several real-world problems demonstrates that the method is highly efficient while yielding accurate solutions. 

Finally, we develop additional local convergence guarantees that account for the sparsity structure of OT solutions. Under mild assumptions, the algorithm identifies the correct sparsity pattern in finitely many iterations, after which faster linear convergence dominates. Moreover, we relate the local rate to graph-theoretical properties of the solution. This analysis not only refines the theoretical understanding of splitting methods for OT but also suggests principled strategies for stepsize tuning. 

Taken together, these contributions advance the theoretical understanding of splitting methods for optimal transport, while improving their practical usability, enabling their application to a variety of OT problems at greater scales. 

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