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

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

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

Текущая версия

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

Содержание

1 Постановка задачи
- 1.1 Норма и двойственная норма
2 Дивергенция Брэгмана и зеркальная геометрия
- 2.1 Геометрическая интуиция
3 Алгоритм зеркального спуска
- 3.1 Псевдокод
- 3.2 Основное одношаговое неравенство
4 Оценки сходимости
5 Важные частные случаи
6 Связь с родственными методами
7 Применения в машинном обучении
8 Выбор зеркального отображения
9 Ограничения и типичные ошибки
10 Классические результаты и современные обобщения
11 Заключение
12 Примечания
13 Литература

Метод зеркального спуска (англ. 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$ имеет инвариантный смысл только после выбора отождествления прямого и двойственного пространств. Евклидово скалярное произведение делает такое отождествление незаметным. Зеркальный спуск выполняет операцию явно:

переводит $x_t$ в двойственные координаты $y_t=\nabla\psi(x_t)$ ;
делает шаг $y_{t+1/2}=y_t-\eta_t g_t$ в двойственном пространстве;
возвращается через $\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$ .

Для :
- получить $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)\}$ ;
Вернуть последнюю точку либо взвешенное среднее
- $\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$ — это совместная оптимизация статистических и вычислительных констант. Полезен следующий порядок проверки.

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

Масштабирование потенциала и шага избыточно: замена $\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. В евклидовой геометрии метод сводится к проекционному градиентному спуску; на симплексе — к экспоненциальному взвешиванию. Классическая теория даёт оптимальные порядки для негладкой выпуклой и стохастической оптимизации, а современные расширения охватывают относительную гладкость, тяжёлые хвосты, онлайн-адаптацию, распределённые и невыпуклые задачи. При переносе гарантий критически важно сохранять точные предпосылки: вид усреднения, ориентацию дивергенции, норму, моментные условия и точность решения прокс-подзадачи.

Примечания

Литература

Bregman L. M. The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming // USSR Computational Mathematics and Mathematical Physics. — 1967. — Т. 7. — № 3. — С. 200—217.
Nemirovsky A. S., Yudin D. B. Problem Complexity and Method Efficiency in Optimization. — Wiley, 1983.
Beck A., Teboulle M. Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization // Operations Research Letters. — 2003. — Т. 31. — № 3. — С. 167—175.
Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust Stochastic Approximation Approach to Stochastic Programming // SIAM Journal on Optimization. — 2009. — Т. 19. — № 4. — С. 1574—1609.
Nesterov Y. Primal-Dual Subgradient Methods for Convex Problems // Mathematical Programming. — 2009. — Т. 120. — № 1. — С. 221—259.
Xiao L. Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization // Journal of Machine Learning Research. — 2010. — Т. 11. — С. 2543—2596.
Duchi J., Hazan E., Singer Y. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization // Journal of Machine Learning Research. — 2011. — Т. 12. — С. 2121—2159.
Bubeck S. Convex Optimization: Algorithms and Complexity // Foundations and Trends in Machine Learning. — 2015. — Т. 8. — № 3—4. — С. 231—357.
Cutkosky A., Orabona F. Black-Box Reductions for Parameter-free Online Learning in Banach Spaces // Proceedings of Machine Learning Research: COLT. — 2018. — Т. 75. — С. 1493—1529.
Lu H., Freund R. M., Nesterov Y. Relatively Smooth Convex Optimization by First-Order Methods, and Applications // SIAM Journal on Optimization. — 2018. — Т. 28. — № 1. — С. 333—354.
Yuan D., Hong Y., Ho D. W. C., Xu S. Distributed Mirror Descent for Online Composite Optimization2020.
Azizian W., Iutzeler F., Malick J., Mertikopoulos P. The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities // Proceedings of Machine Learning Research: AISTATS. — 2021. — Т. 134.
Fang H., Harvey N. J. A., Portella V. S., Friedlander M. P. Online Mirror Descent and Dual Averaging: Keeping Pace in the Dynamic Case // Journal of Machine Learning Research. — 2022. — Т. 23. — С. 1—38.
Vural N. M., Yu L., Balasubramanian K., Volgushev S., Erdogdu M. A. Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance // Proceedings of Machine Learning Research: COLT. — 2022. — Т. 178. — С. 65—102.
Ilandarideva S., Bekri Y., Iouditski A., Perchet V. Stochastic Mirror Descent for Large-Scale Sparse Recovery // Proceedings of Machine Learning Research: AISTATS. — 2023. — Т. 206. — С. 5931—5957.
Eldowa K., Paudice A. General Tail Bounds for Non-Smooth Stochastic Mirror Descent // Proceedings of Machine Learning Research: AISTATS. — 2024. — Т. 238.
Fatkhullin I., He N. Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence // Proceedings of Machine Learning Research: AISTATS. — 2024. — Т. 238.

Источник — «http://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»

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

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 14:00, 15 июля 2026 (MSD)}}
+{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 20:00, 14 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Метод зеркального спуска (оптимизация)]]}}
 {{TOCright}}
