Стохастические и адаптивные оптимизаторы

Заметка о градиентном спуске закончилась двумя издержками. Каждый шаг читает все $n$ примеров, а число шагов растёт с числом обусловленности $\kappa$. Эта заметка борется с обеими. Первая издержка исчезает, если оценивать градиент по небольшой случайной выборке примеров: шаги становятся дешёвыми и шумными, и шум меняет то, как должен вести себя размер шага. Вторую уменьшают, запоминая прошлые градиенты (импульс) и давая каждой координате собственный размер шага (AdaGrad, RMSProp, Adam). Adam обучает почти все нейронные сети в курсах NLP и генеративных моделей, поэтому стоит точно знать, что делает каждая его строка.

Обозначения. Функция потерь — среднее по примерам, $Q(w) = \frac1n\sum_{i=1}^n \ell_i(w)$, где $\ell_i$ — потеря на примере $i$; для метода наименьших квадратов в этой заметке $\ell_i(w) = \frac12(\langle w, x_i\rangle - y_i)^2$. Мини-батч (minibatch) $S$ — случайное множество из $B$ индексов, $g = \frac1B\sum_{i \in S}\nabla\ell_i(w)$ — стохастический градиент (stochastic gradient), а одна эпоха — это $n/B$ шагов, один проход по данным. $\eta_k$ — размер шага на шаге $k$, $\beta$ — коэффициент импульса, $m$ и $v$ — скользящие средние градиентов и квадратов градиентов. Произведения и квадраты векторов в адаптивных методах берутся покоординатно. $H$, $\mu$, $L$ и $\kappa$ — как и раньше, гессиан, его крайние собственные числа и их отношение.

Градиент по выборке#

Градиент среднего — среднее градиентов, $\nabla Q(w) = \frac1n\sum_i\nabla\ell_i(w)$. Выберем один индекс $i$ равновероятно: тогда $E[\nabla\ell_i(w)] = \nabla Q(w)$, так что градиент по одному примеру — несмещённая оценка полного градиента. Усреднение $B$ независимо выбранных примеров сохраняет среднее и делит ковариационную матрицу на $B$:

$$E[g] = \nabla Q(w), \qquad \operatorname{Cov}(g) = \frac1B\,\Sigma(w), \qquad \Sigma(w) = \frac1n\sum_{i=1}^n \big(\nabla\ell_i(w) - \nabla Q(w)\big)\big(\nabla\ell_i(w) - \nabla Q(w)\big)^\top .$$

Это оценка среднего методом Монте-Карло, и её ошибка убывает как $1/\sqrt B$. Стохастический градиентный спуск (stochastic gradient descent, SGD) делает шаг $w \leftarrow w - \eta g$ с этой оценкой. Шаг стоит $O(Bd)$ вместо $O(nd)$. На практике примеры перемешивают один раз за эпоху и берут подряд идущими батчами — это выборка без возвращения, и шума у неё немного меньше, чем у независимых выборов из формулы.

Разобранный пример. На данных о диабете (442 пациента, 10 стандартизованных признаков, центрированная целевая переменная) в точке $w = 0$ среднеквадратичная ошибка градиента по мини-батчу, измеренная по 5000 случайных батчей, равна $238.6$ при $B = 1$, $75.6$ при $B = 10$ и $23.9$ при $B = 100$; формула $\sqrt{\operatorname{tr}\Sigma/B}$ даёт $238.8$, $75.5$ и $23.9$. В десять раз больше примеров на шаг покупают ошибку, меньшую в $\sqrt{10} = 3.16$ раза.

Зачем вообще мириться с шумом? Потому что в начале обучения полный градиент избыточен: выборка из нескольких сотен примеров уже указывает примерно в нужную сторону, а одна эпоха SGD делает $n/B$ шагов по цене одного полного. И нет причин оптимизировать функцию потерь на обучении намного точнее, чем обучающие данные определяют истинную точку минимума: статистическая ошибка $\hat w$ и так порядка $1/\sqrt n$ (Goodfellow, Bengio and Courville, 2016, раздел 8.1.3).

