Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 99-108

1. ВВЕДЕНИЕ

Одной из основных задач в области искусственного интеллекта на данный момент является объединение теории и практики машинного обучения. В теории методов оптимизации, которые являются важным звеном в машинном обучении, обеспечивая эффективную настройку моделей и обработку данных, образование данной связи проявляется в исследованиях при более слабых предположениях, чем стандартные. Эти исследования направлены на анализ методов в более широком классе задач и способствуют более эффективному применению методов машинного обучения. Также стоит отметить, что некоторые явления, возникающие при реализации методов, не могут быть объяснены с помощью классического рассмотрения сходимости по математическому ожиданию [Gorbunov et al., 2020], что вызывает возрастающий интерес к рассмотрению сходимости с большой вероятностью. Таким образом, исследования сходимости методов с большой вероятностью при менее строгих условиях на целевую функцию действительно являются важной областью исследования в области искусственного интеллекта. Несмотря на значительный интерес к данной теме [Nazin et al., 2019, Davis et al., 2021, Cutkosky and Mehta, 2021, Nguyen et al., 2023, Liu and Zhou, 2023, Liu et al., 2023], некоторые важные аспекты оставались неисследованными на протяжении продолжительного времени. Это продолжалось до появления серии работ [Gorbunov et al., 2020, 2021, 2022, Sadiev et al., 2023], в которых были предложены и подробно проанализированы методы, основанные на применении градиентного клиппинга, для решения задач минизации и вариационных неравенств в предположении, что градиентный/операторный шум имеет ограниченный центральный α-й момент для $\alpha \in (1,2]$.

2. ГРАДИЕНТНЫЙ КЛИППИНГ И ТЯЖЕЛЫЕ ХВОСТЫ РАСПРЕДЕЛЕНИЯ

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

В машинном обучении мы часто сталкиваемся с ситуацией, когда, решая задачу минимизации, у нас есть доступ только к стохастическому градиенту. В таком случае мы можем решать данную задачу, генерируя последовательность ${{\{ {{x}_{k}}\} }_{{k \geqslant 0}}}$ с помощью стохастического градиентного спуска SGD, который является одним из наиболее распространенных методов оптимизации, применяемых в случае стохастической оптимизации. Классический стохастический градиентный спуск выглядит следующим образом

где $f(x)$ – целевая функция, γ – размер шага, $\nabla f({{x}^{k}},{{\xi }^{k}})$ – стохастический градиент, т.е. несмещенная оценка $\nabla f({{x}^{k}})$: ${{\mathbb{E}}_{{{{\xi }^{k}}}}}[\nabla f({{x}^{k}},{{\xi }^{k}})] = \nabla f({{x}^{k}})$.

Градиентный клиппинг

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

Данная техника полезна в случаях, когда градиент может быть слишком большим и вызывать проблемы с обучением, такие как взрывной градиент. Градиентный клиппинг ограничивает норму градиента до определенного предела $\lambda > 0$, чтобы избежать таких проблем. Это позволяет контролировать скорость обновления параметров модели и повышает стабильность процесса обучения. Отметим, что оператор ${\text{clip}}(\nabla f({{x}^{k}},{{\xi }^{k}}),\lambda )$ – смещенная оценка $\nabla f({{x}^{k}})$: ${{\mathbb{E}}_{{{{\xi }^{k}}}}}[{\text{clip}}(\nabla f({{x}^{k}},{{\xi }^{k}}),\lambda )] \ne \nabla f({{x}^{k}})$, усложняющая анализ clipped-SGD. Клиппинг набрал популярность в области искусственного интеллекта и машинного обучения с момента публикации статьи [Pascanu et al., 2013] в 2013 г. В этой статье было предложено использовать градиентный клиппинг для решения проблемы взрывающихся градиентов при обучении рекуррентных нейронных сетей. В случае метода без клиппинга значения целевой функции сильно колеблются на разных итерациях обучения, что указывает на нестабильность процесса обучения. В то же время метод с клиппингом градиента проявляет более стабильную сходимость. Это свидетельствует о робастности и надежности сходимости метода с клиппингом градиента. Клиппинг градиента и подобные подходы широко применяются в различных задачах обработки естественного языка (NLP). В 2017 г. было предложено использование клиппинга в LSTM моделях [Merity et al., 2018], а затем в двунаправленной языковой модели [Peters et al., 2017]. В 2020 г. он был применен для тонкой настройки модели BERT [Mosbach et al., 2020]. Эти исследования и применения свидетельствуют о тенденции использования клиппинга или подобных подходов в задачах NLP. Это обусловлено необходимостью обеспечения стабильности и робастности обучения моделей, особенно в случаях с большими и сложными наборами данных, типичными для NLP задач.

