Зеркальный спуск: оптимизация в двойственном пространстве

Обычный градиентный спуск обращается с симплексом вероятностей как с куском $\mathbb{R}^n$ - делает шаг и получает отрицательные вероятности. Дальше - проекция обратно на симплекс, которая не знает ничего о геометрии задачи. Nemirovski и Yudin в 1983 предложили иначе: работать в геометрии задачи с самого начала, через зеркальную функцию, отражающую структуру допустимого множества. Следствия неожиданные: Hedge (оптимальный алгоритм для задачи N экспертов), AdaBoost (через regret bounds) и Adagrad (адаптивный шаг в LLM-обучении) - все это Mirror descent с разными зеркалами.

• **Adagrad и Adam в LLM:** обучение GPT-4, LLaMA - Online Mirror Descent с адаптивной Bregman-метрикой. Adagrad - точный Mirror Descent. Adam - приближённый, с расходимостью на контрпримерах (Reddi et al. 2018). AMSGrad исправляет это через монотонный $\hat{v}_t$
• **Natural Policy Gradient в RL:** PPO и TRPO (OpenAI) используют натуральный градиент - Mirror Descent с зеркалом из метрики Фишера. Ограничение KL между старой и новой политикой - Bregman-проекция, не евклидова. Это объясняет устойчивость PPO к размеру шага
• **Hedge в online advertising:** распределение бюджета между рекламными каналами в реальном времени - задача N экспертов. Google и Meta используют варианты Multiplicative Weights с гарантиями regret bounds для auto-bidding систем
• **Sinkhorn в optimal transport:** алгоритм Синкхорна для OT-расстояний (используется в WGAN, domain adaptation) - Mirror descent с KL-Bregman на бистохастическом многообразии. Каждая строчная и столбцовая нормировка - один шаг Mirror descent

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

• Bregman-дивергенция как обобщение квадратичного расстояния
• Выпуклые функции и их субдифференциалы
• KL-дивергенция как частный случай Bregman при ψ = отрицательная энтропия

• KL как Bregman-дивергенция
• Натуральный градиент
• e- и m-проекции

Mirror map и алгоритм зеркального спуска

Почему обычный градиентный спуск ломается на симплексе

Стандартный градиентный спуск: $x_{t+1} = x_t - \eta \nabla f(x_t)$. На симплексе вероятностей $\Delta_n = \{x \geq 0, \sum x_i = 1\}$ этот шаг мгновенно выводит за пределы допустимого множества - компоненты становятся отрицательными. Проекция обратно на $\Delta_n$ стоит $O(n \log n)$ и не учитывает геометрию симплекса: евклидова метрика одинаково штрафует за сдвиг у края и у центра, хотя геометрически это разные расстояния.

**Mirror descent** (Nemirovski, Yudin 1983) решает это принципиально: вместо шага в исходном пространстве $X$ шаг делается в **двойственном пространстве** $X^*$ через градиент зеркальной функции $\nabla \psi$, которая отражает геометрию задачи. Алгоритм:

Здесь $\tilde{x}_{t+1} = (\nabla \psi)^{-1}(\nabla \psi(x_t) - \eta \nabla f(x_t))$ - некалиброванный шаг в двойственном пространстве, а второй шаг - Bregman-проекция обратно на $X$. **Bregman-дивергенция** $D_\psi$:

**Два ключевых случая Mirror map:** - $\psi(x) = \frac{1}{2}\|x\|^2$ (квадратичная) $\Rightarrow$ $D_\psi(x,y) = \frac{1}{2}\|x-y\|^2$, $\nabla \psi = \text{Id}$. Mirror descent = обычный GD. - $\psi(x) = \sum_i x_i \log x_i$ (отрицательная энтропия на $\Delta_n$) $\Rightarrow$ $D_\psi(x,y) = \text{KL}(x \| y)$. Mirror descent = **Exponentiated Gradient**: $x_{t+1}(i) \propto x_t(i) \cdot \exp(-\eta \nabla f(x_t)_i)$. Симплекс сохраняется автоматически.

Условие на $\psi$: строго выпуклая, дифференцируемая, $\nabla \psi: X \to X^*$ - диффеоморфизм. Это гарантирует, что шаг в двойственном пространстве однозначно обратим.

Hedge и Multiplicative Weights: online learning на симплексе

N экспертов, T раундов: как не проиграть лучшему?

Online learning: на каждом шаге $t$ выбирается распределение $w_t$ над $N$ экспертами, получается вектор потерь $l_t \in [0,1]^N$, несётся потеря $\langle w_t, l_t \rangle$. Цель - минимизировать **regret**: разницу между суммарной потерей и потерей лучшего эксперта по итогам:

**Hedge (Freund, Schapire 1997)** - это Exponentiated Gradient на симплексе с функцией потерь $f_t(w) = \langle w, l_t \rangle$, или эквивалентно Mirror descent с $\psi = \sum w_i \log w_i$:

Regret bound: при $\eta = \sqrt{2 \ln N / T}$ алгоритм гарантирует $R_T \leq \sqrt{2T \ln N}$. Это **оптимально в minimax-смысле**: никакой алгоритм не может гарантировать меньше. Интерпретация: за $T$ раундов среди $N$ экспертов цена незнания лучшего эксперта заранее равна $O(\sqrt{T \ln N})$.

