Субградиентные методы 📐

Открой любую реализацию нейросети на PyTorch, поставь точку останова внутри torch.nn.ReLU и попробуй понять, что именно фреймворк возвращает в качестве производной функции $\text{ReLU}(x) = \max(0, x)$ ровно в точке $x = 0$. Формально у этой функции там излом: слева наклон графика равен нулю, справа — единице, и никакой единой касательной прямой, а значит и единой производной в классическом смысле, в этой точке не существует. Тем не менее обучение через ReLU работает миллионы раз в день на серверах по всему миру, обратное распространение ошибки (backpropagation) исправно считает какое-то число в этой точке и обучение прекрасно сходится. Этот урок — про то, что там на самом деле происходит математически, и почему это не хак и не обход правил, а строгая теория, которая существовала за десятилетия до появления глубокого обучения.

Проблема на самом деле шире, чем один излом в одной функции активации. Функция потерь $|x|$, лежащая в основе L1-регуляризации (Lasso), недифференцируема в нуле. Шарнирная функция потерь (hinge loss) $\max(0, 1 - y f(x))$, на которой обучаются машины опорных векторов (SVM), недифференцируема в точке, где отступ (margin) равен единице. Сама ReLU недифференцируема в нуле. Все три примера объединяет одна и та же структура: гладкая выпуклая функция с одним-единственным «острым углом», где вместо одной касательной прямой к графику можно провести целый веер из них — и все они будут лежать не выше графика функции. Этот урок даёт язык, чтобы говорить об этом строго: субградиент как обобщение градиента для точек излома, субдифференциал как множество всех «подходящих» наклонов сразу, и субградиентный метод спуска — прямое обобщение обычного градиентного спуска, которое использует один любой субградиент вместо единственной несуществующей производной.

Дальше выяснится, что субградиентный метод — с виду точная копия градиентного спуска по формуле шага — на самом деле ведёт себя качественно иначе. Он не гарантирует убывания функции потерь на каждой отдельной итерации, сходится заметно медленнее гладкого градиентного спуска, и требует отдельно отслеживать не последнюю посещённую точку, а лучшую из всех увиденных за всю оптимизацию. Это не второстепенные детали, а вещи, которые напрямую объясняют, почему графики обучения SVM с hinge loss или Lasso-регрессии выглядят более «шумно», чем графики обучения гладких моделей, и почему инженеры библиотек машинного обучения принимают конкретные, зафиксированные в коде решения о том, какое именно число вернуть в качестве «производной» ReLU в нуле.

История

Понятие субградиента родилось не в машинном обучении, а в выпуклом анализе — разделе математики, изучающем свойства выпуклых множеств и выпуклых функций, который бурно развивался в середине XX века на стыке оптимизации, экономики и теории игр. Ключевую роль сыграл Жан-Жак Моро (Jean-Jacques Moreau), французский математик, который в начале 1960-х годов систематически исследовал свойства выпуклых функций, не предполагающих гладкости, и заложил многие базовые конструкции современного негладкого анализа, включая идеи, тесно связанные с субдифференциалом.

Строгую и наиболее влиятельную формализацию субдифференциала как множества всех субградиентов дал американский математик Ральф Тайрелл Рокафеллар (R. Tyrrell Rockafellar). Его монография «Convex Analysis», впервые опубликованная в 1970 году, стала для целого поколения математиков и специалистов по оптимизации тем же, чем «Начала» Евклида были для геометрии, — исчерпывающим, строгим и невероятно влиятельным систематическим изложением предмета. Именно в этой книге понятие субдифференциала получило ту форму определения через опорную линейную функцию, которую используют по сей день.

Практический алгоритм — субградиентный метод спуска — независимо предложили в конце 1960-х – начале 1970-х годов сразу несколько исследователей из советской и западной школ выпуклой оптимизации, среди них Наум Шор, украинский математик, чьи работы по методам негладкой оптимизации на десятилетия опередили тот момент, когда эти методы стали массово востребованы. Долгое время субградиентный метод оставался предметом узкоспециализированного интереса теоретиков оптимизации — до тех пор, пока в 2000-е и особенно в 2010-е годы не случился взрывной рост интереса к задачам с негладкими функциями потерь: сначала SVM с hinge loss, затем Lasso-регрессия с $L_1$-штрафом, а затем и глубокие нейросети с ReLU-подобными активациями сделали субградиентный подход одним из фундаментальных строительных блоков современного машинного обучения — уже не экзотикой, а инструментом, который незримо работает внутри почти каждой обучающейся сети.

Проблема недифференцируемости и определение субградиента

Интуиция

Обычная производная $f'(x_0)$ в точке $x_0$ — это единственное число: угловой коэффициент единственной прямой, касающейся графика функции именно в этой точке и нигде больше локально не пересекающей график «снизу». Для гладкой выпуклой функции такая прямая всегда одна, и она всегда лежит целиком не выше графика функции — это, собственно, геометрическое определение выпуклости через касательные. Проблема начинается там, где график функции делает острый излом: слева от точки излома наклон один, справа — другой, и никакой единственной касательной прямой там не существует. Но выпуклость точки излома не отменяет — график всё ещё «выпукло изогнут», просто в этой конкретной точке подходит не одна прямая-опора, а сразу целый пучок прямых.

Вот ключевая идея, которая спасает ситуацию: если обычная производная определяется как единственный наклон касательной, то субградиент определяется мягче — это любой наклон прямой, проходящей через точку $(x_0, f(x_0))$ и лежащей целиком не выше графика функции. Для гладкой точки такая прямая ровно одна — и субградиент совпадает с обычной производной. Но в точке излома таких прямых может быть много, и любая из них по праву называется субградиентом.