Постоянный шаг застревает в шумовом шаре#

Одномерный случай. Возьмём $Q(w) = \frac\lambda2 w^2$ и стохастический градиент $\lambda w + \xi$ с независимым шумом $\xi$, у которого среднее 0 и дисперсия $s^2$. Обновление имеет вид $w_{k+1} = (1 - \eta\lambda)w_k - \eta\xi_k$. Если $0 < \eta\lambda < 2$, дисперсия $V_k = \operatorname{Var}(w_k)$ подчиняется соотношению $V_{k+1} = (1 - \eta\lambda)^2 V_k + \eta^2 s^2$ и сходится к неподвижной точке

$$V_\infty = \frac{\eta^2 s^2}{1 - (1 - \eta\lambda)^2} = \frac{\eta s^2}{\lambda(2 - \eta\lambda)} \approx \frac{\eta s^2}{2\lambda} \quad (\eta\lambda \ll 1) .$$

Ожидаемый избыток потерь $\frac\lambda2 V_\infty$ примерно равен $\eta s^2/4$: он пропорционален шагу. При $\lambda = s = 1$ получаем $V_\infty = 0.1/1.9 = 0.0526$ для $\eta = 0.1$ и $0.01/1.99 = 0.0050$ для $\eta = 0.01$; 20 000 смоделированных запусков дают $0.053$ и $0.005$ (раздел «Код»). Шаг в десять раз меньше даёт дисперсию в десять раз меньше, шар примерно в $\sqrt{10} \approx 3.2$ раза уже, но приближается к нему в десять раз медленнее, поскольку среднее уменьшается за шаг в $1 - \eta\lambda$ раз.

Метод наименьших квадратов. Вблизи минимума шум градиента по одному примеру $x_i(\langle w, x_i\rangle - y_i)$ возникает в основном из шума в остатках: его ковариационная матрица примерно равна $\sigma^2 H$, если остатки имеют дисперсию $\sigma^2$ и не зависят от $x$. Применив одномерный результат к каждому собственному направлению, где дисперсия шума равна $\sigma^2\lambda_i$, получаем при малых шагах избыток потерь $\sum_i \eta\sigma^2\lambda_i/4 = \eta\sigma^2\operatorname{tr}(H)/4$.

Рисунок

Постоянный шаг останавливается в шумовом шаре

Рисунок показывает этот обмен на задаче, где всё можно вычислить. SGD с шагом $0.1$ за 50 примеров, десятую долю эпохи, доходит до уровня потерь, которого полный градиентный спуск достигает только примерно после пяти эпох, и дальше не улучшается; меньший шаг $0.02$ останавливается примерно в семь раз ниже ($0.0072$ против $0.050$ за последнюю эпоху; формула для малого шага предсказывает пять раз), но идёт туда дольше. Убывающий шаг (decreasing step) сочетает оба преимущества. Классические условия Роббинса и Монро (Robbins and Monro, 1951) таковы:

$$\sum_{k} \eta_k = \infty, \qquad \sum_{k} \eta_k^2 < \infty :$$

шаги должны в сумме давать бесконечное расстояние, чтобы можно было уйти от любой начальной точки, а накопленный шум, дисперсия которого складывается как $\sum\eta_k^2 s^2$, должен оставаться конечным. Шаги $\eta_k \propto 1/k$ удовлетворяют обоим условиям. Для $\mu$-сильно выпуклой функции потерь с ограниченными стохастическими градиентами шаг $\eta_k = 2/(\mu(k + 1))$ обеспечивает сходимость взвешенного среднего приближений со скоростью $O(1/k)$ (Bubeck, 2015, теорема 6.2) — намного медленнее линейной сходимости точного градиентного спуска: это цена шума.

