Distill: почему momentum действительно работает

О переводе

Текст и рисунки Distill распространяются по лицензии CC BY 4.0, поэтому здесь полный перевод. Почти все рисунки статьи — интерактивные: ползунки шага $\alpha$ и momentum $\beta$, перетаскиваемые точки, анимации. Перенести их нельзя, поэтому мы описываем каждый словами — держите оригинал открытым рядом и двигайте ползунки сами. Исходники статьи: github.com/distillpub/post—momentum. Сноски автора собраны в конце («Сноска 1» и т. д.), ссылки на литературу даны по авторам и году. Пометки «Прим. пер.» — наши.

Как читать вместе с курсом

Это самая математическая статья раздела. Нужны: градиентный спуск и импульсимпульс (momentum)EN momentumШаг делается по накопленной «скорости» v = βv + g, а не по текущему градиенту. Гасит зигзаги и разгоняет движение вдоль оврага. из уроков 1.4.1 и 1.4.2, собственные значения и векторы из урока 1.1.3. Обозначения совпадают с курсом: у Гоу $z \leftarrow \beta z + \nabla f(w)$, $w \leftarrow w - \alpha z$ — это ровно вариант PyTorch из урока 1.4.2 ($v \leftarrow \beta v + g$, $\theta \leftarrow \theta - \eta v$).

Первое чтение: разделы «Первые шаги», «Выбор шага», «Динамика momentum» до «Оптимальных параметров» включительно и «Momentum со стохастическими градиентами». Сноски, пример с раскраской и нижнюю границу можно оставить на второй раз.

---

Почему momentum действительно работает

Заглавный рисунок (интерактивный): линии уровня вытянутой «овражной» функции и траектория оптимизации из точки старта к минимуму. Ползунки: шаг $\alpha = 0{,}02$, momentum $\beta = 0{,}99$. Траектория раскачивается из стороны в сторону, но быстро доходит до минимума.

Мы часто думаем о momentum как о способе гасить колебания и ускорять итерации, что ведёт к более быстрой сходимости. Но у него есть и другое интересное поведение. Он позволяет использовать более широкий диапазон шагов и создаёт собственные колебания. Что происходит?

Вот популярная история о momentum (Sutskever и др., 2013; Поляк, 1964; Rutishauser, 1959): градиентный спуск — это человек, идущий вниз с холма. Он идёт по самому крутому пути вниз; продвигается медленно, но верно. Momentum — тяжёлый шар, катящийся с того же холма. Добавленная инерция работает и как сглаживатель, и как ускоритель: гасит колебания и заставляет нас проноситься через узкие долины, небольшие бугры и локальные минимумы.

Эта стандартная история не ошибочна, но многих важных особенностей momentum она не объясняет. На самом деле momentum можно понять гораздо точнее, если изучать его на правильной модели.

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

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

$$w^{k+1} = w^k-\alpha\nabla f(w^k).$$

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

Но экспоненциальное убывание, хоть и привлекательное в теории, на практике часто оказывается бесяще медленным. Обычно всё начинается хорошо — впечатляющее, почти мгновенное падение потерь. Но по ходу итераций дело замедляется. Появляется навязчивое ощущение, что вы продвигаетесь медленнее, чем должны. Что пошло не так?

Проблема может быть в давнем враге оптимизатора — патологической кривизне (pathological curvature). Говоря просто, это области $f$, которые плохо отмасштабированы. Такие ландшафты часто описывают как долины, траншеи, каналы и овраги. Итерации либо прыгают между склонами, либо приближаются к оптимуму мелкими робкими шагами. Продвижение в некоторых направлениях почти останавливается. В этих неудачных областях градиентный спуск буксует.

Momentum предлагает следующую поправку к градиентному спуску. Мы даём ему кратковременную память:

$$\begin{aligned} z^{k+1}&=\beta z^{k}+\nabla f(w^{k})\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1} \end{aligned}$$

Изменение безобидное и почти ничего не стоит. При $\beta = 0$ мы получаем обратно градиентный спуск. Но при $\beta = 0{,}99$ (иногда $0{,}999$, если всё совсем плохо) это, похоже, именно тот толчок, который нам нужен. Итерации возвращают утраченные скорость и смелость и мчатся к оптимуму с новой энергией.

Специалисты по оптимизации называют это маленькое чудо «ускорением» (acceleration).

На первый взгляд новый алгоритм может показаться дешёвым трюком. Простая уловка, чтобы обойти самое странное поведение градиентного спуска, — сглаживатель колебаний между крутыми стенками каньона. Но истина, скорее, обратная. Это градиентный спуск — трюк. Во-первых, momentum даёт на многих функциях ускорение вплоть до квадратичного [сноска 1]. Это не мелочь: такое же ускорение дают быстрое преобразование Фурье, быстрая сортировка и алгоритм Гровера. Когда вселенная дарит вам квадратичное ускорение, пора присмотреться.

Но это ещё не всё. Нижняя граница, полученная Нестеровым (2013), утверждает, что momentum в определённом, очень узком и техническом смысле оптимален. Это не значит, что он лучший алгоритм для всех функций при всех обстоятельствах. Но он обладает удивительно красивыми математическими свойствами, которые утоляют очень человеческую жажду совершенства и завершённости. Но об этом позже. Пока скажем так: momentum — алгоритм «из Книги».

Прим. пер.: «алгоритм из Книги» (an algorithm for the book) — отсылка к выражению математика Пала Эрдёша о «Книге», где Бог записал самые изящные доказательства.

Первые шаги: градиентный спуск

Начнём с изучения градиентного спуска на простейшей нетривиальной модели — выпуклой квадратичной функции:

$$f(w) = \tfrac{1}{2}w^TAw - b^Tw, \qquad w \in \mathbf{R}^n.$$

Пусть $A$ симметрична и обратима, тогда оптимальное решение $w^{\star}$ находится в точке

$$w^{\star} = A^{-1}b.$$

Как ни проста эта модель, она достаточно богата, чтобы приближать многие функции (считайте $A$ своей любимой моделью кривизны — гессианом, информационной матрицей Фишера (Amari, 1998) и т. д.), и отражает все ключевые черты патологической кривизны. А главное, для градиентного спуска на этой функции можно написать точную замкнутую формулу.

Вот как это делается. Поскольку $\nabla f(w)=Aw - b$, итерации имеют вид

$$w^{k+1}=w^{k}- \alpha (Aw^{k} - b).$$

А теперь трюк. Есть очень естественное пространство, в котором все измерения градиентного спуска действуют независимо, — собственные векторы $A$.

У каждой симметричной матрицы $A$ есть разложение по собственным значениям

