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

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

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

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

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

Содержание

1 Постановка задачи
- 1.1 Геометрическая интуиция
2 Нормы и двойственные нормы
3 Базовый алгоритм
4 Оценки сходимости
5 Выбор субградиента
- 5.1 Правила исчисления
- 5.2 Практический выбор
6 Правила шага
7 Связь с родственными методами
8 Применения в машинном обучении
9 Ограничения и типичные ошибки
10 Классические результаты и современные варианты
11 Примечания
12 Литература

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

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

Пусть $X\subseteq\mathbb{R}^d$ — непустое замкнутое выпуклое множество, а $f:X\to\mathbb{R}\cup\{+\infty\}$ — собственная замкнутая выпуклая функция. Рассматривается задача

$f^*=\min_{x\in X} f(x),\qquad X^*=\operatorname{arg\,min}_{x\in X}f(x)\ne\emptyset.$

Вектор $g\in\mathbb{R}^d$ называется субградиентом $f$ в точке $x\in\operatorname{dom}f$ , если для любого $y$

$f(y)\geq f(x)+\langle g,y-x\rangle.$

Множество всех таких векторов обозначается $\partial f(x)$ и называется субдифференциалом Фенхеля — Моро. Для выпуклой дифференцируемой функции $\partial f(x)=\{\nabla f(x)\}$ ; тем самым субградиентный метод продолжает градиентный спуск на негладкий случай. Условие оптимальности неограниченной задачи имеет вид

$0\in\partial f(x^*).$

При ограничении $x\in X$ оно заменяется включением

$0\in\partial f(x^*)+N_X(x^*),$

где $N_X(x^*)$ — нормальный конус множества $X$ ^[1].

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

Неравенство субградиента задаёт опорную аффинную функцию, лежащую не выше графика $f$ . Полупространство

$\{y:\langle g,y-x\rangle\leq0\}$

содержит каждую точку $y$ , для которой $f(y)\leq f(x)$ . Поэтому направление $-g$ отделяет текущую точку от области лучших значений. Однако, в отличие от градиента гладкой функции, $-g$ не обязано быть направлением локального убывания: для $f(x)=|x|$ в точке $x=0$ допустим любой $g\in[-1,1]$ , и выбор $g\ne0$ уводит из минимума. Анализ метода основан не на лемме о гладком спуске, а на уменьшении расстояния до множества решений с точностью до квадрата шага.

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

Для нормы $\|\cdot\|$ двойственная норма определяется как

$\|g\|_*=\sup_{\|u\|\leq1}\langle g,u\rangle.$

Неравенство Гёльдера

$\langle g,u\rangle\leq\|g\|_*\|u\|$

связывает размер области в прямой норме с размером субградиентов в двойственной. Если $f$ выпукла и $G$ -липшицева на открытом множестве относительно $\|\cdot\|$ , то $\|g\|_*\leq G$ для всех субградиентов во внутренних точках; верно и обратное при соответствующих условиях на область.

В евклидовом пространстве градиент отождествляет линейный функционал с вектором, поэтому шаг $x-\alpha g$ естественен. Для общей нормы направление наискорейшего линейного спуска задаётся отображением

$v(g)\in\operatorname{arg\,min}_{v}\left\{\langle g,v\rangle+\frac12\|v\|^2\right\},\qquad \|v(g)\|=\|g\|_*.$

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

Более точно, пусть $\psi$ является $\sigma$ -сильно выпуклым потенциалом относительно $\|\cdot\|$ , а

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

Обновление

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

при $\|g_t\|_*\leq G$ удовлетворяет оценке

$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}.$

Евклидов результат получается при $\psi(x)=\frac12\|x\|_2^2$ . В неевклидовой геометрии константа определяется одновременно брэгмановским расстоянием до решения и нормой субградиентов в двойственной норме; например, на симплексе энтропийная геометрия часто заменяет полиномиальную зависимость от размерности логарифмической^[1].

Базовый алгоритм

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

Выбираются $x_1\in X$ , положительные шаги $\alpha_t$ и субградиенты $g_t\in\partial f(x_t)$ . Итерация имеет вид

$x_{t+1}=\Pi_X(x_t-\alpha_t g_t),$

где

$\Pi_X(z)=\operatorname{arg\,min}_{x\in X}\|x-z\|_2$

— евклидова проекция. При $X=\mathbb{R}^d$ проекция исчезает и получается обычный субградиентный спуск. Если функция дифференцируема, обновление совпадает с projected gradient descent, но оценки для гладкой задачи могут быть существенно быстрее благодаря липшицевости градиента.

Псевдокод

Вход: множество $X$ , точка $x_1\in X$ , число итераций $T$ , правило шага.

Для :
1. получить $g_t\in\partial f(x_t)$ или стохастическую оценку $G_t$ ;
2. выбрать $\alpha_t>0$ по заранее указанному правилу;
3. вычислить $x_{t+1}=\Pi_X(x_t-\alpha_t g_t)$ ;
вернуть лучшую вычисленную точку либо взвешенное среднее

$\bar x_T=\frac{\sum_{t=1}^T\alpha_t x_t}{\sum_{t=1}^T\alpha_t}.$

Для чисто оракульной задачи значение лучшей точки $\operatorname{arg\,min}_{t\leq T}f(x_t)$ требует вычислять $f(x_t)$ . В стохастической задаче выбор по шумной эмпирической потере вносит смещение, поэтому теоремы обычно относятся к усреднению или к специально построенной последней итерации.

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

Неэкспансивность проекции и неравенство субградиента дают для любого $x^*\in X^*$

$\|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.$

Это центральное соотношение: полезный член линеен по $\alpha_t$ , а накопленная ошибка шага квадратична. В общем случае значения $f(x_t)$ не обязаны убывать.

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

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

Теорема. Пусть $f$ выпукла на замкнутом выпуклом $X$ , $X^*\ne\emptyset$ , $\|g_t\|_2\leq G$ и $\|x_1-x^*\|_2\leq R$ для некоторого $x^*\in X^*$ . Тогда для положительных шагов

$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}.$

Та же правая часть ограничивает $\min_{1\leq t\leq T}f(x_t)-f^*$ . При известном горизонте выбор

$\alpha_t=\frac{R}{G\sqrt T}$

даёт

$f(\bar x_T)-f^*\leq\frac{RG}{\sqrt T}.$

Следовательно, для достижения ошибки не более $\varepsilon$ достаточно $O(R^2G^2/\varepsilon^2)$ вызовов субградиентного оракула. Этот порядок оптимален в худшем случае для класса выпуклых липшицевых функций при стандартной модели оракула первого порядка^[1]^[1].

Если горизонт заранее неизвестен, шаг $\alpha_t=c/\sqrt t$ даёт для обычного взвешенного среднего оценку порядка $O(\log T/\sqrt T)$ ; удвоение горизонта по эпохам или более аккуратное усреднение устраняет лишний логарифм. Условия

$\sum_{t=1}^{\infty}\alpha_t=\infty,\qquad \sum_{t=1}^{\infty}\alpha_t^2<\infty$

