Geodesic
A note on the convergence rate in regularized stochastic programming
Kybernetika, Tome 57 (2021) no. 1, pp. 38-45
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2021-1-0038
Classification : 90C15
Keywords: stochastic programming problem; Tikhonov's regularization; Lipschitz conditions; Kantorovich metric; convergence rate 
@article{10_14736_kyb_2021_1_0038,
     author = {Gordienko, Evgueni and Gryazin, Yury},
     title = {A note on the convergence rate in regularized stochastic programming},
     journal = {Kybernetika},
     pages = {38--45},
     year = {2021},
     volume = {57},
     number = {1},
     doi = {10.14736/kyb-2021-1-0038},
     mrnumber = {4231855},
     zbl = {07396254},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-1-0038/}
}
TY  - JOUR
AU  - Gordienko, Evgueni
AU  - Gryazin, Yury
TI  - A note on the convergence rate in regularized stochastic programming
JO  - Kybernetika
PY  - 2021
SP  - 38
EP  - 45
VL  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-1-0038/
DO  - 10.14736/kyb-2021-1-0038
LA  - en
ID  - 10_14736_kyb_2021_1_0038
ER  - 
%0 Journal Article
%A Gordienko, Evgueni
%A Gryazin, Yury
%T A note on the convergence rate in regularized stochastic programming
%J Kybernetika
%D 2021
%P 38-45
%V 57
%N 1
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-1-0038/
%R 10.14736/kyb-2021-1-0038
%G en
%F 10_14736_kyb_2021_1_0038
Gordienko, Evgueni; Gryazin, Yury. A note on the convergence rate in regularized stochastic programming. Kybernetika, Tome 57 (2021) no. 1, pp. 38-45. doi: 10.14736/kyb-2021-1-0038

[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. | DOI | MR

[2] Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition. Springer, New York 1996. | DOI | MR

[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. | DOI | MR

[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. | DOI | MR

[5] Gordienko, E.: A remark on stability in prediction and filtering problems. Izv. Akad. Nank SSR Tekhn. Kibernet. 3 (1978), 202-205. | MR

[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. | DOI | MR

[7] Kaňková, V.: An approximative solution of stochastic optimization problem. In: Trans. 8th Prague Conf. Academia, Prague 1978, pp. 349-353. | DOI | MR

[8] Kaňková, V.: Empirical estimates in stochastic programming via distribution tails. Kybernetika 46 (2010), 459-471. | MR

[9] Kaňková, V., Houda, M.: Thin and heavy tails in stochastic programming. Kybernetika 51 (2015), 433-456. | DOI | MR

[10] Rachev, S. T., Römisch, W.: Quantitative stability and stochastic programming: the method of probabilistic metrics. Math. Oper. Res. 27 (2002), 792-818. | DOI | MR

[11] Shafieezadeh-Abadeh, S., Esfahani, P. M.: Regularization via mass transportation. J. Machine Learning Res. 20 (2019), 1-68. | MR

[12] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constrains, modeling and sample average approximation. Optimization 57 (2008), 395-418. | DOI | MR

[13] Tikhonov, A. N., Arsenin, V. Y.: Solutions of Ill-posed Problems. Winston and Sons, Washington DC 1977. | MR

[14] Vapnik, V. N.: Statistical Learning Theory. Wiley and Sons, New York 1998. | MR

[15] Vapnik, V., Izmailov, R.: Synergy of monotonic rules. J. Machine Learning Res. 17 (2016), 988-999. | MR

Cité par Sources :