В работе [Zhang et al., 2020] представлены результаты эксперимента, целью которого было исследование влияния градиентного клиппинга. Для модели ResNet50 на наборе данных ImageNet эффективно работает стандартный SGD с моментумом, что делает клиппинг необязательным. Но при обучении BERT на Wikipedia+Books градиенты имеют тяжелые хвосты, и метод ADAM, как адаптивный покомпонентный клиппинг, обеспечивает более эффективное обучение и сходимость. ADAM, адаптируя скорость обучения для каждого параметра индивидуально, позволяет более эффективно работать с тяжелыми хвостами распределений градиентов и обеспечивает более стабильное и быстрое обучение модели BERT. Правило обновления для ADAM согласно [Kingma and Ba, 2014] записывается в следующем виде

где все операции с векторами (возведение в квадрат, извлечение корня, деление на вектор) происходят покомпонентно $ \odot $. Когда ${{\beta }_{1}} = 0$ Adam(RMSprop) можно рассматривать как clipped-SGD c “адаптивным” и покомпонентным ${{\lambda }_{k}}$.

Тяжелые хвосты распределения

Далее давайте определим, в каком случае мы будем считать, что распределение имеет тяжелый хвост. Мы будем говорить, что случайный вектор $X$ имеет легкие (субгауссовские) хвосты распределения, если выполняет следующее неравенство:

которое эквивалентно (с точностью до числового коэффициента в $\sigma $)

В общем случае мы говорим, что случайный вектор $X$ имеет тяжелые хвосты распределения, если не выполнено условие (2) и существует конечная дисперсия. Однако были получены результаты при более общем условии, что он имеет ограниченный центральный $\alpha $-й момент для некоторого $\alpha \in (1,2]$:

Когда $\alpha = 2$, приведенное выше предположение восстанавливает стандартное предположение о равномерно ограниченной дисперсии. Однако предположение (4) допускает, чтобы дисперсия была неограниченной, когда $\alpha \in (1,2)$.

3. СХОДИМОСТЬ С БОЛЬШОЙ ВЕРОЯТНОСТЬЮ И СХОДИМОСТЬ ПО МАТЕМАТИЧЕСКОМУ ОЖИДАНИЮ

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

Задача и ограничения

В первую очередь давайте формально определим рассматриваемую нами задачу и уточним предположения, с которыми мы работаем. Мы рассматриваем задачу безусловной стохастической оптимизации, где целевая функция представляет собой математическое ожидание относительно переменной $\xi $

где $f\,:\,\,{{\mathbb{R}}^{n}}\, \to \,\mathbb{R}$ выпуклая и L-гладкая, т.е. $\forall x,y\, \in \,{{\mathbb{R}}^{n}}$

Стохастический градиент $\nabla f(x,\xi )$ с ограниченным центральным $\alpha $-м моментом ($\alpha \in (1,2]$), т.е. $\forall x \in {{\mathbb{R}}^{n}}$

Cходимость итеративного метода

