Ускоренный метаалгоритм и его приложения тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Матюхин Владислав Вячеславович

• Матюхин Владислав Вячеславович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Матюхин Владислав Вячеславович

Введение

Глава 1. Адаптивный Каталист для гладкой выпуклой

оптимизации

1.1 Основная схема

1.2 Приложения

1.2.1 Наискорейший спуск

1.2.2 Рандомизированный адаптивный координатный спуск

1.2.3 Чередующаяся минимизация

1.2.4 Локальный стохастический градиентный спуск

1.2.5 Теоретическое обоснование

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

1.3.1 Ускорение наискорейшего спуска

1.3.2 Ускорение ИЛСЭМ

1.3.3 Переменное ускорение методом наименьших квадратов

1.3.4 Ускорение локального стохастического градиентного спуска

Глава 2. Ускоренный метаалгоритм и его приложения

2.1 Основные результаты

2.2 Ускоренные методы композитной оптимизации

2.3 Ускоренные проксимальные методы. Каталист

2.4 Разделение оракульных сложностей

2.5 Ускоренные методы для седловых задач

2.6 Сравнение с алгоритмом Монтейро-Свайтера

2.7 Возможные обобщения

Глава 3. Ускоренные проксимальные оболочки: применение к

покомпонентому методу

3.1 Ускоренный метаалгоритм и координатный спуск

3.1.1 Теоретическое обоснование

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

3.1.3 Приложение к оптимизации марковских процессов принятия решений

Стр.

Глава 4. Выпуклая оптимизация с неточными градиентами в гильбертовом пространстве и приложения к

эллиптическим обратным задачам

4.1 Основные предположения

4.1.1 Техника рестартов

4.1.2 Градиентный спуск

4.1.3 Концепция неточного градиентного оракула Деволдера-Глинера-Нестерова

4.1.4 Заключительные замечания и примеры

4.2 Двойственные методы

4.3 Условие остановки для БХЫ

4.4 Численные результаты

Заключение

Список литературы

Список рисунков

Список таблиц

Введение

Методы оптимизации являются основным компонентом в современной вычислительной математике. Во многих случаях итерационные алгоритмы для решения задач выпуклой оптимизации достигли уровня эффективности и надежности, сравнимого с передовыми процедурами линейной алгебры. Это в значительной степени верно для задач среднего масштаба, где безраздельно господствуют методы внутренней точки, но в меньшей степени для крупномасштабных задач, где сложность методов первого порядка не так хорошо понятна, а эффективность остается проблемой. В последние годы ситуация заметно улучшилась, в частности, благодаря появлению ряда приложений в области статистики, машинного обучения и обработки сигналов. Основываясь на алгоритме Нестерова, созданном в 80-х годах, было разработано множество ускоренных методов [1] и численных схем, которые как повышают эффективность алгоритмов оптимизации для различных постановок задач, так и уточняют границы их сложности. Но каждый такой случай требовал особого рассмотрения возможности ускорения. Поэтому предложенные конструкции существенно различались и не позволяли предположить способ их обобщения. Существенным шагом к разработке универсальной схемы ускорения методов оптимизации стала работа, в которой был предложен алгоритм под названием Catalyst (каталист), основанный на идее [2; 3] и позволяющий ускорить другие методы оптимизации, используя их для последовательного решения нескольких регуляризованных вспомогательных задач Моро-Иосиды [4; 5]. Вдохновившись этими представлениями, было предложено множество вариантов применения этого метода и его модификаций [6—9]. Среди последних результатов на данный момент также были описаны обобщения обсуждаемого подхода к тензорным методам [10—13]. Соответствующая форма ускоренной проксимальной оболочки, насколько известно, является наиболее общей из описанных в литературе.

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

Цели работы

1. Исследовать ускоренные методы оптимизации, основанные на идее Ка-талист, и обобщить их в дальнейшем

2. Исследовать ускоренные методы выпуклой оптимизации с неточными градиентами в гильбертовом пространстве

3. Примененить универсальные проксимальные оболочки для получения вычислительно эффективных ускоренных методов

Научная новизна. В работе представлена общая структура, которая позволяет ускорить почти произвольные неускоренные детерминированные и рандомизированные алгоритмы для решения задач гладкой выпуклой оптимизации. Основной подход оболочки такой же, как и в Catalyst [4]: метод ускоренного проксимального внешнего градиента, который используется в качестве оболочки для неускоренного внутреннего метода для £2-регуляризованной вспомогательной задачи. Предложенный алгоритм имеет два ключевых отличия: 1) легко проверяемое условие остановки для внутреннего алгоритма; 2) параметр регуляризации, настраиваемый в ходе выполнения. Основной результат работы — новая структура, которая применяется к адаптивным внутренним алгоритмам: наискорейший спуск, адаптивный координатный спуск, чередующаяся минимизация. Более того, в неадаптивном случае данный подход позволяет получить Catalyst без логарифмического множителя, который фигурирует в стандартном Catalyst [4; 5].

Другим важным результатом этой работы является адаптивный выбор параметра сглаживания. Поскольку предложенный подход требует двух входных параметров (это нижняя граница Ld и верхняя граница Lu для неизвестного параметра гладкости L), вряд ли его можно назвать «адаптивным». Причем, чем больше расхождение между этими двумя параметрами, тем более достойной кажется наша адаптивная оболочка в теории. Но почти все эксперименты демонстрируют низкую чувствительность к этим параметрам, а не к реальному параметру гладкости. Но даже для такой «безлогарифмической» и адаптивной оболочки ожидается, что прямые адаптивные ускоренные методы будут работать лучше, чем их аналоги типа Catalyst.

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

Предложен метод проксимально-ускоренного координатного спуска, обеспечивающий эффективную алгоритмическую сложность итерации и позволяющий использовать преимущества разреженных данных. Рассмотрен пример применения предложенного подхода к оптимизации SoftMax-подобной функции: для неё описан метод, позволяющий ослабить зависимость вычислительной сложности от размерности п в О (у/и) раз и на практике демонстрирующий более быструю сходимость по сравнению со стандартными методами. В качестве примера применения предложенного подхода показан вариант получения на его основе эффективных методов оптимизации марковских процессов принятия решений (МПР) в минимаксной постановке со сглаженной по Нестерову целевой функцией.

Вслед за исследованиями [14—16] в работе предложены новые подходы к решению задач выпуклой оптимизации в гильбертовом пространстве [17; 18]. Главное отличие от существующих подходов состоит в том, что в работе не аппроксимируется бесконечномерная задача конечномерной (см. [14; 16]). В работе решена задача в гильбертовом пространстве (бесконечномерном), но через концепцию неточного оракула. То есть аппроксимация используется только тогда, когда вычисляется градиент (производную Фреше) функционала. Это создает неточность при вычислении градиента. В работе предприняты попытки объединить все известные результаты в этой области и найти наилучший способ решения задач выпуклой оптимизации в Гильбертовом пространстве в приложении к некорректным и обратным задачам [15].

