Субградиентные методы (оптимизация)

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

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

Версия 11:12, 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://recognition.su/wiki/index.php?title=%D0%A1%D1%83%D0%B1%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%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]] 21:00, 14 июля 2026 (MSD)}}
+{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 14:00, 15 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Субградиентные методы (оптимизация)]]}}
 {{TOCright}}
-'''Субградиентные методы''' — семейство методов [[Выпуклая оптимизация|выпуклой]] и [[Негладкая оптимизация|негладкой оптимизации]], использующих вместо градиента произвольный [[Субградиент|субградиент]] целевой функции. Их основное достоинство состоит в минимальных требованиях к [[Оракул первого порядка|оракулу первого порядка]]: на каждой итерации достаточно получить значение функции и один субградиент. Платой за это служат медленная наихудшая сходимость, отсутствие монотонного убывания значений функции и высокая чувствительность к выбору шага.
+'''Субградиентные методы''' — семейство [[Методы первого порядка|методов первого порядка]] для минимизации [[Выпуклая функция|выпуклых]], возможно негладких функций. В точке излома вместо единственного градиента используется любой элемент [[Субдифференциал|субдифференциала]]. Простота итерации, малая память и возможность работать со стохастическим или распределённым [[Оракул первого порядка|оракулом]] делают эти методы базовыми для [[Выпуклая оптимизация|выпуклой оптимизации]], [[Негладкая оптимизация|негладкой оптимизации]] и [[Машинное обучение|машинного обучения]]. Цена универсальности — медленная в общем случае сходимость, отсутствие монотонного убывания целевой функции и высокая чувствительность к масштабу задачи и правилу шага.
-Классическая область применимости — выпуклые, но негладкие задачи большой размерности, в частности обучение [[Метод опорных векторов|метода опорных векторов]], минимизация функций с максимумами, двойственные задачи декомпозиции и распределённая оптимизация. Терминология требует осторожности: детерминированный субградиент, случайная несмещённая оценка градиента и обобщённый градиент невыпуклой функции — разные объекты.
 == Постановка задачи ==
-Пусть <tex>C\subseteq\mathbb R^d</tex> — непустое замкнутое выпуклое множество, а <tex>f:\mathbb R^d\to\mathbb R\cup\{+\infty\}</tex> — собственная замкнутая выпуклая функция. Рассматривается задача
+Пусть <tex>X\subseteq\mathbb{R}^d</tex> — непустое замкнутое выпуклое множество, а <tex>f:X\to\mathbb{R}\cup\{+\infty\}</tex> — собственная замкнутая выпуклая функция. Рассматривается задача
-:: <tex>\min_{x\in C} f(x),\qquad f^*=\inf_{x\in C}f(x),\qquad X^*={\rm argmin}_{x\in C}f(x).</tex>
-Если ограничения включены в функцию посредством индикатора <tex>I_C</tex>, задача записывается как безусловная минимизация <tex>f+I_C</tex>. Для количественных гарантий ниже явно предполагается, что <tex>X^*\ne\emptyset</tex>, а используемые субградиенты ограничены по норме.
-== Субградиент и субдифференциал ==
+:: <tex>f^*=\min_{x\in X} f(x),\qquad X^*=\operatorname{arg\,min}_{x\in X}f(x)\ne\emptyset.</tex>
-=== Определение ===
+Вектор <tex>g\in\mathbb{R}^d</tex> называется '''субградиентом''' <tex>f</tex> в точке <tex>x\in\operatorname{dom}f</tex>, если для любого <tex>y</tex>
-Вектор <tex>g\in\mathbb R^d</tex> называется '''субградиентом''' выпуклой функции <tex>f</tex> в точке <tex>x\in{\rm dom}\,f</tex>, если для всех <tex>y\in\mathbb R^d</tex>
 :: <tex>f(y)\geq f(x)+\langle g,y-x\rangle.</tex>
