Безградиентные методы оптимизации для функций с гельдеровым градиентом тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Шибаев Иннокентий Андреевич

• Шибаев Иннокентий Андреевич
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Шибаев Иннокентий Андреевич

2.1 Предположения и решаемая задача

2.2 Сглаживание нормальным распределением

2.2.1 Определения

2.2.2 Cвойства

2.3 Сглаживание равномерным распределением на шаре

2.3.1 Определения

2.3.2 Cвойства

3 Результаты для невыпуклого случая

3.1 Анализ сходимости

3.1.1 Сходимость в смысле \\'Vf (хк)||

3.1.2 Сходимость в смысле (хк)\\

3.2 Вывод

4 Результаты для выпуклого случая

4.1 SSTM для функций с гельдеровым градиентом

4.1.1 Теоретические результаты

4.1.2 Эксперименты

4.2 ZO-SSTM для случая липшицевых функций

4.2.1 Теоретические результаты

4.2.2 Эксперименты

5 Дополнительные материалы

5.1 К главе

5.1.1 Доказательства лемм 2.2.1—2.2.4и3

5.1.2 Результаты из других работ

5.2 К главе

5.2.1 clipped-SSTM, д-во теоремы для выпуклого случая

5.2.2 clipped-SSTM, эксперименты на синтетических данных

5.2.3 clipped-SSTM, обучение нейросетей

5.2.4 ZO-clipped-med-SSTM

6 Заключение

Глава

Введение

Введение диссертации (часть автореферата) на тему «Безградиентные методы оптимизации для функций с гельдеровым градиентом»

Актуальность темы исследования

Методы безградиентной оптимизации, или, иначе, методы оптимизации использующие оракул нулевого порядка (т.е. только значения оптимизируемой функции в точке, не имея доступ к градиенту) в последние годы приобретают все большую значимость в связи с задачами машинного обучения, к примеру в задачах обучения с подкреплением [37], задачах где некоторый оракул используется как черный ящик (к примеру атаки на глубокие нейронные сети [45]) и в других случаях где структура задачи не позволяет получить доступ к градиенту оптимизируемой функции.

Существует подкласс алгоритмов безградиентной оптимизации которые никак не опираются на наличие градиента у функции в своей работе. Простейшим примером может служит просто перебор по сетке, или алгоритмы случайного поиска [51] — исторически одни из первых алгоритмов для решения таких задач, метод Нелдера — Мида [39], или трехточечный (STP) метод [5] и его усовершенствованный вариант STMP [28] и другие, к примеру разделы 2-6 и 10-11 в [9].

Основное преимущество безградиентных методов оптимизации [49, 17, 7, 53, 29, 9, 36] заключается в том, что вычислить значение функции, обычно, проще чем вычислить ее градиент в точке. С другой стороны, методы нулевого порядка обычно имеют худшие скорости сходимости, проигрывая методам первого порядка. Еще больше разрыв увеличивается из-за техники автоматического дифференцирования (Fast Automatic Differentiation, FAD), используемой при вычислении градиента при оптимизации весов моделей на основе нейронных сетей — известно [33, 2], что вычислительная сложность расчета градиента при использовании FAD всего в 4 раза превышает сложность самого расчета функции в точке. При этом детерминированная разностная оценка градиента стоит O(n) вызовов оракула, что, при большом количестве параметров модели, сильно превышает сложность FAD.

С другой стороны, есть ситуации в которых оптимизируемая функция дана как черный

ящик, и доступа к градиенту функции нет, и АД неприменимо. Один из примеров — задачи обучения с подкреплением (Reinforcement Learning, RL), где оптимизируется награда получаемая из черного ящика в зависимости от состояния среды и выбранной стратегии взаимодействия с ней [54]. Средой также может быть симуляция некоторого сложного физического процесса (к примеру движение спутников), и тогда возникает проблема наличия шума в выходах используемых моделей (а значит и в функции наград). Существуют также модели RL в которых заранее предполагается наличие шума в функции наград, более того, шум может быть смещенным [57]. Поэтому для безградиентных методов особенно важным становится получение результатов в условие наличия таких шумов.

Другое применение безградиентных методов это min-max или min-min задачи. К примеру, в [6] авторы рассматривают следующую задачу

min{f (x) = max L(x,y)},

x y

где f имеет локально гельдеров градиент, и при этом доступны лишь зашумленные значения и градиенты f получаемые через решение внутренней задачи maxy L(x, y) с некоторой точностью. В результате возникает невыпуклая задача оптимизации с неточным оракулом. В работе, однако, авторы фокусируются на методах первого порядка с неточным оракулом. Это также показывает, что в задачах безградиентной оптимизации особенный интерес представляют результаты для зашумленных оптимизируемых функций.

Другой класс задач, который будет рассмотрен в данной работе — это задачи стохастической оптимизации с тяжелыми хвостами в шуме оракула. В таких постановках делается предположение о не нормальном распределении шума, т.е. о высокой вероятности выбросов значений возвращаемых оракулом при вычислении значения в точке. Такой шум встречается во многих задачах машинного обучения, в частности связанных с обработкой текста (BERT), обучения больших языковых моделей [35, 59], GAN [21, 24], и других. Для решения таких задач часто применяют методы клиппинга градиента оптимизируемой функции (в случае методов первого порядка) [25, 10, 31, 44, 47].

Степень разработанности темы исследования

В работе [43] используется техника сглаживания нормальным распределением с параметром т исходной оптимизируемой функции. Для случая невыпуклой функции f на Rd с f =