В результате получено условие остановки для STM, для случая аддитивного шума в градиенте. Этот результат можно кратко сформулировать следующим образом: в случае Ь-неточного градиента (неточность аддитивна) градиентный спуск и ускоренный градиентный спуск (рассматриваем STM) сходятся почти как их аналоги без добавления шума (с точностью до функции ~ ЬЯ, где Я — характерный размер решения). После достижения этой точности алгоритм необходимо остановить во избежание накопления ошибки и расхождения метода [19]. Этот результат выглядит довольно неожиданно для ускоренных алгоритмов из-за достаточно плохих результатов, упомянутых в разделе 3, а именно накопления ошибки при другом способе задания шума.

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

- International conference "Quasilinear Equations, Inverse Problems and their Applications"(QIPA) 2022;

- International Conference Mathematical Optimization Theory and Operations Research (MOTOR) 2021;

- International conference "Optimization without borders"2021;

- 63-я конференция МФТИ 2020;

- International conference "Quasilinear Equations, Inverse Problems and their Applications"(QIPA) 2019.

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

Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 5 - в периодических научных журналах, индексируемых Web of Science и Scopus.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 0 приложений. Полный объём диссертации составляет 109 страниц, включая 22 рисунка и 5 таблиц. Список литературы содержит 113 наименований.

Глава 1. Адаптивный Каталист для гладкой выпуклой оптимизации

В данной главе приводится описание адаптивной оболочки Ката-лист(Са1а1уз1) — алгоритм 1, а также обобщенная теорема Монтейро-Свайтера из [10], чтобы показать, как заставить эту оболочку работать. Стоит отметить, что доказательство теоремы содержит в качестве побочного продукта новый теоретический анализ условия останова для внутреннего алгоритма (11). Это условие позволяет показать, что предлагаемая оболочка в неадаптивном режиме лучше в логарифм раз (см. Следствие 1) по общему количеству вызовов оракула внутреннего метода (здесь измеряется сложность оболочки в таких терминах) по сравнению со всеми другими известными оболочками.

Используя эту адаптивную ускоренную проксимальную оболочку, предлагается ускоренный вариант наискорейшего спуска [18; 20] в качестве альтернативы методу ускоренного наискорейшего спуска А. Немировского (см. [21; 22] и ссылки в них), адаптивные ускоренные варианты альтернативных процедур минимизации [23] в качестве альтернативы для [24—26] и адаптивного ускоренного координатного спуска [27]. Для последнего примера, насколько известно, ранее не существовало доведенного до конца метода адаптивного ускоренного координатного спуска. Наиболее продвинутым результатом в этом направлении является работа [28], относящаяся только к задачам с увеличением параметра гладкости в процессе итераций. Например, для целевой функции типа /(х) = х4 эта схема не распознает, что параметры гладкости (в частности, константа градиента Липшица) стремятся к нулю в ходе итераций.

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

наблюдение оказывает значительное влияние на разработку ускоренных алгоритмов. Похожее условие останова, например, возникает в следующих статьях [12; 29], в которых разработан (суб-)оптимальный ускоренный тензорный метод, основанный на ускоренных проксимальных оболочках. Предложенная «безлогарифмическая» оболочка позволяет улучшить наилучшие известные оценки [30] для сильно-выпукло-вогнутых седловых задач (с разными константами сильной выпуклости и вогнутости) на логарифмический множитель [31]. Усложненный вариант этой оболочки также позволяет разрабатывать «безлогарифмические» градиентные методы скользящего типа [13; 31; 32] и их тензорные обобщения [33]. Более того, на основе этой оболочки [34] был разработан один из вариантов сверхбыстрого метода второго порядка. Хотя эта оболочка была известна ранее, кажется, что идея использовать её в процедурах типа Каталист и новая (важная с теоретической точки зрения) переформулировка условия останова для внутренней задачи (11) породила большое количество приложений, некоторые из которых упомянуты в данной статье, а остальные можно найти в процитированной выше литературе. В качестве важного примера в разделе 1.2.2 показано, что разработанная оболочка с неускоренным методом координатного спуска для решения вспомогательной задачи работает намного лучше в теории (и лучше на практике), чем все известные прямые ускоренные алгоритмы покоординатного спуска для разреженных задач типа soft-max. До данной работы не существовало методов, способных обойти стандартные алгоритмы ускоренного покоординатного спуска, не позволяющие учесть разреженность задачи для функционала типа soft-max [20; 35].

Другим важным результатом этой статьи является адаптивный выбор параметра сглаживания. Поскольку подход, предложенный в текущей главе, требует двух входных параметров (это нижняя граница Ь^ и верхняя граница Ьи для неизвестного параметра гладкости Ь), вряд ли его можно назвать «адаптивным». Причем чем больше расхождение между этими двумя параметрами, тем более достойной внимания кажется наша адаптивная оболочка в теории. Но почти все наши эксперименты демонстрируют низкую чувствительность к этим параметрам, а не к реальному параметру гладкости. Но даже для такой «безлогарифмической» и адаптивной оболочки ожидается, что прямые адаптивные ускоренные процедуры будут работать лучше, чем их аналоги типа Каталист. Не так давно это было продемонстрировано в работе [36] для ускоренной процедуры чередующейся минимизации. Но и на сегодняшний день есть задачи,

для которых можно ожидать, что сначала будут разработаны оптимальные ускоренные алгоритмы с использованием процедур типа Каталист, а не прямого ускорения. Недавние достижения в области седловых задач [30; 31; 37] и децентрализованной распределенной оптимизации 1 [40; 41] подтверждают эту мысль. Ожидается, что для архитектур гомогенного федеративного обучения можно разработать ускоренный локальный SGD (современный подход см. в [42]) с использованием оболочки типа Каталист с версией SCAFFOLD локального алгоритма SGD [43]. Насколько известно, по-прежнему остается открытой проблема построения метода с ускоренным локальным SGD в качестве внутреннего алгоритма. В этой работе демонстрируются некоторые эксперименты, внушающие оптимизм в этом направлении.

1.1 Основная схема

Рассмотрим следующую задачу минимизации:

min f (y), (1)

где / — выпуклая функция, а ее градиент липшицев по нормет || • ||2 с константой Ь;:

ЦЧ/(х) -V/ (у)||2 ^ Ь; ||х - у||2.

Через х* обозначаем решение (1).

Чтобы предложить основную схему алгоритма, необходимо определить следующие функции:

FLx(y) = !(у) + |\\У - х||2,

!ь(х) = тт ^,х(У) = ^(х)),

такие, что функция FLX Ь-сильно выпукла, а ее градиент липшицев по норме || • ||2 с константой (Ь + Ь;). Следовательно, выполняется неравенство