Формальное определение

Субградиент выпуклой функции. Пусть $f: \mathbb{R}^n \to \mathbb{R}$ — выпуклая функция. Вектор $g \in \mathbb{R}^n$ называется субградиентом функции $f$ в точке $x$, если для всех $y \in \mathbb{R}^n$ выполняется неравенство

$$f(y) \ge f(x) + g^\top (y - x)$$

Субдифференциал (subdifferential) $\partial f(x)$ — это множество всех субградиентов функции $f$ в точке $x$:

$$\partial f(x) = \{\, g \in \mathbb{R}^n : f(y) \ge f(x) + g^\top (y - x) \text{ для всех } y \,\}$$

Смысл неравенства предельно конкретный: линейная функция $\ell(y) = f(x) + g^\top(y-x)$ — это прямая (или гиперплоскость в многомерном случае), проходящая через точку касания $(x, f(x))$; условие $f(y) \ge \ell(y)$ для всех $y$ говорит, что эта прямая нигде не поднимается выше графика функции — она опорная (support line) к графику. Субдифференциал — это не одно число, а целое множество всех наклонов, для которых опорное свойство выполняется. Важный факт, который стоит запомнить сразу: если $f$ дифференцируема в точке $x$ в обычном смысле, то $\partial f(x)$ состоит ровно из одного элемента — обычного градиента $\nabla f(x)$, и никакого противоречия с привычным анализом не возникает.

Пример 1: полный разбор субдифференциала $|x|$ в нуле

Разберём модельный пример до конца, потому что он лежит в основе интуиции обо всех дальнейших случаях. Функция $f(x) = |x|$ выпукла на всей прямой. При $x > 0$ она совпадает с $x$, и производная там равна $1$; при $x < 0$ она совпадает с $-x$, и производная там равна $-1$. В точке $x=0$ обычной производной нет — предел разностного отношения слева даёт $-1$, справа даёт $1$, и они не совпадают.

Найдём субдифференциал $\partial f(0)$ напрямую из определения. Нужно найти все числа $g$, для которых $f(y) \ge f(0) + g \cdot (y - 0)$ при всех $y$, то есть $|y| \ge g y$ для всех $y \in \mathbb{R}$. Проверим это условие раздельно для $y > 0$ и $y < 0$:

• при $y > 0$: неравенство $|y| \ge g y$ превращается в $y \ge gy$, то есть $1 \ge g$ (делим на положительное $y$);
• при $y < 0$: неравенство $|y| \ge gy$ превращается в $-y \ge gy$, то есть $-1 \le g$ (делим на отрицательное $y$, знак неравенства переворачивается).

Оба условия вместе дают $-1 \le g \le 1$. Значит,

Субдифференциал в нуле — это не одно число, а целый отрезок $[-1, 1]$: любое число из этого промежутка — законный субградиент. Геометрически это означает, что через точку излома графика $|x|$ в начале координат можно провести бесконечно много прямых с наклоном от $-1$ до $1$ включительно, и каждая из них будет опорной — нигде не поднимется выше «уголка» графика. При $x \ne 0$ субдифференциал вырождается в одноточечное множество: $\partial|x| = \{1\}$ при $x>0$ и $\partial|x| = \{-1\}$ при $x<0$, полностью совпадая с обычной производной.

Пример 2: полный разбор субдифференциала ReLU в нуле

Теперь тот самый практический случай, ради которого этот урок особенно важен для машинного обучения. Функция $\text{ReLU}(x) = \max(0, x)$ выпукла (как максимум двух линейных функций — константы $0$ и прямой $x$). При $x > 0$ она совпадает с $x$, производная равна $1$; при $x < 0$ она тождественно равна нулю, производная равна $0$. В точке $x=0$ снова излом: слева наклон $0$, справа наклон $1$.

Повторим тот же приём: ищем все $g$, для которых $\max(0, y) \ge g y$ при всех $y$.

• при $y > 0$: $\max(0,y) = y$, неравенство $y \ge gy$ даёт $g \le 1$;
• при $y < 0$: $\max(0,y) = 0$, неравенство $0 \ge gy$ при отрицательном $y$ даёт $g \ge 0$ (делим на отрицательное число, знак переворачивается: $g \le 0/y = 0$... аккуратнее: $0 \ge gy$, $y<0$, делим обе части на $y$ и меняем знак неравенства: $0 \le g$, то есть $g \ge 0$).

Вместе получаем $0 \le g \le 1$:

Это ровно та математическая структура, которая стоит за практическим поведением фреймворков глубокого обучения. PyTorch, TensorFlow и другие библиотеки при вычислении обратного прохода (backpropagation) через ReLU в точке $x=0$ обязаны вернуть какое-то одно конкретное число — не могут же они хранить и распространять дальше целый отрезок значений. Они берут одно фиксированное значение из субдифференциала $[0,1]$ — по факту чаще всего $0$ (реже встречается реализация с $1$; в некоторых версиях используется $0{,}5$ — среднее значение отрезка). Любой из этих выборов математически корректен, потому что любое число из $[0,1]$ — законный субградиент. На практике эта точка встречается на входе конкретного нейрона крайне редко (вероятность того, что взвешенная сумма входов попадёт ровно в ноль на вещественных числах, исчезающе мала), так что выбор конкретного значения почти никогда не влияет на итоговое качество обучения — но сам факт того, что выбор вообще нужно делать, и что он корректен именно благодаря теории субградиента, а не случайно, стоит понимать явно.

