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

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

Версия от 18:53, 14 июля 2026; Aleksei Kovalenko (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

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

$\min_{x\in C} f(x),\qquad f^*=\inf_{x\in C}f(x),\qquad X^*={\rm argmin}_{x\in C}f(x).$

Если ограничения включены в функцию посредством индикатора $I_C$ , задача записывается как безусловная минимизация $f+I_C$ . Для количественных гарантий ниже явно предполагается, что $X^*\ne\emptyset$ , а используемые субградиенты ограничены по норме.

Субградиент и субдифференциал

Определение

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

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

Множество всех таких векторов называется субдифференциалом:

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

Вне эффективной области определения полагают $\partial f(x)=\emptyset$ . Это субдифференциал выпуклого анализа в смысле Моро—Рокафеллара.^[1]

Если $f$ дифференцируема в $x$ , то $\partial f(x)=\{\nabla f(x)\}$ . Обратное верно для выпуклой функции во внутренней точке области определения: одноэлементность субдифференциала эквивалентна дифференцируемости. Для собственной выпуклой функции субдифференциал непуст в каждой точке относительной внутренности ${\rm ri}({\rm dom}\,f)$ , но на границе он может быть пуст.

Геометрический смысл

Аффинная функция

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

является глобальной опорной снизу плоскостью к графику $f$ . Эквивалентно, гиперплоскость с нормалью $(g,-1)$ поддерживает эпиграф функции в точке $(x,f(x))$ . В точке излома опорных плоскостей обычно несколько; их наклоны и образуют $\partial f(x)$ .

Существование такой глобальной опоры существенно связано с выпуклостью. Если на открытом выпуклом множестве для каждой точки $x$ существует вектор $g_x$ , удовлетворяющий субградиентному неравенству для всех точек множества, то $f$ выпукла. Для произвольной невыпуклой функции касательная или локальная производная такого глобального неравенства, вообще говоря, не даёт.

Условие оптимальности и правила исчисления

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

$x^*\in{\rm argmin}\,f\quad\Longleftrightarrow\quad 0\in\partial f(x^*).$

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

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

где $N_C(x)$ — нормальный конус. При стандартном квалификационном условии, например наличии общей точки относительных внутренностей областей определения, справедливо правило суммы

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

Для линейного отображения при соответствующем условии регулярности

$\partial(f\circ A)(x)=A^{\rm T}\partial f(Ax).$

Если $f(x)=\max_{1\leq j\leq m} f_j(x)$ , где функции $f_j$ выпуклы и непрерывны в рассматриваемой точке, то

$\partial f(x)={\rm conv}\,\bigcup_{j\in I(x)}\partial f_j(x),\qquad I(x)=\{j:f_j(x)=f(x)\}.$

Для дифференцируемых $f_j$ это частный случай теоремы Данскина: можно взять градиент любой активной функции или их выпуклую комбинацию.^[1]

Элементарные примеры

Для абсолютного значения

$\partial |t|=\left\{\begin{array}{ll}\{-1\},&t<0,\\ [-1,1],&t=0,\\ \{1\},&t>0.\end{array}\right.$

Для нормы $\ell_2$

$\partial\|x\|_2=\left\{\begin{array}{ll}\{x/\|x\|_2\},&x\ne0,\\ \{g\mid\|g\|_2\leq1\},&x=0.\end{array}\right.$

Для нормы $\ell_1$ субдифференциал вычисляется покоординатно: при ненулевой координате получается её знак, при нулевой — любой элемент отрезка $[-1,1]$ .

Детерминированный субградиентный метод

Алгоритм

Для задачи без явных ограничений базовая итерация имеет вид

$x_{k+1}=x_k-\alpha_k g_k,\qquad g_k\in\partial f(x_k),\qquad \alpha_k>0.$

В отличие от градиентного спуска, направление $-g_k$ может не быть направлением локального убывания: возле излома метод способен перескакивать через множество решений, а значения $f(x_k)$ — возрастать. Анализ опирается не на лемму о гладкости, а на субградиентное неравенство.

Вход: начальная точка x_1, число итераций T, правило шага
для k = 1,...,T:
    получить g_k из субдифференциала f в x_k
    выбрать положительный шаг alpha_k
    x_{k+1} := x_k - alpha_k g_k
вернуть лучшую точку или взвешенное среднее итератов

Основное неравенство

Для любой оптимальной точки $x^*$

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

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

Выпуклый случай: оценка сходимости

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

$\bar x_T=\frac{\sum_{k=1}^T\alpha_kx_k}{\sum_{k=1}^T\alpha_k}$

выпуклость и телескопирование дают

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

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

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

даёт

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

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

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

Сильно выпуклый случай

Функция $f$ называется сильно выпуклой с параметром $\mu$ на $C$ , если для всех $x,y\in C$ и $g\in\partial f(x)$

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

Пусть дополнительно $\|g_k\|_2\leq G$ , а итерации проецируются на $C$ . При шагах

$\alpha_k=\frac{2}{\mu(k+1)}$

и усреднении с линейно растущими весами

$\tilde x_T=\frac{2}{T(T+1)}\sum_{k=1}^T kx_k$

справедлива оценка

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

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

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

Для явного ограничения $x\in C$ используется итерация

$x_{k+1}=\Pi_C(x_k-\alpha_kg_k),\qquad g_k\in\partial f(x_k),$

где $\Pi_C(z)={\rm argmin}_{x\in C}\|x-z\|_2$ . Проекция однозначна для непустого замкнутого выпуклого множества. Все приведённые выше выпуклые оценки сохраняются, если $R$ ограничивает расстояние начальной точки до решения, а $G$ — нормы выбранных субградиентов вдоль траектории.

Вход: 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

Не следует смешивать этот метод с проекционным градиентным методом: формула совпадает, но последний обычно предполагает дифференцируемую функцию с липшицевым градиентом и допускает существенно более быстрые гарантии. Если проекция на $C$ дорога, полезнее могут оказаться метод условного градиента, зеркальный спуск или специализированная параметризация ограничений.

Выбор шага

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

При постоянном шаге $\alpha_k=\alpha$ и $\|g_k\|\leq G$ из основной оценки следует

$\min_{1\leq k\leq T}(f(x_k)-f^*)\leq\frac{R^2}{2\alpha T}+\frac{\alpha G^2}{2}.$

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

Убывающие шаги

Классические условия

$\alpha_k>0,\qquad \sum_{k=1}^{\infty}\alpha_k=\infty,\qquad \sum_{k=1}^{\infty}\alpha_k^2<\infty$

выполняются, например, для $\alpha_k=a/(k+b)^p$ при $1/2<p\leq1$ . Если задача выпукла, множество решений непусто, итерации остаются в замкнутом выпуклом множестве и субградиенты равномерно ограничены, то значения лучших итератов сходятся к $f^*$ ; при стандартных условиях квазифейеровской монотонности расстояния до множества решений также сходятся, а предельные точки являются решениями. Условие суммируемости квадратов особенно важно в стохастическом случае для подавления шума. Шаг $\alpha_k=a/\sqrt{k}$ удобен для конечного горизонта и оптимальной оценки порядка $1/\sqrt T$ , но его квадраты не суммируются; это не противоречие, поскольку конечновременная оценка и почти наверное сходимость бесконечной шумной последовательности — разные утверждения.

Шаг Поляка

Если известно точное оптимальное значение, применяют

$\alpha_k=\frac{f(x_k)-f^*}{\|g_k\|_2^2},\qquad g_k\ne0.$

Тогда

$\|x_{k+1}-x^*\|_2^2\leq\|x_k-x^*\|_2^2-\frac{(f(x_k)-f^*)^2}{\|g_k\|_2^2}.$

При $\|g_k\|\leq G$ отсюда следует оценка для лучшего итерата порядка $GR/\sqrt T$ . Практическая трудность — необходимость знать $f^*$ . Подстановка завышенной нижней оценки может сделать числитель отрицательным, а слишком низкая оценка ведёт к чрезмерным шагам. Варианты с динамической оценкой уровня относятся к level-методам.^[1]

Нормированный шаг и поиск по линии

Иногда используют $x_{k+1}=x_k-\beta_k g_k/\|g_k\|$ . Это отделяет длину шага от масштаба субградиента, но не устраняет необходимость настраивать $\beta_k$ . Обычный точный поиск по линии менее естественен, чем в гладком спуске: субградиент не обязан задавать направление убывания, а минимум вдоль луча может находиться в нулевой точке.

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

Оракул и отличие от SGD

Пусть

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

или $f(x)=n^{-1}\sum_{i=1}^n f_i(x)$ . На итерации выбирается случайный вектор $G_k$ и выполняется

$x_{k+1}=\Pi_C(x_k-\alpha_kG_k).$

Корректная предпосылка несмещённости формулируется относительно истории $\mathcal F_k$ :

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

Если каждая $F(\cdot,\xi)$ выпукла и измерима, а условия интегрируемости разрешают перестановку математического ожидания и субдифференциала, то можно взять $G_k\in\partial_xF(x_k,\xi_k)$ для независимого примера $\xi_k$ .^[1]

Stochastic gradient descent в узком смысле использует несмещённую оценку обычного градиента дифференцируемой функции. Стохастический субградиентный метод допускает изломы и оценивает элемент субдифференциала. В литературе по машинному обучению обе схемы часто называют SGD; математически это допустимое сокращение только после явного задания оракула.

Гарантии в среднем

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

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

При $\alpha_k=R/(G\sqrt T)$ получается $\mathbb E[f(\bar x_T)-f^*]\leq RG/\sqrt T$ . Если $f$ дополнительно $\mu$ -сильно выпукла, то шаги $2/(\mu(k+1))$ и линейно-взвешенное усреднение дают

$\mathbb E[f(\tilde x_T)-f^*]\leq\frac{2G^2}{\mu(T+1)}.$

Это утверждения о математическом ожидании. Для оценки с вероятностью не менее $1-\delta$ нужны дополнительные хвостовые предпосылки — например, почти наверное ограниченные шум и диаметр множества либо условная субгауссовость. Тогда мартингальные неравенства дают добавку порядка $GR\sqrt{\log(1/\delta)/T}$ ; одной ограниченности второго момента для такой экспоненциальной зависимости от $\delta$ недостаточно.

При независимых мини-пакетах размера $b$ дисперсионная часть второго момента уменьшается примерно в $b$ раз, если индивидуальные ошибки независимы и имеют конечную дисперсию. Систематическое смещение оракула в базовую теорему не входит и обычно оставляет ненулевую ошибку.

Почти наверное сходимость

При условиях Роббинса—Монро на шаги, условной несмещённости, равномерно ограниченном условном втором моменте, непустом множестве решений и стандартных условиях ограниченности итератов стохастическая квазимартингальная аргументация даёт почти наверное сходимость значений к оптимальному и предельных точек к $X^*$ .^[1] Это асимптотический результат; он не заменяет конечновременную оценку ожидаемой ошибки.

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

Hinge loss и линейный SVM

Для размеченного объекта $(a,y)$ , где $y\in\{-1,1\}$ , hinge loss равна

$\ell(w;a,y)=\max\{0,1-y\langle w,a\rangle\}.$

Её субградиент по $w$ можно выбрать как

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

Прямая задача линейного SVM имеет вид

$\min_w\ \frac{\lambda}{2}\|w\|_2^2+\frac1n\sum_{i=1}^n\max\{0,1-y_i\langle w,a_i\rangle\}.$

При случайном выборе $i_k$ стохастический субградиент равен

$G_k=\lambda w_k-y_{i_k}a_{i_k}\,\mathbf{1}_{y_{i_k}\langle w_k,a_{i_k}\rangle<1}.$

Алгоритм Pegasos использует шаг $1/(\lambda k)$ и проекцию на шар радиуса $1/\sqrt\lambda$ ; сильная выпуклость квадратичного регуляризатора обеспечивает скорость порядка $1/T$ с логарифмическими оговорками, зависящими от выбранного выхода алгоритма.^[1]

L1-регуляризация

В задаче

$\min_w\ L(w)+\lambda\|w\|_1$

можно использовать субградиент $\nabla L(w)+\lambda s$ , где $s_j={\rm sign}(w_j)$ при $w_j\ne0$ и $s_j\in[-1,1]$ при $w_j=0$ . Однако обычный субградиентный шаг почти никогда не создаёт точных нулей и игнорирует известную структуру регуляризатора. Если $L$ гладка с липшицевым градиентом, проксимальный градиентный метод

$w_{k+1}={\rm soft}_{\alpha_k\lambda}(w_k-\alpha_k\nabla L(w_k))$

обычно предпочтительнее: мягкое пороговое преобразование даёт точную разреженность, а базовая скорость для выпуклой задачи составляет порядок $1/T$ , ускоренная — порядка $1/T^2$ .^[1]

Максимумы и робастные критерии

Функции вида $f(x)=\max_j f_j(x)$ возникают в многоклассовых margin-потерях, минимаксном обучении, робастной оптимизации и задачах с наихудшим сценарием. Субградиент активной ветви позволяет работать без сглаживания. При большом числе ветвей стоимость поиска точного максимума может доминировать; тогда применяют случайное приближение максимума, cutting-plane или bundle-методы, но смещение приближённого оракула следует учитывать отдельно.

Абсолютная и квантильная потери, $\ell_1$ -отклонения, нормы остатков и CVaR дают выпуклые негладкие робастные критерии. Для CVaR стандартное вариационное представление содержит положительную часть и потому допускает стохастические субградиенты по отдельным наблюдениям.^[1] Робастность статистического критерия не означает робастности самого стохастического оракула к тяжёлым хвостам: при бесконечном втором моменте приведённые оценки неприменимы, и требуются усечение, median-of-means или иные робастные агрегаторы.

Распределённое и федеративное обучение

Если $f(x)=\sum_{i=1}^m f_i(x)$ , а узел $i$ знает только $f_i$ , типичная консенсусная схема имеет вид

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

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

Связь с другими методами

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

У гладкой выпуклой функции субградиент совпадает с градиентом, но анализировать метод как субградиентный обычно невыгодно. Если $\nabla f$ липшицев с константой $L$ , градиентный спуск с шагом порядка $1/L$ имеет скорость порядка $1/T$ , а при сильной выпуклости — линейную. Общий субградиентный метод для липшицевой негладкой функции имеет лишь порядок $1/\sqrt T$ , либо $1/T$ при сильной выпуклости. Projected gradient — градиентный шаг плюс проекция при гладкой цели; projected subgradient — та же внешняя формула с негладким оракулом и другими гарантиями.

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

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

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

Для композитной задачи $F(x)=h(x)+r(x)$ , где $h$ гладка, а проксимальный оператор $r$ вычисляется эффективно, итерация

$x_{k+1}={\rm prox}_{\alpha r}(x_k-\alpha\nabla h(x_k))$

использует структуру $r$ точнее, чем единый субградиент $\nabla h+\partial r$ . Субградиентный метод оправдан, когда проксимальный оператор или декомпозиция недоступны, когда нужен крайне дешёвый потоковый шаг либо умеренная точность достаточна.

Зеркальный спуск

Зеркальный спуск заменяет евклидов квадрат расстояния дивергенцией Брэгмана и выполняет шаг в двойственной геометрии. Евклидов проекционный субградиентный метод — его частный случай. На симплексе энтропийная геометрия может заменить зависимость от размерности порядка $\sqrt d$ на $\sqrt{\log d}$ ; потому выбор нормы и прокс-функции является частью алгоритма, а не косметической заменой.^[1]^[1]

Bundle methods

Обычный метод забывает субградиент сразу после шага. Bundle-методы сохраняют набор опорных плоскостей

$f(y)\geq f(x_i)+\langle g_i,y-x_i\rangle$

и строят кусочно-линейную нижнюю модель, часто стабилизированную проксимальным членом. Они требуют больше памяти и решения вспомогательной задачи, зато обычно устойчивее и эффективнее при дорогом детерминированном оракуле высокой точности. Это естественный выбор для задач, где одно вычисление функции дорого, а число итераций важнее стоимости шага.^[1]^[1]

Сглаживание

Максимум или сопряжённое представление нередко можно заменить гладкой аппроксимацией с параметром $\tau$ . Возникает компромисс: ошибка аппроксимации порядка $\tau$ и константа Липшица градиента, растущая при $\tau\to0$ . Сглаживание Нестерова позволяет применять ускоренный градиентный метод и часто лучше при высокой требуемой точности, если структура максимума доступна.^[1]

Субградиент и обобщённые производные

Выпуклый субдифференциал не следует без оговорок переносить на невыпуклые функции. Для локально липшицевой невыпуклой функции используют субдифференциал Кларка, предельный субдифференциал Мордуховича и другие конструкции. У выпуклой локально липшицевой функции субдифференциал Кларка совпадает с выпуклым субдифференциалом; вне выпуклого случая глобальное опорное неравенство теряется, а условие $0\in\partial_C f(x)$ означает лишь обобщённую стационарность, не глобальный минимум.^[1]

Современная теория рассматривает слабо выпуклые функции, для которых $f(x)+(\rho/2)\|x\|^2$ выпукла. При ограниченном стохастическом оракуле подходящая мера стационарности — норма градиента оболочки Моро; для проекционного стохастического субградиентного метода получены оценки порядка $T^{-1/4}$ для этой нормы.^[1] Это расширение не является гарантией нахождения глобального минимума и не должно подменять классическую выпуклую теорию.

Практическая реализация

Выбор возвращаемой точки

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

Масштабирование и остановка

Ограничение $\|g_k\|\leq G$ зависит от масштаба признаков и выбранной нормы. Стандартизация признаков, предобусловливание, адаптивная диагональная геометрия или зеркальный спуск могут радикально изменить практику. Остановка только по норме выбранного субградиента ненадёжна: в точке излома оракул может вернуть ненулевой элемент даже при наличии нуля в субдифференциале. Более содержательны двойственный разрыв, известная нижняя граница, расстояние между модельными уровнями или устойчивость усреднённой цели.

Типичные ошибки

Считать $-g_k$ направлением убывания и требовать монотонности $f(x_k)$ .
Сообщать оценку для последнего итерата, когда теорема доказана только для среднего или лучшего.
Использовать скорость $1/T$ без сильной выпуклости либо без правильной схемы усреднения.
Называть градиент отдельного примера несмещённым, не проверив схему выборки, веса и возможность перестановки ожидания с субдифференциалом.
Выбрать в нуле для $\ell_1$ -штрафа произвольный знак вне $[-1,1]$ .
Забыть про проекцию или нормальный конус в задаче с ограничениями.
Применять шаг Поляка с неизвестным или неверным $f^*$ без защитного правила.
Переносить выпуклое субградиентное неравенство на невыпуклую нейросетевую функцию.
Сравнивать число итераций, игнорируя стоимость проекции, вычисления максимума, коммуникации и полного значения цели.

Когда метод оправдан

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

Предпочтительнее иной метод, если выполняется одно из условий:

негладкая часть имеет дешёвый проксимальный оператор — тогда обычно лучше проксимальный или проксимально-стохастический метод;
максимум допускает эффективное сглаживание и нужна высокая точность — полезен ускоренный метод для сглаженной цели;
оракул дорог и детерминирован — bundle-метод повторно использует накопленные опорные плоскости;
задача SVM умеренного размера имеет доступную двойственную структуру — coordinate descent или SMO часто быстрее общего субградиентного метода;
функция гладкая — следует использовать градиентный, ускоренный или variance-reduced метод с гарантиями, использующими гладкость;
нужна точная разреженность при $\ell_1$ -штрафе — проксимальный шаг естественнее;
задача невыпукла — необходимо явно выбрать понятие стационарности и теорию, соответствующую классу функции.

Исторические замечания

Первые систематические субградиентные алгоритмы связаны с работами Н. З. Шора и Б. Т. Поляка 1960-х годов.^[1]^[1] Классическая теория сформировалась в выпуклом анализе и негладкой оптимизации; позднее идеи вошли в стохастическую аппроксимацию, онлайн-обучение, зеркальный спуск и распределённые алгоритмы. Современные варианты для слабо выпуклых и иных невыпуклых классов расширяют область применения, но используют другие меры качества и не отменяют границ сложности классического липшицева выпуклого случая.

Примечания

Литература

Rockafellar R. T. Convex Analysis. — Princeton: Princeton University Press, 1970. — 451 с. — ISBN 978-0-691-01586-6
Danskin J. M. The Theory of Max-Min and Its Application to Weapons Allocation Problems. — Berlin, Heidelberg: Springer, 1967.
Polyak B. T. Minimization of Unsmooth Functionals // USSR Computational Mathematics and Mathematical Physics. — 1969. — Т. 9. — № 3. — С. 14—29.
Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. — Киев: Наукова думка, 1979. — 199 с.
Nemirovski A. S., Yudin D. B. Problem Complexity and Method Efficiency in Optimization. — New York: Wiley, 1983. — ISBN 978-0-471-10345-5
Bubeck S. Convex Optimization: Algorithms and Complexity // Foundations and Trends in Machine Learning. — 2015. — Т. 8. — № 3—4. — С. 231—357.
Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. — Boston: Kluwer Academic Publishers, 2004. — ISBN 978-1-4020-7553-7
Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust Stochastic Approximation Approach to Stochastic Programming // SIAM Journal on Optimization. — 2009. — Т. 19. — № 4. — С. 1574—1609.
Robbins H., Monro S. A Stochastic Approximation Method // The Annals of Mathematical Statistics. — 1951. — Т. 22. — № 3. — С. 400—407.
Shalev-Shwartz S., Singer Y., Srebro N., Cotter A. Pegasos: Primal Estimated Sub-Gradient Solver for SVM // Mathematical Programming. — 2011. — Т. 127. — № 1. — С. 3—30.
Beck A., Teboulle M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems // SIAM Journal on Imaging Sciences. — 2009. — Т. 2. — № 1. — С. 183—202.
Rockafellar R. T., Uryasev S. Optimization of Conditional Value-at-Risk // Journal of Risk. — 2000. — Т. 2. — № 3. — С. 21—41.
Nedić A., Ozdaglar A. Distributed Subgradient Methods for Multi-Agent Optimization // IEEE Transactions on Automatic Control. — 2009. — Т. 54. — № 1. — С. 48—61.
Duchi J. C., Agarwal A., Wainwright M. J. Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling // IEEE Transactions on Automatic Control. — 2012. — Т. 57. — № 3. — С. 592—606.
Bregman L. M. The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming // USSR Computational Mathematics and Mathematical Physics. — 1967. — Т. 7. — № 3. — С. 200—217.
Beck A., Teboulle M. Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization // Operations Research Letters. — 2003. — Т. 31. — № 3. — С. 167—175.
Lemaréchal C. Bundle Methods in Nonsmooth Optimization // Nonsmooth Optimization: Proceedings of an IIASA Workshop. — Pergamon Press, 1978. — С. 79—102.
Lemaréchal C., Nemirovskii A., Nesterov Y. New Variants of Bundle Methods // Mathematical Programming. — 1995. — Т. 69. — № 1. — С. 111—147.
Nesterov Y. Smooth Minimization of Non-Smooth Functions // Mathematical Programming. — 2005. — Т. 103. — № 1. — С. 127—152.
Clarke F. H. Optimization and Nonsmooth Analysis. — New York: Wiley, 1983. — ISBN 978-0-471-87504-8
Davis D., Drusvyatskiy D. Stochastic Subgradient Method Converges at the Rate $O(k^{-1/4})$ on Weakly Convex Functions // SIAM Journal on Optimization. — 2019. — Т. 29. — № 1. — С. 207—239.

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

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