Residuals-based distributionally robust optimization with covariate information. (English) Zbl 07915919
Summary: We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained using Wasserstein, sample robust optimization, and phi-divergence-based ambiguity sets within our DRO formulations, and explore cross-validation approaches for sizing these ambiguity sets. Through numerical experiments, we validate our theoretical results, study the effectiveness of our approaches for sizing ambiguity sets, and illustrate the benefits of our DRO formulations in the limited data regime even when the prediction model is misspecified.
Keywords:
data-driven stochastic programming; distributionally robust optimization; Wasserstein distance; phi-divergences; covariates; machine learning; convergence rate; large deviationsReferences:
| [1] | Ban, GY; Gallien, J.; Mersereau, AJ, Dynamic procurement of new products with covariate information: the residual tree method, Manuf. Serv. Oper. Manag., 21, 4, 798-815, 2019 · doi:10.1287/msom.2018.0725 |
| [2] | Ban, GY; Rudin, C., The big data newsvendor: practical insights from machine learning, Oper. Res., 67, 1, 90-108, 2018 · Zbl 1443.90093 · doi:10.1287/opre.2018.1757 |
| [3] | Bansal, M.; Huang, KL; Mehrotra, S., Decomposition algorithms for two-stage distributionally robust mixed binary programs, SIAM J. Optim., 28, 3, 2360-2383, 2018 · Zbl 1401.90126 · doi:10.1137/17M1115046 |
| [4] | Bayraksan, G., Love, D.K.: Data-driven stochastic programming using phi-divergences. In: The Operations Research Revolution, pp. 1-19. INFORMS TutORials in Operations Research (2015) |
| [5] | Bazier-Matte, T., Delage, E.: Generalization bounds for regularized portfolio selection with market side information. INFOR: Information Systems and Operational Research, pp. 1-28 (2020) |
| [6] | Ben-Tal, A.; Den Hertog, D.; De Waegenaere, A.; Melenberg, B.; Rennen, G., Robust solutions of optimization problems affected by uncertain probabilities, Manag. Sci., 59, 2, 341-357, 2013 · doi:10.1287/mnsc.1120.1641 |
| [7] | Bertsimas, D.; Gupta, V.; Kallus, N., Robust sample average approximation, Math. Program., 171, 1-2, 217-282, 2018 · Zbl 1432.90168 · doi:10.1007/s10107-017-1174-z |
| [8] | Bertsimas, D.; Kallus, N., From predictive to prescriptive analytics, Manag. Sci., 66, 3, 1025-1044, 2020 · doi:10.1287/mnsc.2018.3253 |
| [9] | Bertsimas, D.; McCord, C.; Sturt, B., Dynamic optimization with side information, Eur. J. Oper. Res., 304, 2, 634-651, 2023 · Zbl 1524.90234 · doi:10.1016/j.ejor.2022.03.030 |
| [10] | Bertsimas, D.; Shtern, S.; Sturt, B., A data-driven approach to multistage stochastic linear optimization, Manag. Sci., 2022 · doi:10.1287/mnsc.2022.4352 |
| [11] | Bertsimas, D.; Shtern, S.; Sturt, B., Two-stage sample robust optimization, Oper. Res., 70, 1, 624-640, 2022 · Zbl 1485.90077 · doi:10.1287/opre.2020.2096 |
| [12] | Bertsimas, D.; Van Parys, B., Bootstrap robust prescriptive analytics, Math. Program., 195, 1, 39-78, 2022 · Zbl 1504.90076 · doi:10.1007/s10107-021-01679-2 |
| [13] | Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V., Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98, 2017 · Zbl 1356.68030 · doi:10.1137/141000671 |
| [14] | Blanchet, J.; Kang, Y.; Murthy, K., Robust Wasserstein profile inference and applications to machine learning, J. Appl. Probab., 56, 3, 830-857, 2019 · Zbl 1436.62336 · doi:10.1017/jpr.2019.49 |
| [15] | Blanchet, J., Murthy, K., Nguyen, V.A.: Statistical analysis of Wasserstein distributionally robust estimators. In: Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pp. 227-254. INFORMS (2021) |
| [16] | Blanchet, J.; Murthy, K.; Si, N., Confidence regions in Wasserstein distributionally robust estimation, Biometrika, 109, 2, 295-315, 2022 · Zbl 07543325 · doi:10.1093/biomet/asab026 |
| [17] | Boskos, D., Cortés, J., Martínez, S.: Data-driven ambiguity sets for linear systems under disturbances and noisy observations. In: 2020 American Control Conference (ACC), pp. 4491-4496. IEEE (2020) |
| [18] | Boskos, D.; Cortés, J.; Martínez, S., Data-driven ambiguity sets with probabilistic guarantees for dynamic processes, IEEE Trans. Autom. Control, 66, 7, 2991-3006, 2020 · Zbl 1467.93287 · doi:10.1109/TAC.2020.3014098 |
| [19] | Boskos, D., Cortés, J., Martínez, S.: High-confidence data-driven ambiguity sets for time-varying linear systems. arXiv preprint arXiv:2102.01142 (2021) |
| [20] | Deng, Y.; Sen, S., Predictive stochastic programming, CMS, 19, 1, 65-98, 2022 · Zbl 07510425 · doi:10.1007/s10287-021-00400-0 |
| [21] | Dou, X.; Anitescu, M., Distributionally robust optimization with correlated data from vector autoregressive processes, Oper. Res. Lett., 47, 4, 294-299, 2019 · Zbl 1476.90215 · doi:10.1016/j.orl.2019.04.005 |
| [22] | Duchi, JC; Glynn, PW; Namkoong, H., Statistics of robust optimization: a generalized empirical likelihood approach, Math. Oper. Res., 46, 3, 946-969, 2021 · Zbl 1473.62292 · doi:10.1287/moor.2020.1085 |
| [23] | Dunning, I.; Huchette, J.; Lubin, M., JuMP: a modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320, 2017 · Zbl 1368.90002 · doi:10.1137/15M1020575 |
| [24] | Esfahani, PM; 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 |
| [25] | Esteban-Pérez, A.; Morales, JM, Distributionally robust stochastic programs with side information based on trimmings, Math. Program., 195, 1, 1069-1105, 2022 · Zbl 1504.90077 · doi:10.1007/s10107-021-01724-0 |
| [26] | Fournier, N.; Guillin, A., On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Relat. Fields, 162, 3-4, 707-738, 2015 · Zbl 1325.60042 · doi:10.1007/s00440-014-0583-7 |
| [27] | Friedman, J.; Hastie, T.; Tibshirani, R., Regularization paths for generalized linear models via coordinate descent, J. Stat. Softw., 33, 1, 1-22, 2010 · doi:10.18637/jss.v033.i01 |
| [28] | Gao, R., Finite-sample guarantees for Wasserstein distributionally robust optimization: breaking the curse of dimensionality, Oper. Res., 2022 · Zbl 1542.90176 · doi:10.1287/opre.2022.2326 |
| [29] | Gao, R.; Chen, X.; Kleywegt, AJ, Wasserstein distributionally robust optimization and variation regularization, Oper. Res., 2022 · Zbl 07888755 · doi:10.1287/opre.2022.2383 |
| [30] | Gao, R.; Kleywegt, A., Distributionally robust stochastic optimization with Wasserstein distance, Math. Oper. Res., 2022 · Zbl 1540.90171 · doi:10.1287/moor.2022.1275 |
| [31] | Gotoh, JY; Kim, MJ; Lim, AE, Calibration of distributionally robust empirical optimization models, Oper. Res., 69, 5, 1630-1650, 2021 · Zbl 1485.90080 · doi:10.1287/opre.2020.2041 |
| [32] | Hanasusanto, G.A., Kuhn, D.: Robust data-driven dynamic programming. In: Advances in Neural Information Processing Systems, pp. 827-835 (2013) |
| [33] | Hanasusanto, GA; Kuhn, D., Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls, Oper. Res., 66, 3, 849-869, 2018 · Zbl 1455.90121 · doi:10.1287/opre.2017.1698 |
| [34] | Homem-de-Mello, T.; Bayraksan, G., Monte Carlo sampling-based methods for stochastic optimization, Surv. Oper. Res. Manag. Sci., 19, 1, 56-85, 2014 |
| [35] | Kannan, R., Bayraksan, G., Luedtke, J.: Heteroscedasticity-aware residuals-based contextual stochastic optimization. arXiv preprint arXiv:2101.03139, pp. 1-15 (2021) |
| [36] | Kannan, R., Bayraksan, G., Luedtke, J.: Data-driven sample average approximation with covariate information. arXiv preprint arXiv:2207.13554v1, pp. 1-57 (2022) |
| [37] | 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) |
| [38] | Lam, H., Robust sensitivity analysis for stochastic systems, Math. Oper. Res., 41, 4, 1248-1275, 2016 · Zbl 1361.65008 · doi:10.1287/moor.2015.0776 |
| [39] | Lam, H., Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization, Oper. Res., 67, 4, 1090-1105, 2019 · Zbl 1455.90122 |
| [40] | Lewandowski, D.; Kurowicka, D.; Joe, H., Generating random correlation matrices based on vines and extended onion method, J. Multivar. Anal., 100, 9, 1989-2001, 2009 · Zbl 1170.62042 · doi:10.1016/j.jmva.2009.04.008 |
| [41] | Mak, WK; Morton, DP; Wood, RK, Monte Carlo bounding techniques for determining solution quality in stochastic programs, Oper. Res. Lett., 24, 1-2, 47-56, 1999 · Zbl 0956.90022 · doi:10.1016/S0167-6377(98)00054-6 |
| [42] | Nguyen, VA; Zhang, F.; Blanchet, J.; Delage, E.; Ye, Y., Distributionally robust local non-parametric conditional estimation, Adv. Neural Inf. Process. Syst., 33, 15232-15242, 2020 |
| [43] | Pflug, G.; Wozabal, D., Ambiguity in portfolio selection, Quant. Finance, 7, 4, 435-442, 2007 · Zbl 1190.91138 · doi:10.1080/14697680701455410 |
| [44] | Rahimian, H.; Mehrotra, S., Frameworks and results in distributionally robust optimization, Open J. Math. Optim., 3, 1-85, 2022 · Zbl 1492.90109 · doi:10.5802/ojmo.15 |
| [45] | Rigollet, P., Hütter, J.C.: High dimensional statistics. Lecture notes for MIT’s 18.657 course (2017). URl http://www-math.mit.edu/ rigollet/PDFs/RigNotes17.pdf |
| [46] | Rockafellar, RT; Uryasev, S., Optimization of conditional value-at-risk, J. Risk, 2, 21-42, 2000 · doi:10.21314/JOR.2000.038 |
| [47] | Rockafellar, RT; Uryasev, S., Conditional value-at-risk for general loss distributions, J. Bank. Finance, 26, 7, 1443-1471, 2002 · doi:10.1016/S0378-4266(02)00271-6 |
| [48] | Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on stochastic programming: modeling and theory. SIAM (2009) · Zbl 1183.90005 |
| [49] | Trillos, NG; Slepčev, D., On the rate of convergence of empirical measures in \(\infty \)-transportation distance, Can. J. Math., 67, 6, 1358-1383, 2015 · Zbl 1355.60009 · doi:10.4153/CJM-2014-044-6 |
| [50] | van der Vaart, AW; Wellner, JA, Weak Convergence and Empirical Processes: with Applications to Statistics, 1996, Berlin: Springer, Berlin · Zbl 0862.60002 · doi:10.1007/978-1-4757-2545-2 |
| [51] | Villani, C., Optimal Transport: Old and New, 2008, Berlin: Springer Science & Business Media, Berlin |
| [52] | Xie, W., Tractable reformulations of two-stage distributionally robust linear programs over the type-\( \infty\) Wasserstein ball, Oper. Res. Lett., 48, 4, 513-523, 2020 · Zbl 1479.90148 · doi:10.1016/j.orl.2020.06.003 |
| [53] | Xu, H.; Caramanis, C.; Mannor, S., A distributional interpretation of robust optimization, Math. Oper. Res., 37, 1, 95-110, 2012 · Zbl 1243.90167 · doi:10.1287/moor.1110.0531 |
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.