Пример 3: субдифференциал hinge loss в SVM

Третий важный для машинного обучения пример — шарнирная функция потерь (hinge loss), на которой обучаются машины опорных векторов:

где $z$ — отступ (margin), $y \in \{-1, +1\}$ — истинная метка, $f(x)$ — выход модели. Как функция от $z$, hinge loss устроена в точности как ReLU, только отражённая и сдвинутая: при $z > 1$ она равна нулю (производная $0$), при $z < 1$ равна $1-z$ (производная $-1$), а в точке $z = 1$ — снова точка излома.

Тем же приёмом, что и в двух предыдущих примерах, легко получить:

На практике в реализациях SVM с субградиентным обучением (например, в вариантах стохастического субградиентного спуска для линейного SVM) в этой пограничной точке $z=1$ — то есть когда объект оказывается ровно на границе разделяющей полосы — используется одно фиксированное значение из этого отрезка, обычно $0$ или $-1$, точно по тому же принципу, что и с ReLU. Важная деталь: полный градиент по параметрам модели $w$ получается через цепное правило из $\partial L(z)$ и градиента $z$ по $w$, и там же встречается второе слагаемое — производная от $L_2$-регуляризатора $\tfrac{\lambda}{2}\|w\|^2$, которая гладкая и не создаёт никаких дополнительных проблем.

Почему это важно

То, что в трёх, казалось бы, совершенно разных контекстах — активация ReLU в нейросети, разделяющая граница в SVM и регуляризация Lasso — возникает одна и та же математическая структура точки излома с отрезком субградиентов, не случайность. Это глубоко системное явление: выпуклые функции с кусочно-линейными «уголками» повсеместны в современном машинном обучении, потому что кусочно-линейные конструкции дёшево вычисляются и хорошо ведут себя при композиции. Субградиент — это не костыль для обхода математической проблемы, а строгий, самостоятельный математический объект, который позволяет применять весь аппарат выпуклой оптимизации к функциям, для которых классический анализ формально бессилен.

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

Интуиция

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

Формальное определение

Геометрическая характеризация субдифференциала. Вектор $g \in \partial f(x)$ тогда и только тогда, когда гиперплоскость

$$H = \{\,(y, t) \in \mathbb{R}^n \times \mathbb{R} : t = f(x) + g^\top(y-x)\,\}$$

является опорной к надграфику (epigraph) функции $f$, $\text{epi}(f) = \{(y,t): t \ge f(y)\}$, в точке $(x, f(x))$ — то есть весь надграфик лежит по одну сторону от этой гиперплоскости.

Эта формулировка — не альтернатива алгебраическому определению из предыдущего раздела, а его геометрический двойник: множество субградиентов в точке $x$ в точности соответствует множеству углов наклона всех опорных гиперплоскостей к надграфику функции в точке $(x, f(x))$. Для гладкой точки надграфик имеет единственную касательную опорную гиперплоскость. Для точки излома надграфик имеет там «ребро» — и опорных гиперплоскостей, касающихся этого ребра, оказывается бесконечно много, образующих целый веер.

Примеры

Пример 1: визуализация веера опорных прямых для $|x|$ в нуле. Возьмём три конкретных субградиента из отрезка $[-1,1]$, найденного ранее: $g_1 = -1$, $g_2 = 0$, $g_3 = 1$. Опорные прямые: $\ell_1(y) = 0 + (-1)(y-0) = -y$, $\ell_2(y) = 0$, $\ell_3(y) = y$. Проверим, что каждая лежит не выше графика $|y|$ при всех $y$: для $\ell_1(y) = -y$ нужно $|y| \ge -y$ — верно всегда, поскольку $|y| \ge -y$ равносильно $|y| + y \ge 0$, что выполняется для любого $y$ (при $y \ge 0$ сумма равна $2y \ge 0$, при $y<0$ равна $0$). Аналогично проверяется $\ell_2$ и $\ell_3$. Все три прямые касаются графика ровно в начале координат и нигде не поднимаются выше него — визуально это выглядит как веер прямых, зажатый между линией $y=-x$ снизу-слева и линией $y=x$ снизу-справа, все они «подпирают» уголок графика $|x|$ одновременно.

Пример 2: почему субградиент вне точки излома единственный. Возьмём точку $x_0 = 3 > 0$ на графике $f(x)=|x|$. Здесь $f$ гладкая, и единственный субградиент — обычная производная $f'(3) = 1$. Геометрически: любая прямая с наклоном, отличным от $1$, проходящая через точку $(3,3)$, неизбежно окажется выше графика $|x|$ где-то рядом — либо сразу слева, либо сразу справа от точки $3$, потому что график там представляет собой прямую линию с фиксированным наклоном $1$, и никакая другая прямая, кроме самой этой линии, не может лежать не выше неё на всём протяжении. Это подтверждает общий факт: в точках гладкости субдифференциал вырождается ровно в один элемент.