В глубоком обучении убывание задают вручную в виде расписания (schedule), например уменьшая шаг в десять раз после заданного числа эпох или по косинусу; их разбирает заметка об обучении. На данных о диабете SGD с батчами по 32 и постоянным шагом $0.2$ заканчивает 30 эпох с избытком потерь $50.2$ (среднее по пяти начальным значениям генератора для перемешивания, при минимальной потере $1429.8$); уменьшение шага до $0.02$ после 15 эпох даёт в конце $5.1$. С постоянным шагом $0.05$ шумовой шар меньше, но конечная точка, $9.5$, теперь ограничена медленным продвижением вдоль самого пологого направления задачи с $\kappa = 470$, и то же уменьшение шага мало что меняет ($9.3$).

Шар можно уменьшить и усреднением приближений, не трогая шаг. Усреднение Поляка (Polyak averaging) выдаёт $\bar w_k = \frac1k\sum_{j \le k} w_j$ вместо последнего приближения; экспоненциальное скользящее среднее весов, с которым обучают диффузионные модели, — его современная форма (обучение DDPM на практике).

Импульс: запомнить направление#

У зигзага из предыдущей заметки простая причина: вдоль крутого направления градиент на каждом шаге меняет знак, а вдоль пологого он всё время указывает в одну сторону, но мал по величине. Усреднение недавних градиентов гасит первое и накапливает второе. Импульс (momentum), или метод тяжёлого шарика (heavy-ball method; Polyak, 1964), хранит скорость $v$:

$$v_{k+1} = \beta v_k + \nabla Q(w_k), \qquad w_{k+1} = w_k - \eta\, v_{k+1} .$$

В развёрнутом виде $v_{k+1} = \sum_{j \ge 0}\beta^j\nabla Q(w_{k-j})$ — экспоненциально взвешенная сумма прошлых градиентов. Когда градиент постоянен, скорость растёт до $\nabla Q/(1 - \beta)$, так что при $\beta = 0.9$ эффективный шаг вдоль устойчивого направления в десять раз больше $\eta$; компоненты, меняющие знак, в основном взаимно гасятся.

На квадратичной функции метод анализируется точно так же, как градиентный спуск, только теперь как двучленная рекурсия для каждого собственного направления (Goh, 2017). При наилучшем выборе $\eta = 4/(\sqrt L + \sqrt\mu)^2$ и $\beta = \big((\sqrt\kappa - 1)/(\sqrt\kappa + 1)\big)^2$ ошибка асимптотически уменьшается за шаг в

$$\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1} \quad \text{вместо} \quad \frac{\kappa - 1}{\kappa + 1} :$$

число шагов растёт как $\sqrt\kappa$, а не как $\kappa$. При $\kappa = 100$ множители равны $0.818$ и $0.980$. Множитель импульса — спектральный радиус двучленной рекурсии: он задаёт скорость на многих шагах, а не сжатие на каждом шаге. В отличие от градиентного спуска, тяжёлый шарик может сначала удалиться от минимума: из начальной точки рисунка ниже норма его ошибки за четыре шага растёт с $2.88$ до $8.98$ и только потом падает. На квадратичной функции с рисунка ниже, с собственными числами $4.5$ и $0.045$, тысячекратное уменьшение функции потерь занимает у градиентного спуска с наилучшим постоянным шагом 173 шага, а у оптимально настроенного тяжёлого шарика — 39.

Метод Нестерова (Nesterov’s method) вычисляет градиент в точке, куда скорость вот-вот перенесёт приближение, $v_{k+1} = \beta v_k + \nabla Q(w_k - \eta\beta v_k)$, в форме Sutskever et al. (2013). Заглядывание вперёд (look-ahead) поправляет скорость до того, как она проскочит минимум. С $\eta = 1/L$ и $\beta = (\sqrt\kappa - 1)/(\sqrt\kappa + 1)$ ему нужно 17 шагов на той же задаче, и, в отличие от тяжёлого шарика, он сохраняет скорость порядка $\sqrt\kappa$ на любой гладкой сильно выпуклой функции, а не только на квадратичных (Bubeck, 2015, теорема 3.18). Никакой метод, который лишь комбинирует градиенты, не может в худшем случае сделать лучше: для любого такого метода найдётся гладкая сильно выпуклая квадратичная функция в достаточно большой размерности, на которой ошибка после $k$ шагов составляет не меньше $\big((\sqrt\kappa - 1)/(\sqrt\kappa + 1)\big)^k$ от начальной (там же, теорема 3.15).

