Доказана оптимальная скорость сходимости SGD с марковским шумом для PL-условий

В новой работе, опубликованной на arXiv, исследователи решили ключевую задачу теории оптимизации: получена оптимальная скорость сходимости SGD (стохастического градиентного спуска) для функций, удовлетворяющих условию Поляка–Лоясиевича (PL), когда градиенты искажены марковским шумом. Условие PL является одним из важнейших в современной оптимизации, поскольку оно охватывает широкий класс задач, включая обучение нейросетей.

До сих пор существовал разрыв между теоретическими гарантиями для матожидания и неравенствами с высокой вероятностью (high-probability bounds). Для обычного SGD при марковском шуме высоконадёжные оценки имели порядок O(t_{mix}^2/k), в то время как границы для матожидания были O(t_{mix}/k), где t_{mix} — время перемешивания марковской цепи, а k — число итераций. Этот разрыв мешал точному теоретическому анализу алгоритмов, используемых на практике.

Авторы работы закрыли этот пробел с помощью техники lag-blocking (запаздывающей блокировки). Они доказали, что при геометрическом перемешивании высоконадёжная гарантия для ведущего стохастического члена составляет O(t_{mix}/(k+K_0)), то есть линейно зависит от времени перемешивания. Более того, построена нижняя оценка, показывающая, что такая линейная зависимость оптимальна.

Затем исследователи обобщили результат на тяжёлые хвосты (heavy-tailed) марковского шума, когда градиенты имеют конечный p-й момент при p?(1,2]. Для этого случая предложен метод clipped block, который использует все переходы марковской цепи, одновременно подавляя смещение. При ограниченном бюджете T итераций этот метод достигает стохастической ошибки порядка O(?_p^2 (t_{mix}/T)^{2(p-1)/p}), что также признано оптимальным.

Работа не только закрывает теоретический пробел, но и предлагает практический алгоритм для задач с тяжёлыми хвостами. Полученные результаты важны для обучения моделей в условиях, когда градиенты коррелированы во времени, например, при обработке последовательных данных или в распределённых системах.

Таким образом, статья вносит существенный вклад в теорию стохастической оптимизации, устанавливая точную зависимость скорости сходимости от времени перемешивания и толщины хвостов распределения шума. Это позволит разработчикам алгоритмов лучше понимать их поведение в реальных сценариях.