Теперь давайте уточним, что мы понимаем под сходимостью итеративного метода. Какие гарантии на сходимость могут быть предоставлены? Мы будем рассматривать два подхода к анализу этих методов.

Сходимость в среднем. Сходимость в среднем (по математическому ожиданию) подразумевает определение числа итераций N (или вызовов оракула), необходимых для достижения такой точки ${{x}^{N}}$, при которой выполняется одно из следующих условий: $\mathbb{E}[{\text{||}}{{x}^{N}} - x{\kern 1pt} *{\text{|}}{{{\text{|}}}^{2}}]\;\leqslant \;\varepsilon $, $\mathbb{E}[f({{x}^{N}}) - f(x{\kern 1pt} *)]\;\leqslant \;\varepsilon $, $\mathbb{E}[{\text{||}}\nabla f({{x}^{N}}){\text{|}}{{{\text{|}}}^{2}}]\;\leqslant \;\varepsilon $. Обычно такие гарантии зависят только от определенных моментов стохастического градиента, таких как дисперсия.

Сходимость с большой вероятностью. Сходимость с большой вероятностью подразумевает определение числа итераций N (или вызовов оракула), необходимых для достижения такой точки ${{x}^{N}}$, при которой выполняется одно из следующих условий: $\mathbb{P}\{ {\text{||}}{{x}^{N}}\, - \,x{\kern 1pt} *{\text{|}}{{{\text{|}}}^{2}}\;\leqslant \;\varepsilon \} \; \geqslant \;1$ – β, $\mathbb{P}\{ f({{x}^{N}})\, - \,f(x{\kern 1pt} *)\,\leqslant \,\varepsilon \} $ $ \geqslant $ 1 – – β, $\mathbb{P}\{ {\text{||}}\nabla f({{x}^{N}}){\text{|}}{{{\text{|}}}^{2}}\;\leqslant \;\varepsilon \} \; \geqslant \;1$ – β. Такие гарантии чувствительны к распределению шума в стохастических градиентах.

Недостатки сходимости по математическому ожиданию

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

где $\mathbb{E}[\xi ] = 0$ и $\mathbb{E}[{\text{||}}\xi {\text{|}}{{{\text{|}}}^{2}}] = {{\sigma }^{2}}$. Нас интересует случай ограниченной дисперсии в (4) (α = 2), так как согласно примеру в работе [Zhang et al., 2020] в случае не субгауссовского распределения случайной величины $\xi $, SGD может не сходиться по математическому ожиданию, когда $\alpha < 2$. В данном примере рассмотрим 3 варианта распределения $\xi $: нормальное (гауссовское) распределение, распределение Вейбулла (не субгауссовское), распределение Бёрра XII (не субгауссовоское). Оказывается, что все три случая не будут отличимы для гарантий по математическому ожиданию, поскольку известные гарантии для алгоритма SGD [Ghadimi and Lan, 2013] не зависят от распределения шума

В представленной оценке действительно нет явной информации о распределении. Однако как показано на рис. 1, на практике поведение метода может зависеть от распределения шума.

Анализируя графики 1, мы приходим к выводу, что при запуске метода нам бы хотелось уже после первого запуска иметь гарантии с высокой вероятностью получить хорошее решение. В случае обычного SGD мы не можем гарантировать это без уменьшения шага для сдерживания всплесков, что приводит к потери скорости. Однако в случае clipped-SGD с правильным уровнем клиппинга, мы можем избежать необходимости уменьшения шага. Чтобы оценить эту разницу, мы будем рассматривать оценки сходимости с большой вероятностью.

Результаты о сходимости с большой вероятностью в предположении легких хвостов

Прежде чем приступить к обсуждению новейших результатов, давайте посмотрим, что было известно на момент начала обозреваемого цикла работ, т.е. к 2020 г. При предположении о легких хвостах распределения (3), а также при условии выпуклости и L-гладкости функции f, было известно следующее Devolder et al. [2011] показали, что алгоритм SGD достигает точки $\hat {x}$, для которой выполняется неравенство $f(\hat {x})\, - \,f(x{\kern 1pt} *)\,\leqslant \,\varepsilon $ с вероятностью не менее $1 - \beta $, используя

