Стохастический градиентный спуск SGD: формула и шум

Стохастический градиентный спуск, или SGD (Stochastic Gradient Descent), - это способ минимизировать функцию потерь, при котором на каждом шаге градиент считают не по всей обучающей выборке, а по одному примеру или маленькой случайной подвыборке (мини-батчу). Из-за этого направление шага постоянно немного «дрожит» вокруг истинного градиента, и вместо гладкой линии спуска получается зашумлённая ломаная траектория. Именно это отличает SGD от полного (батч-)градиентного спуска, где на каждом шаге считают точный градиент по всем данным сразу. Ниже разберём формулу обновления, откуда берётся шум и как он связан с размером батча, почему SGD в принципе не останавливается точно в минимуме, а «блуждает» рядом с ним, и как всё это выглядит в числах. Чтобы увидеть шум и сходимость сразу на одной картинке, покрути калькулятор ниже - он держит рядом гладкую траекторию обычного градиентного спуска и зашумлённую траекторию SGD на одной и той же чаше потерь.

Формула обновления SGD

Пусть $f(\theta)$ - функция потерь, зависящая от параметров модели $\theta$ (веса нейросети, коэффициенты регрессии и т.п.), а $f_i(\theta)$ - вклад в неё одного обучающего примера $i$. Полный градиент по всей выборке из $n$ примеров - это среднее:

$\nabla f(\theta) = \frac{1}{n} \sum_{i=1}^{n} \nabla f_i(\theta).$

Считать эту сумму на каждом шаге для больших $n$ дорого, поэтому SGD заменяет её оценкой по случайно выбранному мини-батчу $B$ размера $|B|$:

$g_k = \frac{1}{|B|} \sum_{i \in B} \nabla f_i(\theta_k), \qquad \theta_{k+1} = \theta_k - \eta\, g_k,$

где $\eta$ - скорость обучения (learning rate). Оценку $g_k$ удобно записать как истинный градиент плюс шум: $g_k = \nabla f(\theta_k) + \xi_k$. Матожидание шума равно нулю (оценка несмещённая - в среднем по всем возможным батчам $g_k$ совпадает с полным градиентом), но его дисперсия убывает с ростом размера батча примерно как $1/|B|$, то есть стандартное отклонение шума падает как $1/\sqrt{|B|}$. Отсюда и главный компромисс SGD: батч побольше даёт более точную оценку градиента и более гладкий спуск, но каждый шаг обходится дороже; батч поменьше (вплоть до одного примера) даёт дешёвые, но шумные шаги.

Почему SGD не сходится точно в минимум

У полного градиентного спуска с постоянным шагом на квадратичной функции траектория гладко сходится к минимуму, и $\nabla f \to 0$ гасит и сам шаг. У SGD шум $\xi_k$ от градиента не зависит от того, насколько параметры близки к минимуму, - он не исчезает, когда $\theta_k$ уже рядом с оптимумом. Из-за этого при постоянной скорости обучения $\eta$ траектория не останавливается в точке минимума, а входит в небольшую область вокруг него и дальше блуждает внутри неё - размер этой области растёт с $\eta$ и с дисперсией шума и падает с размером батча.

Рассчитать для своей задачи

Именно поэтому на практике скорость обучения $\eta$ часто не держат постоянной, а уменьшают по ходу обучения (расписание, например $\eta_k = \eta_0 / \sqrt{k}$ или ступенчатое снижение) - тогда шаги становятся мельче, шар блуждания сжимается, и в пределе SGD может сходиться точно к минимуму. Без такого расписания метод даёт быстрый прогресс на старте, но выходит на «шумное плато» и перестаёт заметно улучшать функцию потерь.

Рассчитать для своей задачи

Роль размера батча и скорости обучения

Размер мини-батча - не только вопрос вычислительной цены, но и прямой рычаг управления шумом. Если обозначить базовый уровень шума на одном примере как $\sigma$, то эффективное стандартное отклонение шума градиента по батчу размера $B$ составляет:

$\sigma_{\text{eff}} = \frac{\sigma}{\sqrt{B}}.$

Увеличение батча в 4 раза уменьшает шум ровно вдвое - не пропорционально, а по корню, поэтому отдача от увеличения батча быстро падает: чтобы вчетверо снизить шум, батч нужно увеличить в 16 раз. Скорость обучения $\eta$ действует иначе: она одинаково масштабирует и полезный сигнал (движение к минимуму), и шум, поэтому просто уменьшать $\eta$ ради борьбы с шумом - не бесплатно, это же замедляет и сходимость по сигналу. Разумный компромисс - умеренный батч (не обязательно весь датасет) вместе с расписанием, которое снижает $\eta$ по мере приближения к минимуму. В калькуляторе выше это видно напрямую: переключи размер батча и посмотри, как меняется толщина «облака» вокруг конечной траектории SGD на графике сходимости.

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

