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

1. ВВЕДЕНИЕ

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

где $F$ – некоторый оператор, g – выпуклая полунепрерывная функция, определенная на ${\text{dom}}g$. Вариационные неравенства являются одной из популярных оптимизационных формулировок. Это связано с тем, что они включают в себя множество задач, широко встречающихся в различных областях прикладной науки. Чтобы понять важность вариационных неравенств, приведем два классических примера.

Пример 1 (Минимизация). Рассмотрим выпуклую задачу минимизации с регуляризатором:

где f – целевая функция, а g – регуляризатор. Если взять $F(x): = \nabla f(x)$, то можно доказать, что $x{\kern 1pt} * \in {\text{dom}}g$ является решением (1) тогда и только тогда, когда $x{\kern 1pt} * \in {\text{dom}}g$ является решением (2) [1, Section 1.4.1].

Пример 2 (Седловая задача). Рассмотрим выпукло-вогнутую седловую задачу:

где ${{g}_{1}}$ и ${{g}_{2}}$ можно считать регуляризаторами. Определим $F(x)\,: = \,F({{x}_{1}},{{x}_{2}})\,: = \,[{{\nabla }_{{{{x}_{1}}}}}f({{x}_{1}},{{x}_{2}}),$ $ - {{\nabla }_{{{{x}_{2}}}}}f({{x}_{1}},{{x}_{2}})]$ и $g(x) = g({{x}_{1}},{{x}_{2}}) = {{g}_{1}}({{x}_{1}}) + {{g}_{2}}({{x}_{2}})$. Можно доказать, что $x{\kern 1pt} * \in {\text{dom}}g$ является решением (1) тогда и только тогда, когда $z{\kern 1pt} * \in {\text{dom}}g$ является решением (3) [1, Section 1.4.1]. Таким образом, выпукло-вогнутые седловые задачи (3) могут быть рассмотрены с помощью переформулировки в виде вариационного неравенства (1).

В то время как задачи минимизации обычно рассматриваются отдельно от вариационных неравенств, задачи поиска седловых точек очень часто изучаются именно в общности вариационных неравенств. Но даже не принимая во внимание задачи минимизации сами вариационные неравенства [2] и их частный случай – седловые задачи – имеют множество приложений в реальных приложениях. Тут, прежде всего, следует отметить классические примеры из экономики и теории игр, расцвет которых пришелся на середину прошлого века [1, 3, 4]. Важно отметить также классические, но более новые сюжеты из области робастной оптимизации [5–7] и обучения с учителем/без учителя [8–13]. Еще большую значимость вариационным неравенствам придают новые приложения из областей обучения с подкреплением [14, 15], состязательного обучения [16] и генеративных моделей [17–20].

Между тем с каждым годом современные прикладные задачи становятся все более сложными и имеют стохастический характер: F(x) = ${{\mathbb{E}}_{{\xi \sim \mathcal{D}}}}[{{F}_{\xi }}(x)]$. Часто такое математическое ожидание не может быть представлено в аналитической форме из-за того, что распределение $\mathcal{D}$ является нетривиальным или даже неизвестным, поэтому прибегают к подходу Монте-Карло, который аппроксимирует интеграл с помощью выборки из распределения $\mathcal{D}$:

В алгоритмах, предназначенных для решения стохастических задач [21–24], часто избегают обращения к полным операторам или градиентам и прибегают к технике батчирования, когда выбирается одно или несколько слагаемых из (4). Поэтому очень важно, чтобы алгоритм был устойчив при использовании батчей любого размера, что подтверждается как с точки зрения теории, так и на практике. Но даже для задач минимизации не все стохастические методы обладают данным свойством [25, Раздел 5]. Это подводит нас к цели данной работы:

Разработать алгоритм решения монотонного стохастического вариационного неравенства вида конченой суммы с липшицевыми слагаемыми (1) + (4). При этом алгоритм должен быть нечувствителен к размеру батчей.

Краткий обзор существующих результатов. Теория решения монотонных вариационных неравенств с липшицевым оператором имеет обширную историю. Естественной идеей для создания методов для решения вариационных неравенств является обобщение градиентного спуска с помощью замены градиента $\nabla f(x)$ на оператор $F(x)$. Однако для монотонных операторов такой метод может расходиться. Прорывом стало создание экстраградиентного метода [26], который был широко теоретически исследован [7, 27] и впоследствии получил различные модификации и обобщения [28, 29], в том числе и для стохастического случая [30]. Что касается методов решения монотонных стохастических задач вида конечной суммы, то можно выделить работы [31–33], в которых авторы адаптируют технику редукции дисперсии для вариационных неравенств. Более того, результаты из [32] являются оптимальными [34]. Но это справедливо только для случая, когда на каждой итерации мы собираем батч размера один. Как только мы используем неединичный батч, результаты работ [31, 32] становятся хуже. Подробнее см. табл. 1.

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