Ghadimi and Lan [2012] показали, что алгоритм SGD достигает точки $\hat {x}$, для которой выполняется неравенство $f(\hat {x}) - f(x{\kern 1pt} *)\;\leqslant \;\varepsilon $ с вероятностью не менее $1 - \beta $, используя

Неравенство Маркова

На текущем этапе важно отметить, что нельзя просто применить неравенство Маркова и получить гарантии сходимости с большой вероятностью на основе сходимости по математическому ожиданию. Используя неравенство Маркова

и сделав достаточное количество шагов в алгоритме SGD, мы можем обеспечить гарантию $\mathbb{E}[f(\hat {x})\, - \,f(x{\kern 1pt} *)]\,\leqslant \,\varepsilon \beta $, что даст нам $\mathbb{P}\{ f(\hat {x})$ – f(x*) > > $\varepsilon \} \,\leqslant \,\beta $ или $\mathbb{P}\left\{ {f(\hat {x}) - f(x{\kern 1pt} *)\;\leqslant \;\varepsilon } \right\}\; \geqslant $ 1 – β. Для достижения точности $\mathbb{E}[f(\hat {x})\, - \,f(x{\kern 1pt} *)]\;\leqslant \;\varepsilon \beta $ методу SGD необходимо

К сожалению, зависимость от ${{\beta }^{{ - a}}},\;a > 0$ не подходит, так как необходимо получить логарифмическую зависимость от $\frac{1}{\beta }$, потому что $\beta $ должно быть маленьким. Поэтому неравенство Маркова не позволяет получить нужные гарантии о сходимости с большой вероятностью. Однако возникает вопрос: можно ли более точно проанализировать сходимость алгоритма SGD с большой вероятностью? Да, cледующая теорема содержит результаты о сходимости SGD в предположении тяжелых хвостов, но при этом подчеркивает необходимость модификации классического алгоритма SGD. Градиентный клиппинг, описанный в предыдущей главе, является подходящим решением этой задачи.

Теорема 3.1. Для любых $\varepsilon > 0$, $\beta \in (0,1)$ и алгоритма SGD параметризованного количеством шагов $K$ и длиной шага $\gamma $, существует $\mu $-сильно выпуклая $L$-гладкая задача $\mathop {\min }\limits_{x \in Q} f(x)$, а также стохастический оракул с шумом, имеющим ограниченный α-й момент с $\alpha = 2$, при условии $0 < \mu \;\leqslant \;L$ такие, что для алгоритма SGD с длиной шага $0\,\leqslant \,\gamma \,\leqslant \,\frac{1}{\mu }$ выполнено следующее

Результаты о сходимости с большой вероятностью в предположении тяжелых хвостов

Давайте рассмотрим известные результаты о гарантиях сходимости алгоритма SGD с большой вероятностью. В случае, когда распределение имеет тяжелые хвосты, т.е. не выполнено условие (2), и дисперсия равномерно ограничена (4) ($\alpha = 2$), первые результаты были получены в 2019 г. Nazin et al. [2019] предложили Robust Stochastic Mirror Descent (RSMD), напоминающий clipped-SGD, и доказали следующую оценку

Это была первая работа в данной области. Из недостатков стоит отметить, что доказательство опирается на диаметр множества $D < + \infty $ и нет ускорения метода. В скором времени был получен новый результат для другого метода. Davis et al. [2021] предложили proxBoost, основанный на робастном оценивании расстояния и методе проксимальной точки. Авторы данной работы доказали следующую оценку (в сильно выпуклом случае):

