{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/385823"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/385823","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Geometric methods in computational optimal transport and high-dimensional inference","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ballu, Marin"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Schönlieb, Carola-Bibiane","Berthet, Quentin"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-04-16","date_published":"2024-04-16","updated_at":"2026-07-22T22:23:53Z","subjects":["Convex Optimisation","Entropic Regularisation","High dimensional inference","Matrix scaling","Mirror Descent","Optimal transport","Semidefinite Programming","Sinkhorn algorithm","Stochastic Optimisation","Wasserstein distance"],"languages":[],"rights":[],"rights_urls":["https://www.repository.cam.ac.uk/bitstreams/f280d147-d949-4d89-ae0b-0031cd855340/download","https://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.119287","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Schönlieb, Carola-Bibiane","Berthet, Quentin"]},{"key":"dc:contributor.sponsor","label":"Sponsor","values":["ESRC"]},{"key":"dc:creator","label":"Author","values":["Ballu, Marin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2024-04-16"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/385823"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Convex Optimisation","Entropic Regularisation","High dimensional inference","Matrix scaling","Mirror Descent","Optimal transport","Semidefinite Programming","Sinkhorn algorithm","Stochastic Optimisation","Wasserstein distance"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["https://www.repository.cam.ac.uk/bitstreams/f280d147-d949-4d89-ae0b-0031cd855340/download","https://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.119287"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://www.repository.cam.ac.uk/bitstreams/729865bf-7886-47db-af46-282e43c38617/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["c909a7345895caf9d2807c9cd88d28b9","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["Geometric methods in computational optimal transport and high-dimensional inference"]}]}],"canonical_facts":{"dc:contributor.advisor":["Schönlieb, Carola-Bibiane","Berthet, Quentin"],"dc:contributor.sponsor":["ESRC"],"dc:creator":["Ballu, Marin"],"dc:date.issued":["2024-04-16"],"dc:description.abstract":["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."],"dc:format.checksum.md5":["c909a7345895caf9d2807c9cd88d28b9","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.119287"],"dc:identifier.uri":["https://www.repository.cam.ac.uk/bitstreams/729865bf-7886-47db-af46-282e43c38617/download"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/385823"],"dc:rights":["https://www.repository.cam.ac.uk/bitstreams/f280d147-d949-4d89-ae0b-0031cd855340/download","https://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Convex Optimisation","Entropic Regularisation","High dimensional inference","Matrix scaling","Mirror Descent","Optimal transport","Semidefinite Programming","Sinkhorn algorithm","Stochastic Optimisation","Wasserstein distance"],"dc:title":["Geometric methods in computational optimal transport and high-dimensional inference"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:23:53Z"}