Оптимальным параметрам нужны $\mu$ и $L$, а они неизвестны. На практике берут $\beta = 0.9$ и подбирают $\eta$; при стохастических градиентах импульс ещё и усредняет шум, но его шумовой шар — как у эффективного шага $\eta/(1 - \beta)$, так что расписания по-прежнему нужны. На данных о диабете импульс $0.9$ с $\eta = 0.02$ (эффективный шаг $0.2$) заканчивает на $12.6$, а с уменьшением шага на полпути — на $5.4$.

Покоординатные шаги: AdaGrad и RMSProp#

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

AdaGrad (Duchi, Hazan and Singer, 2011) делит шаг каждой координаты на корень из суммы квадратов её градиентов:

$$G_{k} = G_{k-1} + g_k^2, \qquad w_{k+1} = w_k - \frac{\eta}{\sqrt{G_k} + \varepsilon}\, g_k .$$

Координата, которая видела большие градиенты, получает малые шаги; координата редкого признака, градиент которой в основном равен нулю, сохраняет большой шаг для тех немногих примеров, где признак встречается. Это подходит для разреженных задач: векторы слов GloVe обучают с помощью AdaGrad (GloVe). Слабость в том, что $G_k$ только растёт, поэтому все шаги стремятся к нулю, даже когда поверхность функции потерь перестаёт меняться.

RMSProp (Hinton, Srivastava and Swersky, 2012, лекция 6e) заменяет сумму экспоненциальным скользящим средним, $v_k = \rho v_{k-1} + (1 - \rho)g_k^2$ с $\rho = 0.9$, и делит на $\sqrt{v_k}$: шаг подстраивается под недавнюю величину градиента, а не под всю его историю.

Adam#

Adam (Kingma and Ba, 2015, алгоритм 1) хранит два скользящих средних и шагает на их отношение:

$$\begin{aligned} m_k &= \beta_1 m_{k-1} + (1 - \beta_1)\, g_k, & \hat m_k &= m_k / (1 - \beta_1^k), \\ v_k &= \beta_2 v_{k-1} + (1 - \beta_2)\, g_k^2, & \hat v_k &= v_k / (1 - \beta_2^k), \\ w_{k} &= w_{k-1} - \eta\, \hat m_k / \big(\sqrt{\hat v_k} + \varepsilon\big), & & \end{aligned}$$

где $m_0 = v_0 = 0$, а значения по умолчанию — $\eta = 10^{-3}$, $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\varepsilon = 10^{-8}$.

Откуда берётся поправка на смещение (bias correction; Kingma and Ba, 2015, раздел 3). Развернув рекурсию, получаем $m_k = (1 - \beta_1)\sum_{i=1}^k \beta_1^{k-i} g_i$. Если у градиентов постоянное среднее $E[g]$, то $E[m_k] = (1 - \beta_1)\sum_{i=1}^k\beta_1^{k-i}\,E[g] = (1 - \beta_1^k)\,E[g]$ по формуле геометрической прогрессии. Среднее, начатое с нуля, занижает математическое ожидание в $1 - \beta_1^k$ раз — на первом шаге это $0.1$, — и деление на этот множитель убирает смещение; то же верно для $v_k$ с $\beta_2$. Без поправки первый шаг был бы равен $\eta\cdot 0.1\,g/\sqrt{0.001\,g^2} = 3.16\,\eta$ по каждой координате, а при $\beta_2 = 0.999$ оценка второго момента сотни шагов оставалась бы слишком малой.

Разобранный пример. Первый градиент $g_1 = (100, 0.01)$. Тогда $\hat m_1 = g_1$ и $\hat v_1 = g_1^2$, так что первый шаг равен $\eta\,(1, 1)$: каждая координата сдвигается на $\eta$ против знака своего градиента, хотя два градиента различаются в $10^4$ раз. Обычный градиентный спуск сдвинул бы первую координату в $10^4$ раз дальше второй.