$$A=Q\ \text{diag}(\lambda_{1},\ldots,\lambda_{n})\ Q^{T},\qquad Q = [q_1,\ldots,q_n],$$

и, по соглашению, будем считать, что $\lambda_i$ отсортированы от наименьшего $\lambda_1$ до наибольшего $\lambda_n$. Если сделать замену базиса $x^{k} = Q^T(w^{k} - w^\star)$, итерации распадаются и становятся такими:

$$\begin{aligned} x_{i}^{k+1} & =x_{i}^{k}-\alpha \lambda_ix_{i}^{k} \\[0.4em] &= (1-\alpha\lambda_i)x^k_i=(1-\alpha \lambda_i)^{k+1}x^0_i \end{aligned}$$

Вернувшись в исходное пространство $w$, видим, что

$$w^k - w^\star = Qx^k=\sum_i^n x^0_i(1-\alpha\lambda_i)^k q_i$$

— вот и он, градиентный спуск в замкнутой форме.

Прим. пер.: что здесь написано. Ошибку $w - w^\star$ раскладываем по собственным векторам $q_i$ матрицы $A$. Каждая координата $x_i$ этой ошибки на каждом шаге просто умножается на одно и то же число $1 - \alpha\lambda_i$. Например, при $\alpha = 1$ и $\lambda_i = 0{,}1$ множитель равен $0{,}9$: через 10 шагов от этой части ошибки останется $0{,}9^{10} \approx 0{,}35$, через 50 — $0{,}005$.

Разложение ошибки

У этого уравнения простая интерпретация. Каждый элемент $x^0$ — компонента ошибки начального приближения в базисе $Q$. Таких ошибок $n$, и каждая идёт к минимуму своим собственным, отдельным путём, убывая экспоненциально с множителем $1-\alpha\lambda_i$ на шаг. Чем ближе это число к $1$, тем медленнее сходимость.

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

$$f(w^{k})-f(w^{\star})=\sum(1-\alpha\lambda_{i})^{2k}\lambda_{i}[x_{i}^{0}]^2,$$

мы можем визуализировать вклад каждой компоненты ошибки в потери.

Рисунок (интерактивный): оптимизацию можно рассматривать как сочетание нескольких задач-компонент — здесь трёх, с собственными значениями $\lambda_1=0{,}01$, $\lambda_2=0{,}1$ и $\lambda_3=1$. Сверху — три кривые убывания ошибки по каждой компоненте, снизу — их сумма, то есть кривая потерь. Ползунок шага с отметкой «оптимальный шаг». При малом шаге быстро уходит только компонента с $\lambda_3 = 1$, а потери «застревают» на медленной компоненте $\lambda_1 = 0{,}01$; при слишком большом шаге компонента $\lambda_3$ начинает расходиться.

Выбор шага

Этот анализ сразу подсказывает, как выбирать шаг $\alpha$. Чтобы был сходимость, каждое $|1-\alpha \lambda_i|$ должно быть строго меньше 1. Значит, все рабочие шаги лежат в интервале

$$0<\alpha\lambda_i<2.$$

Общая скорость сходимости определяется самой медленной компонентой ошибки — это либо $\lambda_1$, либо $\lambda_n$:

$$\begin{aligned}\text{rate}(\alpha) & ~=~ \max_{i}\left|1-\alpha\lambda_{i}\right|\\[0.9em] & ~=~ \max\left\{|1-\alpha\lambda_{1}|,~ |1-\alpha\lambda_{n}|\right\} \end{aligned}$$

Эта общая скорость минимальна, когда скорости для $\lambda_1$ и $\lambda_n$ равны: это повторяет наше нестрогое наблюдение из прошлого раздела, что при оптимальном шаге первый и последний собственные векторы сходятся с одной скоростью. Доведя выкладки до конца, получаем:

$$\begin{aligned} \text{оптимальный }\alpha ~=~{\mathop{\text{argmin}}\limits_\alpha} ~\text{rate}(\alpha) & ~=~\frac{2}{\lambda_{1}+\lambda_{n}}\\[1.4em] \text{оптимальная скорость} ~=~{\min_\alpha} ~\text{rate}(\alpha) & ~=~\frac{\lambda_{n}/\lambda_{1}-1}{\lambda_{n}/\lambda_{1}+1} \end{aligned}$$

Заметьте: скорость сходимости задачи определяет отношение $\lambda_n/\lambda_1$. Оно встречается настолько часто, что у него есть имя и обозначение — число обусловленности (число обусловленностичисло обусловленностиEN condition numberОтношение самой большой кривизны к самой маленькой. Большое число обусловленности — вытянутый «овраг», где градиентный спуск зигзагует.):

$$\text{число обусловленности} := \kappa :=\frac{\lambda_n}{\lambda_1}$$

Число обусловленности значит многое. Это мера того, насколько матрица близка к вырожденной. Это мера того, насколько решение $A^{-1}b$ устойчиво к возмущениям $b$. А в нашем контексте число обусловленности показывает, насколько плохо будет работать градиентный спуск. Отношение $\kappa = 1$ идеально и даёт сходимость за один шаг (конечно, функция тогда тривиальна). К сожалению, чем больше отношение, тем медленнее градиентный спуск. Поэтому число обусловленности — прямая мера патологической кривизны.

Прим. пер.: пример с числами. Для трёх компонент с рисунка $\lambda_1 = 0{,}01$, $\lambda_3 = 1$, так что $\kappa = 100$. Оптимальный шаг $\alpha = 2/1{,}01 \approx 1{,}98$, скорость $99/101 \approx 0{,}980$: каждый шаг убирает лишь 2 % самой медленной ошибки. Чтобы уменьшить её в миллион раз, нужно $\ln 10^{-6} / \ln 0{,}980 \approx 690$ шагов.

Пример: полиномиальная регрессия

Анализ выше открывает важную мысль: не все ошибки одинаковы. Ошибки бывают разных видов — ровно $n$, по одному на каждый собственный вектор $A$. И градиентный спуск одни виды ошибок исправляет лучше, чем другие. Но что означают собственные векторы $A$? Удивительно, но во многих приложениях у них очень конкретный смысл.

Посмотрим, как это проявляется в полиномиальной регрессии. Даны одномерные данные $\xi_i$; задача — подогнать модель

$$\text{model}(\xi)=w_{1}p_{1}(\xi)+\cdots+w_{n}p_{n}(\xi)\qquad p_{i}=\xi\mapsto\xi^{i-1}$$

к нашим наблюдениям $d_i$. Эта модель нелинейна по входу $\xi$, но линейна по весам, поэтому её можно записать как линейную комбинацию одночленов.

Рисунок (интерактивный): кривая модели как сумма одночленов $1, \xi, \xi^2, \ldots$ с весами; ползунки весов меняют вклад каждого одночлена.

