ИССЛЕДОВАНИЕ ГРАДИЕНТНОГО МЕТОДА С НЕТОЧНОЙ ИНФОРМАЦИЕЙ О ГРАДИЕНТЕ НА НЕКОТОРЫХ КЛАССАХ (L0, L1)-ГЛАДКИХ НЕВЫПУКЛЫХ ЗАДАЧ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Работа посвящена исследованию градиентного метода на классе (L0, L1)-гладких функций при условии, что на итерациях метода вместо точных значений градиента доступны лишь его приближенные значения, что соответствует ситуациям, возникающим при использовании зашумленных данных. Рассмотрено два класса задач: первый – квазивыпуклые функции относительно всякого решения, удовлетворяющие условию градиентного доминирования Поляка-Лоясиевича, второй – квазивыпуклые функции без требования выполнения условия Поляка-Лоясиевича, но с дополнительным ограничением на параметр квазивыпуклости. Для квазивыпуклых функций с PL-условием доказан результат о близкой к линейной скорости сходимости метода в окрестность точного решения. Если значения неточного градиента достаточно малы (что достигается за конечное число итераций), то метод сходится с близкой к линейной скоростью на классе задач с условием Поляка-Лоясиевича без дополнительного предположения о квазивыпуклости. Для (0, M)-гладких квазивыпуклых функций предложен адаптивный градиентный метод и получена оценка его скорости сходимости. Показано, что в случае использования точных значений градиента метод сходится с линейной скоростью.

Об авторах

С. С АБЛАЕВ

Крымский федеральный университет им. В.И. Вернадского, Симферополь; Московский физико-технический институт (национальный исследовательский университет)

Email: seydamet.ablaev@yandex.ru
канд. физ.-мат. наук Симферополь, Россия; Долгопрудный, Россия

Ф. С СТОНЯКИН

Московский физико-технический институт (национальный исследовательский университет); Крымский федеральный университет им. В.И. Вернадского, Симферополь

Email: fedyor@mail.ru
д-р физ.-мат. наук Долгопрудный, Россия; Симферополь, Россия

М. Н ФЕДОТОВ

Национальный исследовательский университет «Высшая школа экономики», Москва

Email: MaximFd-Nk@yandex.ru
Москва, Россия

М. С АЛКУСА

Университет Иннополис

Email: m.alkousa@innopolis.ru
канд. физ.-мат. наук Иннополис, Россия

О. С САВЧУК

Крымский федеральный университет имени В.И. Вернадского, Симферополь; Адыгейский государственный университет, Майкоп

Email: oleg.savchuk19@mail.ru
Симферополь, Россия; Майкоп, Россия

А. В ГАСНИКОВ

Университет Иннополис, Долгопрудный; Московский физико-технический институт (национальный исследовательский университет)