Данный результат ускоренный и получен для любой выпуклой замкнутой области (ограниченной/неограниченной). При этом стоит отметить, что предложенный метод требует решения вспомогательной задачи на каждой итерации, а так же в оценке появился дополнительный логарифм числа обусловленности.

4. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДЛЯ ЗАДАЧ МИНИМИЗАЦИИ

В данной главе мы обсудим основные результаты для задач минимизации, методы и сложности, связанные с их анализом. Давайте начнем с неускоренного метода clipped-SGD. В связи с тем, что его проще анализировать, чем другие методы, на его примере мы сможем понять, с какими сложностями можно столкнуться при анализе методов с клиппингом. Шаг метода clipped-SGD

Смещенность оценки $\mathbb{E}[\widetilde \nabla f({{x}^{k}},{{\xi }^{k}})\,{\text{|}}\,{{x}^{k}}]\, \ne \,\nabla f({{x}^{k}})$ – основная причина сложностей, возникающих при теоретическом анализе. Для того, чтобы понять, где именно возникает эта проблема, давайте посмотрим классическое доказательство сходимости SGD

Используя выпуклость гладкость f и перегруппировывая слагаемые, получается следующее выражение:

где ${{\Delta }_{k}} = f({{x}^{k}}) - f(x{\kern 1pt} *)$, ${{R}_{k}} = {\text{||}}{{x}^{k}} - x{\kern 1pt} *{\text{||}}$, θ_k = = $\widetilde \nabla f({{x}^{k}},{{\xi }^{k}}) - \nabla f({{x}^{k}})$. Красным цветом выделена стохастическая часть суммы, но как оценить сверху эти слагаемые? Это достигается с помощью применения неравенства Бернштейна.

Неравенство Бернштейна для мартингальных разностей

Лемма 4.1. [Bennett, 1962, Dzhaparidze and Van Zanten, 2001, Freedman et al., 1975] Пусть последовательность случайных величин ${{\{ {{X}_{i}}\} }_{{i \geqslant 1}}}$ образует последовательность мартингальных разностей, т.е. $\mathbb{E}\left[ {{{X}_{i}}\,{\text{|}}\,{{X}_{{i - 1}}}, \ldots ,{{X}_{1}}} \right] = 0$ для любых $i \geqslant 1$. Предположим, что существуют условные ограниченные дисперсии $\sigma _{i}^{2}\;\mathop = \limits^{{\text{def}}} \;\mathbb{E}[X_{i}^{2}\,{\text{|}}\,{{X}_{{i - 1}}}, \ldots ,{{X}_{1}}]$, а также существует константа c > 0 такая, что ${\text{|}}{{X}_{i}}{\text{|}} \leqslant c$ для любых $i \geqslant 1$. Тогда для любых $b > 0$, $G > 0$ и $N \geqslant 1$

Для того, чтобы применить лемму (4.1) для сумм $\frac{{2\gamma }}{N}\sum\nolimits_{k = 0}^{N - 1} {\langle x{\kern 1pt} *\; - {{x}^{k}},{{\theta }_{k}}\rangle } $ + $\frac{{2{{\gamma }^{2}}}}{N}\sum\nolimits_{k = 0}^{N - 1} {{\text{||}}{{\theta }_{k}}{\text{|}}{{{\text{|}}}^{2}}} $, необходимо ограничить смещение, дисперсию, ${\text{||}}{{x}^{k}} - x{\kern 1pt} *{\text{||}}$ и ${\text{||}}{{\theta }_{k}}{\text{||}}$ с большой вероятностью. Следующая лемма была доказана для работы со смещением, дисперсией и т.д.

Лемма 4.2. Пусть X случайный вектор в ${{\mathbb{R}}^{n}}$ и $\widetilde X = {\text{clip}}(X,\lambda )$. Тогда,

Более того, если для некоторых $\sigma \; \geqslant \;0$ и $\sigma \in [1,2)$ выполняется

и ${\text{||}}x{\text{||}}\;\leqslant \;\lambda {\text{/}}2$, тогда