Благодаря линейности модель можно подогнать к данным $\xi_i$ линейной регрессией по невязке модели:

$$\text{minimize}_w \qquad\tfrac{1}{2}\sum_i (\text{model}(\xi_{i})-d_{i})^{2} ~~=~~ \tfrac{1}{2}\|Zw - d\|^2,$$

где

$$Z=\left(\begin{array}{ccccc} 1 & \xi_{1} & \xi_{1}^{2} & \ldots & \xi_{1}^{n-1}\\ 1 & \xi_{2} & \xi_{2}^{2} & \ldots & \xi_{2}^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \xi_{m} & \xi_{m}^{2} & \ldots & \xi_{m}^{n-1} \end{array}\right).$$

Путь сходимости, как мы знаем, проясняется, если смотреть на итерации в пространстве $Q$ (собственных векторов $Z^T Z$). Поэтому перепишем задачу регрессии в базисе $Q$. Сначала сменим базис: повернём $w$ в $Qw$, а наши функции признаков $p$ — обратным поворотом в собственное пространство, $\bar{p}$. Теперь ту же регрессию можно понимать как регрессию по другому полиномиальному базису, с моделью

$$\text{model}(\xi)~=~x_{1}\bar{p}_{1}(\xi)~+~\cdots~+~x_{n}\bar{p}_{n}(\xi)\qquad \bar{p}_{i}=\sum q_{ij}p_j.$$

Эта модель тождественна старой. Но у новых признаков $\bar{p}$ (я называю их «собственными признаками», eigenfeatures) и весов есть приятное свойство: каждая координата действует независимо от остальных. Теперь задача оптимизации по сути распадается на $n$ маленьких одномерных задач. И каждую координату можно оптимизировать жадно и независимо, по одной в любом порядке, — и получить итоговый глобальный оптимум. Собственные признаки к тому же гораздо информативнее.

Рисунок (интерактивный): точки данных и графики собственных признаков $\bar p_1, \bar p_2, \ldots$, упорядоченных по собственным значениям. Подписи: «Данные образуют 2 кластера. Первые 2 собственных признака отражают различия между кластерами. Дальше идут плавные изменения внутри кластеров, пики внутри кластеров и, наконец, зубчатые многочлены, которые сильно различаются на соседних точках». Точки можно перетаскивать.

Наблюдения с этого рисунка можно обосновать математически. Со статистической точки зрения мы хотим модель, в каком-то смысле устойчивую к шуму. Модель не может быть осмысленной, если малейшее возмущение наблюдений резко меняет её целиком. А собственные признаки — главные компоненты данных — дают ровно то разложение, которое нужно, чтобы упорядочить признаки по чувствительности к возмущениям $d_i$. Самые устойчивые компоненты идут впереди (с наибольшими собственными значениями), самые чувствительные — в конце (с наименьшими).

Эта мера устойчивости, по весьма удобному совпадению, оказывается и мерой того, насколько легко сходится собственное подпространство. Значит, «патологические направления» — собственные подпространства, которые сходятся медленнее всего, — это и те, что сильнее всего чувствительны к шуму! Поэтому, начав с простой точки вроде $0$ (грубо злоупотребляя терминологией, будем считать её априорным предположением), мы следим за итерациями, пока не достигнем нужного уровня сложности. Посмотрим, как это происходит в градиентном спуске.

Рисунок (интерактивный): подгонка многочлена градиентным спуском по шагам. Справа — столбики вкладов каждого собственного признака; «когда собственное подпространство сошлось до трёх значащих цифр, столбик сереет». Сначала модель ловит грубую форму данных (большие собственные значения), а зубчатые компоненты, которые подгоняют шум, появляются лишь через очень много шагов. Наблюдения можно перетаскивать, чтобы изменить подгонку.

Этот эффект используется в эвристике ранней остановки (ранняя остановкаранняя остановкаEN early stopping): остановив оптимизацию раньше, часто можно получить результат, который лучше обобщается. Действительно, эффект ранней остановки очень похож на эффект более привычных методов регуляризации, например регрессии Тихонова. Оба метода стараются прямо подавить компоненты с наименьшими собственными значениями, хотя затухание по спектру у них устроено по-разному [сноска 2]. Но у ранней остановки есть явное преимущество. Когда шаг выбран, крутить больше нечего: параметров регуляризации нет. Более того, за одну оптимизацию у нас в распоряжении оказывается целое семейство моделей — от недообученных до переобученных. И этот подарок, похоже, ничего не стоит. Поистине прекрасный бесплатный обед (Hinton, NIPS 2015).

Прим. пер.: регрессия Тихонова — это гребневая регрессия (ridge, $L_2$-регуляризация), которую вы видели в уроке о регуляризации.

Динамика momentum

Вернёмся к momentum. Напомним: шаг momentum —

$$\begin{aligned} z^{k+1}&=\beta z^{k}+\nabla f(w^{k})\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}. \end{aligned}$$

Поскольку $\nabla f(w^k) = Aw^k - b$, на квадратичной функции шаг выглядит так:

$$\begin{aligned} z^{k+1}&=\beta z^{k}+ (Aw^{k}-b)\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}. \end{aligned}$$

Следуя O’Donoghue и Candès (2015), проделаем те же движения: замена базиса $x^{k} = Q(w^{k} - w^\star)$ и $y^{k} = Qz^{k}$ даёт правило обновления

$$\begin{aligned} y_{i}^{k+1}&=\beta y_{i}^{k}+\lambda_{i}x_{i}^{k}\\[0.4em] x_{i}^{k+1}&=x_{i}^{k}-\alpha y_{i}^{k+1}, \end{aligned}$$

в котором каждая компонента действует независимо от остальных (хотя $x^k_i$ и $y^k_i$ связаны между собой). Это позволяет переписать итерации так [сноска 3]:

$$\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right)=R^k\left(\!\!\begin{array}{c} y_{i}^{0}\\ x_{i}^{0} \end{array}\!\!\right) \qquad R = \left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ -\alpha\beta & 1-\alpha\lambda_{i} \end{array}\!\!\right).$$

Возвести матрицу в $k$-ю степень можно многими способами. Но для случая $2 \times 2$ есть изящная и малоизвестная формула (Williams, 1992) через собственные значения $R$ — $\sigma_1$ и $\sigma_2$:

$$R^{k}=\begin{cases} \sigma_{1}^{k}R_{1}-\sigma_{2}^{k}R_{2} & \sigma_{1}\neq\sigma_{2}\\ \sigma_{1}^{k}(kR/\sigma_1-(k-1)I) & \sigma_{1}=\sigma_{2} \end{cases},\qquad R_{j}=\frac{R-\sigma_{j}I}{\sigma_{1}-\sigma_{2}}$$