Рисунок

Импульс и Adam на вытянутой чаше

Рисунок показывает, что это даёт и чего не даёт. Когда долина вытянута вдоль осей координат, как бывает, когда признаки имеют разные масштабы, но не коррелированы, деление на $\sqrt{\hat v}$ выравнивает кривизны почти так же, как стандартизация, и Adam нужно 13 шагов против 173 у градиентного спуска. Когда та же долина повёрнута, как бывает при коррелированных признаках, никакое перемасштабирование осей не сделает её круглой, и Adam нужен 171 шаг. Градиентный спуск и импульс зависят только от геометрии функции потерь, поэтому делают ровно столько же шагов в обеих панелях; Adam зависит от системы координат. Его масштабирование — диагональное приближение кривизны, эффективное, когда кривизна в основном диагональна.

Три оговорки из практики и теории:

• Размер шага по-прежнему важен. На данных о диабете Adam с $\eta = 0.01$ заканчивает 30 эпох с избытком потерь $836.6$, а с $\eta = 1$ — с $8.4$. Значения по умолчанию подходят сетям с весами порядка 1, а не задаче, коэффициенты которой исчисляются десятками.
• Adam может не сходиться. Reddi, Kale and Kumar (2018) строят выпуклые задачи, на которых Adam не сходится к оптимуму при любых фиксированных $\beta_1$, $\beta_2$ из диапазона, включающего обычные $0.9$ и $0.999$ (теоремы 1–3), потому что скользящее среднее $v$ забывает редкий большой градиент; их AMSGrad использует вместо этого текущий максимум $v$.
• Другие решения. На задачах со многими точками минимума адаптивные методы могут сходиться не к тем, к которым сходится SGD; Wilson et al. (2017) нашли несколько задач, где они обобщали хуже. Затухание весов (weight decay) тоже взаимодействует с делением на $\sqrt{\hat v}$, поэтому AdamW применяет его отдельно (затухание весов в Adam).

Для проверки формул: обновление выше, записанное на NumPy, и torch.optim.Adam дают одинаковые веса после 100 шагов на задаче о диабете с точностью до $9 \cdot 10^{-15}$ (раздел «Код»).

Что изменилось#

	Градиентный спуск	SGD	SGD с импульсом	Adam
Градиент	точный, $O(nd)$	по $B$ примерам, $O(Bd)$	по $B$ примерам	по $B$ примерам
Постоянный шаг	сходится	застревает в шаре, дисперсия $\propto\eta$	застревает, шар эффективного шага $\eta/(1 - \beta)$	застревает
Зависимость от $\kappa$ (квадратичная функция, точные градиенты)	$\kappa$	$\kappa$	$\sqrt\kappa$ при настроенных $\eta, \beta$	диагональная часть убрана, повёрнутая — нет
Память на вес	нет	нет	одна скорость	два момента
Типичное применение	небольшие гладкие задачи	выпуклые модели, с расписанием	сети для зрения, с расписанием	трансформеры, большая часть глубокого обучения (как AdamW)

Ограничения#

• Шуму нужно расписание. Если шум градиента остаётся ненулевым в минимуме, никакой постоянный шаг не сходится; расписание добавляет гиперпараметры. Исключение — интерполяция: если один вектор весов точно подгоняет каждый пример, как в методе наименьших квадратов с числом признаков больше числа примеров, все градиенты по отдельным примерам там обращаются в ноль, и SGD с постоянным шагом может к нему сойтись. Перепараметризованные модели, подгоняющие обучающую выборку, близки к этому режиму — это постановка оговорки о двойном спуске.
• Оптимальной настройке импульса нужны $\mu$ и $L$. Скорость $\sqrt\kappa$ достигается при наилучших параметрах; при $\beta = 0.9$ и угаданном $\eta$ выигрыш меньше, а слишком большой импульс приводит к колебаниям.
• Адаптивные методы видят только диагональ. Коррелированные признаки оставляют повёрнутую долину, которую покоординатные шаги не могут выпрямить.
• Ни один метод не избавляет от подбора $\eta$. Значения по умолчанию работают для одних семейств моделей и ошибаются на порядки для других.
• Для сетей теория и практика расходятся. Гарантии получены для выпуклых функций потерь; для нейронных сетей выбор опирается на эксперименты.