Пример 3: двумерный аналог — субдифференциал нормы $\|x\|_2$ в нуле. Возьмём функцию $f(x) = \|x\|_2$ на $\mathbb{R}^2$ — евклидову длину вектора. Она выпукла и гладкая всюду, кроме начала координат, где график представляет собой вершину конуса. В точке $x=0$ субдифференциал — это не отрезок, а целый круг единичного радиуса: $\partial f(0) = \{g \in \mathbb{R}^2 : \|g\|_2 \le 1\}$. Геометрическая интерпретация та же самая, только гиперплоскости опоры теперь касаются не «уголка» на плоскости, а вершины конуса в трёхмерном пространстве, и множество допустимых наклонов образует не отрезок, а целый диск — обобщение одномерного отрезка $[-1,1]$ на два измерения. Этот пример полезно держать в голове, потому что $L_2$-норма и её субдифференциал в нуле участвуют, например, в групповой регуляризации (group lasso).

Почему это важно

Геометрическая картина через опорные прямые — это не просто красивая иллюстрация, а рабочий инструмент проверки: если тебе нужно быстро понять, является ли данный вектор $g$ субградиентом в подозрительной точке, не всегда обязательно решать неравенство алгебраически — достаточно представить, ляжет ли прямая с этим наклоном не выше графика в окрестности точки. Эта интуиция особенно ценна при работе с составными негладкими функциями (суммой гладкой части и негладкого регуляризатора вроде $L_1$-штрафа), где полный субдифференциал суммы функций часто оказывается суммой субдифференциалов слагаемых, и удобно представлять себе, как складываются соответствующие веера опорных прямых.

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

Интуиция

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

Формальное определение

Субградиентный метод спуска (subgradient method). Дана выпуклая, не обязательно гладкая функция $f$. Начиная с произвольной точки $x_0$, на каждой итерации выбирается любой субградиент $g_k \in \partial f(x_k)$ и делается шаг

$$x_{k+1} = x_k - \alpha_k\, g_k$$

где $\alpha_k > 0$ — длина шага. В отличие от градиентного спуска, шаг $\alpha_k$ здесь чаще всего выбирают заранее по расписанию (убывающая последовательность вроде $\alpha_k = c/\sqrt{k}$ или $\alpha_k = c/k$), а не через линейный поиск, потому что убывания функции на шаге никто не гарантирует — линейный поиск, ищущий наилучший шаг вдоль направления $-g_k$, здесь теряет часть своего теоретического обоснования.

Формула выглядит буквально как формула градиентного спуска с заменой $\nabla f(x_k)$ на $g_k$ — и в этом одновременно и вся элегантность метода, и источник путаницы для новичков. Элегантность в том, что реализовать субградиентный метод поверх уже существующего кода градиентного спуска почти не требует изменений: достаточно подставить любой субградиент там, где раньше стоял градиент. Путаница в том, что интуиция «маленький шаг против градиента гарантированно немного снижает функцию», прочно усвоенная на гладком случае, здесь перестаёт работать.

Пример 1: субградиентный шаг для $f(x) = |x|$, стартуя из точки излома

Возьмём $f(x) = |x|$, старт $x_0 = 0$ — прямо в точке излома. Выберем субградиент $g_0 = 0{,}5$ (законный выбор, поскольку $0{,}5 \in [-1,1]$) и шаг $\alpha_0 = 1$. Шаг метода: $x_1 = x_0 - \alpha_0 g_0 = 0 - 1 \cdot 0{,}5 = -0{,}5$. Значение функции: $f(x_0) = 0$, $f(x_1) = |{-0{,}5}| = 0{,}5$ — функция выросла, хотя формально шаг был сделан «против субградиента». Если бы вместо $g_0=0{,}5$ выбрать $g_0 = -0{,}5$ (тоже законный субградиент), шаг привёл бы в $x_1 = 0{,}5$ — с тем же самым ростом функции до $0{,}5$. Это прямая иллюстрация того, почему субградиентный метод не является методом спуска в строгом смысле: даже из самой «правильной» стартовой точки — минимума функции — один шаг метода уводит от минимума и увеличивает значение функции, просто потому что субградиент в точке излома не указывает однозначного «правильного» направления.

Пример 2: неубывание функции продолжается и вдали от излома. Возьмём $f(x) = |x|$, старт $x_0 = 3$ (гладкая точка, субградиент единственный и равен обычной производной $g_0 = 1$), но выберем нарочно слишком большой шаг $\alpha_0 = 5$. Тогда $x_1 = 3 - 5 \cdot 1 = -2$, и $f(x_1) = |-2| = 2 > f(x_0) = 3$... на самом деле $2 < 3$, здесь функция убыла. Возьмём шаг ещё больше, $\alpha_0 = 10$: $x_1 = 3 - 10 = -7$, $f(x_1)=7 > 3$ — вот теперь функция выросла. Разница с обычным гладким градиентным спуском принципиальная: там при достаточно малом шаге рост функции исключён теоремой о достаточном убывании, а здесь даже сколь угодно малый шаг из точки $x_0=0$ (пример 1) уже приводит к росту — потому что дело не в размере шага, а в самой природе точки излома, где субградиент — лишь один из целого веера возможных направлений, и он в общем случае просто не является направлением локального убывания функции.

Пример 3: последовательность шагов с убывающей длиной шага сходится, но немонотонно. Возьмём $f(x)=|x|$, старт $x_0=4$, расписание шага $\alpha_k = 1/(k+1)$ (при $k=0,1,2,\dots$), и всегда выбираем субградиент, равный обычной производной там, где она есть. Шаг 0: $g_0 = 1$ (поскольку $x_0=4>0$), $\alpha_0=1$, $x_1 = 4-1\cdot1=3$, $f=3$. Шаг 1: $g_1=1$, $\alpha_1=0{,}5$, $x_2=3-0{,}5=2{,}5$, $f=2{,}5$. Шаг 2: $g_2=1$, $\alpha_2\approx0{,}333$, $x_3\approx2{,}167$, $f\approx2{,}167$. Пока точка остаётся в положительной полуплоскости, последовательность монотонно убывает — но стоит траектории случайно перескочить через $x=0$ при слишком большом относительно текущего $|x_k|$ шаге, значение функции на этом шаге подскочит, прежде чем убывающий шаг снова «пригасит» колебания. Именно такое немонотонное, «дёргающееся» поведение траектории функции — типичная визуальная черта графиков обучения моделей с hinge loss или $L_1$-регуляризацией по сравнению с гладко убывающими кривыми обучения при квадратичных потерях.