обеспечивают асимптотическую сходимость при ограниченных субградиентах, но сами по себе не дают лучшей конечновременной константы^[1].

Постоянный шаг

При $\alpha_t=\alpha$ предыдущая оценка принимает вид

$f(\bar x_T)-f^*\leq\frac{R^2}{2\alpha T}+\frac{\alpha G^2}{2}.$

Итерационный член исчезает, но остаётся окрестность оптимума радиуса по функции порядка $\alpha G^2$ . Поэтому постоянный learning rate без рестартов не обеспечивает произвольно точной сходимости для общей негладкой выпуклой задачи.

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

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

$f(y)\geq f(x)+\langle g,y-x\rangle+\frac\mu2\|y-x\|_2^2$

для всех $g\in\partial f(x)$ . Пусть также $\|g_t\|_2\leq G$ . Для шага

$\alpha_t=\frac{2}{\mu(t+1)}$

и среднего с линейными весами

$\widetilde x_T=\frac{2}{T(T+1)}\sum_{t=1}^T t x_t$

выполняется оценка порядка

$f(\widetilde x_T)-f^*\leq\frac{2G^2}{\mu(T+1)}.$

Таким образом, сложность уменьшается до $O(G^2/(\mu\varepsilon))$ . Для стандартного шага порядка $1/(\mu t)$ последняя итерация или равномерное среднее часто несут дополнительный множитель $\log T$ ; он не является фундаментальным и устраняется правильными весами либо специальным расписанием шагов. В стохастическом случае оптимальность последней итерации требует отдельного анализа^[1].

Сильная выпуклость и негладкость совместимы только на ограниченной области, если все субградиенты глобально ограничены: на всей $\mathbb{R}^d$ сильная выпуклость заставляет нормы субградиентов расти вдали от минимума. Поэтому предпосылка $\|g_t\|\leq G$ относится к траектории или ограниченному множеству.

Шаг Поляка

Если известно точное оптимальное значение $f^*$ , применяется шаг Поляка

$\alpha_t=\gamma\frac{f(x_t)-f^*}{\|g_t\|_2^2},\qquad 0<\gamma<2,$

при $g_t\ne0$ . Тогда

$\|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}.$

Правило не требует заранее знать $R$ или $G$ и автоматически уменьшает шаг около оптимума. Завышенная целевая оценка вместо $f^*$ может привести к преждевременной остановке, заниженная — к ненулевым шагам у решения. При условии острой ошибки $f(x)-f^*\geq\kappa\operatorname{dist}(x,X^*)$ и локально ограниченных субградиентах геометрически убывающие или поликовские шаги могут давать линейную сходимость; это дополнительная структурная гарантия, не следствие одной лишь сильной выпуклости^[1].

Стохастический субградиентный метод

Пусть $F(x,\xi)$ — случайная выпуклая функция и

$f(x)=\mathbb E_{\xi}[F(x,\xi)].$

Stochastic subgradient descent использует

$x_{t+1}=\Pi_X(x_t-\alpha_t G_t),$

где относительно истории $\mathcal F_{t-1}$ условное математическое ожидание удовлетворяет условиям

$\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.$

При выпуклости $f$ , существовании $x^*$ и $\|x_1-x^*\|_2\leq R$ выполняется

$\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}.$

Настроенный постоянный шаг снова даёт $RG/\sqrt T$ по математическому ожиданию. Для $\mu$ -сильно выпуклой цели убывающие шаги и взвешенное усреднение дают порядок $O(G^2/(\mu T))$ ^[1]. Это утверждение требует условной несмещённости и ограничения второго момента полной двойственной нормы; конечной дисперсии отдельных координат недостаточно. Оценки с высокой вероятностью дополнительно требуют ограниченности или хвостовых условий и мартингального анализа^[1].

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

Выбор субградиента

Правила исчисления

Для суммы выпуклых функций при стандартном условии регулярности

$\partial(f+h)(x)=\partial f(x)+\partial h(x).$

Для максимума конечного числа выпуклых функций

$f(x)=\max_{1\leq i\leq m}f_i(x)$

и активного множества $I(x)=\{i:f_i(x)=f(x)\}$

$\partial f(x)=\operatorname{conv}\bigcup_{i\in I(x)}\partial f_i(x).$

Здесь $\operatorname{conv}$ обозначает выпуклую оболочку.

Типичные одномерные примеры:

для $|z|$ субградиент равен $\operatorname{sign}(z)$ при $z\ne0$ и принадлежит $[-1,1]$ при $z=0$ ;
для hinge loss $\ell(z)=\max(0,1-z)$ субградиент равен $-1$ при $z<1$ , $0$ при $z>1$ и принадлежит $[-1,0]$ при $z=1$ ;
для $\|x\|_1$ компонента субградиента равна знаку ненулевой координаты и может быть любой в $[-1,1]$ в нуле.

Практический выбор

Теория допускает любой корректный и ограниченный субградиент, но траектории различаются. В точке с несколькими активными кусками можно выбрать субградиент одного куска, выпуклую комбинацию или элемент минимальной нормы. Последний часто уменьшает квадрат ошибки $\alpha_t^2\|g_t\|^2$ , однако его вычисление само может требовать решения квадратичной задачи. Нулевой субградиент следует выбирать, когда он доступен и подтверждает оптимальность неограниченной выпуклой задачи.

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

Правила шага

Правило	Требуемая информация	Гарантия и замечание
$\alpha=R/(G\sqrt T)$	Горизонт $T$ , оценки $R$ и $G$	Оптимальный порядок $O(RG/\sqrt T)$ для усреднения в выпуклом липшицевом случае
$\alpha_t=c/\sqrt t$	Масштаб $c$	Удобно без известного горизонта; наивное взвешивание может дать лишний логарифм
$\alpha_t=c/t$	Сильная выпуклость и настройка масштаба	Порядок $O(1/T)$ с надлежащими весами; слишком быстро для общей лишь выпуклой задачи
Шаг Поляка	Точное $f^*$ и значение $f(x_t)$	Адаптивен к текущему разрыву; чувствителен к ошибке в целевом значении
Постоянный шаг	Только масштаб субградиента	Быстро входит в окрестность, но оставляет ненулевой уровень ошибки
AdaGrad и диагональные адаптивные шаги	Накопленные квадраты координат субградиентов	Подстраиваются под разреженность и анизотропию данных; гарантия относится к изменяющейся геометрии, а не к произвольному покоординатному клиппингу^[1]

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

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

Градиентный спуск

Если $f$ дифференцируема, субградиент единственен. Однако использование только общей липшицевости функции сохраняет медленную оценку $O(T^{-1/2})$ . Более быстрая оценка градиентного спуска $O(T^{-1})$ требует $L$ -липшицевости градиента, а линейная сходимость — одновременно гладкости и сильной выпуклости. Негладкая сильно выпуклая функция обычно допускает лишь $O(T^{-1})$ , а не геометрический темп для базового субградиентного метода.

Проекционный субградиентный метод

