Dynamic finite-budget allocation of stratified sampling with adaptive variance reduction by strata. (English) Zbl 1512.65008
Summary: We develop and analyze a dynamic finite-budget allocation scheme for stratified sampling for general purposes on the unit hypercube with adaptive variance reduction applied by strata. By batching the parallelized tasks, the proposed scheme succeeds to update the budget allocation only occasionally yet effectively takes into account the decreasing stratum variances while simultaneously estimating the stratum means and updating the variance reduction parameters throughout. The scheme is designed to accommodate a variety of existing algorithms for the parameter search procedure. In particular, when stochastic approximation is employed, we derive optimal stratum batchwise learning rates in accordance with the adjusted batch size along the way. Numerical results are provided to support the theoretical findings and to illustrate the effectiveness of the proposed scheme.
MSC:
| 65C05 | Monte Carlo methods |
| 65Y20 | Complexity and performance of numerical algorithms |
| 93E35 | Stochastic learning and adaptive control |
| 62L20 | Stochastic approximation |
Keywords:
stratified sampling; importance sampling; control variates; stochastic approximation; uniform distribution; budget allocationReferences:
| [1] | Alrefaei, M. H. and Abdul-Rahman, H. M., An adaptive Monte Carlo integration algorithm with general division approach, Math. Comput. Simulation, 79 (2008), pp. 49-59. · Zbl 1151.65005 |
| [2] | Arouna, B., Adaptative Monte Carlo method, a variance reduction technique, Monte Carlo Methods Appl., 10 (2004), pp. 1-24, doi:10.1515/156939604323091180. · Zbl 1063.65003 |
| [3] | Carpentier, A. and Munos, R., Finite-time analysis of stratified sampling for Monte Carlo, in , Curran Associates, 2011, pp. 1-9. |
| [4] | Carpentier, A. and Munos, R., Adaptive stratified sampling for Monte-Carlo integration of differentiable functions, in , Curran Associates, 2012, pp. 1-9. |
| [5] | Carpentier, A. and Munos, R., Toward optimal stratification for stratified Monte-Carlo integration, in Proceedings of the 30th International Conference on Machine Learning 28, , PMLR, 2013, pp. 28-36. |
| [6] | Carpentier, A., Munos, R., and Antos, A., Adaptive strategy for stratified Monte Carlo sampling, J. Mach. Learn. Res., 16 (2015), pp. 2231-2271. · Zbl 1351.62013 |
| [7] | Dingeç, K. D. and Hörmann, W., A general control variate method for option pricing under Lévy processes, Eur. J. Oper. Res., 2 (2012), pp. 368-377. · Zbl 1253.91177 |
| [8] | Dingeç, K. D., Sak, H., and Hörmann, W., Variance reduction for Asian options under a general model framework, Rev. Financ., 19 (2015), pp. 907-949. · Zbl 1417.91552 |
| [9] | Engelund, S. and Rackwitz, R., A benchmark study on importance sampling techniques in structural reliability, Struct. Saf., 12 (1993), pp. 255-276. |
| [10] | Étoré, P., Fort, G., Jourdain, B. and Moulines, E., On adaptive stratification, Ann. Oper. Res., 189 (2011), pp. 127-154, doi:10.1007/s10479-009-0638-9. · Zbl 1279.65007 |
| [11] | Étoré, P. and Jourdain, B., Adaptive optimal allocation in stratified sampling methods, Methodol. Comput. Appl. Probab., 12 (2008), pp. 335-360, doi:10.1007/s11009-008-9108-0. · Zbl 1208.65005 |
| [12] | Ghalehnovi, M., Rashki, M., and Ameryan, A., First order control variates algorithm for reliability analysis of engineering structures, Appl. Math. Model., 77 (2020), pp. 829-847. · Zbl 1443.74257 |
| [13] | Jiang, G., Xu, C., and Fu, M., On sample average approximation algorithms for determining the optimal importance sampling parameters in pricing financial derivatives on Lévy processes, Oper. Res. Lett., 44 (2016), pp. 44-49. · Zbl 1408.91233 |
| [14] | Jourdain, B. and Lelong, J., Robust adaptive importance sampling for normal random vectors, Ann. Appl. Probab., 19 (2009), pp. 1687-1718, doi:10.1214/09-aap595. · Zbl 1202.62106 |
| [15] | Kawai, R., Asymptotically optimal allocation of stratified sampling with adaptive variance reduction by strata, ACM Trans. Model. Comput. Simul., 20 (2010), 9. doi:10.1145/1734222.1734225. · Zbl 1386.65019 |
| [16] | Kawai, R., Acceleration on adaptive importance sampling with sample average approximation, SIAM J. Sci. Comput., 39 (2017), pp. A1586-A1615, doi:10.1137/15M1047192. · Zbl 1372.65005 |
| [17] | Kawai, R., Adaptive importance sampling Monte Carlo simulation for general multivariate probability laws, J. Comput. Appl. Math., 319 (2017), pp. 440-459, doi:10.1016/j.cam.2017.01.029. · Zbl 1360.65044 |
| [18] | Kawai, R., Optimizing adaptive importance sampling by stochastic approximation, SIAM J. Sci. Comput., 40 (2018), pp. A2774-A2800, doi:10.1137/18M1173472. · Zbl 1396.65009 |
| [19] | Kawai, R., Adaptive importance sampling and control variates, J. Math. Anal. Appl., 483 (2020), 123608, doi:10.1016/j.jmaa.2019.123608. · Zbl 07138453 |
| [20] | Lemaire, V. and Pagès, G., Unconstrained recursive importance sampling, Ann. Appl. Probab., 20 (2010), pp. 1029-1067. · Zbl 1207.65007 |
| [21] | Lu, Z., Song, S., Yue, Z., and Wang, J., Reliability sensitivity method by line sampling, Struct. Saf., 30 (2008), pp. 517-532. |
| [22] | MiarNaeimi, F., Azizyan, G., and Rashki, M., Reliability sensitivity analysis method based on subset simulation hybrid techniques, Appl. Math. Model., 75 (2019), pp. 607-626, doi:10.1016/j.apm.2019.05.038. · Zbl 1481.60189 |
| [23] | Papaioannou, I., Papadimitriou, C., and Straub, D., Sequential importance sampling for structural reliability analysis, Struct. Saf., 62 (2016), pp. 66-75, doi:10.1016/j.strusafe.2016.06.002. |
| [24] | Press, W. H. and Farrar, G. R., Recursive stratified sampling for multidimensional Monte Carlo integration, Comput. Phys., 4 (1990), pp. 190-195, doi:10.1063/1.4822899. |
| [25] | Sayah, T., Adaptive stratified Monte Carlo algorithm for numerical computation of integrals, Math. Comput. Simulation, 157 (2019), pp. 143-158, doi:10.1016/j.matcom.2018.10.004. · Zbl 1540.65009 |
| [26] | Shields, M. D., Teferra, K., Hapij, A., and Daddazio, R. P., Refined stratified sampling for efficient Monte Carlo based uncertainty quantification, Reliab. Eng. Syst. Safe., 142 (2015), pp. 310-325, doi:10.1016/j.ress.2015.05.023. |
| [27] | Taverniers, S. and Tartakovsky, D. M., Estimation of distributions via multilevel Monte Carlo with stratified sampling, J. Comput. Phys., 419 (2020), 109572, doi:10.1016/j.jcp.2020.109572. · Zbl 07507220 |
| [28] | Xiao, S., Oldayshkin, S., and Nowak, W., Reliability analysis with stratified importance sampling based on adaptive Kriging, Reliab. Eng. Syst. Safe., 197 (2020), 106852. |
| [29] | Zhao, X., Liang, J., and Dang, C., A stratified sampling based clustering algorithm for large-scale data, Knowledge-Based Syst., 163 (2019), pp. 416-428. |
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.