Остается ограничить расстояние до решения. В силу того, что ${{\Delta }_{k}}\; \geqslant \;0$ $\forall k\; \geqslant \;0$, полученное ранее неравенство

можно переписать следующим образом

Основная идея: доказать по индукции ${{R}_{N}}\;\leqslant \;C{{R}_{0}}$ с большой вероятностью для некоторой числовой константы C. Это означает, что точки, генерируемые методом, остаются в некотором шаре вокруг решения. Мы представили общий подход к получению вероятностных оценок сходимости методов, использующих градиентный клиппинг в предположении, что шум имеет ограниченный центральный $\alpha $-й момент для $\alpha \in (1,2]$.

Сходимость clipped-SGD с большой вероятностью

Теорема 4.1. Пусть f выпуклая и L-гладкая на ${{B}_{{7{{R}_{0}}}}}(x{\kern 1pt} *) = \{ x \in {{\mathbb{R}}^{n}}\,{\text{|}}\,{\text{||}}x - x{\kern 1pt} *{\text{||}}\;\leqslant \;7{{R}_{0}}\} $ и (8) выполняется на ${{B}_{{7{{R}_{0}}}}}(x{\text{*}})$. Тогда для любых $\beta \in (0,1)$, $\varepsilon \; \geqslant \;0$ таких, что $\ln (LR_{0}^{2}{\text{/}}\varepsilon \beta )\; \geqslant \;2$ существует такой выбор $\gamma $, что clipped-SGD с уровнем клиппинга $\lambda \sim 1{\text{/}}\gamma $ достигает ${{\bar {x}}^{N}}$, удовлетворяющую $f({{\bar {x}}^{N}})\, - \,f(x{\kern 1pt} *)\,\leqslant \,\varepsilon $ с вероятностью не менее $1 - \beta $, используя

Полученный результат соответствует (с точностью до логарифмических множителей) результатам для SGD в случае легких хвостов и для RSMD в случае тяжелых хвостов, но для безусловной задачи. Отметим, что все предположения достаточно требовать на шаре вокруг решения.

Ускоренный clipped-SGD: clipped-SSTM

Теперь, имея представление о рассмотренных ранее идеях доказательства, мы готовы перейти к рассмотрению ускоренного метода. На основе метода подобных треугольников (Stochastic Similar Triangles Method) предложенного Gasnikov and Nesterov [2016], и с использованием градиентного клиппинга был получен ускоренный вариант clipped-SGD–clipped-SSTM

Параметр $a$ в clipped-SSTM используется для уменьшения размера шага алгоритма, что позволяет избежать необходимости использовать большие батчи. Что касается основной идеи доказательства, она аналогична неускоренному случаю: с помощью индукции доказывается, что с высокой вероятностью выполнено неравенство ${{R}_{N}}\,\leqslant \,C{{R}_{0}}$. Так же стоит отметить, что в ускоренном случае уровень клиппинга ${{\lambda }_{{k + 1}}}$ уменьшающийся. Из-за чувствительности ускоренных методов к неточностям, включая стохастичность, использование постоянного уровня клиппинга не является достаточным, так как это может привести к значительному смещению. Для метода подобных треугольников можно доказать, что ${\text{||}}\nabla f({{x}^{{k + 1}}}){\text{||}}\, = \,{\kern 1pt} \mathcal{O}(1{\text{/}}{{\alpha }_{{k + 1}}}).$ По аналогии с детерминированным случаем выбирается ${{\lambda }_{{k + 1}}} \sim 1{\text{/}}{{\alpha }_{{k + 1}}}$, и удается доказать, что условие ${\text{||}}\nabla f({{x}^{{k + 1}}}){\text{||}}\, = \,\mathcal{O}(1{\text{/}}{{\alpha }_{{k + 1}}})$ выполняется с высокой вероятностью и в стохастическом случае.

