ISSLEDOVANIE GRADIENTNOGO METODA S NETOChNOY INFORMATsIEY O GRADIENTE NA NEKOTORYKh KLASSAKh (L0, L1)-GLADKIKh NEVYPUKLYKh ZADACh

Мұқаба
  • Авторлар: ABLAEV S.S1,2, STONYaKIN F.S2,1, FEDOTOV M.N3, ALKUSA M.S4, SAVChUK O.S5,6, GASNIKOV A.V7,2
  • Мекемелер:
    1. Крымский федеральный университет им. В.И. Вернадского, Симферополь
    2. Московский физико-технический институт (национальный исследовательский университет)
    3. Национальный исследовательский университет «Высшая школа экономики», Москва
    4. Университет Иннополис
    5. Крымский федеральный университет имени В.И. Вернадского, Симферополь
    6. Адыгейский государственный университет, Майкоп
    7. Университет Иннополис, Долгопрудный
  • Шығарылым: № 9 (2025)
  • Беттер: 3-27
  • Бөлім: Topical issue
  • URL: https://kazanmedjournal.ru/0005-2310/article/view/691176
  • DOI: https://doi.org/10.31857/S0005231025090015
  • EDN: https://elibrary.ru/VMPJNF
  • ID: 691176

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

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

Авторлар туралы

S. ABLAEV

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

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

F. STONYaKIN

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

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

M. FEDOTOV

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

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

M. ALKUSA

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

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

O. SAVChUK

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

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

A. GASNIKOV

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

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
Жүктеу

© Russian Academy of Sciences, 2025