Метод зеркального спуска (оптимизация)

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

Перейти к: навигация, поиск
Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol) и проверена участником Aleksei Kovalenko 20:00, 14 июля 2026 (MSD)


Содержание

Метод зеркального спуска (англ. mirror descent, MD) — метод первого порядка для выпуклой оптимизации, в котором линейная модель целевой функции регуляризуется не обязательно квадратом евклидова расстояния, а дивергенцией Брэгмана, согласованной с геометрией допустимого множества. Метод введён А. С. Немировским и Д. Б. Юдиным[1]; современная форма как нелинейного проекционного субградиентного метода дана А. Беком и М. Тебуллем[1].

Зеркальный спуск включает градиентный спуск и проекционный субградиентный метод как евклидов частный случай, а на вероятностном симплексе с энтропийной геометрией приводит к экспоненциальному обновлению весов. Главное практическое преимущество метода возникает тогда, когда норма, ограничения и структура градиентов существенно неевклидовы: например, на симплексе оценка зависит от размерности как \sqrt{\ln d}, тогда как прямой евклидов анализ часто даёт зависимость порядка \sqrt d.

Постановка задачи

Пусть E — конечномерное вещественное линейное пространство, E^* — его двойственное пространство, X\subset E — непустое замкнутое выпуклое множество. Рассматривается задача

\min_{x\in X} f(x),

где f:X\to\mathbb{R}\cup\{+\infty\} — собственная замкнутая выпуклая функция. В негладком случае оракул первого порядка в точке x_t возвращает субградиент g_t\in\partial f(x_t)\subset E^*. В стохастической задаче

f(x)=\mathbb{E}_{\xi}[F(x,\xi)]

используется случайная оценка G_t=G(x_t,\xi_t), для которой обычно предполагают условную несмещённость

\mathbb{E}[G_t\mid\mathcal{F}_{t-1}]\in\partial f(x_t).

Здесь \mathcal{F}_{t-1} — информация, накопленная до построения G_t.

Норма и двойственная норма

На E фиксируется норма \|\cdot\|. Двойственная норма на E^* определяется равенством

\|z\|_* = \sup_{\|x\|\leq 1}\langle z,x\rangle.

Обобщённое неравенство Гёльдера имеет вид

\langle z,x\rangle\leq\|z\|_*\,\|x\|.

Именно пара норм, а не выбранные координаты, определяет константу Липшица функции и масштаб ошибки. Например, на симплексе естественна норма \|\cdot\|_1, а субградиенты измеряются в \|\cdot\|_\infty. Замена этой пары на евклидову может внести лишний множитель порядка \sqrt d.

Дивергенция Брэгмана и зеркальная геометрия

Пусть \psi:X\to\mathbb{R}\cup\{+\infty\} — дифференцируемая на \mathrm{ri}\,X строго выпуклая функция, называемая порождающей функцией расстояния, зеркальным потенциалом или прокси-функцией. Дивергенция Брэгмана[1] задаётся как

D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.

Она неотрицательна, но, вообще говоря, несимметрична и не удовлетворяет неравенству треугольника. Поэтому D_\psi — не метрика. Порядок аргументов в формулах существенен.

Для анализа базового метода обычно предполагается, что \psi является \sigma-сильно выпуклой относительно \|\cdot\|:

D_\psi(x,y)\geq\frac{\sigma}{2}\|x-y\|^2.

Это неравенство предполагается для всех допустимых x и y.

Если \psi — функция Лежандра, то отображение \nabla\psi переводит внутренность прямой области в двойственное пространство, а обратное отображение задаётся градиентом сопряжённой функции Фенхеля:

(\nabla\psi)^{-1}=\nabla\psi^*.

Геометрическая интуиция