f там показана сходимость градиентного спуска с градиентом замененным рандомизированной разностной оценкой к стационарной точке сглаженной функции ¡т (х). Основная идея заключается в том, что /т (х) имеют более хорошие свойства, к примеру является гладкой даже когда исходная функция гладкой не является. Для случая функции f с липшицевым градиентом там показано, что градиентный спуск с такой оценкой градиента достигает Е [\\Vf (xN )||2] ^ £Vf после N = О ^ ег) итераций с двумя вызовами оракула нулевого порядка на каждом шаге. Для случая липшицевой функции f показано, что при правильном выборе т можно достичь одновременно \ fт (х) — f (х) \ < £f для любых х е Ега и Е [\\VfT(xN)\\2] ^ £Vf после N = О ^^ итераций опять же с двумя вызовами оракула на каждом шаге. Таким образом хоть сходимость и получается по норме градиента сглаженной функции fт, ввиду ее близости к функции f получается и сходимость по функционалу f.

Та же техника сглаживания нормальным распределением была использована затем в работах [23] (RSGF) и [50] (RSPGF) чтобы построить алгоритм который находит т.н. (£, Л)-решение т.е. точку х такую, что P{\\Vf (х)\\2 ^ £vf} ^ 1 — Л, для задачи оптимизации функции f с липшицевым градиентом и стохастическим оракулом f = Г(х,£) таким, что [Г(х,£)] = f (х). В этих работах показано, что для достижения (£Vf, Л)-решения необходимо

сделать О ( С1--+ С2 -2— ) вызовов оракула f (здесь константы С1} С2 зависят от Л и других

параметров, вроде константы Липшица и диаметра множества X на котором ищется решение).

В данной работе мы будем рассматривать подкласс алгоритмов которые основаны на использовании тех или иных разностных оценках градиента в точке, к примеру оценках вида д(х) = ^г=1 [М(х+те)-1:(х))/т] ег где ег это столбцы единичной матрицы 1Л размера d х d, г е {1,..., d}). Для такой оценки, при условии достаточно хорошей оптимизируемых функций (к примеру f е С1/, т.е. непрерывно дифференцируемой функции с липшицевым градиентом) можно показать, к примеру, что \\д(х) — Vf (х)\\2 ^ тЬ\^. Затем мы можем рассмотреть какую-либо схему уже первого порядка (к примеру обычный градиентный спуск), заменить градиент оптимизируемой функцией оценкой такого вида, и использовать неравенства вроде тех что выше чтобы получить результаты уже и для безградиентной оптимизации. Более конкретно - мы будем рассматривать рандомизированные разностные оценки, подробнее о которых будет написано в части 1.

В работах перечисленных выше основной фокус был на функциях f с липшицевым градиентом или липшицевых. В работе [43] рассматривается случай негладкой липшицевой f, однако предполагается доступ к точным значениям функции в точке (f = f).

Вклад данной работы состоит в получении оценок на сходимость безградиентных методов оптимизации при условии гельдеровости градиента оптимизируемой функции, т.е. при условии что существует > 0, V € [0,1], такое, что выполнено \\V f (х) — Vf (у)\\* < Ьи\\х — у\\и. Такое предположение более общее, оно объединяет как случай липшицевой дифференцируемой f, так и f с липшицевым градиентом.

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

итераций. Здесь хк это последовательность точек, fт(•) это сглаженная нормальным распределением версия исходной функции f, Ы = (щ,---,им-1) это множество реализаций случайных нормальных векторов и используемых в разностных оценках. Важно, что это сходимость по градиенту сглаженной функции, который существует даже если исходная функция лишь непрерывна.

Цели исследования

1. Получить новые результаты для сходимости безградиентных методов для невыпуклого случая в условиях наличия шума в оракуле, тем самым развив идеи работ [43] и [12]

2. Для выпуклого случая развить методы на базе SSTM (из работы [25]) на случай функций с гельдеровым градиентом, и на случай безградиентной оптимизации

Задачи исследования

1. Используя методы сглаживания нормальным распределением получить оценки сходимости для градиентного спуска использующего стохастическую разностную оценку градиента по норме градиента для случая невыпуклого функционала с гельдеровым градиентом, в условиях наличия возможно смещенного шума

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

градиентов

3. Экспериментально проверить модификации SSTM в задачах оптимизации моделей распознавания изображений и обработки текста

Научная новизна

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

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

Теоретическая и практическая значимость работы

1. Теоретические результаты: Для случая невыпуклой оптимизации в условиях зашумленного оракула нулевого порядка и функции с гельдеровым градиентом получены оценки на сходимость метода на основе градиентного спуска со стохастической разностной оценкой градиента с помощью сглаживания нормальным распределением. Эти результаты расширили результаты работ [43] и [12]

2. Экспериментальные результаты: для случая выпуклой оптимизации проведены эксперименты с методами на основе SSTM. Для методов Clipped-SSTM проведены эксперименты как на синтетических данных, так и с реальными задачами классификации изображений и задачами из бенчмарка GLUE. Для методов ZO-clipped-SSTM и ZO-med-clipped-SSTM проведены эксперименты, показывающие преимущества этих методов в случае работы в условиях очень тяжелых хвостов распределений отклонений стох. градиентов. Проведены эксперименты с применением данных методов для обучения моделей архитектуры BERT

Методология и методы исследования

Для анализа невыпуклого случая, в диссертации используется постановка из [43], расширенная постановкой зашумленного оракула из [12]. Для анализа сходимости метода на основе градиентного спуска применяется аппарат сглаживания функций нормальными распределениями из [43]. Для полученного метода выводятся две оценки — в смысле сходимости по норме градиента исходной функции и норме градиента сглаженной, для которой показывается ее малое отличие (при правильном выборе параметра сглаживания ß) от исходной.

Для выпуклого случая и экспериментального подтверждения преимуществ методов Clipped-SSTM, ZO-clipped-SSTM и ZO-med-clipped-SSTM, они были реализованы на Python, после чего протестированы как на синтетических данных, так и на некоторых задачах бенчмарка GLUE [56] (для демонстрации случая тяжелых хвостов) и задачах классификации изображений (на задаче ImageNet-100).

Положения, выносимые на защиту