Email: gasnikov@yandex.ru
д-р физ.-мат. наук Иннополис, Россия; Долгопрудный, Россия

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

  1. Zhang J., He T., Sra S., Jadbabaie A. Why gradient clipping accelerates training: A theoretical justification for adaptivity // International Conference on Learning Representations. 2020. P. 1–14.
  2. Schmidt M., Le Roux N., Bach F. Minimizing finite sums with the stochastic average gradient // Mathematical Programming. 2017. V. 162. P. 83–112.
  3. Johnson R., Zhang T. Accelerating stochastic gradient descent using predictive variance reduction // Advances in neural information processing systems. 2013. No. 26. P. 315–323.
  4. Defazio A., Bach F., Lacoste-Julien S. SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives // Advances in neural information processing systems. 2014. No. 2. P. 1646–1654.
  5. Nguyen L., Liu J., Scheinberg K., Takaˇc M. Sarah: A novel method for machine learning problems using stochastic recursive gradient // 34th International Conference on Machine Learning (ICML). 2014. V. 6. P. 4009–4023.
  6. Nguyen L., Scheinberg K., Takaˇc M. Inexact sarah algorithm for stochastic optimization // Optimization Methods and Software. 2021. V. 36. No. 1. P. 237–258.
  7. Beznosikov A. Takaˇc M. Random-reshuffled SARAH does not need full gradient computations // Optim Lett. 2024. V. 18. P. 727–749.
  8. Shi Z., Sadiev A., Loizou N., et al. Ai-sarah: Adaptive and implicit stochastic recursive gradient methods // Transactions on Machine Learning Research. 2023. P. 1–40.
  9. Defazio A., Bottou L. On the ineffectiveness of variance reduced optimization for deep learning // Advances in Neural Information Processing Systems. 2019. V. 32. P. 1753–1763.
  10. Zhang B., Jin J., Fang C., Wang L. Improved Analysis of Clipping Algorithms for Non-convex Optimization // Advances in Neural Information Processing Systems. 2020. V. 19. P. 15511–15522.
  11. Chen Z., Zhou Y., Liang Y., Lu Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization // International Conference on Machine Learning (PMLR). 2023. P. 5396–5427.
  12. Zhao S.-Y., Xie Y.-P., Li W.-J. On the convergence and improvement of stochastic normalized gradient descent // Science China Information Sciences. 2021. V. 64. P. 1–13.
  13. Faw M., Rout L., Caramanis C., Shakkottai S. Beyond uniform smoothness: A stopped analysis of adaptive sgd // The Thirty Sixth Annual Conference on Learning Theory (PMLR). 2023. P. 89–160.
  14. Wang B., Zhang H., Ma Z., Chen W. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions // The Thirty Sixth Annual Conference on Learning Theory (PMLR). 2023. P. 161–190.
  15. Li H., Rakhlin A., Jadbabaie A. Convergence of adam under relaxed assumptions // Advances in Neural Information Processing Systems. 2024. P. 1792–1804.
  16. Hubler F., Yang J., Li X., He N. Parameter-agnostic optimization under relaxed smoothness // International Conference on Artificial Intelligence and Statistics (PMLR). 2024. P. 4861–4869.
  17. Pascanu R., Mikolov T., Bengio Y. On the difficulty of training recurrent neural networks // International Conference on Machine Learning. 2013. V. 28. P. 1310– 1318.
  18. Polyak B. Introduction to Optimization // Optimization Software. 1987. 438 p.
  19. Koloskova A., Hendrikx H., Stich S. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees // International Conference on Machine Learning. 2023. P. 17343–17363.
  20. Takezawa Y., Bao H., Sato R. et al. Polyak meets parameter-free clipped gradient descent // 2024. arXiv:2405.15010
  21. Li H., Qian J., Tian Y., Rakhlin A., Jadbabaie A. Convex and non-convex optimization under generalized smoothness // Advances in Neural Information Processing Systems. 2024. V. 36. P. 2675–2686.
  22. Gorbunov E., Tupitsa N., Choudhury S., et al. Methods for Convex (L0, L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity // 2024. arXiv:2409.14989
  23. Vankov D., Rodomanov A., Nedich A., et al. Optimizing (L0, L1)-Smooth Functions by Gradient Methods // 2024. arXiv:2410.10800
  24. Lobanov A., Gasnikov A., Gorbunov E., Tak´aˇc M. Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L0, L1)-Smoothness // 2024. arXiv:2412.17050
  25. Stonyakin F., Kuruzov I., Polyak B. Stopping Rules for Gradient Methods for Nonconvex Problems with Additive Noise in Gradient // Journal of Optimization Theory and Applications. 2022. V. 198. P. 531–551.
  26. Wang J., Wibisono A. Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization // 2023. 10.48550/arXiv.2302.07851
  27. Hermant J., Aujol J.F., Dossal C., Rondepierre A. Study of the behaviour of Nesterov accelerated gradient in a non convex setting: the strongly quasar convex case // 2024. arXiv:2405.19809
  28. Hinder O., Sidford A., Sohoni N. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond // 2019. arXiv.1906.11985.
  29. Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximalgradient methods under the Polyak–Lojasiewicz condition // Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 2016. P. 795–811.
  30. Stonyakin F., Tyurin A., Gasnikov A., et al. Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model // 2024. arXiv preprint arXiv:2402.06319.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025