Градиентные методы для минимизационных задач с условием Поляка - Лоясиевича: относительная погрешность градиента и адаптивный подбор параметров
Автор: Пучинин С.М., Стонякин Ф.С.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (61) т.16, 2024 года.
Бесплатный доступ
Рассматривается класс задач минимизации функций с условиями Липшица градиента и Поляка - Лоясиевича (градиентного доминирования). Оптимизационные задачи с условием Поляка - Лоясиевича актуальны, поскольку встречаются в самых разных важных приложениях, включая нелинейные системы с параметризацией в глубоком обучении. Естественно, возможна ситуация наличия погрешностей доступной методу информации, и возникает вопрос исследования влияния таких погрешностей на качество выдаваемого методом решения. В работе исследуется постановка задачи минимизации в предположении доступности во всякой текущей точке градиента целевой функции с относительной погрешностью. Предлагаются адаптивные (самонастраивающиеся) методы градиентного типа. Если в первом из них адаптивность подбора размеров шагов реализована только по параметру гладкости целевой функции, то во втором методе - ещё и по величине, связанной с относительной погрешностью градиента. Для каждого метода получена теоретическая оценка качества выходной точки. Адаптивность методов позволяет, в частности, применить полученные результаты к задачам с целевыми функциями, которые не удовлетворяют условию Липшица градиента на всём пространстве. Это проиллюстрировано результатами вычислительных экспериментов для функций Розенброка и Нестерова - Скокова.
Адаптивный метод, градиентный метод, условие поляка - лоясиевича, неточный градиент, относительная неточность
Короткий адрес: https://sciup.org/142241780
IDR: 142241780
Список литературы Градиентные методы для минимизационных задач с условием Поляка - Лоясиевича: относительная погрешность градиента и адаптивный подбор параметров
- Beck A. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics. Oct 2017. https://doi.org/10.1137/1.9781611974997
- Nesterov Y. Introductory Lectures on Convex Optimization. Springer US, 2004. https://doi.org/10.1007/978-1-4419-8853-9
- Polyak B.T. Gradient methods for the minimisation of functionals // USSR Computational Mathematics and Mathematical Physics. 1963. V. 3(4). P. 864–878. https://doi.org/10.1016/0041-5553(63)90382-3
- Yue P., Fang C., Lin Z. On the lower bound of minimizing Polyak – Lojasiewicz functions. The Thirty Sixth Annual Conference on Learning Theory // Proceedings of Machine Learning Research. 2023. V. 195. P. 2948–2968. https://proceedings.mlr.press/v195/yue23a/yue23a.pdf
- Devolder O., Glineur F., Nesterov Y. First-order methods of smooth convex optimization with inexact oracle // Mathematical Programming. 2013. V. 146(1–2). P. 37–75. https://doi.org/10.1007/s10107-013-0677-5
- Поляк Б.Т. Введение в оптимизацию. Москва: Наука, 1983.
- Polyak B.T., Kuruzov I.A., Stonyakin F.S. Stopping rules for gradient methods for nonconvex problems with additive noise in gradient // Journal of Optimization Theory and Applications. 2023. V. 198. P. 531–551. https://doi.org/10.1007/s10957-023-02245-w
- Kuruzov I.A., Stonyakin F.S., Alkousa M.S. Gradient-type methods for optimization problems with Polyak– Lojasiewicz condition: Early stopping and adaptivity to inexactness parameter / Olenev N., Evtushenko Y., Jacimovic M., Khachay M., Malkova V., Pospelov I. (eds) // Advances in Optimization and Applications. OPTIMA 2022. Communications in Computer and Information Science. 2022. V. 1739. P. 18–32. https://doi.org/10.48550/ARXIV.2212.04226
- Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. Москва: МЦНМО, 2021.
- Carter R.G. On the global convergence of trust region algorithms using inexact gradient information // SIAM Journal on Numerical Analysis. 1991. V. 28(1). P. 251–265. https://doi.org/10.1137/0728014
- Berahas A.S., Cao L., Choromanski K., Scheinberg K. A theoretical and empirical comparison of gradient approximations in derivative-free optimization // Foundations of Computational Mathematics. 2021. V. 22(2). P. 507–560. https://doi.org/10.1007/s10208-021-09513-z
- Belkin M. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation // Acta Numerica. 2021. V. 30. P. 203–248. https://doi.org/10.1017/S0962492921000039
- Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximalgradient methods under the Polyak – Lojasiewic condition. Springer, 2016. P. 795–811. https://doi.org/10.1007/978-3-319-46128-1_50
- Polyak B., Tremba A. New versions of Newton method: step-size choice, convergence domain and under-determined equations // Optimization Methods and Software. 2020. V. 35(6), P. 1272–1303. https://doi.org/10.1080/10556788.2019.1669154
- Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. 2014. V. 152(1–2). P. 381–404. https://doi.org/10.1007/s10107-014-0790-0
