Момент

Правило

$$\htmlData{k=vel}{v_{k+1}} = \htmlData{k=beta}{\beta} \, v_k + \nabla f(x_k), \qquad x_{k+1} = x_k - \alpha \, \htmlData{k=vel}{v_{k+1}}$$

Скорость — экспоненциальное среднее градиентов, а не градиент. Раскроем рекурсию:

$v_k = \nabla f(x_k) + \beta \nabla f(x_{k-1}) + \beta^2 \nabla f(x_{k-2}) + \dots$

Отсюда два прочтения, оба полезные:

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

Второе объясняет, почему момент помогает именно на вытянутых ландшафтах. По широкой оси градиент всегда указывает в одну сторону, и вклад накапливается до $\frac{1}{1-\beta}$ раз. По узкой оси знак чередуется, и колебания подавляются.

Множитель $\frac{1}{1-\beta}$ стоит запомнить: при $\beta = 0.9$ это $10$, при $\beta = 0.99$ — $100$. Это и «эффективная длина памяти», и во сколько раз вырастает эффективный шаг вдоль согласованного направления. Отсюда практическое правило: подняв $\beta$, шаг $\alpha$ обычно приходится уменьшить.

√κ вместо κ

Главный результат: при оптимально подобранных $\alpha$ и $\beta$ множитель сокращения ошибки становится

$\rho_{\text{mom}} = \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \qquad\text{вместо}\qquad \rho_{\text{GD}} = \frac{\kappa - 1}{\kappa + 1}$

с оптимальными значениями

$\beta^* = \left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^2, \qquad \alpha^* = \frac{4}{(\sqrt{\mu} + \sqrt{L})^2}$

Проверено численно на $\kappa = 100$ ($\mu = 1$, $L = 100$): теоретический оптимум $\beta^* = 0.669$, $\alpha^* = 0.0331$ доводит лосс до $10^{-6}$ за 69 шагов, тогда как градиентному спуску с его оптимальным шагом нужно 444. Отношение $6.4$, а множитель падает с $0.980$ до $0.818$ — то есть ровно до того значения, которое GD имеет при $\kappa = 10$.

Это и есть смысл «$\sqrt{\kappa}$»: момент делает задачу с $\kappa = 100$ такой же по трудности, как задача с $\kappa = 10$ для обычного спуска. Для $\kappa = 10^4$ разница уже стократная.

Оговорка, которую стоит знать: $\sqrt{\kappa}$ — теоретический предел для методов первого порядка (нижняя граница Нестерова). Быстрее не может ни один метод, использующий только градиенты. Так что момент — не эвристика, а оптимальный по порядку метод.

Переключайтесь между спуском и моментом на третьем ландшафте и подвигайте $\beta$.

κ = 100круглая чашабанан Розенброка

спускмоментНестеров

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

шаг α

0.019

итераций

150

f в конце

6.33e-3

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

100

порог 2/L

0.02

 

сходится

Второй ландшафт стоит посетить обязательно. На круглой чаше момент вредит: он перелетает минимум, потому что накопленная скорость не даёт остановиться. Ускоритель нужен там, где есть что ускорять.

Нестеров

Отличие в одной строке: градиент измеряется не там, где стоим, а там, где окажемся, если продолжим по инерции.

$v_{k+1} = \beta v_k + \nabla f\big(\underbrace{x_k - \alpha\beta v_k}_{\text{с упреждением}}\big)$

Смысл — не проехать поворот. Обычный момент узнаёт о смене склона, уже пролетев мимо; Нестеров смотрит вперёд и начинает торможение раньше. Практически это даёт меньшее перерегулирование и лучшую константу в оценке, хотя порядок $\sqrt{\kappa}$ тот же.

Сравните на первом ландшафте при $\beta = 0.9$: у момента заметный выброс за минимум, у Нестерова он меньше.

Как это выглядит в фреймворках

Здесь есть ловушка, стоящая денег. PyTorch реализует момент так:

$v \leftarrow \beta v + g, \qquad x \leftarrow x - \alpha v$

а часть литературы (и TensorFlow в некоторых режимах) — так:

$v \leftarrow \beta v + (1-\beta) g, \qquad x \leftarrow x - \alpha v$

Разница в множителе $(1-\beta)$: во второй форме $v$ — настоящее среднее градиентов, и эффективный шаг равен $\alpha$; в первой — сумма, и эффективный шаг равен $\frac{\alpha}{1-\beta}$. При $\beta = 0.9$ это десятикратная разница в реальном шаге.

Отсюда конкретное следствие: перенося гиперпараметры между фреймворками или между статьёй и кодом, проверяйте форму. Значение lr=0.1, momentum=0.9 означает разные вещи в двух конвенциях.

Что момент не делает

• не уменьшает $\kappa$. Задача остаётся той же; меняется зависимость алгоритма от неё;
• не гарантирует монотонности. Лосс с моментом может расти на отдельных шагах, и это нормально — инерция проносит через локальные подъёмы;
• не спасает от плохой обусловленности полностью. $\sqrt{10^6} = 10^3$ — всё ещё тысяча шагов. Стандартизация и нормализация уменьшают саму $\kappa$ и потому эффективнее.

Второй пункт полезен практически: увидев немонотонный лосс с моментом, не стоит сразу уменьшать шаг. Немонотонность здесь — механизм, а не симптом.