Двойственная формулировка: цены Канторовича

Задача транспорта: найти план gamma(x,y) с минимальной стоимостью. Звучит как линейное программирование - и это оно и есть. Двойственная LP даёт функции phi(x) и psi(y) - цены в точках источника и назначения. А потом оказывается: эти цены - это и есть critic в Wasserstein GAN. Один и тот же объект: оптимальный план перевозки и 1-Lipschitz функция различения. Канторович не знал о нейросетях. Он просто решал задачу снабжения советских заводов сырьём - и открыл принцип, на котором 75 лет спустя строятся generative models.

• **WGAN critic**: KR-теорема $W_1 = \sup_{\|f\|_L \leq 1} [\mathbb{E}_{\mu}[f] - \mathbb{E}_{\nu}[f]]$ - это буквально loss функция критика Wasserstein GAN. Gradient penalty и spectral normalization - способы обеспечить Lipschitz-ограничение
• **Input Convex Neural Networks**: теорема Брение дает: при квадратичной стоимости dual potential - выпуклая функция, карта T = grad phi. ICNN параметризуют phi напрямую, давая scalable OT-maps для domain adaptation
• **Sinkhorn как dual-итерации**: scaling vectors u, v в алгоритме Синхорна - это exp(phi/eps) и exp(psi/eps). Логарифм Sinkhorn-потенциалов - это regularized dual OT variables

Предварительные знания

• Задача Канторовича (primal формулировка)
• Sinkhorn алгоритм
• Преобразование Лежандра (желательно)

• Задача Канторовича
• Алгоритм Синхорна

Двойственность Канторовича

1942 год. Советский математик Леонид Канторович, будущий нобелевский лауреат по экономике, решает задачу транспорта. Он замечает, что задача - линейная программа. А у любой LP есть двойственная. Через 75 лет эта двойственность окажется в сердце Wasserstein GAN.

**Primal задача**: найти транспортный план $\gamma \in \Pi(\mu, \nu)$ с минимальной стоимостью: $$W_c(\mu, \nu) = \min_{\gamma \in \Pi(\mu, \nu)} \int c(x, y) \, d\gamma(x, y)$$

**Двойственная задача** (Канторович): найти функции $\varphi(x)$ и $\psi(y)$ - цены источника и цены назначения - максимизирующие суммарную выплату: $$W_c(\mu, \nu) = \sup_{\varphi \oplus \psi \leq c} \left[ \int \varphi \, d\mu + \int \psi \, d\nu \right]$$ при ограничении $\varphi(x) + \psi(y) \leq c(x, y)$ для всех $x, y$.

**Сильная двойственность**: при слабых условиях регулярности primal = dual (нет зазора двойственности). Экономически: цена транспортировки равна максимуму рыночных цен, согласованных с ограничением стоимости. Математически: теорема LP-двойственности в бесконечномерном случае.

Kantorovich-Rubinstein и W_1

При $c(x, y) = \|x - y\|$ (расстояние $W_1$) двойственная задача упрощается радикально. Ограничение $\varphi(x) + \psi(y) \leq \|x - y\|$ при $\psi = -\varphi$ превращается в Липшицево условие.

**Теорема Канторовича-Рубинштейна**: $$W_1(\mu, \nu) = \sup_{\|f\|_L \leq 1} \left[ \mathbb{E}_{x \sim \mu}[f(x)] - \mathbb{E}_{y \sim \nu}[f(y)] \right]$$ Максимум берётся по всем 1-Липшицевым функциям $f$. Это и есть critic loss в Wasserstein GAN.

Именно это уравнение написано в статье Arjovsky et al. 2017 как обоснование WGAN. Ограничение на Липшицевость критика (weight clipping, gradient penalty) - практическая реализация $\|f\|_L \leq 1$. Critic обучается максимизировать разность ожиданий - буквально решает двойственную задачу Канторовича.

c-вогнутые функции и теорема Брение

Для общей стоимости $c(x,y)$ оптимальные dual-потенциалы удовлетворяют условию c-сопряжённости. Функция $\varphi$ называется c-вогнутой, если: $$\varphi(x) = \inf_y [c(x,y) - \psi(y)]$$

Это обобщение выпуклого сопряжения Лежандра. При $c(x,y) = \langle x, y \rangle$ - буквально преобразование Лежандра. При $c(x,y) = \|x-y\|^2/2$ связь с выпуклостью ещё теснее.

**Теорема Брение** (1991): при $c(x,y) = \|x-y\|^2$ оптимальный dual potential $\varphi$ является выпуклой функцией, и оптимальная карта транспорта: $T = \nabla \varphi$. Градиент выпуклой функции - и есть карта Монжа. Это соединяет выпуклый анализ, OT и теорию полярных разложений.

Ключевые идеи

• **Двойственность Канторовича**: primal (min coupling) = dual (max over potentials phi, psi). Нет зазора при слабых условиях регулярности
• **KR-теорема**: $W_1(\mu, \nu) = \sup_{\|f\|_L \leq 1}[\mathbb{E}_{\mu}[f] - \mathbb{E}_{\nu}[f]]$. WGAN critic - это 1-Lipschitz dual potential
• **c-вогнутые функции**: обобщение Лежандра для произвольной стоимости $c$. Оптимальные потенциалы всегда c-вогнуты
• **Теорема Брение**: при $c = \|\cdot\|^2$ dual potential выпукла, оптимальная карта $T = \nabla\varphi$. Мост между OT, выпуклым анализом и ICNN

Куда дальше

Двойственность открывает практические инструменты OT:

• Wasserstein GAN — Обучение KR dual potential как critic нейросети
• Теорема Брение — Оптимальная карта через градиент выпуклого потенциала
• Двойственная структура в IG — Primal-dual как e/m-двойственность Амари
• Вычислительный OT — Sinkhorn потенциалы как regularized dual variables

Вопросы для размышления

• Critic в WGAN решает задачу максимизации KR dual. Что происходит с этой задачей, если распределения real и fake не имеют перекрывающегося носителя - и как это связано с проблемами обычного GAN?
• Теорема Брение работает при c = ||x-y||^2. Что меняется при c = ||x-y|| (задача W_1)? Почему оптимальная карта в этом случае не обязана быть градиентом выпуклой функции?
• Sinkhorn потенциалы u, v сходятся к exp(phi/eps), exp(psi/eps). При eps -> 0 что происходит с этими потенциалами? Как это связано с точной двойственностью Канторовича?

Связанные уроки

• ot-07-wgan — WGAN critic - это в точности dual potential Канторовича
• ot-06-brenier — Теорема Брение - следствие двойственности при квадратичной стоимости
• ot-04-sinkhorn — Sinkhorn = двойственные переменные u, v в log-domain
• ot-02-kantorovich — Primal задача Канторовича - отправная точка для двойственности
• ig-05-dual-flat — Primal-dual структура - та же идея двойственности в информационной геометрии
• calc-01-sequences