-Множество всех таких векторов называется '''[[Субдифференциал|субдифференциалом]]''':
-:: <tex>\partial f(x)=\left\{g\in\mathbb R^d\mid f(y)\geq f(x)+\langle g,y-x\rangle\quad\forall y\in\mathbb R^d\right\}.</tex>
-Вне [[Эффективная область определения|эффективной области определения]] полагают <tex>\partial f(x)=\emptyset</tex>. Это субдифференциал выпуклого анализа в смысле Моро—Рокафеллара.<ref name="rock">См. Rockafellar (1970), гл. 23—25.</ref>
-Если <tex>f</tex> дифференцируема в <tex>x</tex>, то <tex>\partial f(x)=\{\nabla f(x)\}</tex>. Обратное верно для выпуклой функции во внутренней точке области определения: одноэлементность субдифференциала эквивалентна дифференцируемости. Для собственной выпуклой функции субдифференциал непуст в каждой точке относительной внутренности <tex>{\rm ri}({\rm dom}\,f)</tex>, но на границе он может быть пуст.
+Множество всех таких векторов обозначается <tex>\partial f(x)</tex> и называется [[Субдифференциал|субдифференциалом]] Фенхеля — Моро. Для выпуклой дифференцируемой функции <tex>\partial f(x)=\{\nabla f(x)\}</tex>; тем самым субградиентный метод продолжает [[Градиентный спуск|градиентный спуск]] на негладкий случай. Условие оптимальности неограниченной задачи имеет вид
-=== Геометрический смысл ===
+:: <tex>0\in\partial f(x^*).</tex>
-Аффинная функция
+При ограничении <tex>x\in X</tex> оно заменяется включением
-:: <tex>y\mapsto f(x)+\langle g,y-x\rangle</tex>
-является глобальной опорной снизу плоскостью к графику <tex>f</tex>. Эквивалентно, гиперплоскость с нормалью <tex>(g,-1)</tex> поддерживает [[Эпиграф|эпиграф]] функции в точке <tex>(x,f(x))</tex>. В точке излома опорных плоскостей обычно несколько; их наклоны и образуют <tex>\partial f(x)</tex>.
-Существование такой глобальной опоры существенно связано с выпуклостью. Если на открытом выпуклом множестве для каждой точки <tex>x</tex> существует вектор <tex>g_x</tex>, удовлетворяющий субградиентному неравенству для всех точек множества, то <tex>f</tex> выпукла. Для произвольной невыпуклой функции касательная или локальная производная такого глобального неравенства, вообще говоря, не даёт.
+:: <tex>0\in\partial f(x^*)+N_X(x^*),</tex>
-=== Условие оптимальности и правила исчисления ===
+где <tex>N_X(x^*)</tex> — [[Нормальный конус|нормальный конус]] множества <tex>X</tex><ref name="Rockafellar">{{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://doi.org/10.1515/9781400873173 |издательство=Princeton University Press |год=1970 |язык=en}}</ref>.
-Для собственной выпуклой функции выполняется критерий Ферма
+=== Геометрическая интуиция ===
-:: <tex>x^*\in{\rm argmin}\,f\quad\Longleftrightarrow\quad 0\in\partial f(x^*).</tex>
-В задаче с ограничениями условие принимает вид
-:: <tex>0\in\partial f(x^*)+N_C(x^*),</tex>
-где <tex>N_C(x)</tex> — [[Нормальный конус|нормальный конус]]. При стандартном [[Условия регулярности|квалификационном условии]], например наличии общей точки относительных внутренностей областей определения, справедливо правило суммы
-:: <tex>\partial(f+h)(x)=\partial f(x)+\partial h(x).</tex>
-Для линейного отображения при соответствующем условии регулярности
-:: <tex>\partial(f\circ A)(x)=A^{\rm T}\partial f(Ax).</tex>
-Если <tex>f(x)=\max_{1\leq j\leq m} f_j(x)</tex>, где функции <tex>f_j</tex> выпуклы и непрерывны в рассматриваемой точке, то
-:: <tex>\partial f(x)={\rm conv}\,\bigcup_{j\in I(x)}\partial f_j(x),\qquad I(x)=\{j:f_j(x)=f(x)\}.</tex>
-Для дифференцируемых <tex>f_j</tex> это частный случай [[Теорема Данскина|теоремы Данскина]]: можно взять градиент любой активной функции или их выпуклую комбинацию.<ref>См. Danskin (1967).</ref>
-=== Элементарные примеры ===
+Неравенство субградиента задаёт опорную аффинную функцию, лежащую не выше графика <tex>f</tex>. Полупространство
-Для абсолютного значения
+:: <tex>\{y:\langle g,y-x\rangle\leq0\}</tex>
-:: <tex>\partial |t|=\left\{\begin{array}{ll}\{-1\},&t<0,\\ [-1,1],&t=0,\\ \{1\},&t>0.\end{array}\right.</tex>
-Для нормы <tex>\ell_2</tex>
-:: <tex>\partial\|x\|_2=\left\{\begin{array}{ll}\{x/\|x\|_2\},&x\ne0,\\ \{g\mid\|g\|_2\leq1\},&x=0.\end{array}\right.</tex>
-Для нормы <tex>\ell_1</tex> субдифференциал вычисляется покоординатно: при ненулевой координате получается её знак, при нулевой — любой элемент отрезка <tex>[-1,1]</tex>.
-== Детерминированный субградиентный метод ==
+содержит каждую точку <tex>y</tex>, для которой <tex>f(y)\leq f(x)</tex>. Поэтому направление <tex>-g</tex> отделяет текущую точку от области лучших значений. Однако, в отличие от градиента гладкой функции, <tex>-g</tex> не обязано быть направлением локального убывания: для <tex>f(x)=|x|</tex> в точке <tex>x=0</tex> допустим любой <tex>g\in[-1,1]</tex>, и выбор <tex>g\ne0</tex> уводит из минимума. Анализ метода основан не на лемме о гладком спуске, а на уменьшении расстояния до множества решений с точностью до квадрата шага.
-=== Алгоритм ===
+== Нормы и двойственные нормы ==
-Для задачи без явных ограничений базовая итерация имеет вид
+Для нормы <tex>\|\cdot\|</tex> [[Двойственная норма|двойственная норма]] определяется как
-:: <tex>x_{k+1}=x_k-\alpha_k g_k,\qquad g_k\in\partial f(x_k),\qquad \alpha_k>0.</tex>
-В отличие от [[Градиентный спуск|градиентного спуска]], направление <tex>-g_k</tex> может не быть направлением локального убывания: возле излома метод способен перескакивать через множество решений, а значения <tex>f(x_k)</tex> — возрастать. Анализ опирается не на лемму о гладкости, а на субградиентное неравенство.
-<pre>
+:: <tex>\|g\|_*=\sup_{\|u\|\leq1}\langle g,u\rangle.</tex>
-Вход: начальная точка x_1, число итераций T, правило шага
-для k = 1,...,T:
-    получить g_k из субдифференциала f в x_k
-    выбрать положительный шаг alpha_k
-    x_{k+1} := x_k - alpha_k g_k
-вернуть лучшую точку или взвешенное среднее итератов
-</pre>
-=== Основное неравенство ===
+[[Неравенство Гёльдера]]
-Для любой оптимальной точки <tex>x^*</tex>
+:: <tex>\langle g,u\rangle\leq\|g\|_*\|u\|</tex>
-:: <tex>\|x_{k+1}-x^*\|_2^2\leq\|x_k-x^*\|_2^2-2\alpha_k(f(x_k)-f^*)+\alpha_k^2\|g_k\|_2^2.</tex>
-В безусловной задаче здесь равенство получается раскрытием квадрата и затем применяется определение субградиента. В проекционном варианте неравенство сохраняется вследствие нерастягивающего свойства [[Евклидова проекция|евклидовой проекции]]. Это соотношение является основой почти всех классических оценок.<ref name="polyak">См. Polyak (1969).</ref><ref name="shor">См. Шор (1979).</ref>
-=== Выпуклый случай: оценка сходимости ===
+связывает размер области в прямой норме с размером субградиентов в двойственной. Если <tex>f</tex> выпукла и <tex>G</tex>-липшицева на открытом множестве относительно <tex>\|\cdot\|</tex>, то <tex>\|g\|_*\leq G</tex> для всех субградиентов во внутренних точках; верно и обратное при соответствующих условиях на область.
+В [[Евклидово пространство|евклидовом пространстве]] градиент отождествляет линейный функционал с вектором, поэтому шаг <tex>x-\alpha g</tex> естественен. Для общей нормы направление [[Метод наискорейшего спуска|наискорейшего линейного спуска]] задаётся отображением
+:: <tex>v(g)\in\operatorname{arg\,min}_{v}\left\{\langle g,v\rangle+\frac12\|v\|^2\right\},\qquad \|v(g)\|=\|g\|_*.</tex>
+Если квадратичная стабилизация заменяется сильно выпуклым потенциалом и [[Дивергенция Брэгмана|дивергенцией Брэгмана]], получается [[Метод зеркального спуска|зеркальный спуск]]. Следовательно, упоминание произвольной нормы в оценке не означает, что евклидово обновление автоматически стало неевклидовым: должны быть согласованы норма, двойственная норма и геометрия проекции.
+Более точно, пусть <tex>\psi</tex> является <tex>\sigma</tex>-сильно выпуклым потенциалом относительно <tex>\|\cdot\|</tex>, а
+:: <tex>D_\psi(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle.</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>\|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>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>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>\alpha_t>0</tex> по заранее указанному правилу;
+## вычислить <tex>x_{t+1}=\Pi_X(x_t-\alpha_t g_t)</tex>;
+# вернуть лучшую вычисленную точку либо взвешенное среднее
+:: <tex>\bar x_T=\frac{\sum_{t=1}^T\alpha_t x_t}{\sum_{t=1}^T\alpha_t}.</tex>
+Для чисто оракульной задачи значение лучшей точки <tex>\operatorname{arg\,min}_{t\leq T}f(x_t)</tex> требует вычислять <tex>f(x_t)</tex>. В стохастической задаче выбор по шумной эмпирической потере вносит смещение, поэтому теоремы обычно относятся к усреднению или к специально построенной последней итерации.
+=== Основное одношаговое неравенство ===
+Неэкспансивность проекции и неравенство субградиента дают для любого <tex>x^*\in X^*</tex>
+:: <tex>\|x_{t+1}-x^*\|_2^2\leq\|x_t-x^*\|_2^2-2\alpha_t\bigl(f(x_t)-f^*\bigr)+\alpha_t^2\|g_t\|_2^2.</tex>
+Это центральное соотношение: полезный член линеен по <tex>\alpha_t</tex>, а накопленная ошибка шага квадратична. В общем случае значения <tex>f(x_t)</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^*\leq\frac{R^2+G^2\sum_{t=1}^T\alpha_t^2}{2\sum_{t=1}^T\alpha_t}.</tex>
+Та же правая часть ограничивает <tex>\min_{1\leq t\leq T}f(x_t)-f^*</tex>. При известном горизонте выбор
+:: <tex>\alpha_t=\frac{R}{G\sqrt T}</tex>
-Пусть <tex>f</tex> выпукла, <tex>X^*\ne\emptyset</tex>, <tex>\|x_1-x^*\|_2\leq R</tex> для некоторого <tex>x^*\in X^*</tex> и <tex>\|g_k\|_2\leq G</tex> на всех итерациях. Для взвешенного среднего
-:: <tex>\bar x_T=\frac{\sum_{k=1}^T\alpha_kx_k}{\sum_{k=1}^T\alpha_k}</tex>
-выпуклость и телескопирование дают
-:: <tex>f(\bar x_T)-f^*\leq\frac{R^2+G^2\sum_{k=1}^T\alpha_k^2}{2\sum_{k=1}^T\alpha_k}.</tex>
-Та же правая часть ограничивает наилучшее значение <tex>\min_{1\leq k\leq T}f(x_k)-f^*</tex>. При известном горизонте выбор постоянного шага
-:: <tex>\alpha_k=\frac{R}{G\sqrt T}</tex>
 даёт
 :: <tex>f(\bar x_T)-f^*\leq\frac{RG}{\sqrt T}.</tex>
-Следовательно, для точности <tex>\varepsilon</tex> достаточно порядка <tex>(RG/\varepsilon)^2</tex> обращений к оракулу. Для класса [[Липшицева функция|липшицевых]] выпуклых функций эта зависимость от точности в общем случае неулучшаема методами первого порядка.<ref>См. Nemirovski, Yudin (1983).</ref><ref>Современное изложение оценок сложности см. в Bubeck (2015).</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>C</tex>, если для всех <tex>x,y\in C</tex> и <tex>g\in\partial f(x)</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^2.</tex>
-Пусть дополнительно <tex>\|g_k\|_2\leq G</tex>, а итерации проецируются на <tex>C</tex>. При шагах
-:: <tex>\alpha_k=\frac{2}{\mu(k+1)}</tex>
-и усреднении с линейно растущими весами
-:: <tex>\tilde x_T=\frac{2}{T(T+1)}\sum_{k=1}^T kx_k</tex>
-справедлива оценка
-:: <tex>f(\tilde x_T)-f^*\leq\frac{2G^2}{\mu(T+1)}.</tex>
-Точные константы зависят от индексации и схемы усреднения; обычное равномерное усреднение с шагом порядка <tex>1/(\mu k)</tex> обычно даёт более слабую оценку порядка <tex>G^2(1+\log T)/(\mu T)</tex>. Сильная выпуклость улучшает сложность до порядка <tex>G^2/(\mu\varepsilon)</tex>, но не превращает негладкий метод в [[Линейная сходимость|линейно сходящийся]] без дополнительных структурных предпосылок.<ref>См. Nesterov (2004), разд. 3.2.</ref>
-== Проекционный субградиентный метод ==
+обеспечивают асимптотическую сходимость при ограниченных субградиентах, но сами по себе не дают лучшей конечновременной константы<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>x\in C</tex> используется итерация
+=== Постоянный шаг ===
-:: <tex>x_{k+1}=\Pi_C(x_k-\alpha_kg_k),\qquad g_k\in\partial f(x_k),</tex>
-где <tex>\Pi_C(z)={\rm argmin}_{x\in C}\|x-z\|_2</tex>. [[Проекция на выпуклое множество|Проекция]] однозначна для непустого замкнутого выпуклого множества. Все приведённые выше выпуклые оценки сохраняются, если <tex>R</tex> ограничивает расстояние начальной точки до решения, а <tex>G</tex> — нормы выбранных субградиентов вдоль траектории.
-<pre>
+При <tex>\alpha_t=\alpha</tex> предыдущая оценка принимает вид
-Вход: x_1 в C, горизонт T
-для k = 1,...,T:
-    g_k := выбранный субградиент f в x_k
-    z_k := x_k - alpha_k g_k
-    x_{k+1} := евклидова проекция z_k на C
-вернуть взвешенное среднее точек x_k
-</pre>
-Не следует смешивать этот метод с '''проекционным градиентным методом''': формула совпадает, но последний обычно предполагает дифференцируемую функцию с липшицевым градиентом и допускает существенно более быстрые гарантии. Если проекция на <tex>C</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>\alpha_k=\alpha</tex> и <tex>\|g_k\|\leq G</tex> из основной оценки следует
+Пусть <tex>f</tex> <tex>\mu</tex>-[[Сильно выпуклая функция|сильно выпукла]] относительно евклидовой нормы:
-:: <tex>\min_{1\leq k\leq T}(f(x_k)-f^*)\leq\frac{R^2}{2\alpha T}+\frac{\alpha G^2}{2}.</tex>
-При фиксированном <tex>\alpha</tex> метод в общем случае входит лишь в окрестность оптимума размера порядка <tex>\alpha G^2</tex>. Постоянный шаг удобен в нестационарном и онлайн-обучении, где отслеживание меняющейся цели важнее асимптотической точности.
-=== Убывающие шаги ===
+:: <tex>f(y)\geq f(x)+\langle g,y-x\rangle+\frac\mu2\|y-x\|_2^2</tex>
-Классические условия
+для всех <tex>g\in\partial f(x)</tex>. Пусть также <tex>\|g_t\|_2\leq G</tex>. Для шага
-:: <tex>\alpha_k>0,\qquad \sum_{k=1}^{\infty}\alpha_k=\infty,\qquad \sum_{k=1}^{\infty}\alpha_k^2<\infty</tex>
-выполняются, например, для <tex>\alpha_k=a/(k+b)^p</tex> при <tex>1/2<p\leq1</tex>. Если задача выпукла, множество решений непусто, итерации остаются в замкнутом выпуклом множестве и субградиенты равномерно ограничены, то значения лучших итератов сходятся к <tex>f^*</tex>; при стандартных условиях [[Последовательность Фейера|квазифейеровской монотонности]] расстояния до множества решений также сходятся, а предельные точки являются решениями. Условие суммируемости квадратов особенно важно в стохастическом случае для подавления шума.
-Шаг <tex>\alpha_k=a/\sqrt{k}</tex> удобен для конечного горизонта и оптимальной оценки порядка <tex>1/\sqrt T</tex>, но его квадраты не суммируются; это не противоречие, поскольку конечновременная оценка и почти наверное сходимость бесконечной шумной последовательности — разные утверждения.
+:: <tex>\alpha_t=\frac{2}{\mu(t+1)}</tex>
+и среднего с линейными весами
+:: <tex>\widetilde x_T=\frac{2}{T(T+1)}\sum_{t=1}^T t x_t</tex>
+выполняется оценка порядка
+:: <tex>f(\widetilde x_T)-f^*\leq\frac{2G^2}{\mu(T+1)}.</tex>
+Таким образом, сложность уменьшается до <tex>O(G^2/(\mu\varepsilon))</tex>. Для стандартного шага порядка <tex>1/(\mu t)</tex> последняя итерация или равномерное среднее часто несут дополнительный множитель <tex>\log T</tex>; он не является фундаментальным и устраняется правильными весами либо специальным расписанием шагов. В стохастическом случае оптимальность последней итерации требует отдельного анализа<ref name="JainLast">{{статья |автор=Jain P., Nagaraj D., Netrapalli P. |заглавие=Making the Last Iterate of SGD Information Theoretically Optimal |ссылка=https://proceedings.mlr.press/v99/jain19a.html |издание=Proceedings of Machine Learning Research: COLT |год=2019 |том=99 |страницы=1752—1755 |язык=en}}</ref>.
+Сильная выпуклость и негладкость совместимы только на ограниченной области, если все субградиенты глобально ограничены: на всей <tex>\mathbb{R}^d</tex> сильная выпуклость заставляет нормы субградиентов расти вдали от минимума. Поэтому предпосылка <tex>\|g_t\|\leq G</tex> относится к траектории или ограниченному множеству.
 === Шаг Поляка ===
-Если известно точное оптимальное значение, применяют
+Если известно точное оптимальное значение <tex>f^*</tex>, применяется шаг Поляка
-:: <tex>\alpha_k=\frac{f(x_k)-f^*}{\|g_k\|_2^2},\qquad g_k\ne0.</tex>
-Тогда
-:: <tex>\|x_{k+1}-x^*\|_2^2\leq\|x_k-x^*\|_2^2-\frac{(f(x_k)-f^*)^2}{\|g_k\|_2^2}.</tex>
-При <tex>\|g_k\|\leq G</tex> отсюда следует оценка для лучшего итерата порядка <tex>GR/\sqrt T</tex>. Практическая трудность — необходимость знать <tex>f^*</tex>. Подстановка завышенной нижней оценки может сделать числитель отрицательным, а слишком низкая оценка ведёт к чрезмерным шагам. Варианты с динамической оценкой уровня относятся к [[Level-метод|level-методам]].<ref name="polyak"/>
-=== Нормированный шаг и поиск по линии ===
+:: <tex>\alpha_t=\gamma\frac{f(x_t)-f^*}{\|g_t\|_2^2},\qquad 0<\gamma<2,</tex>
-Иногда используют <tex>x_{k+1}=x_k-\beta_k g_k/\|g_k\|</tex>. Это отделяет длину шага от масштаба субградиента, но не устраняет необходимость настраивать <tex>\beta_k</tex>. Обычный точный поиск по линии менее естественен, чем в гладком спуске: субградиент не обязан задавать направление убывания, а минимум вдоль луча может находиться в нулевой точке.
+при <tex>g_t\ne0</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>
-=== Оракул и отличие от SGD ===
+Правило не требует заранее знать <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>f(x)=\mathbb E_{\xi}[F(x,\xi)]</tex>
-или <tex>f(x)=n^{-1}\sum_{i=1}^n f_i(x)</tex>. На итерации выбирается случайный вектор <tex>G_k</tex> и выполняется
-:: <tex>x_{k+1}=\Pi_C(x_k-\alpha_kG_k).</tex>
-Корректная предпосылка несмещённости формулируется относительно истории <tex>\mathcal F_k</tex>:
-:: <tex>\mathbb E[G_k\mid\mathcal F_k]\in\partial f(x_k),\qquad \mathbb E[\|G_k\|_2^2\mid\mathcal F_k]\leq G^2.</tex>
-Если каждая <tex>F(\cdot,\xi)</tex> выпукла и измерима, а условия интегрируемости разрешают перестановку [[Математическое ожидание|математического ожидания]] и субдифференциала, то можно взять <tex>G_k\in\partial_xF(x_k,\xi_k)</tex> для независимого примера <tex>\xi_k</tex>.<ref name="nemirovski09">См. Nemirovski et al. (2009).</ref>
-'''Stochastic gradient descent''' в узком смысле использует несмещённую оценку обычного градиента дифференцируемой функции. '''Стохастический субградиентный метод''' допускает изломы и оценивает элемент субдифференциала. В литературе по машинному обучению обе схемы часто называют SGD; математически это допустимое сокращение только после явного задания оракула.
+Пусть <tex>F(x,\xi)</tex> — случайная выпуклая функция и
-=== Гарантии в среднем ===
+:: <tex>f(x)=\mathbb E_{\xi}[F(x,\xi)].</tex>
-Пусть <tex>C</tex> замкнуто и выпукло, <tex>f</tex> выпукла, <tex>x^*\in X^*</tex>, <tex>\|x_1-x^*\|\leq R</tex>, а стохастический оракул удовлетворяет двум условным моментным условиям выше. Тогда
+'''Stochastic subgradient descent''' использует
-:: <tex>\mathbb E[f(\bar x_T)-f^*]\leq\frac{R^2+G^2\sum_{k=1}^T\alpha_k^2}{2\sum_{k=1}^T\alpha_k}.</tex>
-При <tex>\alpha_k=R/(G\sqrt T)</tex> получается <tex>\mathbb E[f(\bar x_T)-f^*]\leq RG/\sqrt T</tex>. Если <tex>f</tex> дополнительно <tex>\mu</tex>-сильно выпукла, то шаги <tex>2/(\mu(k+1))</tex> и линейно-взвешенное усреднение дают
-:: <tex>\mathbb E[f(\tilde x_T)-f^*]\leq\frac{2G^2}{\mu(T+1)}.</tex>
-Это утверждения о математическом ожидании. Для оценки с вероятностью не менее <tex>1-\delta</tex> нужны дополнительные хвостовые предпосылки — например, почти наверное ограниченные шум и диаметр множества либо условная [[Субгауссовская случайная величина|субгауссовость]]. Тогда [[Мартингал|мартингальные]] неравенства дают добавку порядка <tex>GR\sqrt{\log(1/\delta)/T}</tex>; одной ограниченности второго момента для такой экспоненциальной зависимости от <tex>\delta</tex> недостаточно.
-При независимых мини-пакетах размера <tex>b</tex> дисперсионная часть второго момента уменьшается примерно в <tex>b</tex> раз, если индивидуальные ошибки независимы и имеют конечную дисперсию. Систематическое смещение оракула в базовую теорему не входит и обычно оставляет ненулевую ошибку.
+:: <tex>x_{t+1}=\Pi_X(x_t-\alpha_t G_t),</tex>
-=== Почти наверное сходимость ===
+где относительно истории <tex>\mathcal F_{t-1}</tex> [[Условное математическое ожидание|условное математическое ожидание]] удовлетворяет условиям
-При условиях [[Стохастическая аппроксимация|Роббинса—Монро]] на шаги, условной несмещённости, равномерно ограниченном условном втором моменте, непустом множестве решений и стандартных условиях ограниченности итератов стохастическая квазимартингальная аргументация даёт [[Сходимость почти наверное|почти наверное сходимость]] значений к оптимальному и предельных точек к <tex>X^*</tex>.<ref>См. Robbins, Monro (1951).</ref> Это асимптотический результат; он не заменяет конечновременную оценку ожидаемой ошибки.
+:: <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>f</tex>, существовании <tex>x^*</tex> и <tex>\|x_1-x^*\|_2\leq R</tex> выполняется
-=== Hinge loss и линейный SVM ===
+:: <tex>\mathbb E[f(\bar x_T)-f^*]\leq\frac{R^2+G^2\sum_{t=1}^T\alpha_t^2}{2\sum_{t=1}^T\alpha_t}.</tex>
-Для размеченного объекта <tex>(a,y)</tex>, где <tex>y\in\{-1,1\}</tex>, [[Функция потерь|hinge loss]] равна
+Настроенный постоянный шаг снова даёт <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>\ell(w;a,y)=\max\{0,1-y\langle w,a\rangle\}.</tex>
-Её субградиент по <tex>w</tex> можно выбрать как
-:: <tex>g(w)=\left\{\begin{array}{ll}-ya,&y\langle w,a\rangle<1,\\ 0,&y\langle w,a\rangle>1,\\ -\theta ya,\quad\theta\in[0,1],&y\langle w,a\rangle=1.\end{array}\right.</tex>
-Прямая задача линейного [[Метод опорных векторов|SVM]] имеет вид
-:: <tex>\min_w\ \frac{\lambda}{2}\|w\|_2^2+\frac1n\sum_{i=1}^n\max\{0,1-y_i\langle w,a_i\rangle\}.</tex>
-При случайном выборе <tex>i_k</tex> стохастический субградиент равен
-:: <tex>G_k=\lambda w_k-y_{i_k}a_{i_k}\,\mathbf{1}_{y_{i_k}\langle w_k,a_{i_k}\rangle<1}.</tex>
-Алгоритм [[Pegasos]] использует шаг <tex>1/(\lambda k)</tex> и проекцию на шар радиуса <tex>1/\sqrt\lambda</tex>; сильная выпуклость квадратичного регуляризатора обеспечивает скорость порядка <tex>1/T</tex> с логарифмическими оговорками, зависящими от выбранного выхода алгоритма.<ref name="pegasos">См. Shalev-Shwartz et al. (2011).</ref>
-=== L1-регуляризация ===
+Стохастический субградиентный метод не следует смешивать с детерминированным методом: случайный субградиент отдельного примера обязан быть несмещённым субградиентом ожидаемой цели. Для максимума, квантили риска, отрицательного семплирования и других нелинейных преобразований эмпирический оракул может оказаться смещённым.
-В задаче
+== Выбор субградиента ==
-:: <tex>\min_w\ L(w)+\lambda\|w\|_1</tex>
-можно использовать субградиент <tex>\nabla L(w)+\lambda s</tex>, где <tex>s_j={\rm sign}(w_j)</tex> при <tex>w_j\ne0</tex> и <tex>s_j\in[-1,1]</tex> при <tex>w_j=0</tex>. Однако обычный субградиентный шаг почти никогда не создаёт точных нулей и игнорирует известную структуру регуляризатора. Если <tex>L</tex> гладка с липшицевым градиентом, [[Проксимальный градиентный метод|проксимальный градиентный метод]]
-:: <tex>w_{k+1}={\rm soft}_{\alpha_k\lambda}(w_k-\alpha_k\nabla L(w_k))</tex>
-обычно предпочтительнее: [[Мягкая пороговая функция|мягкое пороговое преобразование]] даёт точную разреженность, а базовая скорость для выпуклой задачи составляет порядок <tex>1/T</tex>, ускоренная — порядка <tex>1/T^2</tex>.<ref>См. Beck, Teboulle (2009).</ref>
-=== Максимумы и робастные критерии ===
+=== Правила исчисления ===
-Функции вида <tex>f(x)=\max_j f_j(x)</tex> возникают в многоклассовых margin-потерях, минимаксном обучении, робастной оптимизации и задачах с наихудшим сценарием. Субградиент активной ветви позволяет работать без сглаживания. При большом числе ветвей стоимость поиска точного максимума может доминировать; тогда применяют случайное приближение максимума, cutting-plane или bundle-методы, но смещение приближённого оракула следует учитывать отдельно.
+Для суммы выпуклых функций при стандартном условии регулярности
-[[Абсолютная ошибка|Абсолютная]] и [[Квантильная регрессия|квантильная]] потери, <tex>\ell_1</tex>-отклонения, нормы остатков и [[Conditional Value-at-Risk|CVaR]] дают выпуклые негладкие робастные критерии. Для CVaR стандартное вариационное представление содержит положительную часть и потому допускает стохастические субградиенты по отдельным наблюдениям.<ref>См. Rockafellar, Uryasev (2000).</ref> Робастность статистического критерия не означает робастности самого стохастического оракула к тяжёлым хвостам: при бесконечном втором моменте приведённые оценки неприменимы, и требуются усечение, [[Median-of-means|median-of-means]] или иные робастные агрегаторы.
+:: <tex>\partial(f+h)(x)=\partial f(x)+\partial h(x).</tex>
-=== [[Распределённая оптимизация|Распределённое]] и [[Федеративное обучение|федеративное обучение]] ===
+Для максимума конечного числа выпуклых функций
-Если <tex>f(x)=\sum_{i=1}^m f_i(x)</tex>, а узел <tex>i</tex> знает только <tex>f_i</tex>, типичная консенсусная схема имеет вид
+:: <tex>f(x)=\max_{1\leq i\leq m}f_i(x)</tex>
-:: <tex>x_{i,k+1}=\Pi_C\left(\sum_{j=1}^m W_{ij,k}x_{j,k}-\alpha_k g_{i,k}\right),\qquad g_{i,k}\in\partial f_i(x_{i,k}).</tex>
-Сходимость требует не только выпуклости и ограниченности субградиентов, но и связности графа во времени, стохастичности матриц смешивания и согласования шага с коммуникационной ошибкой. Скорость зависит от [[Спектральный зазор|спектрального зазора]] сети; утверждение «каждый узел делает локальный субградиентный шаг» само по себе гарантии не даёт.<ref>См. Nedić, Ozdaglar (2009).</ref><ref>См. Duchi, Agarwal, Wainwright (2012).</ref>
-== Связь с другими методами ==
+и активного множества <tex>I(x)=\{i:f_i(x)=f(x)\}</tex>
-=== Градиентный спуск и projected gradient ===
+:: <tex>\partial f(x)=\operatorname{conv}\bigcup_{i\in I(x)}\partial f_i(x).</tex>
-У гладкой выпуклой функции субградиент совпадает с градиентом, но анализировать метод как субградиентный обычно невыгодно. Если <tex>\nabla f</tex> липшицев с константой <tex>L</tex>, градиентный спуск с шагом порядка <tex>1/L</tex> имеет скорость порядка <tex>1/T</tex>, а при сильной выпуклости — линейную. Общий субградиентный метод для липшицевой негладкой функции имеет лишь порядок <tex>1/\sqrt T</tex>, либо <tex>1/T</tex> при сильной выпуклости. Projected gradient — градиентный шаг плюс проекция при гладкой цели; projected subgradient — та же внешняя формула с негладким оракулом и другими гарантиями.
+Здесь <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>F(x)=h(x)+r(x)</tex>, где <tex>h</tex> гладка, а проксимальный оператор <tex>r</tex> вычисляется эффективно, итерация
+Теория допускает любой корректный и ограниченный субградиент, но траектории различаются. В точке с несколькими активными кусками можно выбрать субградиент одного куска, выпуклую комбинацию или элемент минимальной нормы. Последний часто уменьшает квадрат ошибки <tex>\alpha_t^2\|g_t\|^2</tex>, однако его вычисление само может требовать решения квадратичной задачи. Нулевой субградиент следует выбирать, когда он доступен и подтверждает оптимальность неограниченной выпуклой задачи.
-:: <tex>x_{k+1}={\rm prox}_{\alpha r}(x_k-\alpha\nabla h(x_k))</tex>
-использует структуру <tex>r</tex> точнее, чем единый субградиент <tex>\nabla h+\partial r</tex>. Субградиентный метод оправдан, когда проксимальный оператор или декомпозиция недоступны, когда нужен крайне дешёвый потоковый шаг либо умеренная точность достаточна.
-=== Зеркальный спуск ===
+Нельзя брать градиент произвольно выбранной неактивной ветви максимума, заменять истинный субградиент усечённым вектором без изменения анализа или считать результат автоматического дифференцирования корректным для любой композиции. Для невыпуклых функций применяются другие понятия — например, субдифференциал Кларка или предельный субдифференциал, — и выпуклые гарантии выше уже не действуют.
-[[Зеркальный спуск]] заменяет евклидов квадрат расстояния [[Расстояние Брэгмана|дивергенцией Брэгмана]] и выполняет шаг в двойственной геометрии. Евклидов проекционный субградиентный метод — его частный случай. На [[Симплекс|симплексе]] энтропийная геометрия может заменить зависимость от размерности порядка <tex>\sqrt d</tex> на <tex>\sqrt{\log d}</tex>; потому выбор нормы и прокс-функции является частью алгоритма, а не косметической заменой.<ref>Определение дивергенции см. в Bregman (1967); связь с зеркальным спуском — в Beck, Teboulle (2003).</ref><ref name="nemirovski09"/>
+== Правила шага ==
+{| class="wikitable"
+! Правило
+! Требуемая информация
+! Гарантия и замечание
+|-
+| <tex>\alpha=R/(G\sqrt T)</tex>
+| Горизонт <tex>T</tex>, оценки <tex>R</tex> и <tex>G</tex>
+| Оптимальный порядок <tex>O(RG/\sqrt T)</tex> для усреднения в выпуклом липшицевом случае
+|-
+| <tex>\alpha_t=c/\sqrt t</tex>
+| Масштаб <tex>c</tex>
+| Удобно без известного горизонта; наивное взвешивание может дать лишний логарифм
+|-
+| <tex>\alpha_t=c/t</tex>
+| Сильная выпуклость и настройка масштаба
+| Порядок <tex>O(1/T)</tex> с надлежащими весами; слишком быстро для общей лишь выпуклой задачи
+|-
+| Шаг Поляка
+| Точное <tex>f^*</tex> и значение <tex>f(x_t)</tex>
+| Адаптивен к текущему разрыву; чувствителен к ошибке в целевом значении
+|-
+| Постоянный шаг
+| Только масштаб субградиента
+| Быстро входит в окрестность, но оставляет ненулевой уровень ошибки
+|-
+| AdaGrad и диагональные адаптивные шаги
+| Накопленные квадраты координат субградиентов
+| Подстраиваются под разреженность и анизотропию данных; гарантия относится к изменяющейся геометрии, а не к произвольному покоординатному клиппингу<ref name="AdaGrad">{{статья |автор=Duchi J., Hazan E., Singer Y. |заглавие=Adaptive Subgradient Methods for Online Learning and Stochastic Optimization |ссылка=https://jmlr.org/papers/v12/duchi11a.html |издание=Journal of Machine Learning Research |год=2011 |том=12 |страницы=2121—2159 |язык=en}}</ref>
+|}
+[[Линейный поиск]], основанный на локальном убывании, ненадёжен: допустимое направление <tex>-g_t</tex> может не быть направлением спуска. [[Масштабирование признаков]] меняет нормы субградиентов, поэтому шаг, подходящий до стандартизации данных, не обязан оставаться подходящим после неё.
+== Связь с родственными методами ==
+=== Градиентный спуск ===
+Если <tex>f</tex> дифференцируема, субградиент единственен. Однако использование только общей липшицевости функции сохраняет медленную оценку <tex>O(T^{-1/2})</tex>. Более быстрая оценка [[Градиентный спуск|градиентного спуска]] <tex>O(T^{-1})</tex> требует <tex>L</tex>-липшицевости градиента, а линейная сходимость — одновременно гладкости и сильной выпуклости. Негладкая сильно выпуклая функция обычно допускает лишь <tex>O(T^{-1})</tex>, а не геометрический темп для базового субградиентного метода.
+=== Проекционный субградиентный метод ===
+Projected subgradient descent — не отдельный тип оракула, а базовое обновление с явным допустимым множеством. Проекция обеспечивает допустимость и не увеличивает расстояние до решения. Если <tex>\Pi_X</tex> дорога, одна «простая» итерация фактически содержит отдельную оптимизационную задачу. Неевклидова прокс-проекция приводит к зеркальному спуску.
+=== Проксимальные методы ===
+Для [[Составная оптимизация|составной задачи]]
+:: <tex>\min_x\{F(x)=h(x)+r(x)\},</tex>
+где <tex>h</tex> выпукла и <tex>L</tex>-гладка, а проксимальный оператор <tex>r</tex> вычислим, [[Проксимальный градиентный метод]] выполняет
+:: <tex>x_{t+1}=\operatorname{prox}_{\alpha r}(x_t-\alpha\nabla h(x_t)),</tex>
+:: <tex>\operatorname{prox}_{\alpha r}(z)=\operatorname{arg\,min}_x\left\{r(x)+\frac{1}{2\alpha}\|x-z\|_2^2\right\}.</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>.
 === Bundle methods ===
-Обычный метод забывает субградиент сразу после шага. [[Bundle method|Bundle-методы]] сохраняют набор опорных плоскостей
+[[Bundle method|Bundle methods]] сохраняют несколько опорных плоскостей
-:: <tex>f(y)\geq f(x_i)+\langle g_i,y-x_i\rangle</tex>
-и строят [[Кусочно-линейная функция|кусочно-линейную]] нижнюю модель, часто стабилизированную проксимальным членом. Они требуют больше памяти и решения вспомогательной задачи, зато обычно устойчивее и эффективнее при дорогом детерминированном оракуле высокой точности. Это естественный выбор для задач, где одно вычисление функции дорого, а число итераций важнее стоимости шага.<ref>См. Lemaréchal (1978).</ref><ref>См. Lemaréchal, Nemirovskii, Nesterov (1995).</ref>
+:: <tex>m_t(x)=\max_{i\in B_t}\{f(x_i)+\langle g_i,x-x_i\rangle\}</tex>
+и минимизируют стабилизированную кусочно-линейную модель. Они используют больше памяти и решают более дорогую подзадачу, но повторно используют информацию о прошлых изломах, различают серьёзные и холостые шаги и обычно устойчивее к масштабу. Современный анализ проксимального bundle method показывает адаптацию к гладкости и условиям роста и оптимальные темпы при подходящих непостоянных параметрах<ref name="DiazGrimmer">{{статья |автор=Díaz M., Grimmer B. |заглавие=Optimal Convergence Rates for the Proximal Bundle Method |ссылка=https://doi.org/10.1137/21M1428601 |издание=SIAM Journal on Optimization |год=2023 |том=33 |номер=2 |страницы=424—454 |язык=en}}</ref>. Bundle method не является «субградиентным методом с памятью» в смысле одной и той же итерации: его модель и критерий принятия шага принципиально иные.
+=== Сравнение ===
+{| class="wikitable"
+! Метод
+! Предпосылка о цели
+! Ограничения
+! Стоимость итерации
+! Память
+! Типичная гарантия
+|-
+| Субградиентный спуск
+| Выпуклость и ограниченные субградиенты
+| Без ограничений
+| Один оракул и векторное сложение, обычно <tex>O(d)</tex>
+| <tex>O(d)</tex>
+| <tex>O(T^{-1/2})</tex>; <tex>O(T^{-1})</tex> при сильной выпуклости и правильном усреднении
+|-
+| Projected subgradient descent
+| То же
+| Замкнутое выпуклое <tex>X</tex>
+| Оракул плюс проекция на <tex>X</tex>
+| <tex>O(d)</tex> без состояния проектора
+| Те же порядки; константа зависит от расстояния в допустимом множестве
+|-
+| Градиентный спуск
+| Выпуклость и <tex>L</tex>-гладкость
+| Обычно без ограничений или с проекцией
+| Градиент и простой шаг
+| <tex>O(d)</tex>
+| <tex>O(T^{-1})</tex>; линейно при сильной выпуклости
+|-
+| Proximal gradient
+| <tex>h</tex> гладка, <tex>r</tex> проксимально проста
+| Через prox или отдельную проекцию
+| Градиент плюс prox
+| <tex>O(d)</tex>
+| <tex>O(T^{-1})</tex>, ускоренно <tex>O(T^{-2})</tex>; линейно при дополнительных условиях
+|-
+| Bundle method
+| Выпуклая негладкая цель и оракул значений с субградиентами
+| Встраиваются в модель или подзадачу
+| Решение стабилизированной QP или родственной задачи
+| <tex>O(md)</tex> для bundle размера <tex>m</tex>, без учёта факторизаций
+| Сохраняет оракульные оценки базового класса; лучшие практические и адаптивные гарантии при дополнительной структуре
+|}
+== Применения в машинном обучении ==
+=== Негладкие функции потерь ===
+Субградиентный оракул естественен для [[Абсолютная ошибка|абсолютной ошибки]], [[Квантильная регрессия|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>g_i(w)=\begin{cases}-y_i x_i,&s_i<1,\\0,&s_i>1,\end{cases}</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>\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_2</tex>-регуляризацией сильная выпуклость оправдывает шаг порядка <tex>1/t</tex>. Для нестрого выпуклой линейной модели нельзя использовать эту оценку только потому, что функция потерь выпукла.
-Максимум или [[Выпуклое сопряжение|сопряжённое представление]] нередко можно заменить гладкой аппроксимацией с параметром <tex>\tau</tex>. Возникает компромисс: ошибка аппроксимации порядка <tex>\tau</tex> и константа Липшица градиента, растущая при <tex>\tau\to0</tex>. [[Сглаживание Нестерова]] позволяет применять [[Ускоренный градиентный метод|ускоренный градиентный метод]] и часто лучше при высокой требуемой точности, если структура максимума доступна.<ref>См. Nesterov (2005).</ref>
+=== Крупномасштабное и онлайн-обучение ===
-== Субградиент и обобщённые производные ==
+Один субградиент примера или [[Мини-пакет|мини-пакета]] стоит существенно дешевле полного прохода по данным. В [[Онлайн-обучение|онлайн-обучении]] то же одношаговое неравенство оценивает [[Regret|regret]]
-Выпуклый субдифференциал не следует без оговорок переносить на невыпуклые функции. Для локально липшицевой невыпуклой функции используют [[Субдифференциал Кларка|субдифференциал Кларка]], [[Субдифференциал Мордуховича|предельный субдифференциал Мордуховича]] и другие конструкции. У выпуклой локально липшицевой функции субдифференциал Кларка совпадает с выпуклым субдифференциалом; вне выпуклого случая глобальное опорное неравенство теряется, а условие <tex>0\in\partial_C f(x)</tex> означает лишь обобщённую стационарность, не глобальный минимум.<ref>См. Clarke (1983).</ref>
+:: <tex>\operatorname{Regret}_T(u)=\sum_{t=1}^T\bigl(f_t(x_t)-f_t(u)\bigr).</tex>
-Современная теория рассматривает [[Слабая выпуклость|слабо выпуклые функции]], для которых <tex>f(x)+(\rho/2)\|x\|^2</tex> выпукла. При ограниченном стохастическом оракуле подходящая мера стационарности — норма градиента [[Оболочка Моро|оболочки Моро]]; для проекционного стохастического субградиентного метода получены оценки порядка <tex>T^{-1/4}</tex> для этой нормы.<ref>См. Davis, Drusvyatskiy (2019).</ref> Это расширение не является гарантией нахождения глобального минимума и не должно подменять классическую выпуклую теорию.
+При выпуклых потерях, диаметре области <tex>R</tex> и субградиентах нормы не более <tex>G</tex> настроенный шаг даёт <tex>\operatorname{Regret}_T(u)\leq RG\sqrt T</tex>. Деление на <tex>T</tex> и online-to-batch conversion возвращает статистическую оценку порядка <tex>1/\sqrt T</tex>. AdaGrad улучшает зависимость от координатной геометрии для разреженных признаков, но не меняет худший порядок без дополнительной структуры.
-== Практическая реализация ==
+=== Распределённая оптимизация ===
-=== Выбор возвращаемой точки ===
+В [[Распределённая оптимизация|распределённой оптимизации]] для суммы локальных целей
-* Для теоретически контролируемой выпуклой задачи следует хранить взвешенное среднее, соответствующее доказательству.
+:: <tex>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 на одном общем потоке данных.
-Ограничение <tex>\|g_k\|\leq G</tex> зависит от масштаба признаков и выбранной нормы. Стандартизация признаков, предобусловливание, адаптивная диагональная геометрия или зеркальный спуск могут радикально изменить практику. Остановка только по норме выбранного субградиента ненадёжна: в точке излома оракул может вернуть ненулевой элемент даже при наличии нуля в субдифференциале. Более содержательны двойственный разрыв, известная нижняя граница, расстояние между модельными уровнями или устойчивость усреднённой цели.
+=== Невыпуклые модели ===
-=== Типичные ошибки ===
+В [[Глубокая нейронная сеть|глубоких сетях]] с [[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>-g_k</tex> направлением убывания и требовать монотонности <tex>f(x_k)</tex>.
+== Ограничения и типичные ошибки ==
-* Сообщать оценку для последнего итерата, когда теорема доказана только для среднего или лучшего.
-* Использовать скорость <tex>1/T</tex> без сильной выпуклости либо без правильной схемы усреднения.
-* Называть градиент отдельного примера несмещённым, не проверив схему выборки, веса и возможность перестановки ожидания с субдифференциалом.
-* Выбрать в нуле для <tex>\ell_1</tex>-штрафа произвольный знак вне <tex>[-1,1]</tex>.
-* Забыть про проекцию или нормальный конус в задаче с ограничениями.
-* Применять шаг Поляка с неизвестным или неверным <tex>f^*</tex> без защитного правила.
-* Переносить выпуклое субградиентное неравенство на невыпуклую нейросетевую функцию.
-* Сравнивать число итераций, игнорируя стоимость проекции, вычисления максимума, коммуникации и полного значения цели.
-== Когда метод оправдан ==
+* '''Ожидание монотонного спуска.''' Значение цели может возрастать даже при корректном субградиенте; контролируется лучшая или усреднённая точка.
+* '''Слишком большой постоянный шаг.''' Метод остаётся в широкой окрестности решения и может осциллировать через излом.
+* '''Слишком быстрое убывание.''' Если сумма шагов конечна, траектория может не дойти до оптимума; правило <tex>1/t</tex> без сильной выпуклости часто преждевременно замораживает обучение.
+* '''Неверный субградиент на границе кусков.''' Производная неактивной ветви максимума или неверный знак у hinge loss нарушают опорное неравенство.
+* '''Игнорирование масштаба.''' Необработанные признаки делают <tex>G</tex> большим и анизотропным; нормализация, зеркальная геометрия или AdaGrad могут изменить константы на порядки.
+* '''Необоснованная несмещённость.''' Субградиент случайного слагаемого не всегда можно переставить с математическим ожиданием; условия интегрируемости и правила субдифференцирования ожидания должны быть проверены.
+* '''Неправильный выход.''' Гарантия для <tex>\bar x_T</tex> не переносится автоматически на <tex>x_T</tex>; усреднение параметров может быть нежелательно для структурно разреженного решения.
+* '''Смешение с proximal gradient.''' Обработка <tex>\ell_1</tex>-штрафа его субградиентом не эквивалентна soft-thresholding и обычно не создаёт точных нулей.
+* '''Скрытая стоимость проекции.''' Для сложного <tex>X</tex> проекционная подзадача может доминировать над вычислением субградиента.
+* '''Перенос выпуклой теории на нейронные сети.''' Выбор производной ReLU библиотекой не делает глобальную цель выпуклой.
-Субградиентный метод разумен, если одновременно важны простота шага, очень большая размерность или поток данных, функция выпукла и негладка, доступен только оракул первого порядка, а требуемая точность умеренна. Он особенно уместен в двойственной декомпозиции, онлайн-обучении, распределённых задачах с дешёвыми локальными вычислениями и как базовый алгоритм для получения грубого решения.
+Субградиентный метод практически предпочтителен, когда требуется очень дешёвая итерация, доступен только оракул негладкой функции, точность умеренна, размерность или поток данных исключают хранение моделей, а prox или bundle-подзадача дороже нескольких дополнительных проходов. Для высокой точности, доступной составной структуры или дорогого оракула обычно выгоднее проксимальные, сглаженные, cutting-plane или bundle methods.
-Предпочтительнее иной метод, если выполняется одно из условий:
+== Классические результаты и современные варианты ==
-* негладкая часть имеет дешёвый проксимальный оператор — тогда обычно лучше проксимальный или проксимально-стохастический метод;
-* максимум допускает эффективное сглаживание и нужна высокая точность — полезен ускоренный метод для сглаженной цели;
-* оракул дорог и детерминирован — bundle-метод повторно использует накопленные опорные плоскости;
-* задача SVM умеренного размера имеет доступную двойственную структуру — coordinate descent или SMO часто быстрее общего субградиентного метода;
-* функция гладкая — следует использовать градиентный, ускоренный или variance-reduced метод с гарантиями, использующими гладкость;
-* нужна точная разреженность при <tex>\ell_1</tex>-штрафе — проксимальный шаг естественнее;
-* задача невыпукла — необходимо явно выбрать понятие стационарности и теорию, соответствующую классу функции.
-== Исторические замечания ==
+К классическому ядру относятся субдифференциал выпуклой функции, проекционное обновление, оценки <tex>O(T^{-1/2})</tex>, роббинс-монровские условия на шаги и правило Поляка<ref name="Bertsekas">{{книга |автор=Bertsekas D. P. |заглавие=Convex Optimization Algorithms |издательство=Athena Scientific |год=2015 |язык=en}}</ref>. Стохастическая аппроксимация, распределённые схемы, AdaGrad и оптимальные правила усреднения развивают эту основу, сохраняя выпуклую постановку.
-Первые систематические субградиентные алгоритмы связаны с работами Н. З. Шора и Б. Т. Поляка 1960-х годов.<ref name="polyak"/><ref name="shor"/> Классическая теория сформировалась в выпуклом анализе и негладкой оптимизации; позднее идеи вошли в стохастическую аппроксимацию, онлайн-обучение, зеркальный спуск и распределённые алгоритмы. Современные варианты для слабо выпуклых и иных невыпуклых классов расширяют область применения, но используют другие меры качества и не отменяют границ сложности классического липшицева выпуклого случая.
+К более новым направлениям относятся точный анализ последней итерации, робастные методы при тяжёлых хвостах, слабовыпуклые и стратифицированные невыпуклые функции, а также адаптивные 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>.
 == Примечания ==
@@ Строка 294: / Строка 401: @@
 == Литература ==
-* {{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://press.princeton.edu/books/paperback/9780691015866/convex-analysis |издательство=Princeton University Press |место=Princeton |год=1970 |страниц=451 |isbn=978-0-691-01586-6 |язык=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}}
-* {{книга |автор=Danskin J. M. |заглавие=The Theory of Max-Min and Its Application to Weapons Allocation Problems |ссылка=https://link.springer.com/book/10.1007/978-3-642-46092-0 |издательство=Springer |место=Berlin, Heidelberg |год=1967 |doi=10.1007/978-3-642-46092-0 |язык=en}}
+* {{книга |автор=Rockafellar R. T. |заглавие=Convex Analysis |ссылка=https://doi.org/10.1515/9781400873173 |издательство=Princeton University Press |год=1970 |язык=en}}
-* {{статья |автор=Polyak B. T. |заглавие=Minimization of Unsmooth Functionals |ссылка=https://doi.org/10.1016/0041-5553(69)90061-5 |издание=USSR Computational Mathematics and Mathematical Physics |год=1969 |том=9 |номер=3 |страницы=14—29 |doi=10.1016/0041-5553(69)90061-5 |язык=en}}
+* {{книга |автор=Nemirovski A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |издательство=Wiley |год=1983 |язык=en}}
-* {{книга |автор=Шор Н. З. |заглавие=Методы минимизации недифференцируемых функций и их приложения |издательство=Наукова думка |место=Киев |год=1979 |страниц=199 |язык=ru}}
+* {{книга |автор=Shor N. Z. |заглавие=Minimization Methods for Non-Differentiable Functions |ссылка=https://doi.org/10.1007/978-3-642-82118-9 |издательство=Springer |год=1985 |язык=en}}
-* {{книга |автор=Nemirovski A. S., Yudin D. B. |заглавие=Problem Complexity and Method Efficiency in Optimization |издательство=Wiley |место=New York |год=1983 |isbn=978-0-471-10345-5 |язык=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}}
-* {{статья |автор=Bubeck S. |заглавие=Convex Optimization: Algorithms and Complexity |ссылка=https://doi.org/10.1561/2200000050 |издание=Foundations and Trends in Machine Learning |год=2015 |том=8 |номер=3—4 |страницы=231—357 |doi=10.1561/2200000050 |язык=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}}
-* {{книга |автор=Nesterov Y. |заглавие=Introductory Lectures on Convex Optimization: A Basic Course |ссылка=https://link.springer.com/book/10.1007/978-1-4419-8853-9 |издательство=Kluwer Academic Publishers |место=Boston |год=2004 |isbn=978-1-4020-7553-7 |язык=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}}
-* {{статья |автор=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}}
+* {{книга |автор=Bertsekas D. P. |заглавие=Convex Optimization Algorithms |издательство=Athena Scientific |год=2015 |язык=en}}
-* {{статья |автор=Robbins H., Monro S. |заглавие=A Stochastic Approximation Method |ссылка=https://doi.org/10.1214/aoms/1177729586 |издание=The Annals of Mathematical Statistics |год=1951 |том=22 |номер=3 |страницы=400—407 |doi=10.1214/aoms/1177729586 |язык=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}}
-* {{статья |автор=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 |номер=1 |страницы=3—30 |doi=10.1007/s10107-010-0420-4 |язык=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}}
-* {{статья |автор=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 |doi=10.1137/080716542 |язык=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}}
-* {{статья |автор=Rockafellar R. T., Uryasev S. |заглавие=Optimization of Conditional Value-at-Risk |ссылка=https://doi.org/10.21314/JOR.2000.038 |издание=Journal of Risk |год=2000 |том=2 |номер=3 |страницы=21—41 |doi=10.21314/JOR.2000.038 |язык=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}}
-* {{статья |автор=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 |doi=10.1109/TAC.2008.2009515 |язык=en}}
-* {{статья |автор=Duchi J. C., Agarwal A., Wainwright M. J. |заглавие=Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling |ссылка=https://doi.org/10.1109/TAC.2011.2161027 |издание=IEEE Transactions on Automatic Control |год=2012 |том=57 |номер=3 |страницы=592—606 |doi=10.1109/TAC.2011.2161027 |язык=en}}
-* {{статья |автор=Bregman L. M. |заглавие=The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming |ссылка=https://doi.org/10.1016/0041-5553(67)90040-7 |издание=USSR Computational Mathematics and Mathematical Physics |год=1967 |том=7 |номер=3 |страницы=200—217 |doi=10.1016/0041-5553(67)90040-7 |язык=en}}
-* {{статья |автор=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}}
-* {{статья |автор=Lemaréchal C. |заглавие=Bundle Methods in Nonsmooth Optimization |издание=Nonsmooth Optimization: Proceedings of an IIASA Workshop |год=1978 |страницы=79—102 |издательство=Pergamon Press |язык=en}}
-* {{статья |автор=Lemaréchal C., Nemirovskii A., Nesterov Y. |заглавие=New Variants of Bundle Methods |ссылка=https://doi.org/10.1007/BF01585555 |издание=Mathematical Programming |год=1995 |том=69 |номер=1 |страницы=111—147 |doi=10.1007/BF01585555 |язык=en}}
-* {{статья |автор=Nesterov Y. |заглавие=Smooth Minimization of Non-Smooth Functions |ссылка=https://doi.org/10.1007/s10107-004-0552-5 |издание=Mathematical Programming |год=2005 |том=103 |номер=1 |страницы=127—152 |doi=10.1007/s10107-004-0552-5 |язык=en}}
-* {{книга |автор=Clarke F. H. |заглавие=Optimization and Nonsmooth Analysis |издательство=Wiley |место=New York |год=1983 |isbn=978-0-471-87504-8 |язык=en}}
-* {{статья |автор=Davis D., Drusvyatskiy D. |заглавие=Stochastic Subgradient Method Converges at the Rate <tex>O(k^{-1/4})</tex> on Weakly Convex Functions |ссылка=https://doi.org/10.1137/18M1178244 |издание=SIAM Journal on Optimization |год=2019 |том=29 |номер=1 |страницы=207—239 |doi=10.1137/18M1178244 |язык=en}}
 [[Категория:Методы оптимизации]]