Формула довольно сложная, но главное вот что: она играет ровно ту же роль, что и отдельные скорости сходимости $1-\alpha\lambda_i$ в градиентном спуске. Только вместо одной геометрической прогрессии у нас две связанные, и их значения могут быть вещественными или комплексными. Поэтому скорость сходимости — медленнейшая из двух скоростей, $\max\{|\sigma_{1}|,|\sigma_{2}|\}$ [сноска 4]. Построив её график, видим, что в пространстве параметров есть отчётливые области, которые раскрывают богатую классификацию видов сходимости (Flammarion и Bach, 2015):

Рисунок (интерактивный): карта $\max\{|\sigma_1|, |\sigma_2|\}$ на плоскости «$\alpha\lambda$ по горизонтали, $\beta$ по вертикали»; цвет — скорость сходимости. Видны отдельные области, у каждой свой стиль сходимости. Наведя мышку на точку карты, видно соответствующую траекторию: при малом $\beta$ — плавное монотонное приближение, в средней области — колебания с затуханием, у правой границы ($\alpha\lambda$ близко к $2 + 2\beta$) — колебания с переменой знака на каждом шаге, за границей — расходимость.

При каких $\alpha$ и $\beta$ momentum сходится? Поскольку сходиться должны и $\sigma_1$, и $\sigma_2$, критерий сходимости теперь — $\max\{|\sigma_{1}|,|\sigma_{2}|\} < 1$. Диапазон допустимых шагов получается таким [сноска 5]:

$$0<\alpha\lambda_{i}<2+2\beta \qquad \text{при} \qquad 0 \leq \beta < 1.$$

При $\beta = 0$ получаем прежний результат для градиентного спуска. Но заметьте немедленный выигрыш: momentum позволяет увеличить шаг почти вдвое, прежде чем начнётся расходимость.

Критический коэффициент затухания

Настоящая магия, однако, начинается, когда мы находим «золотую середину» $\alpha$ и $\beta$. Сначала попробуем оптимизировать по $\beta$.

У momentum есть интересная физическая интерпретация при малом $\alpha$ (Qian, 1999): это дискретизация затухающего гармонического осциллятора. Рассмотрим физическую симуляцию в дискретном времени (как в видеоигре).

$$\underbrace{y_{i}^{k+1}}_{\text{скорость}} \;=\; \underbrace{\beta y_{i}^{k}}_{\text{затухает на каждом шаге}} \;+\; \underbrace{\lambda_{i}x_{i}^{k}}_{\text{внешняя сила}} \qquad\qquad \underbrace{x_i^{k+1}}_{\text{положение}} \;=\; x_i^k - \alpha y_i^{k+1}$$

Подписи на рисунке оригинала: $-y_i^k$ можно считать скоростью, которая затухает на каждом шаге и возмущается внешним силовым полем. А $x$ — положение нашей частицы, которое на каждом шаге немного сдвигается в направлении скорости $y^{k+1}_i$.

Разберём это уравнение по частям, чтобы увидеть, как каждая компонента влияет на динамику системы. Ниже для $150$ итераций показана скорость частицы (горизонтальная ось) против её положения (вертикальная ось) — на фазовой диаграмме.

Рисунок (интерактивный): несколько фазовых диаграмм для разных $\beta$. Слишком малое $\beta$ — частица ползёт к нулю медленно, без колебаний (передемпфирование). Слишком большое $\beta$ — спираль из многих витков вокруг нуля (недодемпфирование). Критическое $\beta$ — самый быстрый путь к нулю.

Эту систему лучше всего представлять как груз, подвешенный на пружине. Оттягиваем груз вниз на одну единицу и смотрим, по какому пути он возвращается в равновесие. В этой аналогии пружина — источник внешней силы $\lambda_ix^k_i$, а равновесие — состояние, когда и положение $x^k_i$, и скорость $y^k_i$ равны 0. Выбор $\beta$ решающим образом влияет на скорость возвращения в равновесие.

Критическое значение $\beta = (1 - \sqrt{\alpha \lambda_i})^2$ даёт скорость сходимости (в собственном подпространстве $i$) $1 - \sqrt{\alpha\lambda_i}$. Улучшение до квадратного корня по сравнению с градиентным спуском, у которого $1-\alpha\lambda_i$! Увы, это относится только к ошибке в $i$-м собственном подпространстве при фиксированном $\alpha$.

Прим. пер.: пример. Пусть $\alpha\lambda_i = 0{,}01$. Градиентный спуск уменьшает эту компоненту ошибки в $1 - 0{,}01 = 0{,}99$ раза за шаг. При критическом $\beta = (1 - 0{,}1)^2 = 0{,}81$ momentum даёт множитель $1 - 0{,}1 = 0{,}9$ — в десять раз больше «откусывает» за шаг.

Оптимальные параметры

Чтобы получить глобальную скорость сходимости, нужно оптимизировать и по $\alpha$, и по $\beta$. Это более сложное дело [сноска 6], но ответ получается таким:

$$\alpha = \left(\frac{2}{\sqrt{\lambda_{1}}+\sqrt{\lambda_{n}}}\right)^{2} \quad \beta = \left(\frac{\sqrt{\lambda_{n}}-\sqrt{\lambda_{1}}}{\sqrt{\lambda_{n}}+\sqrt{\lambda_{1}}}\right)^{2}$$

Подставьте это в скорость сходимости — и получите

$$\underbrace{\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}}_{\text{скорость сходимости, momentum}} \qquad\text{против}\qquad \underbrace{\frac{\kappa-1}{\kappa+1}}_{\text{скорость сходимости, градиентный спуск}}$$

Едва ли приложив дополнительные усилия, мы по сути извлекли квадратный корень из числа обусловленности! В принципе, для этого выигрыша нужно явно знать $\lambda_1$ и $\lambda_n$. Но формулы подсказывают простое правило. Когда задача плохо обусловлена, оптимальное $\alpha$ примерно вдвое больше, чем у градиентного спуска, а коэффициент momentum близок к $1$. Так что ставьте $\beta$ как можно ближе к $1$, а затем ищите самое большое $\alpha$, при котором ещё есть сходимость. Как и в градиентном спуске, находиться на острие ножа, у самой границы расходимости, — хорошее место.

Рисунок (интерактивный): то же разложение на компоненты с $\lambda_1=0{,}01$, $\lambda_2=0{,}1$ и $\lambda_3=1$, но для momentum. Убывание уже не монотонное, зато значительно быстрее. Ниже — кривая $f(w^k) - f(w^\star)$ и ползунки $\alpha$ и $\beta$. Подпись: «Заметьте, что оптимальные параметры не обязательно дают самую быструю сходимость — только самую быструю асимптотическую скорость сходимости».

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