Почему это важно

Осознание того, что субградиентный метод — не метод спуска в строгом смысле, напрямую меняет то, как нужно читать графики обучения на практике. Если ты видишь, что кривая функции потерь SVM с hinge loss или Lasso-регрессии временами подскакивает вверх на несколько итераций подряд перед тем, как продолжить общее снижение, это не обязательно баг в коде и не обязательно слишком большая скорость обучения (learning rate) — это может быть совершенно ожидаемое, математически объяснимое поведение субградиентного метода вблизи точек излома функции потерь. Понимание этого спасает часы отладки, потраченные на охоту за несуществующей ошибкой.

Скорость сходимости и необходимость отслеживать лучшее значение

Интуиция

У обычного градиентного спуска на гладких выпуклых функциях с константой Липшица для градиента есть строгая теоретическая гарантия скорости сходимости порядка $O(1/k)$ — после $k$ итераций разрыв между текущим значением функции и минимумом убывает пропорционально $1/k$. У субградиентного метода на негладких выпуклых функциях аналогичная гарантия заметно слабее — порядка $O(1/\sqrt{k})$. Разница между этими двумя скоростями на практике огромна: чтобы получить точность в десять раз лучше, гладкому градиентному спуску нужно примерно в десять раз больше итераций, а субградиентному методу — примерно в сто раз больше. Негладкость не просто «немного мешает» — она принципиально ограничивает, насколько быстро вообще можно гарантированно приближаться к минимуму в худшем случае.

Формальное определение

Скорость сходимости субградиентного метода. Пусть $f$ выпукла, субградиенты ограничены по норме константой $G$ (то есть $\|g_k\| \le G$ для всех итераций), и шаг выбран по расписанию $\alpha_k = c/\sqrt{k+1}$. Тогда для лучшего найденного значения за первые $k$ итераций

$$f_{\text{best}}^{(k)} = \min_{0 \le i \le k} f(x_i)$$

выполняется оценка сходимости

$$f_{\text{best}}^{(k)} - f^\ast = O\!\left(\frac{1}{\sqrt{k}}\right)$$

где $f^\ast$ — истинный минимум функции. Обрати внимание: оценка сформулирована именно для лучшего значения среди всех посещённых точек, а не для значения в последней точке $f(x_k)$.

Последняя деталь определения — не техническая мелочь, а важнейшая практическая инструкция к реализации. Поскольку метод немонотонен и может временно уходить от минимума (как показал пример 1 из предыдущего раздела), значение $f(x_k)$ в самой последней точке итерации в принципе может оказаться заметно хуже, чем значение в какой-то из предыдущих точек. Теоретические гарантии сходимости доказываются именно для минимума по всей истории, а значит и практическая реализация обязана отдельно хранить и обновлять лучшее найденное значение (best iterate) — иначе можно на выходе из цикла оптимизации вернуть точку, которая заметно хуже той, что метод уже успел посетить несколькими шагами раньше.

Примеры

Пример 1: конкретный расчёт числа итераций для заданной точности. Пусть $G = 10$ (типичная оценка нормы субградиентов для не слишком экзотичной задачи), начальное расстояние до минимума $\|x_0 - x^\ast\| = R = 5$, и нужна точность $\varepsilon = 0{,}1$. Классическая оценка для субградиентного метода с оптимально подобранным постоянным шагом даёт число итераций порядка $k = O\!\left(\dfrac{R^2 G^2}{\varepsilon^2}\right) = \dfrac{25 \cdot 100}{0{,}01} = 250\,000$. Для сравнения: гладкий градиентный спуск при сопоставимых константах требовал бы порядка $R^2 L / \varepsilon$ итераций (где $L$ — константа Липшица градиента), что при тех же порядках величин легко может быть на два-три порядка меньше. Разница в требуемом числе итераций — это прямая, ощутимая на практике цена негладкости.

Пример 2: почему $f(x_k)$ может быть хуже $f_{\text{best}}^{(k)}$ на порядок. Продолжим числовой пример 3 из предыдущего раздела с $f(x)=|x|$, стартом $x_0=4$ и шагом $\alpha_k = 1/(k+1)$. Допустим, что где-то на итерации 50 траектория оказалась очень близко к нулю, скажем $x_{50} = 0{,}02$, $f(x_{50}) = 0{,}02$ — это отличное, близкое к минимуму значение. Но следующий субградиентный шаг с ещё не успевшим стать совсем маленьким $\alpha_{50}$ может перебросить точку через ноль в область с бо́льшим по модулю $x$, скажем $x_{51} = -0{,}3$, $f(x_{51}) = 0{,}3$ — в пятнадцать раз хуже, чем было мгновение назад. Если бы алгоритм наивно возвращал только последнюю точку $x_{51}$, он бы «потерял» уже найденное отличное решение $x_{50}$. Именно поэтому правильная реализация обязана на каждой итерации сравнивать $f(x_k)$ с текущим рекордом $f_{\text{best}}$ и обновлять рекорд только при улучшении, а в конце возвращать не $x_k$, а $x_{\text{best}}$.