1. Для случая невыпуклой оптимизации — обобщение результатов работ [43] и [12] на случай наличия шума и переменной гладкости соответственно. Показана сходимость метода на основе градиентного спуска для такой постановки и получены оценки скорости сходимости и оценки на число вызовов оракула для достижения определенной точности по норме градиента, и норме градиента сглаженной функции

2. Для случая выпуклой оптимизации - многочисленные эксперименты с методами Clipped-SSTM (см. [26]), ZO-clipped-SSTM и ZO-med-clipped-SSTM (см. [1, 38]) демонстрирующие преимущество этих методов в постановках с тяжелыми хвостами распределений

Степень достоверности и апробация результатов

Результаты, представленные в диссертационной работе, были изложены на следующих конференциях и научных семинарах:

1. Kornilov N., Shamir O., Lobanov A., Dvinskikh D., Gasnikov A., Shibaev I., Gorbunov E.,

and Horvâth S. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance // Advances in Neural Information Processing Systems. — 2024.

Публикации

Результаты диссертации опубликованы в Optimization Letters и Journal of Optimization Theory and Applications индексируемых Scopus и Web of Science.

Структура диссертации

Работа состоит из введения, 3 глав, дополнительных материалов, заключения и списка литературы. Библиография состоит из 59 работ.

Глава 2

Разностные оценки и методы сглаживания

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

2.1 Предположения и решаемая задача

Рассмотрим некоторое выпуклое множество E С Rd. В данной работе мы рассматриваем задачу минимизации следующего вида

min f(x), (2.1.1)

xeE

где f : E С Rd ^ R, при этом мы предполагаем доступ к оракулу нулевого порядка f, необязательно совпадающего с f. Основные предположения которые будут использоваться в этой работе:

Предположение 1. Функция f дифференцируема и имеет гельдеров градиент, т.е. существует v £ [0,1] и Lv ^ 0 такие, что

\\Vf (y) - Vf (x)\\2 ^ Lv\\y - x\\v2, Ух, y £ E. (2.1.2)

Предположение 2. Функция f является ß сильно выпуклой, т.е. существует ß > 0 такое, что для любых x,y £ E

f (y) > f (x) + (Vf (x),y - x) + ß\\y - x\\l (2.1.3)

Если ß = 0, то функция f является выпуклой.

В некоторых случаях мы будем отдельно говорить о липшицовости функции или градиента, поэтому вынесем их отдельно:

Предположение 3. Функция f — липшицева, т.е. существует Ь0 ^ 0 такое, что

\\1 (у) - f (х)У ^ Ыу - х\\2, Ух,у Е Е. (2.1.4)

Предположение 4. Функция f липшицев градиент, т.е. существует Ь1 ^ 0 такое, что

\\Vf (у) - Vf (х) \\2 ^ ь1\у - х\2, Ух,у Е Е. (2.1.5)

Следствием Предположения 1 является:

f (у) < f (х) + (Vf (х),у - х) + ^\\у - х\\1+^, Ух,у Е Е. (2.1.6)

При V = 1 это условие есть липшицевость градиента f, при V = 0 (т.е. ограниченности изменения градиента) это дает и липшицевость самой функции. Остальные предположения более специфичны (в основном предположения о характере шума в /), и мы будем делать их в следующих частях.

Перейдем к оценкам рандомизированным оценкм градиента. Один из способов построения

к "

таких оценок — использовать разностную оценку градиента в точке хк по случайному направлению ик:

д(хк,ик) := / (хк + Тик) - /(хк) . ик

т

Для ик имеет смысл использовать центрально-симметричные распределения, например равномерное распределение на единичной сфере 54-1 = {х Е Е : \\х\\2 = 1} (к примеру [18, 27, 14]), или ик ~ N(0,1п) — сглаживание нормальным распределением, из работы [43]. Мы рассмотрим оценки на основе свертки с нормальным распределением, и с равномерным распределением на сфере. Общий вид рассматриваемых оценок приведен в Таблице 2.1.

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

Название Градиентная оценка g(x)

GSG, (Gaussian Smoothed Gradients) i £ f(X+Tui)-f(x)ui, u ^ n(0,id) i=1

BSG, (Ball Smoothed Gradients) d £ f(X+TU)-f(X) иг, иг ^U S-1) Г i=1 T

cBSG, (centered Ball Smoothed Gradients) d r f(x+TU)- f(x-TU)иг, иг „ U (Sd-1) Г i=1 T

2.2 Сглаживание нормальным распределением

2.2.1 Определения

Сглаживание нормальным распределением будет использоваться в этой работе для получения оценок в невыпуклом случае. Начнем с определения из [43]:

Определение 2.2.1. Рассмотрим функцию f : Е ^ М. Назовем сглаженной нормальным распределением функцией ¡Т (х) следующую:

¡г (х) = 1 [/ (х + ти)е-1 |Н|2 ¿и, (2.2.1)

к ]

Е

где

к е-1М2 ¿и = (2п)Л/2. (2.2.2)

Е