Прим. пер.: проверим на числах. Возьмём ту же диагональную задачу с $\lambda = (0{,}01;\ 0{,}1;\ 1)$, $\kappa = 100$. Оптимальные параметры momentum: $\alpha = (2/1{,}1)^2 \approx 3{,}31$, $\beta = (0{,}9/1{,}1)^2 \approx 0{,}669$; скорость $9/11 \approx 0{,}818$ против $0{,}980$ у градиентного спуска. До уменьшения ошибки в миллион раз — около 69 шагов вместо 690. Короткий код, который это проверяет:

import numpy as np

lam = np.array([0.01, 0.1, 1.0])   # собственные значения A: задача уже в «собственном» базисе
x0 = np.ones(3)                    # начальная ошибка по каждому направлению

def loss_after(alpha, beta, steps):
    x, z = x0.copy(), np.zeros(3)
    for _ in range(steps):
        z = beta * z + lam * x     # градиент функции 0.5 * sum(lam * x**2) равен lam * x
        x = x - alpha * z
    return 0.5 * np.sum(lam * x**2)    # f(w) - f(w*)

a_gd = 2 / (lam.min() + lam.max())                                   # ≈ 1.98, β = 0
s1, sn = np.sqrt(lam.min()), np.sqrt(lam.max())
a_m, b_m = (2 / (s1 + sn))**2, ((sn - s1) / (sn + s1))**2            # ≈ 3.31 и 0.669

for k in (10, 50, 100, 200):
    print(k, f"GD {loss_after(a_gd, 0.0, k):.2e}", f"momentum {loss_after(a_m, b_m, k):.2e}")

Ожидаемый вывод:

10 GD 3.39e-01 momentum 3.33e+00
50 GD 6.83e-02 momentum 8.14e-06
100 GD 9.25e-03 momentum 6.21e-14
200 GD 1.69e-04 momentum 9.18e-31

Видно ровно то, о чём говорит автор: на 10-м шаге momentum ещё хуже (колебания раскачали быструю компоненту), но дальше он уходит вперёд на много порядков.

Пример: задача раскраски

Посмотрим, как momentum ускоряет сходимость, на конкретном примере. На сетке пикселей пусть $G$ — граф, вершины которого — пиксели, $E$ — множество рёбер, соединяющих каждый пиксель с четырьмя соседями, а $D$ — небольшое множество из нескольких выделенных вершин. Рассмотрим задачу минимизации

$$\text{minimize} \qquad \underbrace{\frac{1}{2} \sum_{i\in D} (w_i - 1)^2}_{\text{раскрашиватель}} \;+\; \underbrace{\frac{1}{2} \sum_{i,j\in E} (w_i - w_j)^2.}_{\text{сглаживатель}}$$

Раскрашиватель (colorizer) тянет выделенные пиксели к 1. Сглаживатель (smoother) растекает цвет.

Оптимальное решение этой задачи — вектор из одних $1$ [сноска 7]. Если присмотреться к итерации градиентного спуска, видно, почему мы идём туда так долго. Шаг градиента для каждой компоненты — своего рода взвешенное среднее текущего значения и значений соседей:

$$w_{i}^{k+1}=w_{i}^{k}-\alpha\sum_{j\in N}(w_{i}^{k}-w_{j}^{k})-\begin{cases} \alpha(w_{i}^{k}-1) & i\in D\\ 0 & i\notin D \end{cases}$$

Такое локальное усреднение хорошо сглаживает локальные колебания пикселей, но плохо использует глобальную структуру. Обновления похожи на каплю чернил, расплывающуюся в воде. Движение к равновесию идёт только через локальные поправки, поэтому, если ничего не менять, путь к решению медленный и мучительный. К счастью, momentum заметно ускоряет дело.

Рисунок (интерактивный): сетка пикселей, где из нескольких выделенных точек «растекается» цвет; рядом — тот же процесс с momentum, который заливает сетку гораздо быстрее. Подпись: «Собственные векторы задачи раскраски образуют обобщённый базис Фурье для $R^n$. У наименьших собственных значений — низкие частоты, поэтому градиентный спуск хорошо исправляет высокочастотные ошибки, но плохо — низкочастотные».

В векторной форме задача раскраски выглядит так:

$$\text{minimize} \qquad \frac{1}{2}\sum_{i\in D}\left(x^{T}e_{i}e_{i}^{T}x-e_{i}^{T}x\right) \;+\; \frac{1}{2}x^{T}L_{G}x$$

Квадратичная форма сглаживателя — это лапласиан графа (graph Laplacian). А раскрашиватель — небольшая поправка низкого ранга с линейным членом; $e_i$ — $i$-й единичный вектор.

Матрица Лапласа $L_G$ [сноска 8], которая определяет поведение задачи оптимизации, — ценный мост между линейной алгеброй и теорией графов. Это богатая область, но для нашего разговора важен один факт. Обусловленность $L_G$ — здесь это отношение второго собственного значения к последнему (первое собственное значение всегда 0, и ему соответствует вектор из всех единиц) — напрямую связана со связностью графа.

Рисунок: три семейства графов. Подписи: «Графы „тесного мира“ — экспандеры и плотные графы — обусловлены прекрасно. Обусловленность сеток улучшается с ростом размерности. А длинные, тонкие графы вроде путей обусловлены плохо».

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

Пределы спуска

Сделаем шаг назад. С помощью хитрого трюка мы улучшили сходимость градиентного спуска в квадратичное число раз, добавив всего одну вспомогательную последовательность. Но лучшее ли это, что мы можем? Нельзя ли ускориться ещё сильнее с двумя последовательностями? Может быть, выбирать $\alpha$ и $\beta$ разумно и адаптивно? Так и тянет оседлать эту волну оптимизма — до кубического корня и дальше!

К сожалению, хотя улучшения алгоритма momentum существуют, все они упираются в определённую, критическую, почти неизбежную нижнюю границу.

Приключения в пространстве алгоритмов

Чтобы понять пределы возможного, нужно сначала формально определить пространство алгоритмов, в котором мы ищем. Вот одно возможное определение. Наблюдение такое: и градиентный спуск, и momentum можно «развернуть». Действительно, поскольку

$$\begin{array}{lll} w^{1} & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0})\\[0.35em] w^{2} & \!= & \!w^{1} ~-~ \alpha\nabla f(w^{1})\\[0.35em] & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0}) ~-~ \alpha\nabla f(w^{1})\\[0.35em] & ~ \!\vdots \\ w^{k+1} & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0}) ~-~~~~ \cdots\cdots ~~~~-~ \alpha\nabla f(w^{k}), \end{array}$$