Пример 3: как отслеживание лучшего значения выглядит в псевдокоде. Практическая реализация субградиентного метода выглядит примерно так:

x = x0
f_best = f(x0)
x_best = x0

for k in range(K):
    g = subgradient(f, x)      # любой субградиент в текущей точке
    alpha = c / sqrt(k + 1)    # убывающий шаг
    x = x - alpha * g
    if f(x) < f_best:
        f_best = f(x)
        x_best = x

return x_best, f_best

Обрати внимание: строчки if f(x) < f_best — это не защитное программирование «на всякий случай», а прямое, обязательное следствие теоремы о сходимости $O(1/\sqrt{k})$, сформулированной именно для минимума по истории. Без этих двух строчек код будет технически исполняться, но теоретическая гарантия сходимости, ради которой метод вообще применяют, перестанет быть применима к тому, что этот код фактически возвращает.

Почему это важно

Скорость сходимости $O(1/\sqrt{k})$ вместо $O(1/k)$ — не абстрактная теоретическая деталь, а прямое практическое основание для того, почему во многих современных библиотеках машинного обучения для задач с негладкими функциями потерь (SVM, Lasso) предпочитают не наивный субградиентный метод, а более продвинутые подходы — например, проксимальные методы из следующего урока, которые для многих практически важных негладких функций (в том числе для $L_1$-регуляризации) восстанавливают скорость сходимости $O(1/k)$ и даже быстрее, обрабатывая негладкую часть функции особым, более аккуратным способом, а не просто «подставляя субградиент туда, где раньше был градиент».

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Дана функция $f(x) = |x|$. Вычисли обычную производную $f'(x)$ при $x = 5$ и при $x = -3$.

Задание 2: Проверь по определению, является ли число $g = 2$ субградиентом функции $f(x) = |x|$ в точке $x = 0$.

Задание 3: Является ли число $g = -0{,}7$ субградиентом функции $f(x)=|x|$ в точке $x=0$?

Задание 4: Найди субдифференциал $\partial\,\text{ReLU}(x)$ в точке $x = 5$ и в точке $x=-2$.

Задание 5: Чему равен субдифференциал $\partial\,\text{ReLU}(0)$? Опиши его как множество.

Задание 6: Сделай один шаг субградиентного метода для $f(x)=|x|$ из точки $x_0=2$ с шагом $\alpha_0=0{,}5$, используя обычную производную как субградиент.

Задание 7: Дана функция $f(x) = |x|$, старт $x_0=0$, выбран субградиент $g_0=1$, шаг $\alpha_0=0{,}3$. Вычисли $x_1$ и сравни $f(x_1)$ с $f(x_0)$.

Задание 8: Даны значения функции потерь по итерациям: $f(x_0)=5$, $f(x_1)=3$, $f(x_2)=4$, $f(x_3)=2$, $f(x_4)=2{,}5$. Найди $f_{\text{best}}^{(4)}$.

Задание 9: Вычисли значение шага по расписанию $\alpha_k = 1/\sqrt{k+1}$ для $k=0$, $k=3$ и $k=99$.

Задание 10: Объясни своими словами, в чём главное отличие субградиента от обычного градиента.

Продвинутые задания (11–20)

Задание 11: Докажи по определению, что $g=1$ является субградиентом $f(x)=|x|$ в точке $x=0{,}5$ (гладкая точка).

Задание 12: Найди субдифференциал функции $f(x) = 2|x|$ в точке $x=0$ (используй линейность субдифференциала при умножении на положительную константу: $\partial(cf)(x) = c\,\partial f(x)$ при $c>0$).

Задание 13: Найди субдифференциал функции $f(x) = |x| + x^2$ в точке $x=0$ (используй правило: субдифференциал суммы гладкой и негладкой функции — это субдифференциал негладкой части плюс обычный градиент гладкой части в этой точке).

Задание 14: Дана шарнирная функция потерь $L(z) = \max(0, 1-z)$. Найди $\partial L(z)$ при $z=2$, при $z=0$ и при $z=1$.

Задание 15: Смоделируй два шага субградиентного метода для $f(x)=|x|$, старт $x_0=1$, шаг $\alpha_k = 1/(k+1)$, субградиент всегда равен обычной производной там, где она существует.

Задание 16: Оцени число итераций субградиентного метода, необходимое для точности $\varepsilon=0{,}01$, если константа субградиентов $G=5$ и начальное расстояние до минимума $R=2$, используя оценку $k = O(R^2G^2/\varepsilon^2)$.

Задание 17: Для гладкого градиентного спуска со скоростью сходимости $O(1/k)$ и той же требуемой точностью $\varepsilon=0{,}01$ (упрощённо считая константы равными единице) оцени порядок числа итераций $k \sim 1/\varepsilon$ и сравни с ответом предыдущего задания.

Задание 18: Объясни, почему для субградиентного метода обычно не используют линейный поиск (line search) вдоль направления $-g_k$ так, как это делают для градиентного спуска.

Задание 19: В реализации torch.nn.ReLU производная в нуле возвращается как одно фиксированное число. Объясни, почему любой выбор числа из $[0,1]$ математически корректен, но конкретное числовое значение всё равно приходится "зашивать" в код.

Задание 20: Дана функция $f(x,y) = |x| + |y|$ (используется как $L_1$-регуляризатор с двумя параметрами). Найди субдифференциал $\partial f(0,0)$.