\\VFLxx(У2) -VFLx(Уl)\\2 ^ (Ь + Ь;)\\у1 - у2\\2. (2)

1 Обратите внимание, что результаты этих статей были получены заново с использованием прямого ускорения [38; 39].

В соответствии с этим определением для всех L ^ 0 имеем, что fl(x) ^ f (x) и выпуклая функция f имеет Липшицев градиент с константой Липшица L. Более того, в соответствии с [18] [теорема 5, глава 6] из

X* ^ Argmin fL(x),

xeRn

получаем

Argmin f (x) and fL(x*) = f (x*).

xeRn

Таким образом, вместо исходной задачи (1) можно рассмотреть регуляри-зованную задачу Моро-Иосиды

min fb(x). (3)

xeR"

Обратите внимание, что задача (3) является обыкновенной задачей гладкой выпуклой оптимизации. Тогда сложность решения задачи (3) с точностью до £ по функции методом быстрого градиента (FGM) [1] можно оценить как O ^ sqrt. Под «сложностью» здесь понимается количество вызовов оракула. Каждый вызов оракула означает вычисление VfL(x) = L(x — yL(x)), где

Vl(x) — точное решение вспомогательной задачи min FL,x(y).

ye Rn

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

В конце этого краткого введения в стандартные методы ускоренных проксимальных точек опишем этап обычного (проксимального) градиентного спуска (подробнее см. [2])

Xk+1 = xk — L VfL(xk) = xk — L (Xk — yi(xk)) = yi(xk).

Чтобы разработать адаптивную проксимальную ускоренную оболочку, необходимо заменить стандартный FGM [1] на следующий адаптивный вариант алгоритма FGM 1, разработанный в [10].

Анализ алгоритма основан на следующей теореме.

Теорема 1 (Теорема 3.6 [10]). Пусть последовательность (xk,yk,zk), k ^ 0 сгенерирована алгоритмом 1. Определим R := lly0 — xJL. Тогда для всех N ^

Алгоритм 1 Алгоритм Монтейро-Свайтера

Входные данные: z0,y°,A0 = 0 for k = 0,1, ...,N - 1 do

Выбрать Lk+i и yk+1 такие, что

где

end for Вывод: yN

^<k+lMI Lk+iIL k+l ry>k+ ill

\vFLk+1 xk+1 (y № ^ —\\У - X Il2,

l/Lfc+iWl/Lk+i+4Afc/Lk+i

ak+l = -2-

Ak+l = Ak + ak+l, xk+l = A- yk + A+1 z

A и i 1 ^ A и i 1

zk+l = zk - ak+iVf (yk+l)

N

i \\zN - x*\\22 + An • (f (y^ - f Ы) + i ^ AkLk \\yk - xk||2 ^ f.

k=i

¡У) - ! (х*) < &, - х*\\2 < Е' (5)

N

^АкЬк \\ук - хк\\2 ^ 2Я2. (6)

к=\

Нам также необходима следующая лемма. Лемма[Лемма 3.7а [10]] Пусть последовательности {Ак} , {Ьк}, к ^ 0 сгенерированы алгоритмом 1. Тогда для всех N ^ 0

\ 2

1 * (7)

An > i (g ^ .

Определим неускоренный метод M, который будем использовать для решения вспомогательной задачи.

Предположение 1. Скорость сходимости (после t итераций/вызовов оракула) метода M для задачи

min F (y)

можно записать в общем виде следующим образом: с вероятностью не менее 1 — 6 выполняется (для рандомизированных алгоритмов, таких как Алгоритм 4, эта оценка выполняется с высокой вероятностью)2

F (yt) — F (y*) = О (LF R log 6) min{ Cn, exp (—CL)} ,

где y* — решение задачи, Ry = \ \y° — y*\\2, функция F -сильно выпукла и Lf — константа, характеризующая гладкосьть функции F.

Как правило, Cn = О(1) для стандартных полноградиентных методов первого порядка, Cn = O(p), где p — количество блоков, для чередующейся минимизации с p блоками и Cn = O(n) для методов безградиентного или координатного спуска, где n — размерность y. Подробнее см. ссылки в следующем примечании.

Замечание 1. Следует понимать, что подразумевается под константой LF, характеризующей гладкость функции F. Обычно для методов первого порядка это просто константа Липшица градиента F (см. [18; 44] для наискорейшего спуска и [24; 26; 45] для чередующейся минимизации); для безградиентных методов типа алгоритма 4 эта константа является средним значением параметров направленной гладкости, для безградиентных методов см. [46—50], методы покоординатного спуска см. в [27; 51; 52], а более общие случаи см. в

[53].

Замечание 2. Стоит заметить, что в предположении 1 первая оценка соответствует оценке скорости сходимости метода M для выпуклых задач. А вторая оценка соответствует оценке для сильно выпуклых задач.

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

Обозначим F^1 = FLk+lXk+i. Основываясь на ускоренном проксимальном методе Монтейро-Свайтера, предлагается алгоритм 2.

Теперь докажем основную теорему о скорости сходимости предложенной схемы. Принимая во внимание, что О(-) — это то же, что и О(-), с точностью

2Для детерминированных алгоритмов можно опустить «с вероятностью не менее 1 — 6» и множитель log y .

Алгоритм 2 Адаптивный Каталист

Входные данные: Стартовая точка x0 = y0 = z0; исходное предположение Lo > 0; параметры а > ß > у > 1; метод оптимизации M, A0 = 0. for k = 0,1,...,N - 1 do Lk+i = ß • min {aLk,LU} r = 0 repeat

r := r + 1

Lk+i := max{Lk+i/ß,Ld} Вычислить

l/Lk+iWl/Lk+i+4Ak/Lk+i

ak+i =-2-

Ak+i = Ak + ak+l,

xk+l = Ak yk + «k+i zk x = A, 1 y + A, 1 z .

Вычислить приближенное решение следующей задачи вспомогательным неускоренным методом M:

yk+1 ж argmin FL+ (y) :

y

Запуская M с начальной точкой xk+1 и конечной точкой yk+1, есть необходимость в Nr итерациях, чтобы удовлетворить адаптивному условию останова

IIvfl5v+1)||2 ^ v \|yk+1 - xk+1\\2.

until r > 1 и Nr ^ у • Nr-1 or Lk+1 = Ld zk+1 = zk - ak+1V/ (yk+1) end for Вывод: yN

до логарифмического множителя, на основании теоремы Монтейро-Свайтера 1 можно ввести следующую теорему:

Теорема 2. Рассмотрим алгоритм 2 с 0 < Ld < Lu для решения задачи (1), где Q = Rn, со вспомогательным (внутренним) неускоренным алгоритмом (методом) M, удовлетворяющий предположению 1 с константами Cn и Lf такими, что Ld ^ Lf ^ Lu.

Тогда общая сложность 3 в предлагаемом алгоритме 2 со внутренним методом Л4 составляет

Lu 4 f L , /к?2 Lf 'V Ld

О [Cn • max jA IL* J Lf с вероятностью не менее 1 — 8.

Доказательство. Заметим, что условие Монтейро-Свайтера (М-С)

I|VFLJV+1)I|2 ^ L+1 \\yk+1 — xk+1h (8)

вместо точного решения y^1 = уьк+1 (xk+1) вспомогательной задачи, для которого

iVF^y+^h = о,

позвоялет использовать приближенное, удовлетворяющее условию (8).

Поскольку yi+1 является решением задачи min FL+}(y), то VFL+1(y,k+1) =

