Optimization in the space of measures : new techniques from optimal transport
Abstract/Contents
- Abstract
- Optimal transport is a profound and elegant tool in probability theory which measures discrepancy between probability distributions. It is a legacy of more than 200 years of mathematical progress and unites disparate areas of science-- stretching from analytic geometry to physics. Because of this, optimal transport has become a primary mechanism for developing and understanding computational methods in robust optimization, machine learning, and artificial intelligence. In this work, we provide novel results which cement this link between optimal transport and data-driven, computational methods. Our first result connects the discrete optimal transport problem with recent developments in theoretical computer science. We exploit this connection to provide novel methods for computing solutions to the discrete optimal transport problem. Moreover, these procedures achieve computational complexities that are close to optimal. Our second result applies the geometry of optimal transport to develop a novel, infinite-dimensional, Frank-Wolfe method for a large class of problems in machine learning and artificial intelligence. Despite operating on an infinite-dimensional level, our procedure is concretely implementable (with finite sample guarantees) and has iteration complexities that mimic convergence rates of finite-dimensional, first-order methods. Using several canonical examples, we also demonstrate that practical implementations of our method possess attractive convergence properties. Finally, our third result develops a strong duality theory for non-parametric model uncertainty problems-- where model uncertainty is specified in terms of optimal transport discrepancy to a set of reference distributions. This duality theory extends a long line of previous results and, most importantly, establishes a computational basis for solving these (infinite-dimensional) problems. Specifically, we establish strong duality with a dual problem that can be solved computationally, using finite-dimensional optimization techniques.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kent, Carson Richard |
|---|---|
| Degree supervisor | Blanchet, Jose H |
| Thesis advisor | Blanchet, Jose H |
| Thesis advisor | Glynn, Peter W |
| Thesis advisor | Ye, Yinyu |
| Degree committee member | Glynn, Peter W |
| Degree committee member | Ye, Yinyu |
| Associated with | Stanford University, Department of Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Carson Richard Kent. |
|---|---|
| Note | Submitted to the Department of Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/fr414tz0559 |
Access conditions
- Copyright
- © 2021 by Carson Richard Kent
Also listed in
Loading usage metrics...