Пример решения типовой задачи

Возьмём ту же модельную чашу потерь $f(x, y) = \tfrac12(x^2 + 6y^2)$, старт из точки $(x_0, y_0) = (8, 4)$, скорость обучения $\eta = 0{,}12$ и батч размера 1 (максимальный шум, $\sigma_{\text{eff}} = 1{,}5$). Полный градиент в старте: $\nabla f(8, 4) = (8, 24)$. Оценка по батчу добавляет к нему шум первого шага $\xi_0 = (0{,}497,\ 0{,}813)$, умноженный на $\sigma_{\text{eff}}$:

$g_0 = (8 + 1{,}5 \cdot 0{,}497,\ \ 24 + 1{,}5 \cdot 0{,}813) = (8{,}75,\ 25{,}22).$

Шаг обновления даёт новую точку и новое значение потерь:

$(x_1, y_1) = (8, 4) - 0{,}12 \cdot (8{,}75,\ 25{,}22) = (6{,}95,\ 0{,}97), \qquad f(x_1, y_1) \approx 27{,}0.$

За 30 таких шагов итоговое значение функции потерь и его зависимость от размера батча (при том же $\eta$) выглядят так:

Видно закономерность из предыдущего раздела: чем больше батч, тем ближе итоговое значение к результату полного градиентного спуска, но даже батч 64 не даёт точно такого же $f$, как GD, - небольшой шум остаётся всегда, пока $\eta$ постоянна.

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

• Путать SGD с обычным градиентным спуском. В классическом (батч-) градиентном спуске градиент на каждом шаге точный - по всей выборке; в SGD это всегда оценка по мини-батчу или одному примеру, отсюда и шум.
• Ждать, что итоговое значение функции потерь дойдёт до нуля. При постоянной скорости обучения SGD в общем случае сходится не к точке минимума, а к небольшой окрестности вокруг неё - это не баг, а свойство метода.
• Считать, что увеличение батча вдвое вдвое же снижает шум. Зависимость идёт через корень: $\sigma_{\text{eff}} \propto 1/\sqrt{B}$, а не $1/B$. Чтобы снизить шум в 2 раза, батч нужно увеличить в 4 раза.
• Игнорировать взаимосвязь батча и скорости обучения. Один и тот же $\eta$ при маленьком батче может расходиться, хотя при полном градиенте с тем же $\eta$ спуск был устойчив, - шум увеличивает эффективный разброс шага.
• Забывать про несмещённость оценки. Хотя каждый отдельный шаг SGD зашумлён, в среднем по батчам оценка градиента $g_k$ совпадает с истинным $\nabla f(\theta_k)$ - это и есть формальная причина, почему метод вообще работает.

FAQ

Чем SGD отличается от градиентного спуска (GD)? В GD градиент считается точно по всей обучающей выборке на каждом шаге; в SGD - по одному примеру или мини-батчу, из-за чего оценка градиента шумная, а траектория - зигзагообразная и не гладкая.

Почему SGD не сходится точно к минимуму при постоянной скорости обучения? Потому что шум оценки градиента не зависит от расстояния до минимума и не исчезает, когда параметры уже рядом с оптимумом. Точка входит в небольшую область вокруг минимума и продолжает в ней блуждать.

Как размер батча влияет на шум градиента? Эффективное стандартное отклонение шума убывает как $1/\sqrt{B}$, где $B$ - размер батча. Увеличение батча в 4 раза снижает шум только вдвое - отдача от роста батча ограничена.

Нужно ли уменьшать скорость обучения по ходу обучения SGD? Да, если нужна сходимость точно к минимуму: убывающее расписание $\eta_k$ (например $\eta_0/\sqrt{k}$) сжимает область блуждания к нулю. При постоянной $\eta$ метод быстро прогрессирует на старте, но выходит на шумное плато.

Коротко

Стохастический градиентный спуск обновляет параметры по формуле $\theta_{k+1} = \theta_k - \eta\, g_k$, где $g_k$ - несмещённая, но зашумлённая оценка полного градиента по мини-батчу размера $B$. Дисперсия шума убывает как $1/B$, поэтому эффективный разброс шага падает как $1/\sqrt{B}$: батч побольше сглаживает траекторию, но не бесплатно по вычислениям. При постоянной скорости обучения метод не сходится точно в минимум, а входит в небольшую область блуждания вокруг него, - избавиться от этого можно только убывающим расписанием $\eta_k$. Это ровно то же ядро правила обновления, которое лежит в основе обучения нейросетей через обратное распространение ошибки: backpropagation считает градиент функции потерь по весам, а SGD (или его модификации вроде Adam) решает, как именно этим градиентом обновлять веса на каждом шаге.