градиентный спуск можно записать как

$$w^{k+1} ~~=~~ w^{0} ~-~ \alpha\sum_i^k\nabla f(w^{i}).$$

Похожий трюк проходит и с momentum:

$$w^{k+1} ~~=~~ w^{0} ~+~ \alpha\sum_i^k\frac{(1-\beta^{k+1-i})}{1-\beta}\nabla f(w^i).$$

Прим. пер.: в этой формуле оригинала перед суммой стоит «$+$»; по смыслу (шаг идёт против градиента) должен быть «$-$». На вывод ниже это не влияет: коэффициенты $\gamma_i^k$ в общей формуле могут быть любого знака.

На самом деле самые разные алгоритмы первого порядка — включая метод сопряжённых градиентов, AdaMax, усреднённый градиент и другие — можно записать (хотя и не так аккуратно) в такой развёрнутой форме. Поэтому класс алгоритмов, для которых

$$w^{k+1} ~~=~~ w^{0} ~+~ \sum_{i}^{k}\gamma_{i}^{k}\nabla f(w^{i}) \qquad \text{ для некоторых } \gamma_{i}^{k},$$

содержит momentum, градиентный спуск и целую кучу других алгоритмов, какие только можно придумать. Именно это предполагается в Предположении 2.1.4 у Нестерова (2013). Но пойдём ещё дальше и расширим класс, разрешив разные шаги для разных направлений:

$$w^{k+1} ~~=~~ w^{0} ~+~ \sum_{i}^{k}\Gamma_{i}^{k}\nabla f(w^{i}) \quad \text{ для некоторой диагональной матрицы } \Gamma_{i}^{k}.$$

Этот класс методов охватывает большинство популярных алгоритмов обучения нейросетей, включая AdamAdamEN Adam (adaptive moment estimation)Momentum + RMSProp + поправка смещения. Стандартный оптимизатор нейросетей с 2015 года. и AdaGrad. Будем называть его «линейными методами первого порядка» (Linear First Order Methods) и покажем одну функцию, на которой все эти методы в конце концов терпят неудачу.

Сопротивляющийся оракул

Раньше, говоря о задаче раскраски, мы заметили, что тонкие графы делают задачу оптимизации плохо обусловленной. Доведём это до крайности и возьмём граф из одного пути — функцию настолько плохо обусловленную, что один её вариант Нестеров назвал «худшей функцией в мире». Функция устроена так же, как задача раскраски, и мы назовём её выпуклой функцией Розенброка (Convex Rosenbrock):

$$f^n(w) \;=\; \underbrace{\frac{1}{2}\left(w_{1}-1\right)^{2}}_{\text{раскрашиватель из одной вершины}} \;+\; \underbrace{\frac{1}{2}\sum_{i=1}^{n}(w_{i}-w_{i+1})^{2}}_{\text{сильная связь соседних вершин пути}} \;+\; \underbrace{\frac{2}{\kappa-1}\|w\|^{2}.}_{\text{и небольшая регуляризация}}$$

Оптимальное решение этой задачи —

$$w_{i}^{\star}=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{i},$$

а число обусловленности задачи $f^n$ стремится к $\kappa$, когда $n$ стремится к бесконечности. Теперь посмотрим, как ведёт себя momentum на этой функции, стартуя с $w^0 = 0$.

Рисунок (интерактивный, с ползунками $\alpha$ и $\beta$): первые 50 итераций momentum на выпуклой функции Розенброка при $n=25$; по горизонтали — номер веса, по вертикали — номер итерации, цвет — ошибка. Подписи: «Поведение здесь такое же, как у любого линейного алгоритма первого порядка. Этот треугольник — „мёртвая зона“ итераций: здесь веса всегда равны 0, какими бы ни были параметры. Оставшееся расширяющееся пространство — „световой конус“ влияния итераций. С оптимальными параметрами momentum здесь работает очень хорошо».

Наблюдения с этого рисунка верны для любого линейного алгоритма первого порядка. Докажем это. Сначала заметим, что каждая компонента градиента зависит только от значений непосредственно до и после неё:

$$\nabla f(x)_{i}=2w_{i}-w_{i-1}-w_{i+1} +\frac{4}{\kappa-1} w_{i}, \qquad i \neq 1.$$

Поэтому раз мы стартуем с 0, компонента обязана стоически оставаться нулём, пока элемент до или после неё не станет ненулевым. А значит, по индукции, для любого линейного алгоритма первого порядка

$$\begin{array}{lllllllll} w^{0} & = & [~~0, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{1} & = & [~w_{1}^{1}, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{2} & = & [~w_{1}^{2}, & w_{2}^{2}, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] & ~ \vdots \\ w^{k} & = & [~w_{1}^{k}, & w_{2}^{k}, & w_{3}^{k}, & \ldots & w_{k}^{k}, & 0, & \ldots & 0~].\\ \end{array}$$

Считайте это ограничение «скоростью света» для передачи информации. Сигналу ошибки нужно не меньше $k$ шагов, чтобы дойти от $w_0$ до $w_k$. Поэтому можно сложить ошибки, которые ещё не могли измениться [сноска 9]:

$$\begin{aligned} \|w^{k}-w^{\star}\|_{\infty}&\geq\max_{i\geq k+1}\{|w_{i}^{\star}|\}\\[0.9em]&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k+1}\\[0.9em]&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k}\|w^{0}-w^{\star}\|_{\infty}. \end{aligned}$$

С ростом $n$ число обусловленности $f^n$ приближается к $\kappa$. И разрыв закрывается: скорость сходимости, которую обещает momentum, совпадает с лучшей, на какую способен любой линейный алгоритм первого порядка. Мы приходим к разочаровывающему выводу: на этой задаче лучше сделать нельзя.

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

Прим. пер.: именно этим занимаются нормализация (урок 3.4.1) и предобусловливание в Adam и Muon: они меняют геометрию задачи, а не только правило шага.

Momentum со стохастическими градиентами

Остался последний вопрос. Всё обсуждение выше предполагало доступ к истинному градиенту — роскошь, которую современное машинное обучение позволяет себе редко. Чтобы вычислить точный градиент, нужен полный проход по всем данным, а это бывает непомерно дорого. Вместо этого как прямую замену $\nabla f(w)$ часто используют случайные приближения градиента, например выборку мини-батча (мини-батчмини-батчEN mini-batchНебольшая случайная порция примеров, по которой считается одна оценка градиента и делается один шаг.). Приближение можно записать из двух частей:

