Методы второго порядка

Ньютон

Градиентный спуск использует линейное приближение функции. Метод Ньютона — квадратичное:

$$x_{k+1} = x_k - \htmlData{k=hess}{\big[\nabla^2 f(x_k)\big]^{-1}} \nabla f(x_k)$$

Вывод в одну строку: приблизим $f$ квадратикой в точке $x_k$ и прыгнем сразу в её минимум. Отсюда главное свойство: на квадратичной функции Ньютон попадает в минимум за один шаг из любой точки, независимо от обусловленности.

Проверено: при $\kappa = 100$, $\kappa = 1$ и даже $\kappa = 10^5$ ответ достигается за одну итерацию. Сравните с $691$ шагом обычного спуска при $\kappa = 100$.

Причина в терминах урока 050: обратный гессиан — это идеальный предобусловливатель. Он делает $\kappa = 1$ по построению, а при $\kappa = 1$ шаг $1/L$ попадает в минимум сразу.

Заодно у Ньютона нет learning rate — размер шага определяется кривизной. Это и достоинство (нечего подбирать), и опасность (шаг может оказаться огромным, если кривизна мала).

Почему им не пользуются

Стоимость. Для $d$ параметров:

$d$	градиент $O(d)$	гессиан $O(d^2)$	обращение $O(d^3)$
$10^3$	$10^3$	$10^6$	$10^9$
$10^6$	$10^6$	$10^{12}$	$10^{18}$
$10^9$	$10^9$	$10^{18}$	$10^{27}$

При $d = 10^9$ гессиан содержит $10^{18}$ чисел — это $8$ эксабайт памяти. Не «медленно», а физически невозможно.

Плюс две проблемы помимо стоимости:

• на невыпуклой задаче гессиан не положительно определён. Тогда «шаг в минимум квадратики» может оказаться шагом вверх — в направлении отрицательной кривизны квадратика уходит в минус бесконечность. Отсюда все модификации: сдвиг спектра, доверительные области, гауссов-ньютон;
• шум. Гессиан по минибатчу — плохая оценка, и обращать шумную матрицу опаснее, чем усреднять шумный градиент.

Что используют вместо

метод	что делает	стоимость
L-BFGS	приближает $H^{-1}$ по истории $m$ последних шагов	$O(md)$
гауссов-ньютон	заменяет $H$ на $J^\top J$, всегда $\succeq 0$	зависит
natural gradient	предобусловливает матрицей Фишера	$O(d^2)$, нужны приближения
K-FAC	Фишер как кронекерово произведение блоков	практично
Adam	диагональное приближение по вторым моментам	$O(d)$

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

L-BFGS стоит знать как реально работающий классический метод. Он хранит $m$ пар (шаг, изменение градиента), обычно $m \in [5, 20]$, и строит из них приближение $H^{-1}$ без явной матрицы. В глубоком обучении применяется редко — плохо переносит шум минибатчей — но для детерминированных задач среднего размера часто лучший выбор.

Natural gradient

Отдельная идея, из другого места. Обычный градиент зависит от параметризации: перейдите к $\theta' = 2\theta$, и градиент изменится. А ведь модель — та же.

Natural gradient предлагает мерить расстояние не в пространстве параметров, а в пространстве распределений, которые модель задаёт:

$\tilde{\nabla} = F^{-1}\nabla, \qquad F = \mathbb{E}\big[\nabla \log p_\theta \, \nabla \log p_\theta^\top\big]$

$F$ — матрица Фишера, и она есть в точности гессиан KL-дивергенции между $p_\theta$ и $p_{\theta + \delta}$ при малом $\delta$. То есть natural gradient — это спуск, у которого шаг ограничен в KL, а не в евклидовой норме.

Отсюда сразу три связи с уже пройденным:

• KL из блока 4 оказывается метрикой на пространстве моделей, а не только функцией потерь;
• информация Фишера из блока 3 (кривизна log-правдоподобия) оказывается той самой матрицей;
• PPO и TRPO ограничивают шаг в KL — это и есть natural gradient в приближении, и ветка B к нему вернётся.

Практически $F$ имеет размер $d \times d$ и потому недоступна; K-FAC приближает её кронекеровыми произведениями поблочно, и это работает.

Что стоит унести

Сравните Adam и спуск на повёрнутом ландшафте — это лучшая иллюстрация того, чего не хватает диагональным методам и что дал бы полный гессиан.

выровнено по осямповёрнуто на 45°

спускмоментAdam

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

шаг α

0.05

итераций

150

f в конце

4.15e-7

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

30

порог 2/L

0.067

 

сходится

Итог блока в одной мысли: вся эта иерархия методов — способы получить информацию о кривизне за приемлемую цену. Ньютон берёт её точно и стоит $O(d^3)$; L-BFGS — по истории за $O(md)$; Adam — по диагонали за $O(d)$; момент — вообще без кривизны, но с памятью, что даёт $\sqrt{\kappa}$. А нормализация и стандартизация из уроков 050 и 100 действуют иначе: они уменьшают саму $\kappa$, и потому остаются самым выгодным вложением.