y ' '

0. Тогда по неравенству (2) получаем

l|VFik+1(yk+1)||2 < (Lk+1 + Lf)||yk+1 — yk+1||2. (9)

По неравенству треугольника имеем

||xk+1 — yk+1||2 — ||yk+1 — yk+1||2 ^ ||yk+1 — xk+1 | | 2. (10)

Поскольку правая часть неравенства (10) совпадаем с правой частью условия М-С, а левая часть неравенства (9) совпадает с левой частью условия М-С с точностью до множителя Lk+1/2, можно сделать вывод, что если выполнено

I |yk+1 yk+1|| Lk+1 I |xk+1 yk+1|| (Ii)

||y — y* ||2 ^ 3Lk+1+2Lf ||X — y* ||2 (11)

то выполнено и условие М-С.

Для решения вспомогательной задачи min FLk+-, xk+i (y) используем неуско-

y '

ренный метод M. Используя предположение 1 с вероятностью ^ 1 — N (где N —общее число шагов Каталист), получаем, что скорость сходимости (после t итераций M, см. Предположение 1)

3Число вызовов оракула (итераций) вспомогательного метода M, требуемое для поиска е-точного по функции решения (1)

FiW) - Fpak-1) = O ((Lf + Lk+1)^2+1 log f) exp (-¿X.)

Заметим, что ^k+1 = ||xk+1 — yk+1||2, если xk+1 — стартовая точка. Поскольку F^1 Lk+1-сильно выпукла, выполнено неравенство [1]

\\уГ — yk+1|l2 < Fgbt1) — F?+1(yi+1).

Тогда

I- УГI12 < О (^^ ?) exp (-^^) • (12)

Из (11), (12) и того факта, что запускаем М из жк+1, поулчаем, что сложность Т (число итераций М) решения вспомогательной задачи с вероятностью не менее 1 — N выводится из

0 1о^) exp (—„,)) - ^ь (13)

Следовательно,

Т = 00 (Ъп • (14)

Поскольку в данном случае используется (14) 0(-)-нотация, можно принять, что Т является оценкой, соответствующей общей сложности решения вспомогательной задачи со всеми внутренними рестартами на Ькй1. Подставляя неравенство (7) в оценку (6), получаем

N4 «г/ \ ^ 2Д2

f (yn ) - f X) ^

N 1 4 2 '

Поскольку сложность вспомогательной задачи с вероятностью не менее 1 — N равна Т, предполагается, что в худшем случае все Ькй1 равны. Тогда наихудший случай можно оценить как следующую оптимизационную задачу

max .

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