$$\underbrace{\nabla f(w)}_{\text{истинный градиент}} \;+\; \underbrace{\text{error}(w)}_{\text{ошибка приближения}}.$$

Если оценка несмещённая, то есть $\mathbf{E}[\text{error}(w)] = 0$, то полезно думать о приближённом градиенте как о впрыскивании в итерации особого шума. С помощью аппарата из предыдущих разделов с этим дополнительным членом можно работать напрямую. На квадратичной функции член ошибки аккуратно отделяется [сноска 10]:

$$\underbrace{\left(\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\right)}_{\text{зашумлённые итерации}} \;=\; \underbrace{R^{k}\left(\begin{array}{c} y_{i}^{0}\\ x_{i}^{0} \end{array}\right)}_{\text{детерминированные итерации без шума}} \;+\; \underbrace{\epsilon^k_i \sum_{j=1}^{k}R^{k-j}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)}_{\text{затухающая сумма ошибок}},$$

где $\epsilon^k = Q \cdot \text{error}(w^k)$.

Член ошибки $\epsilon^k$, зависящий от $w^k$, — довольно «лохматый» объект. Следуя Flammarion и Bach (2015), будем моделировать его как независимый гауссов шум с нулевым средним. В этой упрощённой модели целевая функция тоже распадается на две отдельные компоненты — сумму детерминированной и стохастической ошибки [сноска 11], — показанные на рисунке.

Рисунок (интерактивный): математическое ожидание $\mathbf{E} f(w) - f(w^\star)$ разложено на детерминированную и стохастическую части; мелкие чёрные точки — один запуск стохастического градиента; ползунки $\alpha$ и $\beta$. Подпись: «Как замечают Sutskever и др. (2013), у оптимизации две фазы. В начальной, переходной фазе величина шума меньше величины градиента, и momentum по-прежнему хорошо продвигается. Во второй, стохастической фазе шум пересиливает градиент, и momentum менее эффективен».

Заметьте: тут есть набор неприятных компромиссов, которые словно сталкивают две компоненты ошибки лбами. Например, уменьшение шага снижает стохастическую ошибку, но и замедляет сходимость. А увеличение momentum, вопреки распространённому мнению, заставляет ошибки накапливаться. Несмотря на эти нежелательные свойства, стохастический градиентный спуск с momentum, как было показано, работает на нейросетях вполне конкурентоспособно. Как заметили Sutskever и др. (2013), в машинном обучении переходная фаза, похоже, важнее фазы тонкой доводки. И недавно даже было высказано предположение (Zhang и др., 2016), что этот шум — хорошая вещь: он работает как неявный регуляризатор, который, подобно ранней остановке, не даёт переобучиться в фазе доводки.

Дальше — и ниже

Исследование ускорения переживает небольшое возрождение в сообществе оптимизации. Если идеи этой статьи вас увлекли, почитайте Su, Boyd и Candès (2014): там идея momentum как дискретизации определённого дифференциального уравнения исследована полностью. Но есть и другие, менее физические интерпретации. Есть алгебраическая интерпретация momentum через приближающие многочлены (Rutishauser, 1959; Hardt, 2013). Появляются геометрические интерпретации (Bubeck и др., 2015; Drusvyatskiy и др., 2016), связывающие momentum с более старыми методами вроде метода эллипсоидов. Наконец, есть интерпретации, связывающие momentum с двойственностью (Allen-Zhu и Orecchia, 2014), — возможно, они подскажут, как ускорять методы второго порядка и квазиньютоновские методы (первый шаг — см. Нестеров, 2008). Но, как в притче о слепых, ощупывающих слона, momentum кажется чем-то большим, чем сумма частей. Однажды — надеюсь, скоро — разные точки зрения сойдутся в удовлетворительное целое.

Благодарности

Я глубоко обязан Шану Картеру и Крису Оле за редакторскую работу, без которой статья была бы куда беднее. Шан Картер полностью переделал многие из моих исходных интерактивных виджетов, придал визуальную цельность всем рисункам и заметно ускорил работу страницы. Крис Ола дал безупречную редакторскую обратную связь на всех уровнях детализации и абстракции — от структуры содержания до выравнивания формул.

Я также благодарен Майклу Нильсену за название статьи, которое по-настоящему её связало. Маркос Хинестра помогал редактировать самые ранние черновики и поддерживал меня духовно, когда это было нужнее всего. Моя благодарность и рецензентам — Мэтту Хоффману и анонимному рецензенту B — за проницательные замечания и критику. Отдельно спасибо рецензенту B за то, что он указал на две нетривиальные ошибки в исходной рукописи (обсуждение здесь). Библиотека для линий уровня заглавной визуализации — совместная работа Бена Фредериксона, Джеффа Хира и Майка Бостока.

Большое спасибо за многочисленные pull request’ы и issues на GitHub. Особенно — Осемваро Педро, заметившему ошибку «на единицу» в одной из формул, и Дэну Шмидту, который вычитал весь проект и исправил множество опечаток и грамматических ошибок.

Обсуждение и рецензии

• Рецензент A — Мэтт Хоффман
• Рецензент B — анонимный
• Обсуждение с пользователем derifatives

---

Сноски автора

Сноска 1. Однако можно построить весьма специфические контрпримеры, где momentum не сходится даже на выпуклых функциях. Контрпример см. у Lessard, Recht и Packard (2016).

Сноска 2. В регрессии Тихонова к задаче добавляют квадратичный штраф и минимизируют

$$\text{minimize}\qquad\tfrac{1}{2}\|Zw-d\|^{2}+\frac{\eta}{2}\|w\|^{2}=\tfrac{1}{2}w^{T}(Z^{T}Z+\eta I)w-(Zd)^{T}w$$

Напомним, что $Z^{T}Z=Q\ \text{diag}(\Lambda_{1},\ldots,\Lambda_{n})\ Q^T$. Поэтому решение регрессии Тихонова —

$$(Z^{T}Z+\eta I)^{-1}(Zd)=Q\ \text{diag}\left(\frac{1}{\lambda_{1}+\eta},\cdots,\frac{1}{\lambda_{n}+\eta}\right)Q^T(Zd)$$

Регуляризацию можно понимать как функцию, которая «гасит» наибольшие собственные значения:

$$\text{регуляризованное по Тихонову } \lambda_i = \frac{1}{\lambda_{i}+\eta}=\frac{1}{\lambda_{i}}\left(1-\left(1+\lambda_{i}/\eta\right)^{-1}\right).$$

Градиентный спуск можно считать похожим затуханием, но с другой скоростью:

$$\text{регуляризованное градиентным спуском } \lambda_i = \frac{1}{\lambda_i} \left( 1-\left(1-\alpha\lambda_{i}\right)^{k} \right).$$