Обычный градиент g_t — ковектор, то есть элемент E^*. Вычитание его из точки x_t\in E имеет инвариантный смысл только после выбора отождествления прямого и двойственного пространств. Евклидово скалярное произведение делает такое отождествление незаметным. Зеркальный спуск выполняет операцию явно:

  1. переводит x_t в двойственные координаты y_t=\nabla\psi(x_t);
  2. делает шаг y_{t+1/2}=y_t-\eta_t g_t в двойственном пространстве;
  3. возвращается через \nabla\psi^* и, при наличии ограничений, выполняет брэгмановскую проекцию на X.

В эквивалентной вариационной форме эти три действия объединяются в одну задачу. Геометрия задаётся кривизной \psi: локально матрица \nabla^2\psi(x) играет роль переменного метрического тензора, а формальный малый шаг имеет вид

x_{t+1}-x_t\approx-\eta_t[\nabla^2\psi(x_t)]^{-1}g_t.

Это объясняет сходство с предобусловливанием, но точный зеркальный шаг определяется глобальной брэгмановской дивергенцией, а не только локальной квадратичной аппроксимацией.

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

При шагах \eta_t>0 основная итерация имеет вид

x_{t+1}\in\operatorname{arg\,min}_{x\in X}\left\{\eta_t\langle g_t,x\rangle+D_\psi(x,x_t)\right\}.

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

Псевдокод

Вход: множество X, потенциал \psi, начальная точка x_1\in\mathrm{ri}\,X, шаги \eta_1,\ldots,\eta_T.

  1. Для t=1,\ldots,T:
    • получить g_t\in\partial f(x_t) или стохастическую оценку G_t;
    • вычислить x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\eta_t\langle g_t,x\rangle+D_\psi(x,x_t)\};
  2. Вернуть последнюю точку либо взвешенное среднее
    • \bar x_T=(\sum_{t=1}^T\eta_t x_t)/(\sum_{t=1}^T\eta_t).

Для негладких выпуклых задач гарантия обычно относится к \bar x_T, а не к последней итерации. Замена усреднённой точки последней без дополнительной теории — распространённая ошибка.

Основное одношаговое неравенство

Оптимальность зеркального шага и трёхточечное тождество Брэгмана дают для любого u\in X

\eta_t\langle g_t,x_{t+1}-u\rangle\leq D_\psi(u,x_t)-D_\psi(u,x_{t+1})-D_\psi(x_{t+1},x_t).

Если \psi \sigma-сильно выпукла, то после переноса x_t-x_{t+1}, применения неравенства Гёльдера и неравенства Юнга получается фундаментальная оценка

\eta_t\langle g_t,x_t-u\rangle\leq D_\psi(u,x_t)-D_\psi(u,x_{t+1})+\frac{\eta_t^2}{2\sigma}\|g_t\|_*^2.

Телескопирование дивергенций Брэгмана в этой формуле является основой большинства классических доказательств.

Оценки сходимости

Выпуклая липшицева задача

Теорема. Пусть f выпукла на X, \psi \sigma-сильно выпукла относительно \|\cdot\|, x^*\in\operatorname{arg\,min}_{x\in X} f(x), а выбранные субградиенты удовлетворяют \|g_t\|_*\leq G. Тогда для любого набора положительных шагов

f(\bar x_T)-f(x^*)\leq\frac{D_\psi(x^*,x_1)+\frac{G^2}{2\sigma}\sum_{t=1}^T\eta_t^2}{\sum_{t=1}^T\eta_t}.

В частности, если известно D_\psi(x^*,x_1)\leq R_\psi^2 и взять постоянный шаг

\eta=\frac{R_\psi\sqrt{2\sigma}}{G\sqrt T},

то

f(\bar x_T)-f(x^*)\leq G R_\psi\sqrt{\frac{2}{\sigma T}}.

Это оптимальный по порядку темп O(T^{-1/2}) для общего класса липшицевых негладких выпуклых функций при оракуле первого порядка[1].

Сильно выпуклая негладкая задача

Пусть дополнительно f является \mu-сильно выпуклой относительно той же нормы:

