Optimal stochastic couplings
Abstract/Contents
- Abstract
- Stochastic coupling is a powerful technique in probability theory that facilitates comparison between two probability distributions. The coupling technique is useful to bound discrepancy between two distributions, design simulation algorithms, and study asymptotic behavior of stochastic processes. In this thesis, we study the applications of stochastic coupling in the context of exact simulation and distributionally robust optimization (DRO). In the first part, we provide the first generic exact simulation algorithm for multivariate diffusions. Current exact sampling algorithms for diffusions require the existence of a transformation which can be used to reduce the sampling problem to the case of a constant diffusion matrix and a drift which is the gradient of some function. Such transformation, called Lamperti transformation, can be applied in general only in one dimension. Therefore, completely different ideas are required for exact sampling of generic multivariate diffusions. Our strategy combines techniques borrowed from the theory of rough paths, on one hand, and multilevel Monte Carlo on the other, in which the random level is coupled with the diffusion process to simulate. The second part of the thesis is dedicated to optimal transport based DRO, where the optimal transport distance is defined as the expected transportation cost under the maximal coupling between two probability measures. The DRO is a systematic modelling approach to mitigate the effect of modelling error and distributional ambiguity in stochastic optimization problems. For optimal transport based DRO, we adopt a minimax framework that minimizes the expectation of random function under the worst distribution in a distributional uncertainty set characterized by optimal transport distance. We propose a methodology which learns the optimal transport cost function in a natural data-driven way. Then, under affine decision rules and conventional convexity assumptions on the underlying loss function, we obtain structural results about the objective value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g. strong convexity even if the non-DRO problem was not strongly convex, a suitable scaling of the Lagrangian for the DRO constraint, etc. which are crucial for the design of efficient algorithms). As a consequence of these results, one can develop efficient optimization procedures which have the same sample and iteration complexity as a natural non-DRO benchmark algorithm such as stochastic gradient descent.
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 | Zhang, Fan |
|---|---|
| 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 Management Science and Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Fan Zhang. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/cb096wz6175 |
Access conditions
- Copyright
- © 2021 by Fan Zhang
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...