Что нужно запомнить#

• Градиент по мини-батчу — несмещённая оценка полного градиента с ковариационной матрицей $\Sigma/B$: ошибка $\propto 1/\sqrt B$, стоимость $\propto B$.
• При постоянном шаге SGD оседает в шумовом шаре: избыток потерь примерно $\eta s^2/4$ в одномерном случае и $\eta\sigma^2\operatorname{tr}(H)/4$ для метода наименьших квадратов. Убывающие шаги с $\sum\eta_k = \infty$, $\sum\eta_k^2 < \infty$ сходятся; на практике — расписания.
• Импульс, $v \leftarrow \beta v + g$, $w \leftarrow w - \eta v$, накапливает устойчивые направления и гасит колеблющиеся; на квадратичных функциях ему нужно $\sqrt\kappa$ шагов вместо $\kappa$. Заглядывание вперёд у Нестерова сохраняет эту скорость на всех гладких сильно выпуклых функциях.
• AdaGrad делит на корень из накопленных квадратов градиентов (хорошо для разреженных признаков, шаги уменьшаются бесконечно); RMSProp — на их скользящее среднее.
• Adam = импульс + RMSProp + поправка на смещение $1/(1 - \beta^k)$; его первый шаг равен $\eta\,\mathrm{sign}(g)$. Он исправляет различия масштаба между координатами, но не корреляции, и его размер шага всё равно нужно подбирать.

Код#

Шумовой шар, шум мини-батчей, импульс и метод Нестерова против числа обусловленности, Adam на двух чашах, поправка на смещение, сверка с PyTorch и оптимизаторы на данных о диабете:

import numpy as np, torch
from sklearn.datasets import load_diabetes

rng = np.random.default_rng(0)

# шумовой шар в одномерном случае: Q(w) = w^2 / 2, стохастический градиент w + шум с дисперсией 1
for eta in (0.1, 0.01):
    w = np.zeros(20_000)                                 # 20 000 независимых запусков из w = 0
    for k in range(int(20 / eta)):
        w = w - eta * (w + rng.normal(size=w.size))
    print(eta, round(w.var(), 4), round(eta / (2 - eta), 4))   # смоделированная и стационарная дисперсия w
# 0.1 0.053 0.0526 | 0.01 0.005 0.005

# градиенты по мини-батчам на диабете (стандартизованные признаки, центрированная цель) в w = 0: ошибка убывает как 1/sqrt(B)
X, y = load_diabetes(return_X_y=True)
X = (X - X.mean(0)) / X.std(0); y = y - y.mean(); n = len(y)
G = X * (-y)[:, None]                                    # градиенты (x^T w - y)^2 / 2 по отдельным примерам в w = 0
g = G.mean(0)
for B in (1, 10, 100):
    err = [np.linalg.norm(G[rng.integers(0, n, B)].mean(0) - g) for _ in range(5000)]
    print(B, round(float(np.sqrt(np.mean(np.square(err)))), 1), round(float(np.sqrt(np.trace(np.cov(G.T, bias=True)) / B)), 1))
# 1 238.6 238.8 | 10 75.6 75.5 | 100 23.9 23.9

# квадратичная функция с собственными числами 0.045 и 4.5 (kappa = 100): шаги до уменьшения избытка потерь в 1000 раз
mu, L = 0.045, 4.5
c, s = np.cos(np.pi / 6), np.sin(np.pi / 6); R = np.array([[c, -s], [s, c]])
H1 = np.diag([L, mu]); H2 = R @ H1 @ R.T                 # одна и та же чаша, вдоль осей и повёрнутая на 30 градусов
def steps(H, w0, method, eta, beta=0.0, K=2000):
    w, v, m, s2 = w0.copy(), np.zeros(2), np.zeros(2), np.zeros(2)
    q0 = w0 @ H @ w0
    for k in range(1, K + 1):
        g = H @ w
        if method == 'gd': w = w - eta * g
        if method == 'momentum': v = beta * v + g; w = w - eta * v
        if method == 'nesterov':
            g = H @ (w - eta * beta * v); v = beta * v + g; w = w - eta * v
        if method == 'adam':
            m = 0.9 * m + 0.1 * g; s2 = 0.999 * s2 + 0.001 * g * g
            w = w - eta * (m / (1 - 0.9 ** k)) / (np.sqrt(s2 / (1 - 0.999 ** k)) + 1e-8)
        if w @ H @ w < 1e-3 * q0: return k