Projected subgradient descent — не отдельный тип оракула, а базовое обновление с явным допустимым множеством. Проекция обеспечивает допустимость и не увеличивает расстояние до решения. Если $\Pi_X$ дорога, одна «простая» итерация фактически содержит отдельную оптимизационную задачу. Неевклидова прокс-проекция приводит к зеркальному спуску.

Проксимальные методы

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

$\min_x\{F(x)=h(x)+r(x)\},$

где $h$ выпукла и $L$ -гладка, а проксимальный оператор $r$ вычислим, Проксимальный градиентный метод выполняет

$x_{t+1}=\operatorname{prox}_{\alpha r}(x_t-\alpha\nabla h(x_t)),$

$\operatorname{prox}_{\alpha r}(z)=\operatorname{arg\,min}_x\left\{r(x)+\frac{1}{2\alpha}\|x-z\|_2^2\right\}.$

Это не субградиентный шаг для всей $F$ : негладкий член обрабатывается точно внутри проксимальной подзадачи. При $\alpha\leq1/L$ метод имеет порядок $O(1/T)$ , а ускоренный вариант — $O(1/T^2)$ . Для $r(x)=\lambda\|x\|_1$ soft-thresholding создаёт точные нули, тогда как обычный субградиентный шаг обычно колеблется около нуля^[1].

Bundle methods

Bundle methods сохраняют несколько опорных плоскостей

$m_t(x)=\max_{i\in B_t}\{f(x_i)+\langle g_i,x-x_i\rangle\}$

и минимизируют стабилизированную кусочно-линейную модель. Они используют больше памяти и решают более дорогую подзадачу, но повторно используют информацию о прошлых изломах, различают серьёзные и холостые шаги и обычно устойчивее к масштабу. Современный анализ проксимального bundle method показывает адаптацию к гладкости и условиям роста и оптимальные темпы при подходящих непостоянных параметрах^[1]. Bundle method не является «субградиентным методом с памятью» в смысле одной и той же итерации: его модель и критерий принятия шага принципиально иные.

Сравнение

Метод	Предпосылка о цели	Ограничения	Стоимость итерации	Память	Типичная гарантия
Субградиентный спуск	Выпуклость и ограниченные субградиенты	Без ограничений	Один оракул и векторное сложение, обычно $O(d)$	$O(d)$	$O(T^{-1/2})$ ; $O(T^{-1})$ при сильной выпуклости и правильном усреднении
Projected subgradient descent	То же	Замкнутое выпуклое $X$	Оракул плюс проекция на $X$	$O(d)$ без состояния проектора	Те же порядки; константа зависит от расстояния в допустимом множестве
Градиентный спуск	Выпуклость и $L$ -гладкость	Обычно без ограничений или с проекцией	Градиент и простой шаг	$O(d)$	$O(T^{-1})$ ; линейно при сильной выпуклости
Proximal gradient	$h$ гладка, $r$ проксимально проста	Через prox или отдельную проекцию	Градиент плюс prox	$O(d)$	$O(T^{-1})$ , ускоренно $O(T^{-2})$ ; линейно при дополнительных условиях
Bundle method	Выпуклая негладкая цель и оракул значений с субградиентами	Встраиваются в модель или подзадачу	Решение стабилизированной QP или родственной задачи	$O(md)$ для bundle размера $m$ , без учёта факторизаций	Сохраняет оракульные оценки базового класса; лучшие практические и адаптивные гарантии при дополнительной структуре

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

Негладкие функции потерь

Субградиентный оракул естественен для абсолютной ошибки, pinball loss, hinge loss и максимумов потерь. Для линейной модели $s_i=y_i\langle w,x_i\rangle$ и hinge loss

$\ell_i(w)=\max(0,1-s_i)$

можно взять

$g_i(w)=\begin{cases}-y_i x_i,&s_i<1,\\0,&s_i>1,\end{cases}$

а при $s_i=1$ — любую точку отрезка между этими векторами. Стохастический выбор примера даёт дешёвое обновление линейного SVM. Алгоритм Pegasos сочетает такой шаг с регуляризацией и проекцией и для регуляризованной primal-задачи SVM имеет сложность, не зависящую линейно от числа обучающих примеров^[1].

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

В задаче регуляризованного эмпирического риска

$\min_w\frac1n\sum_{i=1}^n\ell_i(w)+\lambda R(w)$

субградиент суммы позволяет обрабатывать негладкие $\ell_i$ и $R$ единым оракулом. Это полезно, если prox для $R$ неизвестен или слишком дорог. Если же $R=\|w\|_1$ , групповая норма или индикатор простого множества, проксимальный или зеркальный метод обычно предпочтительнее: он использует структуру регуляризатора, сохраняет разреженность и допускает более быстрый темп при гладкой части потерь.

Для задачи с $\ell_2$ -регуляризацией сильная выпуклость оправдывает шаг порядка $1/t$ . Для нестрого выпуклой линейной модели нельзя использовать эту оценку только потому, что функция потерь выпукла.

Крупномасштабное и онлайн-обучение

Один субградиент примера или мини-пакета стоит существенно дешевле полного прохода по данным. В онлайн-обучении то же одношаговое неравенство оценивает regret

$\operatorname{Regret}_T(u)=\sum_{t=1}^T\bigl(f_t(x_t)-f_t(u)\bigr).$

При выпуклых потерях, диаметре области $R$ и субградиентах нормы не более $G$ настроенный шаг даёт $\operatorname{Regret}_T(u)\leq RG\sqrt T$ . Деление на $T$ и online-to-batch conversion возвращает статистическую оценку порядка $1/\sqrt T$ . AdaGrad улучшает зависимость от координатной геометрии для разреженных признаков, но не меняет худший порядок без дополнительной структуры.

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

В распределённой оптимизации для суммы локальных целей

$f(x)=\sum_{i=1}^m f_i(x)$

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

Невыпуклые модели

В глубоких сетях с ReLU автоматическое дифференцирование выбирает одну из допустимых производных на изломах, и процедура внешне похожа на stochastic subgradient descent. Однако функция параметров невыпукла, субградиент в смысле выпуклого анализа неприменим, а приведённые выше оценки разрыва до глобального оптимума неверны. Для локально липшицевых слабовыпуклых функций современные результаты измеряют стационарность через градиент оболочки Моро; стохастический субградиентный метод достигает характерного порядка $O(T^{-1/4})$ по норме такого градиента при ограниченном втором моменте стохастических субградиентов и надлежащем случайном выборе выходной итерации^[1]. Для tame-функций установлена почти наверное сходимость предельных точек к критическому множеству при роббинс-монровских шагах и дополнительных геометрических предпосылках^[1]. Это современные невыпуклые обобщения, а не классическая выпуклая теория.

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

