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

Градиент — это ожидание

Лосс на выборке — среднее по примерам, значит его градиент тоже среднее:

$$\htmlData{k=full}{\nabla f(x) = \frac{1}{n}\sum_{i=1}^{n} \nabla f_i(x)} \ \approx \ \htmlData{k=batch}{\frac{1}{B}\sum_{i \in \mathcal{B}} \nabla f_i(x)}$$

Это в точности оценка Монте-Карло из блока 3 (урок 150), и всё, что там было сказано, переносится сюда без изменений:

• оценка несмещена при любом $B$, даже при $B = 1$. Это следует из линейности ожидания и ничего не требует;
• её дисперсия равна $\sigma^2 / B$, где $\sigma^2$ — дисперсия градиента по отдельным примерам.

Второй пункт проверяется точно. На выборке из тысячи точек с дисперсией градиентов $9.452$:

$B$	измеренная дисперсия	$\sigma^2/B$
$1$	$9.517$	$9.452$
$4$	$2.358$	$2.363$
$16$	$0.591$	$0.591$
$64$	$0.147$	$0.148$
$256$	$0.037$	$0.037$

Отсюда сразу видно, почему большие батчи дают убывающую отдачу: чтобы уменьшить шум вдвое, нужно увеличить батч вчетверо — знакомая цена $1/\sqrt{B}$.

Почему стохастический метод вообще выигрывает

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

	один полный шаг	тысяча стохастических шагов
стоимость	$n$ градиентов	$n$ градиентов
точность направления	идеальная	шумная
пройденное расстояние	один шаг	тысяча шагов

Тысяча приблизительно верных шагов уводит дальше, чем один точный. Это и есть весь аргумент, и он тем сильнее, чем больше $n$.

Шум не исчезает

Ключевое отличие от полного градиента: SGD с постоянным шагом не сходится в точку. Он приходит в область вокруг минимума и остаётся там, потому что шум не даёт остановиться.

Размер этой области считается точно. Для $f = \frac{a}{2}x^2$ с шумом градиента $\sigma$ стационарная дисперсия равна

$\operatorname{Var}[x_\infty] = \frac{\alpha\sigma^2}{a\,(2 - \alpha a)}$

и численный эксперимент это подтверждает:

$\alpha$	$\sigma$	измеренная $\operatorname{Var}$	теория
$0.1$	$1$	$0.0517$	$0.0526$
$0.05$	$1$	$0.0250$	$0.0256$
$0.01$	$1$	$0.0049$	$0.0050$
$0.1$	$0.5$	$0.0129$	$0.0132$

Формула читается так: шумовой шар пропорционален $\alpha\sigma^2$. Уменьшить его можно двумя способами — уменьшив шаг или уменьшив шум (то есть увеличив батч), и это взаимозаменяемо.

Подвигайте шум и шаг в виджете. При нулевом шуме траектория идёт гладко, при большом начинает дёргаться и в конце не останавливается.

чашавытянутая чашаседло

SGDSGD с моментом

лосс, логарифмическая шкала

шаг α

0.05

итераций

200

шум градиента σ

0

f в конце

4.45e-9

обусловленность κ

1

порог 2/L

2

 

сходится

Как всё-таки сходиться

Раз шумовой шар пропорционален $\alpha$, для сходимости в точку шаг обязан убывать. Классические условия Роббинса–Монро:

$\sum_k \alpha_k = \infty \qquad \text{и} \qquad \sum_k \alpha_k^2 < \infty$

Первое — «суммарного пути хватает, чтобы дойти куда угодно», второе — «накопленный шум конечен». Расписание $\alpha_k = c/k$ удовлетворяет обоим, $\alpha_k = c/\sqrt{k}$ — только первому.

На практике условия Роббинса–Монро почти не соблюдают буквально: используют кусочно-постоянные или косинусные расписания (урок 090), которые формально не удовлетворяют первому условию, потому что обучение конечно. Это нормально — цель не предельная сходимость, а хорошая модель за отведённое время.

Batch size и learning rate связаны

Из формулы шумового шара следует практическое правило. Величина $\alpha \sigma^2 = \alpha \sigma_1^2 / B$ определяет уровень шума, значит:

$\frac{\alpha}{B} \approx \text{const}$

сохраняет режим обучения. Отсюда два известных приёма:

• линейное правило масштабирования: увеличили батч в $k$ раз — увеличьте шаг в $k$ раз. Работает до некоторого предела, после которого мешает уже граница устойчивости $2/L$;
• увеличивать батч вместо уменьшения шага: даёт тот же эффект на шум, но лучше параллелизуется.

Предел важен и объясняет «критический размер батча». Шаг нельзя растить бесконечно — над $2/L$ метод расходится независимо от шума. Поэтому за некоторым $B$ увеличение батча перестаёт ускорять обучение: шум уже не является узким местом, а шаг поднять нельзя.

Шум как регуляризатор

Последнее, и самое неожиданное: шум SGD бывает полезен, и не только около седел.

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

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