Сходимость clipped-SSTM с большой вероятностью

Теорема 4.2. Пусть f выпуклая и $L$-гладкая на ${{B}_{{3{{R}_{0}}}}}(x{\kern 1pt} *) = \{ x \in {{\mathbb{R}}^{n}}\,{\text{|}}\,{\text{||}}x - x{\kern 1pt} *{\text{||}}\;\leqslant \;3{{R}_{0}}\} $ и (8) выполняется на ${{B}_{{3{{R}_{0}}}}}(x{\kern 1pt} *)$. Тогда для любых $\beta \in (0,1)$, $\varepsilon \; \geqslant \;0$ таких, что $\ln (\sqrt L {{R}_{0}}{\text{/}}\sqrt \varepsilon \beta )\; \geqslant \;2$ существует такой выбор a, что clipped-SSTM с уровнем клиппинга $\lambda \sim 1{\text{/}}{{\alpha }_{{k + 1}}}$ достигает y^N, удовлетворяющую f(y^N) – – $f(x{\kern 1pt} *)\;\leqslant \;\varepsilon $ с вероятностью не менее $1 - \beta $, используя

Полученный результат соответствует (с точностью до логарифмических множителей) результатам для AC-SA в случае легких хвостов и лучше чем результаты для clipped-SGD. Так же в работах [Gorbunov et al., 2020, 2021, 2022, Sadiev et al., 2023] получены результаты для невыпуклых, сильно выпуклых функций и для функций с непрерывными по Гёльдеру градиентами. Как и в случае clipped-SGD, все предположения достаточно требовать на шаре вокруг решения.

Численные эксперименты

На практике работоспособность методов была проверена на следующих задачах¹¹:

BERT ($ \approx {\kern 1pt} 0.6M$ параметров) донастройка на датасете CoLA. Мы используем предварительно обученную модель BERT и замораживаем все слои, кроме двух последних линейных. В этом наборе данных содержится 8551 предложений, и задача бинарной классификации заключается в определении, является ли предложение грамматически верным.

ResNet-18 ($ \approx {\kern 1pt} 11.7M$ параметров) обучение на датасете ImageNet-100 (первые 100 классов из ImageNet). В нем содержится 134 395 изображений.

Один из экспериментов был проведен с целью анализа распределения шума в стохастических градиентах. [Gorbunov et al., 2021]. В начальной  точке бралось достаточно большое количество пробатченных стохастических градиентов $\nabla f({{x}^{0}},{{\xi }_{1}}), \ldots ,\nabla f({{x}^{0}},{{\xi }_{K}})$ с размером батча   32 и строились гистограммы для ${\text{||}}\nabla f({{x}^{0}},{{\xi }_{1}}) - \nabla f({{x}^{0}}){\text{|}}{{{\text{|}}}_{2}}$, ..., ${\text{||}}\nabla f({{x}^{0}},{{\xi }_{K}}) - \nabla f({{x}^{0}}){\text{|}}{{{\text{|}}}_{2}}$, см. рис. 2. Как видно, распределение шума для BERT + CoLA значительно отличается от субгауссовского, в то время как распределение для ResNet-18 + Imagenet-100 почти гауссовское. Наблюдается аналогичное распределения шума в разных точках на траектории методов (ADAM, SGD, clipped-SGD, clipped-SSTM) для предложенных задач.

Далее было проведено сравнительное исследование различных методов для решения данных задач: ADAM, SGD, clipped-SGD и clipped-SSTM [Gorbunov et al., 2021]. Иллюстрация результатов приведена на рис. 3, 4.

5. ОСНОВНОЙ РЕЗУЛЬТАТ ДЛЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ

В данной серии исследований также освещается анализ методов для работы с безусловными вариационными неравенствами (VIP), представляющими собой нелинейные уравнения [Harker and Pang, 1990, Ryu and Yin, 2022]. Эти уравнения, в свою очередь, возникают в контексте игровых формулировок задач машинного обучения [Goodfellow et al., 2014, Gidel et al., 2019].