2. ПОСТАНОВКА ЗАДАЧИ И ПРЕДПОЛОЖЕНИЯ

В работе рассматривается задача (1) + (4), где $\mathcal{X}$ – конечномерное евклидово пространство со скалярным произведением $\langle \cdot , \cdot \rangle $ и индуцированной нормой ${\text{||}}\, \cdot \,{\text{||}}$. Для выпуклой полунепрерывной g обозначим ее область определения как domg = = $\{ x:g(x) < + \infty \} $. Предполагаем, что функция $g$ является такой, что оператор prox(x) = = $\arg {{\min }_{{y \in \mathcal{X}}}}\left\{ {\alpha g(y) + \frac{1}{2}{\text{||}}y - x{\text{|}}{{{\text{|}}}^{2}}} \right\}$ при любом $\alpha > 0$ может быть точно вычислен “бесплатно”. Отметим важное свойство prox, а именно для y = ${\text{pro}}{{{\text{x}}}_{{\alpha g}}}(x)$ выполняется

Через ${{\mathbb{E}}_{k}}$ обозначим условное матожидание $\mathbb{E}\left[ { \cdot \,{\text{|}}\,{{S}^{{k - 1}}},{{S}^{{k - 2}}}, \cdot \cdot \cdot ,{{S}^{0}}} \right].$

Каждый оператор ${{F}_{i}}:{\text{dom}}g \to {{\mathbb{R}}^{d}}$ является однозначным. Основные предположения работы формулируются следующим образом.

Предположение 1.

$ \bullet $ Решение задачи (1) + (4) существует и может быть не единственным.

$ \bullet $ Оператор $F$ монотонный, т.е. для любых $u,v \in {{\mathbb{R}}^{d}}$ выполняется

$ \bullet $ Оператор $F$ $L$-липшицевый, т.е. для любых $u,v \in {{\mathbb{R}}^{d}}$ выполняется

$ \bullet $ Оператор ${{F}_{m}}$ является ${{L}_{m}}$-липшицевым. Определим $\bar {L}$, как ${{\bar {L}}^{2}} = \frac{1}{M}\sum\limits_{m = 1}^M {L_{m}^{2}} $.

3. ОСНОВНАЯ ЧАСТЬ

В основу описанного в данной статье метода положена нераспределенная версия Алгоритма 1 из статьи [35]. Данный алгоритм основан на так называемой “оптимистической” модификации [28] метода экстраградиента [26]. Суть этой модификации заключается в использовании значения оператора не только в точках текущей итерации (${{x}^{k}}$ и ${{w}^{k}}$), но и с прошлой итерации (${{x}^{{k - 1}}}$ и ${{w}^{{k - 1}}}$). Также в методе используется техника редукции дисперсии [22, 32], для чего введена дополнительную последовательность ${{w}^{k}}$. Отметим, что точка ${{w}^{k}}$ (опорная точка) меняется редко (если p мало), и поэтому полный оператор $F({{w}^{k}})$ практически не пересчитывается. Также в данной работе применен случайный отрицательный момент $\gamma ({{w}^{k}} - {{x}^{k}})$, который необходим для применения техники редукции дисперсии в методах вариационных неравенств [32, 33].

В качестве критерия сходимости используем следующую функцию:

Здесь мы берем максимум не на всем множестве $\mathcal{X}$, а на $\mathcal{C}$ – компактном подмножестве $\mathcal{X}$. Таким образом, мы можем рассматривать и неограниченные множества $\mathcal{X} \subseteq {{\mathbb{R}}^{d}}$. Это допустимо, поскольку рассмотренная версия критерия справедлива, если решение $x{\kern 1pt} *$ лежит в $\mathcal{C}$; подробнее см. [6]. Следующая теорема представляет сходимость предложенного метода.

Теорема 1. Рассмотрим задачу (1) + (4) в Предположениях 1. Пусть $\{ {{x}^{k}}\} $ – последовательность, генерируемая Алгоритмом 3 с выбранными $\eta ,\theta ,\alpha ,\beta ,\gamma $ следующим образом:

Тогда, при $\varepsilon > 0$, количество итераций для достижения $\mathbb{E}[{\text{Gap}}({{x}^{k}})]\;\leqslant \;\varepsilon $ равно

Algorithm 1. Оптимистичный Метод с Моментум и Батчированием

