Geometric methods in computational optimal transport and high-dimensional inference

This dissertation advances the understanding of computational optimal transport and high-dimensional inference through four main contributions, each exploring fundamental connections between geometric structure and algorithmic efficiency. First, a refined analysis of the Sinkhorn algorithm’s convergence properties via the Hilbert projective metric is provided. For probability measures supported on at most n points, it is established that an ε-accurate transport plan can be computed in O(n2log(n)ε−2) operations, maintaining the optimal asymptotic rate while yielding sharper constants than previous analyses. The proof technique, based on careful tracking of the transport polytope’s geometric properties, offers a template for analysing related matrix scaling algorithms. Second, a framework for regularised Wasserstein estimators incorporating new entropic penalties is developed. For measures supported on finite sets, a dual formulation is derived that enables stochastic updates with O(1) complexity per iteration, independent of support size. Under suitable regularity conditions, non-asymptotic convergence bounds of order O(log(T)/T) for appropriately chosen step-sizes are proved. This framework naturally extends to mixture models through additional entropy regularisation on mixing coefficients, as well as to Wasserstein barycenters. Third, the Mirror Sinkhorn algorithm is introduced, unifying mirror descent with matrix scaling in a single loop procedure for optimising convex functions over transport polytopes. For B-Lipschitz objectives, it is shown that the algorithm achieves an O B√δT regret bound, where δ measures the complexity of the marginal constraints. When applied to optimal transport, this leads to a complexity of O(n2log(n)ε−2) while converging to the unregularised solution, giving an advantage over the Sinkhorn algorithm that extends to stochastic settings and multi-marginal transport. For strongly convex objectives, improved rates that depend explicitly on the problem’s geometric parameters are established. Finally, exact recovery in the Binary Spiked Wishart Model is addressed, where Gaussian vectors are observed with a covariance matrix perturbed by an unknown rank-one binary spike. Through careful analysis of a semidefinite programming relaxation, it is proved that exact recovery requires a sample size scaling as Θ(plogp/λ2), where p is the dimension and λ the signal strength. Matching lower bounds are established, thereby precisely characterising the sample complexity threshold. Collectively, these results demonstrate how exploiting problem geometry can lead to both theoretical insights and practical algorithms in high-dimensional inference. The methods developed herein suggest promising directions for future work in distributed optimisation, robust estimation, and structured recovery problems.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2024

Author dc:creator

• Ballu, Marin

Advisors dc:contributor.advisor

• Schönlieb, Carola-Bibiane
• Berthet, Quentin

• Convex Optimisation
• Entropic Regularisation
• High dimensional inference
• Matrix scaling
• Mirror Descent
• Optimal transport
• Semidefinite Programming
• Sinkhorn algorithm
• Stochastic Optimisation
• Wasserstein distance

Licence

• https://www.repository.cam.ac.uk/bitstreams/f280d147-d949-4d89-ae0b-0031cd855340/download
• https://creativecommons.org/licenses/by/4.0/

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.119287

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/385823