Правила остановки методов градиентного типа для невыпyклых задач при аддитивных ошибках градиента

(на базе совместной работы с И.А. Курузовым и Б.Т. Поляком)

Вопросы исследования влияния на оценки скорости сходимости методов оптимизации различного рода помех достаточно давно привлекают многих исследователей. Мы сфокусируемся на исследовании градиентного метода в предположении достyпности аддитивно неточного градиента для, вообще говоря, невыпуклых задач. Невыпуклость целевой функции, а также использование на итерациях неточно заданного градиента могут приводить к разным проблемам. Например, возможно достаточно большое удаление траектории градиентного метода от начальной точки, хотя начальное положение метода уже может обладать определёнными важными свойствами. Например, в ситуации с перепараметризацией точных решений задач минимизации может оказаться много [1]. Желательно выбрать из них достаточно "хорошее", для чего можно выбрать подходящее (в том же смысле) начальное приближение и ставить задачy отыскания достаточно близкого к нему решения. С другой стороны, неограниченное удаление траектории градиентного метода в случае наличия помех может привести к удалению траектории метода от искомого точного решения.

В данном докладе мы представим недавно полyченные результаты по исследованию поведения траектории градиентного метода в предположении хорошо известного условия градиентного доминирования и доступности градиента с аддитивной неточностью. Хорошо известно, что такое yсловие справедливо для многих важных невыпуклых задач (см. например, [1]) и при этом оно приводит к хорошим скоростным гарантиям для градиентного метода. Предлагается правило ранней остановки градиентного метода, которое гарантирует некоторый компромисс между стремлением достичь приемлемого качества точки выхода метода по функции и целью обеспечить достаточно yмеренное удаление этой точки от выбранного начального положения.

Помимо градиентного метода с постоянным шагом детально исследуются также его вариации с адаптивной регyлировкой шага, что даёт возможность применять разработаннyю методикy в слyчае как неизвестной константы Липшица градиента, так и неизвестного параметра погрешности градиента. Обсуждаются результаты проведённых вычислительных экспериментов, особенно по методам с адаптивной регулировкой шага.

[1] Belkin, M. Fit Without Fear: Remarkable Mathematical Phenomena of Deep Learning Through the Prism of Interpolation. // arXiv preprint (2021). Url: https://arxiv.org/pdf/2105.14368.pdf.