f(y)\geq f(x)+\langle g,y-x\rangle+\frac{\mu}{2}\|y-x\|^2,\quad g\in\partial f(x).

При \|g_t\|_*\leq G, \sigma-сильной выпуклости \psi и шагах \eta_t=\sigma/(\mu t) стандартное равномерное усреднение даёт

f\left(\frac1T\sum_{t=1}^T x_t\right)-f(x^*)\leq\frac{G^2}{2\mu T}(1+\ln T).

Логарифм не является информационно-теоретически необходимым. Полиномиально взвешенное усреднение, суффиксное усреднение или перезапуски дают при тех же ограничениях порядок O(G^2/(\mu T)); конкретная константа зависит от схемы весов и нумерации шагов. Поэтому утверждение оценки O(T^{-1}) без описания усреднения недостаточно.

Гладкость относительно зеркального потенциала

Классический анализ гладкого градиентного спуска предполагает липшицевость градиента в норме. Более общее условие относительной гладкости требует, чтобы для некоторого L>0

f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+L D_\psi(y,x).

Для дважды дифференцируемых функций это соответствует неравенству кривизн \nabla^2 f(x)\leq L\nabla^2\psi(x) в смысле порядка Лёвнера. При выпуклости f, относительной L-гладкости, существовании решения и точном решении зеркальной подзадачи шаг

x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\langle\nabla f(x_t),x-x_t\rangle+L D_\psi(x,x_t)\}

порождает невозрастающие значения цели и удовлетворяет оценке последней вычисленной точки

f(x_{T+1})-f(x^*)\leq\frac{L D_\psi(x^*,x_1)}{T}.

При дополнительной относительной сильной выпуклости, то есть при нижней оценке той же формы с \mu D_\psi(y,x), специальные схемы брэгмановского градиента допускают линейную сходимость; ориентация дивергенции и точная схема шага входят в предпосылки и не могут быть опущены[1]. Относительная гладкость особенно полезна для логарифмических барьеров, задач оптимального дизайна и моделей, у которых евклидова константа Липшица градиента бесконечна или крайне велика.

Стохастический зеркальный спуск

Пусть G_t условно несмещён, \mathbb{E}[\|G_t\|_*^2\mid\mathcal{F}_{t-1}]\leq G^2, f выпукла, а \psi \sigma-сильно выпукла. Тогда

\mathbb{E}[f(\bar x_T)-f(x^*)]\leq\frac{D_\psi(x^*,x_1)+\frac{G^2}{2\sigma}\sum_{t=1}^T\eta_t^2}{\sum_{t=1}^T\eta_t}.

Следовательно, при настроенном постоянном шаге математическое ожидание ошибки имеет порядок O(T^{-1/2}). Для \mu-сильно выпуклой функции убывающие шаги и надлежащее усреднение дают порядок O(G^2/(\mu T)). Эти результаты требуют ограничения второго момента в двойственной норме, а не только конечной дисперсии каждой координаты[1].

Оценки с высокой вероятностью требуют дополнительных хвостовых предпосылок либо робастизации. При субгауссовском шуме применимы мартингальные концентрационные неравенства. При наличии лишь конечного момента порядка 1+\kappa, 0<\kappa\leq1, обычная теория второго момента неприменима; равномерно выпуклые потенциалы и робастные варианты SMD позволяют получать оптимальные для тяжёлых хвостов темпы[1]. Общие хвостовые оценки для негладкого SMD при более слабых, чем субгауссовские, режимах получены К. Элдовой и А. Паудиче[1].

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

Евклидов градиентный и проекционный спуск

Пусть E=\mathbb{R}^d, \psi(x)=\frac12\|x\|_2^2. Тогда

D_\psi(x,y)=\frac12\|x-y\|_2^2

и зеркальный шаг совпадает с евклидовой проекцией:

x_{t+1}=\Pi_X(x_t-\eta_t g_t).

