On Monte-Carlo methods in convex stochastic optimization. (English) Zbl 1502.90114
Summary: We develop a novel procedure for estimating the optimizer of general convex stochastic optimization problems of the form \(\min_{x\in \mathcal{X}}\mathbb{E}[F(x,\xi)]\), when the given data is a finite independent sample selected according to \(\xi\). The procedure is based on a median-of-means tournament, and is the first procedure that exhibits the optimal statistical performance in heavy tailed situations: we recover the asymptotic rates dictated by the central limit theorem in a nonasymptotic manner once the sample size exceeds some explicitly computable threshold. Additionally, our results apply in the high-dimensional setup, as the threshold sample size exhibits the optimal dependence on the dimension (up to a logarithmic factor). The general setting allows us to recover recent results on multivariate mean estimation and linear regression in heavy-tailed situations and to prove the first sharp, nonasymptotic results for the portfolio optimization problem.
MSC:
| 90C15 | Stochastic programming |
| 90C25 | Convex programming |
| 90B50 | Management decision making, including multiple objectives |
| 62J02 | General nonlinear regression |
Keywords:
finite sample/nonasymptotic concentration inequality; sample-path optimization; stochastic counterpart method; stochastic optimizationReferences:
| [1] | Adamczak, R., Litvak, A. E., Pajor, A. and Tomczak-Jaegermann, N. (2010). Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles. J. Amer. Math. Soc. 23 535-561. · Zbl 1206.60006 · doi:10.1090/S0894-0347-09-00650-X |
| [2] | BANHOLZER, D., FLIEGE, J. and WERNER, R. (2022). On rates of convergence for sample average approximations in the almost sure sense and in mean. Math. Program. 191 307-345. · Zbl 1489.90073 · doi:10.1007/s10107-019-01400-4 |
| [3] | BARTL, D. and TANGPI, L. (2020). Non-asymptotic rates for the estimation of risk measures. Preprint. Available at arXiv:2003.10479. · Zbl 1459.60156 |
| [4] | BERTSIMAS, D., GUPTA, V. and KALLUS, N. (2018). Robust sample average approximation. Math. Program. 171 217-282. · Zbl 1432.90168 · doi:10.1007/s10107-017-1174-z |
| [5] | Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press, Oxford. · Zbl 1337.60003 · doi:10.1093/acprof:oso/9780199535255.001.0001 |
| [6] | CHERAPANAMJERI, Y., FLAMMARION, N. and BARTLETT, P. (2019). Fast mean estimation with sub-Gaussian rates. In Conference on Learning Theory, PMLR 786-806. |
| [7] | FÖLLMER, H. and SCHIED, A. (2011). Stochastic Finance: An Introduction in Discrete Time. de Gruyter, Berlin. · Zbl 1213.91006 · doi:10.1515/9783110218053 |
| [8] | GHODRATI, H. and ZAHIRI, Z. (2014). A Monte Carlo simulation technique to determine the optimal portfolio. Manag. Sci. Lett. 4 465-474. |
| [9] | GUIGUES, V. (2017). Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures. Math. Program. 163 169-212. · Zbl 1380.90200 · doi:10.1007/s10107-016-1060-0 |
| [10] | GUIGUES, V., JUDITSKY, A. and NEMIROVSKI, A. (2017). Non-asymptotic confidence bounds for the optimal value of a stochastic program. Optim. Methods Softw. 32 1033-1058. · Zbl 1386.90091 · doi:10.1080/10556788.2017.1350177 |
| [11] | GUIGUES, V., KRÄTSCHMER, V. and SHAPIRO, A. (2018). A central limit theorem and hypotheses testing for risk-averse stochastic programs. SIAM J. Optim. 28 1337-1366. · Zbl 1422.90032 · doi:10.1137/16M1104639 |
| [12] | HOMEM-DE-MELLO, T. and BAYRAKSAN, G. (2014). Monte Carlo sampling-based methods for stochastic optimization. Surv. Oper. Res. Manag. Sci. 19 56-85. · doi:10.1016/j.sorms.2014.05.001 |
| [13] | HOPKINS, S. B. (2020). Mean estimation with sub-Gaussian rates in polynomial time. Ann. Statist. 48 1193-1213. · Zbl 1454.62162 · doi:10.1214/19-AOS1843 |
| [14] | KIM, S., PASUPATHY, R. and HENDERSON, S. G. (2015). A guide to sample average approximation. In Handbook of Simulation Optimization 207-243. Springer, New York. |
| [15] | KLEYWEGT, A. J., SHAPIRO, A. and HOMEM-DE-MELLO, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12 479-502. · Zbl 0991.90090 · doi:10.1137/S1052623499363220 |
| [16] | KOLTCHINSKII, V. and MENDELSON, S. (2015). Bounding the smallest singular value of a random matrix without concentration. Int. Math. Res. Not. IMRN 2015 12991-13008. · Zbl 1331.15027 · doi:10.1093/imrn/rnv096 |
| [17] | LAN, G., NEMIROVSKI, A. and SHAPIRO, A. (2012). Validation analysis of mirror descent stochastic approximation method. Math. Program. 134 425-458. · Zbl 1273.90154 · doi:10.1007/s10107-011-0442-6 |
| [18] | Lecué, G. and Mendelson, S. (2018). Regularization and the small-ball method I: Sparse recovery. Ann. Statist. 46 611-641. · Zbl 1403.60085 · doi:10.1214/17-AOS1562 |
| [19] | LEDOUX, M. and TALAGRAND, M. (2013). Probability in Banach Spaces: Isoperimetry and Processes. Classics in Mathematics. Springer, Berlin. |
| [20] | LUGOSI, G. and MENDELSON, S. (2019). Mean estimation and regression under heavy-tailed distributions: A survey. Found. Comput. Math. 19 1145-1190. · Zbl 1431.62123 · doi:10.1007/s10208-019-09427-x |
| [21] | LUGOSI, G. and MENDELSON, S. (2019). Near-optimal mean estimators with respect to general norms. Probab. Theory Related Fields 175 957-973. · Zbl 1431.62234 · doi:10.1007/s00440-019-00906-4 |
| [22] | LUGOSI, G. and MENDELSON, S. (2019). Sub-Gaussian estimators of the mean of a random vector. Ann. Statist. 47 783-794. · Zbl 1417.62192 · doi:10.1214/17-AOS1639 |
| [23] | LUGOSI, G. and MENDELSON, S. (2020). Risk minimization by median-of-means tournaments. J. Eur. Math. Soc. (JEMS) 22 925-965. · Zbl 1436.62312 · doi:10.4171/jems/937 |
| [24] | MARKOWITZ, H. (1952). Portfolio selection. J. Finance 7 77-91. |
| [25] | MENDELSON, S. (2014). Learning without concentration. In Conference on Learning Theory 25-39. · Zbl 1333.68232 |
| [26] | MENDELSON, S. (2017). On aggregation for heavy-tailed classes. Probab. Theory Related Fields 168 641-674. · Zbl 1371.62032 · doi:10.1007/s00440-016-0720-6 |
| [27] | MENDELSON, S. (2019). An unrestricted learning procedure. J. ACM 66 Art. 42, 42 pp. · Zbl 1473.68156 · doi:10.1145/3361699 |
| [28] | MENDELSON, S. (2020). On the geometry of random polytopes. In Geometric Aspects of Functional Analysis. Vol. II. Lecture Notes in Math. 2266 187-198. Springer, Cham. · Zbl 1454.60015 · doi:10.1007/978-3-030-46762-3_8 |
| [29] | MENDELSON, S. (2021). Extending the scope of the small-ball method. Studia Math. 256 147-167. · Zbl 1468.60064 · doi:10.4064/sm190420-21-11 |
| [30] | NEMIROVSKY, A. S. and YUDIN, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York. · Zbl 0501.90062 |
| [31] | OLIVEIRA, R. I. and THOMPSON, P. (2017). Sample average approximation with heavier tails I: Non-asymptotic bounds with weak assumptions and stochastic constraints. Preprint. Available at arXiv:1705.00822. |
| [32] | OLIVEIRA, R. I. and THOMPSON, P. (2017). Sample average approximation with heavier tails II: Localization in stochastic convex optimization and persistence results for the Lasso. Preprint. Available at arXiv:1711.04734. |
| [33] | PFLUG, G. C. (1999). Stochastic programs and statistical data. Ann. Oper. Res. 85 59-78. · Zbl 0919.90118 · doi:10.1023/A:1018982129937 |
| [34] | PFLUG, G. C. (2003). Stochastic optimization and statistical inference. In Stochastic Programming. Handbooks Oper. Res. Management Sci. 10 427-482. Elsevier, Amsterdam. · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10007-2 |
| [35] | RÖMISCH, W. (2003). Stability of stochastic programming problems. In Stochastic Programming. Handbooks Oper. Res. Management Sci. 10 483-554. Elsevier, Amsterdam. · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10008-4 |
| [36] | Rudelson, M. (1999). Random vectors in the isotropic position. J. Funct. Anal. 164 60-72. · Zbl 0929.46021 · doi:10.1006/jfan.1998.3384 |
| [37] | SHAPIRO, A. (2003). Monte Carlo sampling methods. In Stochastic Programming. Handbooks Oper. Res. Management Sci. 10 353-425. Elsevier, Amsterdam. · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10006-0 |
| [38] | SHAPIRO, A., DENTCHEVA, D. and RUSZCZYŃSKI, A. (2014). Lectures on Stochastic Programming: Modeling and Theory, 2nd ed. MOS-SIAM Series on Optimization 9. SIAM, Philadelphia. · Zbl 1302.90003 |
| [39] | Srivastava, N. and Vershynin, R. (2013). Covariance estimation for distributions with \[2+\varepsilon\] moments. Ann. Probab. 41 3081-3111. · Zbl 1293.62121 · doi:10.1214/12-AOP760 |
| [40] | TALAGRAND, M. (1994). Sharper bounds for Gaussian and empirical processes. Ann. Probab. 22 28-76. · Zbl 0798.60051 |
| [41] | Talagrand, M. (2014). Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Ergebnisse der Mathematik und Ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics] 60. Springer, Heidelberg. · Zbl 1293.60001 · doi:10.1007/978-3-642-54075-2 |
| [42] | TIKHOMIROV, K. (2018). Sample covariance matrices of heavy-tailed distributions. Int. Math. Res. Not. IMRN 2018 6254-6289. · Zbl 1462.62330 · doi:10.1093/imrn/rnx067 |
| [43] | TROPP, J. A. (2016). The expected norm of a sum of independent random matrices: An elementary approach. In High Dimensional Probability VII. Progress in Probability 71 173-202. Springer, Cham. · Zbl 1382.60016 · doi:10.1007/978-3-319-40519-3_8 |
| [44] | VOGEL, S. (2008). Universal confidence sets for solutions of optimization problems. SIAM J. Optim. 19 1467-1488. · Zbl 1198.90310 · doi:10.1137/070680023 |
| [45] | WANG, Q. and SUN, H. (2018). Sparse Markowitz portfolio selection by using stochastic linear complementarity approach. J. Ind. Manag. Optim. 14 541-559. · Zbl 1412.90098 · doi:10.3934/jimo.2017059 |
| [46] | WEBER, S. (2007). Distribution-invariant risk measures, entropy, and large deviations. J. Appl. Probab. 44 16-40. · Zbl 1214.91059 · doi:10.1239/jap/1175267161 |
| [47] | XU, H. and ZHANG, D. (2012). Monte Carlo methods for mean-risk optimization and portfolio selection. Comput. Manag. Sci. 9 3-29. · Zbl 1273.91459 · doi:10.1007/s10287-010-0123-6 |
| [48] | YASKOV, P. (2015). Sharp lower bounds on the least singular value of a random matrix without the fourth moment condition. Electron. Commun. Probab. 20 no. 44, 9 pp · Zbl 1318.60009 · doi:10.1214/ECP.v20-4089 |
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.
