Faster Kriging: facing high-dimensional simulators. (English) Zbl 1445.90001

Lu, Xuefei; Rudi, Alessandro; Borgonovo, Emanuele; Rosasco, Lorenzo

Oper. Res. 68, No. 1, 233-249 (2020).

Summary: Kriging is one of the most widely used emulation methods in simulation. However, memory and time requirements potentially hinder its application to data sets generated by high-dimensional simulators. We borrow from the machine learning literature to propose a new algorithmic implementation of kriging that, while preserving prediction accuracy, notably reduces time and memory requirements. The theoretical and computational foundations of the algorithm are provided. The work then reports results of extensive numerical experiments to compare the performance of the proposed algorithm against current kriging implementations, on simulators of increasing dimensionality. Findings show notable savings in time and memory requirements that allow one to handle inputs across more that 10,000 dimensions.

MSC:

90-10

Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming

Keywords:

simulation; Kriging; metamodeling; machine learning

Software:

DiceOptim; DiceKriging; GitHub; DACE; laGP; UQLab; EGO; GPy

References:

[1]	Ankenman BE, Nelson BL, Staum J (2010) Stochastic kriging for simulation metamodeling. Oper. Res. 58(2):371-382.Link, Google Scholar · Zbl 1342.62134
[2]	Aronszajn N (1950) Theory of reproducing kernels. Trans. Amer. Math. Soc. 68(3):337-404.Crossref, Google Scholar · Zbl 0037.20701
[3]	Barton RR (1992) Metamodels for simulation input-output relations. Proc. 24th Conf. Winter Simulation (ACM, New York), 289-299.Google Scholar
[4]	Barton RR (1994) Metamodeling: A state of the art review. Proc. 26th Winter Simulation Conf. (IEEE, Piscataway, NJ), 237-244.Google Scholar
[5]	Barton RR (2015) Tutorial: Simulation metamodeling. Proc. 2015 Winter Simulation Conf. (IEEE, Piscataway, NJ), 1765-1779.Google Scholar
[6]	Barton RR, Meckesheimer M (2006) Metamodel-based simulation optimization. Henderson SG, Nelson BL, eds. Simulation, Handbooks in Operations Research and Management Science, vol. 13 (Elsevier, Amsterdam), 535-574.Google Scholar
[7]	Baucells M, Borgonovo E (2013) Invariant probabilistic sensitivity analysis. Management Sci. 59(11):2536-2549.Link, Google Scholar
[8]	Bettonvil B, Kleijnen J (1997) Searching for important factors in simulation models with many factors: Sequential bifurcation. European J. Oper. Res. 96(1):180-194.Crossref, Google Scholar · Zbl 0924.90047
[9]	Biller B, Corlu CG (2011) Accounting for parameter uncertainty in large-scale stochastic simulations with correlated inputs. Oper. Res. 59(3):661-673.Link, Google Scholar · Zbl 1342.62098
[10]	Biller B, Nelson BL (2005) Fitting time-series input processes for simulation. Oper. Res. 53(3):549-559.Link, Google Scholar · Zbl 1165.62335
[11]	Biller B, Nelson BL (2008) Evaluation of the ARTAFIT method for fitting time-series input processes for simulation. INFORMS J. Comput. 20(3):485-498.Link, Google Scholar · Zbl 1243.62114
[12]	Binois M, Gramacy RB, Ludkovski M (2018) Practical heteroskedastic gaussian process modeling for large simulation experiments. J. Comput. Graphical Statist. 27(4):808-821.Crossref, Google Scholar
[13]	Borgonovo E, Hazen G, Plischke E (2016) A common rationale for global sensitivity measures and their estimation. Risk Anal. 36(10):1871-1895.Crossref, Google Scholar
[14]	Caponnetto A, De Vito E (2007) Optimal rates for the regularized least-squares algorithm. Foundations Comput. Math. 7(3):331-368.Crossref, Google Scholar · Zbl 1129.68058
[15]	Chen VC, Tsui KL, Barton RR, Meckesheimer M (2006) A review on design, modeling and applications of computer experiments. IIE Trans. 38(4):273-291.Crossref, Google Scholar
[16]	Chen X, Kim KK (2016) Efficient VaR and CVaR measurement via stochastic kriging. INFORMS J. Comput. 28(4):629-644.Link, Google Scholar · Zbl 1414.91421
[17]	Chen X, Ankenman BE, Nelson BL (2012) The effects of common random numbers on stochastic kriging metamodels. ACM Trans. Model. Comput. Simulation 22(2):1-20.Crossref, Google Scholar · Zbl 1384.62174
[18]	Chen X, Ankenman BE, Nelson BL (2013) Enhancing stochastic kriging metamodels with gradient estimators. Oper. Res. 61(2):512-528.Link, Google Scholar · Zbl 1329.62356
[19]	Chick S (2001) Input distribution selection for simulation experiments: accounting for input uncertainty. Oper. Res. 49(5):744-758.Link, Google Scholar
[20]	Chick SE, Gans N (2009) Economic analysis of simulation selection problems. Management Sci. 55(3):421-437.Link, Google Scholar
[21]	Chilès JP, Desassis N (2018) Fifty years of kriging. Daya Sagar BS, Cheng Q, Agterberg, F eds. Handbook of Mathematical Geosciences (Springer, New York), 589-612.Google Scholar
[22]	Conway RW (1963) Some tactical problems in digital simulation. Management Sci. 10(1):47-61.Link, Google Scholar
[23]	Conway RW, Johnson B, Maxwell M (1959) Some problems of digital simulation. Management Sci. 6:92-110.Link, Google Scholar
[24]	Critchfield GG, Willard KE (1986) Probabilistic analysis of decision trees using Monte Carlo simulation. Medical Decision Making 6(2):85-92.Crossref, Google Scholar
[25]	Durrande N, Ginsbourger D, Roustant O, Carraro L (2013) ANOVA kernels and RKHS of zero mean functions for model-based sensitivity analysis. J. Multivariate Anal. 115:57-67.Crossref, Google Scholar · Zbl 1259.49066
[26]	Erickson CB, Ankenman BE, Sanchez SM (2018) Comparison of Gaussian process modeling software. European J. Oper. Res. 266(1):179-192.Crossref, Google Scholar · Zbl 1403.62006
[27]	Fu MC, ed. (2015) International Series in Operations Research & Management Science: Handbook of Simulation Optimization (Springer, New York).Google Scholar
[28]	Gamboa F, Klein T, Lagnoux A (2018) Sensitivity analysis based on Cramér-von Mises distance. SIAM/ASA J. Uncertainty Quantification 6(2):522-548.Crossref, Google Scholar · Zbl 1392.62091
[29]	Glasserman P, Liu Z (2010) Sensitivity estimates from characteristic functions. Oper. Res. 58(6):1611-1623.Link, Google Scholar · Zbl 1226.62016
[30]	GPy contributors (since 2012) GPy: A Gaussian process framework in Python. Accessed December 30, 2018, http://github.com/SheffieldML/GPy.Google Scholar
[31]	Gramacy RB (2016) laGP: large-scale spatial modeling via local approximate Gaussian processes in R. J. Statist. Software 72(1):1-46.Crossref, Google Scholar
[32]	Gramacy RB, Apley DW (2015) Local Gaussian process approximation for large computer experiments. J. Comput. Graphical Statist. 24(2):561-578.Crossref, Google Scholar
[33]	Hensman J, Fusi N, Lawrence ND (2013) Gaussian processes for big data. Working paper, University of Sheffield, Sheffield, UK.Google Scholar
[34]	Hong LJ, Nelson BL, Xu J (2010) Speeding up COMPASS for high-dimensional discrete optimization via simulation. Oper. Res. Lett. 38(6):550-555.Crossref, Google Scholar · Zbl 1202.90195
[35]	Hong LJ, Nelson BL, Xu J (2015) Discrete optimization via simulation. Fu MC, ed. International Series in Operations Research & Management Science: Handbook of Simulation Optimization (Springer, New York), 9-44.Google Scholar
[36]	Huang D, Allen TT, Notz WI, Miller RA (2006) Sequential kriging optimization using multiple-fidelity evaluations. Structural Multidisciplinary Optim. 32(5):369-382.Crossref, Google Scholar
[37]	Ilić V, Tadić JM, Imširagić A (2016) Kriging with machine learning covariates in environmental sciences: a hybrid approach. GeoMLA, Geostatistics and Machine Learning Applications in Climate and Environmental Sciences (University of Belgrade, Belgrade, Serbia).Google Scholar
[38]	Jalali H, Van Nieuwenhuyse I, Picheny V (2017) Comparison of Kriging-based algorithms for simulation optimization with heterogeneous noise. European J. Oper. Res. 261(1):279-301.Crossref, Google Scholar · Zbl 1403.90553
[39]	Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J. Global Optim. 13:455-492.Crossref, Google Scholar · Zbl 0917.90270
[40]	Kimeldorf G, Wahba G (1971) Some results on Tchebycheffian spline functions. J. Math. Anal. Appl. 33(1):82-95.Crossref, Google Scholar · Zbl 0201.39702
[41]	Kleijnen J (2009) Kriging metamodeling in simulation: A review. European J. Oper. Res. 192(3):707-716.Crossref, Google Scholar · Zbl 1157.90544
[42]	Kleijnen J (2017a) Design and analysis of simulation experiments: tutorial. Tolk A, Fowler J, Shao G, Yücesan E, eds. Advances in Modeling and Simulation, Simulation, Foundations, Methods and Applications (Springer, Cham), 135-158.Google Scholar
[43]	Kleijnen J (2017b) Regression and Kriging metamodels with their experimental designs in simulation: A review. European J. Oper. Res. 256(1):1-16.Crossref, Google Scholar · Zbl 1394.90004
[44]	Kleijnen J, Sargent RG (2000) A methodology for fitting and validating metamodels in simulation. European J. Oper. Res. 120(1):14-29.Crossref, Google Scholar · Zbl 0985.65007
[45]	Kleijnen J, van Beers W (2005) Robustness of Kriging when interpolating in random simulation with heterogeneous variances: Some experiments. European J. Oper. Res. 165(3):826-834.Crossref, Google Scholar · Zbl 1141.65330
[46]	Kleijnen J, van Beers W (2018) Prediction for big data through kriging: small sequential and one-shot designs. Working paper, Tilburg University, Tilburg, Netherlands.Google Scholar
[47]	Lataniotis C, Marelli S, Sudret B (2015) UQLab user manual - Kriging (Gaussian process modelling). Technical report, ETH Zurich, Zurich.Google Scholar
[48]	Lawrence ND, Seeger M, Herbrich R (2003) Fast sparse gaussian process methods: The informative vector machine. Becker S, Thrun S, Obermayer K, eds. Advances in Neural Information Processing Systems 15 (MIT Press, Cambridge, MA), 625-632.Google Scholar
[49]	L’Ecuyer P (1990) A unified view of the IPA, SF, and LR gradient estimation techniques. Management Sci. 36:1364-1383.Link, Google Scholar · Zbl 0731.65130
[50]	Lophaven SN, Søndergaard J, Nielsen HB (2002) DACE: A Matlab kriging toolbox, Version 2.0. (Informatiocs and Mathematical Modelling, The Technical University of Denmark).Google Scholar
[51]	Ludkovski M (2018) Kriging metamodels and experimental design for bermudan option pricing. J. Computational Finance 22(1):37-77.Google Scholar
[52]	Marrell A, Iooss B, Laurent B, Roustant O (2009) Calculations of Sobol indices for the Gaussian process metamodel. Reliability Engrg. System Safety 94:742-751.Crossref, Google Scholar
[53]	Marrel A, Iooss B, Veiga S, Ribatet M (2012) Global sensitivity analysis of stochastic computer models with joint metamodels. Statist. Comput. 22(3):833-847.Crossref, Google Scholar · Zbl 1252.62120
[54]	Mitchell TJ, Morris MD (1992) The spatial correlation function approach to response surface estimation. Proc. 24th Winter Simulation Conf. (ACM, New York), 565-571.Google Scholar
[55]	Nelson BL (2004) Stochastic simulation research in management science. Management Sci. 50(7):855-868.Link, Google Scholar
[56]	Nesterov Y (2012) Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2):341-362.Crossref, Google Scholar · Zbl 1257.90073
[57]	Noordegraaf AV, Nielen M, Kleijnen JP (2003) Sensitivity analysis by experimental design and metamodelling: Case study on simulation in national animal disease control. European J. Oper. Res. 146(3):433-443.Crossref, Google Scholar · Zbl 1038.62106
[58]	Nuclear Energy Agency (1989) PSACOIN Level E intercomparison. Technical report, OECD, Paris.Google Scholar
[59]	Picheny V, Wagner T, Ginsbourger D (2013) A benchmark of kriging-based infill criteria for noisy optimization. Structural Multidisciplinary Optim. 48(3):607-626.Crossref, Google Scholar
[60]	Plischke E, Borgonovo E (2018) Probabilistic sensitivity measures from cumulative distribution functions: Investigation and comparison with alternative methods. Working paper, Bocconi University, Milan.Google Scholar
[61]	Plischke E, Borgonovo E, Smith C (2013) Global sensitivity measures from given data. European J. Oper. Res. 226(3):536-550.Crossref, Google Scholar · Zbl 1292.90290
[62]	Preuss M, Wagner T, Ginsbourger D (2012) High-dimensional model-based optimization based on noisy evaluations of computer games. Hamadi Y, Schoenauer M, eds. Internat. Conf. Learn. Intelligent Optim.: Learn. Intelligent Optim. (Springer, New York), 145-159.Google Scholar
[63]	Pronzato L, Müller WG (2012) Design of computer experiments: Space filling and beyond. Stat. Comput. 22(3):681-701.Crossref, Google Scholar · Zbl 1252.62080
[64]	Qu H, Fu MC (2014) Gradient extrapolated stochastic kriging. ACM Trans. Model. Comput. Simulation 24(4):1-25.Crossref, Google Scholar · Zbl 1371.65011
[65]	Quiñonero-candela J, Rasmussen CE, Herbrich R (2005) A unifying view of sparse approximate Gaussian process regression. J. Mach. Learn. Res. 6:1935-1959.Google Scholar · Zbl 1222.68282
[66]	Rahman S (2016) The f-sensitivity index. SIAM/ASA J. Uncertain. Quantif. 4(1):130-162.Crossref, Google Scholar · Zbl 1348.62015
[67]	Rasmussen CE, Williams CKI (2006) Gaussian Processes for Machine Learning (MIT Press, Cambridge, MA).Google Scholar
[68]	Ratto M, Castelletti A, Pagano A (2012) Emulation techniques for the reduction and sensitivity analysis of complex environmental models. Environ. Model. Software 34:1-4.Crossref, Google Scholar
[69]	Rosenbaum I, Staum J (2017) Multilevel Monte Carlo metamodeling. Oper. Res. 65(4):1062-1077.Link, Google Scholar · Zbl 1380.65014
[70]	Roustant O, Ginsbourger D, Deville Y (2012) DiceKriging, DiceOptim: Two R packages for the analysis of computer experiments by kriging-based metamodeling and optimization. J. Statist. Software 51(1):1-55.Crossref, Google Scholar
[71]	Rubinstein RY (1989) Sensitivity analysis and performance extrapolation for computer simulation models. Oper. Res. 37(1):72-81.Link, Google Scholar
[72]	Rudi A, Camoriano R, Rosasco L (2015) Less is more: Nyström computational regularization. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. Proc. 28th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 1657-1665.Google Scholar
[73]	Saltelli A, Tarantola S (2002) On the relative importance of input factors in mathematical models: safety assessment for nuclear waste disposal. J. Amer. Statist. Assoc. 97(459):702-709.Crossref, Google Scholar · Zbl 1073.62602
[74]	Santner TJ, Williams BJ, Notz WI (2018) The Design and Analysis of Computer Experiments, 2nd ed. (Springer, New York).Crossref, Google Scholar · Zbl 1405.62110
[75]	Schölkopf B, Smola AJ (2002) Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (MIT Press, Cambridge, MA).Google Scholar
[76]	Smola AJ, Schökopf B (2000) Sparse greedy matrix approximation for machine learning. Langley P, ed. Proc. 17th Internat. Conf. Machine Learning (Morgan Kaufmann Publishers, San Francisco), 911-918.Google Scholar
[77]	Snelson E, Ghahramani Z (2006) Sparse gaussian processes using pseudo-inputs. Weiss Y, Schölkopf B, Platt JC, eds. Advances in Neural Information Processing Systems 18 (MIT Press, Cambridge, MA), 1257-1264.Google Scholar
[78]	Sobol IM (1993) Sensitivity estimates for nonlinear mathematical models. Math. Modeling Comput. Experiment. 1(4):407-414.Google Scholar · Zbl 1039.65505
[79]	Song E, Nelson BL, Staum J (2016) Shapley effects for global sensitivity analysis: Theory and computation. SIAM/ASA J. Uncertainty Quantification 4(1):1060-1083.Crossref, Google Scholar · Zbl 1403.62226
[80]	Steinwart I, Christmann A (2008) Support Vector Machines (Springer, New York).Google Scholar
[81]	Sun F, Gramacy RB, Haaland B, Lawrence E, Walker A (2019) Emulating satellite drag from large simulation experiments. SIAM/ASA J. Uncertainty Quantification 7(2):720-759.Google Scholar · Zbl 1430.62085
[82]	Sun L, Hong LJ, Hu Z (2014) Balancing exploitation and exploration in discrete optimization via simulation through a gaussian process-based search. Oper. Res. 62(6):1416-1438.Link, Google Scholar · Zbl 1327.90120
[83]	Tadić JM, Ilić VSB (2015) Examination of geostatistical and machine-learning techniques as interpolators in anisotropic atmospheric environments. Atmospheric Environ. 111(June):28-38.Crossref, Google Scholar
[84]	UK Government Office for Science (2018) Computational modelling: Technological features. Report, Council for Science and Technology, London.Google Scholar
[85]	Urtasun R, Darrell T (2008) Sparse probabilistic regression for activity-independent human pose inference. 2008 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1-8.Google Scholar
[86]	van Beers W, Kleijnen J (2003) Kriging for interpolation in random simulation. J. Oper. Res. Soc. 54(3):255-262.Crossref, Google Scholar · Zbl 1171.65305
[87]	Wagner HM (1995) Global sensitivity analysis. Oper. Res. 43(6):948-969.Link, Google Scholar · Zbl 0852.90122
[88]	Wendell RE (2004) Tolerance sensitivity and optimality bounds in linear programming. Management Sci. 50(6):797-803.Link, Google Scholar · Zbl 1232.90305
[89]	Wendland H (2004) Scattered Data Approximation (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1185.65022
[90]	Williams CKI, Seeger M (2001) Using the Nyström method to speed up kernel machines. Leen TK, Dietterich TG, Tresp V, eds. Advances in Neural Information Processing Systems 13 (MIT Press, Cambridge, MA), 682-688.Google Scholar
[91]	Xie J, Frazier PI, Chick SE (2016) Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs. Oper. Res. 64(2):542-559.Link, Google Scholar · Zbl 1342.90107
[92]	Xie W, Nelson BL, Barton RR (2014) A Bayesian framework for quantifying uncertainty in stochastic simulation. Oper. Res. 62(6):1439-1452.Link, Google Scholar · Zbl 1328.62054
[93]	Xu J (2012) Efficient discrete optimization via simulation using stochastic kriging. Proc. 2012 Winter Simulation Conf. (IEEE, Piscataway, NJ), 1-12.Google Scholar
[94]	Yin J, Ng SH, Ng KM (2009) A study on the effects of parameter estimation on Kriging model’s prediction error in stochastic simulations. Jain S, Creasey R, Himmelspach J, White KP, Fu MC, eds. Proc. 2009 Winter Simulation Conf. (IEEE, Piscataway, NJ), 674-685.Google Scholar
[95]	Yin J,