Если X=\mathbb{R}^d, это обычный градиентный или субградиентный спуск. Тем самым зеркальный спуск не является «градиентным спуском после нелинейной замены переменных» в общем случае, но строго содержит евклидов метод как частный случай.

Экспоненциальное обновление на симплексе

Пусть

\Delta_d=\{x\in\mathbb{R}_+^d:\sum_{i=1}^d x_i=1\}

и выбран отрицательный энтропийный потенциал

\psi(x)=\sum_{i=1}^d x_i\ln x_i.

Тогда D_\psi(x,y)=\sum_i x_i\ln(x_i/y_i) — дивергенция Кульбака — Лейблера, являющаяся важным частным случаем дивергенции Брэгмана. Потенциал 1-сильно выпукл относительно \|\cdot\|_1 на симплексе вследствие неравенства Пинскера. Решение зеркальной подзадачи имеет закрытую форму

x_{t+1,i}=\frac{x_{t,i}\exp(-\eta_t g_{t,i})}{\sum_{j=1}^d x_{t,j}\exp(-\eta_t g_{t,j})}.

Это экспоненциальное обновление, также лежащее в основе алгоритмов multiplicative weights и Hedge. Если x_{1,i}=1/d, \|g_t\|_\infty\leq G, то для любого u\in\Delta_d

\sum_{t=1}^T\langle g_t,x_t-u\rangle\leq\frac{\ln d}{\eta}+\frac{\eta G^2T}{2}.

При \eta=\sqrt{2\ln d}/(G\sqrt T) статическое сожаление не превосходит

G\sqrt{2T\ln d}.

Зависимость от размерности логарифмическая. Для устойчивого вычисления обновления следует вычитать максимум из логитов до экспоненцирования и выполнять нормировку в логарифмическом масштабе.

Другие геометрии

Область и норма Типичный потенциал Дивергенция и вычислительный эффект
\mathbb{R}^d, \|\cdot\|_2 \psi(x)=\frac12\|x\|_2^2 Квадрат евклидова расстояния; обычная проекция
Симплекс, \|\cdot\|_1 \psi(x)=\sum_i x_i\ln x_i KL-дивергенция; мультипликативное обновление за O(d)
Шар \ell_p, 1<p\leq2 Масштабированный квадрат \|x\|_p^2 Согласование с разреженной геометрией; двойственная норма \ell_q, где 1/p+1/q=1
Положительный ортант Логарифмический барьер \psi(x)=-\sum_i\ln x_i Барьерная брэгмановская геометрия; сохранение строгой положительности
Положительно полуопределённые матрицы плотности X\geq0, \mathrm{tr}\,X=1 Энтропия фон Неймана \psi(X)=\mathrm{tr}(X\ln X) Матричное экспоненциальное обновление; спектральная декомпозиция обычно доминирует в стоимости

Выбор p=1+O(1/\ln d) часто используется как гладкая аппроксимация геометрии \ell_1. Правильный потенциал одновременно должен давать малый брэгмановский радиус, достаточную сильную выпуклость и дешёвую прокс-операцию.

Связь с родственными методами

Брэгмановская проекция

В неограниченном случае зеркальный шаг записывается как

y_{t+1}=\nabla\psi^*(\nabla\psi(x_t)-\eta_t g_t).

При ограничениях следующий элемент можно интерпретировать как брэгмановскую проекцию двойственного шага:

x_{t+1}\in\operatorname{arg\,min}_{x\in X}D_\psi(x,y_{t+1}).

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

Proximal mirror descent

Для составной задачи

\min_{x\in X}\{f(x)+r(x)\},

где r выпукла и имеет доступный проксимальный оператор, проксимальный зеркальный спуск использует

x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\eta_t\langle g_t,x\rangle+\eta_t r(x)+D_\psi(x,x_t)\}.