-'''Субградиентные методы''' — семейство [[Методы первого порядка|методов первого порядка]] для минимизации [[Выпуклая функция|выпуклых]], возможно негладких функций. В точке излома вместо единственного градиента используется любой элемент [[Субдифференциал|субдифференциала]]. Простота итерации, малая память и возможность работать со стохастическим или распределённым [[Оракул первого порядка|оракулом]] делают эти методы базовыми для [[Выпуклая оптимизация|выпуклой оптимизации]], [[Негладкая оптимизация|негладкой оптимизации]] и [[Машинное обучение|машинного обучения]]. Цена универсальности — медленная в общем случае сходимость, отсутствие монотонного убывания целевой функции и высокая чувствительность к масштабу задачи и правилу шага.
+'''Метод зеркального спуска''' (англ. ''mirror descent'', MD) — [[Методы первого порядка|метод первого порядка]] для [[Выпуклая оптимизация|выпуклой оптимизации]], в котором линейная модель целевой функции регуляризуется не обязательно квадратом евклидова расстояния, а [[Дивергенция Брэгмана|дивергенцией Брэгмана]], согласованной с геометрией допустимого множества. Метод введён А. С. Немировским и Д. Б. Юдиным<ref name="NY">{{книга |автор=Nemirovsky A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |ссылка=https://www2.isye.gatech.edu/~nemirovs/Nemirovskii_Yudin_1983.pdf |издательство=Wiley |год=1983 |язык=en}}</ref>; современная форма как нелинейного проекционного субградиентного метода дана А. Беком и М. Тебуллем<ref name="BT">{{статья |автор=Beck A., Teboulle M. |заглавие=Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization |ссылка=https://doi.org/10.1016/S0167-6377(02)00231-6 |издание=Operations Research Letters |год=2003 |том=31 |номер=3 |страницы=167—175 |doi=10.1016/S0167-6377(02)00231-6 |язык=en}}</ref>.
+Зеркальный спуск включает [[Градиентный спуск|градиентный спуск]] и проекционный субградиентный метод как евклидов частный случай, а на вероятностном симплексе с энтропийной геометрией приводит к экспоненциальному обновлению весов. Главное практическое преимущество метода возникает тогда, когда норма, ограничения и структура градиентов существенно неевклидовы: например, на симплексе оценка зависит от размерности как <tex>\sqrt{\ln d}</tex>, тогда как прямой евклидов анализ часто даёт зависимость порядка <tex>\sqrt d</tex>.
 == Постановка задачи ==
-Пусть <tex>X\subseteq\mathbb{R}^d</tex> — непустое замкнутое выпуклое множество, а <tex>f:X\to\mathbb{R}\cup\{+\infty\}</tex> — собственная замкнутая выпуклая функция. Рассматривается задача
+Пусть <tex>E</tex> — конечномерное вещественное [[Линейное пространство|линейное пространство]], <tex>E^*</tex> — его [[Двойственное пространство|двойственное пространство]], <tex>X\subset E</tex> — непустое замкнутое [[Выпуклое множество|выпуклое множество]]. Рассматривается задача
-:: <tex>f^*=\min_{x\in X} f(x),\qquad X^*=\operatorname{arg\,min}_{x\in X}f(x)\ne\emptyset.</tex>
+:: <tex>\min_{x\in X} f(x),</tex>
-Вектор <tex>g\in\mathbb{R}^d</tex> называется '''субградиентом''' <tex>f</tex> в точке <tex>x\in\operatorname{dom}f</tex>, если для любого <tex>y</tex>
+где <tex>f:X\to\mathbb{R}\cup\{+\infty\}</tex> — собственная замкнутая [[Выпуклая функция|выпуклая функция]]. В негладком случае [[Оракул первого порядка|оракул первого порядка]] в точке <tex>x_t</tex> возвращает [[Субградиент|субградиент]] <tex>g_t\in\partial f(x_t)\subset E^*</tex>. В [[Стохастическая оптимизация|стохастической задаче]]
-:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle.</tex>
+:: <tex>f(x)=\mathbb{E}_{\xi}[F(x,\xi)]</tex>
-Множество всех таких векторов обозначается <tex>\partial f(x)</tex> и называется [[Субдифференциал|субдифференциалом]] Фенхеля — Моро. Для выпуклой дифференцируемой функции <tex>\partial f(x)=\{\nabla f(x)\}</tex>; тем самым субградиентный метод продолжает [[Градиентный спуск|градиентный спуск]] на негладкий случай. Условие оптимальности неограниченной задачи имеет вид
+используется случайная оценка <tex>G_t=G(x_t,\xi_t)</tex>, для которой обычно предполагают условную несмещённость
-:: <tex>0\in\partial f(x^*).</tex>
+:: <tex>\mathbb{E}[G_t\mid\mathcal{F}_{t-1}]\in\partial f(x_t).</tex>
-При ограничении <tex>x\in X</tex> оно заменяется включением
+Здесь <tex>\mathcal{F}_{t-1}</tex> — информация, накопленная до построения <tex>G_t</tex>.
-:: <tex>0\in\partial f(x^*)+N_X(x^*),</tex>
+=== Норма и двойственная норма ===
-где <tex>N_X(x^*)</tex> — [[Нормальный конус|нормальный конус]] множества <tex>X</tex><ref name="Rockafellar">{{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://doi.org/10.1515/9781400873173 |издательство=Princeton University Press |год=1970 |язык=en}}</ref>.
+На <tex>E</tex> фиксируется норма <tex>\|\cdot\|</tex>. Двойственная норма на <tex>E^*</tex> определяется равенством
-=== Геометрическая интуиция ===
+:: <tex>\|z\|_* = \sup_{\|x\|\leq 1}\langle z,x\rangle.</tex>
-Неравенство субградиента задаёт опорную аффинную функцию, лежащую не выше графика <tex>f</tex>. Полупространство
+Обобщённое неравенство Гёльдера имеет вид
-:: <tex>\{y:\langle g,y-x\rangle\leq0\}</tex>
+:: <tex>\langle z,x\rangle\leq\|z\|_*\,\|x\|.</tex>
-содержит каждую точку <tex>y</tex>, для которой <tex>f(y)\leq f(x)</tex>. Поэтому направление <tex>-g</tex> отделяет текущую точку от области лучших значений. Однако, в отличие от градиента гладкой функции, <tex>-g</tex> не обязано быть направлением локального убывания: для <tex>f(x)=|x|</tex> в точке <tex>x=0</tex> допустим любой <tex>g\in[-1,1]</tex>, и выбор <tex>g\ne0</tex> уводит из минимума. Анализ метода основан не на лемме о гладком спуске, а на уменьшении расстояния до множества решений с точностью до квадрата шага.
+Именно пара норм, а не выбранные координаты, определяет константу Липшица функции и масштаб ошибки. Например, на симплексе естественна норма <tex>\|\cdot\|_1</tex>, а субградиенты измеряются в <tex>\|\cdot\|_\infty</tex>. Замена этой пары на евклидову может внести лишний множитель порядка <tex>\sqrt d</tex>.
-== Нормы и двойственные нормы ==
+== Дивергенция Брэгмана и зеркальная геометрия ==
-Для нормы <tex>\|\cdot\|</tex> [[Двойственная норма|двойственная норма]] определяется как
+Пусть <tex>\psi:X\to\mathbb{R}\cup\{+\infty\}</tex> — дифференцируемая на <tex>\mathrm{ri}\,X</tex> строго выпуклая функция, называемая '''порождающей функцией расстояния''', '''зеркальным потенциалом''' или '''прокси-функцией'''. [[Дивергенция Брэгмана]]<ref name="Bregman">{{статья |автор=Bregman L. M. |заглавие=The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming |ссылка=https://doi.org/10.1016/0041-5553(67)90040-7 |издание=USSR Computational Mathematics and Mathematical Physics |год=1967 |том=7 |номер=3 |страницы=200—217 |doi=10.1016/0041-5553(67)90040-7 |язык=en}}</ref> задаётся как
-:: <tex>\|g\|_*=\sup_{\|u\|\leq1}\langle g,u\rangle.</tex>
+:: <tex>D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.</tex>
-[[Неравенство Гёльдера]]
+Она неотрицательна, но, вообще говоря, несимметрична и не удовлетворяет неравенству треугольника. Поэтому <tex>D_\psi</tex> — не метрика. Порядок аргументов в формулах существенен.
-:: <tex>\langle g,u\rangle\leq\|g\|_*\|u\|</tex>
+Для анализа базового метода обычно предполагается, что <tex>\psi</tex> является <tex>\sigma</tex>-сильно выпуклой относительно <tex>\|\cdot\|</tex>:
-связывает размер области в прямой норме с размером субградиентов в двойственной. Если <tex>f</tex> выпукла и <tex>G</tex>-липшицева на открытом множестве относительно <tex>\|\cdot\|</tex>, то <tex>\|g\|_*\leq G</tex> для всех субградиентов во внутренних точках; верно и обратное при соответствующих условиях на область.
+:: <tex>D_\psi(x,y)\geq\frac{\sigma}{2}\|x-y\|^2.</tex>
-В [[Евклидово пространство|евклидовом пространстве]] градиент отождествляет линейный функционал с вектором, поэтому шаг <tex>x-\alpha g</tex> естественен. Для общей нормы направление [[Метод наискорейшего спуска|наискорейшего линейного спуска]] задаётся отображением
+Это неравенство предполагается для всех допустимых <tex>x</tex> и <tex>y</tex>.
-:: <tex>v(g)\in\operatorname{arg\,min}_{v}\left\{\langle g,v\rangle+\frac12\|v\|^2\right\},\qquad \|v(g)\|=\|g\|_*.</tex>
+Если <tex>\psi</tex> — [[Функция Лежандра|функция Лежандра]], то отображение <tex>\nabla\psi</tex> переводит внутренность прямой области в [[Двойственное пространство|двойственное пространство]], а обратное отображение задаётся градиентом [[Преобразование Фенхеля — Лежандра|сопряжённой функции Фенхеля]]:
-Если квадратичная стабилизация заменяется сильно выпуклым потенциалом и [[Дивергенция Брэгмана|дивергенцией Брэгмана]], получается [[Метод зеркального спуска|зеркальный спуск]]. Следовательно, упоминание произвольной нормы в оценке не означает, что евклидово обновление автоматически стало неевклидовым: должны быть согласованы норма, двойственная норма и геометрия проекции.
+:: <tex>(\nabla\psi)^{-1}=\nabla\psi^*.</tex>
-Более точно, пусть <tex>\psi</tex> является <tex>\sigma</tex>-сильно выпуклым потенциалом относительно <tex>\|\cdot\|</tex>, а
+=== Геометрическая интуиция ===
-:: <tex>D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.</tex>
+Обычный градиент <tex>g_t</tex> — ковектор, то есть элемент <tex>E^*</tex>. Вычитание его из точки <tex>x_t\in E</tex> имеет инвариантный смысл только после выбора отождествления прямого и двойственного пространств. Евклидово скалярное произведение делает такое отождествление незаметным. Зеркальный спуск выполняет операцию явно:
-Обновление
+# переводит <tex>x_t</tex> в двойственные координаты <tex>y_t=\nabla\psi(x_t)</tex>;
+# делает шаг <tex>y_{t+1/2}=y_t-\eta_t g_t</tex> в двойственном пространстве;
+# возвращается через <tex>\nabla\psi^*</tex> и, при наличии ограничений, выполняет [[Дивергенция Брэгмана#Брэгмановская проекция|брэгмановскую проекцию]] на <tex>X</tex>.
-:: <tex>x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\alpha_t\langle g_t,x\rangle+D_\psi(x,x_t)\}</tex>
+В эквивалентной вариационной форме эти три действия объединяются в одну задачу. Геометрия задаётся кривизной <tex>\psi</tex>: локально матрица <tex>\nabla^2\psi(x)</tex> играет роль переменного метрического тензора, а формальный малый шаг имеет вид
-при <tex>\|g_t\|_*\leq G</tex> удовлетворяет оценке
+:: <tex>x_{t+1}-x_t\approx-\eta_t[\nabla^2\psi(x_t)]^{-1}g_t.</tex>
-:: <tex>f(\bar x_T)-f^*\leq\frac{D_\psi(x^*,x_1)+\frac{G^2}{2\sigma}\sum_{t=1}^T\alpha_t^2}{\sum_{t=1}^T\alpha_t}.</tex>
+Это объясняет сходство с [[Предобусловливание|предобусловливанием]], но точный зеркальный шаг определяется глобальной [[Дивергенция Брэгмана|брэгмановской дивергенцией]], а не только локальной квадратичной аппроксимацией.
-Евклидов результат получается при <tex>\psi(x)=\frac12\|x\|_2^2</tex>. В неевклидовой геометрии константа определяется одновременно брэгмановским расстоянием до решения и нормой субградиентов в двойственной норме; например, на симплексе энтропийная геометрия часто заменяет полиномиальную зависимость от размерности логарифмической<ref name="BeckTeboulleMD">{{статья |автор=Beck A., Teboulle M. |заглавие=Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization |ссылка=https://doi.org/10.1016/S0167-6377(02)00231-6 |издание=Operations Research Letters |год=2003 |том=31 |номер=3 |страницы=167—175 |язык=en}}</ref>.
+== Алгоритм зеркального спуска ==
-== Базовый алгоритм ==
+При шагах <tex>\eta_t>0</tex> основная итерация имеет вид
-=== Евклидов проекционный субградиентный метод ===
+:: <tex>x_{t+1}\in\operatorname{arg\,min}_{x\in X}\left\{\eta_t\langle g_t,x\rangle+D_\psi(x,x_t)\right\}.</tex>
-Выбираются <tex>x_1\in X</tex>, положительные шаги <tex>\alpha_t</tex> и субградиенты <tex>g_t\in\partial f(x_t)</tex>. Итерация имеет вид
+Добавление не зависящих от <tex>x</tex> членов показывает, что минимизируется линейная модель <tex>f</tex> в <tex>x_t</tex> плюс штраф за удаление от текущей точки в выбранной геометрии.
-:: <tex>x_{t+1}=\Pi_X(x_t-\alpha_t g_t),</tex>
-где
-:: <tex>\Pi_X(z)=\operatorname{arg\,min}_{x\in X}\|x-z\|_2</tex>
-— евклидова [[Проекция на выпуклое множество|проекция]]. При <tex>X=\mathbb{R}^d</tex> проекция исчезает и получается обычный субградиентный спуск. Если функция дифференцируема, обновление совпадает с projected gradient descent, но оценки для гладкой задачи могут быть существенно быстрее благодаря липшицевости градиента.
 === Псевдокод ===
-'''Вход:''' множество <tex>X</tex>, точка <tex>x_1\in X</tex>, число итераций <tex>T</tex>, правило шага.
+'''Вход:''' множество <tex>X</tex>, потенциал <tex>\psi</tex>, начальная точка <tex>x_1\in\mathrm{ri}\,X</tex>, шаги <tex>\eta_1,\ldots,\eta_T</tex>.
 # Для <tex>t=1,\ldots,T</tex>:
-## получить <tex>g_t\in\partial f(x_t)</tex> или стохастическую оценку <tex>G_t</tex>;
+#* получить <tex>g_t\in\partial f(x_t)</tex> или стохастическую оценку <tex>G_t</tex>;
-## выбрать <tex>\alpha_t>0</tex> по заранее указанному правилу;
+#* вычислить <tex>x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\eta_t\langle g_t,x\rangle+D_\psi(x,x_t)\}</tex>;
-## вычислить <tex>x_{t+1}=\Pi_X(x_t-\alpha_t g_t)</tex>;
+# Вернуть последнюю точку либо взвешенное среднее
-# вернуть лучшую вычисленную точку либо взвешенное среднее
+#* <tex>\bar x_T=(\sum_{t=1}^T\eta_t x_t)/(\sum_{t=1}^T\eta_t)</tex>.
-:: <tex>\bar x_T=\frac{\sum_{t=1}^T\alpha_t x_t}{\sum_{t=1}^T\alpha_t}.</tex>
-Для чисто оракульной задачи значение лучшей точки <tex>\operatorname{arg\,min}_{t\leq T}f(x_t)</tex> требует вычислять <tex>f(x_t)</tex>. В стохастической задаче выбор по шумной эмпирической потере вносит смещение, поэтому теоремы обычно относятся к усреднению или к специально построенной последней итерации.
+Для негладких выпуклых задач гарантия обычно относится к <tex>\bar x_T</tex>, а не к последней итерации. Замена усреднённой точки последней без дополнительной теории — распространённая ошибка.
 === Основное одношаговое неравенство ===
-Неэкспансивность проекции и неравенство субградиента дают для любого <tex>x^*\in X^*</tex>
+Оптимальность зеркального шага и [[Дивергенция Брэгмана#Трёхточечное тождество|трёхточечное тождество Брэгмана]] дают для любого <tex>u\in X</tex>
-:: <tex>\|x_{t+1}-x^*\|_2^2\leq\|x_t-x^*\|_2^2-2\alpha_t\bigl(f(x_t)-f^*\bigr)+\alpha_t^2\|g_t\|_2^2.</tex>
+:: <tex>\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).</tex>
-Это центральное соотношение: полезный член линеен по <tex>\alpha_t</tex>, а накопленная ошибка шага квадратична. В общем случае значения <tex>f(x_t)</tex> не обязаны убывать.
+Если <tex>\psi</tex> <tex>\sigma</tex>-сильно выпукла, то после переноса <tex>x_t-x_{t+1}</tex>, применения неравенства Гёльдера и неравенства Юнга получается фундаментальная оценка
+:: <tex>\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.</tex>
+Телескопирование [[Дивергенция Брэгмана|дивергенций Брэгмана]] в этой формуле является основой большинства классических доказательств.
 == Оценки сходимости ==
@@ Строка 104: / Строка 102: @@
 === Выпуклая липшицева задача ===
-'''Теорема.''' Пусть <tex>f</tex> выпукла на замкнутом выпуклом <tex>X</tex>, <tex>X^*\ne\emptyset</tex>, <tex>\|g_t\|_2\leq G</tex> и <tex>\|x_1-x^*\|_2\leq R</tex> для некоторого <tex>x^*\in X^*</tex>. Тогда для положительных шагов
+'''Теорема.''' Пусть <tex>f</tex> выпукла на <tex>X</tex>, <tex>\psi</tex> <tex>\sigma</tex>-сильно выпукла относительно <tex>\|\cdot\|</tex>, <tex>x^*\in\operatorname{arg\,min}_{x\in X} f(x)</tex>, а выбранные субградиенты удовлетворяют <tex>\|g_t\|_*\leq G</tex>. Тогда для любого набора положительных шагов
-:: <tex>f(\bar x_T)-f^*\leq\frac{R^2+G^2\sum_{t=1}^T\alpha_t^2}{2\sum_{t=1}^T\alpha_t}.</tex>
+:: <tex>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}.</tex>
-Та же правая часть ограничивает <tex>\min_{1\leq t\leq T}f(x_t)-f^*</tex>. При известном горизонте выбор
+В частности, если известно <tex>D_\psi(x^*,x_1)\leq R_\psi^2</tex> и взять постоянный шаг
-:: <tex>\alpha_t=\frac{R}{G\sqrt T}</tex>
+:: <tex>\eta=\frac{R_\psi\sqrt{2\sigma}}{G\sqrt T},</tex>
-даёт
+то
-:: <tex>f(\bar x_T)-f^*\leq\frac{RG}{\sqrt T}.</tex>
+:: <tex>f(\bar x_T)-f(x^*)\leq G R_\psi\sqrt{\frac{2}{\sigma T}}.</tex>
-Следовательно, для достижения ошибки не более <tex>\varepsilon</tex> достаточно <tex>O(R^2G^2/\varepsilon^2)</tex> вызовов субградиентного оракула. Этот порядок оптимален в худшем случае для класса выпуклых липшицевых функций при стандартной модели оракула первого порядка<ref name="NY">{{книга |автор=Nemirovski A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |издательство=Wiley |год=1983 |язык=en}}</ref><ref name="Shor">{{книга |автор=Shor N. Z. |заглавие=Minimization Methods for Non-Differentiable Functions |ссылка=https://doi.org/10.1007/978-3-642-82118-9 |издательство=Springer |год=1985 |язык=en}}</ref>.
+Это оптимальный по порядку темп <tex>O(T^{-1/2})</tex> для общего класса липшицевых негладких выпуклых функций при оракуле первого порядка<ref name="Bubeck">{{статья |автор=Bubeck S. |заглавие=Convex Optimization: Algorithms and Complexity |ссылка=https://arxiv.org/abs/1405.4980 |издание=Foundations and Trends in Machine Learning |год=2015 |том=8 |номер=3—4 |страницы=231—357 |язык=en}}</ref>.
-Если горизонт заранее неизвестен, шаг <tex>\alpha_t=c/\sqrt t</tex> даёт для обычного взвешенного среднего оценку порядка <tex>O(\log T/\sqrt T)</tex>; удвоение горизонта по эпохам или более аккуратное усреднение устраняет лишний логарифм. Условия
+=== Сильно выпуклая негладкая задача ===
-:: <tex>\sum_{t=1}^{\infty}\alpha_t=\infty,\qquad \sum_{t=1}^{\infty}\alpha_t^2<\infty</tex>
+Пусть дополнительно <tex>f</tex> является <tex>\mu</tex>-сильно выпуклой относительно той же нормы:
-обеспечивают асимптотическую сходимость при ограниченных субградиентах, но сами по себе не дают лучшей конечновременной константы<ref name="Boyd">{{статья |автор=Boyd S., Xiao L., Mutapcic A. |заглавие=Subgradient Methods |ссылка=https://web.stanford.edu/class/ee364b/lectures/subgrad_method_notes.pdf |год=2003 |язык=en}}</ref>.
+:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle+\frac{\mu}{2}\|y-x\|^2,\quad g\in\partial f(x).</tex>
-=== Постоянный шаг ===
+При <tex>\|g_t\|_*\leq G</tex>, <tex>\sigma</tex>-сильной выпуклости <tex>\psi</tex> и шагах <tex>\eta_t=\sigma/(\mu t)</tex> стандартное равномерное усреднение даёт
-При <tex>\alpha_t=\alpha</tex> предыдущая оценка принимает вид
+:: <tex>f\left(\frac1T\sum_{t=1}^T x_t\right)-f(x^*)\leq\frac{G^2}{2\mu T}(1+\ln T).</tex>
-:: <tex>f(\bar x_T)-f^*\leq\frac{R^2}{2\alpha T}+\frac{\alpha G^2}{2}.</tex>
+Логарифм не является информационно-теоретически необходимым. Полиномиально взвешенное усреднение, суффиксное усреднение или перезапуски дают при тех же ограничениях порядок <tex>O(G^2/(\mu T))</tex>; конкретная константа зависит от схемы весов и нумерации шагов. Поэтому утверждение оценки <tex>O(T^{-1})</tex> без описания усреднения недостаточно.
-Итерационный член исчезает, но остаётся окрестность оптимума радиуса по функции порядка <tex>\alpha G^2</tex>. Поэтому постоянный learning rate без рестартов не обеспечивает произвольно точной сходимости для общей негладкой выпуклой задачи.
+=== Гладкость относительно зеркального потенциала ===
-=== Сильно выпуклая задача ===
+Классический анализ гладкого градиентного спуска предполагает липшицевость градиента в норме. Более общее условие '''относительной гладкости''' требует, чтобы для некоторого <tex>L>0</tex>
-Пусть <tex>f</tex> <tex>\mu</tex>-[[Сильно выпуклая функция|сильно выпукла]] относительно евклидовой нормы:
+:: <tex>f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+L D_\psi(y,x).</tex>
-:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle+\frac\mu2\|y-x\|_2^2</tex>
+Для дважды дифференцируемых функций это соответствует неравенству кривизн <tex>\nabla^2 f(x)\leq L\nabla^2\psi(x)</tex> в смысле порядка Лёвнера. При выпуклости <tex>f</tex>, относительной <tex>L</tex>-гладкости, существовании решения и точном решении зеркальной подзадачи шаг
-для всех <tex>g\in\partial f(x)</tex>. Пусть также <tex>\|g_t\|_2\leq G</tex>. Для шага
+:: <tex>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)\}</tex>
-:: <tex>\alpha_t=\frac{2}{\mu(t+1)}</tex>
+порождает невозрастающие значения цели и удовлетворяет оценке последней вычисленной точки
-и среднего с линейными весами
+:: <tex>f(x_{T+1})-f(x^*)\leq\frac{L D_\psi(x^*,x_1)}{T}.</tex>
-:: <tex>\widetilde x_T=\frac{2}{T(T+1)}\sum_{t=1}^T t x_t</tex>
+При дополнительной [[Относительная сильная выпуклость|относительной сильной выпуклости]], то есть при нижней оценке той же формы с <tex>\mu D_\psi(y,x)</tex>, специальные схемы брэгмановского градиента допускают линейную сходимость; [[Дивергенция Брэгмана#Несимметричность|ориентация дивергенции]] и точная схема шага входят в предпосылки и не могут быть опущены<ref name="LFN">{{статья |автор=Lu H., Freund R. M., Nesterov Y. |заглавие=Relatively Smooth Convex Optimization by First-Order Methods, and Applications |ссылка=https://doi.org/10.1137/16M1099546 |издание=SIAM Journal on Optimization |год=2018 |том=28 |номер=1 |страницы=333—354 |doi=10.1137/16M1099546 |язык=en}}</ref>. [[Относительная гладкость]] особенно полезна для логарифмических барьеров, задач оптимального дизайна и моделей, у которых евклидова константа Липшица градиента бесконечна или крайне велика.
-выполняется оценка порядка
+=== Стохастический зеркальный спуск ===
-:: <tex>f(\widetilde x_T)-f^*\leq\frac{2G^2}{\mu(T+1)}.</tex>
+Пусть <tex>G_t</tex> условно несмещён, <tex>\mathbb{E}[\|G_t\|_*^2\mid\mathcal{F}_{t-1}]\leq G^2</tex>, <tex>f</tex> выпукла, а <tex>\psi</tex> <tex>\sigma</tex>-сильно выпукла. Тогда
-Таким образом, сложность уменьшается до <tex>O(G^2/(\mu\varepsilon))</tex>. Для стандартного шага порядка <tex>1/(\mu t)</tex> последняя итерация или равномерное среднее часто несут дополнительный множитель <tex>\log T</tex>; он не является фундаментальным и устраняется правильными весами либо специальным расписанием шагов. В стохастическом случае оптимальность последней итерации требует отдельного анализа<ref name="JainLast">{{статья |автор=Jain P., Nagaraj D., Netrapalli P. |заглавие=Making the Last Iterate of SGD Information Theoretically Optimal |ссылка=https://proceedings.mlr.press/v99/jain19a.html |издание=Proceedings of Machine Learning Research: COLT |год=2019 |том=99 |страницы=1752—1755 |язык=en}}</ref>.
+:: <tex>\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}.</tex>
-Сильная выпуклость и негладкость совместимы только на ограниченной области, если все субградиенты глобально ограничены: на всей <tex>\mathbb{R}^d</tex> сильная выпуклость заставляет нормы субградиентов расти вдали от минимума. Поэтому предпосылка <tex>\|g_t\|\leq G</tex> относится к траектории или ограниченному множеству.
+Следовательно, при настроенном постоянном шаге математическое ожидание ошибки имеет порядок <tex>O(T^{-1/2})</tex>. Для <tex>\mu</tex>-сильно выпуклой функции убывающие шаги и надлежащее усреднение дают порядок <tex>O(G^2/(\mu T))</tex>. Эти результаты требуют ограничения второго момента в двойственной норме, а не только конечной дисперсии каждой координаты<ref name="NJLS">{{статья |автор=Nemirovski A., Juditsky A., Lan G., Shapiro A. |заглавие=Robust Stochastic Approximation Approach to Stochastic Programming |ссылка=https://doi.org/10.1137/070704277 |издание=SIAM Journal on Optimization |год=2009 |том=19 |номер=4 |страницы=1574—1609 |doi=10.1137/070704277 |язык=en}}</ref>.
-=== Шаг Поляка ===
+Оценки с высокой вероятностью требуют дополнительных хвостовых предпосылок либо робастизации. При субгауссовском шуме применимы мартингальные концентрационные неравенства. При наличии лишь конечного момента порядка <tex>1+\kappa</tex>, <tex>0<\kappa\leq1</tex>, обычная теория второго момента неприменима; равномерно выпуклые потенциалы и робастные варианты SMD позволяют получать оптимальные для тяжёлых хвостов темпы<ref name="Vural">{{статья |автор=Vural N. M., Yu L., Balasubramanian K., Volgushev S., Erdogdu M. A. |заглавие=Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance |ссылка=https://proceedings.mlr.press/v178/vural22a.html |издание=Proceedings of Machine Learning Research: COLT |год=2022 |том=178 |страницы=65—102 |язык=en}}</ref>. Общие хвостовые оценки для негладкого SMD при более слабых, чем субгауссовские, режимах получены К. Элдовой и А. Паудиче<ref name="Eldowa">{{статья |автор=Eldowa K., Paudice A. |заглавие=General Tail Bounds for Non-Smooth Stochastic Mirror Descent |ссылка=https://proceedings.mlr.press/v238/eldowa24a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2024 |том=238 |язык=en}}</ref>.
-Если известно точное оптимальное значение <tex>f^*</tex>, применяется шаг Поляка
+== Важные частные случаи ==
-:: <tex>\alpha_t=\gamma\frac{f(x_t)-f^*}{\|g_t\|_2^2},\qquad 0<\gamma<2,</tex>
+=== Евклидов градиентный и проекционный спуск ===
-при <tex>g_t\ne0</tex>. Тогда
+Пусть <tex>E=\mathbb{R}^d</tex>, <tex>\psi(x)=\frac12\|x\|_2^2</tex>. Тогда
-:: <tex>\|x_{t+1}-x^*\|_2^2\leq\|x_t-x^*\|_2^2-\gamma(2-\gamma)\frac{(f(x_t)-f^*)^2}{\|g_t\|_2^2}.</tex>
+:: <tex>D_\psi(x,y)=\frac12\|x-y\|_2^2</tex>
-Правило не требует заранее знать <tex>R</tex> или <tex>G</tex> и автоматически уменьшает шаг около оптимума. Завышенная целевая оценка вместо <tex>f^*</tex> может привести к преждевременной остановке, заниженная — к ненулевым шагам у решения. При условии острой ошибки <tex>f(x)-f^*\geq\kappa\operatorname{dist}(x,X^*)</tex> и локально ограниченных субградиентах геометрически убывающие или поликовские шаги могут давать линейную сходимость; это дополнительная структурная гарантия, не следствие одной лишь сильной выпуклости<ref name="Polyak1969">{{статья |автор=Polyak B. T. |заглавие=Minimization of Unsmooth Functionals |издание=USSR Computational Mathematics and Mathematical Physics |год=1969 |том=9 |номер=3 |страницы=14—29 |doi=10.1016/0041-5553(69)90061-5 |язык=en}}</ref>.
+и зеркальный шаг совпадает с [[Проекция на выпуклое множество|евклидовой проекцией]]:
-=== Стохастический субградиентный метод ===
+:: <tex>x_{t+1}=\Pi_X(x_t-\eta_t g_t).</tex>
-Пусть <tex>F(x,\xi)</tex> — случайная выпуклая функция и
+Если <tex>X=\mathbb{R}^d</tex>, это обычный [[Градиентный спуск|градиентный]] или субградиентный спуск. Тем самым зеркальный спуск не является «градиентным спуском после нелинейной замены переменных» в общем случае, но строго содержит евклидов метод как частный случай.
-:: <tex>f(x)=\mathbb E_{\xi}[F(x,\xi)].</tex>
+=== Экспоненциальное обновление на симплексе ===
-'''Stochastic subgradient descent''' использует
+Пусть
-:: <tex>x_{t+1}=\Pi_X(x_t-\alpha_t G_t),</tex>
+:: <tex>\Delta_d=\{x\in\mathbb{R}_+^d:\sum_{i=1}^d x_i=1\}</tex>
-где относительно истории <tex>\mathcal F_{t-1}</tex> [[Условное математическое ожидание|условное математическое ожидание]] удовлетворяет условиям
+и выбран отрицательный энтропийный потенциал
-:: <tex>\mathbb E[G_t\mid\mathcal F_{t-1}]\in\partial f(x_t),\qquad \mathbb E[\|G_t\|_2^2\mid\mathcal F_{t-1}]\leq G^2.</tex>
+:: <tex>\psi(x)=\sum_{i=1}^d x_i\ln x_i.</tex>
-При выпуклости <tex>f</tex>, существовании <tex>x^*</tex> и <tex>\|x_1-x^*\|_2\leq R</tex> выполняется
+Тогда <tex>D_\psi(x,y)=\sum_i x_i\ln(x_i/y_i)</tex> — [[Расстояние Кульбака — Лейблера|дивергенция Кульбака — Лейблера]], являющаяся важным частным случаем [[Дивергенция Брэгмана|дивергенции Брэгмана]]. Потенциал <tex>1</tex>-сильно выпукл относительно <tex>\|\cdot\|_1</tex> на симплексе вследствие [[Неравенство Пинскера|неравенства Пинскера]]. Решение зеркальной подзадачи имеет закрытую форму
-:: <tex>\mathbb E[f(\bar x_T)-f^*]\leq\frac{R^2+G^2\sum_{t=1}^T\alpha_t^2}{2\sum_{t=1}^T\alpha_t}.</tex>
+:: <tex>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})}.</tex>
-Настроенный постоянный шаг снова даёт <tex>RG/\sqrt T</tex> по [[Математическое ожидание|математическому ожиданию]]. Для <tex>\mu</tex>-сильно выпуклой цели убывающие шаги и взвешенное усреднение дают порядок <tex>O(G^2/(\mu T))</tex><ref name="NJLS">{{статья |автор=Nemirovski A., Juditsky A., Lan G., Shapiro A. |заглавие=Robust Stochastic Approximation Approach to Stochastic Programming |ссылка=https://doi.org/10.1137/070704277 |издание=SIAM Journal on Optimization |год=2009 |том=19 |номер=4 |страницы=1574—1609 |язык=en}}</ref>. Это утверждение требует условной несмещённости и ограничения второго момента полной двойственной нормы; конечной дисперсии отдельных координат недостаточно. Оценки с высокой вероятностью дополнительно требуют ограниченности или хвостовых условий и [[Мартингал|мартингального анализа]]<ref name="Harvey">{{статья |автор=Harvey N. J. A., Liaw C., Plan Y., Randhawa S. |заглавие=Tight Analyses for Non-Smooth Stochastic Gradient Descent |ссылка=https://proceedings.mlr.press/v99/harvey19a.html |издание=Proceedings of Machine Learning Research: COLT |год=2019 |том=99 |страницы=1579—1613 |язык=en}}</ref>.
+Это [[Экспоненциальное взвешивание|экспоненциальное обновление]], также лежащее в основе алгоритмов multiplicative weights и Hedge. Если <tex>x_{1,i}=1/d</tex>, <tex>\|g_t\|_\infty\leq G</tex>, то для любого <tex>u\in\Delta_d</tex>
-Стохастический субградиентный метод не следует смешивать с детерминированным методом: случайный субградиент отдельного примера обязан быть несмещённым субградиентом ожидаемой цели. Для максимума, квантили риска, отрицательного семплирования и других нелинейных преобразований эмпирический оракул может оказаться смещённым.
+:: <tex>\sum_{t=1}^T\langle g_t,x_t-u\rangle\leq\frac{\ln d}{\eta}+\frac{\eta G^2T}{2}.</tex>
-== Выбор субградиента ==
+При <tex>\eta=\sqrt{2\ln d}/(G\sqrt T)</tex> статическое сожаление не превосходит
-=== Правила исчисления ===
+:: <tex>G\sqrt{2T\ln d}.</tex>
-Для суммы выпуклых функций при стандартном условии регулярности
+Зависимость от размерности логарифмическая. Для устойчивого вычисления обновления следует вычитать максимум из логитов до экспоненцирования и выполнять нормировку в логарифмическом масштабе.
-:: <tex>\partial(f+h)(x)=\partial f(x)+\partial h(x).</tex>
+=== Другие геометрии ===
-Для максимума конечного числа выпуклых функций
-:: <tex>f(x)=\max_{1\leq i\leq m}f_i(x)</tex>
-и активного множества <tex>I(x)=\{i:f_i(x)=f(x)\}</tex>
-:: <tex>\partial f(x)=\operatorname{conv}\bigcup_{i\in I(x)}\partial f_i(x).</tex>
-Здесь <tex>\operatorname{conv}</tex> обозначает [[Выпуклая оболочка|выпуклую оболочку]].
-Типичные одномерные примеры:
-* для <tex>|z|</tex> субградиент равен <tex>\operatorname{sign}(z)</tex> при <tex>z\ne0</tex> и принадлежит <tex>[-1,1]</tex> при <tex>z=0</tex>;
-* для hinge loss <tex>\ell(z)=\max(0,1-z)</tex> субградиент равен <tex>-1</tex> при <tex>z<1</tex>, <tex>0</tex> при <tex>z>1</tex> и принадлежит <tex>[-1,0]</tex> при <tex>z=1</tex>;
-* для <tex>\|x\|_1</tex> компонента субградиента равна знаку ненулевой координаты и может быть любой в <tex>[-1,1]</tex> в нуле.
-=== Практический выбор ===
-Теория допускает любой корректный и ограниченный субградиент, но траектории различаются. В точке с несколькими активными кусками можно выбрать субградиент одного куска, выпуклую комбинацию или элемент минимальной нормы. Последний часто уменьшает квадрат ошибки <tex>\alpha_t^2\|g_t\|^2</tex>, однако его вычисление само может требовать решения квадратичной задачи. Нулевой субградиент следует выбирать, когда он доступен и подтверждает оптимальность неограниченной выпуклой задачи.
-Нельзя брать градиент произвольно выбранной неактивной ветви максимума, заменять истинный субградиент усечённым вектором без изменения анализа или считать результат автоматического дифференцирования корректным для любой композиции. Для невыпуклых функций применяются другие понятия — например, субдифференциал Кларка или предельный субдифференциал, — и выпуклые гарантии выше уже не действуют.
-== Правила шага ==
 {| class="wikitable"
-! Правило
+! Область и норма
-! Требуемая информация
+! Типичный потенциал
-! Гарантия и замечание
+! Дивергенция и вычислительный эффект
-|-
-| <tex>\alpha=R/(G\sqrt T)</tex>
-| Горизонт <tex>T</tex>, оценки <tex>R</tex> и <tex>G</tex>
-| Оптимальный порядок <tex>O(RG/\sqrt T)</tex> для усреднения в выпуклом липшицевом случае
 |-
-| <tex>\alpha_t=c/\sqrt t</tex>
+| <tex>\mathbb{R}^d</tex>, <tex>\|\cdot\|_2</tex>
-| Масштаб <tex>c</tex>
+| <tex>\psi(x)=\frac12\|x\|_2^2</tex>
-| Удобно без известного горизонта; наивное взвешивание может дать лишний логарифм
+| Квадрат евклидова расстояния; обычная проекция
 |-
-| <tex>\alpha_t=c/t</tex>
+| Симплекс, <tex>\|\cdot\|_1</tex>
-| Сильная выпуклость и настройка масштаба
+| <tex>\psi(x)=\sum_i x_i\ln x_i</tex>
-| Порядок <tex>O(1/T)</tex> с надлежащими весами; слишком быстро для общей лишь выпуклой задачи
+| KL-дивергенция; мультипликативное обновление за <tex>O(d)</tex>
 |-
-| Шаг Поляка
+| Шар <tex>\ell_p</tex>, <tex>1<p\leq2</tex>
-| Точное <tex>f^*</tex> и значение <tex>f(x_t)</tex>
+| Масштабированный квадрат <tex>\|x\|_p^2</tex>
-| Адаптивен к текущему разрыву; чувствителен к ошибке в целевом значении
+| Согласование с разреженной геометрией; двойственная норма <tex>\ell_q</tex>, где <tex>1/p+1/q=1</tex>
 |-
-| Постоянный шаг
+| Положительный ортант
-| Только масштаб субградиента
+| Логарифмический барьер <tex>\psi(x)=-\sum_i\ln x_i</tex>
-| Быстро входит в окрестность, но оставляет ненулевой уровень ошибки
+| Барьерная брэгмановская геометрия; сохранение строгой положительности
 |-
-| AdaGrad и диагональные адаптивные шаги
+| Положительно полуопределённые матрицы плотности <tex>X\geq0</tex>, <tex>\mathrm{tr}\,X=1</tex>
-| Накопленные квадраты координат субградиентов
+| Энтропия фон Неймана <tex>\psi(X)=\mathrm{tr}(X\ln X)</tex>
-| Подстраиваются под разреженность и анизотропию данных; гарантия относится к изменяющейся геометрии, а не к произвольному покоординатному клиппингу<ref name="AdaGrad">{{статья |автор=Duchi J., Hazan E., Singer Y. |заглавие=Adaptive Subgradient Methods for Online Learning and Stochastic Optimization |ссылка=https://jmlr.org/papers/v12/duchi11a.html |издание=Journal of Machine Learning Research |год=2011 |том=12 |страницы=2121—2159 |язык=en}}</ref>
+| Матричное экспоненциальное обновление; спектральная декомпозиция обычно доминирует в стоимости
 |}
-[[Линейный поиск]], основанный на локальном убывании, ненадёжен: допустимое направление <tex>-g_t</tex> может не быть направлением спуска. [[Масштабирование признаков]] меняет нормы субградиентов, поэтому шаг, подходящий до стандартизации данных, не обязан оставаться подходящим после неё.
+Выбор <tex>p=1+O(1/\ln d)</tex> часто используется как гладкая аппроксимация геометрии <tex>\ell_1</tex>. Правильный потенциал одновременно должен давать малый [[Дивергенция Брэгмана#Брэгмановский радиус|брэгмановский радиус]], достаточную [[Сильно выпуклая функция|сильную выпуклость]] и дешёвую прокс-операцию.
 == Связь с родственными методами ==
-=== Градиентный спуск ===
+=== Брэгмановская проекция ===
-Если <tex>f</tex> дифференцируема, субградиент единственен. Однако использование только общей липшицевости функции сохраняет медленную оценку <tex>O(T^{-1/2})</tex>. Более быстрая оценка [[Градиентный спуск|градиентного спуска]] <tex>O(T^{-1})</tex> требует <tex>L</tex>-липшицевости градиента, а линейная сходимость — одновременно гладкости и сильной выпуклости. Негладкая сильно выпуклая функция обычно допускает лишь <tex>O(T^{-1})</tex>, а не геометрический темп для базового субградиентного метода.
+В неограниченном случае зеркальный шаг записывается как
-=== Проекционный субградиентный метод ===
+:: <tex>y_{t+1}=\nabla\psi^*(\nabla\psi(x_t)-\eta_t g_t).</tex>
-Projected subgradient descent — не отдельный тип оракула, а базовое обновление с явным допустимым множеством. Проекция обеспечивает допустимость и не увеличивает расстояние до решения. Если <tex>\Pi_X</tex> дорога, одна «простая» итерация фактически содержит отдельную оптимизационную задачу. Неевклидова прокс-проекция приводит к зеркальному спуску.
+При ограничениях следующий элемент можно интерпретировать как [[Дивергенция Брэгмана#Брэгмановская проекция|брэгмановскую проекцию]] двойственного шага:
-=== Проксимальные методы ===
+:: <tex>x_{t+1}\in\operatorname{arg\,min}_{x\in X}D_\psi(x,y_{t+1}).</tex>
-Для [[Составная оптимизация|составной задачи]]
+В отличие от [[Ортогональная проекция|ортогональной проекции]], эта операция обычно несимметрична и зависит от [[Дивергенция Брэгмана#Несимметричность|ориентации дивергенции Брэгмана]].
-:: <tex>\min_x\{F(x)=h(x)+r(x)\},</tex>
+=== Proximal mirror descent ===
-где <tex>h</tex> выпукла и <tex>L</tex>-гладка, а проксимальный оператор <tex>r</tex> вычислим, [[Проксимальный градиентный метод]] выполняет
+Для составной задачи
-:: <tex>x_{t+1}=\operatorname{prox}_{\alpha r}(x_t-\alpha\nabla h(x_t)),</tex>
+:: <tex>\min_{x\in X}\{f(x)+r(x)\},</tex>
-:: <tex>\operatorname{prox}_{\alpha r}(z)=\operatorname{arg\,min}_x\left\{r(x)+\frac{1}{2\alpha}\|x-z\|_2^2\right\}.</tex>
+где <tex>r</tex> выпукла и имеет доступный проксимальный оператор, '''проксимальный зеркальный спуск''' использует
-Это не субградиентный шаг для всей <tex>F</tex>: негладкий член обрабатывается точно внутри проксимальной подзадачи. При <tex>\alpha\leq1/L</tex> метод имеет порядок <tex>O(1/T)</tex>, а [[Ускоренный градиентный метод|ускоренный вариант]] — <tex>O(1/T^2)</tex>. Для <tex>r(x)=\lambda\|x\|_1</tex> [[Мягкая пороговая обработка|soft-thresholding]] создаёт точные нули, тогда как обычный субградиентный шаг обычно колеблется около нуля<ref name="BeckTeboulle">{{статья |автор=Beck A., Teboulle M. |заглавие=A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |ссылка=https://doi.org/10.1137/080716542 |издание=SIAM Journal on Imaging Sciences |год=2009 |том=2 |номер=1 |страницы=183—202 |язык=en}}</ref>.
+:: <tex>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)\}.</tex>
-=== Bundle methods ===
+Это не то же самое, что базовый MD, если <tex>r</tex> включена только через субградиент. Точное включение <tex>r</tex> часто сохраняет разреженность и улучшает константы. [[Проксимальный градиентный метод]] обычно означает евклидову схему для гладкой <tex>f</tex> и негладкой <tex>r</tex>; брэгмановский проксимальный градиент является её неевклидовым обобщением.
-[[Bundle method|Bundle methods]] сохраняют несколько опорных плоскостей
+=== Dual averaging ===
-:: <tex>m_t(x)=\max_{i\in B_t}\{f(x_i)+\langle g_i,x-x_i\rangle\}</tex>
+Метод двойственного усреднения накапливает градиенты
-и минимизируют стабилизированную кусочно-линейную модель. Они используют больше памяти и решают более дорогую подзадачу, но повторно используют информацию о прошлых изломах, различают серьёзные и холостые шаги и обычно устойчивее к масштабу. Современный анализ проксимального bundle method показывает адаптацию к гладкости и условиям роста и оптимальные темпы при подходящих непостоянных параметрах<ref name="DiazGrimmer">{{статья |автор=Díaz M., Grimmer B. |заглавие=Optimal Convergence Rates for the Proximal Bundle Method |ссылка=https://doi.org/10.1137/21M1428601 |издание=SIAM Journal on Optimization |год=2023 |том=33 |номер=2 |страницы=424—454 |язык=en}}</ref>. Bundle method не является «субградиентным методом с памятью» в смысле одной и той же итерации: его модель и критерий принятия шага принципиально иные.
+:: <tex>s_t=\sum_{k=1}^t\alpha_k g_k</tex>
-=== Сравнение ===
+и строит точку, например, по правилу
+:: <tex>x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\langle s_t,x\rangle+\beta_t\psi(x)\}.</tex>
+В MD регуляризатор центрирован в текущей точке через <tex>D_\psi(x,x_t)</tex>; в dual averaging он сопоставляет всей накопленной линейной модели один регуляризатор, обычно центрированный в фиксированной исходной точке. При постоянных параметрах некоторые варианты алгебраически совпадают, но при изменяющемся темпе обучения различия существенны. В частности, обычный online MD с наивно меняющимся шагом может иметь линейное сожаление там, где dual averaging сохраняет хорошую гарантию; стабилизированные варианты MD устраняют эту проблему<ref name="Fang">{{статья |автор=Fang H., Harvey N. J. A., Portella V. S., Friedlander M. P. |заглавие=Online Mirror Descent and Dual Averaging: Keeping Pace in the Dynamic Case |ссылка=https://jmlr.org/papers/v23/21-1027.html |издание=Journal of Machine Learning Research |год=2022 |том=23 |страницы=1—38 |язык=en}}</ref>. Классические конструкции dual averaging принадлежат Ю. Нестерову<ref name="Nesterov2009">{{статья |автор=Nesterov Y. |заглавие=Primal-Dual Subgradient Methods for Convex Problems |ссылка=https://doi.org/10.1007/s10107-007-0149-x |издание=Mathematical Programming |год=2009 |том=120 |номер=1 |страницы=221—259 |doi=10.1007/s10107-007-0149-x |язык=en}}</ref>; регуляризованная версия для стохастического обучения подробно исследована Л. Сяо<ref name="Xiao">{{статья |автор=Xiao L. |заглавие=Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization |ссылка=https://jmlr.org/papers/v11/xiao10a.html |издание=Journal of Machine Learning Research |год=2010 |том=11 |страницы=2543—2596 |язык=en}}</ref>.
+=== Natural gradient ===
+[[Естественный градиент]] задаёт риманову метрику, часто матрицей информации Фишера, и делает локальный шаг
+:: <tex>x_{t+1}\approx x_t-\eta_t G(x_t)^{-1}\nabla f(x_t).</tex>
+Если <tex>G(x)=\nabla^2\psi(x)</tex>, это локальная аппроксимация зеркального шага. Однако не всякая [[Риманова метрика|риманова метрика]] является гессианом глобального выпуклого потенциала, зеркальная итерация использует конечную [[Дивергенция Брэгмана|дивергенцию Брэгмана]], а естественный градиент обычно формулируется на [[Статистическое многообразие|статистическом многообразии]]. Поэтому отождествлять методы без дополнительных условий нельзя.
+=== Сравнение методов ===
 {| class="wikitable"
 ! Метод
-! Предпосылка о цели
+! Геометрия и ограничения
-! Ограничения
+! Итерационная подзадача
-! Стоимость итерации
 ! Память
-! Типичная гарантия
+! Типичная гарантия в выпуклом липшицевом случае
 |-
-| Субградиентный спуск
+| [[Градиентный спуск]] / субградиентный спуск
-| Выпуклость и ограниченные субградиенты
+| Евклидова; без ограничений
-| Без ограничений
+| Векторное сложение, обычно <tex>O(d)</tex>
-| Один оракул и векторное сложение, обычно <tex>O(d)</tex>
 | <tex>O(d)</tex>
-| <tex>O(T^{-1/2})</tex>; <tex>O(T^{-1})</tex> при сильной выпуклости и правильном усреднении
+| <tex>O(T^{-1/2})</tex> для негладкой задачи; <tex>O(T^{-1})</tex> для выпуклой <tex>L</tex>-гладкой задачи
 |-
-| Projected subgradient descent
+| Projected gradient descent
-| То же
+| Евклидова; явное множество <tex>X</tex>
-| Замкнутое выпуклое <tex>X</tex>
+| Евклидова проекция; от закрытой формы до отдельной задачи оптимизации
-| Оракул плюс проекция на <tex>X</tex>
+| <tex>O(d)</tex>
-| <tex>O(d)</tex> без состояния проектора
+| <tex>O(T^{-1/2})</tex> в негладком и <tex>O(T^{-1})</tex> в гладком случае при стандартных предпосылках
-| Те же порядки; константа зависит от расстояния в допустимом множестве
 |-
-| Градиентный спуск
+| Mirror descent
-| Выпуклость и <tex>L</tex>-гладкость
+| Произвольная норма и брэгмановская геометрия
-| Обычно без ограничений или с проекцией
+| Зеркальная прокс-операция; часто <tex>O(d)</tex> на симплексе, но может быть дорогой
-| Градиент и простой шаг
 | <tex>O(d)</tex>
-| <tex>O(T^{-1})</tex>; линейно при сильной выпуклости
+| <tex>O(T^{-1/2})</tex>; константа определяется <tex>D_\psi</tex> и двойственной нормой
 |-
 | Proximal gradient
-| <tex>h</tex> гладка, <tex>r</tex> проксимально проста
+| Обычно евклидова; составная цель <tex>f+r</tex>
-| Через prox или отдельную проекцию
+| Проксимальный оператор <tex>r</tex>
-| Градиент плюс prox
 | <tex>O(d)</tex>
-| <tex>O(T^{-1})</tex>, ускоренно <tex>O(T^{-2})</tex>; линейно при дополнительных условиях
+| <tex>O(T^{-1})</tex> при выпуклой гладкой <tex>f</tex>; ускорение даёт <tex>O(T^{-2})</tex>
 |-
-| Bundle method
+| Proximal mirror descent
-| Выпуклая негладкая цель и оракул значений с субградиентами
+| Брэгмановская; составная цель и ограничения
-| Встраиваются в модель или подзадачу
+| Совместная прокс-операция для <tex>r</tex> и <tex>D_\psi</tex>
-| Решение стабилизированной QP или родственной задачи
+| <tex>O(d)</tex>
-| <tex>O(md)</tex> для bundle размера <tex>m</tex>, без учёта факторизаций
+| Как у MD при ограниченных субградиентах; быстрее при относительной гладкости и дополнительных условиях
-| Сохраняет оракульные оценки базового класса; лучшие практические и адаптивные гарантии при дополнительной структуре
+|-
+| Dual averaging
+| Геометрия фиксированного регуляризатора
+| Минимизация накопленной линейной модели с регуляризатором
+| <tex>O(d)</tex> для суммы градиентов; хранить всю историю не требуется
+| <tex>O(T^{-1/2})</tex>; особенно удобно для меняющихся шагов и явной регуляризации
 |}
+Указанная память не включает состояние стохастического оракула, распределённой системы или адаптивного предобусловливателя. Сложность зеркальной подзадачи является частью алгоритма: теоретически подходящая геометрия бесполезна, если соответствующий prox нельзя вычислить достаточно точно и дёшево.
 == Применения в машинном обучении ==
-=== Негладкие функции потерь ===
+=== Вероятностный симплекс и смеси ===
-Субградиентный оракул естественен для [[Абсолютная ошибка|абсолютной ошибки]], [[Квантильная регрессия|pinball loss]], [[Кусочно-линейная функция потерь|hinge loss]] и максимумов потерь. Для [[Линейная модель|линейной модели]] <tex>s_i=y_i\langle w,x_i\rangle</tex> и hinge loss
+Энтропийный MD естественно поддерживает неотрицательность и единичную сумму без евклидовой сортирующей проекции. Это используется при обучении весов ансамбля, смесей экспертов, вероятностных распределений, тематических моделей, политик и матриц переходов. Мультипликативный шаг изменяет относительные, а не абсолютные веса: малая компонента получает изменение, пропорциональное её текущему масштабу.
-:: <tex>\ell_i(w)=\max(0,1-s_i)</tex>
+При оптимуме на границе симплекса энтропийные итерации, начатые во внутренности, остаются строго положительными. Они могут сходиться к граничной точке, но не создают точный ноль за конечное число шагов. Если точная разреженность обязательна, полезнее иной потенциал, явный проксимальный член или последующее пороговое преобразование с отдельным анализом.
-можно взять
+=== Онлайн-обучение ===
-:: <tex>g_i(w)=\begin{cases}-y_i x_i,&s_i<1,\\0,&s_i>1,\end{cases}</tex>
+В [[Онлайн-обучение|онлайн-выпуклой оптимизации]] на раунде <tex>t</tex> алгоритм выбирает <tex>x_t</tex>, затем наблюдает выпуклую потерю <tex>\ell_t</tex>. Статическое сожаление относительно <tex>u\in X</tex> равно
-а при <tex>s_i=1</tex> — любую точку отрезка между этими векторами. Стохастический выбор примера даёт дешёвое обновление линейного [[Метод опорных векторов|SVM]]. Алгоритм Pegasos сочетает такой шаг с регуляризацией и проекцией и для регуляризованной primal-задачи SVM имеет сложность, не зависящую линейно от числа обучающих примеров<ref name="Pegasos">{{статья |автор=Shalev-Shwartz S., Singer Y., Srebro N., Cotter A. |заглавие=Pegasos: Primal Estimated sub-GrAdient SOlver for SVM |ссылка=https://doi.org/10.1007/s10107-010-0420-4 |издание=Mathematical Programming |год=2011 |том=127 |страницы=3—30 |язык=en}}</ref>.
+:: <tex>\mathrm{Reg}_T(u)=\sum_{t=1}^T[\ell_t(x_t)-\ell_t(u)].</tex>
-=== Регуляризованные линейные модели ===
+По выпуклости оно не превосходит <tex>\sum_t\langle g_t,x_t-u\rangle</tex>. Поэтому основное неравенство MD сразу даёт
-В задаче [[Регуляризация|регуляризованного]] [[Эмпирический риск|эмпирического риска]]
+:: <tex>\mathrm{Reg}_T(u)\leq\frac{D_\psi(u,x_1)}{\eta}+\frac{\eta}{2\sigma}\sum_{t=1}^T\|g_t\|_*^2.</tex>
-:: <tex>\min_w\frac1n\sum_{i=1}^n\ell_i(w)+\lambda R(w)</tex>
+При ограниченных градиентах это <tex>O(\sqrt T)</tex>, то есть среднее сожаление стремится к нулю. Энтропийный случай даёт алгоритм предсказания с экспертами. Адаптивные регуляризаторы превращают эту идею в семейство методов, родственное [[AdaGrad]]<ref name="Duchi">{{статья |автор=Duchi J., Hazan E., Singer Y. |заглавие=Adaptive Subgradient Methods for Online Learning and Stochastic Optimization |ссылка=https://jmlr.org/papers/v12/duchi11a.html |издание=Journal of Machine Learning Research |год=2011 |том=12 |страницы=2121—2159 |язык=en}}</ref>.
-субградиент суммы позволяет обрабатывать негладкие <tex>\ell_i</tex> и <tex>R</tex> единым оракулом. Это полезно, если prox для <tex>R</tex> неизвестен или слишком дорог. Если же <tex>R=\|w\|_1</tex>, [[Групповая регуляризация|групповая норма]] или [[Индикатор множества|индикатор]] простого множества, проксимальный или зеркальный метод обычно предпочтительнее: он использует структуру регуляризатора, сохраняет [[Разреженность|разреженность]] и допускает более быстрый темп при гладкой части потерь.
+=== Линейные модели и разреженность ===
-Для задачи с <tex>\ell_2</tex>-регуляризацией сильная выпуклость оправдывает шаг порядка <tex>1/t</tex>. Для нестрого выпуклой линейной модели нельзя использовать эту оценку только потому, что функция потерь выпукла.
+Для линейной и логистической регрессии геометрия <tex>\ell_1/\ell_\infty</tex> полезна, когда признаки высокоразмерны, а градиенты естественно ограничены в максимальной норме. Однако сам энтропийный MD требует неотрицательных переменных; знаковые коэффициенты представляют как разность двух неотрицательных векторов либо выбирают <tex>\ell_p</tex>-потенциал. Для составной цели с <tex>\ell_1</tex>-штрафом proximal MD или regularized dual averaging предпочтительнее включения субградиента штрафа: точный prox способен создавать нулевые коэффициенты<ref name="Xiao"/>. Современные схемы стохастического зеркального спуска применяются и к крупномасштабному восстановлению разреженных параметров и обобщённым линейным моделям<ref name="Ilandarideva">{{статья |автор=Ilandarideva S., Bekri Y., Iouditski A., Perchet V. |заглавие=Stochastic Mirror Descent for Large-Scale Sparse Recovery |ссылка=https://proceedings.mlr.press/v206/ilandarideva23a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2023 |том=206 |страницы=5931—5957 |язык=en}}</ref>.
-=== Крупномасштабное и онлайн-обучение ===
+=== Стохастическая и распределённая оптимизация ===
-Один субградиент примера или [[Мини-пакет|мини-пакета]] стоит существенно дешевле полного прохода по данным. В [[Онлайн-обучение|онлайн-обучении]] то же одношаговое неравенство оценивает [[Regret|regret]]
+В стохастическом обучении зеркальная геометрия меняет то, в какой норме контролируется шум. Это может уменьшить размерностную зависимость, но не устраняет дисперсию автоматически. Мини-батчи, усреднение итераций, уменьшение дисперсии, отсечение тяжёлых хвостов и адаптация шага являются отдельными механизмами.
-:: <tex>\operatorname{Regret}_T(u)=\sum_{t=1}^T\bigl(f_t(x_t)-f_t(u)\bigr).</tex>
+В распределённой задаче агенты сочетают локальные зеркальные шаги с консенсусом или отслеживанием градиента. Потенциал можно согласовать не только с локальными ограничениями, но и с геометрией согласования. Итоговая скорость зависит одновременно от брэгмановского радиуса, шума, числа локальных шагов и спектральных характеристик коммуникационного графа; локальная гарантия MD сама по себе не устраняет сетевой член. Для распределённой составной онлайн-оптимизации разработаны варианты с динамическим сожалением и зеркальными prox-шагами<ref name="Yuan">{{cite web |url=https://arxiv.org/abs/2004.00837 |title=Distributed Mirror Descent for Online Composite Optimization |author=Yuan D., Hong Y., Ho D. W. C., Xu S. |date=2020 |website=arXiv |access-date=2026-07-14 |lang=en}}</ref>.
-При выпуклых потерях, диаметре области <tex>R</tex> и субградиентах нормы не более <tex>G</tex> настроенный шаг даёт <tex>\operatorname{Regret}_T(u)\leq RG\sqrt T</tex>. Деление на <tex>T</tex> и online-to-batch conversion возвращает статистическую оценку порядка <tex>1/\sqrt T</tex>. AdaGrad улучшает зависимость от координатной геометрии для разреженных признаков, но не меняет худший порядок без дополнительной структуры.
+== Выбор зеркального отображения ==
-=== Распределённая оптимизация ===
+Практический выбор <tex>\psi</tex> — это совместная оптимизация статистических и вычислительных констант. Полезен следующий порядок проверки.
-В [[Распределённая оптимизация|распределённой оптимизации]] для суммы локальных целей
+# '''Согласовать норму с оракулом.''' Найти норму, в которой <tex>\|g_t\|_*</tex> мало или естественно контролируется.
+# '''Оценить [[Дивергенция Брэгмана#Брэгмановский радиус|брэгмановский радиус]].''' Для предполагаемого класса решений оценить <tex>\sup_{u}D_\psi(u,x_1)</tex> либо локальную величину <tex>D_\psi(x^*,x_1)</tex>.
+# '''Проверить сильную выпуклость.''' Константа <tex>\sigma</tex> должна относиться к той же норме, которая использована для градиента.
+# '''Решить prox-подзадачу.''' Нужна закрытая форма, быстрый специализированный алгоритм или контролируемая точность внутреннего решателя.
+# '''Проверить область потенциала.''' Градиент <tex>\nabla\psi</tex> должен существовать на всех итерациях; для барьерных и энтропийных потенциалов требуется старт в относительной внутренности.
+# '''Проверить численную устойчивость.''' Экспоненты, логарифмы и спектральные функции требуют стабилизации; формальная закрытая форма не гарантирует устойчивой реализации.
-:: <tex>f(x)=\sum_{i=1}^m f_i(x)</tex>
+Масштабирование потенциала и шага избыточно: замена <tex>\psi</tex> на <tex>c\psi</tex> эквивалентна соответствующему изменению <tex>\eta_t</tex>. Сравнивать потенциалы только по константе сильной выпуклости без учёта радиуса <tex>D_\psi</tex> некорректно; в оценке участвует их отношение.
-узлы могут чередовать усреднение параметров по [[Граф (математика)|графу]] связи и локальный субградиентный шаг. Сходимость требует связности во времени, согласованных [[Стохастическая матрица|стохастических матриц]] смешивания, убывающих шагов и контроля ошибок [[Консенсус в многоагентных системах|консенсуса]]. Скорость зависит не только от <tex>G</tex> и геометрии задачи, но и от [[Спектральный разрыв|спектрального разрыва]] сети; задержки, квантизация и несбалансированные ориентированные графы требуют отдельных вариантов<ref name="NedicOzdaglar">{{статья |автор=Nedić A., Ozdaglar A. |заглавие=Distributed Subgradient Methods for Multi-Agent Optimization |ссылка=https://doi.org/10.1109/TAC.2008.2009515 |издание=IEEE Transactions on Automatic Control |год=2009 |том=54 |номер=1 |страницы=48—61 |язык=en}}</ref>. Это распределённый алгоритм консенсуса с субградиентами, а не обычный SGD на одном общем потоке данных.
+== Ограничения и типичные ошибки ==
-=== Невыпуклые модели ===
+* '''Дорогой зеркальный prox.''' На общих многогранниках, спектральных множествах и при сложных составных ограничениях подзадача может быть дороже евклидовой проекции.
+* '''Несогласованные нормы.''' Нельзя брать сильную выпуклость относительно <tex>\ell_1</tex>, а градиент ограничивать в <tex>\ell_2</tex>, не вводя явные коэффициенты эквивалентности норм.
+* '''Неверный порядок аргументов.''' В общем случае <tex>D_\psi(x,y)\neq D_\psi(y,x)</tex>; из-за [[Дивергенция Брэгмана#Несимметричность|несимметричности дивергенции Брэгмана]] перестановка аргументов ломает телескопирование и алгоритм.
+* '''Игнорирование границы.''' У отрицательной энтропии градиент не определён при нулевых координатах. Старт с нуля делает стандартную двойственную запись некорректной, а мультипликативное обновление навсегда сохраняет ноль.
+* '''Смешение гладкости.''' Евклидова липшицевость градиента, относительная гладкость и ограниченность субградиента — разные предпосылки и приводят к разным скоростям.
+* '''Неправильный выход.''' Для негладкой выпуклой задачи оценка часто доказана только для взвешенного среднего. Последняя итерация может требовать сильной выпуклости, монотонности шага или отдельного результата.
+* '''Неточная подзадача.''' Ошибки внутреннего prox-решателя должны быть суммируемы или явно включены в оценку; иначе номинальная скорость не гарантируется.
+* '''Наивно меняющийся шаг в online MD.''' Эквивалентность с dual averaging может исчезнуть, а сожаление — ухудшиться вплоть до линейного<ref name="Fang"/>.
+* '''Слишком общий вывод о natural gradient.''' Совпадение локальных метрических тензоров не доказывает совпадение конечных итераций.
+* '''Плохая численная реализация.''' Прямое вычисление экспонент вызывает переполнение и исчезновение малых весов; матричные зеркальные шаги могут терять положительную определённость из-за округления.
-В [[Глубокая нейронная сеть|глубоких сетях]] с [[ReLU|ReLU]] [[Автоматическое дифференцирование|автоматическое дифференцирование]] выбирает одну из допустимых производных на изломах, и процедура внешне похожа на stochastic subgradient descent. Однако функция параметров невыпукла, субградиент в смысле выпуклого анализа неприменим, а приведённые выше оценки разрыва до глобального оптимума неверны. Для локально липшицевых [[Слабовыпуклая функция|слабовыпуклых функций]] современные результаты измеряют [[Стационарная точка|стационарность]] через градиент [[Оболочка Моро|оболочки Моро]]; стохастический субградиентный метод достигает характерного порядка <tex>O(T^{-1/4})</tex> по норме такого градиента при ограниченном втором моменте стохастических субградиентов и надлежащем случайном выборе выходной итерации<ref name="DavisDrusvyatskiy">{{статья |автор=Davis D., Drusvyatskiy D. |заглавие=Stochastic Subgradient Method Converges at the Rate <tex>O(k^{-1/4})</tex> on Weakly Convex Functions |ссылка=https://arxiv.org/abs/1802.02988 |год=2018 |язык=en}}</ref>. Для tame-функций установлена почти наверное сходимость предельных точек к критическому множеству при роббинс-монровских шагах и дополнительных геометрических предпосылках<ref name="Tame">{{статья |автор=Davis D., Drusvyatskiy D., Kakade S., Lee J. D. |заглавие=Stochastic Subgradient Method Converges on Tame Functions |ссылка=https://doi.org/10.1007/s10208-018-09409-5 |издание=Foundations of Computational Mathematics |год=2020 |том=20 |страницы=119—154 |язык=en}}</ref>. Это современные невыпуклые обобщения, а не классическая выпуклая теория.
+Зеркальный спуск практически предпочтителен евклидовым методам, когда ограничения имеют простой неевклидов prox, [[Дивергенция Брэгмана#Брэгмановский радиус|брэгмановский радиус]] заметно меньше евклидова, а градиенты хорошо ограничены в соответствующей [[Двойственная норма|двойственной норме]]. Типичные примеры — большой симплекс, матричный симплекс, задачи с относительной гладкостью и высокоразмерные онлайн-задачи. Евклидов метод обычно предпочтительнее, если проекция проста, геометрия близка к изотропной, а вычисление зеркального отображения требует дорогой факторизации или внутренней оптимизации.
-== Ограничения и типичные ошибки ==
+== Классические результаты и современные обобщения ==
-* '''Ожидание монотонного спуска.''' Значение цели может возрастать даже при корректном субградиенте; контролируется лучшая или усреднённая точка.
+К классическому ядру относятся: метод Немировского—Юдина; интерпретация через [[Дивергенция Брэгмана|дивергенцию Брэгмана]] и негладкая оценка <tex>O(T^{-1/2})</tex>; энтропийный шаг на симплексе; стохастический MD с ограниченным вторым моментом; dual averaging и составные prox-варианты<ref name="NY"/><ref name="BT"/><ref name="NJLS"/><ref name="Xiao"/>.
-* '''Слишком большой постоянный шаг.''' Метод остаётся в широкой окрестности решения и может осциллировать через излом.
-* '''Слишком быстрое убывание.''' Если сумма шагов конечна, траектория может не дойти до оптимума; правило <tex>1/t</tex> без сильной выпуклости часто преждевременно замораживает обучение.
-* '''Неверный субградиент на границе кусков.''' Производная неактивной ветви максимума или неверный знак у hinge loss нарушают опорное неравенство.
-* '''Игнорирование масштаба.''' Необработанные признаки делают <tex>G</tex> большим и анизотропным; нормализация, зеркальная геометрия или AdaGrad могут изменить константы на порядки.
-* '''Необоснованная несмещённость.''' Субградиент случайного слагаемого не всегда можно переставить с математическим ожиданием; условия интегрируемости и правила субдифференцирования ожидания должны быть проверены.
-* '''Неправильный выход.''' Гарантия для <tex>\bar x_T</tex> не переносится автоматически на <tex>x_T</tex>; усреднение параметров может быть нежелательно для структурно разреженного решения.
-* '''Смешение с proximal gradient.''' Обработка <tex>\ell_1</tex>-штрафа его субградиентом не эквивалентна soft-thresholding и обычно не создаёт точных нулей.
-* '''Скрытая стоимость проекции.''' Для сложного <tex>X</tex> проекционная подзадача может доминировать над вычислением субградиента.
-* '''Перенос выпуклой теории на нейронные сети.''' Выбор производной ReLU библиотекой не делает глобальную цель выпуклой.
-Субградиентный метод практически предпочтителен, когда требуется очень дешёвая итерация, доступен только оракул негладкой функции, точность умеренна, размерность или поток данных исключают хранение моделей, а prox или bundle-подзадача дороже нескольких дополнительных проходов. Для высокой точности, доступной составной структуры или дорогого оракула обычно выгоднее проксимальные, сглаженные, cutting-plane или bundle methods.
+Более новые направления не следует считать синонимами базового MD:
-== Классические результаты и современные варианты ==
+* '''Относительная гладкость''' заменяет глобальную липшицевость градиента сравнением кривизны цели и потенциала<ref name="LFN"/>.
+* '''Оптимистический MD''' и mirror-prox используют предсказание следующего градиента или дополнительную оценку оператора; они предназначены, в частности, для седловых задач и [[Вариационное неравенство|вариационных неравенств]], а не являются одной итерацией обычного MD. Для стохастических вариационных неравенств исследованы гарантии последней итерации оптимистических методов<ref name="Azizian">{{статья |автор=Azizian W., Iutzeler F., Malick J., Mertikopoulos P. |заглавие=The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities |ссылка=https://proceedings.mlr.press/v134/azizian21a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2021 |том=134 |язык=en}}</ref>.
+* '''Адаптивный и параметрически свободный online MD''' выбирает регуляризатор или масштаб из истории градиентов; гарантии выражаются через наблюдаемую геометрию, но алгоритм уже отличается от MD с фиксированным потенциалом<ref name="Cutkosky">{{статья |автор=Cutkosky A., Orabona F. |заглавие=Black-Box Reductions for Parameter-free Online Learning in Banach Spaces |ссылка=https://proceedings.mlr.press/v75/cutkosky18a.html |издание=Proceedings of Machine Learning Research: COLT |год=2018 |том=75 |страницы=1493—1529 |язык=en}}</ref>.
+* '''Тяжёлохвостый SMD''' заменяет условие ограниченного второго момента более слабыми моментными условиями и нередко применяет отсечение или равномерно выпуклые потенциалы.
+* '''Невыпуклый SMD''' измеряет стационарность через [[Дивергенция Брэгмана#Брэгмановское градиентное отображение|брэгмановское градиентное отображение]]. Современный анализ допускает общие [[Дивергенция Брэгмана|дивергенции Брэгмана]], включая энтропийную, без глобальной липшицевости градиента потенциала<ref name="Fatkhullin">{{статья |автор=Fatkhullin I., He N. |заглавие=Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence |ссылка=https://proceedings.mlr.press/v238/fatkhullin24a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2024 |том=238 |язык=en}}</ref>. Эти результаты не дают глобальной оптимальности для общей невыпуклой функции.
-К классическому ядру относятся субдифференциал выпуклой функции, проекционное обновление, оценки <tex>O(T^{-1/2})</tex>, роббинс-монровские условия на шаги и правило Поляка<ref name="Bertsekas">{{книга |автор=Bertsekas D. P. |заглавие=Convex Optimization Algorithms |издательство=Athena Scientific |год=2015 |язык=en}}</ref>. Стохастическая аппроксимация, распределённые схемы, AdaGrad и оптимальные правила усреднения развивают эту основу, сохраняя выпуклую постановку.
+== Заключение ==
-К более новым направлениям относятся точный анализ последней итерации, робастные методы при тяжёлых хвостах, слабовыпуклые и стратифицированные невыпуклые функции, а также адаптивные bundle methods. Их гарантии используют разные критерии качества — разрыв по функции, regret, расстояние до решения или норму градиента оболочки Моро — и потому не должны сравниваться только по степени <tex>T</tex>. Например, хвостовые оценки для негладкого stochastic mirror descent при шуме тяжелее субгауссовского требуют явных моментных предпосылок и иной концентрационной техники<ref name="Eldowa">{{статья |автор=Eldowa K., Paudice A. |заглавие=General Tail Bounds for Non-Smooth Stochastic Mirror Descent |ссылка=https://proceedings.mlr.press/v238/eldowa24a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2024 |том=238 |язык=en}}</ref>.
+Зеркальный спуск отделяет информацию первого порядка от способа измерения перемещений. Его универсальная итерация остаётся простой, но качество метода определяется согласованием трёх объектов: нормы и её двойственной нормы, брэгмановского потенциала и вычислимости зеркального prox. В евклидовой геометрии метод сводится к проекционному градиентному спуску; на симплексе — к экспоненциальному взвешиванию. Классическая теория даёт оптимальные порядки для негладкой выпуклой и стохастической оптимизации, а современные расширения охватывают относительную гладкость, тяжёлые хвосты, онлайн-адаптацию, распределённые и невыпуклые задачи. При переносе гарантий критически важно сохранять точные предпосылки: вид усреднения, ориентацию дивергенции, норму, моментные условия и точность решения прокс-подзадачи.
 == Примечания ==
@@ Строка 401: / Строка 396: @@
 == Литература ==
-* {{статья |автор=Polyak B. T. |заглавие=Minimization of Unsmooth Functionals |издание=USSR Computational Mathematics and Mathematical Physics |год=1969 |том=9 |номер=3 |страницы=14—29 |doi=10.1016/0041-5553(69)90061-5 |язык=en}}
+* {{статья |автор=Bregman L. M. |заглавие=The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming |ссылка=https://doi.org/10.1016/0041-5553(67)90040-7 |издание=USSR Computational Mathematics and Mathematical Physics |год=1967 |том=7 |номер=3 |страницы=200—217 |doi=10.1016/0041-5553(67)90040-7 |язык=en}}
-* {{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://doi.org/10.1515/9781400873173 |издательство=Princeton University Press |год=1970 |язык=en}}
+* {{книга |автор=Nemirovsky A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |ссылка=https://www2.isye.gatech.edu/~nemirovs/Nemirovskii_Yudin_1983.pdf |издательство=Wiley |год=1983 |язык=en}}
-* {{книга |автор=Nemirovski A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |издательство=Wiley |год=1983 |язык=en}}
+* {{статья |автор=Beck A., Teboulle M. |заглавие=Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization |ссылка=https://doi.org/10.1016/S0167-6377(02)00231-6 |издание=Operations Research Letters |год=2003 |том=31 |номер=3 |страницы=167—175 |doi=10.1016/S0167-6377(02)00231-6 |язык=en}}
-* {{книга |автор=Shor N. Z. |заглавие=Minimization Methods for Non-Differentiable Functions |ссылка=https://doi.org/10.1007/978-3-642-82118-9 |издательство=Springer |год=1985 |язык=en}}
+* {{статья |автор=Nemirovski A., Juditsky A., Lan G., Shapiro A. |заглавие=Robust Stochastic Approximation Approach to Stochastic Programming |ссылка=https://doi.org/10.1137/070704277 |издание=SIAM Journal on Optimization |год=2009 |том=19 |номер=4 |страницы=1574—1609 |doi=10.1137/070704277 |язык=en}}
-* {{статья |автор=Beck A., Teboulle M. |заглавие=Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization |ссылка=https://doi.org/10.1016/S0167-6377(02)00231-6 |издание=Operations Research Letters |год=2003 |том=31 |номер=3 |страницы=167—175 |язык=en}}
+* {{статья |автор=Nesterov Y. |заглавие=Primal-Dual Subgradient Methods for Convex Problems |ссылка=https://doi.org/10.1007/s10107-007-0149-x |издание=Mathematical Programming |год=2009 |том=120 |номер=1 |страницы=221—259 |doi=10.1007/s10107-007-0149-x |язык=en}}
-* {{статья |автор=Nemirovski A., Juditsky A., Lan G., Shapiro A. |заглавие=Robust Stochastic Approximation Approach to Stochastic Programming |ссылка=https://doi.org/10.1137/070704277 |издание=SIAM Journal on Optimization |год=2009 |том=19 |номер=4 |страницы=1574—1609 |язык=en}}
+* {{статья |автор=Xiao L. |заглавие=Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization |ссылка=https://jmlr.org/papers/v11/xiao10a.html |издание=Journal of Machine Learning Research |год=2010 |том=11 |страницы=2543—2596 |язык=en}}
 * {{статья |автор=Duchi J., Hazan E., Singer Y. |заглавие=Adaptive Subgradient Methods for Online Learning and Stochastic Optimization |ссылка=https://jmlr.org/papers/v12/duchi11a.html |издание=Journal of Machine Learning Research |год=2011 |том=12 |страницы=2121—2159 |язык=en}}
-* {{книга |автор=Bertsekas D. P. |заглавие=Convex Optimization Algorithms |издательство=Athena Scientific |год=2015 |язык=en}}
 * {{статья |автор=Bubeck S. |заглавие=Convex Optimization: Algorithms and Complexity |ссылка=https://arxiv.org/abs/1405.4980 |издание=Foundations and Trends in Machine Learning |год=2015 |том=8 |номер=3—4 |страницы=231—357 |язык=en}}
-* {{статья |автор=Davis D., Drusvyatskiy D., Kakade S., Lee J. D. |заглавие=Stochastic Subgradient Method Converges on Tame Functions |ссылка=https://doi.org/10.1007/s10208-018-09409-5 |издание=Foundations of Computational Mathematics |год=2020 |том=20 |страницы=119—154 |язык=en}}
+* {{статья |автор=Cutkosky A., Orabona F. |заглавие=Black-Box Reductions for Parameter-free Online Learning in Banach Spaces |ссылка=https://proceedings.mlr.press/v75/cutkosky18a.html |издание=Proceedings of Machine Learning Research: COLT |год=2018 |том=75 |страницы=1493—1529 |язык=en}}
-* {{статья |автор=Díaz M., Grimmer B. |заглавие=Optimal Convergence Rates for the Proximal Bundle Method |ссылка=https://doi.org/10.1137/21M1428601 |издание=SIAM Journal on Optimization |год=2023 |том=33 |номер=2 |страницы=424—454 |язык=en}}
+* {{статья |автор=Lu H., Freund R. M., Nesterov Y. |заглавие=Relatively Smooth Convex Optimization by First-Order Methods, and Applications |ссылка=https://doi.org/10.1137/16M1099546 |издание=SIAM Journal on Optimization |год=2018 |том=28 |номер=1 |страницы=333—354 |doi=10.1137/16M1099546 |язык=en}}
+* {{cite web |url=https://arxiv.org/abs/2004.00837 |title=Distributed Mirror Descent for Online Composite Optimization |author=Yuan D., Hong Y., Ho D. W. C., Xu S. |date=2020 |website=arXiv |access-date=2026-07-14 |lang=en}}
+* {{статья |автор=Azizian W., Iutzeler F., Malick J., Mertikopoulos P. |заглавие=The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities |ссылка=https://proceedings.mlr.press/v134/azizian21a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2021 |том=134 |язык=en}}
+* {{статья |автор=Fang H., Harvey N. J. A., Portella V. S., Friedlander M. P. |заглавие=Online Mirror Descent and Dual Averaging: Keeping Pace in the Dynamic Case |ссылка=https://jmlr.org/papers/v23/21-1027.html |издание=Journal of Machine Learning Research |год=2022 |том=23 |страницы=1—38 |язык=en}}
+* {{статья |автор=Vural N. M., Yu L., Balasubramanian K., Volgushev S., Erdogdu M. A. |заглавие=Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance |ссылка=https://proceedings.mlr.press/v178/vural22a.html |издание=Proceedings of Machine Learning Research: COLT |год=2022 |том=178 |страницы=65—102 |язык=en}}
+* {{статья |автор=Ilandarideva S., Bekri Y., Iouditski A., Perchet V. |заглавие=Stochastic Mirror Descent for Large-Scale Sparse Recovery |ссылка=https://proceedings.mlr.press/v206/ilandarideva23a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2023 |том=206 |страницы=5931—5957 |язык=en}}
 * {{статья |автор=Eldowa K., Paudice A. |заглавие=General Tail Bounds for Non-Smooth Stochastic Mirror Descent |ссылка=https://proceedings.mlr.press/v238/eldowa24a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2024 |том=238 |язык=en}}
+* {{статья |автор=Fatkhullin I., He N. |заглавие=Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence |ссылка=https://proceedings.mlr.press/v238/fatkhullin24a.html |издание=Proceedings of Machine Learning Research: AISTATS |год=2024 |том=238 |язык=en}}
 [[Категория:Методы оптимизации]]
@@ Строка 418: / Строка 418: @@
 [[Категория:Энциклопедия анализа данных]]
 [[Категория:Выпуклая оптимизация]]
-[[Категория:Стохастическая оптимизация]]
+[[Категория:Онлайн-обучение]]