2026-09-21T13:26:53Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/3858232025-12-20T02:17:06Zcom_1810_213747com_1810_256064col_1810_213748

Geometric methods in computational optimal transport and high-dimensional inference https://doi.org/10.17863/CAM.119287 Ballu, Marin Schönlieb, Carola-Bibiane Berthet, Quentin 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. University of Cambridge 2024-04-16 Thesis Doctoral Doctor of Philosophy (PhD) ESRC https://www.repository.cam.ac.uk/handle/1810/385823 https://www.repository.cam.ac.uk/bitstreams/729865bf-7886-47db-af46-282e43c38617/download c909a7345895caf9d2807c9cd88d28b9 https://www.repository.cam.ac.uk/bitstreams/f280d147-d949-4d89-ae0b-0031cd855340/download 87eda9de84448d1f82354d60eee3eb5f https://creativecommons.org/licenses/by/4.0/ Convex Optimisation Entropic Regularisation High dimensional inference Matrix scaling Mirror Descent Optimal transport Semidefinite Programming Sinkhorn algorithm Stochastic Optimisation Wasserstein distance