Beyond IID: Data-Driven Decision Making in Heterogeneous Environments

References

• Allouah A, Bahamou A, Besbes O (2022) Pricing with samples. Oper. Res. 70(2):1088–1104.Link, Google Scholar
• Babaioff M, Gonczarowski YA, Mansour Y, Moran S (2018) Are two (samples) really better than one? EC’18: Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 175–175.Google Scholar
• Ben-David S, Blitzer J, Crammer K, Kulesza A, Pereira F, Vaughan JW (2010) A theory of learning from different domains. Machine Learn. 79(1):151–175.Crossref, Google Scholar
• Bennouna A, Van Parys B (2022) Holistic robust data-driven decisions. Preprint, submitted July 19, https://arxiv.org/abs/2207.09560.Google Scholar
• Bergemann D, Schlag K (2011) Robust monopoly pricing. J. Econom. Theory 146(6):2527–2543.Crossref, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Gupta V, Kallus N (2018) Robust sample average approximation. Math. Programming 171(1):217–282.Crossref, Google Scholar
• Besbes O, Mouchtaki O (2023) How big should your data really be? Data-driven newsvendor: Learning one sample at a time. Management Sci. 69(10):5848–5865.Link, Google Scholar
• Besbes O, Gur Y, Zeevi A (2014) Stochastic multi-armed-bandit problem with non-stationary rewards. NIPS’14: Proc. 28th Internat. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 199–207.Google Scholar
• Bilodeau B, Negrea J, Roy DM (2020) Relaxing the I.I.D. assumption: Adaptively minimax optimal regret via root-entropic regularization. Preprint, submitted July 13, https://arxiv.org/abs/2007.06552.Google Scholar
• Blanc G, Lange J, Malik A, Tan L-Y (2022) On the power of adaptivity in statistical adversaries. Proc. 35th Conf. Learn. Theory (COLT), vol. 178 (PMLR, New York), 5030–5061.Google Scholar
• Blanchard M (2022) Universal online learning: An optimistically universal learning rule. Proc. 35th Conf. Learn. Theory (COLT), vol. 178 (PMLR, New York), 1077–1125.Google Scholar
• Block A, Dagan Y, Golowich N, Rakhlin A (2022) Smoothed online learning is as easy as statistical learning. Proc. 35th Conf. Learn. Theory (COLT), vol. 178 (PMLR, New York), 1716–1786.Google Scholar
• Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Brustle J, Cai Y, Daskalakis C (2020) Multi-item mechanisms without item-independence: Learnability via robustness. EC’20: Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 715–761.Google Scholar
• Cai Y, Daskalakis C (2017) Learning multi-item auctions with (or without) samples. 2017 IEEE 58th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 516–527.Google Scholar
• Chen X, Wang Y (2022) Robust dynamic pricing with demand learning in the presence of outlier customers. Oper. Res. 71(4):1362–1386.Google Scholar
• Cheung WC, Simchi-Levi D (2019) Sampling-based approximation schemes for capacitated stochastic inventory control models. Math. Oper. Res. 44(2):668–692.Link, Google Scholar
• Cheung WC, Simchi-Levi D, Zhu R (2022) Hedging the drift: Learning to optimize under nonstationarity. Management Sci. 68(3):1696–1713.Link, Google Scholar
• Daskalakis C, Zampetakis M (2020) More revenue from two samples via factor revealing SDPs. EC’20: Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 257–272.Google Scholar
• Delage E, Kuhn D, Wiesemann W (2019) “Dice”-sion–making under uncertainty: When can a random decision reduce risk? Management Sci. 65(7):3282–3301.Link, Google Scholar
• Diakonikolas I, Kontonis V, Tzamos C, Vakilian A, Zarifis N (2021) Learning online algorithms with distributional advice. Proc. 38th Internat. Conf. Machine Learn. (ICML), vol. 139 (PMLR, New York), 2687–2696.Google Scholar
• Diakonikolas I, Kamath G, Kane D, Li J, Moitra A, Stewart A (2019) Robust estimators in high-dimensions without the computational intractability. SIAM J. Comput. 48(2):742–864.Crossref, Google Scholar
• Duchi JC, Namkoong H (2021) Learning models with uniform performance via distributionally robust optimization. Ann. Statist. 49(3):1378–1406.Crossref, Google Scholar
• Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math. Programming 95(3):493–511.Crossref, Google Scholar
• Dütting P, Kesselheim T (2019) Posted pricing and prophet inequalities with inaccurate priors. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 111–129.Google Scholar
• Eren SS, Maglaras C (2010) Monopoly pricing with limited demand information. J. Revenue Pricing Management 9(1–2):23–48.Crossref, Google Scholar
• Fu H, Immorlica N, Lucier B, Strack P (2015) Randomization beats second price as a prior-independent auction. Proc. 16th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 323–323.Google Scholar
• Gallego G, Moon I (1993) The distribution free newsboy problem: Review and extensions. J. Oper. Res. Soc. 44(8):825–834.Crossref, Google Scholar
• Gibbs AL, Su FE (2002) On choosing and bounding probability metrics. Internat. Statist. Rev. 70(3):419–435.Crossref, Google Scholar
• Glasserman P, Xu X (2014) Robust risk measurement and model risk. Quant. Finance 14(1):29–58.Crossref, Google Scholar
• Guo W, Jordan M, Zampetakis E (2021) Robust learning of optimal auctions. NIPS’21: Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 21273–21284.Google Scholar
• Haghtalab N, Roughgarden T, Shetty A (2022a) Smoothed analysis with adaptive adversaries. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 942–953.Google Scholar
• Haghtalab N, Han Y, Shetty A, Yang K (2022b) Oracle-efficient online learning for smoothed adversaries. NeurIPS’22: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 4072–4084.Google Scholar
• Hampel FR (1971) A general qualitative definition of robustness. Ann. Math. Statist. 42(6):1887–1896.Crossref, Google Scholar
• Hanneke S (2021) Learning whenever learning is possible: Universal learning under general stochastic processes. J. Machine Learn. Res. 22(130):1–116.Google Scholar
• Haussler D (1992) Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. Comput. 100(1):78–150.Crossref, Google Scholar
• Huang Z, Mansour Y, Roughgarden T (2018) Making the most of your samples. SIAM J. Comput. 47(3):651–674.Crossref, Google Scholar
• Huber PJ (1992) Robust estimation of a location parameter. Kotz S, Johnson NL, eds. Breakthroughs in Statistics, Springer Series in Statistics (Springer, New York), 492–518.Crossref, Google Scholar
• Kantorovich LV, Akilov GP (2016) Functional Analysis (Elsevier, Amsterdam).Google Scholar
• Kantorovich LV, Rubinshtein S (1958) On a space of totally additive functions. Vestnik St. Petersburg Uni. Math. 13(7):52–59.Google Scholar
• Karnin ZS, Anava O (2016) Multi-armed bandits: Competing with optimal sequences. NIPS’16: Proc. 30th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 199–207.Google Scholar
• Kearns M, Li M (1993) Learning in the presence of malicious errors. SIAM J. Comput. 22(4):807–837.Crossref, Google Scholar
• Kearns MJ, Schapire RE, Sellie LM (1994) Toward efficient agnostic learning. Machine Learn. 17(2):115–141.Crossref, Google Scholar
• Kim S, Pasupathy R, Henderson SG (2015) A guide to sample average approximation. Fu M, ed. Handbook of Simulation Optimization, International Series in Operations Research & Management Science, vol. 216 (Springer, New York), 207–243.Crossref, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Klivans AR, Long PM, Servedio RA (2009) Learning halfspaces with malicious noise. J. Machine Learn. Res. 10(12):2715–2740.Google Scholar
• Lam H (2021) On the impossibility of statistically improving empirical optimization: A second-order stochastic dominance perspective. Preprint, submitted May 27, https://arxiv.org/abs/2105.13419.Google Scholar
• Levi R, Perakis G, Uichanco J (2015) The data-driven newsvendor problem: New bounds and insights. Oper. Res. 63(6):1294–1306.Link, Google Scholar
• Lin M, Huh WT, Krishnan H, Uichanco J (2022) Data-driven newsvendor problem: Performance of the sample average approximation. Oper. Res. 70(4):1996–2012.Link, Google Scholar
• Luo H, Wei C-Y, Agarwal A, Langford J (2018) Efficient contextual bandits in non-stationary worlds. Proc. 31st Conf. Learn. Theory (COLT), vol. 75 (PMLR, New York), 1739–1776.Google Scholar
• Lykouris T, Mirrokni V, Paes Leme R (2018) Stochastic bandits robust to adversarial corruptions. STOC 2018: Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 114–122.Google Scholar
• Lykouris T, Simchowitz M, Slivkins A, Sun W (2021) Corruption-robust exploration in episodic reinforcement learning. Proc. 34th Conf. Learn. Theory (COLT), vol. 134 (PMLR, New York), 3242–3245.Google Scholar
• Mansour Y, Mohri M, Rostamizadeh A (2009) Domain adaptation: Learning bounds and algorithms. Preprint, submitted February 9, https://arxiv.org/abs/0902.3430.Google Scholar
• Mohajerin Esfahani P, Kuhn D (2018) Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1):115–166.Crossref, Google Scholar
• Mohri M, Muñoz Medina A (2012) New analysis and algorithm for learning with drifting distributions. Bshouty NH, Stoltz G, Vayatis N, Zeugmann T, eds. Algorithmic Learn. Theory. ALT 2012, Lecture Notes in Computer Science, vol. 7568 (Springer, Berlin, Heidelberg), 124–138.Google Scholar
• Morse PM, Kimball GE (1946) Methods of operations research. Technical report, Operations Evaluation Group, Center for Naval Analyses, Alexandria, VA.Google Scholar
• Müller A (1997) Integral probability metrics and their generating classes of functions. Adv. Appl. Probab. 29(2):429–443.Crossref, Google Scholar
• Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• Perakis G, Roels G (2008) Regret in the newsvendor model with partial information. Oper. Res. 56(1):188–203.Link, Google Scholar
• Pichler A, Xu H (2022) Quantitative stability analysis for minimax distributionally robust risk optimization. Math. Programming 191(1):47–77.Crossref, Google Scholar
• Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ML predictions. NIPS’18: Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 9684–9693.Google Scholar
• Rachev ST, Römisch W (2002) Quantitative stability in stochastic programming: The method of probability metrics. Math. Oper. Res. 27(4):792–818.Link, Google Scholar
• Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. Preprint, submitted August 13, https://arxiv.org/abs/1908.05659.Google Scholar
• Rakhlin A, Sridharan K, Tewari A (2011) Online learning: Stochastic, constrained, and smoothed adversaries. Proc. 25th Internat. Conf. Neural Inform. Processing Systems (NIPS’11) (Curran Associates Inc., Red Hook, NY), 1764–1772.Google Scholar
• Riley J, Zeckhauser R (1983) Optimal selling strategies: When to haggle, when to hold firm. Quart. J. Econom. 98(2):267–289.Crossref, Google Scholar
• Römisch W, Schultz R (1991) Stability analysis for stochastic programs. Ann. Oper. Re. 30(1):241–266.Crossref, Google Scholar
• Roughgarden T (2021) Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK).Google Scholar
• Scarf H (1958) A min-max solution of an inventory problem. Arrow KJ, Karlin S, Scarf H, eds. Studies in the Mathematical Theory of Inventory and Production (Stanford University Press, Redwood City, CA), 201–209.Google Scholar
• Schultz R (1996) Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optim. 6(4):1138–1152.Crossref, Google Scholar
• Servedio RA (2003) Smooth boosting and learning with malicious noise. J. Machine Learn. Res. 4:633–648.Google Scholar
• Sriperumbudur BK, Gretton A, Fukumizu K, Schölkopf B, Lanckriet GR (2010) Hilbert space embeddings and metrics on probability measures. J. Machine Learn. Res. 11(50):1517–1561.Google Scholar
• Vapnik V, Chervonenkis A (1974) Theory of Pattern Recognition (Nauka, Moscow). [In Russian.]Google Scholar
• Xu H, Zhang S (2021) Quantitative statistical robustness in distributionally robust optimization models. Pacific J. Optim. 19(2):335–361.Google Scholar
• Zolotarev VM (1984) Probability metrics. Theory Probab. Appl. 28(2):278–302.Crossref, Google Scholar