Ожидание монотонного спуска. Значение цели может возрастать даже при корректном субградиенте; контролируется лучшая или усреднённая точка.
Слишком большой постоянный шаг. Метод остаётся в широкой окрестности решения и может осциллировать через излом.
Слишком быстрое убывание. Если сумма шагов конечна, траектория может не дойти до оптимума; правило $1/t$ без сильной выпуклости часто преждевременно замораживает обучение.
Неверный субградиент на границе кусков. Производная неактивной ветви максимума или неверный знак у hinge loss нарушают опорное неравенство.
Игнорирование масштаба. Необработанные признаки делают $G$ большим и анизотропным; нормализация, зеркальная геометрия или AdaGrad могут изменить константы на порядки.
Необоснованная несмещённость. Субградиент случайного слагаемого не всегда можно переставить с математическим ожиданием; условия интегрируемости и правила субдифференцирования ожидания должны быть проверены.
Неправильный выход. Гарантия для $\bar x_T$ не переносится автоматически на $x_T$ ; усреднение параметров может быть нежелательно для структурно разреженного решения.
Смешение с proximal gradient. Обработка $\ell_1$ -штрафа его субградиентом не эквивалентна soft-thresholding и обычно не создаёт точных нулей.
Скрытая стоимость проекции. Для сложного $X$ проекционная подзадача может доминировать над вычислением субградиента.
Перенос выпуклой теории на нейронные сети. Выбор производной ReLU библиотекой не делает глобальную цель выпуклой.

Субградиентный метод практически предпочтителен, когда требуется очень дешёвая итерация, доступен только оракул негладкой функции, точность умеренна, размерность или поток данных исключают хранение моделей, а prox или bundle-подзадача дороже нескольких дополнительных проходов. Для высокой точности, доступной составной структуры или дорогого оракула обычно выгоднее проксимальные, сглаженные, cutting-plane или bundle methods.

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

К классическому ядру относятся субдифференциал выпуклой функции, проекционное обновление, оценки $O(T^{-1/2})$ , роббинс-монровские условия на шаги и правило Поляка^[1]. Стохастическая аппроксимация, распределённые схемы, AdaGrad и оптимальные правила усреднения развивают эту основу, сохраняя выпуклую постановку.

К более новым направлениям относятся точный анализ последней итерации, робастные методы при тяжёлых хвостах, слабовыпуклые и стратифицированные невыпуклые функции, а также адаптивные bundle methods. Их гарантии используют разные критерии качества — разрыв по функции, regret, расстояние до решения или норму градиента оболочки Моро — и потому не должны сравниваться только по степени $T$ . Например, хвостовые оценки для негладкого stochastic mirror descent при шуме тяжелее субгауссовского требуют явных моментных предпосылок и иной концентрационной техники^[1].

Примечания

Литература

Polyak B. T. Minimization of Unsmooth Functionals // USSR Computational Mathematics and Mathematical Physics. — 1969. — Т. 9. — № 3. — С. 14—29.
Rockafellar R. T. Convex Analysis. — Princeton University Press, 1970.
Nemirovski A. S., Yudin D. B. Problem Complexity and Method Efficiency in Optimization. — Wiley, 1983.
Shor N. Z. Minimization Methods for Non-Differentiable Functions. — Springer, 1985.
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.
Duchi J., Hazan E., Singer Y. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization // Journal of Machine Learning Research. — 2011. — Т. 12. — С. 2121—2159.
Bertsekas D. P. Convex Optimization Algorithms. — Athena Scientific, 2015.
Bubeck S. Convex Optimization: Algorithms and Complexity // Foundations and Trends in Machine Learning. — 2015. — Т. 8. — № 3—4. — С. 231—357.
Davis D., Drusvyatskiy D., Kakade S., Lee J. D. Stochastic Subgradient Method Converges on Tame Functions // Foundations of Computational Mathematics. — 2020. — Т. 20. — С. 119—154.
Díaz M., Grimmer B. Optimal Convergence Rates for the Proximal Bundle Method // SIAM Journal on Optimization. — 2023. — Т. 33. — № 2. — С. 424—454.
Eldowa K., Paudice A. General Tail Bounds for Non-Smooth Stochastic Mirror Descent // Proceedings of Machine Learning Research: AISTATS. — 2024. — Т. 238.