Задания-челленджи (21–30)

Задание 21: Функция потерь модели строится как $F(w) = \frac{1}{2}\|Xw-y\|_2^2 + \lambda\|w\|_1$ (Lasso). Объясни, какая часть этой функции гладкая, а какая требует субградиента, и почему для полного градиента/субградиента $\partial F$ нужно складывать вклад обеих частей.

Задание 22: Почему при обучении SVM с hinge loss стохастическим субградиентным методом (SGD с субградиентами по мини-батчам) график функции потерь на обучающей выборке обычно выглядит более "зашумлённым" и немонотонным, чем при обучении гладкой модели тем же SGD?

Задание 23: Приведи контрпример, показывающий, что для невыпуклой функции определение субградиента через неравенство $f(y) \ge f(x) + g^\top(y-x)$ для всех $y$ может не иметь решений вообще ни для одного $g$.

Задание 24: Функция $f(x) = -|x|$ (вогнутая версия модуля). Есть ли у неё субградиент в нуле в смысле определения, данного в уроке (для выпуклых функций)?

Задание 25: Реализация (псевдокод) наивно возвращает $x_K$ — точку после последней итерации — вместо $x_{\text{best}}$. Опиши конкретный сценарий (например, на функции $|x|$), где это приводит к тому, что возвращённое решение заметно хуже, чем то, которое алгоритм фактически "видел" по пути.

Задание 26: Выведи (по аналогии с разбором для $|x|$ и ReLU в уроке) субдифференциал функции $f(x) = \max(x, 2x)$ в точке $x=0$.

Задание 27: Объясни, почему при $m>1$ кусочно-линейных "кусков", сходящихся в одной точке (как в задании 26, только с тремя и более линейными функциями под максимумом), субдифференциал в точке излома — это по-прежнему отрезок (а не более сложное множество) на прямой $\mathbb{R}$, но не обязательно на $\mathbb{R}^n$ при $n>1$.

Задание 28: SVM с hinge loss обучается субградиентным методом на выборке из 3 объектов с текущими отступами $z_1=0{,}5$, $z_2=1$, $z_3=2$. Для каждого объекта укажи субдифференциал hinge loss $\partial L(z_i)$.

Задание 29: Объясни, почему теорема о сходимости $O(1/\sqrt{k})$ субградиентного метода требует ограниченности нормы субградиентов константой $G$, и что физически может пойти не так, если субградиенты неограниченно растут по норме от итерации к итерации.

Задание 30: Сравни своими словами (2–3 предложения), в чём субградиентный метод одновременно и удивительно прост в реализации, и заметно менее эффективен в теории и на практике по сравнению с обычным градиентным спуском на гладких функциях.

Частые ошибки

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

Ошибка 2: путать субградиент с "любым удобным числом, которое не сломает код". Субградиент — не произвольное число, а элемент строго определённого множества $\partial f(x)$, заданного неравенством из определения. Число $2$ не является субградиентом $|x|$ в нуле, потому что оно не удовлетворяет неравенству $|y| \ge 2y$ при всех $y$ — это математический факт, а не вопрос удобства реализации.

Ошибка 3: использовать линейный поиск (line search) вдоль направления $-g_k$ так, как в гладком градиентном спуске, и удивляться нестабильному поведению. Линейный поиск предполагает, что движение вдоль направления действительно улучшает функцию хотя бы локально — а для субградиента этой гарантии нет. Разумная альтернатива — заранее заданное расписание убывающего шага.

Ошибка 4: забывать отдельно хранить и обновлять лучшее найденное значение (best iterate) в реализации цикла оптимизации. Возврат просто последней точки $x_K$ после цикла — распространённая, но потенциально дорогостоящая ошибка: как показано в разобранных примерах, последняя точка вполне может оказаться заметно хуже, чем точка, посещённая несколькими итерациями раньше.

Ошибка 5: считать, что скорость сходимости $O(1/\sqrt{k})$ субградиентного метода — это ошибка реализации или неудачный выбор гиперпараметров, которую можно исправить более удачным шагом. Это фундаментальный теоретический предел для класса недифференцируемых выпуклых функций общего вида (не улучшаемый принципиально никаким выбором шага для этого класса задач), а не следствие плохой настройки — для более быстрой сходимости нужно использовать структуру конкретной задачи (например, проксимальные методы), а не просто "подкручивать" субградиентный метод.

Ошибка 6: считать выбор конкретного значения производной ReLU в нуле во фреймворках глубокого обучения произвольным хаком без теоретического обоснования. На самом деле это законный и предсказуемый выбор одного элемента из строго определённого множества субградиентов $[0,1]$, обоснованный ровно той теорией, которая разобрана в этом уроке, а не случайным инженерным трюком.

Главное запомнить

• Субградиент — обобщение обычного градиента для точек, где обычная производная не существует, определяемое через неравенство $f(y) \ge f(x) + g^\top(y-x)$ для всех $y$.

• Субдифференциал $\partial f(x)$ — это множество всех субградиентов в точке $x$; в точках гладкости оно состоит ровно из одного элемента и совпадает с обычным градиентом.

• Субдифференциал $|x|$ в нуле — это отрезок $[-1,1]$; субдифференциал ReLU в нуле — это отрезок $[0,1]$; субдифференциал hinge loss в точке отступа $z=1$ — отрезок $[-1,0]$.

• Геометрически субградиент — это наклон любой опорной прямой (или гиперплоскости) к графику функции, лежащей не выше самого графика и касающейся его в данной точке.

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

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