w0 = np.array([-2.4, 1.6])
rk = np.sqrt(L / mu)
print(round((L - mu) / (L + mu), 3), round((rk - 1) / (rk + 1), 3),
      steps(H1, w0, 'gd', 2 / (L + mu)), steps(H1, w0, 'momentum', 4 / (np.sqrt(L) + np.sqrt(mu)) ** 2, ((rk - 1) / (rk + 1)) ** 2),
      steps(H1, w0, 'nesterov', 1 / L, (rk - 1) / (rk + 1)))
# 0.98 0.818 173 39 17: асимптотические множители за шаг у GD и импульса; шаги GD, оптимального тяжёлого шарика, Нестерова
w, v, norms = w0.copy(), np.zeros(2), []
for _ in range(10):
    v = ((rk - 1) / (rk + 1)) ** 2 * v + H1 @ w; w = w - 4 / (np.sqrt(L) + np.sqrt(mu)) ** 2 * v; norms.append(np.linalg.norm(w))
print(round(float(np.linalg.norm(w0)), 2), round(float(max(norms)), 2), int(np.argmax(norms)) + 1)
# 2.88 8.98 4: оптимальный тяжёлый шарик сначала удаляется, норма ошибки 2.88 -> 8.98 за 4 шага
for name, H, start in (('aligned', H1, w0), ('rotated', H2, R @ w0)):
    print(name, steps(H, start, 'gd', 2 / (L + mu)), steps(H, start, 'momentum', 0.05, 0.9), steps(H, start, 'adam', 0.2))
# aligned 173 48 13 | rotated 173 48 171

# первый шаг Adam равен eta * sign(g) по каждой координате при любом масштабе градиента; без поправки на смещение — в 3.16 раза больше
g1 = np.array([100.0, 0.01])
m1, v1 = 0.1 * g1, 0.001 * g1 ** 2
print((m1 / 0.1) / np.sqrt(v1 / 0.001), (m1 / np.sqrt(v1)).round(2))   # [1. 1.] [3.16 3.16]

# наш Adam совпадает с torch.optim.Adam; затем SGD, импульс и Adam на диабете, 30 эпох мини-батчами по 32
Xt, yt = torch.tensor(X), torch.tensor(y)
w_hat = np.linalg.lstsq(X, y, rcond=None)[0]; q_hat = 0.5 * np.mean((X @ w_hat - y) ** 2)
loss = lambda w: 0.5 * ((Xt @ w - yt) ** 2).mean()
wt = torch.zeros(10, dtype=torch.float64, requires_grad=True); opt = torch.optim.Adam([wt], lr=0.1)
wm, m, v = np.zeros(10), np.zeros(10), np.zeros(10)
for k in range(1, 101):
    opt.zero_grad(); loss(wt).backward(); opt.step()
    gm = X.T @ (X @ wm - y) / n; m = 0.9 * m + 0.1 * gm; v = 0.999 * v + 0.001 * gm ** 2
    wm = wm - 0.1 * (m / (1 - 0.9 ** k)) / (np.sqrt(v / (1 - 0.999 ** k)) + 1e-8)