где $F(x) = {{\mathbb{E}}_{{\xi \sim \mathcal{D}}}}[{{F}_{\xi }}(x)]$. Аналогично с задачами минимизации сохраняется предположение об ограниченности центрального $\alpha $-го момента оператора $F$. Предполагается, что существует некоторое множество $Q \subseteq {{\mathbb{R}}^{n}}$ и значения $\sigma \; \geqslant \;0$, $\alpha \in (1,2]$, такие что для всех $x \in Q$clipped-SEG – клиппированный стохастический экстраградиентный метод где $\xi _{1}^{k}$, $\xi _{2}^{k}$ независимо выбираются из ${{\mathcal{D}}_{k}}$ на каждом шаге. Данный метод рассматривается для решения вариационных неравенств (VIP) в предположении о монотонности и липшицевости оператора $F$. Предполагается, что существует некоторое множество $Q \subseteq {{\mathbb{R}}^{n}}$, для которого оператор $F$ монотонен на $Q$, т.е. для всех $x,y \in Q$и существует константа $L > 0$, такая что для всех $x,y \in Q$

Теорема 5.1 (Сходимость clipped-SEG). Пусть предположения (18), (21), (22) выполняются для $Q = {{B}_{{4R}}}(x{\kern 1pt} *)$ и 0 < γ = $\mathcal{O}(\min \{ 1{\text{/}}LA$, $R{\text{/}}{{K}^{{1{\text{/}}\alpha }}}\sigma {{A}^{{(\alpha - 1){\text{/}}\alpha }}}\} )$, ${{\lambda }_{k}} = \lambda = \Theta \left( {R{\text{/}}\gamma A} \right)$, где A = = ${\text{ln}}\frac{{6(K + 1)}}{\beta }\; \geqslant \;1$, $\beta \in (0,1]$. Чтобы гарантировать $Ga{{p}_{R}}(\tilde {x}_{{{\text{avg}}}}^{K})\;\leqslant \;\varepsilon $ с вероятностью $ \geqslant 1 - \beta $ clipped-SEG, требуется

вызовов оракула.

Основная идея доказательства вышеупомянутой теоремы аналогична принципу в минимизации. Детальное описание результатов для разнообразных случаев можно найти в статьях [Gorbunov et al., 2022, Sadiev et al., 2023]. Также следует обратить внимание на статью [Gorbunov et al., 2022], где демонстрируется, что градиентный шум во многих генеративно-состязательных сетях (GAN) имеет тяжелые хвосты, и что использование клиппинга положительно сказывается на эффективности SEG.

6. ЗАКЛЮЧЕНИЕ

В данном обзоре демонстрируется и объясняется роль клиппинга в современных state-of-the-art результатах о сходимости с большой вероятностью. Мы рассмотрели важные аспекты задач, связанных с присутствием шума с тяжелыми хвостами в различных областях, включая обработку естественного языка (NLP) и генеративно-состязательные сети (GAN). Клиппинг выделяется в качестве эффективного и простого инструмента для борьбы с шумом с тяжелыми хвостами. Этот подход подтвердил свою эффективность в улучшении оценок вероятностной сходимости методов, в сравнении с гарантиями сходимости альтернативных методов, не использующих клиппинг. Также интересными являются предположения о частичных объяснениях успеха адаптивных методов, включая, например, метод ADAM, в задачах GAN и NLP. Это может предоставить дополнительные идеи для разработки алгоритмов в этих областях. Исходя из результатов и выводов, представленных в данной работе, можно заключить, что использование методов с клиппингом представляет собой перспективный подход для улучшения сходимости в условиях шума с тяжелыми хвостами в различных задачах, и дальнейшие исследования в этом направлении могут привести к еще более значимым результатам и новым практическим применениям.