Т.е. сглаженная функция ¡Т(х) есть свертка исходной функции ¡ с нормальным распределением с дисперсией т (можно получить заменой переменной и' := ти). Можно показать (раздел 2 из [43]), что

УЛ(х) = 1 [ ¡(Х + Ти) ~ ¡(Х) е-1 И'2Ыи (2.2.3)

кт

Е

= 1 Г ¡х^и!е-1И«"2или (2.2.4)

кт

ЕЕ

У¡(х) = К У(У¡(х),и)е-2||ад"2или, (2.2.5)

Е

здесь последнее неравенство выполняется если ¡(х) дифференцируема в точке х. Если ¡ дифференцируема на Е, то

У ¡т(х) = - [ У¡(х + ти)е-1 |Н|2¿и. (2.2.6)

к

Е

Так как мы имеем доступ не к самой оптимизируемой функции ¡, но к оракулу ¡ , мы обозначим ¡т сглаженную нормальным распределением функцию ¡ :

Нт(х) = 1 [ Нх + ти)е-1 |Н|2¿и. (2.2.7)

к

Аналогичным образом мы определим и вектор, который будет играть роль "градиента" и т:

Ш = 1 [ f (Х + ТЦ) ~ /(х) е"IИРили (2.2.8)

к

Е

1Ч ^И^ е" 2 и2 ийи. (2.2.9)

к з т

Е

Важно ответить, что в общем случаем для и т не верна форма вида (2.2.6) т.к. f не обязательно является даже непрерывной, не то что дифференцируемой (к примеру в случае ограниченного, но случайного шума).

2.2.2 Cвойства

Как показано в лемме 3 из [43], для f (х) с липшицевым градиентом верно

\\VfT(х) -ъи(х)|| ^ ^& + 3)3/2.

Этот результат можно обобщить на случай ограниченного (Предположение 5 которое мы будем использовать для невыпуклого случая) шума (А.1 в [4])

г

\\У!т(х,5) -Ъи(х)\\ ^ -й1/2 + тЬ^2.

т

Обобщая это на случай функций с гельдеровым градиентом можно получить следующий результат Лемма 2.2.1. В условии Предположений 1 и 5 верно следующее

г

\\VMx,-) -Ъ^(х)\\ ^ -¿1/2

т

\\VfT(х) -ъи(х)\\ ^ т*Ь

и, следовательно,

г

\\ЪМх,-) -ъи(х)\\ ^ -й1/2 + тиЬ„йи/2. (2.2.10)

т

Доказательство. В дополнительных материалах.

■

Можно показать (в условии Предположения 3), что и т имеет липшицев градиент с Ь = ^¿Ьо/т (Лемма 2 из [43]). В таком случае можно получить следующее неравенство

и (у) - и (х) - (ъи (х),у - х)\ ^ Ь\\х - У\?- (2.2.11)

Если предположить более общее условие гельдеровости градиента то можно получить обобщенную версию неравенства (2.2.11)

Лемма 2.2.2. В условии Предположения 1 верно, что

\Ит (у) - ¡т (х) - (У ¡Г (х),У - х)\ ^ А\\У - х||2 + А2,

где А1 и А2 можно взять равными

Ьи 1+К. А! = —— й 2 , А2 = 0,

1 _1_V ' 2 '

т

или, если дополнительно выполнено Предположение 5

А1 =

Доказательство. В дополнительных материалах.

1-v

l+v 2Ту - -

^, А2 = 5 Ьит 1±V где Н > 0,

1 — V

т1

Одно из самых важных свойств сглаженной функции ¡Т (х) это то, что она дает хорошую аппроксимацию функции И. К примеру, если выполнено Предположение 3 то можно показать (Теорема 1 из [43]), что

\Ит (х) - И (х)\ ^ тЬод1'2. Аналогично предыдущим леммам, это свойство можно обобщить на случай гельдеровости Лемма 2.2.3. Пусть верно Предположение 1, тогда

\Ит (х) - И (х)\ < т ^ л ^ .

1 + V

Доказательство. В дополнительных материалах.

■

Следствием Леммы 2.2.1 является оценка которая связывает норму градиента И и его сглаженной ¡т. В дальнейшем мы используем это чтобы получить скорость сходимости по норме градиента исходной функции по соответствующей скорости сходимости по градиенту сглаженной.

Лемма 2.2.4. Пусть верно Предположение 1, тогда

\\УИ(х)||2 ^ 2\\УИт(х)||2 + 2т^Ь1 ¿V.

Доказательство. В дополнительных материалах.

2.3 Сглаживание равномерным распределением на шаре 2.3.1 Определения

Аналогично сглаживанию нормальным распределением, сглаживание распределением на сфере вводится как свертка [16, 46, 41, 43, 53]

Определение 2.3.1. Рассмотрим функцию И : Е ^ К. Назовем сглаженной равномерным распределением на сфере функцией Ит (х) следующую:

Ит(х) = 1 I И(х + ти)йи, (2.3.1)

к I

в*

где Bf; — единичный d-мерный шар, и

к = i e-fМ2du = - (2.3.2)

J г (f + 1) ' '

Далее рассматривается разностная оценка градиента вида

d

9(x, е) = —U(x + те) - f (x - те)е (2.3.3)

2т

2.3.2 Свойства

Следующий результат обобщает Теорему 2.1 из [46] на случай функций с гельдеровым градиентом

Лемма 2.3.1 (Свойства функции fT). Рассмотрим множество E С Rd и т > 0 такие, что 1 и 2 выполнены на ET = E + тВ%. Тогда,

1. Функция fT является /i-сильно выпуклой, и для нее верно

sup \!t(x) - f (x)\< т1+v

x£E 1 + v

2. Функция fT (x) дифференцируема на E и ее градиент имеет следующий вид

Vfr (x) = E

^ и (Sd

сфере

¿И (х + т е)е т

где е ~ и(Б%) случайный вектор равномерно распределенный на единичной евклидовой

3. Для функции fT (x) выполнено следующее

WVfr (x) - VfT (y)h < ^»/т\\y - x||2 • (r + 1 \\y - x|h) ,

в частности, при v = 0 (липшицева функция f) f T имеет Липшицев градиент с L = ^Ли/ на E.

Доказательство. 1. ^-сильно выпуклость следует из доказательства первого пункта теоремы 2.1 из [46]. Неравенство можно показать следующим образом:

IfT(x) - f(x)\ = |Eu[f(x + ru) - f(x) - (Vf(x),ru)]\ ^ Eu\\tu\\1+v = r 1+v

1 + v 1 + v

2. Аналогично, второй пункт является следствием теоремы 2.1 из [46]

3. Для доказательства третьего пункта в начале модифицируем лемму 11 из [11]:

E[g(Z) - g(y + Z)] = j g(z)r (z)dz - J g(y + z)r (z )dz

= j g(z)r(z)dz - j g(z)r(z - y)dz = g(z)[r(z) - r(z - y)\dz - g(z)[r(z - y) - r(z)]dz

JI> Ji<

где I> = {z E Rd\r(z) > r(z - y} и I< = {z E Rd\r(z) < r(z - y}. Таким образом

\\E[g(Z) - g(y + Z)]\\< sup \\g(z)\\ i [r(z) - r(z - y)]dz -f [r(z - y) - r(z)]dz

z€l>L)I< J I> JI<

= sup \\g(z)\ \r(z) - r(z - y)ldz

z&I>UI< J

В теореме 2.1 затем используется тот факт, что sup \\g(z) \\ ^ L1 (что является следствием

Z£I>UI<

выпуклости и липшицевости функции f). Вместо этого, повторим доказательство третьего пункта теоремы 2.1 [46] но не будем подставлять это значение сразу:

\\VfT(y) - VfT(x)\\ = \\(VfT(y) - Vf(^)) - (VfT(x) - Vf(^)\\

< sup Wg^W \r(z - y) - r(z - x)\dz

z&I>Ul< J

< sup Hg^H^/T\\y - x\ \2

z€l>L)I<

где g(z) = VfT(z) - Vf (Xj^) где z E rS%(x) U rS%(y) — объединение шаров вокруг точек x и y. Тогда, пользуясь тем что (из гельдеровости градиента)

\\Vf (y + ru) - Vf (^)\\ ^ Lv\\ru + — \\v ^ Lv(r + \\—\\)v \\Vf (x + ru) - Vf (^)\\ ^ Lv\\ru + ^\\v ^ Lv(r + \\—\\)v

мы получаем, что

\\Ч/т (х) -Ч/т (У)У < *ир \Ш\\^/т\\у - х||2

г€1>и1<

< ^Чт\\у - х\2 • (т + 2\\у - х\\2^

Глава 3

Результаты для невыпуклого случая

В данном разделе приведены результаты работы [52]. Мы рассматриваем задачу оптимизации невыпуклой функции f, в условиях Предположения 1 и, дополнительно

Предположение 5. Для функции f (x) есть неточный оракул нулевого порядка f (x) = f (x,8) с некоторым 8 > 0 т.е. существует 8 > 0 и можно вычислить f(x, 8) Е R такую, что для любых x Е E выполнено

\f(x) - f(x,8)\ ^ 8. (3.0.1)

т.е. предположение об оракуле с ограниченным шумом. Мы рассматриваем градиентный спуск, в котором вместо градиента используется разностная оценка GSG (см. таблицу 2.1) с r = 1, в которой вместо f используется f т.е. оценку градиента следующего вида

/ еч f(x + ти,8) - I(x,8) (3 0 2)

gT (x,u,8) =-и, (3.0.2)

т

и градиентный спуск, в котором градиент заменен этой оценкой. Таким образом итоговый алгоритм имеет следующий вид:

Algorithm 1 (ZO-GD, рандомизированная оценка GSG) Require: Начальная точка x0, число итераций N, длины шагов {hi}i=0N-1 1: for k = 0,1,...,N - 1 do

2: Сгенерировать случайный вектор uk ~ N(0, In) 3: xk+1 = xk - hk • gT(xk,u,8) 4: end for Ensure: xN

Для следующих частей нам понадобится еще одна лемма:

Лемма 3.0.1. В условиях предположений 1 и 5 для градиентной оценки (3.0.2) верно

[\\дт(x, u, 8) ||2] ^ 20(d + 4)\\V fT(x) ||2+

+ 4 482 d +-4^2 т2V d2+v + ^ (d + 6)3 + A

V т2 (1 + V)2 4 4 ' т2

где A1} A2 это те же константы Л1} A2 из Леммы 2.2.2. Доказательство. В дополнительных материалах.

3.1 Анализ сходимости

Мы рассматриваем градиентный спуск вида

xk+1 = xk - hkдт(xk,uk,8), (3.1.1)

где uk это случайный нормальный вектор дт(xk, uk, 8) определен выше в (3.0.2). Мы рассмотрим два вида сходимости — \\ V f (xk) \\ и \\ V fT (xk) \\ . Начнем с доказательства следующего результата

Лемма 3.1.1. Рассмотрим процесс (3.1.1). В предположениях 1 и 5 то можно показать, что после N - 1 шага

min E гш f ( 21 ^ 320(d + 4)Af (xo) - f *) + (319)

^N-1} Eu \ \ \ VfT(xk) \ \] ^-nd-+ (3.1.2)

+ ^ (482 d+ т 2V d2+v + iW d+6)3 + A2 d) + + 4(d + 4)V т2 ( +(1 + v)2т d + 4 (d + 6) + т2 d) +

