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

Материал из 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»

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

Версия 11:05, 15 июля 2026 (править) Aleksei Kovalenko (Обсуждение \| вклад) ← К предыдущему изменению		Версия 11:12, 15 июля 2026 (править) (отменить) Aleksei Kovalenko (Обсуждение \| вклад) К следующему изменению →
Строка 1:		Строка 1:
-	{{well\|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko\|Aleksei Kovalenko]] 14:00, 15 июля 2026 (MSD)}}	+	{{well\|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko\|Aleksei Kovalenko]] 14:00, 15 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Субградиентные методы (оптимизация)]]}}
	{{TOCright}}		{{TOCright}}