Источник — «http://poligon.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) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 20:00, 14 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Метод зеркального спуска (оптимизация)]]}}
+{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 14:00, 15 июля 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>E</tex> — конечномерное вещественное [[Линейное пространство|линейное пространство]], <tex>E^*</tex> — его [[Двойственное пространство|двойственное пространство]], <tex>X\subset E</tex> — непустое замкнутое [[Выпуклое множество|выпуклое множество]]. Рассматривается задача
+Пусть <tex>X\subseteq\mathbb{R}^d</tex> — непустое замкнутое выпуклое множество, а <tex>f:X\to\mathbb{R}\cup\{+\infty\}</tex> — собственная замкнутая выпуклая функция. Рассматривается задача
-:: <tex>\min_{x\in X} f(x),</tex>
+:: <tex>f^*=\min_{x\in X} f(x),\qquad X^*=\operatorname{arg\,min}_{x\in X}f(x)\ne\emptyset.</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>g\in\mathbb{R}^d</tex> называется '''субградиентом''' <tex>f</tex> в точке <tex>x\in\operatorname{dom}f</tex>, если для любого <tex>y</tex>
-:: <tex>f(x)=\mathbb{E}_{\xi}[F(x,\xi)]</tex>
+:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle.</tex>
-используется случайная оценка <tex>G_t=G(x_t,\xi_t)</tex>, для которой обычно предполагают условную несмещённость
+Множество всех таких векторов обозначается <tex>\partial f(x)</tex> и называется [[Субдифференциал|субдифференциалом]] Фенхеля — Моро. Для выпуклой дифференцируемой функции <tex>\partial f(x)=\{\nabla f(x)\}</tex>; тем самым субградиентный метод продолжает [[Градиентный спуск|градиентный спуск]] на негладкий случай. Условие оптимальности неограниченной задачи имеет вид
-:: <tex>\mathbb{E}[G_t\mid\mathcal{F}_{t-1}]\in\partial f(x_t).</tex>
+:: <tex>0\in\partial f(x^*).</tex>
-Здесь <tex>\mathcal{F}_{t-1}</tex> — информация, накопленная до построения <tex>G_t</tex>.
+При ограничении <tex>x\in X</tex> оно заменяется включением
-=== Норма и двойственная норма ===
+:: <tex>0\in\partial f(x^*)+N_X(x^*),</tex>
-На <tex>E</tex> фиксируется норма <tex>\|\cdot\|</tex>. Двойственная норма на <tex>E^*</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>\|z\|_* = \sup_{\|x\|\leq 1}\langle z,x\rangle.</tex>
+=== Геометрическая интуиция ===
-Обобщённое неравенство Гёльдера имеет вид
+Неравенство субградиента задаёт опорную аффинную функцию, лежащую не выше графика <tex>f</tex>. Полупространство
-:: <tex>\langle z,x\rangle\leq\|z\|_*\,\|x\|.</tex>
+:: <tex>\{y:\langle g,y-x\rangle\leq0\}</tex>
-Именно пара норм, а не выбранные координаты, определяет константу Липшица функции и масштаб ошибки. Например, на симплексе естественна норма <tex>\|\cdot\|_1</tex>, а субградиенты измеряются в <tex>\|\cdot\|_\infty</tex>. Замена этой пары на евклидову может внести лишний множитель порядка <tex>\sqrt d</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>\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>\|\cdot\|</tex> [[Двойственная норма|двойственная норма]] определяется как
-:: <tex>D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.</tex>
+:: <tex>\|g\|_*=\sup_{\|u\|\leq1}\langle g,u\rangle.</tex>
-Она неотрицательна, но, вообще говоря, несимметрична и не удовлетворяет неравенству треугольника. Поэтому <tex>D_\psi</tex> — не метрика. Порядок аргументов в формулах существенен.
+[[Неравенство Гёльдера]]
-Для анализа базового метода обычно предполагается, что <tex>\psi</tex> является <tex>\sigma</tex>-сильно выпуклой относительно <tex>\|\cdot\|</tex>:
+:: <tex>\langle g,u\rangle\leq\|g\|_*\|u\|</tex>
-:: <tex>D_\psi(x,y)\geq\frac{\sigma}{2}\|x-y\|^2.</tex>
+связывает размер области в прямой норме с размером субградиентов в двойственной. Если <tex>f</tex> выпукла и <tex>G</tex>-липшицева на открытом множестве относительно <tex>\|\cdot\|</tex>, то <tex>\|g\|_*\leq G</tex> для всех субградиентов во внутренних точках; верно и обратное при соответствующих условиях на область.
-Это неравенство предполагается для всех допустимых <tex>x</tex> и <tex>y</tex>.
+В [[Евклидово пространство|евклидовом пространстве]] градиент отождествляет линейный функционал с вектором, поэтому шаг <tex>x-\alpha g</tex> естественен. Для общей нормы направление [[Метод наискорейшего спуска|наискорейшего линейного спуска]] задаётся отображением
-Если <tex>\psi</tex> — [[Функция Лежандра|функция Лежандра]], то отображение <tex>\nabla\psi</tex> переводит внутренность прямой области в [[Двойственное пространство|двойственное пространство]], а обратное отображение задаётся градиентом [[Преобразование Фенхеля — Лежандра|сопряжённой функции Фенхеля]]:
+:: <tex>v(g)\in\operatorname{arg\,min}_{v}\left\{\langle g,v\rangle+\frac12\|v\|^2\right\},\qquad \|v(g)\|=\|g\|_*.</tex>
-:: <tex>(\nabla\psi)^{-1}=\nabla\psi^*.</tex>
+Если квадратичная стабилизация заменяется сильно выпуклым потенциалом и [[Дивергенция Брэгмана|дивергенцией Брэгмана]], получается [[Метод зеркального спуска|зеркальный спуск]]. Следовательно, упоминание произвольной нормы в оценке не означает, что евклидово обновление автоматически стало неевклидовым: должны быть согласованы норма, двойственная норма и геометрия проекции.
-=== Геометрическая интуиция ===
+Более точно, пусть <tex>\psi</tex> является <tex>\sigma</tex>-сильно выпуклым потенциалом относительно <tex>\|\cdot\|</tex>, а
-Обычный градиент <tex>g_t</tex> — ковектор, то есть элемент <tex>E^*</tex>. Вычитание его из точки <tex>x_t\in E</tex> имеет инвариантный смысл только после выбора отождествления прямого и двойственного пространств. Евклидово скалярное произведение делает такое отождествление незаметным. Зеркальный спуск выполняет операцию явно:
+:: <tex>D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.</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>\psi</tex>: локально матрица <tex>\nabla^2\psi(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>x_{t+1}-x_t\approx-\eta_t[\nabla^2\psi(x_t)]^{-1}g_t.</tex>
+при <tex>\|g_t\|_*\leq G</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</tex> членов показывает, что минимизируется линейная модель <tex>f</tex> в <tex>x_t</tex> плюс штраф за удаление от текущей точки в выбранной геометрии.
+Выбираются <tex>x_1\in X</tex>, положительные шаги <tex>\alpha_t</tex> и субградиенты <tex>g_t\in\partial f(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>\psi</tex>, начальная точка <tex>x_1\in\mathrm{ri}\,X</tex>, шаги <tex>\eta_1,\ldots,\eta_T</tex>.
+'''Вход:''' множество <tex>X</tex>, точка <tex>x_1\in X</tex>, число итераций <tex>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>x_{t+1}\in\operatorname{arg\,min}_{x\in X}\{\eta_t\langle g_t,x\rangle+D_\psi(x,x_t)\}</tex>;
+## выбрать <tex>\alpha_t>0</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>\bar x_T</tex>, а не к последней итерации. Замена усреднённой точки последней без дополнительной теории — распространённая ошибка.
+Для чисто оракульной задачи значение лучшей точки <tex>\operatorname{arg\,min}_{t\leq T}f(x_t)</tex> требует вычислять <tex>f(x_t)</tex>. В стохастической задаче выбор по шумной эмпирической потере вносит смещение, поэтому теоремы обычно относятся к усреднению или к специально построенной последней итерации.
 === Основное одношаговое неравенство ===
-Оптимальность зеркального шага и [[Дивергенция Брэгмана#Трёхточечное тождество|трёхточечное тождество Брэгмана]] дают для любого <tex>u\in X</tex>
+Неэкспансивность проекции и неравенство субградиента дают для любого <tex>x^*\in X^*</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>\|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>\psi</tex> <tex>\sigma</tex>-сильно выпукла, то после переноса <tex>x_t-x_{t+1}</tex>, применения неравенства Гёльдера и неравенства Юнга получается фундаментальная оценка
+Это центральное соотношение: полезный член линеен по <tex>\alpha_t</tex>, а накопленная ошибка шага квадратична. В общем случае значения <tex>f(x_t)</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>
-Телескопирование [[Дивергенция Брэгмана|дивергенций Брэгмана]] в этой формуле является основой большинства классических доказательств.
 == Оценки сходимости ==
@@ Строка 102: / Строка 104: @@
 === Выпуклая липшицева задача ===
-'''Теорема.''' Пусть <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</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(\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>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>D_\psi(x^*,x_1)\leq R_\psi^2</tex> и взять постоянный шаг
+Та же правая часть ограничивает <tex>\min_{1\leq t\leq T}f(x_t)-f^*</tex>. При известном горизонте выбор
-:: <tex>\eta=\frac{R_\psi\sqrt{2\sigma}}{G\sqrt T},</tex>
+:: <tex>\alpha_t=\frac{R}{G\sqrt T}</tex>
-то
+даёт
-:: <tex>f(\bar x_T)-f(x^*)\leq G R_\psi\sqrt{\frac{2}{\sigma T}}.</tex>
+:: <tex>f(\bar x_T)-f^*\leq\frac{RG}{\sqrt T}.</tex>
-Это оптимальный по порядку темп <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>\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>\alpha_t=c/\sqrt t</tex> даёт для обычного взвешенного среднего оценку порядка <tex>O(\log T/\sqrt T)</tex>; удвоение горизонта по эпохам или более аккуратное усреднение устраняет лишний логарифм. Условия
-Пусть дополнительно <tex>f</tex> является <tex>\mu</tex>-сильно выпуклой относительно той же нормы:
+:: <tex>\sum_{t=1}^{\infty}\alpha_t=\infty,\qquad \sum_{t=1}^{\infty}\alpha_t^2<\infty</tex>
-:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle+\frac{\mu}{2}\|y-x\|^2,\quad g\in\partial f(x).</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>\|g_t\|_*\leq G</tex>, <tex>\sigma</tex>-сильной выпуклости <tex>\psi</tex> и шагах <tex>\eta_t=\sigma/(\mu t)</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>\alpha_t=\alpha</tex> предыдущая оценка принимает вид
-Логарифм не является информационно-теоретически необходимым. Полиномиально взвешенное усреднение, суффиксное усреднение или перезапуски дают при тех же ограничениях порядок <tex>O(G^2/(\mu T))</tex>; конкретная константа зависит от схемы весов и нумерации шагов. Поэтому утверждение оценки <tex>O(T^{-1})</tex> без описания усреднения недостаточно.
+:: <tex>f(\bar x_T)-f^*\leq\frac{R^2}{2\alpha T}+\frac{\alpha G^2}{2}.</tex>
-=== Гладкость относительно зеркального потенциала ===
+Итерационный член исчезает, но остаётся окрестность оптимума радиуса по функции порядка <tex>\alpha G^2</tex>. Поэтому постоянный learning rate без рестартов не обеспечивает произвольно точной сходимости для общей негладкой выпуклой задачи.
-Классический анализ гладкого градиентного спуска предполагает липшицевость градиента в норме. Более общее условие '''относительной гладкости''' требует, чтобы для некоторого <tex>L>0</tex>
+=== Сильно выпуклая задача ===
-:: <tex>f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+L D_\psi(y,x).</tex>
+Пусть <tex>f</tex> <tex>\mu</tex>-[[Сильно выпуклая функция|сильно выпукла]] относительно евклидовой нормы:
-Для дважды дифференцируемых функций это соответствует неравенству кривизн <tex>\nabla^2 f(x)\leq L\nabla^2\psi(x)</tex> в смысле порядка Лёвнера. При выпуклости <tex>f</tex>, относительной <tex>L</tex>-гладкости, существовании решения и точном решении зеркальной подзадачи шаг
+:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle+\frac\mu2\|y-x\|_2^2</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>g\in\partial f(x)</tex>. Пусть также <tex>\|g_t\|_2\leq G</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>\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>\widetilde x_T=\frac{2}{T(T+1)}\sum_{t=1}^T t x_t</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>f(\widetilde x_T)-f^*\leq\frac{2G^2}{\mu(T+1)}.</tex>
-:: <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>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>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>\mathbb{R}^d</tex> сильная выпуклость заставляет нормы субградиентов расти вдали от минимума. Поэтому предпосылка <tex>\|g_t\|\leq G</tex> относится к траектории или ограниченному множеству.
-Оценки с высокой вероятностью требуют дополнительных хвостовых предпосылок либо робастизации. При субгауссовском шуме применимы мартингальные концентрационные неравенства. При наличии лишь конечного момента порядка <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>E=\mathbb{R}^d</tex>, <tex>\psi(x)=\frac12\|x\|_2^2</tex>. Тогда
+при <tex>g_t\ne0</tex>. Тогда
-:: <tex>D_\psi(x,y)=\frac12\|x-y\|_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>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>X=\mathbb{R}^d</tex>, это обычный [[Градиентный спуск|градиентный]] или субградиентный спуск. Тем самым зеркальный спуск не является «градиентным спуском после нелинейной замены переменных» в общем случае, но строго содержит евклидов метод как частный случай.
+Пусть <tex>F(x,\xi)</tex> — случайная выпуклая функция и
-=== Экспоненциальное обновление на симплексе ===
+:: <tex>f(x)=\mathbb E_{\xi}[F(x,\xi)].</tex>
-Пусть
+'''Stochastic subgradient descent''' использует
-:: <tex>\Delta_d=\{x\in\mathbb{R}_+^d:\sum_{i=1}^d x_i=1\}</tex>
+:: <tex>x_{t+1}=\Pi_X(x_t-\alpha_t G_t),</tex>
-и выбран отрицательный энтропийный потенциал
+где относительно истории <tex>\mathcal F_{t-1}</tex> [[Условное математическое ожидание|условное математическое ожидание]] удовлетворяет условиям
-:: <tex>\psi(x)=\sum_{i=1}^d x_i\ln x_i.</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>D_\psi(x,y)=\sum_i x_i\ln(x_i/y_i)</tex> — [[Расстояние Кульбака — Лейблера|дивергенция Кульбака — Лейблера]], являющаяся важным частным случаем [[Дивергенция Брэгмана|дивергенции Брэгмана]]. Потенциал <tex>1</tex>-сильно выпукл относительно <tex>\|\cdot\|_1</tex> на симплексе вследствие [[Неравенство Пинскера|неравенства Пинскера]]. Решение зеркальной подзадачи имеет закрытую форму
+При выпуклости <tex>f</tex>, существовании <tex>x^*</tex> и <tex>\|x_1-x^*\|_2\leq R</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>\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>
-Это [[Экспоненциальное взвешивание|экспоненциальное обновление]], также лежащее в основе алгоритмов multiplicative weights и Hedge. Если <tex>x_{1,i}=1/d</tex>, <tex>\|g_t\|_\infty\leq G</tex>, то для любого <tex>u\in\Delta_d</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>.
-:: <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>\mathbb{R}^d</tex>, <tex>\|\cdot\|_2</tex>
+| <tex>\alpha_t=c/\sqrt t</tex>
-| <tex>\psi(x)=\frac12\|x\|_2^2</tex>
+| Масштаб <tex>c</tex>
-| Квадрат евклидова расстояния; обычная проекция
+| Удобно без известного горизонта; наивное взвешивание может дать лишний логарифм
 |-
-| Симплекс, <tex>\|\cdot\|_1</tex>
+| <tex>\alpha_t=c/t</tex>
-| <tex>\psi(x)=\sum_i x_i\ln x_i</tex>
+| Сильная выпуклость и настройка масштаба
-| KL-дивергенция; мультипликативное обновление за <tex>O(d)</tex>
+| Порядок <tex>O(1/T)</tex> с надлежащими весами; слишком быстро для общей лишь выпуклой задачи
 |-
-| Шар <tex>\ell_p</tex>, <tex>1<p\leq2</tex>
+| Шаг Поляка
-| Масштабированный квадрат <tex>\|x\|_p^2</tex>
+| Точное <tex>f^*</tex> и значение <tex>f(x_t)</tex>
-| Согласование с разреженной геометрией; двойственная норма <tex>\ell_q</tex>, где <tex>1/p+1/q=1</tex>
+| Адаптивен к текущему разрыву; чувствителен к ошибке в целевом значении
 |-
-| Положительный ортант
+| Постоянный шаг
-| Логарифмический барьер <tex>\psi(x)=-\sum_i\ln x_i</tex>
+| Только масштаб субградиента
-| Барьерная брэгмановская геометрия; сохранение строгой положительности
+| Быстро входит в окрестность, но оставляет ненулевой уровень ошибки
 |-
-| Положительно полуопределённые матрицы плотности <tex>X\geq0</tex>, <tex>\mathrm{tr}\,X=1</tex>
+| AdaGrad и диагональные адаптивные шаги
-| Энтропия фон Неймана <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>p=1+O(1/\ln d)</tex> часто используется как гладкая аппроксимация геометрии <tex>\ell_1</tex>. Правильный потенциал одновременно должен давать малый [[Дивергенция Брэгмана#Брэгмановский радиус|брэгмановский радиус]], достаточную [[Сильно выпуклая функция|сильную выпуклость]] и дешёвую прокс-операцию.
+[[Линейный поиск]], основанный на локальном убывании, ненадёжен: допустимое направление <tex>-g_t</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>
+=== Проксимальные методы ===
-В отличие от [[Ортогональная проекция|ортогональной проекции]], эта операция обычно несимметрична и зависит от [[Дивергенция Брэгмана#Несимметричность|ориентации дивергенции Брэгмана]].
+Для [[Составная оптимизация|составной задачи]]
-=== Proximal mirror descent ===
+:: <tex>\min_x\{F(x)=h(x)+r(x)\},</tex>
-Для составной задачи
+где <tex>h</tex> выпукла и <tex>L</tex>-гладка, а проксимальный оператор <tex>r</tex> вычислим, [[Проксимальный градиентный метод]] выполняет
-:: <tex>\min_{x\in X}\{f(x)+r(x)\},</tex>
+:: <tex>x_{t+1}=\operatorname{prox}_{\alpha r}(x_t-\alpha\nabla h(x_t)),</tex>
-где <tex>r</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>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>
+Это не субградиентный шаг для всей <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>.
-Это не то же самое, что базовый MD, если <tex>r</tex> включена только через субградиент. Точное включение <tex>r</tex> часто сохраняет разреженность и улучшает константы. [[Проксимальный градиентный метод]] обычно означает евклидову схему для гладкой <tex>f</tex> и негладкой <tex>r</tex>; брэгмановский проксимальный градиент является её неевклидовым обобщением.
+=== Bundle methods ===
-=== Dual averaging ===
+[[Bundle method|Bundle methods]] сохраняют несколько опорных плоскостей
-Метод двойственного усреднения накапливает градиенты
+:: <tex>m_t(x)=\max_{i\in B_t}\{f(x_i)+\langle g_i,x-x_i\rangle\}</tex>
-:: <tex>s_t=\sum_{k=1}^t\alpha_k g_k</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>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>L</tex>-гладкой задачи
+| <tex>O(T^{-1/2})</tex>; <tex>O(T^{-1})</tex> при сильной выпуклости и правильном усреднении
 |-
-| Projected gradient descent
+| Projected subgradient descent
-| Евклидова; явное множество <tex>X</tex>
+| То же
-| Евклидова проекция; от закрытой формы до отдельной задачи оптимизации
+| Замкнутое выпуклое <tex>X</tex>
-| <tex>O(d)</tex>
+| Оракул плюс проекция на <tex>X</tex>
-| <tex>O(T^{-1/2})</tex> в негладком и <tex>O(T^{-1})</tex> в гладком случае при стандартных предпосылках
+| <tex>O(d)</tex> без состояния проектора
+| Те же порядки; константа зависит от расстояния в допустимом множестве
 |-
-| Mirror descent
+| Градиентный спуск
-| Произвольная норма и брэгмановская геометрия
+| Выпуклость и <tex>L</tex>-гладкость
-| Зеркальная прокс-операция; часто <tex>O(d)</tex> на симплексе, но может быть дорогой
+| Обычно без ограничений или с проекцией
+| Градиент и простой шаг
 | <tex>O(d)</tex>
-| <tex>O(T^{-1/2})</tex>; константа определяется <tex>D_\psi</tex> и двойственной нормой
+| <tex>O(T^{-1})</tex>; линейно при сильной выпуклости
 |-
 | Proximal gradient
-| Обычно евклидова; составная цель <tex>f+r</tex>
+| <tex>h</tex> гладка, <tex>r</tex> проксимально проста
-| Проксимальный оператор <tex>r</tex>
+| Через prox или отдельную проекцию
+| Градиент плюс prox
 | <tex>O(d)</tex>
-| <tex>O(T^{-1})</tex> при выпуклой гладкой <tex>f</tex>; ускорение даёт <tex>O(T^{-2})</tex>
+| <tex>O(T^{-1})</tex>, ускоренно <tex>O(T^{-2})</tex>; линейно при дополнительных условиях
 |-
-| Proximal mirror descent
+| Bundle method
-| Брэгмановская; составная цель и ограничения
+| Выпуклая негладкая цель и оракул значений с субградиентами
-| Совместная прокс-операция для <tex>r</tex> и <tex>D_\psi</tex>
+| Встраиваются в модель или подзадачу
-| <tex>O(d)</tex>
+| Решение стабилизированной QP или родственной задачи
-| Как у MD при ограниченных субградиентах; быстрее при относительной гладкости и дополнительных условиях
+| <tex>O(md)</tex> для bundle размера <tex>m</tex>, без учёта факторизаций
-|-
+| Сохраняет оракульные оценки базового класса; лучшие практические и адаптивные гарантии при дополнительной структуре
-| Dual averaging
-| Геометрия фиксированного регуляризатора
-| Минимизация накопленной линейной модели с регуляризатором
-| <tex>O(d)</tex> для суммы градиентов; хранить всю историю не требуется
-| <tex>O(T^{-1/2})</tex>; особенно удобно для меняющихся шагов и явной регуляризации
 |}
-Указанная память не включает состояние стохастического оракула, распределённой системы или адаптивного предобусловливателя. Сложность зеркальной подзадачи является частью алгоритма: теоретически подходящая геометрия бесполезна, если соответствующий prox нельзя вычислить достаточно точно и дёшево.
 == Применения в машинном обучении ==
-=== Вероятностный симплекс и смеси ===
+=== Негладкие функции потерь ===
-Энтропийный MD естественно поддерживает неотрицательность и единичную сумму без евклидовой сортирующей проекции. Это используется при обучении весов ансамбля, смесей экспертов, вероятностных распределений, тематических моделей, политик и матриц переходов. Мультипликативный шаг изменяет относительные, а не абсолютные веса: малая компонента получает изменение, пропорциональное её текущему масштабу.
+Субградиентный оракул естественен для [[Абсолютная ошибка|абсолютной ошибки]], [[Квантильная регрессия|pinball loss]], [[Кусочно-линейная функция потерь|hinge loss]] и максимумов потерь. Для [[Линейная модель|линейной модели]] <tex>s_i=y_i\langle w,x_i\rangle</tex> и hinge loss
-При оптимуме на границе симплекса энтропийные итерации, начатые во внутренности, остаются строго положительными. Они могут сходиться к граничной точке, но не создают точный ноль за конечное число шагов. Если точная разреженность обязательна, полезнее иной потенциал, явный проксимальный член или последующее пороговое преобразование с отдельным анализом.
+:: <tex>\ell_i(w)=\max(0,1-s_i)</tex>
-=== Онлайн-обучение ===
+можно взять
-В [[Онлайн-обучение|онлайн-выпуклой оптимизации]] на раунде <tex>t</tex> алгоритм выбирает <tex>x_t</tex>, затем наблюдает выпуклую потерю <tex>\ell_t</tex>. Статическое сожаление относительно <tex>u\in X</tex> равно
+:: <tex>g_i(w)=\begin{cases}-y_i x_i,&s_i<1,\\0,&s_i>1,\end{cases}</tex>
-:: <tex>\mathrm{Reg}_T(u)=\sum_{t=1}^T[\ell_t(x_t)-\ell_t(u)].</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>\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>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>\min_w\frac1n\sum_{i=1}^n\ell_i(w)+\lambda R(w)</tex>
-=== Линейные модели и разреженность ===
+субградиент суммы позволяет обрабатывать негладкие <tex>\ell_i</tex> и <tex>R</tex> единым оракулом. Это полезно, если prox для <tex>R</tex> неизвестен или слишком дорог. Если же <tex>R=\|w\|_1</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>.
+Для задачи с <tex>\ell_2</tex>-регуляризацией сильная выпуклость оправдывает шаг порядка <tex>1/t</tex>. Для нестрого выпуклой линейной модели нельзя использовать эту оценку только потому, что функция потерь выпукла.
-=== Стохастическая и распределённая оптимизация ===
+=== Крупномасштабное и онлайн-обучение ===
-В стохастическом обучении зеркальная геометрия меняет то, в какой норме контролируется шум. Это может уменьшить размерностную зависимость, но не устраняет дисперсию автоматически. Мини-батчи, усреднение итераций, уменьшение дисперсии, отсечение тяжёлых хвостов и адаптация шага являются отдельными механизмами.
+Один субградиент примера или [[Мини-пакет|мини-пакета]] стоит существенно дешевле полного прохода по данным. В [[Онлайн-обучение|онлайн-обучении]] то же одношаговое неравенство оценивает [[Regret|regret]]
-В распределённой задаче агенты сочетают локальные зеркальные шаги с консенсусом или отслеживанием градиента. Потенциал можно согласовать не только с локальными ограничениями, но и с геометрией согласования. Итоговая скорость зависит одновременно от брэгмановского радиуса, шума, числа локальных шагов и спектральных характеристик коммуникационного графа; локальная гарантия 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>\operatorname{Regret}_T(u)=\sum_{t=1}^T\bigl(f_t(x_t)-f_t(u)\bigr).</tex>
-== Выбор зеркального отображения ==
+При выпуклых потерях, диаметре области <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>\psi</tex> на <tex>c\psi</tex> эквивалентна соответствующему изменению <tex>\eta_t</tex>. Сравнивать потенциалы только по константе сильной выпуклости без учёта радиуса <tex>D_\psi</tex> некорректно; в оценке участвует их отношение.
+:: <tex>f(x)=\sum_{i=1}^m f_i(x)</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.''' Совпадение локальных метрических тензоров не доказывает совпадение конечных итераций.
-* '''Плохая численная реализация.''' Прямое вычисление экспонент вызывает переполнение и исчезновение малых весов; матричные зеркальные шаги могут терять положительную определённость из-за округления.
-Зеркальный спуск практически предпочтителен евклидовым методам, когда ограничения имеют простой неевклидов prox, [[Дивергенция Брэгмана#Брэгмановский радиус|брэгмановский радиус]] заметно меньше евклидова, а градиенты хорошо ограничены в соответствующей [[Двойственная норма|двойственной норме]]. Типичные примеры — большой симплекс, матричный симплекс, задачи с относительной гладкостью и высокоразмерные онлайн-задачи. Евклидов метод обычно предпочтительнее, если проекция проста, геометрия близка к изотропной, а вычисление зеркального отображения требует дорогой факторизации или внутренней оптимизации.
+В [[Глубокая нейронная сеть|глубоких сетях]] с [[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>. Это современные невыпуклые обобщения, а не классическая выпуклая теория.
-== Классические результаты и современные обобщения ==
+== Ограничения и типичные ошибки ==
-К классическому ядру относятся: метод Немировского—Юдина; интерпретация через [[Дивергенция Брэгмана|дивергенцию Брэгмана]] и негладкая оценка <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 библиотекой не делает глобальную цель выпуклой.
-Более новые направления не следует считать синонимами базового MD:
+Субградиентный метод практически предпочтителен, когда требуется очень дешёвая итерация, доступен только оракул негладкой функции, точность умеренна, размерность или поток данных исключают хранение моделей, а prox или bundle-подзадача дороже нескольких дополнительных проходов. Для высокой точности, доступной составной структуры или дорогого оракула обычно выгоднее проксимальные, сглаженные, cutting-plane или bundle methods.
-* '''Относительная гладкость''' заменяет глобальную липшицевость градиента сравнением кривизны цели и потенциала<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 и оптимальные правила усреднения развивают эту основу, сохраняя выпуклую постановку.
-Зеркальный спуск отделяет информацию первого порядка от способа измерения перемещений. Его универсальная итерация остаётся простой, но качество метода определяется согласованием трёх объектов: нормы и её двойственной нормы, брэгмановского потенциала и вычислимости зеркального prox. В евклидовой геометрии метод сводится к проекционному градиентному спуску; на симплексе — к экспоненциальному взвешиванию. Классическая теория даёт оптимальные порядки для негладкой выпуклой и стохастической оптимизации, а современные расширения охватывают относительную гладкость, тяжёлые хвосты, онлайн-адаптацию, распределённые и невыпуклые задачи. При переносе гарантий критически важно сохранять точные предпосылки: вид усреднения, ориентацию дивергенции, норму, моментные условия и точность решения прокс-подзадачи.
+К более новым направлениям относятся точный анализ последней итерации, робастные методы при тяжёлых хвостах, слабовыпуклые и стратифицированные невыпуклые функции, а также адаптивные 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>.
 == Примечания ==
@@ Строка 396: / Строка 401: @@
 == Литература ==
-* {{статья |автор=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}}
+* {{статья |автор=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}}
-* {{книга |автор=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}}
+* {{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://doi.org/10.1515/9781400873173 |издательство=Princeton University Press |год=1970 |язык=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}}
+* {{книга |автор=Nemirovski A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |издательство=Wiley |год=1983 |язык=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}}
+* {{книга |автор=Shor N. Z. |заглавие=Minimization Methods for Non-Differentiable Functions |ссылка=https://doi.org/10.1007/978-3-642-82118-9 |издательство=Springer |год=1985 |язык=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}}
+* {{статья |автор=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}}
-* {{статья |автор=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}}
+* {{статья |автор=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}}
 * {{статья |автор=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}}
-* {{статья |автор=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}}
+* {{статья |автор=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}}
-* {{статья |автор=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}}
+* {{статья |автор=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}}
-* {{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: @@
 [[Категория:Энциклопедия анализа данных]]
 [[Категория:Выпуклая оптимизация]]
-[[Категория:Онлайн-обучение]]
+[[Категория:Стохастическая оптимизация]]