**Boosting = специальный случай Hedge.** AdaBoost - это Multiplicative Weights, где эксперты - слабые классификаторы, потеря - ошибка на объекте. Regret bound AdaBoost - это regret bound Hedge. Аналогично: **Follow the Regularized Leader (FTRL)** с энтропийным регуляризатором эквивалентен Hedge при линейных потерях.

Натуральный градиент, Adagrad и Adam как Mirror descent

Единая картина: разные Mirror map - разные оптимизаторы

Mirror descent - это семейство, параметризованное выбором $\psi$. Разные $\psi$ порождают классические оптимизаторы ML-сообщества:

**Натуральный градиент** (Amari 1998) - Mirror descent с $\psi(\theta) = \frac{1}{2} \theta^\top F(\theta) \theta$, где $F$ - матрица Фишера. На практике: $\theta_{t+1} = \theta_t - \eta F(\theta_t)^{-1} \nabla \mathcal{L}$. Bregman-дивергенция здесь - локально квадратичное приближение KL между $p_\theta$ и $p_{\theta_0}$.

**Adagrad** (Duchi et al. 2011): $\psi(x) = \frac{1}{2} \sum_i G_{ii} x_i^2$, где $G_{ii} = \sum_{s \leq t} g_{si}^2$ - сумма квадратов прошлых градиентов по координате $i$. Bregman-дивергенция: $D_\psi(x,y) = \frac{1}{2}(x-y)^\top G (x-y)$. Адаптивная метрика: редкие координаты получают большой шаг, частые - малый.

**Adam как приближённый Mirror descent.** Adam использует $v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2$ вместо кумулятивной суммы Adagrad. Это не точный Mirror descent с фиксированным $\psi$ - метрика меняется со временем. Reddi et al. 2018 (AMSGrad) доказали, что стандартный Adam может расходиться из-за немонотонности $v_t$. AMSGrad фиксирует: $\hat{v}_t = \max(\hat{v}_{t-1}, v_t)$ - монотонно возрастающая Bregman-метрика, правильный Mirror descent. На практике Adam и AMSGrad дают сходные результаты, но теория AMSGrad корректна.

Что унести из урока

• **Mirror descent** = шаг в двойственном пространстве через $\nabla \psi$, потом Bregman-проекция. Формула: $\nabla \psi(x_{t+1}) = \nabla \psi(x_t) - \eta \nabla f(x_t)$
• **$\psi = \sum x_i \log x_i$** (отрицательная энтропия): Bregman = KL, алгоритм = Exponentiated Gradient. Симплекс сохраняется автоматически через softmax-обратимость $\nabla \psi$
• **Hedge / Multiplicative Weights**: EG на симплексе с линейными потерями. Regret bound $O(\sqrt{T \ln N})$ - оптимальный minimax. AdaBoost = Hedge со слабыми классификаторами как экспертами
• **Натуральный градиент**: Mirror Descent с Fisher-Bregman. PPO и TRPO используют KL-ограничение политики - это Bregman-проекция, объясняющая устойчивость к шагу
• **Adagrad = Online Mirror Descent** с $G_t = \mathrm{diag}(\sum g_s^2)$. Adam - приближённый Mirror Descent; AMSGrad (монотонный $\hat{v}_t$) - корректный с доказанными regret bounds

Куда дальше

Mirror descent - мост между информационной геометрией и практическими оптимизаторами:

• Information geometry в deep learning — VAE, диффузия, LLM-обучение через Mirror Descent с разными Bregman
• e/m-проекции и EM — M-step EM - Bregman-проекция, тот же механизм Mirror step

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

• Hedge гарантирует regret $O(\sqrt{T \ln N})$ при оптимальном $\eta = \sqrt{2 \ln N / T}$. Но $T$ обычно неизвестно заранее. AdaHedge и Squint адаптивно выбирают $\eta$ на ходу и достигают того же bound без знания $T$. Какое свойство Mirror map позволяет это сделать, и как меняется $\psi$ при адаптивном $\eta$?
• Натуральный градиент = Mirror Descent с матрицей Фишера. В больших моделях (LLM) Fisher-матрица $d \times d$ невычислима. K-FAC аппроксимирует её блочно-диагонально. Ухудшает ли это теоретические гарантии Mirror Descent, и почему K-FAC всё равно работает лучше SGD на практике?
• Adagrad накапливает квадраты градиентов монотонно - шаг убывает до нуля. Adam использует экспоненциальное скользящее среднее - шаг не убывает. Который из них правильный Mirror Descent, и почему Adam работает лучше на практике несмотря на теоретические проблемы с расходимостью?

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

• ig-08-info-projection — m-проекция с Bregman-дивергенцией - это шаг Mirror descent на выпуклом множестве
• ig-07-natural-gradient — Натуральный градиент = Mirror descent с зеркалом ψ(θ) = KL, связь через метрику Фишера
• ig-04-kl-bregman — Bregman-дивергенция - основа Mirror map; KL - частный случай при ψ = отрицательная энтропия
• ig-10-deep-learning — Adam и Adagrad - приближённые Mirror descent с адаптивной Bregman-метрикой
• stat-01-sampling