| Title:
|
A note on the convergence rate in regularized stochastic programming (English) |
| Author:
|
Gordienko, Evgueni |
| Author:
|
Gryazin, Yury |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
57 |
| Issue:
|
1 |
| Year:
|
2021 |
| Pages:
|
38-45 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We deal with a stochastic programming problem that can be inconsistent. To overcome the inconsistency we apply Tikhonov's regularization technique, and, using recent results on the convergence rate of empirical measures in Wasserstein metric, we treat the following two related problems: 1. A choice of regularization parameters that guarantees the convergence of the minimization procedure. 2. Estimation of the rate of convergence in probability. Considering both light and heavy tail distributions and Lipschitz objective functions (which can be unbounded), we obtain the power bounds for the convergence rate. (English) |
| Keyword:
|
stochastic programming problem |
| Keyword:
|
Tikhonov's regularization |
| Keyword:
|
Lipschitz conditions |
| Keyword:
|
Kantorovich metric |
| Keyword:
|
convergence rate |
| MSC:
|
90C15 |
| idZBL:
|
Zbl 07396254 |
| idMR:
|
MR4231855 |
| DOI:
|
10.14736/kyb-2021-1-0038 |
| . |
| Date available:
|
2021-07-30T12:46:36Z |
| Last updated:
|
2021-11-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149025 |
| . |
| Reference:
|
[1] Boissard, E., Gouic, T. Le: On the mean speed of convergence of empirical and occupation measures in Wasserstein distance..Annales de l'Institut Henry Poincaré, Probabilités et Statistiques 50 (2014), 539-563. MR 3189084, |
| Reference:
|
[2] Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition..Springer, New York 1996. MR 1383093, |
| Reference:
|
[3] Evgeniou, T., Poggio, T., Pontil, M., Verri, A.: Regularization and statistical learning theory for data analysis..Comput. Statist. Data Anal. 38 (2002), 421-432. MR 1884873, |
| Reference:
|
[4] Fournier, N., Guillin, A.: On the rate of convergence in Wasserstein distance of the empirical measure..Probab. Theory Related Fields 162 (2015), 707-738. MR 3383341, |
| Reference:
|
[5] Gordienko, E.: A remark on stability in prediction and filtering problems..Izv. Akad. Nank SSR Tekhn. Kibernet. 3 (1978), 202-205. MR 0536708 |
| Reference:
|
[6] Gryazin, Y. A., Klibanov, M. V., Lucas, T. R.: Numerical solution of a subsurface imaging inverse problem..SIAM J. Appl. Math. 62 (2001), 664-683. MR 1870710, |
| Reference:
|
[7] Kaňková, V.: An approximative solution of stochastic optimization problem..In: Trans. 8th Prague Conf. Academia, Prague 1978, pp. 349-353. MR 0536792, |
| Reference:
|
[8] Kaňková, V.: Empirical estimates in stochastic programming via distribution tails..Kybernetika 46 (2010), 459-471. MR 2676083 |
| Reference:
|
[9] Kaňková, V., Houda, M.: Thin and heavy tails in stochastic programming..Kybernetika 51 (2015), 433-456. MR 3391678, |
| Reference:
|
[10] Rachev, S. T., Römisch, W.: Quantitative stability and stochastic programming: the method of probabilistic metrics..Math. Oper. Res. 27 (2002), 792-818. MR 1939178, |
| Reference:
|
[11] Shafieezadeh-Abadeh, S., Esfahani, P. M.: Regularization via mass transportation..J. Machine Learning Res. 20 (2019), 1-68. MR 3990457 |
| Reference:
|
[12] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constrains, modeling and sample average approximation..Optimization 57 (2008), 395-418. MR 2412074, |
| Reference:
|
[13] Tikhonov, A. N., Arsenin, V. Y.: Solutions of Ill-posed Problems..Winston and Sons, Washington DC 1977. MR 0455365 |
| Reference:
|
[14] Vapnik, V. N.: Statistical Learning Theory..Wiley and Sons, New York 1998. MR 1641250 |
| Reference:
|
[15] Vapnik, V., Izmailov, R.: Synergy of monotonic rules..J. Machine Learning Res. 17 (2016), 988-999. MR 3555027 |
| . |