Это не то же самое, что базовый MD, если r включена только через субградиент. Точное включение r часто сохраняет разреженность и улучшает константы. Проксимальный градиентный метод обычно означает евклидову схему для гладкой f и негладкой r; брэгмановский проксимальный градиент является её неевклидовым обобщением.

Dual averaging

Метод двойственного усреднения накапливает градиенты

s_t=\sum_{k=1}^t\alpha_k g_k

и строит точку, например, по правилу

x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\langle s_t,x\rangle+\beta_t\psi(x)\}.

В MD регуляризатор центрирован в текущей точке через D_\psi(x,x_t); в dual averaging он сопоставляет всей накопленной линейной модели один регуляризатор, обычно центрированный в фиксированной исходной точке. При постоянных параметрах некоторые варианты алгебраически совпадают, но при изменяющемся темпе обучения различия существенны. В частности, обычный online MD с наивно меняющимся шагом может иметь линейное сожаление там, где dual averaging сохраняет хорошую гарантию; стабилизированные варианты MD устраняют эту проблему[1]. Классические конструкции dual averaging принадлежат Ю. Нестерову[1]; регуляризованная версия для стохастического обучения подробно исследована Л. Сяо[1].

Natural gradient

Естественный градиент задаёт риманову метрику, часто матрицей информации Фишера, и делает локальный шаг

x_{t+1}\approx x_t-\eta_t G(x_t)^{-1}\nabla f(x_t).

Если G(x)=\nabla^2\psi(x), это локальная аппроксимация зеркального шага. Однако не всякая риманова метрика является гессианом глобального выпуклого потенциала, зеркальная итерация использует конечную дивергенцию Брэгмана, а естественный градиент обычно формулируется на статистическом многообразии. Поэтому отождествлять методы без дополнительных условий нельзя.

Сравнение методов

Метод Геометрия и ограничения Итерационная подзадача Память Типичная гарантия в выпуклом липшицевом случае
Градиентный спуск / субградиентный спуск Евклидова; без ограничений Векторное сложение, обычно O(d) O(d) O(T^{-1/2}) для негладкой задачи; O(T^{-1}) для выпуклой L-гладкой задачи
Projected gradient descent Евклидова; явное множество X Евклидова проекция; от закрытой формы до отдельной задачи оптимизации O(d) O(T^{-1/2}) в негладком и O(T^{-1}) в гладком случае при стандартных предпосылках
Mirror descent Произвольная норма и брэгмановская геометрия Зеркальная прокс-операция; часто O(d) на симплексе, но может быть дорогой O(d) O(T^{-1/2}); константа определяется D_\psi и двойственной нормой
Proximal gradient Обычно евклидова; составная цель f+r Проксимальный оператор r O(d) O(T^{-1}) при выпуклой гладкой f; ускорение даёт O(T^{-2})
Proximal mirror descent Брэгмановская; составная цель и ограничения Совместная прокс-операция для r и D_\psi O(d) Как у MD при ограниченных субградиентах; быстрее при относительной гладкости и дополнительных условиях
Dual averaging Геометрия фиксированного регуляризатора Минимизация накопленной линейной модели с регуляризатором O(d) для суммы градиентов; хранить всю историю не требуется O(T^{-1/2}); особенно удобно для меняющихся шагов и явной регуляризации

Указанная память не включает состояние стохастического оракула, распределённой системы или адаптивного предобусловливателя. Сложность зеркальной подзадачи является частью алгоритма: теоретически подходящая геометрия бесполезна, если соответствующий prox нельзя вычислить достаточно точно и дёшево.

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

Вероятностный симплекс и смеси

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

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

Онлайн-обучение

В онлайн-выпуклой оптимизации на раунде t алгоритм выбирает x_t, затем наблюдает выпуклую потерю \ell_t. Статическое сожаление относительно u\in X равно

\mathrm{Reg}_T(u)=\sum_{t=1}^T[\ell_t(x_t)-\ell_t(u)].

