Distributionally robust stochastic programs with side information based on trimmings. (English) Zbl 1504.90077
Summary: We consider stochastic programs conditional on some covariate information, where the only knowledge of the possible relationship between the uncertain parameters and the covariates is reduced to a finite data sample of their joint distribution. By exploiting the close link between the notion of trimmings of a probability measure and the partial mass transportation problem, we construct a data-driven Distributionally Robust Optimization (DRO) framework to hedge the decision against the intrinsic error in the process of inferring conditional information from limited joint data. We show that our approach is computationally as tractable as the standard (without side information) Wasserstein-metric-based DRO and enjoys performance guarantees. Furthermore, our DRO framework can be conveniently used to address data-driven decision-making problems under contaminated samples. Finally, the theoretical results are illustrated using a single-item newsvendor problem and a portfolio allocation problem with side information.
Keywords:
distributionally robust optimization; trimmings; side information; partial mass transportation problem; newsvendor problem; portfolio optimizationReferences:
| [1] | Agulló Antolín, M.: Trimming methods for model validation and supervised classification in the presence of contamination. Ph.D. thesis (2018). http://uvadoc.uva.es/handle/10324/31682 |
| [2] | Álvarez-Esteban, del Barrio, E., Cuesta-Albertos, J.A., Matrán, C.: Similarity of samples and trimming. Bernoulli 18(2), 606-634 (2012) · Zbl 1239.62005 |
| [3] | Álvarez-Esteban, PC; del Barrio, E.; Cuesta-Albertos, JA; Matrán, C., Uniqueness and approximate computation of optimal incomplete transportation plans, Ann. Inst. Henri Poincare-Probab. Stat., 47, 2, 358-375 (2011) · Zbl 1215.49042 |
| [4] | Balghiti, O.E., Elmachtoub, A.N., Grigas, P., Tewari, A.: Generalization bounds in the predict-then-optimize framework (2019). arXiv:1905.11488 |
| [5] | Ban, GY; Rudin, C., The big data newsvendor: Practical insights from machine learning, Oper. Res., 67, 1, 90-108 (2019) · Zbl 1443.90093 · doi:10.1287/opre.2018.1757 |
| [6] | del Barrio, E.; Matrán, C., Rates of convergence for partial mass problems, Probab. Theory Relat. Field, 155, 3-4, 521-542 (2013) · Zbl 1286.60004 · doi:10.1007/s00440-011-0406-z |
| [7] | Bertsimas, D.; Kallus, N., From predictive to prescriptive analytics, Manag. Sci., 66, 3, 1025-1044 (2020) · doi:10.1287/mnsc.2018.3253 |
| [8] | Bertsimas, D., McCord, C.: Optimization over continuous and multi-dimensional decisions with observational data (2018). arXiv:1807.04183 |
| [9] | Bertsimas, D., McCord, C., Sturt, B.: Dynamic optimization with side information (2019). arXiv:1907.07307 |
| [10] | Bertsimas, D., Shtern, S., Sturt, B.: A data-driven approach for multi-stage linear optimization (2018). http://www.optimization-online.org/DB_HTML/2018/11/6907.html |
| [11] | Bertsimas, D., Shtern, S., Sturt, B.: Technical note-Two-stage sample robust optimization. Oper. Res. (2021). doi:10.1287/opre.2020.2096 · Zbl 1485.90077 |
| [12] | Bertsimas, D., Van Parys, B.: Bootstrap robust prescriptive analytics (2017). arXiv:1711.09974 |
| [13] | Biau, G., Devroye, L.: Lectures on the Nearest Neighbor Method. Springer Series in the Data Sciences. Springer (2015) · Zbl 1330.68001 |
| [14] | Chen, R.: Distributionally robust learning under the Wasserstein metric. Ph.D. thesis (2019). https://open.bu.edu/handle/2144/38236 |
| [15] | Chen, Z.; Sim, M.; Xiong, P., Robust stochastic optimization made easy with rsome, Manag. Sci., 66, 8, 3329-3339 (2020) · doi:10.1287/mnsc.2020.3603 |
| [16] | Diao, S., Sen, S.: Distribution-free algorithms for learning enabled predictive stochastic programming (2020). http://www.optimization-online.org/DB_HTML/2020/03/7661.html |
| [17] | Donti, P.; Amos, B.; Kolter, JZ, Task-based end-to-end model learning in stochastic optimization, Adv. Neural Inf. Process Syst., 1, 5484-5494 (2017) |
| [18] | Elmachtoub, A.N., Grigas, P.: Smart “predict, then optimize.” Manage. Sci. (2021). doi:10.1287/mnsc.2020.3922 |
| [19] | Esteban-Pérez, A., Morales, J.M.: Distributionally robust stochastic programs with side information based on trimmings—Extended version (2020). arXiv:2009.10592 |
| [20] | Esteban-Pérez, A., Morales, J.M.: Distributionally robust stochastic programs with side information based on trimmings - Codes and Data. GitHub repository (2021). https://github.com/groupoasys/DRO_CONDITIONAL_TRIMMINGS |
| [21] | Falk, M., Hüsler, J., Reiss, R.D.: Laws of small numbers: extremes and rare events. Springer (2010) |
| [22] | Farokhi, F.: Why does regularization help with mitigating poisoning attacks? Neural Process. Lett. (2021). doi:10.1007/s11063-021-10539-1 |
| [23] | Fournier, N.; Guillin, A., On the rate of convergence in wasserstein distance of the empirical measure, Probab. Theory Relat. Field, 162, 3, 707-738 (2015) · Zbl 1325.60042 · doi:10.1007/s00440-014-0583-7 |
| [24] | Gao, R.: Finite-sample guarantees for Wasserstein distributionally robust optimization: Breaking the curse of dimensionality (2020). arXiv:2009.04382 |
| [25] | Gao, R., Kleywegt, A.J.: Distributionally Robust Stochastic Optimization with Wasserstein Distance (2016). arXiv:1604.02199 |
| [26] | Gibbs, AL; Su, FE, On choosing and bounding probability metrics, Int. Stat. Rev., 70, 3, 419-435 (2002) · Zbl 1217.62014 · doi:10.1111/j.1751-5823.2002.tb00178.x |
| [27] | Gray, R.M.: Probability, Random Processes, and Ergodic Properties. Springer (2009). doi:10.1007/978-1-4419-1090-5 · Zbl 1191.60007 |
| [28] | Hanasusanto, GA; Kuhn, D., Robust data-driven dynamic programming, Adv. Neural Inf. Process. Syst., 26, 827-835 (2013) |
| [29] | Hannah, L.; Powell, W.; Blei, D., Nonparametric density estimation for stochastic optimization with an observable state variable, Adv. Neural Inf. Process Syst., 23, 820-828 (2010) |
| [30] | Huber, J.; Müller, S.; Fleischmann, M.; Stuckenschmidt, H., A data-driven newsvendor problem: from data to decision, Eur. J. Oper. Res., 278, 3, 904-915 (2019) · Zbl 1430.90021 · doi:10.1016/j.ejor.2019.04.043 |
| [31] | Kannan, R., Bayraksan, G., Luedtke, J.: Heteroscedasticity-aware residuals-based contextual stochastic optimization. arXiv preprint arXiv:2101.03139 (2021) |
| [32] | Kannan, R., Bayraksan, G., Luedtke, J.R.: Data-driven sample average approximation with covariate information. Optimization. Online. http://www.optimization-online.org/DB_HTML/2020/07/7932.html (2020) |
| [33] | Kannan, R., Bayraksan, G., Luedtke, J.R.: Residuals-based distributionally robust optimization with covariate information (2020). arXiv:2012.01088 |
| [34] | Kuhn, D., Esfahani, P.M., Nguyen, V.A., Shafieezadeh-Abadeh, S.: Wasserstein distributionally robust optimization: Theory and applications in machine learning. In: Operations Research & Management Science in the Age of Analytics, pp. 130-166. INFORMS (2019). doi:10.1287/educ.2019.0198 |
| [35] | Mohajerin Esfahani, P.; Kuhn, D., Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations, Math. Program., 171, 1-2, 115-166 (2018) · Zbl 1433.90095 · doi:10.1007/s10107-017-1172-1 |
| [36] | Muñoz, M.A., Pineda, S., Morales, J.M.: A bilevel framework for decision-making under uncertainty with contextual information (2020). arXiv:2008.01500 |
| [37] | Nguyen, V.A., Zhang, F., Blanchet, J., Delage, E., Ye, Y.: Distributionally robust local non-parametric conditional estimation (2020). arXiv:2010.05373 |
| [38] | Nguyen, V.A., Zhang, F., Blanchet, J., Delage, E., Ye, Y.: Robustifying conditional portfolio decisions via optimal transport (2021). arXiv:2103.16451 |
| [39] | Pang Ho, C., Hanasusanto, G.A.: On data-driven prescriptive analytics with side information: A regularized Nadaraya-Watson approach (2019). http://www.optimization-online.org/DB_HTML/2019/01/7043.html |
| [40] | Rahimian, H., Mehrotra, S.: Distributionally robust optimization: a review (2019). arXiv:1908.05659 |
| [41] | Rockafellar, RT; Uryasev, S., Optimization of conditional value-at-risk, J. Risk, 2, 21-41 (2000) · doi:10.21314/JOR.2000.038 |
| [42] | Santambrogio, F.: Optimal transport for applied mathematicians (2015). doi:10.1007/978-3-319-20828-2 · Zbl 1401.49002 |
| [43] | Sen, S., Deng, Y.: Learning enabled optimization: Towards a fusion of statistical learning and stochastic programming (2018). http://www.optimization-online.org/DB_HTML/2017/03/5904.html |
| [44] | Sion, M.: On general minimax theorems. Pac. J. Math. 1103040253 (1958) · Zbl 0081.11502 |
| [45] | Villani, C.: Topics in Optimal Transportation, Graduate Studies in Mathematics, vol. 58. American Mathematical Society (2003) · Zbl 1106.90001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
