- Код статьи
- S24139777S0005231025090015-1
- DOI
- 10.7868/S2413977725090015
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 9
- Страницы
- 3-27
- Аннотация
- Работа посвящена исследованию градиентного метода на классе (L, L)-гладких функций при условии, что на итерациях метода вместо точных значений градиента доступны лишь его приближенные значения, что соответствует ситуациям, возникающим при использовании зашумленных данных. Рассмотрено два класса задач: первый – квазивыпуклые функции относительно всякого решения, удовлетворяющие условию градиентного доминирования Поляка-Лоясиевича, второй – квазивыпуклые функции без требования выполнения условия Поляка-Лоясиевича, но с дополнительным ограничением на параметр квазивыпуклости. Для квазивыпуклых функций с PL-условием доказан результат о близкой к линейной скорости сходимости метода в окрестность точного решения. Если значения неточного градиента достаточно малы (что достигается за конечное число итераций), то метод сходится с близкой к линейной скоростью на классе задач с условием Поляка-Лоясиевича без дополнительного предположения о квазивыпуклости. Для (0, M)-гладких квазивыпуклых функций предложен адаптивный градиентный метод и получена оценка его скорости сходимости. Показано, что в случае использования точных значений градиента метод сходится с линейной скоростью.
- Ключевые слова
- градиентный метод Δ-неточный градиент (L, L)-гладкая функция ρ-квазивыпуклая функция условие Поляка-Лоясиевича логистическая регрессия
- Дата публикации
- 24.02.2026
- Год выхода
- 2026
- Всего подписок
- 0
- Всего просмотров
- 3
Библиография
- 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.
