Практика: оптимизаторы с нуля

Блок в одной формуле

Всё, что было, сводится к одному числу и способам от него не зависеть.

$$\text{итераций} \ \sim \ \htmlData{k=kappa}{\kappa} \ \text{для GD}, \qquad \sqrt{\htmlData{k=kappa}{\kappa}} \ \text{для момента}, \qquad 1 \ \text{для Ньютона}$$

средство	что делает с $\kappa$	цена
подбор шага	ничего	—
момент	$\kappa \to \sqrt\kappa$ в оценке	$O(d)$ памяти
Adam	уменьшает эффективную $\kappa$ по диагонали	$2 \times O(d)$ памяти
Ньютон	делает $\kappa = 1$	$O(d^3)$
стандартизация	уменьшает саму $\kappa$	почти бесплатно
нормализация слоёв	то же, внутри сети	небольшая

Две последние строки — почему блок заканчивается не оптимизаторами, а нормализацией.

Что реализовать

1. Четыре оптимизатора, один интерфейс

Напишите функцию, принимающую градиент и состояние, для каждого из: GD, момент, Нестеров, Adam. Все четыре умещаются в двадцать строк, если состояние передавать явно.

Проверки, которые обязаны сойтись:

• GD на $f = \frac{a}{2}x^2$: после $k$ шагов $x_k = x_0(1 - \alpha a)^k$ точно. Сравните с замкнутой формой, а не «на глаз»;
• Adam из нулевого состояния: при любом ненулевом постоянном градиенте первый шаг равен $\alpha$ с точностью до $10^{-7}$. Если получилось $0.1\alpha$ — забыта коррекция $\hat m$; если $31\alpha$ — забыта коррекция $\hat v$;
• момент при $\beta = 0$ обязан совпадать с GD побитово.

2. Плохо обусловленная квадратика

Возьмите $f = \frac12(x^2 + \kappa y^2)$ и проверьте четыре предсказания блока:

что проверить	ожидание
порог устойчивости GD	расходимость строго при $\alpha > 2/\kappa$
при $\alpha = 2/\kappa$ ровно	вечные колебания, лосс не падает
число шагов GD до $10^{-6}$	$\approx \frac{\kappa}{2}\ln 10^{6}$
момент с $\beta^*, \alpha^*$	в $\approx\sqrt\kappa$ раз меньше шагов

Для $\kappa = 100$ последние две строки дают $691$ и $69$ — сверьтесь. И проверьте формулу $\beta^* = \left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^2$: при $\kappa = 100$ это $0.669$, а не привычные $0.9$.

3. Batch size и learning rate

Соберите игрушечную стохастическую задачу: $f_i(x) = \frac12(x - c_i)^2$ с разбросанными $c_i$. Тогда шум градиента известен точно, и можно проверить:

• дисперсия градиента по батчу равна $\sigma_1^2/B$ — измерьте на $B = 1, 4, 16, 64$;
• при постоянном шаге итерат не сходится, а гуляет с дисперсией $\frac{\alpha\sigma^2}{a(2-\alpha a)}$. Измерьте после отбрасывания первых итераций;
• правило $\alpha/B = \text{const}$ сохраняет уровень шума. Проверьте на четырёх парах и найдите, где оно начинает ломаться — это происходит, когда $\alpha$ подходит к $2/L$.

Третий пункт — самый содержательный, потому что даёт «критический размер батча» не как эмпирическое наблюдение, а как следствие формулы.

4. Траектория на 2D-ландшафте

Нарисуйте линии уровня и путь каждого оптимизатора. Обязательный набор картинок:

1. круглая чаша — GD попадает за один шаг при $\alpha = 1/L$, момент перелетает;
2. вытянутая чаша — GD зигзагует, момент идёт почти прямо;
3. повёрнутая вытянутая чаша — Adam теряет преимущество, потому что диагональ не видит поворота;
4. банан Розенброка — ни один параметр не хорош на всём пути.

Третья картинка — самая полезная и чаще всего пропускаемая. Сравните две матрицы Гессе: $\text{diag}(1, 100)$ и $\begin{pmatrix} 50.5 & 49.5 \\ 49.5 & 50.5\end{pmatrix}$. Спектр у них один и тот же, а диагонали совершенно разные — вот и вся разница между полным и диагональным предобусловливанием.

круглаявытянутаяповёрнутаяРозенброк

GDмоментНестеровAdam

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

шаг α

0.02

итераций

200

шум

0

f в конце

1.12e-3

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

1

порог 2/L

2

 

сходится

5. Нормализация как предобусловливание

Самое короткое и самое убедительное упражнение блока:

1. возьмите линейную регрессию на данных, где один признак имеет масштаб $10^4$;
2. посчитайте $\kappa$ матрицы $X^\top X$ — получится около $10^8$;
3. обучите градиентным спуском, логируя лосс. Он будет ползти;
4. стандартизуйте признаки, пересчитайте $\kappa$ — упадёт до десятков;
5. обучите снова тем же методом и тем же шагом.

Разница в скорости будет на порядки, при том что оптимизатор не менялся. Это и есть главный вывод блока, полученный своими руками.

Что должно сойтись

проверка	ожидание
GD на квадратике против замкнутой формы	совпадение до $10^{-12}$
порог расходимости	ровно $2/L$, не «примерно»
момент при $\beta = 0$ против GD	побитово одинаково
первый шаг Adam из нуля	$\alpha$ с точностью $10^{-7}$
дисперсия градиента по батчу	$\sigma_1^2/B$ в пределах шума измерения
$\kappa$ до и после стандартизации	разница в $10^6$–$10^7$ раз

И одна вещь, которая сойтись не должна: не пытайтесь получить теоретические $\beta^*$ и $\alpha^*$ в реальном обучении. Они требуют знать $\mu$ и $L$, которых нет. Формулы нужны, чтобы понимать порядок величин и то, откуда берутся привычные значения — а не чтобы их подставлять.