Если все Ьк+1 = Ь(1 ^ (на каждой итерации оцениваем параметр регуляризации по нижней границе), то (Ьк+1+Ь /^ ~ ТЬ+[ и общая сложность с вероятностью ^ 1 — 6 составит

6 = о (спу// V

Если все

Ьк+1 = Ьи ^ (на каждой итерации оцениваем параметр регуляризации по верхней границе), то (Ьк+1+Ь/^ ~ 1 и общая сложность с вероятностью ^ 1 — 6 составит

(5 (О.^= (5 (а,^ V.

Теперь, используя эти две оценки, можно легко получить утверждение теоремы.

Важно заметить, что этот результат показывает, что такая процедура будет работать не хуже, чем стандартный Каталист [4; 5] с точностью до множителя О ^шах | , не зависящего от условия остановки при рестартах на Ьк+1.

Поскольку сложность решения вспомогательной задачи пропорциональна (Ьк+ьк+1, при уменьшении параметра так, что < Ь^, сложность решения вспомогательной задачи возрастет экспоненциально. Поэтому в качестве условия остановки внутреннего метода осмысленно выбрать сравнение количества итераций N и количества итераций при предыдущем перезапуске ¿—1. Это означает, что если N1 ^ yNt—l, то сложность начинает расти экспоненциально и необходимо переходить к следующей итерации внешнего метода. Используя такое адаптивное правило, в работе пытаемся найти наилучшее возможное значение Ьк+1 — . Это лежит в основе стандартного подхода Каталист [4; 5] и имеет очень простое объяснение. Чтобы минимизировать общую сложность, нужно выбрать параметр Ь^+1 = Ь таким, что

шт Л/ — • О

Ь V Ь \ ь

Ь/+ь

Это приводит к Ьк+1 — Ь!.

Заметим, что и в неадаптивном случае (если выберем все Ь^+1 = Ь/) из теоремы 2 можно получить следствие:

Следствие 1. Если рассмотреть алгоритм 2 с = для решения задачи (1) то общая сложность предложенного алгоритма 2 со внутренним нерандомизированным методом М составляет

O (c„/) . (15)

Доказательство. Используя (13) без множителя log (поскольку M неран-

домизированный), получаем, что сложность решения вспомогательной задачи составляет (см. также (14))

T = O (on (Lfc+fc1+1L/) • log 3Lfcj+fc1+12L/) И, поскольку выбираем Lk+1 = Lf,

3Lfc+. +2L/ _ 5

Lfc+i

Тогда сложность вспомогательной задачи составляет T = O (Cn). Используя эту оценку, получаем, что общая сложность составляет (15). □

Если метод M рандомизирован, получаем дополнительный множитель log — log . Следовательно, (15) изменяется: с вероятностью не менее 1 - 6

O(C„ log i

Обратите внимание, что в стандартном подходе Каталист [4; 5] общая сложность составляет O ^Cn log • • log , где £ = Poly(e) — отно-

сительная точность решения вспомогательной задачи на каждой итерации. Отсюда получаем, что, выбирая критерий остановки для внутреннего метода идентичным критерию из Алгоритма 2, можно получить Каталист без логарифмического выражения log 1. Кажется, что такой вариант Каталист может быть полезен во многих приложениях. Например, в качестве универсальной оболочки для неускоренных асинхронных централизованных распределенных алгоритмов.

1.2 Приложения

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

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

1.2.1 Наискорейший спуск

Рассмотрим задачу

min f (x),

жбМ™

где f — Lf-гладкая выпуклая функция (ее градиент Липшицев по норме || • || 2 с константой Lf).

Чтобы решить эту задачу, рассмотрим общеий вид шага градиентного спуска:

xk+1 = xk - hkVf (xk).

В [18] был предложен адаптивный способ выбора hk следующим образом (см. также [44] для точной скорости сходимости):

hk = argmin f (xk - hVf (xk)).

heR

Алгоритм 3 Наискорейший спуск

Входные данные: Стартовая точка x0. for dok = 0,1, ...,N - 1

Выбрать hk = argminheR f (xk — hVf (xk)) Положить xk+1 = xk — hkVf (xk) end for Вывод: xN

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

С другой стороны непосредственное ускорение алгоритма наискорейшего спуска отсутствует. Кроме того, с ним сложно использовать Каталист, так как

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

Стоит заметить, что для алгоритма 3 выполняется предположение 1 с Сп = 0(1), а является константой Липшица для градиента функции /.

1.2.2 Рандомизированный адаптивный координатный спуск

Рассмотрим следующую задачу без ограничений:

min f(x).

xGR"

Теперь предположим гладкость по направлениям для f, т. е. существование ßi,..., ßn таких, что для любых x G Rn, u G R

\Vtf (x + uei) - Vi f (x)| < ßi\u\, i = 1,...,n,

где Vif (x) = df (x)/dxi. Для дважды дифференцируемой f это эквивалентно тому, что (V2f(x))i;i ^ ßi. В связи с тем, что рассматривается ситуация, когда константы гладкости неизвестны, используем схему динамической подстройки из [27; 51].

Стоит заметить, что для алгоритма 4 справедливо предположение 1 с

n

Cn = O(n) (для x G Rn) и4 Lf = Lf := ^Yl ßi (среднее значение парамет-

n i=i

ров направленной гладкости).

Рассмотрим в качестве примера следующую задачу минимизации:

/ m \

min f (x) = y ln i У^ exp ^r1) -(b,x), (16)

где A G Rmxn, b G Rn. Обозначим i-ю строку матрицы A через Ai. A разрежена, то есть среднее число ненулевых элементов в Ai меньше, чем s. f —

4

Строго говоря, такая константа имеет место для неадаптивного варианта СБМ при конкретном

выборе [27]: = у) = —^—. Для описанного ИАСБМ анализ более сложен [35].

е р/

?=1 '

Алгоритм 4 RACDM

Входные данные: Стартовая точка x0; нижние границы (i := в0 £ (0, в«] , г = 1,...,п for k = 0,1, ...,N — 1 do

Список литературы диссертационного исследования кандидат наук Матюхин Владислав Вячеславович, 2022 год

Список литературы

1. Lectures on convex optimization

[Текст]. Т. 137 / Y. Nesterov [и др.]. — Springer, 2018.

2. Proximal algorithms

[Текст] / N. Parikh, S. Boyd [и др.] // Foundations and Trends® in Optimization. — 2014. — Т. 1, № 3. — С. 127—239.

3. Rockafellar, R. T. Monotone operators and the proximal point algorithm [Текст] / R. T. Rockafellar // SIAM journal on control and optimization. -1976. — Т. 14, № 5. — С. 877—898.

4. Lin, H. A universal catalyst for first-order optimization

[Текст] / H. Lin, J. Mairal, Z. Harchaoui // Advances in neural information processing systems. — 2015. — Т. 28.

5. Lin, H. Catalyst acceleration for first-order convex optimization: from theory to practice

[Текст] / H. Lin, J. Mairal, Z. Harchaoui // Journal of Machine Learning Research. — 2018. — Т. 18, № 1. — С. 7854—7907.

6. Catalyst acceleration for gradient-based non-convex optimization [Текст] / C. Paquette [и др.] // arXiv preprint arXiv:1703.10993. — 2017.

7. Adaptive catalyst for smooth convex optimization

[Текст] / A. Ivanova [и др.] // International Conference on Optimization and Applications. — Springer. 2021. — С. 20—37.

8. Kulunchakov, A. A generic acceleration framework for stochastic composite optimization

[Текст] / A. Kulunchakov, J. Mairal // Advances in Neural Information Processing Systems. — 2019. — Т. 32.

9. Recapp: Crafting a more efficient catalyst for convex optimization

[Текст] / Y. Carmon [и др.] // International Conference on Machine Learning. — PMLR. 2022. — С. 2658—2685.

10. Monteiro, R. D. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods

[Текст] / R. D. Monteiro, B. F. Svaiter // SIAM Journal on Optimization. — 2013. - Т. 23, № 2. - С. 1092-1125.

11. Near-optimal method for highly smooth convex optimization

[Текст] / S. Bubeck [и др.] // Conference on Learning Theory. — PMLR.

2019. — С. 492—507.

12. Doikov, N. Contracting proximal methods for smooth convex optimization [Текст] / N. Doikov, Y. Nesterov // SIAM Journal on Optimization. -

2020. — Т. 30, № 4. — С. 3146—3169.

13. Accelerated and nonaccelerated stochastic gradient descent with model conception

[Текст] / D. Dvinskikh [и др.] // arXiv preprint arXiv:2001.03443. — 2020.

14. Vasiliev, F. Optimization Methods: In 2 books, 1053 [Текст] / F. Vasiliev // MCCME, Moscow. — 2011.

15. Kabanikhin, S. I. Definitions and examples of inverse and ill-posed problems [Текст] / S. I. Kabanikhin. — 2008.

16. Evtushenko, Y. G. Optimization and fast automatic differentiation [Текст] / Y. G. Evtushenko // Computing Center of RAS, Moscow. — 2013.

17. Kantorovich, L. V. Functional analysis and applied mathematics

[Текст] / L. V. Kantorovich // Uspekhi Matematicheskikh Nauk. — 1948. — Т. 3, № 6. — С. 89—185.

18. Polyak, B. T. Introduction to optimization. optimization software [Текст] / B. T. Polyak // Inc., Publications Division, New York. — 1987. — Т. 1. — С. 32.

19. Poljak, B. Iterative algorithms for singular minimization problems [Текст] / B. Poljak // Nonlinear Programming 4. — Elsevier, 1981. — С. 147—166.

20. Gasnikov, A. Universal gradient descent

[Текст] / A. Gasnikov // arXiv preprint arXiv:1711.00394. — 2017.

21. Diakonikolas, J. Conjugate gradients and accelerated methods unified: the approximate duality gap view

[Текст] / J. Diakonikolas, L. Orecchia // arXiv preprint arXiv:1907.00289. — 2019.

22. Primal-dual accelerated gradient descent with line search for convex and nonconvex optimization problems

[Текст] / Y. Nesterov [и др.] // arXiv preprint arXiv:1809.05895. — 2018.

23. Beck, A. First-order methods in optimization [Текст] / A. Beck. — SIAM, 2017.

24. Diakonikolas, J. Alternating randomized block coordinate descent

[Текст] / J. Diakonikolas, L. Orecchia // International Conference on Machine Learning. — PMLR. 2018. — С. 1224—1232.

25. Guminov, S. Accelerated alternating minimization

[Текст] / S. Guminov, P. Dvurechensky, A. Gasnikov // arXiv preprint arXiv:1906.03622. — 2019.

26. Alternating minimization methods for strongly convex optimization [Текст] / N. Tupitsa [и др.] // Journal of Inverse and Ill-posed Problems. -2021. — Т. 29, № 5. — С. 721—739.

27. Nesterov, Y. Efficiency of coordinate descent methods on huge-scale optimization problems

[Текст] / Y. Nesterov // SIAM Journal on Optimization. — 2012. — Т. 22, № 2. — С. 341—362.

28. Fercoq, O. Accelerated, parallel, and proximal coordinate descent

[Текст] / O. Fercoq, P. Richtarik // SIAM Journal on Optimization. — 2015. — Т. 25, № 4. — С. 1997—2023.

29. Doikov, N. Inexact Tensor Methods with Dynamic Accuracies.

[Текст] / N. Doikov, Y. E. Nesterov // ICML. — 2020. — С. 2577—2586.

30. Lin, T. On gradient descent ascent for nonconvex-concave minimax problems [Текст] / T. Lin, C. Jin, M. Jordan // International Conference on Machine Learning. — PMLR. 2020. — С. 6083—6093.

31. Accelerated meta-algorithm for convex optimization problems

[Текст] / A. Gasnikov [и др.] // Computational Mathematics and Mathematical Physics. — 2021. — Т. 61, № 1. — С. 17—28.

32. Oracle complexity separation in convex optimization

[Текст] / A. Ivanova [и др.] // Journal of Optimization Theory and Applications. — 2022. — Т. 193, № 1. — С. 462—490.

33. Kamzolov, D. Optimal combination of tensor optimization methods [Текст] / D. Kamzolov, A. Gasnikov, P. Dvurechensky // International Conference on Optimization and Applications. — Springer. 2020.

С. 166—183.

34. Kamzolov, D. Near-optimal hyperfast second-order method for convex optimization and its sliding

[Текст] / D. Kamzolov, A. Gasnikov // arXiv preprint arXiv:2002.09050. — 2020.

35. Anikin, A. Accelerated proximal envelopes: application to componentwise methods

[Текст] / A. Anikin, V. Matyukhin, D. Pasechnyuk // Computational Mathematics and Mathematical Physics. — 2022. — Т. 62, № 2. — С. 336—345.

36. Tupitsa, N. Accelerated alternating minimization and adaptability to strong convexity

[Текст] / N. Tupitsa // arXiv preprint arXiv:2006.09097. — 2020.

37. A catalyst framework for minimax optimization

[Текст] / J. Yang [и др.] // Advances in Neural Information Processing Systems. — 2020. — Т. 33. — С. 5667—5678.

38. Kovalev, D. Optimal and practical algorithms for smooth and strongly convex decentralized optimization

[Текст] / D. Kovalev, A. Salim, P. Richtarik // Advances in Neural Information Processing Systems. — 2020. — Т. 33. — С. 18342—18352.

39. Li, H. Optimal accelerated variance reduced extra and diging for strongly convex and smooth decentralized optimization

[Текст] / H. Li, Z. Lin, Y. Fang // arXiv preprint arXiv:2009.04373. — 2020.

40. Hendrikx, H. Dual-free stochastic decentralized optimization with variance reduction

[Текст] / H. Hendrikx, F. Bach, L. Massoulie // Advances in Neural Information Processing Systems. — 2020. — Т. 33. — С. 19455—19466.

41. Li, H. Revisiting extra for smooth distributed optimization

[Текст] / H. Li, Z. Lin // SIAM Journal on Optimization. — 2020. — Т. 30, № 3. — С. 1795—1821.

42. Is local SGD better than minibatch SGD?

[Текст] / B. Woodworth [и др.] // International Conference on Machine Learning. — PMLR. 2020. — С. 10334—10343.

43. Scaffold: Stochastic controlled averaging for federated learning

[Текст] / S. P. Karimireddy [и др.] // International Conference on Machine Learning. — PMLR. 2020. — С. 5132—5143.

44. De Klerk, E. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

[Текст] / E. De Klerk, F. Glineur, A. B. Taylor // Optimization Letters. — 2017. — Т. 11, № 7. — С. 1185—1199.

45. Karimi, H. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition

[Текст] / H. Karimi, J. Nutini, M. Schmidt // Joint European conference on machine learning and knowledge discovery in databases. — Springer. 2016. — С. 795—811.

46. Optimal rates for zero-order convex optimization: The power of two function evaluations

[Текст] / J. C. Duchi [и др.] // IEEE Transactions on Information Theory. —

2015. — Т. 61, № 5. — С. 2788—2806.

47. Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex

[Текст] / A. V. Gasnikov [и др.] // Automation and Remote Control. —

2016. — Т. 77, № 11. — С. 2018—2034.

48. Shamir, O. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback

[Текст] / O. Shamir // The Journal of Machine Learning Research. — 2017. — Т. 18, № 1. — С. 1703—1713.

49. Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise

[Текст] / A. Bayandina [и др.] // arXiv preprint arXiv:1701.03821. — 2017.

50. Gorbunov, E. An accelerated method for derivative-free smooth stochastic convex optimization

[Текст] / E. Gorbunov, P. Dvurechensky, A. Gasnikov // SIAM Journal on Optimization. — 2022. — Т. 32, № 2. — С. 1210—1238.

51. Wright, S. J. Coordinate descent algorithms

[Текст] / S. J. Wright // Mathematical Programming. — 2015. — Т. 151, № 1. — С. 3—34.

52. Nesterov, Y. Efficiency of the accelerated coordinate descent method on structured optimization problems

[Текст] / Y. Nesterov, S. U. Stich // SIAM Journal on Optimization. — 2017. — Т. 27, № 1. — С. 110—123.

53. SGD: General analysis and improved rates

[Текст] / R. M. Gower [и др.] // International Conference on Machine Learning. — PMLR. 2019. — С. 5200—5209.

54. Convex optimization: Algorithms and complexity

[Текст] / S. Bubeck [и др.] // Foundations and Trends® in Machine Learning. — 2015. — Т. 8, № 3/4. — С. 231—357.

55. Gasnikov, A. On accelerated randomized methods

[Текст] / A. Gasnikov, P. Dvurechensky, I. Usmanova // Proceedings of Moscow Institute of Physics and Technology. — 2016. — Т. 8, № 2. — С. 67—100. — In Russian, first appeared in arXiv:1508.02182.

56. Khaled, A. Better communication complexity for local sgd [Текст] / A. Khaled, K. Mishchenko, P. Richtarik. — 2019.

57. Advances and open problems in federated learning

[Текст] / P. Kairouz [и др.] // Foundations and Trends® in Machine Learning. — 2021. — Т. 14, № 1/2. — С. 1—210.

58. Dvurechensky, P. Parallel algorithms and probability of large deviation for stochastic convex optimization problems

[Текст] / P. Dvurechensky, A. Gasnikov, A. Lagunovskaya // Numerical Analysis and Applications. — 2018. — Т. 11, № 1. — С. 33—37.

59. Nesterov, Y. Confidence level solutions for stochastic programming [Текст] / Y. Nesterov, J.-P. Vial // Automatica. — 2008. — Т. 44, № 6. — С. 1559—1568.

60. Stich, S. U. Local SGD converges fast and communicates little [Текст] / S. U. Stich // arXiv preprint arXiv:1805.09767. — 2018.

61. Adaptive gradient descent for convex and non-convex stochastic optimization

[Текст] / A. Ogaltsov [и др.] // arXiv preprint arXiv:1911.08380. — 2019.

62. Nemirovsky, A. S. Problem Complexity and Method Efficiency in Optimization

[Текст] / A. S. Nemirovsky, D. B. Yudin. — Wiley, 1983. — (A Wiley-Interscience publication).

63. Gorbunov, E. Optimal decentralized distributed algorithms for stochastic convex optimization

[Текст] / E. Gorbunov, D. Dvinskikh, A. Gasnikov // arXiv preprint arXiv:1911.07363. — 2019.

64. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization

[Текст] / B. E. Woodworth [и др.] // Advances in neural information processing systems. — 2018. — Т. 31.

65. Chang, C.-C. LIBSVM: a library for support vector machines

[Текст] / C.-C. Chang, C.-J. Lin // ACM transactions on intelligent systems and technology (TIST). — 2011. — Т. 2, № 3. — С. 1—27.

66. Hilbert, D. Ein beitrag zur theorie des legendre'schen polynoms

[Текст] / D. Hilbert // Acta mathematica. — 1894. — Т. 18, № 1. -С. 155—159.

67. Hu, Y. Collaborative filtering for implicit feedback datasets

[Текст] / Y. Hu, Y. Koren, C. Volinsky // 2008 Eighth IEEE international conference on data mining. — Ieee. 2008. — С. 263—272.

68. Near optimal methods for minimizing convex functions with lipschitz p-th derivatives

[Текст] / A. Gasnikov [и др.] // Conference on Learning Theory. — PMLR. 2019. — С. 1392—1393.

69. Nesterov, Y. Implementable tensor methods in unconstrained convex optimization

[Текст] / Y. Nesterov // Mathematical Programming. — 2021. — Т. 186, № 1. — С. 157—183.

70. Grapiglia, G. N. On inexact solution of auxiliary problems in tensor methods for convex optimization

[Текст] / G. N. Grapiglia, Y. Nesterov // Optimization Methods and Software. — 2021. — Т. 36, № 1. — С. 145—170.

71. Гасников, А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска

[Текст] / А. В. Гасников. — Федеральное государственное автономное образовательное учреждение высшего образования «Московский физико-технический институт (национальный исследовательский университет)», 2018.

72. Lan, G. Lectures on optimization

[Текст] / G. Lan // Methods for machine learning. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA. — 2019.

73. Dvurechensky, P. Randomized similar triangles method: A unifying framework for accelerated randomized optimization methods (coordinate descent, directional search, derivative-free method)

[Текст] / P. Dvurechensky, A. Gasnikov, A. Tiurin // arXiv preprint arXiv:1707.08486. — 2017.

74. Accelerated methods for composite non-bilinear saddle point problem [Текст] / M. Alkousa [и др.] // arXiv preprint arXiv:1906.03620. — 2019.

75. Lin, T. Near-optimal algorithms for minimax optimization

[Текст] / T. Lin, C. Jin, M. I. Jordan // Conference on Learning Theory. -PMLR. 2020. — С. 2738—2779.

76. Spokoiny, V. Accuracy of Gaussian approximation in nonparametric Bernstein-von Mises Theorem

[Текст] / V. Spokoiny, M. Panov // arXiv preprint arXiv:1910.06028. — 2019.

77. Lucchi, A. A stochastic tensor method for non-convex optimization [Текст] / A. Lucchi, J. Kohler // arXiv preprint arXiv:1911.10367. — 2019.

78. Baes, M. Estimate sequence methods: extensions and approximations [Текст] / M. Baes // Institute for Operations Research, ETH, Zürich, Switzerland. — 2009. — С. 2.

79. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads

[Текст] / A. Anikin [и др.] // Proceedings of International conference ITAS-2015. Russia, Sochi. — 2015.

80. Acceleration methods

[Текст] / A. d'Aspremont, D. Scieur, A. Taylor [и др.] // Foundations and Trends® in Optimization. — 2021. — Т. 5, № 1/2. — С. 1—245.

81. Chernov, A. Direct-dual method for solving the entropy-linear programming problem

[Текст] / A. Chernov // Intelligent systems. Theory and applications. — 2016. — Т. 20, № 1. — С. 39—59.

82. Efficient numerical methods for entropy-linear programming problems [Текст] / A. V. Gasnikov [и др.] // Computational Mathematics and Mathematical Physics. — 2016. — Т. 56, № 4. — С. 514—524.

83. Python Scipy documentation: scipy.sparse.csr_matrix [Текст] / SciPy.org.

84. Blanchard, P. Accurately computing the log-sum-exp and softmax functions [Текст] / P. Blanchard, D. J. Higham, N. J. Higham // IMA Journal of Numerical Analysis. — 2021. — Т. 41, № 4. — С. 2311—2330.

85. Bertsekas, D. P. Dynamic Programming and Optimal Control [Текст] / D. P. Bertsekas. — 1995.

86. Nesterov, Y. Smooth minimization of non-smooth functions

[Текст] / Y. Nesterov // Mathematical programming. — 2005. — Т. 103, № 1. — С. 127—152.

87. Jin, Y. Efficiently solving MDPs with stochastic mirror descent

[Текст] / Y. Jin, A. Sidford // International Conference on Machine Learning. — PMLR. 2020. — С. 4890—4900.

88. Variance reduction for matrix games

[Текст] / Y. Carmon [и др.] // Advances in Neural Information Processing Systems. — 2019. — Т. 32.

89. Coordinate methods for matrix games

[Текст] / Y. Carmon [и др.] // 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). — IEEE. 2020. — С. 283—293.

90. Variance reduced value iteration and faster algorithms for solving markov decision processes

[Текст] / A. Sidford [и др.] // Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. — SIAM. 2018. — С. 770—787.

91. Gasnikov, A. V. Universal method for stochastic composite optimization problems

[Текст] / A. V. Gasnikov, Y. E. Nesterov // Computational Mathematics and Mathematical Physics. — 2018. — Т. 58, № 1. — С. 48—64.

92. Nocedal, J. Numerical Optimization

[Текст] / J. Nocedal, S. Wright. — Springer Science & Business Media, 2006.

93. Primal-dual accelerated gradient methods with small-dimensional relaxation oracle

[Текст] / Y. Nesterov [и др.] // Optimization Methods and Software. — 2021. — Т. 36, № 4. — С. 773—810.

94. Nesterov, Y. Universal gradient methods for convex optimization problems [Текст] / Y. Nesterov // Mathematical Programming. — 2015. — Т. 152, № 1. — С. 381—404.

95. Advances in low-memory subgradient optimization

[Текст] / P. E. Dvurechensky [и др.] // Numerical Nonsmooth Optimization. — Springer, 2020. — С. 19—59.

96. Halmos, P. A Hilbert Space Problem Book

[Текст]. Т. 19 / P. Halmos. — Springer Science & Business Media, 1982.

97. Tseng, P. On accelerated proximal gradient methods for convex-concave optimization

[Текст] / P. Tseng // submitted to SIAM Journal on Optimization. — 2008. — Т. 2, № 3.

98. Tyurin, A. Mirror version of similar triangles method for constrained optimization problems

[Текст] / A. Tyurin // arXiv preprint arXiv:1705.09809. — 2017.

99. Nemirovskij, A. S. Problem complexity and method efficiency in optimization [Текст] / A. S. Nemirovskij, D. B. Yudin. — 1983.

100. Fercoq, O. Restarting accelerated gradient methods with a rough strong convexity estimate

[Текст] / O. Fercoq, Z. Qu // arXiv preprint arXiv:1609.07358. — 2016.

101. Kamzolov, D. Universal intermediate gradient method for convex problems with inexact oracle

[Текст] / D. Kamzolov, P. Dvurechensky, A. V. Gasnikov // Optimization Methods and Software. — 2021. — Т. 36, № 6. — С. 1289—1316.

102. Devolder, O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization

[Текст] : дис. ... канд. / Devolder Olivier. — PhD thesis, 2013.

103. Dvurechensky, P. Stochastic intermediate gradient method for convex problems with stochastic inexact oracle

[Текст] / P. Dvurechensky, A. Gasnikov // Journal of Optimization Theory and Applications. — 2016. — Т. 171, № 1. — С. 121—145.

104. Kabanikhin, S. Iteration methods of solving inverse and ill-posed problems with data on the part of the boundary

[Текст] / S. Kabanikhin, M. Bektemesov, A. Nurseitova. — 2006.

105. Around power law for PageRank components in Buckley-Osthus model of web graph

[Текст] / A. Gasnikov [и др.] // arXiv preprint arXiv:1701.02595. — 2017.

106. Dvurechensky, P. Gradient method with inexact oracle for composite non-convex optimization

[Текст] / P. Dvurechensky // arXiv preprint arXiv:1703.09180. — 2017.

107. Alekseev, V. The Lagrange Principle for Problems of the Classical Calculus of Variations and Optimal Control Theory

[Текст] / V. Alekseev, V. Tikhomirov, S. Fomin // Optimal Control. — Springer, 1987. — С. 203—277.

108. Ryaben'kii, V. Introduction to computational mathematics [Текст] / V. Ryaben'kii. — 1994.

109. Dual approaches to the strongly convex simple function minimization problem under affine restrictions

[Текст] / A. Anikin [и др.] // arXiv preprint arXiv:1602.01686. — 2016.

110. Chernov, A. Fast primal-dual gradient method for strongly convex minimization problems with linear constraints

[Текст] / A. Chernov, P. Dvurechensky, A. Gasnikov // International Conference on Discrete Optimization and Operations Research. — Springer. 2016. — С. 391—403.

111. Gasnikov, A. Stochastic gradient methods with inexact oracle

[Текст] / A. Gasnikov, P. Dvurechensky, Y. Nesterov // TRUDY MIPT. — 2016. — Т. 8, № 1. — С. 41—91.

112. Dvinskikh, D. Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems

[Текст] / D. Dvinskikh, A. Gasnikov // Journal of Inverse and Ill-posed Problems. — 2021. — Т. 29, № 3. — С. 385—405.

113. Inexact relative smoothness and strong convexity for optimization and variational inequalities by inexact model

[Текст] / F. Stonyakin [и др.] // arXiv preprint arXiv:2001.09013. — 2020.

Список рисунков

1 Логистическая регрессия (17) на датасете rcv1_train....................26

2 Логистическая регрессия (17) на датасете a1a............................26

3 Результаты ускорения RACDM для квадратичной задачи (18) с гильбертовой матрицей, n = 1000..........................................28

4 Синтетическая квадратичная задача (18) с матрицей A,n = 100. . . 30

5 Задача логистической регрессии (19) на датасете madelon..............30

6 Задача дополнения матрицы (20) с разными (а, в, Y)....................32

7 Задача дополнения матрицы (20) с большой матрицей..................32

8 Регуляризированные логистические потери (23) для разных интервалов синхронизации т................................................33

9 Минимизация логистических потерь (23) с минибатчингом............33

10 Зависимость величины (F(xk) — F(x*))/(F(x0) — F(x*)) (в log масштабе) от числа вычислений компонент градиентов Vf¡ и Vg¿. Двухмерные проекции......................................................47

11 Зависимость величины (F(xk) — F(x*))/(F(x0) — F(x*)) (в log масштабе) от времени работы и числа итераций внутреннего метода. 47

12 Сходимость методов для задачи SoftMax (58) с равномерно разреженной случайной матрицей..........................................63

13 Сходимость методов для задачи SoftMax (58) с неравномерно разреженной случайной матрицей..........................................63

14 Тест 1 — истинное решение ..............................................88

15 Тест 1 — решение задачи продолжения методами GD и STM .... 89

16 Тест 1 — функционал невязки (логарифмическая шкала)..............90

17 Тест 1 — ошибки методов GD, SGD, STM ..............................90

18 Тест 3 (увеличенное число итераций) — функционал невязки (логарифмическая шкала) ................................................91

19 Тест 3 (увеличенное число итераций) — ошибки методов..............91

20 Тест 2 (увеличенная глубина) — решение задачи продолжения методами GD и STM........................................................92

21 Тест 2 — функционал невязки (логарифмическая шкала)..............93

22 Тест 2 (увеличенная глубина) — ошибки методов ........... 93

Список таблиц

1 Сравнение сложности алгоритмов.................... 22

2 Теоретические оценки с и без М-С ускорения.............. 25

3 Сравнение эффективности методов................... 59

4 Сравнение эффективности подходов (случай у =1).......... 66

5 Сравнение эффективности подходов (случай у £ (0; 1))........ 67