1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 514, № 2, 2023

Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 99-108

МЕТОДЫ, ИСПОЛЬЗУЮЩИЕ ГРАДИЕНТНЫЙ КЛИППИНГ, ДЛЯ ЗАДАЧ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ С ТЯЖЕЛЫМ ШУМОМ

М. Ю. Данилова 1, *

1 Московский физико-технический институт
Москва, Россия

* E-mail: danilovamarina15@gmail.com

Поступила в редакцию 02.09.2023
После доработки 08.10.2023
Принята к публикации 15.10.2023

Аннотация

Эта статья представляет собой обзор результатов ряда исследований [Gorbunov et al., 2020, 2021, 2022, Sadiev et al., 2023], в которых постепенно устранялись открытые вопросы, связанные с анализом сходимости с большой вероятностью стохастических методов оптимизации первого порядка при слабых предположениях о шуме. В начале мы представим концепцию градиентного клиппинга, которая играет ключевую роль в развитии стохастических методов для успешной работы в случае распределений с тяжелыми хвостами. Далее мы рассмотрим важность получения оценок сходимости методов в вероятностном контексте и их взаимосвязь с оценками сходимости по математическому ожиданию. Заключительные разделы статьи посвящены основным результатам в области задач минимизации и результатам численных экспериментов.

Ключевые слова: выпуклая оптимизация, стохастическая оптимизация, методы первого порядка

Список литературы

  1. Bennett G. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association. 1962. V. 57 (297). P. 33–45.

  2. Cutkosky A., Mehta H. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems. 2021. V. 34.

  3. Davis D., Drusvyatskiy D., Xiao L., Zhang J. From low probability to high confidence in stochastic convex optimization. Journal of Machine Learning Research. 2021. V. 22 (49). P. 1–38.

  4. Devolder O. et al. Stochastic first order methods in smooth convex optimization. Technical report, CORE, 2011.

  5. Dzhaparidze K., Van Zanten J. On bernstein-type inequalities for martingales. Stochastic processes and their applications. 2001. V. 93 (1). P. 109–117.

  6. Freedman D.A. et al. On tail probabilities for martingales. the Annals of Probability. 1975. V. 3 (1). P. 100–118.

  7. Gasnikov A., Nesterov Y. Universal fast gradient method for stochastic composit optimization problems. arXiv preprint arXiv:1604.05275, 2016.

  8. Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization. 2012. V. 22 (2). P. 1469–1492.

  9. Ghadimi S., Lan G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization. 2013. V. 23 (2). P. 2341–2368.

  10. Gidel G., Berard H., Vignoud G., Vincent P., Lacoste-Julien S. A variational inequality perspective on generative adversarial networks. International Conference on Learning Representations, 2019.

  11. Goodfellow I., Pouget-Abadie J., Mirza M., Xu B., Warde-Farley D., Ozair S., Courville A., Bengio Y. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.

  12. Gorbunov E., Danilova M., Gasnikov A. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems. 2020. V. 33. P. 15042–15053.

  13. Gorbunov E., Danilova M., Shibaev I., Dvurechensky P., Gasnikov A. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.05958, 2021.

  14. Gorbunov E., Danilova M., Dobre D., Dvurechenskii P., Gasnikov A., Gidel G. Clipped stochastic methods for variational inequalities with heavy-tailed noise. Advances in Neural Information Processing Systems. 2022. V. 35. P. 31319–31332.

  15. Harker P.T., Pang J.-S. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming. 1990. V. 48 (1-3). P. 161–220.

  16. Kingma D.P., Ba J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

  17. Liu Z., Zhou Z. Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprint arXiv:2303.12277, 2023.

  18. Liu Z., Nguyen T.D., Nguyen T.H., Ene A., Nguyen H. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, PMLR, 2023. P. 21884–21914.

  19. Merity S., Keskar N.S., Socher R. Regularizing and optimizing lstm language models. In International Conference on Learning Representations, 2018.

  20. Mosbach M., Andriushchenko M., Klakow D. On the stability of fine-tuning bert: Misconceptions, explanations, and strong baselines. In International Conference on Learning Representations, 2020.

  21. Nazin V., Nemirovsky A., Tsybakov A.B., Juditsky A. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control. 2019. V. 80 (7). P. 1607–1627.

  22. Nguyen T.D., Nguyen T.H., Ene A., Nguyen H.L. High probability convergence of clipped-sgd under heavy-tailed noise. arXiv preprint arXiv:2302.05437, 2023.

  23. Pascanu R., Mikolov T., Bengio Y. On the difficulty of training recurrent neural networks. In International conference on machine learning, Pmlr, 2013. P. 1310–1318.

  24. Peters M.E., Ammar W., Bhagavatula C., Power R. Semi-supervised sequence tagging with bidirectional language models. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2017. P. 1756–1765.

  25. Ryu E.K., Yin W. Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, 2022.

  26. Sadiev A., Danilova M., Gorbunov E., Horv’ath S., Gidel G., Dvurechensky P., Gasnikov A., Richt’arik P. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023. P. 29563–29648.

  27. Zhang J., Karimireddy S.P., Veit A., Kim S., Reddi S., Kumar S., Sra S. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems. 2020. V. 33. P. 15383–15393.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал