Градиентный спуск

Заметка о методе наименьших квадратов закончилась двумя проблемами замкнутой формулы. Ей нужна матрица $X^\top X$ размера $d \times d$ и решение системы за $O(d^3)$, что недостижимо для миллиона признаков; и она существует только для квадратичной ошибки, а у функции потерь Хьюбера, абсолютной ошибки и всех функций потерь классификации в этом курсе формулы для точки минимума нет. У обеих проблем один ответ. Вместо того чтобы решать уравнение на точку, где градиент обращается в ноль, будем идти к ней: начнём где угодно, вычислим градиент, сделаем небольшой шаг против него и повторим. Эта заметка разбирает такое движение на методе наименьших квадратов, где всё вычисляется точно, а затем формулирует, что сохраняется для общих функций потерь.

Обозначения. $Q(w)$ — минимизируемая функция потерь, здесь среднеквадратичная ошибка $\frac1n\lVert Xw - y\rVert^2$ из заметки о методе наименьших квадратов с матрицей признаков $X \in \mathbb R^{n \times d}$, а $\hat w$ — её точка минимума. $\nabla Q(w)$ — градиент, $w^{(k)}$ — приближение после $k$ шагов, $\eta > 0$ — размер шага, или шаг обучения (learning rate). Для метода наименьших квадратов гессиан — постоянная матрица $A = \frac2n X^\top X$; её наименьшее и наибольшее собственные числа — $\mu$ и $L$, а $\kappa = L/\mu$ — её число обусловленности (condition number).

В какую сторону вниз?#

Вблизи точки $w$ дифференцируемая функция близка к своему линейному приближению:

$$Q(w + h) = Q(w) + \langle \nabla Q(w), h\rangle + o(\lVert h\rVert) .$$

Среди всех шагов $h$ фиксированной малой длины $\varepsilon$ изменение определяется главным образом членом $\langle \nabla Q(w), h\rangle$, а он по неравенству Коши–Буняковского не меньше $-\varepsilon\lVert\nabla Q(w)\rVert$, причём равенство достигается только при $h = -\varepsilon\,\nabla Q(w)/\lVert\nabla Q(w)\rVert$. Антиградиент — направление наискорейшего спуска, и достаточно малый шаг вдоль него уменьшает $Q$, если градиент не равен нулю. Градиентный спуск (gradient descent) повторяет такие шаги:

$$w^{(k+1)} = w^{(k)} - \eta\, \nabla Q\big(w^{(k)}\big) .$$

Для метода наименьших квадратов градиент из вывода нормальных уравнений, делённый на $n$, равен

$$\nabla Q(w) = \frac2n X^\top (Xw - y) ,$$

это два произведения матрицы на вектор, $O(nd)$ операций, и всего $O(\text{число ненулевых элементов})$, когда $X$ разреженная. Ничего размера $d \times d$ не строится.

Разобранный пример. Четыре точки из заметки о методе наименьших квадратов, $x = (0, 1, 2, 3)$, $y = (1, 3, 2, 5)$, со столбцами $1$ и $x$. В точке $w^{(0)} = 0$ остаток равен $-y$, поэтому $\nabla Q = -\frac12 X^\top y = -\frac12 (11, 22) = (-5.5, -11)$, а $Q = (1 + 9 + 4 + 25)/4 = 9.75$. При $\eta = 0.2$ получаем $w^{(1)} = (1.1, 2.2)$ и $Q = 4.91$; следующий градиент равен $(3.3, 7.7)$, $w^{(2)} = (0.44, 0.66)$ и $Q = 2.659$. Функция потерь убывает к своему минимуму $2.7/4 = 0.675$ в точке $\hat w = (1.1, 1.1)$, но коэффициент наклона прошёл от 0 мимо цели до $2.2$ и вернулся к $0.66$. Этому перескоку посвящён следующий раздел.

Какой длины шаг? Квадратичный случай#

Для метода наименьших квадратов функция потерь вокруг минимума в точности квадратична. Её градиент обращается в ноль в $\hat w$, а гессиан всюду равен $A$, поэтому

$$Q(w) = Q(\hat w) + \tfrac12 (w - \hat w)^\top A\, (w - \hat w), \qquad \nabla Q(w) = A\,(w - \hat w) .$$

Обозначим ошибку $e^{(k)} = w^{(k)} - \hat w$. Один шаг даёт

$$e^{(k+1)} = e^{(k)} - \eta A\, e^{(k)} = (I - \eta A)\, e^{(k)} .$$

Матрица $A$ симметрична, её собственные числа $\mu = \lambda_1 \le \dots \le \lambda_d = L$, а собственные векторы $u_1, \dots, u_d$ ортонормированы. В этом базисе $I - \eta A$ диагональна, и компонента ошибки вдоль $u_i$ на каждом шаге умножается на $1 - \eta\lambda_i$ независимо от остальных. Три следствия:

• Наибольший безопасный шаг. Все компоненты уменьшаются из любой начальной точки тогда и только тогда, когда $\lvert 1 - \eta\lambda_i\rvert < 1$ для всех $i$, то есть $0 < \eta < 2/L$ (при $\mu > 0$). При $\eta > 2/L$ самая крутая компонента на каждом шаге меняет знак и растёт: спуск расходится почти из любой начальной точки, как бы близко к минимуму она ни была; избегает этого только начальная точка, у которой самая крутая компонента в точности равна нулю.
• Наилучший постоянный шаг. Скорость задаёт худший множитель $\rho(\eta) = \max\big(\lvert 1 - \eta\mu\rvert, \lvert 1 - \eta L\rvert\big)$. Первый член убывает по $\eta$, а второй с некоторого момента растёт, поэтому максимум наименьший там, где $1 - \eta\mu = \eta L - 1$: $\eta^* = 2/(L + \mu)$, при этом $\rho^* = \dfrac{L - \mu}{L + \mu} = \dfrac{\kappa - 1}{\kappa + 1}$.
• Число шагов. Чтобы уменьшить ошибку до доли $\varepsilon$ от начальной, нужно $\ln(1/\varepsilon)/\ln(1/\rho^*)$ шагов, а $\ln\frac{\kappa + 1}{\kappa - 1} \approx 2/\kappa$ при больших $\kappa$, так что примерно $\tfrac{\kappa}{2}\ln(1/\varepsilon)$: линейно по числу обусловленности.

Рисунок

Во сколько раз шаг сокращает ошибку

Разобранный пример. Для четырёх точек $A = \frac24 X^\top X = \begin{pmatrix} 2 & 3 \\ 3 & 7\end{pmatrix}$. Её след равен 9, определитель — 5, поэтому собственные числа равны $(9 \pm \sqrt{61})/2$: $\mu = 0.595$ и $L = 8.405$, $\kappa = 14.1$. Шаги больше $2/L = 0.238$ расходятся; наилучший шаг — $2/(L + \mu) = 2/9 = 0.222$ с множителем $\rho^* = 0.868$, и тысячекратное уменьшение ошибки занимает $\ln 1000/\ln(1/0.868) = 49$ шагов. У шага $\eta = 1/L = 0.119$, привычного безопасного выбора по умолчанию, оценка множителя — $1 - 1/\kappa = 0.929$, и из $w = 0$ ему нужно 80 шагов. В примере из заметки о данных и признаках два признака в масштабах 1 и 100 дают $\kappa \approx 10^4$, и то же тысячекратное уменьшение требует примерно $\tfrac{10^4}{2}\ln 1000 \approx 35\,000$ шагов.

Почему ошибка вдоль $u_1$ убывает так медленно? Потому что $\mu$ — кривизна в самом пологом направлении: градиент там мал, поэтому и шаги малы, а размер шага нельзя увеличить из-за самого крутого направления. Приближение мечется зигзагом поперёк узкой долины и ползёт вдоль её дна.

Масштабирование признаков#

Собственные числа $A = \frac2n X^\top X$ зависят от единиц измерения признаков. В примере с четырьмя точками внедиагональный элемент $A$ равен $\frac2n\sum_i x_i = 3$ — это связь между свободным членом и наклоном, которую создаёт ненулевое среднее признака, а диагональные элементы 2 и 7 различаются потому, что второй момент $x$ больше, чем у константного столбца. Центрирование $x$ обнуляет связь; масштабирование к единичной дисперсии выравнивает диагональ. Для стандартизованного признака $(x - 1.5)/1.118$ получаем $A = 2I$, $\kappa = 1$: кривизна во всех направлениях одинакова, градиент указывает прямо в минимум, и шаг $\eta = 2/(L + \mu) = 0.5$ попадает в $\hat w$ за один шаг.

Рисунок

Градиентный спуск на вытянутой и на круглой чаше

На реальных данных эффект велик. На данных о вине из scikit-learn, где содержание алкоголя предсказывается по остальным 12 измерениям (их стандартные отклонения — примерно от 0.1 до 300), число обусловленности гессиана метода наименьших квадратов равно $1.6 \cdot 10^8$ на исходных признаках и 45 после стандартизации. Градиентный спуск с $\eta = 1/L$ уменьшает избыток потерь $Q(w) - Q(\hat w)$ относительно начального значения до $10^{-1}$, $9 \cdot 10^{-2}$, $2 \cdot 10^{-2}$ и $10^{-2}$ за 10, 100, 1000 и 10 000 шагов на исходных признаках; на стандартизованных — до $8 \cdot 10^{-3}$ за 10 шагов, $2 \cdot 10^{-8}$ за 100 и до машинной точности за 1000 (раздел «Код»). Оставшееся $\kappa = 45$ масштабирование убрать не может: оно возникает из корреляций между признаками. Для этого понадобился бы ещё и поворот — его фактически и применяют методы второго порядка.

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

За пределами квадратичных функций: что гарантировано#

Большинство функций потерь не квадратичны, но анализ переносится на них через два свойства. Дифференцируемая $Q$ называется $L$-гладкой (L-smooth), если её градиент $L$-липшицев, $\lVert\nabla Q(u) - \nabla Q(v)\rVert \le L\lVert u - v\rVert$; для дважды дифференцируемой $Q$ это значит, что ни одно собственное число гессиана не превосходит $L$ по модулю. Она $\mu$-сильно выпукла (μ-strongly convex), если $Q(v) \ge Q(u) + \langle\nabla Q(u), v - u\rangle + \frac\mu2\lVert v - u\rVert^2$; для дважды дифференцируемой $Q$ все собственные числа гессиана не меньше $\mu$. Метод наименьших квадратов с независимыми столбцами обладает обоими свойствами с $\mu$ и $L$ матрицы $A$.

Лемма о спуске (descent lemma). Гладкость ограничивает функцию сверху параболой: $Q(v) \le Q(u) + \langle\nabla Q(u), v - u\rangle + \frac L2\lVert v - u\rVert^2$. Подставим $v = u - \eta\nabla Q(u)$:

$$Q\big(u - \eta\nabla Q(u)\big) \le Q(u) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert\nabla Q(u)\rVert^2 .$$

Каждый шаг с $0 < \eta < 2/L$ уменьшает функцию потерь — тот же порог, что и в квадратичном случае, — а гарантированное уменьшение наибольшее при $\eta = 1/L$, где оно равно $\lVert\nabla Q(u)\rVert^2/(2L)$. Отсюда три гарантии. Это теория, стоящая за практической процедурой, которой ни одна из скоростей не нужна: вычислить градиент, проверить, что функция потерь падает на каждом шаге, отмасштабировать входы и взять наибольший шаг, при котором спуск не расходится.

• Невыпуклая $L$-гладкая функция, $\eta = 1/L$. Суммируя уменьшения за $K$ шагов, получаем $\frac{1}{2L}\sum_{k < K}\lVert\nabla Q(w^{(k)})\rVert^2 \le Q(w^{(0)}) - Q(w^{(K)}) \le Q(w^{(0)}) - \inf Q$, поэтому наименьшая встреченная норма градиента удовлетворяет $\min_{k < K}\lVert\nabla Q(w^{(k)})\rVert^2 \le 2L\big(Q(w^{(0)}) - \inf Q\big)/K$. Градиент становится малым, и только: пределом может оказаться локальный минимум или седловая точка. Это единственная общая гарантия для нейронных сетей, и она предполагает гладкость, которой у сетей с активациями ReLU нет всюду.
• Выпуклая $L$-гладкая функция, $\eta = 1/L$. $Q(w^{(k)}) - Q(\hat w) \le 2L\lVert w^{(0)} - \hat w\rVert^2/k$ (Bubeck, 2015, теорема 3.3): избыток потерь убывает как $1/k$.
• $\mu$-сильно выпуклая и $L$-гладкая функция, $\eta = 2/(L + \mu)$. $Q(w^{(k)}) - Q(\hat w) \le \frac L2 \exp\big(-\frac{4k}{\kappa + 1}\big)\lVert w^{(0)} - \hat w\rVert^2$ (Bubeck, 2015, теорема 3.12): линейная сходимость, при которой число шагов пропорционально $\kappa$, как на квадратичной функции.

Когда у $X$ зависимые столбцы, метод наименьших квадратов выпуклый, но не сильно выпуклый ($\mu = 0$): точка минимума не единственна, и общая теорема для выпуклых функций выше даёт лишь скорость $1/k$. Но метод наименьших квадратов остаётся фиксированной квадратичной функцией, и анализ по собственным векторам из квадратичного случая по-прежнему работает: при $0 < \eta < 2/L$ компоненты ошибки вдоль собственных векторов с положительными собственными значениями убывают геометрически, со скоростью, заданной наименьшим положительным собственным значением, а компонента в ядре $A$ не меняется вовсе. Градиентный спуск, начатый из $w = 0$, тогда сходится геометрически к решению с минимальной нормой, потому что каждый шаг добавляет вектор вида $X^\top v$ и остаётся в пространстве строк $X$.

Выбор шага на практике#

$L$ редко известна. Три практических ответа:

• Сетка в логарифмическом масштабе. Попробовать $\eta = 1, 0.1, 0.01, \dots$ на несколько сотен шагов и оставить наибольший, при котором спуск не расходится. Функция потерь, которая растёт с первых шагов, означает, что $\eta$ больше $2/L$.
• Линейный поиск с возвратом (backtracking line search). На каждом шаге начать с большого $\eta$ и делить его пополам, пока не выполнится $Q(w - \eta g) \le Q(w) - \frac\eta2\lVert g\rVert^2$, где $g = \nabla Q(w)$ (Boyd and Vandenberghe, 2004, раздел 9.2, здесь с константой 1/2). По лемме о спуске любой $\eta \le 1/L$ проходит проверку, поэтому поиск заканчивается с $\eta \ge 1/(2L)$, и знать $L$ не нужно. Кроме того, он принимает более длинные шаги, когда градиент направлен вдоль пологого направления. На стандартизованной задаче о вине, где $1/L = 0.108$, 100 шагов с возвратом, начиная с $\eta = 1$, приняли $0.0625$ двенадцать раз, $0.125$ — 41 раз, $0.25$ — девять раз, $0.5$ — двенадцать раз и $1$ — 26 раз и закончили с нормой градиента $2 \cdot 10^{-6}$, против $10^{-3}$ после 100 шагов с фиксированным $\eta = 1/L$.
• Остановка. Останавливаться, когда норма градиента или относительное уменьшение $Q$ падает ниже допуска. В машинном обучении есть критерий лучше, чем функция потерь на обучении: остановиться, когда функция потерь на валидации перестаёт улучшаться. Тогда число шагов работает как регуляризатор, как показывает заметка об обучении.

Метод Ньютона (Newton’s method) использует ещё и кривизну: $w \leftarrow w - (\nabla^2 Q)^{-1}\nabla Q$. На квадратичной функции он попадает в $\hat w$ за один шаг из любой точки, потому что решает нормальные уравнения; в общем случае вблизи минимума он сходится за несколько шагов ценой решения системы размера $d \times d$ на каждом шаге. Заметка о логистической регрессии использует его там, где $d$ мало. Градиентный спуск — метод, который масштабируется.

Функции потерь без замкнутой формулы#

Градиентному спуску нужен только градиент, поэтому он без изменений работает для функций потерь, с которыми не справлялась замкнутая формула. Для функции потерь Хьюбера с порогом $\delta$ производная $\rho_\delta(r)$ — это остаток, обрезанный до $[-\delta, \delta]$, поэтому

$$\nabla Q(w) = -\frac1n X^\top \operatorname{clip}(y - Xw,\, -\delta,\, \delta) .$$

Вторая производная $\rho_\delta$ не больше 1, поэтому $Q$ является $L$-гладкой с $L$, равным наибольшему собственному числу $\frac1n X^\top X$, и шаг $\eta = 1/L$ безопасен. На десяти точках с одним выбросом из заметки о методе наименьших квадратов 5000 шагов приходят в $(0.986, 0.533)$ — прямую Хьюбера с рисунка той заметки. Абсолютная ошибка недифференцируема при нулевом остатке; градиент можно заменить её субградиентом $\operatorname{sign}(r)$, но для сходимости субградиентные шаги должны со временем уменьшаться — это тема следующей заметки. Заметки о логистической регрессии и линейных классификаторах применяют то же обновление к функциям потерь классификации, обратное распространение ошибки вычисляет градиент для нейронных сетей, а градиентный бустинг делает шаги в пространстве функций.

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

	Нормальные уравнения	Градиентный спуск
Что нужно	$X^\top X$ и решение системы $d \times d$	градиент, $O(nd)$ на шаг
Стоимость	$O(nd^2 + d^3)$ один раз	$O(nd)$, умноженное примерно на $\kappa\ln(1/\varepsilon)$ шагов
Функции потерь	только квадратичная ошибка	любая дифференцируемая
Точность	точно с точностью до округления	останавливается при достижении допуска
Гиперпараметры	нет	шаг $\eta$, число шагов
Чувствительность к масштабу	численная точность ($\kappa^2$, если строится $X^\top X$)	скорость ($\kappa$ шагов); расходится при $\eta > 2/L$

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

• Скорость зависит от числа обусловленности. Плохо масштабированные или коррелированные признаки заставляют спуск ползти; масштабирование исправляет первое, но не второе.
• Шаг нужно выбирать. Слишком малый тратит шаги впустую, больше $2/L$ — расходится; линейный поиск стоит дополнительных вычислений функции потерь.
• Каждый шаг — полный проход по данным. Когда $n$ исчисляется миллионами, один шаг дорог, а бо́льшая часть информации в нём избыточна.
• Невыпуклые функции потерь. Гарантирован только малый градиент; результат зависит от начальной точки.
• Недифференцируемым функциям потерь нужны субградиенты или сглаживание, и постоянные шаги уже не сходятся.

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

• Антиградиент — направление наискорейшего спуска; градиентный спуск повторяет $w \leftarrow w - \eta\nabla Q(w)$. Для метода наименьших квадратов $\nabla Q = \frac2n X^\top(Xw - y)$.
• На квадратичной функции с собственными числами гессиана в $[\mu, L]$: сходится тогда и только тогда, когда $\eta < 2/L$; наилучший постоянный шаг $2/(L + \mu)$ уменьшает ошибку за шаг в $(\kappa - 1)/(\kappa + 1)$ раз; нужно примерно $\frac\kappa2\ln(1/\varepsilon)$ шагов.
• Стандартизуйте признаки перед градиентным спуском: центрирование развязывает свободный член, масштабирование выравнивает кривизны. На данных о вине это снижает $\kappa$ с $1.6 \cdot 10^8$ до 45.
• Для $L$-гладких функций потерь с $\eta = 1/L$: каждый шаг уменьшает $Q$ не меньше чем на $\lVert\nabla Q\rVert^2/(2L)$; избыток потерь равен $O(1/k)$ для выпуклых и $O(e^{-k/\kappa})$ для сильно выпуклых функций; для невыпуклых гарантирован лишь малый градиент.
• Линейный поиск с возвратом находит хороший шаг, не зная $L$.
• Градиентный спуск справляется с функциями потерь без замкнутой формулы, например с функцией Хьюбера, градиент которой — обрезанный остаток.

Код#

Разобранный пример, размеры шага на исходной и стандартизованной задаче, данные о вине, линейный поиск с возвратом и подгонка Хьюбера:

import numpy as np
from sklearn.datasets import load_wine

def gd(grad, w0, eta, steps):
    w = np.array(w0, float)
    for _ in range(steps):
        w = w - eta * grad(w)
    return w

# пример с четырьмя точками: Q(w) = среднеквадратичная ошибка, градиент (2/n) X^T (Xw - y)
x = np.array([0., 1, 2, 3]); y = np.array([1., 3, 2, 5])
for name, col in (('raw', x), ('standardized', (x - x.mean()) / x.std())):
    X = np.column_stack([np.ones(4), col])
    A = 2 / 4 * X.T @ X                                  # гессиан Q
    grad = lambda w: A @ w - 2 / 4 * X.T @ y
    w_hat = np.linalg.solve(X.T @ X, X.T @ y)
    mu, L = np.linalg.eigvalsh(A)
    print(name, A.ravel(), round(mu, 3), round(L, 3), round(L / mu, 2), round(2 / L, 3), round(2 / (L + mu), 3), round((L - mu) / (L + mu), 3))
    for eta in (0.05, 1 / L, 2 / (L + mu), 0.24):
        w, k = np.zeros(2), 0                            # шаги, пока расстояние до w-hat не станет меньше 1/1000 начального
        while np.linalg.norm(w - w_hat) > 1e-3 * np.linalg.norm(w_hat) and k < 1000 and np.linalg.norm(w) < 1e3:
            w, k = w - eta * grad(w), k + 1
        print('  ', round(eta, 3), k if k < 1000 and np.linalg.norm(w) < 1e3 else 'diverges')
# raw [2. 3. 3. 7.] 0.595 8.405 14.13 0.238 0.222 0.868
#    0.05 194 | 0.119 80 | 0.222 49 | 0.24 diverges
# standardized [2. 0. 0. 2.] 2.0 2.0 1.0 1.0 0.5 0.0
#    0.05 66 | 0.5 1 | 0.5 1 | 0.24 11

X = np.column_stack([np.ones(4), x])
w = np.zeros(2)
for k in range(3):                                       # разобранный пример: eta = 0.2 из w = 0
    print(k, w.round(2), (2 / 4 * X.T @ (X @ w - y)).round(2), round(np.mean((X @ w - y) ** 2), 3))
    w = w - 0.2 * 2 / 4 * X.T @ (X @ w - y)
# 0 [0. 0.] [ -5.5 -11. ] 9.75 | 1 [1.1 2.2] [3.3 7.7] 4.91 | 2 [0.44 0.66] [-2.64 -5.06] 2.659

# вино: предсказываем алкоголь по остальным 12 измерениям; исходные признаки против стандартизованных, eta = 1/L
D = load_wine().data; t, F = D[:, 0], D[:, 1:]
for name, M in (('raw', F), ('standardized', (F - F.mean(0)) / F.std(0))):
    Xw = np.column_stack([np.ones(len(t)), M])
    A = 2 / len(t) * Xw.T @ Xw
    ev = np.linalg.eigvalsh(A)
    Q = lambda w: np.mean((Xw @ w - t) ** 2)
    Q_hat, Q_0 = Q(np.linalg.lstsq(Xw, t, rcond=None)[0]), Q(np.zeros(13))
    w, out = np.zeros(13), []
    for k in range(1, 10_001):
        w -= 1 / ev[-1] * 2 / len(t) * Xw.T @ (Xw @ w - t)
        if k in (10, 100, 1000, 10_000): out.append(f'{(Q(w) - Q_hat) / (Q_0 - Q_hat):.0e}')
    print(name, f'{ev[-1] / ev[0]:.2g}', out)
# raw 1.6e+08 ['1e-01', '9e-02', '2e-02', '1e-02']: относительный избыток потерь после 10, 100, 1000, 10000 шагов
# standardized 45 ['8e-03', '2e-08', '7e-19', '7e-19']

# линейный поиск с возвратом (делим eta пополам, пока Q не упадёт хотя бы на eta/2 * |grad|^2) сам находит шаг около 1/L
Xs = np.column_stack([np.ones(len(t)), (F - F.mean(0)) / F.std(0)])
Q = lambda w: np.mean((Xs @ w - t) ** 2); grad = lambda w: 2 / len(t) * Xs.T @ (Xs @ w - t)
w, etas = np.zeros(13), []
for k in range(100):
    g, eta = grad(w), 1.0
    while Q(w - eta * g) > Q(w) - eta / 2 * g @ g:
        eta /= 2
    w, etas = w - eta * g, etas + [eta]
L = np.linalg.eigvalsh(2 / len(t) * Xs.T @ Xs)[-1]
w_fixed = gd(grad, np.zeros(13), 1 / L, 100)
print(round(1 / L, 3), {e: etas.count(e) for e in sorted(set(etas))}, f'{np.linalg.norm(grad(w)):.0e} {np.linalg.norm(grad(w_fixed)):.0e}')
# 0.108 {0.0625: 12, 0.125: 41, 0.25: 9, 0.5: 12, 1.0: 26} 2e-06 1e-03

# у функции потерь Хьюбера из заметки о методе наименьших квадратов нет замкнутой формулы; её градиент — обрезанный остаток
xo = np.arange(10.); yo = np.array([1.3, 1.1, 2.2, 3.0, 2.7, 3.6, 3.5, 4.9, 13.0, 5.3]); Xo = np.column_stack([np.ones(10), xo])
huber_grad = lambda w: -Xo.T @ np.clip(yo - Xo @ w, -1, 1) / 10
L = np.linalg.eigvalsh(Xo.T @ Xo / 10)[-1]
print(gd(huber_grad, [0, 0], 1 / L, 5000).round(3))   # [0.986 0.533]

Дальше#

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

То же обновление обучает модели во всех курсах: курс генеративных моделей подгоняет распределения градиентными шагами по оценке KL, а GAN чередует шаги спуска двух игроков.

Литература#

• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 3: обучение линейной регрессии, градиентный спуск и его сходимость.
• S. Bubeck. Convex optimization: algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4), 2015. Теорема 3.3 (гладкие выпуклые функции), теорема 3.12 (гладкие сильно выпуклые функции).
• S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Раздел 9.2 (методы спуска и линейный поиск с возвратом), раздел 9.3 (градиентный спуск и его сходимость), раздел 9.5 (метод Ньютона).
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. Раздел 4.2 (плохая обусловленность), раздел 4.3 (градиентная оптимизация и гессиан).
• M. P. Deisenroth, A. A. Faisal, C. S. Ong. Mathematics for Machine Learning. Cambridge University Press, 2020. Раздел 7.1 (оптимизация градиентным спуском).