1: Параметры: размер шага $\eta > 0$, момент $\gamma > 0$, вероятность $p \in (0;1)$, размер батча $b \in \{ 1, \ldots ,M\} $,            количество итераций K

2: Инициализация: выбрать ${{x}^{0}} = {{w}^{0}} = {{x}^{{ - 1}}} = {{w}^{{ - 1}}} \in {{\mathbb{R}}^{d}}$

3: for $k = 0,1, \ldots ,$ do

4:   Выбрать $j_{1}^{k}, \ldots ,j_{b}^{k}$ случайным образом из $\{ 1,...,M\} $ независимо и равномерно

5:   ${{S}^{k}} = \{ j_{1}^{k},...,j_{b}^{k}\} $

6:   ${{\Delta }^{k}} = \frac{1}{b}\sum\limits_{j \in {{S}^{k}}}^{} {({{F}_{j}}({{x}^{k}}) - {{F}_{j}}({{w}^{{k - 1}}})} + ({{F}_{j}}({{x}^{k}}) - {{F}_{j}}({{x}^{{k - 1}}}))) + F({{w}^{{k - 1}}})$

7:   ${{x}^{{k + 1}}} = {\text{pro}}{{{\text{x}}}_{{\eta g}}}({{x}^{k}} + \gamma ({{w}^{k}} - {{x}^{k}}) - \eta {{\Delta }^{k}})$

8:   ${{w}^{{k + 1}}} = \left\{ \begin{gathered} {{x}^{{k + 1}}},\quad {\text{с}}\;{\text{вероятностью}}\;p \hfill \\ {{w}^{k}},\quad {\text{с}}\;{\text{вероятностью}}\;1 - p \hfill \\ \end{gathered} \right.$

9: end for

Доказательство см. в Приложении A . Отметим, что Теорема дает итерационную сложность Алгоритма 3, но интерес представляет, прежде всего, оракульная сложность (количество обращений к слагаемым ${{F}_{i}}$). Можно заметить, что на каждой итерации в среднем вызывается $\mathcal{O}\left( {b + pn} \right)$ слагаемых – каждый раз вызывается батч размера $b$, и с вероятностью $p$ вычисляется полный оператор. Отсюда сразу получаем оптимальный выбор для $p$:

Следствие 1. В условиях теоремы 1 при выборе $p = \frac{b}{n}$ получается следующая оракульная сложность для Алгоритма 1

Если $b\;\leqslant \;\frac{{\overline L \sqrt n }}{L}$, то получаем $\mathcal{O}\left( {\sqrt n \frac{{\bar {L}}}{\varepsilon }} \right)$. Этот результат  является оптимальным и неулучшаемым [34].

4. ЭКСПЕРИМЕНТЫ

В данном разделе проверяется эффективность работы алгоритма 1 на практике.

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

где ${{\Delta }^{d}}$ – единичный симплекс в ${{\mathbb{R}}^{d}}$. В данной работе используются те же экспериментальные наборы входных данных, что и в [32], в частности, рассматриваются матрицы игры “вор и полицейский” из [36] и первая тестовая матрица из [37]. Заметим, что задача (7) не имеет вид конечной суммы, как (1) + (4), но можно переписать A из (7) следующим образом: $A = \sum\limits_{i = 1}^d {{{A}_{{i:}}}} $ или $A = \sum\limits_{i = 1}^d {{{A}_{{:i}}}} $, где ${{A}_{{i:}}}$ – $i$-я строка A, а ${{A}_{{:i}}}$ – $i$-й столбец A – см. подробнее в Разделе 5.1.2 из [32].

Для сравнения взяты методы из табл. 1. В частности, выбраны Алгоритмы 1 и 2 из [32], Алгоритм 1 + 2 из [31]. Все алгоритмы рассматриваются в евклидовой постановке с проекцией на симплекс из [38].

Параметры всех методов настраиваются, исходя из теоретических результатов, соответствующих статей – см. Раздел 6 из [32]. Все методы проверяются с различными размерами батчей. В качестве критерия сходимости используется зазор двойственности (6), который вычисляется как $\left[ {{{{\max }}_{i}}{{{({{A}^{T}}x)}}_{i}} - {{{\min }}_{j}}{{{(Ay)}}_{j}}} \right]$ ввиду решения задачи на симплексе. Критерием сравнения является количество операций (одна операция вычислительно равна вычислениям Ay и ${{A}^{T}}x$).

Результаты отражены на рис. 1 и 2. Они показывают, что алгоритм 3 превосходит всех конкурентов.

5. ВЫВОДЫ

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