320(d + 4)A1 ( . 82 82

+ D \2 + 2^ d + т-2 d

где U = (u0, ...,uN-1) это случайный вектор из i.i.d. {ukA1}A2 и A^,, A2 это независимые пары констант из Леммы 2.2.2 и D Е (0,1].

Доказательство. Из Леммы 2.2.1, Леммы 2.2.2 и того факта, что ab ^ + jC где C > 0, a =

\ \ y - x \ \ и b = ^ и1'2 мы получаем

\It (У) - It (x) -(VIt (x, 8),y - x)\ ^

< \It (У) - It (x) -(V It (x),y - x)\ + \(V f t (x, 8) -V It (x),y - x)\ ^

^ V \\ y - x \\ 2 + A2 + V2 \\ y - x \ \ ^ 2 т

^ (A + C) \\У - x\\2 + A2 + ^d C =A1 A1 \\y - x\\2 + (A + ^d

Рассмотрим процесс (3.1.1). Подставив его (у := хк+г) и (3.0.2) в неравенство выше, и взяв матожидание по ик приходим к

^ [¡г(хк+г)] ^ ¡т(хк) - Нк\\Ч?т(хк,Ь)\\2 + Н2кА{Еик [\\дт(хк,ик,Ь)\\2] +

+ М2 +2АТ2 d

Теперь, воспользуемся тем (из (а + Ь)2 ^ 2а2 + 2Ь2), что

V¡т(х)\\2 ^ 2\\Ч¡т(х,8)\\2 + 2\\Ч¡т(х) - VIт(х,8)\\2 ^

^ 2№¡т(х,5)\\2 + 2 • -21

т 2

подставляя это в предыдущее неравенство получаем

Е„к [¡т(хк+г)} < ¡т(хк) - ^ т(хк)\\2 + Ь1 ЛгЕ^ [\\дт(хк,Ь)\\2] +

^ и т7 { (х ) II2 | к2

(а Ь2 , & , + [Л2 +2АТ~21 + Т21

Подставляя результат Леммы 3.0.1 (мы переименовываем константы из этой леммы в Л'г, Л2 т.к. это новая пара констант, и ее можно будет позже выбрать независимо от Лг, Л2) приходим к

Еик [¡т(хк+г)] < ¡т(хк) - (у - 20(1 + 4)ккЛ^ ^¡т(хк)\\2+

+ к2кЛг • 5 1 т2»12+» + ТМ1(1 + 6)3 + ^^ +

к \т2 (1 + и )2 4 К т2 )

Л ь2 * Ь2 x

+ \Л2 + 2ЛГ21+Т2 V-

Выберем к = кк = 80(п1В4)А1 где П е (0,1], тогда

Еик [¡т(хк+г)] < ¡т(хк) - 320{1°+ А)А1 т(хк)\\2+

5Б2 (4Ь2 4Ь2 2„ ,2+„ г2(Л\)2 Л)2 Л

(л Ь2 Ь2

+ [Л2 +21^2 1 + Т-2 1

и, после суммирования по всем итерациям и взятию матожидания по и получаем

п м-г

Ей [¡т(хм)] ^ ¡т(хо) - Ш{1 + 4)А^ Е [^¡т(хк)\\2] +

5МБ2 (462 4Ь2 2„ ,2+„ г2(Л'1)2 Л)2 и

+ л^Щ^К ^1 + (ГГ^т 1 +4 (1 + 6) 1 > +

ът, л Ь2 ^ ,

+ М{Л2 + 2^2 1 + ^ 1

Осталось переставить слагаемые, и применить тот факт, что f * < EU [fT (xN)] и мы приходим к (3.1.2).

■

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

3.1.1 Сходимость в смысле 11V f (xk) \ \

Теорема 3.1.1. Рассмотрим процесс (3.1.1) в Предположениях 1 и 5. Предположим, что мы хотим чтобы после N шагов было выполнено

min Eu [ \ \ Vf (xk) \ \ 2] < £Vf

k£{U,N — 1}

тогда можно показать, что при правильном выборе параметра сглаживания т это неравенство выполнится за

( d2+—

N = O I | (3.1.3)

V £w

шагов градиентного спуска (3.1.1) при условии, что уровень шума ограничен следующим образом

— ( £ ^

= O [-f | . (3.1.4)

d 4 \d

Доказательство. Воспользуемся Леммой 2.2.4 чтобы перейти от нормы градиента исходной функции к норме градиента сглаженной, а затем используем Лемму 3.1.1

Lern. 2.2.4 (3.1.2)

Eu [ \ \ Vf (x) \ \ 2 < ^1} (2EU [ \ \ VfT (x) \ \2] + 2t2v Li<f) <

< 640(d + 4)Af(x0) - f*) +

< ND +

D fA52 4L2 2v j2+v t2(a1)2 ,3 (A2)2 \

+ W+T){ ^d + HTV? Т 2 d + ^(d + 6) d) +

+ A + At~2 d + 72d) + 2t2VL2dv.

Как мы видим, наибольшая степень т которую мы можем здесь получить это 2v, поэтому выбор нефиксированных параметров будем делать на основе этого. Рассмотрим случай A1 =

1-v

—d^, A2 = 0 и A1 = | 1+v 2-7, Л!2 = 5Lvт1+v с S = (d + 6) (параметры выбраны так,

T

чтобы выравнять степень d во втором слагаемом):

^ Mm WiK 640("+f- f ) * * + (3.1.5)

/ Л£2 лт2 \

+ тТ){ ^d + â+iï d2+" + L2 (* + 6\+" + L2 *(* + 6)1+") +

+ mt+iK лъ f() + fv * + + 2^Lld».

dt 1-v \ 2Lvdl+ тt2 ) v

Теперь остались только слагаемые с т2 и слагаемые с 82 и некоторой степенью т. Чтобы ослабить предположения на шум 8 рассмотрим максимальное возможное D = 1. Тогда ограничение на 8 примет вид 6 ^ de, где а = (это следует из третьего слагаемого, мы хотим выравнять т2a-(1-v)-2 и т2v) и в = 3-Е — они выбраны такими, чтобы выравнять степени d во втором (dl+v)

Список литературы диссертационного исследования кандидат наук Шибаев Иннокентий Андреевич, 2024 год

Литература

[1] Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance / Kornilov N., Shamir O., Lobanov A., Dvinskikh D., Gasnikov A., Shibaev I., Gorbunov E., and Horvath S. // Advances in Neural Information Processing Systems. —2023. — Vol. 36.—P. 64083-64102.

[2] Baydin A., Pearlmutter B., Radul A., Siskind J. Automatic differentiation in machine learning: A survey // Journal of Machine Learning Research. —2018. — Vol. 18. —P. 1-43.

[3] Bennett G. Probability inequalities for the sum of independent random variables // Journal of the American Statistical Association. — 1962. — Vol. 57, no. 297. —P. 33-45.

[4] Berahas A., Cao L., Choromanski K., Scheinberg K. A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization // Foundations of Computational Mathematics. — 2021. — Vol. 22. — P. 507-560.

[5] Bergou E. H., Gorbunov E., Richtarik P. Stochastic Three Points Method for Unconstrained Smooth Minimization // SIAM Journal on Optimization. —2020. —Vol. 30, no. 4. —P. 2726-2749.

[6] Bolte J., Glaudin L., Pauwels E., Serrurier M. A Hölderian backtracking method for min-max and min-min problems. — 2020. — arxiv.org/abs/2007.08810.

[7] Brent R. Algorithms for Minimization Without Derivatives. Dover Books on Mathematics. — Dover Publications, 1973. —ISBN: 9780486419985.

[8] Chaux C., Combettes P. L., Pesquet J.-C., Wajs V. R. A variational formulation for frame-based inverse problems // Inverse Problems. — 2007. — June. — Vol. 23, no. 4. —P. 1495-1518.

[9] Conn A. R., Scheinberg K., Vicente L. N. Introduction to Derivative-Free Optimization. — Society for Industrial and Applied Mathematics, 2009. — ISBN: 9780898718768.

[10] Cutkosky A., Mehta H. High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails // Advances in Neural Information Processing Systems. — 2021. — Vol. 34. — P. 4883-4895.

[11] Duchi J. C., Bartlett P. L., Wainwright M. J. Randomized Smoothing for Stochastic Optimization // SIAM Journal on Optimization. —2012. — Vol. 22, no. 2. — P. 674-701.

[12] Dvurechensky P. Gradient Method With Inexact Oracle for Composite Non-Convex Optimization // Computer Research and Modeling. — 2022. — Vol. 14, no. 2.—P. 321-334.

[13] Dvurechensky P., Gasnikov A. Stochastic intermediate gradient method for convex problems with stochastic inexact oracle // Journal of Optimization Theory and Applications. — 2016. — Vol. 171, no. 1.—P. 121-145.

[14] Dvurechensky P., Gorbunov E., Gasnikov A. An accelerated directional derivative method for smooth stochastic convex optimization // European Journal of Operational Research. —2021. — Vol. 290, no. 2. — P. 601-621.

[15] DzhaparidzeK., VanZanten J. On Bernstein-type inequalities for martingales// Stochastic processes and their applications. — 2001. — Vol. 93, no. 1. — P. 109-117.

[16] Ermoliev Y. Stochastic programming methods. — 1976.

[17] Fabian V. Stochastic Approximation of Minima with Improved Asymptotic Speed // The Annals of Mathematical Statistics. — 1967. — Vol. 38, no. 1. — P. 191-200.

[18] Flaxman A. D., Kalai A. T., McMahan H. B. Online Convex Optimization in the Bandit Setting: Gradient Descent Without a Gradient // Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. —2005. — SODA '05. — P. 385-394.

[19] Freedman D. A. et al. On tail probabilities for martingales // the Annals of Probability. — 1975. — Vol. 3, no. 1.—P. 100-118.

[20] Gasnikov A. V., Nesterov Y. E. Universal method for stochastic composite optimization problems // Computational Mathematics and Mathematical Physics. — 2018. —Vol. 58. —P. 48-64.

[21] Generative Adversarial Nets / Goodfellow I., Pouget-Abadie J., Mirza M., Xu B., Warde-Farley D., Ozair S., Courville A., and Bengio Y. // Advances in Neural Information Processing Systems. — 2014. — Vol. 27. — P. 2672-2680.

[22] Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework // SIAM Journal on Optimization. — 2012. —Vol. 22, no. 4.—P. 1469-1492.

[23] Ghadimi S., Lan G. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming // SIAM Journal on Optimization. — 2013. — Vol. 23, no. 4. —P. 2341-2368.

[24] Gorbunov E., Danilova M., Dobre D. et al. Clipped stochastic methods for variational inequalities with heavy-tailed noise // Advances in Neural Information Processing Systems. — 2022. — Vol. 35.—P. 31319-31332.

[25] Gorbunov E., Danilova M., Gasnikov A. Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping // Advances in Neural Information Processing Systems. — 2020. — Vol. 33.—P. 15042-15053.

[26] Gorbunov E., Danilova M., Shibaev I. et al. High-Probability Complexity Bounds for Non-smooth Stochastic Convex Optimization with Heavy-Tailed Noise // Journal of Optimization Theory and Applications. — 2024. — 10. — P. 1-60.

[27] Gorbunov E., Dvurechensky P., Gasnikov A. An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization // SIAM Journal on Optimization. — 2022. —Vol. 32, no. 2. — P. 1210-1238.

[28] Gorbunov E. A., Bibi A., Sener O. et al. A Stochastic Derivative Free Optimization Method with Momentum // ICLR. — 2020.

[29] Granichin O., Polyak B. Randomized Algorithms of an Estimation and Optimization Under Almost Arbitrary Noises // M.: Nauka. — 2003.

[30] Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization // Journal of Complexity. — 2015. — Vol. 31, no. 1. —P. 1-14.

[31] High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance / Sadiev A., Danilova M., Gorbunov E., Horvath S., Gidel G., Dvurechensky P., Gasnikov A., and Richtarik P. // Proceedings of the 40th International Conference on Machine Learning. — 2023. — ICML'23.

[32] ImageNet Large Scale Visual Recognition Challenge / Russakovsky O., Deng J., Su H., Krause J., Satheesh S., Ma S., Huang Z., Karpathy A., Khosla A., Bernstein M., Berg A. C., and Fei-Fei L. // International Journal of Computer Vision (IJCV). — 2015. — Vol. 115, no. 3. —P. 211-252.

[33] Kim K., Nesterov Y., Skokov V., Cherkasskii B. Efficient algorithm for calculation of derivatives and extreme problems // Ekonomika i matematicheskie metody. — 1984. — Vol. 20, no. 2. — P. 309-318.

[34] Lan G. An optimal method for stochastic composite optimization // Mathematical Programming. — 2012. —Vol. 133, no. 1-2.—P. 365-397.

[35] Language models are few-shot learners / Brown T., Mann B., Ryder N., Subbiah M., Kaplan J. D., Dhariwal P., Neelakantan A., Shyam P., Sastry G., Askell A., et al. // Advances in neural information processing systems. —2020. — Vol. 33. —P. 1877-1901.

[36] Larson J., Menickelly M., Wild S. M. Derivative-free optimization methods // Acta Numerica. — 2019. —Vol. 28.—P. 287-404.

[37] Malik D., Pananjady A., Bhatia K. et al. Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems // Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. — 2019. —Vol. 89 of Proceedings of Machine Learning Research. —P. 2916-2925.

[38] Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi Arm Bandit Problem with Heavy-tailed Symmetric Noise / Kornilov N., Dorn Y., Lobanov A., Kutuzov N., Shibaev I., Gorbunov E. A., Gasnikov A. V., and Nazin A. — 2024. — Access mode: https://api.semanticscholar.org/CorpusID:267411971.

[39] Nelder J. A., Mead R. A simplex method for function minimization // The computer journal. — 1965. —Vol. 7, no. 4.—P. 308-313.

[40] Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust stochastic approximation approach to stochastic programming // SIAM Journal on optimization. — 2009. — Vol. 19, no. 4. — P. 1574-1609.

[41] Nemirovskij A. S., Yudin D. B. Problem complexity and method efficiency in optimization. — John Wiley & Sons, 1983. —ISBN: 9780471103455.

[42] Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming.—2015. —Vol. 152, no. 1.—P. 381-404.

[43] Nesterov Y., Spokoiny V. Random Gradient-Free Minimization of Convex Functions // Foundations of Computational Mathematics. — 2015. —Nov. — Vol. 17, no. 2. —P. 527-566.

[44] Nguyen T. D., Ene A., Nguyen H. L. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails // arXiv preprint arXiv:2304.01119. —2023.

[45] Papernot N., McDaniel P., Goodfellow I. et al. Practical Black-Box Attacks against Machine Learning // Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. —2017. —ASIA CCS '17.—P. 506-519.

[46] The power of first-order smooth optimization for black-box non-smooth problems / Gasnikov A., Novitskii A., Novitskii V., Abdukhakimov F., Kamzolov D., Beznosikov A., Takac M., Dvurechensky P., and Gu B. // International Conference on Machine Learning. — PMLR. — 2022. — Vol. 162 of Proceedings of Machine Learning Research. —P. 7241-7265.

[47] Puchkin N., Gorbunov E., Kutuzov N., Gasnikov A. Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems // Proceedings of The 27th International Conference on Artificial Intelligence and Statistics. — PMLR. —2024. —Vol. 238 of Proceedings of Machine Learning Research.—P. 856-864.

[48] PyTorch: An Imperative Style, High-Performance Deep Learning Library / Paszke A., Gross S., Massa F., Lerer A., Bradbury J., Chanan G., Killeen T., Lin Z., Gimelshein N., Antiga L., Desmaison A., Kopf A., Yang E., DeVito Z., Raison M., Tejani A., Chilamkurthy S., Steiner B., Fang L., Bai J., and Chintala S. // Advances in Neural Information Processing Systems 32. — 2019. — P. 8024-8035. — Access mode: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.

[49] Rosenbrock H. H. An Automatic Method for Finding the Greatest or Least Value of a Function // The Computer Journal. — 1960. — Vol. 3, no. 3. —P. 175-184.

[50] Saeed Ghadimi G. L., Zhang H. Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization // Mathematical Programming. — 2013. — Vol. 155.

[51] Schumer M., Steiglitz K. Adaptive step size random search // IEEE Transactions on Automatic Control. — 1968. — Vol. 13, no. 3. —P. 270-276.

[52] Shibaev I., Dvurechensky P., Gasnikov A. Zeroth-order methods for noisy Holder-gradient functions // Optimization Letters. — 2022. — Sep. — Vol. 16.

[53] Spall J. C. Introduction to Stochastic Search and Optimization. — 1 ed. — John Wiley & Sons, 2003. —ISBN: 0471330523.

[54] Sutton R. S., Barto A. G. Reinforcement learning: An introduction. — MIT press, 2018. — ISBN: 0262039249.

[55] Transformers: State-of-the-Art Natural Language Processing / Wolf T., Debut L., Sanh V., Chaumond J., Delangue C., Moi A., Cistac P., Rault T., Louf R., Funtowicz M., Davison J., Shleifer S., von Platen P., Ma C., Jernite Y., Plu J., Xu C., Scao T. L., Gugger S., Drame M., Lhoest Q., and Rush A. M. // Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. — Online : Association for Computational Linguistics. — 2020. — P. 38-45. — Access mode: https://www.aclweb.org/anthology/2020.emnlp-demos.6.

[56] Wang A., Singh A., Michael J. et al. GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding // Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. — Association for Computational Linguistics. — 2018. —P. 353-355. — Access mode: https://aclanthology.org/W18-5446.

[57] Wang J., Liu Y., Li B. Reinforcement Learning with Perturbed Rewards // Proceedings of the AAAI Conference on Artificial Intelligence. — 2020. — Vol. 34. — P. 6202-6209.

[58] Warstadt A., Singh A., Bowman S. R. Neural Network Acceptability Judgments // Transactions of the Association for Computational Linguistics. — 2019. — Vol. 7. — P. 625-641. — Access mode: https://aclanthology. org/Q19-1040.

[59] Why are adaptive methods good for attention models? / Zhang J., Karimireddy S. P., Veit A., Kim S., Reddi S., Kumar S., and Sra S. // Advances in Neural Information Processing Systems. — 2020. — Vol. 33.—P. 15383-15393.