Седловые задачи (оптимизация)

Материал из MachineLearning.

(Различия между версиями)

Aleksei Kovalenko (Обсуждение | вклад)
(Новая: {{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Alek...)
К следующему изменению →

Версия 15:10, 15 июля 2026

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником Aleksei Kovalenko 18:00, 15 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Седловые задачи (оптимизация).

Содержание

1 Определение и основные понятия
- 1.1 Что не следует отождествлять
2 Выпукло-вогнутая структура
- 2.1 Условия первого порядка
- 2.2 Монотонность
3 Существование, единственность и минимаксные теоремы
- 3.1 Теорема фон Неймана — Сиона
- 3.2 Сильная выпуклость и гладкость
4 Лагранжева двойственность
- 4.1 Сопряжённые функции
5 Геометрия допустимых множеств
- 5.1 Функция расстояния Брегмана
6 Важные частные случаи
7 Методы решения
8 Применения в машинном обучении
9 Когда седловая форма предпочтительнее прямой минимизации
10 Ограничения и типичные ошибки
11 Классические и современные направления
12 Практическая схема анализа
13 См. также
14 Примечания
15 Литература

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

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

Пусть $X$ и $Y$ — непустые допустимые множества в вещественных линейных пространствах, а $L:X\times Y\to\mathbb R\cup\{+\infty,-\infty\}$ — седловая функция. Седловой задачей в ориентации «минимум — максимум» называют

$\inf_{x\in X}\sup_{y\in Y}L(x,y).$

Пара $(x^\star,y^\star)\in X\times Y$ называется седловой точкой, если

$L(x^\star,y)\leq L(x^\star,y^\star)\leq L(x,y^\star)\qquad \forall x\in X,\ \forall y\in Y.$

Иными словами, $x^\star$ является наилучшим ответом минимизирующей стороны на $y^\star$ , а $y^\star$ — наилучшим ответом максимизирующей стороны на $x^\star$ . Геометрически сечение $L(\cdot,y^\star)$ имеет минимум в $x^\star$ , а сечение $L(x^\star,\cdot)$ — максимум в $y^\star$ . Слово «седло» описывает противоположную кривизну этих двух сечений, но не требует, чтобы график был гиперболическим параболоидом или чтобы функция была дважды дифференцируема.

Определяют нижнее и верхнее значения

$\underline v=\sup_{y\in Y}\inf_{x\in X}L(x,y),\qquad \overline v=\inf_{x\in X}\sup_{y\in Y}L(x,y).$

Всегда выполняется слабое минимаксное неравенство $\underline v\leq\overline v$ . Разность $\overline v-\underline v$ — минимаксный разрыв. Если существует седловая точка, то

$\underline v=L(x^\star,y^\star)=\overline v.$

Обратное утверждение требует достижения обоих экстремумов. Равенство чисел $\underline v=\overline v$ само по себе не создаёт седловую точку на некомпактных или открытых множествах.

Для кандидата $(x,y)$ естественной мерой качества служит прямо-двойственный разрыв

$\operatorname{Gap}(x,y)=\sup_{v\in Y}L(x,v)-\inf_{u\in X}L(u,y)\geq 0.$

Если оба экстремума конечны и достигаются, то $\operatorname{Gap}(x,y)=0$ эквивалентно седловому условию. На неограниченных множествах этот разрыв может быть бесконечным даже для хорошей приближённой точки; тогда используют ограниченный разрыв по тестовому множеству $B\subseteq X\times Y$ , резидуал вариационного неравенства или расстояние до множества решений.

Что не следует отождествлять

Минимаксная задача — оптимизация вложенной функции $\varphi(x)=\sup_{y\in Y}L(x,y)$ . Она может иметь решение, даже когда максимизатор не достигается и седловой пары нет.
Седловая точка — глобальное двустороннее неравенство. Для выпукло-вогнутой функции это естественное понятие решения всей игры.
Решение вариационного неравенства — точка, удовлетворяющая операторному неравенству. При корректно построенном седловом операторе оно эквивалентно седловой точке в выпукло-вогнутом случае, но произвольное вариационное неравенство не обязано происходить из седловой функции.
Стационарная точка гладкой игры удовлетворяет $\nabla_xL=0$ и $\nabla_yL=0$ в отсутствие ограничений. Без выпуклости и вогнутости это лишь условие первого порядка: точка может быть локальным максимумом по $x$ , локальным минимумом по $y$ или не иметь минимаксного смысла.
Локальная минимаксная точка в невыпукло-невогнутой задаче зависит от порядка и масштаба локальных окрестностей. Она не тождественна локальной седловой точке; эти понятия необходимо задавать отдельно.^[1]

Выпукло-вогнутая структура

Функция $L$ называется выпукло-вогнутой, если $L(\cdot,y)$ выпукла на $X$ при каждом $y$ , а $L(x,\cdot)$ вогнута на $Y$ при каждом $x$ . Обычно предполагается, что $X$ и $Y$ выпуклы и замкнуты. Для расширеннозначных функций ограничения можно включить индикаторами:

$\widetilde L(x,y)=L(x,y)+\delta_X(x)-\delta_Y(y),$

где $\delta_C(z)=0$ при $z\in C$ и $+\infty$ иначе. Знак перед $\delta_Y$ отражает максимизацию. Такая запись связывает седловые задачи с выпуклым анализом, субдифференциалами, нормальными конусами и монотонными операторами.

Условия первого порядка

Если $L$ собственная, замкнутая и выпукло-вогнутая, то седловое условие эквивалентно включениям

$0\in \partial_xL(x^\star,y^\star)+N_X(x^\star),\qquad 0\in-\partial_yL(x^\star,y^\star)+N_Y(y^\star).$

Здесь $N_C$ — нормальный конус множества $C$ . В гладком случае вводят седловой оператор

$F(x,y)=\bigl(\nabla_xL(x,y),-\nabla_yL(x,y)\bigr).$

Для $Z=X\times Y$ седловая точка решает вариационное неравенство

$\langle F(z^\star),z-z^\star\rangle\geq0\qquad\forall z\in Z.$

При негладком $L$ используют максимальный монотонный оператор

$T(x,y)=\bigl(\partial_xL(x,y),-\partial_yL(x,y)\bigr)+N_{X\times Y}(x,y)$

и включение $0\in T(z^\star)$ . Теорема Рокафеллара о седловых функциях связывает замкнутые собственные выпукло-вогнутые функции с максимальными монотонными операторами.^[1]

Монотонность

Для дифференцируемой выпукло-вогнутой функции оператор $F$ монотонен:

$\langle F(z)-F(z'),z-z'\rangle\geq0.$

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

Если $L(\cdot,y)$ является $\mu_x$ -сильно выпуклой, а $L(x,\cdot)$ — $\mu_y$ -сильно вогнутой относительно евклидовых норм, то

$\langle F(z)-F(z'),z-z'\rangle\geq \mu_x\left\|x-x'\right\|^2+\mu_y\left\|y-y'\right\|^2.$

Следовательно, при $\mu=\min\{\mu_x,\mu_y\}>0$ оператор сильно монотонен в стандартной произведённой норме, а седловая точка единственна. Если сильная кривизна имеется только по одной переменной, единственность всей пары и линейная сходимость общего метода из этого не следуют.

Существование, единственность и минимаксные теоремы

Теорема фон Неймана — Сиона

Одна из основных форм минимаксной теоремы Сиона утверждает следующее. Пусть $X$ — компактное выпуклое подмножество линейного топологического пространства, $Y$ — выпуклое множество, а для каждого $y$ функция $L(\cdot,y)$ полунепрерывна снизу и квазивыпукла, для каждого $x$ функция $L(x,\cdot)$ полунепрерывна сверху и квазивогнута. Тогда

$\min_{x\in X}\sup_{y\in Y}L(x,y)=\sup_{y\in Y}\min_{x\in X}L(x,y).$

Если дополнительно $Y$ компактно, то оба внешних экстремума достигаются, и существует седловая точка.^[1] Для непрерывной выпукло-вогнутой функции на компактных выпуклых $X$ и $Y$ эти условия выполнены автоматически.

Компактность можно заменить условиями инф-компактности и суп-компактности: подходящие подуровневые множества по $x$ и надуровневые по $y$ должны быть непустыми и компактными. На практике это обеспечивают коэрцитивность, сильная выпуклость/вогнутость или регуляризация. Неограниченность множества множителей Лагранжа требует отдельного доказательства ограниченности оптимальных множителей.

Сильная выпуклость и гладкость

Пусть $X$ и $Y$ замкнуты и выпуклы, $L$ замкнута, $\mu_x$ -сильно выпукла по $x$ и $\mu_y$ -сильно вогнута по $y$ , причём соответствующие сечения коэрцитивны. Тогда седловая точка существует и единственна. Сильная выпуклость без замкнутости или достижения экстремума недостаточна.

Если $F$ дополнительно $\ell$ -липшицев,

$\left\|F(z)-F(z')\right\|_*\leq \ell\left\|z-z'\right\|,$

то число обусловленности естественно задаётся как $\kappa=\ell/\mu$ . Для общих сильно монотонных липшицевых операторов экстраградиентные и проксимальные методы достигают геометрического уменьшения ошибки с показателем порядка $\exp(-cN/\kappa)$ , тогда как прямой операторный шаг без дополнительной кокоэрцитивности в общем анализе даёт зависимость порядка $\exp(-cN/\kappa^2)$ .

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

Лагранжева двойственность

Рассмотрим выпуклую задачу

$\min\left\{f(x)\mid x\in X,\ g_i(x)\leq0,\ i=1,\ldots,m,\ Ax=b\right\}.$

Её функция Лагранжа равна

$\mathcal L(x,\lambda,\nu)=f(x)+\sum_{i=1}^m\lambda_i g_i(x)+\langle\nu,Ax-b\rangle,\qquad \lambda\geq0.$

Прямая задача имеет вид $\inf_x\sup_{\lambda\geq0,\nu}\mathcal L$ , а двойственная — $\sup_{\lambda\geq0,\nu}\inf_x\mathcal L$ . Слабая двойственность есть частный случай минимаксного неравенства. При условии Слейтера — существовании относительного внутреннего допустимого $x$ со строгими неравенствами — для собственных замкнутых выпуклых данных обычно выполняются сильная двойственность и существование оптимальных множителей; вместе с достижением прямого решения это даёт седловую точку Лагранжиана и условия Каруша — Куна — Таккера.^[1]

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

Сопряжённые функции

По тождеству Фенхеля — Моро для собственной замкнутой выпуклой $h$

$h(u)=\sup_y\{\langle u,y\rangle-h^*(y)\}.$

Поэтому составная задача

$\min_x g(x)+h(Kx)$

имеет седловую форму

$\min_x\max_y\;g(x)+\langle Kx,y\rangle-h^*(y).$

Эта формулировка отделяет линейный оператор $K$ от функций $g$ и $h^*$ с легко вычисляемыми проксимальными отображениями; на ней основаны прямо-двойственные методы и алгоритм Чамболла — Пока.

Геометрия допустимых множеств

Выбор геометрии является частью постановки, а не косметической заменой евклидовой нормы. Пусть $\left\|\cdot\right\|$ — норма на пространстве $Z=X\times Y$ . Двойственная норма определяется как

$\left\|s\right\|_* = \sup_{\left\|z\right\|\leq1}\langle s,z\rangle.$

Именно пара норм входит в неравенство Гёльдера $\langle s,z\rangle\leq\left\|s\right\|_*\left\|z\right\|$ , в условие Липшица оператора и в оценки шума. Для матричной игры на симплексе естественны $\ell_1$ -геометрия решений и $\ell_\infty$ -геометрия градиентов; энтропийное проксимальное отображение приводит к мультипликативным весам и логарифмической зависимости от размерности. Для разреженных векторов часто уместна $\ell_1$ -геометрия, для матриц — нормы Фробениуса, спектральная и ядерная нормы, для распределений — энтропия и дивергенция Кульбака — Лейблера.

Функция расстояния Брегмана

Пусть $\omega$ дифференцируема и $1$ -сильно выпукла относительно выбранной нормы. Расстояние Брегмана

$V_z(u)=\omega(u)-\omega(z)-\langle\nabla\omega(z),u-z\rangle$

удовлетворяет $V_z(u)\geq\frac{1}{2}\left\|u-z\right\|^2$ , но обычно несимметрично и не является метрикой. Зеркальный шаг имеет вид

$\operatorname{Prox}_z(\eta s)=\arg\min_{u\in Z}\{\eta\langle s,u\rangle+V_z(u)\}.$

Для декартова произведения можно взять $\omega(x,y)=\omega_x(x)+\omega_y(y)$ с разными масштабами. Это эквивалентно предобусловливанию: масштабы следует согласовать с блоковыми константами Липшица и стоимостью вычисления каждого блока.

Диаметр $\Omega=\sup_{z\in Z}V_{z_0}(z)$ заменяет евклидов $D^2$ в оценках. Если $\left\|F(z)\right\|_*\leq G$ , зеркальный спуск даёт члены порядка $G\sqrt{\Omega/N}$ ; если $F$ монотонен и $\ell$ -липшицев, Mirror-Prox даёт порядок $\ell\Omega/N$ .^[1]

Важные частные случаи

Билинейные и матричные задачи

Билинейная задача имеет вид

$\min_{x\in X}\max_{y\in Y}\;\langle Kx,y\rangle+\langle a,x\rangle-\langle b,y\rangle.$

Если $X=\Delta_m$ и $Y=\Delta_n$ — симплексы, получается конечная антагонистическая матричная игра. Теорема фон Неймана гарантирует существование смешанного равновесия. При $X=\mathbb R^m$ , $Y=\mathbb R^n$ и $L(x,y)=x^{T}Ky$ точка $(0,0)$ седловая, но не единственная при наличии ядер $K$ или $K^{T}$ .

На скалярной игре $L(x,y)=xy$ одновременный градиентный спуск-подъём даёт

$\left(\begin{array}{c}x_{k+1}\\y_{k+1}\end{array}\right)=\left(\begin{array}{cc}1&-\eta\\ \eta&1\end{array}\right)\left(\begin{array}{c}x_k\\y_k\end{array}\right).$

Модуль собственных значений равен $\sqrt{1+\eta^2}>1$ , поэтому итерации расходятся при любом постоянном $\eta>0$ . Это стандартный контрпример против переноса интуиции обычного градиентного спуска на игры.

Регуляризованные минимаксные задачи

Добавление регуляризаторов

$\min_{x\in X}\max_{y\in Y}\;L(x,y)+\lambda_xR_x(x)-\lambda_yR_y(y)$

может сделать стороны сильно выпуклой и сильно вогнутой, ограничить решения и улучшить обусловленность. Квадратичная регуляризация соответствует евклидовой геометрии, отрицательная энтропия — геометрии симплекса. Однако регуляризация меняет исходную игру: ошибка решения должна включать как алгоритмическую ошибку, так и смещение порядка, зависящего от $\lambda_x,\lambda_y$ . Уменьшение регуляризации по этапам лежит в основе рекурсивной регуляризации и гомотопических схем.

Лагранжевы задачи

В лагранжевой седловой задаче двойственные переменные — цены нарушения ограничений. Проекция $\lambda$ на неотрицательный ортант обеспечивает двойственную допустимость, но искусственное ограничение $\left\|\lambda\right\|\leq R$ допустимо лишь при доказанной верхней границе оптимального множителя; иначе решается другая задача. Для равенств множитель обычно свободен по знаку.

Методы решения

Ниже $z=(x,y)$ , $Z=X\times Y$ , $F=(\nabla_xL,-\nabla_yL)$ , а $\Pi_Z$ — евклидова проекция. Оценки относятся к детерминированным задачам, если явно не сказано обратное. Одна «итерация» может требовать разного числа вызовов градиента, умножений на оператор и проксимальных отображений; поэтому сравнение только по числу итераций неполно.

Градиентный спуск-подъём

Одновременный градиентный спуск-подъём записывается как

$z_{k+1}=\Pi_Z\bigl(z_k-\eta F(z_k)\bigr).$

Он использует один вызов $F$ и одну проекцию. Если $F$ $\mu$ -сильно монотонен и $\ell$ -липшицев в евклидовой норме, то нерасширяемость проекции даёт

$\left\|z_{k+1}-z^\star\right\|^2\leq(1-2\eta\mu+\eta^2\ell^2)\left\|z_k-z^\star\right\|^2.$

Следовательно, при $0<\eta<2\mu/\ell^2$ имеется линейная сходимость, но оптимальный по этой оценке шаг $\eta=\mu/\ell^2$ приводит к сложности $O(\kappa^2\log(1/\varepsilon))$ по квадрату расстояния. Более быстрые оценки требуют дополнительной структуры, например ко-коэрцитивности. Для простой монотонной билинейной задачи метод с постоянным шагом расходится; усреднение или убывающий шаг могут уменьшать разрыв, не обеспечивая хорошего поведения последней итерации.

При попеременном обновлении сначала $x$ , затем $y$ используется уже новое значение $x$ ; это другой оператор расщепления с иной устойчивостью. Нельзя переносить на него без доказательства оценки одновременной схемы.

Экстраградиентный метод

Экстраградиентный метод Корпелевич делает прогноз и корректировку:

$\widehat z_k=\Pi_Z(z_k-\eta F(z_k)),\qquad z_{k+1}=\Pi_Z(z_k-\eta F(\widehat z_k)).$

Вторая оценка поля видит предсказанное вращение и стабилизирует билинейную динамику.^[1] Для монотонного $\ell$ -липшицева оператора на замкнутом выпуклом множестве и шага не больше постоянной порядка $1/\ell$ взвешенное среднее прогнозов имеет разрыв

$\operatorname{Gap}(\overline z_N)\leq C\ell D^2/N,$

если $Z$ ограничено евклидовым диаметром $D$ ; $C$ — абсолютная константа, зависящая от соглашения о шаге. Это $O(1/N)$ , тогда как субградиентные схемы при одной лишь ограниченности оператора обычно дают $O(1/\sqrt N)$ . При сильной монотонности и липшицевости экстраградиент с постоянным шагом порядка $1/\ell$ имеет линейную скорость $O(\kappa\log(1/\varepsilon))$ с точностью до констант.^[1]

Цена — два вызова полного оператора и обычно две проекции за итерацию. Если один вызов особенно дорог, преимущество по итерациям может исчезнуть; существуют варианты с одним новым вызовом оператора, блочные и стохастические варианты, но их условия и метрики сходимости различаются.

Зеркальный спуск-подъём и Mirror-Prox

Зеркальный спуск-подъём заменяет евклидову проекцию брегмановским проксимальным шагом:

$z_{k+1}=\operatorname{Prox}_{z_k}(\eta_kF(z_k)).$

Если $F$ монотонен, $\left\|F(z)\right\|_*\leq G$ и брегмановский диаметр конечен, то при $\eta_k\asymp1/\sqrt N$ эргодический разрыв имеет порядок $O(G\sqrt{\Omega/N})$ . Та же базовая скорость сохраняется в ожидании для несмещённого стохастического оракула с ограниченным вторым моментом после замены $G^2$ соответствующей границей момента.

Mirror-Prox — зеркальный аналог экстраградиента с двумя проксимальными шагами из одного центра. Для монотонного $\ell$ -липшицева оператора он достигает $O(\ell\Omega/N)$ по эргодическому разрыву. Смешивать эти две скорости нельзя: $O(1/N)$ использует гладкость оператора и дополнительную оценку в точке прогноза; обычный зеркальный спуск при одной оценке поля имеет в общем случае лишь $O(1/\sqrt N)$ .

Метод предпочтителен, когда евклидова проекция дорога или искажает структуру: на симплексе энтропийное проксимальное отображение вычисляется покоординатно, сохраняет положительность и даёт зависимость от $\log d$ вместо евклидова диаметра порядка $d$ в подходящих оценках.

Алгоритм Чамболла — Пока

Для задачи

$\min_x\max_y\;g(x)+\langle Kx,y\rangle-h^*(y)$

алгоритм Чамболла — Пока в одной стандартной форме имеет вид

$y^{k+1}=\operatorname{prox}_{\sigma h^*}(y^k+\sigma K\bar x^k),$

$x^{k+1}=\operatorname{prox}_{\tau g}(x^k-\tau K^{T}y^{k+1}),$

$\bar x^{k+1}=x^{k+1}+\theta(x^{k+1}-x^k).$

Для собственных замкнутых выпуклых $g,h^*$ , существующей седловой точки, $\theta=1$ и $\tau\sigma\left\|K\right\|^2<1$ итерации сходятся, а эргодический прямо-двойственный разрыв убывает как $O(1/N)$ на ограниченных тестовых множествах.^[1] При сильной выпуклости одной стороны ускоренные варианты получают $O(1/N^2)$ для соответствующей меры, а при сильной выпуклости обеих сторон — линейную сходимость; конкретные правила изменения $\tau,\sigma,\theta$ являются частью теоремы и не заменяются базовым постоянным шагом.

Каждая итерация требует умножений на $K$ и $K^{T}$ и вычисления двух проксимальных отображений, но не требует решения линейной системы. Метод особенно эффективен для разреженных линейных операторов, регуляризации полной вариацией, обратных задач и составных моделей.

Оптимистические градиентные методы

оптимистический градиентный метод использует текущую и предыдущую оценки поля. Евклидов OGDA можно записать как

$z_{k+1}=\Pi_Z\bigl(z_k-2\eta F(z_k)+\eta F(z_{k-1})\bigr).$

Он требует один новый вызов $F$ на итерацию после инициализации и хранит предыдущий градиент. Поправка экстраполирует изменение поля и приближает шаг проксимальной точки. В гладких билинейных и сильно выпукло-сильно вогнутых задачах OGDA имеет линейную сходимость при достаточно малом постоянном шаге; в общем монотонном липшицевом случае типичные гарантии относятся к усреднённому разрыву $O(1/N)$ или операторному резидуалу при дополнительных условиях.^[1]

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

Сравнение

Метод	Базовые предпосылки для указанной гарантии	Типичная гарантия	Цена итерации	Характерные применения и ограничения
Градиентный спуск-подъём	$\mu$ -сильная монотонность и $\ell$ -липшицевость	Линейная; общий прямой анализ даёт $O(\kappa^2\log(1/\varepsilon))$	Один градиент, одна проекция	Прост и дёшев; неустойчив на чисто билинейной игре
Экстраградиент	Монотонность и $\ell$ -липшицевость; ограниченность для глобального разрыва	Эргодический разрыв $O(\ell D^2/N)$ ; при сильной монотонности линейная	Два градиента, до двух проекций	Устойчив к вращению; дороже при полном градиенте
Зеркальный спуск-подъём	Монотонность, ограниченный двойственный градиент, конечный брегманов диаметр	Эргодический разрыв $O(G\sqrt{\Omega/N})$	Один градиент, один брегмановский проксимальный шаг	Симплексы, вероятности, разреженная геометрия; без экстраградиентного шага не использует гладкость для достижения скорости $O(1/N)$
Mirror-Prox	Монотонность и липшицевость в выбранной паре норм	Эргодический разрыв $O(\ell\Omega/N)$	Два градиента, два брегмановских проксимальных шага	Неевклидовы гладкие игры; требует доступного проксимального отображения
Чамболла — Пока	Композитная билинейная связь, легко вычисляемые проксимальные отображения $g,h^*$ , $\tau\sigma\left\\|K\right\\|^2<1$	Эргодический разрыв $O(1/N)$ ; ускорение при кривизне	$K,K^{T}$ и два проксимальных отображения	Обратные задачи, полный вариационный штраф, линейные ограничения
OGDA / оптимистический зеркальный метод	Обычно монотонность и гладкость; для линейной скорости — билинейная невырожденность или сильная монотонность	$O(1/N)$ для подходящей эргодической меры; линейная в сильном режиме	Один новый градиент, память предыдущего	Хорошее отношение вызовов оракула к устойчивости; чувствительность к шуму и шагу

В стохастическом случае несмещённость $\mathbb E[\widehat F(z)\mid z]=F(z)$ и граница условной дисперсии должны быть указаны явно. При фиксированной дисперсии оптимальный стохастический член в выпукло-вогнутом режиме обычно имеет порядок $O(1/\sqrt N)$ ; детерминированный член $O(1/N)$ не отменяет шум. Для конечной суммы редукция дисперсии может восстановить более быстрые зависимости, но сложность следует считать в компонентных градиентах.^[1]

Применения в машинном обучении

Генеративно-состязательные сети

Классическая генеративно-состязательная сеть решает игру генератора $G_\theta$ и дискриминатора $D_\phi$ :

$\min_\theta\max_\phi\;\mathbb E_{x\sim P_{\rm data}}\log D_\phi(x)+\mathbb E_{z\sim P_z}\log\bigl(1-D_\phi(G_\theta(z))\bigr).$

При неограниченном дискриминаторе исходная теория связывает оптимум с дивергенцией Йенсена — Шеннона между распределением данных и моделью.^[1] На параметрических нейронных сетях функция обычно невыпукла по $\theta$ и невогнута по $\phi$ . Поэтому теорема Сиона, монотонность седлового оператора и глобальные оценки выпукло-вогнутых методов к обучению GAN напрямую неприменимы. Экстраградиентные и оптимистические обновления могут уменьшать локальное вращение, но не гарантируют глобальную седловую точку, отсутствие коллапса мод или даже сходимость.

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

Состязательное и робастное обучение

состязательное обучение часто формулируют как

$\min_\theta\;\mathbb E_{(a,b)}\left[\max_{\delta\in\Delta}\ell(\theta;a+\delta,b)\right].$

Внутренний игрок выбирает худшее допустимое возмущение, например из шара $\left\|\delta\right\|_p\leq\rho$ , а внешний минимизирует робастный риск.^[1] На практике внутренний максимум заменяется несколькими шагами проецированного подъёма. Полученный градиент является градиентом точной функции максимума лишь при выполнении условий теоремы Дански и достаточно точном решении внутренней задачи. Для нейросетей задача невыпукло-невогнута; «сильная атака» — вычислительное, а не математическое доказательство нахождения глобального максимума.

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

Обучение с ограничениями

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

$\min\left\{\widehat R(\theta)\mid \widehat g_i(\theta)\leq0,\ i=1,\ldots,m\right\}.$

Лагранжева игра между моделью и неотрицательными множителями позволяет применять онлайн-обучение и методы без сожаления. В выпуклом случае усреднение прямых и двойственных решений контролирует одновременно субоптимальность и нарушение ограничений. Для невыпуклой нейросети KKT-стационарность не означает глобальной допустимости или оптимальности. В задачах справедливой классификации рандомизация над гипотезами делает лагранжиан билинейным и сводит лучшие ответы к стоимостно-чувствительной классификации.^[1]

Распределённая и федеративная оптимизация

Задачу согласования

$\min_{x_1,\ldots,x_m}\sum_{i=1}^m f_i(x_i),\qquad x_i=x_j,\quad (i,j)\in E.$

где $E$ — множество рёбер сети, можно записать через матрицу инцидентности $B$ как седловую функцию $\sum_i f_i(x_i)+\langle y,Bx\rangle$ . Двойственные переменные распространяют цену несогласованности, а произведения на $B$ и $B^{T}$ реализуются локальными обменами. Скорость зависит не только от обусловленности функций, но и от спектрального разрыва графа, задержек, гетерогенности данных и числа коммуникационных раундов. Локальные шаги уменьшают коммуникации, но в минимаксной игре дрейф клиентов может усиливать вращение; оценки централизованного экстраградиента без сетевого члена здесь неверны.^[1]

Оптимальный транспорт

Для дискретных мер транспортная задача является линейной программой, а её двойственная форма Канторовича имеет потенциалы $u,v$ :

$\max\left\{\langle a,u\rangle+\langle b,v\rangle\mid u_i+v_j\leq C_{ij},\ 1\leq i\leq m,\ 1\leq j\leq n\right\}.$

Лагранжевы представления и представления Фенхеля превращают регуляризованный оптимальный транспорт и задачи барицентров в седловые задачи. Энтропическая регуляризация делает транспортный план строго выпуклым и приводит к алгоритму Синкхорна; при малой регуляризации возникает плохая численная обусловленность и смещение относительно нерегуляризованной стоимости. Седловые методы полезны при огромной матрице стоимости, когда доступны произведения с оператором или стохастические выборки, но хранение полного плана невозможно.^[1]

Вероятностные модели и вариационные представления

Сопряжённое представление дивергенции $f$ имеет вид

$D_f(P\|Q)=\sup_{T}\left\{\mathbb E_P[T(X)]-\mathbb E_Q[f^*(T(X))]\right\}.$

Если $Q=Q_\theta$ задаётся генератором, минимизация по $\theta$ и максимизация по тестовой функции $T$ образуют состязательную вероятностную модель; f-GAN является систематическим примером.^[1] Аналогично, вариационные формулы для логарифма нормирующей константы, отношений плотностей, моментов и интегральных вероятностных метрик вводят вспомогательный максимизирующий объект.

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

Когда седловая форма предпочтительнее прямой минимизации

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

Функция $h(Kx)$ негладка, но $\operatorname{prox}_{h^*}$ вычисляется просто; двойственная переменная устраняет необходимость вычислять проксимальное отображение композиции.
Ограничения многочисленны или поступают онлайн, а множители можно обновлять дешевле, чем проектировать $x$ на сложное пересечение.
Вложенный максимум дорог решать до высокой точности на каждом внешнем шаге; одновременная прямо-двойственная схема повторно использует предыдущий двойственный прогресс.
Данные или оператор распределены, а лагранжева связь раскладывается по узлам и рёбрам.
Требуется сертификат качества: прямо-двойственный разрыв одновременно оценивает прямую и двойственную субоптимальность.

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

Ограничения и типичные ошибки

Перестановка минимума и максимума без теоремы. Выпуклость по $x$ и вогнутость по $y$ недостаточны без топологических условий, достижения или коэрцитивности.
Подмена седловой точки стационарной. Равенство градиентов нулю не является глобальным сертификатом в невыпукло-невогнутой игре.
Игнорирование ограничений в условиях первого порядка. На границе нужен нормальный конус или градиентное отображение, а не равенство $F(z)=0$ .
Использование неверного разрыва. На неограниченном $Y$ глобальный прямо-двойственный разрыв часто бесконечен. Ограниченный разрыв должен содержать явно заданное тестовое множество; малый операторный резидуал и малый разрыв — разные гарантии.
Смешение последней итерации и среднего. Оценка $O(1/N)$ для $\overline z_N$ не доказывает сходимость $z_N$ . В играх усреднение может сходиться, когда траектория циклическая.
Сравнение итераций вместо вызовов оракула. Экстраградиент обычно делает два вызова, OGDA — один новый, а PDHG — два умножения на линейный оператор и два проксимальных отображения.
Неверная константа Липшица. Для $F=(\nabla_xL,-\nabla_yL)$ важна совместная операторная норма, включая смешанные производные, а не только гладкость диагональных блоков.
Несогласованные нормы. Градиент измеряется в двойственной норме; евклидова константа нельзя без пересчёта подставлять в энтропийную оценку.
Искусственное ограничение множителей. Проекция двойственных переменных на слишком малый шар создаёт смещённое решение и может скрыть недопустимость прямой точки.
Игнорирование ошибки внутреннего максимума. Вложенная схема получает градиент функции максимума только при условиях теоремы Дански и контролируемой точности внутреннего цикла.
Перенос выпуклых гарантий на GAN. Наблюдаемая стабилизация не доказывает монотонность, выпуклость-вогнутость или глобальную сходимость.
Неполный стохастический анализ. Нужно различать дисперсию, смещение, корреляцию выборок, размер батча и порядок математического ожидания относительно супремума. Сильный и слабый популяционные разрывы могут иметь разные статистические оценки.^[1]

Классические и современные направления

К классическому ядру относятся минимаксные теоремы фон Неймана и Сиона, седловая теория Рокафеллара, лагранжева двойственность, экстраградиент Корпелевич и проксимальная точка. Результат Немировского 2004 года установил оптимальный для общего монотонного липшицева оракула порядок $O(1/N)$ для Mirror-Prox. Метод PDHG, или алгоритм Чамболла — Пока, использует композитную билинейную структуру и дешёвые проксимальные отображения.

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

Последняя итерация. Исследуются условия, при которых OGDA, экстраградиент и якорные методы сходятся без усреднения. Для ограниченных матричных игр линейная сходимость последней итерации может следовать из свойств конкретной полиэдральной геометрии и строгой комплементарности, а не из одной монотонности.^[1]
Стохастические и конечносуммовые методы. Редукция дисперсии, возрастающие батчи и рандомизированные блочные шаги уменьшают число компонентных градиентов. Гарантия должна отдельно показывать оптимизационный и статистический члены.
Адаптивность. Линейный поиск и варианты без априорно заданных параметров оценивают локальную липшицевость по ходу работы. Адаптивный шаг не устраняет необходимость структурного предположения о монотонности или его ослаблении.
Ускорение. При сильной кривизне одного блока, билинейной разделимости или доступе к проксимальному оракулу возможны улучшенные зависимости от блоковых чисел обусловленности. Нижние оценки показывают, что ускорение обычной минимизации $O(1/N^2)$ не переносится автоматически на общий гладкий монотонный седловой оператор.^[1]
Невыпукло-вогнутые и невыпукло-невогнутые задачи. Целью часто становится малая норма градиента внешней функции $\varphi(x)=\max_yL(x,y)$ , локальная минимаксная точка или иная игровая стационарность. Это другой класс результатов; слово «седловой» в названии алгоритма не восстанавливает глобальную выпуклую теорию.
Обобщение и приватность. Для стохастических седловых задач различают эмпирическую оптимизацию и популяционный разрыв; регуляризация обеспечивает устойчивость, но вносит смещение. Современные приватные методы получают оптимальные по порядку оценки сильного разрыва при выпукло-вогнутой липшицевой структуре и явных ограничениях на область и чувствительность.^[1]
Результаты 2025—2026 годов. Развиваются ускоренные расщепления с редукцией дисперсии для обобщённых уравнений, включающих минимаксные задачи, а также адаптивные экстраградиентные методы с неэргодическими гарантиями без заранее известной глобальной константы Липшица.^[1] По состоянию на июль 2026 года результаты о последней итерации простых стохастических EG/OGDA при стандартном оракуле с ограниченной дисперсией продолжают уточняться; новые утверждения о схемах возмущения и якорных схемах имеют статус препринтов и не должны цитироваться как устоявшаяся общая теорема.^[1]

Практическая схема анализа

Зафиксировать ориентацию $\min_x\max_y$ , области $X,Y$ и правила достижения экстремумов.
Проверить выпуклость по $x$ , вогнутость по $y$ , замкнутость, полунепрерывность и компактность либо коэрцитивность.
Построить оператор $F=(\partial_xL,-\partial_yL)$ вместе с нормальными конусами; проверить монотонность, сильную монотонность и липшицевость в одной и той же паре норм.
Выбрать сертификат: глобальный или ограниченный прямо-двойственный разрыв, резидуал вариационного неравенства, расстояние до решения либо стационарность внешней функции. Указать, относится ли оценка к последней или усреднённой итерации.
Выбрать геометрию и проксимальное отображение, соответствующие множествам: евклидова геометрия — для шаров и линейных подпространств, энтропийная — для симплексов, блочная — для неоднородных переменных.
Посчитать стоимость вызова каждого блока, проекции, проксимального отображения и коммуникации. Затем сравнивать методы по общей оракульной и вычислительной сложности.
В стохастической задаче записать условную несмещённость, момент шума, размер батча и различие эмпирического и популяционного критериев.
Для невыпуклой модели явно отказаться от глобальных выпукло-вогнутых выводов и сформулировать достижимое локальное понятие решения.

См. также

Примечания

Литература

Rockafellar R. T. Convex Analysis. — Princeton: Princeton University Press, 1970. — 472 с.
Ekeland I., Temam R. Convex Analysis and Variational Problems. — Philadelphia: SIAM, 1999. — 402 с.
Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity Problems. — New York: Springer, 2003. — T. I—II.
Boyd S., Vandenberghe L. Convex Optimization. — Cambridge: Cambridge University Press, 2004. — 716 с.
Peyré G., Cuturi M. Computational Optimal Transport. — Now Publishers, 2019. — T. 11. — С. 355—607. — (Foundations and Trends in Machine Learning).
Sion M. On General Minimax Theorems // Pacific Journal of Mathematics. — 1958. — Т. 8. — № 1. — С. 171—176.
Корпелевич Г. М. Экстраградиентный метод для нахождения седловых точек и других задач // Экономика и математические методы. — 1976. — Т. 12. — С. 747—756.
Nemirovski A. Prox-Method with Rate of Convergence $O(1/t)$ for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems // SIAM Journal on Optimization. — 2004. — Т. 15. — № 1. — С. 229—251.
Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust Stochastic Approximation Approach to Stochastic Programming // SIAM Journal on Optimization. — 2009. — Т. 19. — № 4. — С. 1574—1609.
Chambolle A., Pock T. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging // Journal of Mathematical Imaging and Vision. — 2011. — Т. 40. — № 1. — С. 120—145.
Mertikopoulos P., Lecouat B., Zenati H., Foo C.-S., Chandrasekhar V., Piliouras G. Optimistic Mirror Descent in Saddle-Point Problems: Going the Extra (Gradient) Mile // International Conference on Learning Representations. — 2019.
Mokhtari A., Ozdaglar A., Pattathil S. A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems // Proceedings of AISTATS. — 2020. — Т. 108. — С. 1497—1507.
Ouyang Y., Xu Y. Lower Complexity Bounds of First-Order Methods for Convex-Concave Bilinear Saddle-Point Problems // Mathematical Programming. — 2021. — Т. 185. — С. 1—35.
Goodfellow I., Pouget-Abadie J., Mirza M. et al. Generative Adversarial Nets // Advances in Neural Information Processing Systems. — 2014. — Т. 27. — С. 2672—2680.
Madry A., Makelov A., Schmidt L., Tsipras D., Vladu A. Towards Deep Learning Models Resistant to Adversarial Attacks // International Conference on Learning Representations. — 2018.
Agarwal A., Beygelzimer A., Dudík M., Langford J., Wallach H. A Reductions Approach to Fair Classification // Proceedings of ICML. — 2018. — Т. 80. — С. 60—69.
Bassily R., Guzmán C., Menart M. Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap // Proceedings of COLT. — 2023. — Т. 195. — С. 2482—2508.
Tran-Dinh Q. VFOSA: Variance-Reduced Fast Operator Splitting Algorithms for Generalized Equations // Journal of Machine Learning Research. — 2025. — Т. 26. — С. 1—68.
Zhang J., Hong M., Wang M., Zhang S. Generalization Bounds for Stochastic Saddle Point Problems // PMLR. 2021.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D0%B5%D0%B4%D0%BB%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%28%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F%29»

Категории: Математическая оптимизация | Машинное обучение | Энциклопедия анализа данных | Выпуклый анализ | Теория игр