По выпуклости оно не превосходит \sum_t\langle g_t,x_t-u\rangle. Поэтому основное неравенство MD сразу даёт

\mathrm{Reg}_T(u)\leq\frac{D_\psi(u,x_1)}{\eta}+\frac{\eta}{2\sigma}\sum_{t=1}^T\|g_t\|_*^2.

При ограниченных градиентах это O(\sqrt T), то есть среднее сожаление стремится к нулю. Энтропийный случай даёт алгоритм предсказания с экспертами. Адаптивные регуляризаторы превращают эту идею в семейство методов, родственное AdaGrad[1].

Линейные модели и разреженность

Для линейной и логистической регрессии геометрия \ell_1/\ell_\infty полезна, когда признаки высокоразмерны, а градиенты естественно ограничены в максимальной норме. Однако сам энтропийный MD требует неотрицательных переменных; знаковые коэффициенты представляют как разность двух неотрицательных векторов либо выбирают \ell_p-потенциал. Для составной цели с \ell_1-штрафом proximal MD или regularized dual averaging предпочтительнее включения субградиента штрафа: точный prox способен создавать нулевые коэффициенты[1]. Современные схемы стохастического зеркального спуска применяются и к крупномасштабному восстановлению разреженных параметров и обобщённым линейным моделям[1].

Стохастическая и распределённая оптимизация

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

В распределённой задаче агенты сочетают локальные зеркальные шаги с консенсусом или отслеживанием градиента. Потенциал можно согласовать не только с локальными ограничениями, но и с геометрией согласования. Итоговая скорость зависит одновременно от брэгмановского радиуса, шума, числа локальных шагов и спектральных характеристик коммуникационного графа; локальная гарантия MD сама по себе не устраняет сетевой член. Для распределённой составной онлайн-оптимизации разработаны варианты с динамическим сожалением и зеркальными prox-шагами[1].

Выбор зеркального отображения

Практический выбор \psi — это совместная оптимизация статистических и вычислительных констант. Полезен следующий порядок проверки.

  1. Согласовать норму с оракулом. Найти норму, в которой \|g_t\|_* мало или естественно контролируется.
  2. Оценить брэгмановский радиус. Для предполагаемого класса решений оценить \sup_{u}D_\psi(u,x_1) либо локальную величину D_\psi(x^*,x_1).
  3. Проверить сильную выпуклость. Константа \sigma должна относиться к той же норме, которая использована для градиента.
  4. Решить prox-подзадачу. Нужна закрытая форма, быстрый специализированный алгоритм или контролируемая точность внутреннего решателя.
  5. Проверить область потенциала. Градиент \nabla\psi должен существовать на всех итерациях; для барьерных и энтропийных потенциалов требуется старт в относительной внутренности.
  6. Проверить численную устойчивость. Экспоненты, логарифмы и спектральные функции требуют стабилизации; формальная закрытая форма не гарантирует устойчивой реализации.

Масштабирование потенциала и шага избыточно: замена \psi на c\psi эквивалентна соответствующему изменению \eta_t. Сравнивать потенциалы только по константе сильной выпуклости без учёта радиуса D_\psi некорректно; в оценке участвует их отношение.

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

  • Дорогой зеркальный prox. На общих многогранниках, спектральных множествах и при сложных составных ограничениях подзадача может быть дороже евклидовой проекции.
  • Несогласованные нормы. Нельзя брать сильную выпуклость относительно \ell_1, а градиент ограничивать в \ell_2, не вводя явные коэффициенты эквивалентности норм.
  • Неверный порядок аргументов. В общем случае D_\psi(x,y)\neq D_\psi(y,x); из-за несимметричности дивергенции Брэгмана перестановка аргументов ломает телескопирование и алгоритм.
  • Игнорирование границы. У отрицательной энтропии градиент не определён при нулевых координатах. Старт с нуля делает стандартную двойственную запись некорректной, а мультипликативное обновление навсегда сохраняет ноль.
  • Смешение гладкости. Евклидова липшицевость градиента, относительная гладкость и ограниченность субградиента — разные предпосылки и приводят к разным скоростям.
  • Неправильный выход. Для негладкой выпуклой задачи оценка часто доказана только для взвешенного среднего. Последняя итерация может требовать сильной выпуклости, монотонности шага или отдельного результата.
  • Неточная подзадача. Ошибки внутреннего prox-решателя должны быть суммируемы или явно включены в оценку; иначе номинальная скорость не гарантируется.
  • Наивно меняющийся шаг в online MD. Эквивалентность с dual averaging может исчезнуть, а сожаление — ухудшиться вплоть до линейного[1].
  • Слишком общий вывод о natural gradient. Совпадение локальных метрических тензоров не доказывает совпадение конечных итераций.
  • Плохая численная реализация. Прямое вычисление экспонент вызывает переполнение и исчезновение малых весов; матричные зеркальные шаги могут терять положительную определённость из-за округления.