print(f'{np.abs(wt.detach().numpy() - wm).max():.0e}')   # 9e-15
def train(make, cut_at=None, seeds=5):                  # средний избыток потерь после 30 эпох по 5 начальным значениям перемешивания
    out = []
    for seed in range(seeds):
        torch.manual_seed(seed)
        wt = torch.zeros(10, dtype=torch.float64, requires_grad=True); opt = make([wt])
        for epoch in range(30):
            if epoch == cut_at:                          # делим шаг обучения на 10 на полпути
                for group in opt.param_groups: group['lr'] /= 10
            for idx in torch.randperm(n).split(32):
                opt.zero_grad(); (0.5 * ((Xt[idx] @ wt - yt[idx]) ** 2).mean()).backward(); opt.step()
        out.append(loss(wt).item() - q_hat)
    return round(float(np.mean(out)), 1)
print(round(q_hat, 1), round(float(np.linalg.cond(X.T @ X)), 0))   # 1429.8 470.0: минимальная потеря и kappa
for name, make in (('sgd 0.05', lambda p: torch.optim.SGD(p, lr=0.05)), ('sgd 0.2', lambda p: torch.optim.SGD(p, lr=0.2)),
                   ('momentum 0.02', lambda p: torch.optim.SGD(p, lr=0.02, momentum=0.9)),
                   ('adam 0.01', lambda p: torch.optim.Adam(p, lr=0.01)), ('adam 1', lambda p: torch.optim.Adam(p, lr=1.0))):
    print(name, train(make), train(make, cut_at=15))
# sgd 0.05 9.5 9.3 | sgd 0.2 50.2 5.1 | momentum 0.02 12.6 5.4 | adam 0.01 836.6 1083.5 | adam 1 8.4 8.7

Дальше#

Метод наименьших квадратов теперь можно обучить при любых $n$ и $d$ — по формуле или спуском. Но то, что модель можно обучить, ещё не делает её хорошей. При большом числе признаков или признаках, почти повторяющих друг друга, заметка о методе наименьших квадратов показала коэффициенты, которые скачут при каждой реализации шума, и $R^2$ на обучении, который растёт, пока $R^2$ на валидации рушится. Следующая заметка добавляет штраф на величину весов: гребневая регрессия и лассо, стоящие за ними априорные распределения и выбор силы штрафа по валидации.

Оптимизаторы этой заметки обучают сети других курсов: Adam и AdamW — выбор по умолчанию в обучении моделей курса генеративных моделей, а следующий раздел этого курса использует их для нейронных сетей.

Литература#

• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 3: оценивание градиента, стохастический градиентный спуск, импульс, AdaGrad, RMSProp и Adam.
• H. Robbins, S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22(3), 1951.
• B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5), 1964.
• I. Sutskever, J. Martens, G. Dahl, G. Hinton. On the importance of initialization and momentum in deep learning. ICML, 2013. Раздел 2 (метод Нестерова как импульс с градиентом, вычисленным с заглядыванием вперёд).
• G. Goh. Why momentum really works. Distill, 2017. Раздел об оптимальных параметрах.
• S. Bubeck. Convex optimization: algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4), 2015. Теорема 3.15 (нижняя оценка для методов первого порядка), теорема 3.18 (ускоренный метод Нестерова), теорема 6.2 (SGD для сильно выпуклых функций).
• J. Duchi, E. Hazan, Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12, 2011.
• G. Hinton, N. Srivastava, K. Swersky. Neural networks for machine learning, lecture 6: overview of mini-batch gradient descent. Lecture materials, University of Toronto, 2012. Лекция 6e (RMSProp).
• D. P. Kingma, J. Ba. Adam: a method for stochastic optimization. ICLR, 2015. Алгоритм 1, раздел 3 (поправка на смещение при инициализации).
• S. J. Reddi, S. Kale, S. Kumar. On the convergence of Adam and beyond. ICLR, 2018. Теоремы 1–3, раздел 4 (AMSGrad).
• A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, B. Recht. The marginal value of adaptive gradient methods in machine learning. NeurIPS, 2017.
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. Раздел 8.1.3 (пакетные алгоритмы и алгоритмы на мини-батчах), раздел 8.3 (SGD, импульс, импульс Нестерова), раздел 8.5 (AdaGrad, RMSProp, Adam), раздел 8.7.3 (усреднение Поляка).