The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Distributionally Robust Stochastic Optimization with Wasserstein Distance
Open accessAbstract
Distributionally robust stochastic optimization (DRSO) is an approach to optimization under uncertainty in which, instead of assuming that there is a known true underlying probability distribution, one hedges against a chosen set of distributions. In this paper, we first point out that the set of distributions should be chosen to be appropriate for the application at hand and some of the choices that have been popular until recently are, for many applications, not good choices. We next consider sets of distributions that are within a chosen Wasserstein distance from a nominal distribution. Such a choice of sets has two advantages: (1) The resulting distributions hedged against are more reasonable than those resulting from other popular choices of sets. (2) The problem of determining the worst-case expectation over the resulting set of distributions has desirable tractability properties. We derive a strong duality reformulation of the corresponding DRSO problem and construct approximate worst-case distributions (or an exact worst-case distribution if it exists) explicitly via the first-order optimality conditions of the dual problem. Our contributions are fourfold. (i) We identify necessary and sufficient conditions for the existence of a worst-case distribution, which are naturally related to the growth rate of the objective function. (ii) We show that the worst-case distributions resulting from an appropriate Wasserstein distance have a concise structure and a clear interpretation. (iii) Using this structure, we show that data-driven DRSO problems can be approximated to any accuracy by robust optimization problems, and thereby many DRSO problems become tractable by using tools from robust optimization. (iv) Our strong duality result holds in a very general setting. As examples, we show that it can be applied to infinite dimensional process control and intensity estimation for point processes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
The Earth Mover's Distance as a Metric for Image Retrieval
Rubner, Y., Tomasi, C., & Guibas, L. J. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026543900054 · Cited by 4,568
Topics in Optimal Transportation
Villani, C. (2003) · Graduate Studies in Mathematics · doi:10.1090/gsm/058 · Cited by 4,412
Functions of Bounded Variation and Free Discontinuity Problems
Ambrosio, L., Fusco, N., & Pallara, D. (2000) · doi:10.1093/oso/9780198502456.001.0001 · Cited by 4,318
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
An Introduction to the Theory of Point Processes
Daley, D. J., & Vere-Jones, D. (2008) · Probability and Its Applications · doi:10.1007/978-0-387-49835-5 · Cited by 3,351
(2008) · doi:10.1007/978-3-7643-8722-8 · Cited by 2,220
Delage, E., & Ye, Y. (2010) · Operations Research · doi:10.1287/opre.1090.0741 · Cited by 1,893
Adjustable robust solutions of uncertain linear programs
Ben-Tal, A., Goryashko, A., Guslitzer, E., & Nemirovski, A. (2004) · Mathematical Programming · doi:10.1007/s10107-003-0454-y · Cited by 1,380
On Choosing and Bounding Probability Metrics
Gibbs, A. L., & Su, F. E. (2002) · International Statistical Review · doi:10.1111/j.1751-5823.2002.tb00178.x · Cited by 1,163
Mathematical Methods of Organizing and Planning Production
Kantorovich, L. V. (1960) · Management Science · doi:10.1287/mnsc.6.4.366 · Cited by 1,082
The shortest path through many points
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034095 · Cited by 937
Digital Image Processing 3rd Edition
González, R. C., & Woods, R. E. (2014) · Cited by 924
Adjustable robust solutions of uncertain linear programs
Ben-TalA., GoryashkoA., GuslitzerE., et al. (2004) · Mathematical Programming · doi:10.5555/2990016.3114320 · Cited by 849
Nemirovski, A. (2004) · SIAM Journal on Optimization · doi:10.1137/s1052623403425629 · Cited by 750
Robust Solutions of Optimization Problems Affected by Uncertain Probabilities
Ben-Tal, A., den Hertog, D., De Waegenaere, A., Melenberg, B., & Rennen, G. (2013) · Management Science · doi:10.1287/mnsc.1120.1641 · Cited by 748
On the Translocation of Masses
Kantorovich, L. V. (2006) · Journal of Mathematical Sciences · doi:10.1007/s10958-006-0049-2 · Cited by 744
Distributionally robust joint chance constraints with second-order moment information
Zymler, S., Kühn, D., & Rüstem, B. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0494-7 · Cited by 710
An Introduction to the Theory of Point Processes : Volume I: Elementary Theory and Methods
Daley, D. J., & Vere‐Jones, D. (2003) · Cited by 701
Distributionally Robust Optimization and Its Tractable Approximations
Goh, J., & Sim, M. (2010) · Operations Research · doi:10.1287/opre.1090.0795 · Cited by 668
Hwang, F. K., & Richards, D. S. (1992) · Networks · doi:10.1002/net.3230220105 · Cited by 663
Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach
Ghaoui, L. E., Oks, M., & Oustry, F. (2003) · Operations Research · doi:10.1287/opre.51.4.543.16101 · Cited by 662
Blackledge, J. M. (2005) · Woodhead Publishing Limited eBooks · doi:10.1533/9780857099464 · Cited by 639
Lectures on Stochastic Programming: Modeling and Theory, Second Edition
Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2014) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611973433 · Cited by 575
A Min-Max Solution of an Inventory Problem
Scarf, H. (2005) · Herbert Scarf’s Contributions to Economics, Game Theory and Operations Research · doi:10.1057/9781137024381_3 · Cited by 552
On Distributionally Robust Chance-Constrained Linear Programs
Calafiore, G. C., & Ghaoui, L. E. (2006) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-006-9084-x · Cited by 508
Data-driven chance constrained stochastic program
Jiang, R., & Guan, Y. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0929-7 · Cited by 485
Calculation of the Wasserstein Distance Between Probability Distributions on the Line
Vallender, S. S. (1974) · Theory of Probability & Its Applications · doi:10.1137/1118101 · Cited by 483
An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison
Ling, H., & Okada, K. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1058 · Cited by 414
Bounds and Heuristics for Capacitated Routing Problems
Haimovich, M., & Kan, A. H. G. R. (1985) · Mathematics of Operations Research · doi:10.1287/moor.10.4.527 · Cited by 363
Quantifying Distributional Model Risk via Optimal Transport
Blanchet, J., & Murthy, K. (2019) · Mathematics of Operations Research · doi:10.1287/moor.2018.0936 · Cited by 350
On Duality Theory of Conic Linear Problems
Shapiro, A. (2001) · Nonconvex optimization and its applications · doi:10.1007/978-1-4757-3403-4_7 · Cited by 312
Ambiguous chance constrained problems and robust optimization
Erdoğan, E., & Iyengar, G. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0678-0 · Cited by 302
Multistage Stochastic Optimization
Pflug, G. C., & Pichler, A. (2014) · Springer series in operations research/Springer series in operations research and financial engineering · doi:10.1007/978-3-319-08843-3 · Cited by 258
The Data-Driven Newsvendor Problem: New Bounds and Insights
Levi, R., Perakis, G., & Uichanco, J. (2015) · Operations Research · doi:10.1287/opre.2015.1422 · Cited by 256
Robust Wasserstein profile inference and applications to machine learning
Blanchet, J., Kang, Y., & Murthy, K. (2019) · Journal of Applied Probability · doi:10.1017/jpr.2019.49 · Cited by 250
Quantitative Concentration Inequalities for Empirical Measures on Non-compact Spaces
Bolley, F., Guillin, A., & Villani, C. (2007) · Probability Theory and Related Fields · doi:10.1007/s00440-006-0004-7 · Cited by 248
Robust Mean-Covariance Solutions for Stochastic Optimization
Popescu, I. (2007) · Operations Research · doi:10.1287/opre.1060.0353 · Cited by 235
An optimal randomized incremental gradient method
Lan, G., & Zhou, Y. (2017) · Mathematical Programming · doi:10.1007/s10107-017-1173-0 · Cited by 178
On minimax solutions of stochastic linear programming problems
Žáčková, J. (1966) · Časopis pro pěstování matematiky · doi:10.21136/cpm.1966.117583 · Cited by 158
The minimax approach to stochastic programming and an illustrative application
Dupačová, J. (1987) · Stochastics · doi:10.1080/17442508708833436 · Cited by 154
Mohajerin Esfahani, P., & Kuhn, D. (2018) · Mathematical Programming · doi:10.1007/s10107-017-1172-1 · Cited by 136
A framework for optimization under ambiguity
Wozabal, D. (2010) · Annals of Operations Research · doi:10.1007/s10479-010-0812-0 · Cited by 112
Convergence Analysis for Distributionally Robust Optimization and Equilibrium Problems
Sun, H., & Xu, H. (2015) · Mathematics of Operations Research · doi:10.1287/moor.2015.0732 · Cited by 108
Robustifying Convex Risk Measures for Linear Portfolios: A Nonparametric Approach
Wozabal, D. (2014) · Operations Research · doi:10.1287/opre.2014.1323 · Cited by 72
On first-order algorithms forl1/nuclear norm minimization
Nesterov, Y. E., & Nemirovski, A. S. (2013) · Acta Numerica · doi:10.1017/s096249291300007x · Cited by 58
UNCERTAINTY- IMMUNIZED SOLUTIONS IN LINEAR PROGRAMMING
Guslitser, E. (2002) · Cited by 49
Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
Minoux, M. (2011) · Optimization Letters · doi:10.1007/s11590-011-0341-z · Cited by 12
Cited by
Adversarial Attacks and Defenses in Deep Learning
Ren, K., Zheng, T., Qin, Z., & Liu, X. (2020) · Engineering · doi:10.1016/j.eng.2019.12.012 · Cited by 678
Frameworks and Results in Distributionally Robust Optimization
Rahimian, H., & Mehrotra, S. (2022) · Open Journal of Mathematical Optimization · doi:10.5802/ojmo.15 · Cited by 506
Quantifying Distributional Model Risk via Optimal Transport
Blanchet, J., & Murthy, K. (2019) · Mathematics of Operations Research · doi:10.1287/moor.2018.0936 · Cited by 350
Ning, C., & You, F. (2019) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.03.034 · Cited by 343
Certifying Some Distributional Robustness with Principled Adversarial Training
Sinha, A., Namkoong, H., Volpi, R., & Duchi, J. C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.10571 · Cited by 307
Metadata
- Authors
- Gao, R., & Kleywegt, A.
- Venue
- Mathematics of Operations Research
- Published
- 2023-05
- Volume
- 48
- Issue
- 2
- Pages
- 603-655
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2336156739
- Cited by
- 630
- References
- 48
- FWCI
- 46.76
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.