Заметьте, что это затухание зависит от шага.

Сноска 3. Это верно, потому что обновления можно записать в матричной форме:

$$\left(\!\!\begin{array}{cc} 1 & 0\\ \alpha & 1 \end{array}\!\!\right)\Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ 0 & 1 \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right),$$

откуда, обратив матрицу слева, получаем

$$\Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ -\alpha\beta & 1-\alpha\lambda_{i} \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right)=R^{k+1}\left(\!\!\begin{array}{c} x_{i}^{0}\\ y_{i}^{0} \end{array}\!\!\right)$$

Сноска 4. Скорости сходимости можно выписать явно. Собственные значения —

$$\begin{aligned} \sigma_{1} & =\frac{1}{2}\left(1-\alpha\lambda+\beta+\sqrt{(-\alpha\lambda+\beta+1)^{2}-4\beta}\right)\\[0.6em] \sigma_{2} & =\frac{1}{2}\left(1-\alpha\lambda+\beta-\sqrt{(-\alpha\lambda+\beta+1)^{2}-4\beta}\right) \end{aligned}$$

Когда $(-\alpha\lambda+\beta+1)^{2}-4\beta$ меньше нуля, корни комплексные, и скорость сходимости равна

$$|\sigma_{1}|=|\sigma_{2}| =\sqrt{\beta}.$$

Удивительно, но она не зависит ни от шага, ни от собственного значения $\alpha\lambda$. Когда корни вещественные, скорость сходимости равна

$$\max\{|\sigma_{1}|,|\sigma_{2}|\}=\tfrac{1}{2}\max\left\{ |1-\alpha\lambda_{i}+\beta\pm\sqrt{(1-\alpha\lambda_{i}+\beta)^{2}-4\beta}|\right\}$$

Прим. пер.: в оригинале модуль комплексных корней записан как $\sqrt{(1-\alpha\lambda+\beta)^{2}+|(-\alpha\lambda+\beta+1)^{2}-4\beta|}=2\sqrt{\beta}$ — без множителя $\tfrac12$ из формулы для $\sigma$. С этим множителем получается $|\sigma_1| = |\sigma_2| = \sqrt{\beta}$: произведение двух комплексно-сопряжённых корней равно $\det R = \beta$. Вывод автора — скорость не зависит от $\alpha\lambda$ — от этого не меняется.

Сноска 5. Это можно вывести, упростив неравенства для всех 4 + 1 случаев явной формулы скорости сходимости выше.

Сноска 6. Нужно оптимизировать

$$\min_{\alpha,\beta}\max\left\{ \bigg\| \! \left(\begin{array}{cc} \beta & \lambda_{1}\\ -\alpha\beta & 1-\alpha\lambda_{1} \end{array}\right) \! \bigg\|,\ldots,\bigg\| \! \left(\begin{array}{cc} \beta & \lambda_{n}\\ -\alpha\beta & 1-\alpha\lambda_{n} \end{array}\right)\! \bigg\|\right\}$$

(здесь $\|\cdot \|$ — модуль наибольшего собственного значения); оптимум достигается, когда у матриц, соответствующих крайним собственным значениям, корни характеристического многочлена кратные.

Сноска 7. Задача оптимизации выше ограничена снизу нулём, а вектор из всех $1$ этого нуля достигает.

Сноска 8. Явно её можно записать так:

$$[L_{G}]_{ij}=\begin{cases} \text{степень вершины }i & i=j\\ -1 & i\neq j,\ (i,j)\text{ или }(j,i)\in E\\ 0 & \text{иначе} \end{cases}$$

Сноска 9. Ошибку мы измеряем бесконечной нормой; похожие результаты выводятся для норм 1 и 2.

Сноска 10. Итерации momentum —

$$\begin{aligned} z^{k+1}&=\beta z^{k}+ A w^{k} + \text{error}(w^k) \\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}, \end{aligned}$$

что после замены переменных становится

$$\left(\!\!\begin{array}{cc} 1 & 0\\ \alpha & 1 \end{array}\!\!\right)\Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ 0 & 1 \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right)+\left(\!\!\begin{array}{c} \epsilon_{i}^{k}\\ 0 \end{array}\!\!\right)$$

Обратив матрицу $2 \times 2$ слева и применив формулу рекурсивно, получаем окончательное решение.

Сноска 11. Для одномерной функции $f(x)=\frac{\lambda}{2}x^{2}$ значение целевой функции равно

$$\begin{aligned}\mathbf{E}f(x^{k})&=\frac{\lambda}{2}\mathbf{E}[(x^{k})^{2}]\\&=\frac{\lambda}{2}\mathbf{E}\left(e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\epsilon^{k}e_{2}^{T}\sum_{i=1}^{k}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda}{2}\mathbf{E}\left(\epsilon^{k}e_{2}^{T}\sum_{i=1}^{k}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda}{2}\mathbf{E}[\epsilon^{k}]\,\cdot\,\sum_{i=1}^{k}\left(e_{2}^{T}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda\mathbf{E}[\epsilon^{k}]}{2}\cdot\sum_{i=1}^{k}\gamma_{i}^{2}, \qquad \gamma_i = e_{2}^{T}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right) \end{aligned}$$

В третьем равенстве используется то, что $\mathbf{E} \epsilon^k = 0$, в четвёртом — что ошибки некоррелированы.

Прим. пер.: формулы этой сноски воспроизведены как в оригинале. Строго говоря, в первом слагаемом детерминированная часть должна стоять в квадрате, а вместо $\mathbf{E}[\epsilon^k]$ — дисперсия $\mathbf{E}[(\epsilon^k)^2]$; на смысл разложения «детерминированная ошибка + стохастическая ошибка» это не влияет.

Словарик

EN	RU
momentum, heavy ball	momentum (метод тяжёлого шара)
step-size	шаг (learning rate)
pathological curvature	патологическая кривизна
convex quadratic	выпуклая квадратичная функция
eigenvalue decomposition, eigenspace	разложение по собственным значениям, собственное подпространство
condition number	число обусловленности
eigenfeatures	собственные признаки
early stopping	ранняя остановка
Tikhonov regression	регрессия Тихонова (гребневая, ridge)
damped harmonic oscillator	затухающий гармонический осциллятор
critical damping	критическое затухание
phase diagram	фазовая диаграмма
graph Laplacian	лапласиан графа
linear first order methods	линейные методы первого порядка
lower bound	нижняя граница
transient phase / stochastic phase	переходная фаза / стохастическая фаза
implicit regularizer	неявный регуляризатор

Оригинал: Gabriel Goh, «Why Momentum Really Works», Distill, 2017, distill.pub/2017/momentum, CC BY 4.0. Перевод распространяется на тех же условиях.