Зеркальный спуск практически предпочтителен евклидовым методам, когда ограничения имеют простой неевклидов prox, брэгмановский радиус заметно меньше евклидова, а градиенты хорошо ограничены в соответствующей двойственной норме. Типичные примеры — большой симплекс, матричный симплекс, задачи с относительной гладкостью и высокоразмерные онлайн-задачи. Евклидов метод обычно предпочтительнее, если проекция проста, геометрия близка к изотропной, а вычисление зеркального отображения требует дорогой факторизации или внутренней оптимизации.

Классические результаты и современные обобщения

К классическому ядру относятся: метод Немировского—Юдина; интерпретация через дивергенцию Брэгмана и негладкая оценка O(T^{-1/2}); энтропийный шаг на симплексе; стохастический MD с ограниченным вторым моментом; dual averaging и составные prox-варианты[1][1][1][1].

Более новые направления не следует считать синонимами базового MD:

  • Относительная гладкость заменяет глобальную липшицевость градиента сравнением кривизны цели и потенциала[1].
  • Оптимистический MD и mirror-prox используют предсказание следующего градиента или дополнительную оценку оператора; они предназначены, в частности, для седловых задач и вариационных неравенств, а не являются одной итерацией обычного MD. Для стохастических вариационных неравенств исследованы гарантии последней итерации оптимистических методов[1].
  • Адаптивный и параметрически свободный online MD выбирает регуляризатор или масштаб из истории градиентов; гарантии выражаются через наблюдаемую геометрию, но алгоритм уже отличается от MD с фиксированным потенциалом[1].
  • Тяжёлохвостый SMD заменяет условие ограниченного второго момента более слабыми моментными условиями и нередко применяет отсечение или равномерно выпуклые потенциалы.
  • Невыпуклый SMD измеряет стационарность через брэгмановское градиентное отображение. Современный анализ допускает общие дивергенции Брэгмана, включая энтропийную, без глобальной липшицевости градиента потенциала[1]. Эти результаты не дают глобальной оптимальности для общей невыпуклой функции.

Заключение

Зеркальный спуск отделяет информацию первого порядка от способа измерения перемещений. Его универсальная итерация остаётся простой, но качество метода определяется согласованием трёх объектов: нормы и её двойственной нормы, брэгмановского потенциала и вычислимости зеркального prox. В евклидовой геометрии метод сводится к проекционному градиентному спуску; на симплексе — к экспоненциальному взвешиванию. Классическая теория даёт оптимальные порядки для негладкой выпуклой и стохастической оптимизации, а современные расширения охватывают относительную гладкость, тяжёлые хвосты, онлайн-адаптацию, распределённые и невыпуклые задачи. При переносе гарантий критически важно сохранять точные предпосылки: вид усреднения, ориентацию дивергенции, норму, моментные условия и точность решения прокс-подзадачи.

Примечания


Литература

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%B5%D1%80%D0%BA%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0_%28%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F%29»