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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».