Optimization under uncertainty : bounding the correlation gap
Abstract/Contents
- Abstract
- Modern decision models increasingly involve parameters that are unknown or uncertain. Uncertainty is typically modeled by probability distribution over possible realizations of some random parameters. In presence of high dimensional multivariate random variables, estimating the joint probability distributions is difficult, and optimization models are often simplified by assuming that the random variables are independent. Although popular, the effect of this heuristic on the solution quality was little understood. This thesis centers around the following question: "How much can the expected cost increase if the random variables are arbitrarily correlated?" We introduce a new concept of Correlation Gap to quantify this increase. For given marginal distributions, Correlation Gap compares the expected value of a function on the worst case (expectation maximizing) joint distribution to its expected value on the independent (product) distribution. Correlation gap captures the "Price of Correlations" in stochastic optimization -- using a distributionally robust stochastic programming model, we show that a small correlation gap implies that the efficient heuristic of assuming independence is actually robust against any adversarial correlations, while a large correlation gap suggests that it is important to invest more in data collection and learning correlations. Apart from decision making under uncertainty, we show that our upper bounds on correlation gap are also useful for solving many deterministic optimization problems like welfare maximization, k-dimensional matching and transportation problems, for which it captures the performance of randomized algorithmic techniques like independent random selection and independent randomized rounding. Our main technical results include upper and lower bounds on correlation gap based on the properties of the cost function. We demonstrate that monotonicity and submodularity of function implies a small correlation gap. Further, we employ techniques of cross-monotonic cost-sharing schemes from game theory in a novel manner to provide a characterization of non-submodularity functions with small correlation gap. Results include small constant bounds for cost functions resulting from many popular applications such as stochastic facility location, Steiner tree network design, minimum spanning tree, minimum makespan scheduling, single-source rent-or-buy network design etc. Notably, we show that for many interesting functions, correlation gap is bounded irrespective of the dimension of the problem or type of marginal distributions. Additionally, we demonstrate the tightness of our characterization, that is, small correlation gap of a function implies existence of an "approximate" crossmonotonic cost-sharing scheme. This observation could also be useful for enhancing the understanding of such schemes, and may be of independent interest.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Agrawal, Shipra |
|---|---|
| Associated with | Stanford University, Computer Science Department |
| Primary advisor | Roughgarden, Tim |
| Primary advisor | Ye, Yinyu |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Ye, Yinyu |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Saberi, Amin |
| Advisor | Goel, Ashish |
| Advisor | Saberi, Amin |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Shipra Agrawal. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Shipra Agrawal
- 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...