A note on the convergence rate in regularized stochastic programming

Evgueni I. Gordienko; Yury Gryazin

Kybernetika (2021)

  • Issue: 1, page 38-45
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Gordienko, Evgueni I., and Gryazin, Yury. "A note on the convergence rate in regularized stochastic programming." Kybernetika (2021): 38-45. <http://eudml.org/doc/297669>.

@article{Gordienko2021,
abstract = {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.},
author = {Gordienko, Evgueni I., Gryazin, Yury},
journal = {Kybernetika},
keywords = {stochastic programming problem; Tikhonov's regularization; Lipschitz conditions; Kantorovich metric; convergence rate},
language = {eng},
number = {1},
pages = {38-45},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A note on the convergence rate in regularized stochastic programming},
url = {http://eudml.org/doc/297669},
year = {2021},
}

TY - JOUR
AU - Gordienko, Evgueni I.
AU - Gryazin, Yury
TI - A note on the convergence rate in regularized stochastic programming
JO - Kybernetika
PY - 2021
PB - Institute of Information Theory and Automation AS CR
IS - 1
SP - 38
EP - 45
AB - 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.
LA - eng
KW - stochastic programming problem; Tikhonov's regularization; Lipschitz conditions; Kantorovich metric; convergence rate
UR - http://eudml.org/doc/297669
ER -

References

top
  1. Boissard, E., Gouic, T. Le, , Annales de l'Institut Henry Poincaré, Probabilités et Statistiques 50 (2014), 539-563. MR3189084DOI
  2. Devroye, L., Györfi, L., Lugosi, G., , Springer, New York 1996. MR1383093DOI
  3. Evgeniou, T., Poggio, T., Pontil, M., Verri, A., , Comput. Statist. Data Anal. 38 (2002), 421-432. MR1884873DOI
  4. Fournier, N., Guillin, A., , Probab. Theory Related Fields 162 (2015), 707-738. MR3383341DOI
  5. Gordienko, E., A remark on stability in prediction and filtering problems., Izv. Akad. Nank SSR Tekhn. Kibernet. 3 (1978), 202-205. MR0536708
  6. Gryazin, Y. A., Klibanov, M. V., Lucas, T. R., , SIAM J. Appl. Math. 62 (2001), 664-683. MR1870710DOI
  7. Kaňková, V., , In: Trans. 8th Prague Conf. Academia, Prague 1978, pp. 349-353. MR0536792DOI
  8. Kaňková, V., Empirical estimates in stochastic programming via distribution tails., Kybernetika 46 (2010), 459-471. MR2676083
  9. Kaňková, V., Houda, M., , Kybernetika 51 (2015), 433-456. MR3391678DOI
  10. Rachev, S. T., Römisch, W., , Math. Oper. Res. 27 (2002), 792-818. MR1939178DOI
  11. Shafieezadeh-Abadeh, S., Esfahani, P. M., Regularization via mass transportation., J. Machine Learning Res. 20 (2019), 1-68. MR3990457
  12. Shapiro, A., Xu, H., , Optimization 57 (2008), 395-418. MR2412074DOI
  13. Tikhonov, A. N., Arsenin, V. Y., Solutions of Ill-posed Problems., Winston and Sons, Washington DC 1977. MR0455365
  14. Vapnik, V. N., Statistical Learning Theory., Wiley and Sons, New York 1998. MR1641250
  15. Vapnik, V., Izmailov, R., Synergy of monotonic rules., J. Machine Learning Res. 17 (2016), 988-999. MR3555027

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.