• Скорость сходимости субградиентного метода $O(1/\sqrt{k})$ заметно медленнее скорости $O(1/k)$ обычного гладкого градиентного спуска — это фундаментальное, а не устранимое ограничение.

• Из-за немонотонности необходимо отдельно отслеживать лучшее найденное значение (best iterate) за всю историю итераций, а не возвращать значение в последней посещённой точке.

• PyTorch и TensorFlow при вычислении обратного прохода через ReLU в нуле возвращают одно конкретное фиксированное число из субдифференциала $[0,1]$ — это законный инженерный выбор внутри теоретически допустимого диапазона.

Связь с темами курса

Субградиентные методы связаны с целым рядом тем курса машинного обучения не абстрактно, а напрямую, через конкретные повседневные инструменты. ReLU — самая распространённая функция активации в глубоком обучении — технически недифференцируема в нуле, и каждый раз, когда фреймворк выполняет обратный проход через слой ReLU, он фактически применяет ровно ту теорию субградиента, которая разобрана в этом уроке, просто не называя её по имени в документации для пользователя. Hinge loss в машинах опорных векторов (SVM) — классический пример функции потерь, обучение которой стохастическим субградиентным методом было одним из первых массовых практических применений этой теории в машинном обучении задолго до расцвета глубокого обучения. $L_1$-регуляризация (Lasso), порождающая разреженные модели путём зануления части весов, технически требует субградиента вместо обычного градиента ровно в тех точках, где вес зануляется, — и понимание этого напрямую объясняет, почему наивный субградиентный спуск для Lasso сходится довольно медленно на практике, и почему следующий урок про проксимальные методы предлагает для этой конкретной задачи специализированную и заметно более быструю альтернативу.

Интересные факты

• Слово «субдифференциал» отражает буквальный смысл: субградиенты образуют множество, которое всегда содержится «под» (sub-) обычной производной в том смысле, что верхняя граница отрезка субдифференциала в точке излома совпадает с производной справа, а нижняя — с производной слева, и любой обычный градиент в гладкой точке — это частный случай, когда это множество схлопывается в одну точку.

• Теория субградиентов и выпуклого анализа Рокафеллара была разработана в первую очередь для задач экономики, теории игр и исследования операций — оптимального распределения ресурсов, теории двойственности в линейном и выпуклом программировании — за много десятилетий до того, как в машинном обучении вообще возникла массовая потребность обучать модели с негладкими функциями потерь.

• Хотя субградиентный метод сходится с теоретической скоростью $O(1/\sqrt{k})$, эта оценка является наихудшим случаем (worst-case) для произвольной выпуклой негладкой функции; на многих реальных задачах, где негладкость сосредоточена лишь в отдельных изолированных точках (как у $|x|$ или ReLU), практическая сходимость зачастую оказывается заметно лучше этой пессимистичной теоретической гарантии.

• Вопрос о том, какое именно фиксированное значение возвращать в качестве субградиента ReLU в нуле, обсуждался разработчиками основных фреймворков глубокого обучения открыто — выбор $0$ мотивирован в том числе тем, что он делает ReLU идентичной функции «отсечения снизу» с чуть более предсказуемым поведением градиента для «мёртвых» нейронов, не активирующихся ни на одном примере обучающей выборки.

Лайфхаки

• Если график обучения модели с hinge loss или $L_1$-регуляризацией выглядит "дёрганым" с временными скачками функции потерь вверх, не спеши сразу уменьшать скорость обучения — сначала проверь, не связано ли это с ожидаемой немонотонностью субградиентного метода вблизи точек излома, разобранной в этом уроке.

• При реализации любого варианта субградиентного метода с нуля заводи переменные best_x и best_f с самого начала цикла оптимизации и обновляй их на каждой итерации сравнением, а не пытайся добавить это "потом" — забытое отслеживание лучшего значения легко потерять уже найденное хорошее решение.

• Чтобы быстро проверить, является ли конкретное число законным субградиентом в подозрительной точке, не всегда обязательно решать неравенство определения аналитически — подставь пару-тройку конкретных значений $y$ по обе стороны от точки излома и проверь неравенство численно, это часто быстрее и снижает риск ошибки в алгебре.

• Если задача позволяет (функция потерь раскладывается на гладкую часть и негладкий регуляризатор вроде $L_1$-нормы, как в Lasso), присмотрись сначала к проксимальным методам из следующего урока, а не к «чистому» субградиентному методу — для этого широкого класса практически важных задач проксимальный подход даёт заметно более быструю сходимость почти без дополнительных затрат на реализацию.

• При отладке кода, вычисляющего субградиент вручную для составной функции, отдельно проверяй значение в гладких точках (должно точно совпадать с обычной численной производной) и отдельно — поведение вблизи точки излома, где численное дифференцирование конечными разностями может давать неустойчивые, «дребезжащие» результаты именно из-за самой негладкости.

Субградиент — это не заплатка поверх математики, которая перестала работать, а расширение того же самого языка на класс функций, где раньше приходилось разводить руками. Как только этот отрезок $[-1,1]$ для $|x|$ или $[0,1]$ для ReLU в нуле перестаёт быть загадочным местом в коде фреймворка и становится понятным, строго определённым математическим объектом, гораздо проще уверенно читать графики обучения реальных моделей, отлаживать неожиданное поведение loss-функции и осознанно выбирать между субградиентным методом и более специализированными инструментами вроде проксимальных методов, к которым ты перейдёшь в следующем уроке.