Квазиньютоновские методы ⚖️

В прошлом уроке ты увидел метод Ньютона во всей его мощи: если функция потерь достаточно гладкая, а стартовая точка выбрана разумно, метод Ньютона сходится квадратично — количество верных цифр в ответе удваивается на каждой итерации. Но там же ты упёрся в неприятную стену: чтобы сделать один шаг, нужно вычислить и обратить гессиан — матрицу вторых частных производных размера $n \times n$. Для логистической регрессии со ста признаками это вполне посильно. Для модели с миллионом параметров — уже физически невозможно: матрица $10^6 \times 10^6$ вещественных чисел в двойной точности занимает около восьми терабайт памяти, а её обращение стоит порядка $10^{18}$ операций. Ни один компьютер не обратит такую матрицу за разумное время, сколько бы ядер у него ни было.

Получается развилка. Градиентный спуск из урока 285 использует только первую производную — он дёшев на каждом шаге (нужен всего лишь вектор градиента), но слеп к кривизне поверхности потерь: на вытянутых, плохо обусловленных ландшафтах он петляет тысячами мелких шагов там, где метод Ньютона прыгнул бы к минимуму за одну-две итерации. Метод Ньютона видит кривизну и потому сходится стремительно, но платит за это вычислением и хранением полного гессиана на каждом шаге — а это ровно та цена, которую на практике почти никогда нельзя себе позволить.

Квазиньютоновские методы — это осознанный компромисс между двумя крайностями. Идея обманчиво простая: а что, если не вычислять гессиан точно, а оценивать его приближённо, используя только то, что у нас и так уже есть, — историю значений градиента в нескольких последних точках? Каждый шаг оптимизации даёт нам пару чисел «на сколько сдвинулась точка» и «насколько изменился градиент» — а из отношения этих двух величин, как оказывается, можно восстановить приближённую информацию о кривизне функции почти бесплатно, без единой явно посчитанной второй производной. Это тот же самый трюк, которым в одномерном случае пользуется метод секущих, заменяющий точную производную $f''(x)$ отношением конечных разностей $\bigl(f'(x_{k+1}) - f'(x_k)\bigr)/(x_{k+1}-x_k)$ — только теперь обобщённый на матрицы.

В этом уроке ты разберёшь идею приближённой оценки обратного гессиана через уравнение секущих, изучишь формулу обновления BFGS — самого известного и самого надёжного квазиньютоновского метода, — и его экономную по памяти версию L-BFGS, которая делает квазиньютоновский подход реально применимым в задачах с десятками и сотнями тысяч параметров. В конце ты увидишь честную сравнительную картину всех трёх семейств методов — градиентного спуска, метода Ньютона и L-BFGS — по трём осям сразу: скорости сходимости, стоимости одного шага и требованиям к памяти, а также узнаешь, где именно L-BFGS реально работает в машинном обучении сегодня, а где он бессилен и уступает место SGD и Adam из урока 286.

История

Первым квазиньютоновским методом принято считать работу американского физика Уильяма Дэвидона (William C. Davidon), сотрудника Аргоннской национальной лаборатории. В 1959 году Дэвидон занимался расчётами, связанными с ядерными реакторами, и ему требовалось решать задачи оптимизации с сотнями переменных на компьютерах, чья вычислительная мощность по нынешним меркам была ничтожной. Метод Ньютона был для его задач попросту неподъёмным — а вот идея накапливать информацию о кривизне из истории градиентов сработала. Дэвидон написал технический отчёт с описанием метода, но научный журнал, куда он его отправил, отчёт отклонил как «недостаточно значимый» — и он много лет циркулировал в виде препринта Аргоннской лаборатории, прежде чем был официально опубликован в академическом журнале лишь в 1991 году, спустя более тридцати лет после написания. Тем не менее уже в начале 1960-х годов о методе знали в узких кругах вычислительных математиков.

В 1963 году Роджер Флетчер (Roger Fletcher) и Майкл Пауэлл (Michael J. D. Powell) формализовали и заметно улучшили идею Дэвидона, опубликовав статью с чёткой формулой обновления приближения обратного гессиана. Их вариант метода получил название DFP — по первым буквам фамилий Дэвидона, Флетчера и Пауэлла — и на добрые семь лет стал стандартным квазиньютоновским алгоритмом.

А дальше произошло нечто редкое в истории математики: в 1970 году четыре разных исследователя из разных университетов, не согласовывая свою работу друг с другом, независимо опубликовали статьи с практически идентичной, но заметно более удачной формулой обновления, чем DFP. Это были Чарльз Бройден (Charles George Broyden), тот же Роджер Флетчер, Дональд Голдфарб (Donald Goldfarb) и Дэвид Шанно (David Shanno). Ни один из четверых не претендовал на единоличный приоритет — формулы, полученные ими независимо разными путями (кто-то через анализ симметричных обновлений ранга два, кто-то через двойственность с DFP), оказались математически эквивалентны. Математическое сообщество отреагировало справедливо: метод назвали по первым буквам всех четырёх фамилий — BFGS. Так родился алгоритм, который полвека спустя всё ещё остаётся решателем по умолчанию для логистической регрессии в scikit-learn.

Идея: оцениваем гессиан по истории градиентов, а не вычисляем его

Интуиция

Вернись на секунду к одномерному методу секущих, который ты видел ещё до метода Ньютона: чтобы найти корень уравнения $f'(x) = 0$, а не пользоваться точной второй производной $f''(x)$, метод секущих строит её приближение по двум последним точкам —

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

Квазиньютоновские методы делают ровно тот же трюк, но в $n$-мерном пространстве, где вместо одного числа $f''(x)$ фигурирует целая матрица — гессиан $\nabla^2 f(x)$ размера $n \times n$. На каждом шаге оптимизации у тебя и так появляются две величины практически бесплатно: вектор смещения точки $s_k = x_{k+1} - x_k$ и вектор изменения градиента $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$. Из соотношения между этими двумя векторами можно построить матрицу, которая ведёт себя как гессиан именно вдоль направления последнего шага — и с каждой новой итерацией эта аппроксимация становится точнее сразу по нескольким направлениям.

Формализация: уравнение секущих

Уравнение секущих (secant equation). Пусть $B_{k+1}$ — приближение истинного гессиана $\nabla^2 f(x_{k+1})$ в новой точке. Квазиньютоновские методы требуют, чтобы это приближение было согласовано с уже известным изменением градиента вдоль последнего сделанного шага:

$$B_{k+1}\, s_k = y_k, \qquad s_k = x_{k+1} - x_k, \qquad y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$$

Эквивалентно для приближения обратного гессиана $H_{k+1} = B_{k+1}^{-1}$ (именно его в реализациях и хранят, чтобы не обращать матрицу на каждом шаге):

$$H_{k+1}\, y_k = s_k$$

На практике работают именно со второй формой — приближением обратного гессиана $H_k$, потому что тогда направление следующего шага получается прямым матрично-векторным умножением $d_k = -H_k \nabla f(x_k)$, без решения системы линейных уравнений и без единого обращения матрицы за всю оптимизацию.

Важная деталь, которую стоит проговорить сразу: при $n > 1$ уравнение секущих — это система из $n$ уравнений (по одному на каждую координату вектора $y_k$), а неизвестных в симметричной матрице $B_{k+1}$ размера $n \times n$ — целых $n(n+1)/2$. При $n \ge 2$ неизвестных заведомо больше, чем уравнений, значит, уравнению секущих удовлетворяет не одна, а целое семейство матриц. Именно эта недоопределённость и есть источник разных квазиньютоновских формул: DFP, BFGS и другие методы — это разные, по-своему обоснованные способы выбрать одну конкретную матрицу $B_{k+1}$ (или $H_{k+1}$) из всего этого семейства, обычно ту, что ближе всего к предыдущему приближению $B_k$ в некоторой матричной норме и одновременно остаётся симметричной и положительно определённой.

Примеры

Пример 1: секущее приближение в одномерном случае. Пусть $f(x) = x^2$, точная вторая производная $f''(x) = 2$ везде. Возьмём две точки: $x_0 = 3$, $x_1 = 1$. Тогда $f'(x) = 2x$, значит $f'(x_0) = 6$, $f'(x_1) = 2$. Секущее приближение: $\dfrac{f'(x_1) - f'(x_0)}{x_1 - x_0} = \dfrac{2 - 6}{1 - 3} = \dfrac{-4}{-2} = 2$. Приближение совпало с точным значением $f''(x)=2$ — и это не случайность, а следствие того, что для квадратичной функции вторая производная постоянна, так что любая пара точек восстанавливает её точно с первого раза.

Пример 2: недоопределённость в двух измерениях. Пусть $s_k = (1, 0)^\top$ и $y_k = (2, 3)^\top$. Уравнение секущих $B_{k+1} s_k = y_k$ для симметричной матрицы $B_{k+1} = \begin{pmatrix} a & b \\ b & c\end{pmatrix}$ даёт систему $a = 2$, $b = 3$ — а про $c$ уравнение не говорит вообще ничего, потому что $s_k$ не имеет второй компоненты. Любое значение $c$ формально удовлетворяет уравнению секущих. Это ровно тот случай недоопределённости из формального определения: одного шага $s_k$ недостаточно, чтобы полностью восстановить матрицу $n \times n$ при $n \ge 2$ — нужна информация о поведении градиента вдоль нескольких разных направлений, которая накапливается только за несколько итераций подряд.

Пример 3: почему нужно условие $y_k^\top s_k > 0$. Возьмём $s_k = (1, 0)^\top$ и $y_k = (-1, 0)^\top$ — то есть при движении в направлении $s_k$ проекция градиента на это направление убывает. Тогда $y_k^\top s_k = -1 < 0$. Если попытаться построить симметричную положительно определённую матрицу $H_{k+1}$, для которой $H_{k+1} y_k = s_k$, окажется, что это невозможно: положительно определённая матрица обязана давать $y_k^\top H_{k+1} y_k > 0$ для любого ненулевого $y_k$, а из уравнения секущих $y_k^\top H_{k+1} y_k = y_k^\top s_k$ — если правая часть отрицательна, требование положительной определённости нарушается автоматически. Условие $y_k^\top s_k > 0$ называют условием кривизны (curvature condition) — это не техническая мелочь, а строгое математическое требование, без которого квазиньютоновское приближение попросту не может оставаться корректной моделью выпуклой чаши.

Почему это важно

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

Метод BFGS: формула обновления обратного гессиана

Интуиция

BFGS решает задачу недоопределённости уравнения секущих конкретным, математически обоснованным способом: на каждом шаге он берёт предыдущее приближение $H_k$ и вносит в него минимальное изменение, необходимое для того, чтобы новое приближение $H_{k+1}$ удовлетворяло уравнению секущих, оставалось симметричным и оставалось положительно определённым (при условии, что положительно определённым было предыдущее приближение и выполнено условие кривизны). Формально это формулируется как задача минимизации матричного расстояния между $H_{k+1}$ и $H_k$ в специальной взвешенной норме при ограничении в виде уравнения секущих — но для практики важнее сама итоговая формула и то, что она гарантированно порождает корректную, положительно определённую матрицу на каждом шаге, если условие кривизны выполнено.

Формальное определение

Формула обновления BFGS (для приближения обратного гессиана). Обозначим $\rho_k = \dfrac{1}{y_k^\top s_k}$. Тогда

$$H_{k+1} = \bigl(I - \rho_k\, s_k y_k^\top\bigr)\, H_k\, \bigl(I - \rho_k\, y_k s_k^\top\bigr) + \rho_k\, s_k s_k^\top$$

Шаг оптимизации при этом выглядит так:

$$d_k = -H_k \nabla f(x_k), \qquad x_{k+1} = x_k + \alpha_k d_k$$

где $\alpha_k$ — длина шага, обычно подбираемая линейным поиском (line search), удовлетворяющим условиям Вольфа (Wolfe conditions) — они, среди прочего, гарантируют выполнение условия кривизны $y_k^\top s_k > 0$ для гладких функций.

Обрати внимание на структуру формулы: это не просто прибавление поправки к старой матрице, а сопряжение — старое приближение $H_k$ «зажато» между двумя похожими матрицами $(I - \rho_k s_k y_k^\top)$ и её транспонированной версией, плюс отдельное слагаемое ранга один $\rho_k s_k s_k^\top$. Такая конструкция называется обновлением ранга два (rank-two update) — она изменяет матрицу $H_k$ не в одном, а сразу в двух независимых направлениях за одну итерацию, что и придаёт BFGS его знаменитое «самокорректирующееся» поведение: даже если на каком-то шаге приближение немного «промахнулось» с кривизной, последующие обновления имеют тенденцию сами исправлять накопленную ошибку, а не усиливать её — в отличие от более раннего метода DFP, у которого это свойство выражено слабее.

Примеры

Пример 1: степень квадратичной аппроксимации. Разберём, почему шаг $d_k = -H_k \nabla f(x_k)$ — это ровно то же самое действие, что делает метод Ньютона, только с приближённой матрицей вместо точной. Метод Ньютона строит шаг $d_k = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$ — направление к минимуму квадратичной аппроксимации функции в текущей точке. BFGS заменяет точный обратный гессиан $[\nabla^2 f(x_k)]^{-1}$ на накопленное приближение $H_k$ — и при $H_k = I$ (единичная матрица, стандартный выбор для самой первой итерации, когда истории ещё нет) шаг BFGS в точности совпадает с шагом градиентного спуска. Это красиво иллюстрирует место BFGS в общей картине курса: на первой итерации BFGS — это градиентный спуск, а по мере накопления истории он всё точнее имитирует метод Ньютона.

Пример 2: полный численный расчёт одной итерации. Возьмём квадратичную функцию $f(x, y) = x^2 + 4y^2$ с градиентом $\nabla f(x,y) = (2x,\ 8y)$. Истинный гессиан здесь постоянен: $\nabla^2 f = \begin{pmatrix}2 & 0\\0 & 8\end{pmatrix}$, а истинный обратный гессиан — $\begin{pmatrix}0{,}5 & 0\\0 & 0{,}125\end{pmatrix}$.

Стартуем в точке $x_0 = (2, 2)$ с $H_0 = I$. Градиент в старте: $\nabla f(x_0) = (4, 16)$. Направление первого шага при $H_0=I$ — это направление обычного градиентного спуска: $d_0 = -(4, 16)$. Возьмём шаг $\alpha_0 = 0{,}25$, тогда

Теперь вычислим векторы для обновления:

Проверим условие кривизны: $y_0^\top s_0 = (-2)(-1) + (-32)(-4) = 2 + 128 = 130 > 0$ — условие выполнено, обновление корректно, $\rho_0 = 1/130$.

Подставляя $s_0$, $y_0$, $\rho_0$ и $H_0 = I$ в формулу BFGS и выполняя прямое матричное умножение, получаем новое приближение обратного гессиана:

Присмотрись к элементу в правом нижнем углу: $0{,}1271$ — это уже почти точное совпадение с истинным значением $0{,}125$ из обратного гессиана! Всего за одну итерацию, не вычислив ни единой второй производной аналитически, метод восстановил кривизну вдоль направления $y$ с точностью до второго знака после запятой — именно потому, что первый шаг случайно оказался «богат информацией» именно про это направление. Направление вдоль $x$ пока восстановлено куда грубее ($1{,}0377$ вместо истинных $0{,}5$) — это ожидаемо: уравнение секущих на одном шаге даёт информацию в первую очередь про то направление, куда фактически сдвинулась точка, а дальнейшие итерации постепенно «дотягивают» и остальные направления.

Пример 3: почему шаг становится длиннее сам по себе. Продолжая тот же пример, вычислим направление следующего шага: $d_1 = -H_1 \nabla f(x_1) = -H_1 \cdot (2, -16)$. Подставляя матрицу $H_1$ из предыдущего примера: первая координата $-(1{,}0377 \cdot 2 + (-0{,}0336)\cdot(-16)) = -(2{,}075 + 0{,}538) = -2{,}613$, вторая координата $-((-0{,}0336)\cdot 2 + 0{,}1271\cdot(-16)) = -(-0{,}067 - 2{,}034) = 2{,}101$. Направление $d_1 \approx (-2{,}613,\ 2{,}101)$ уже заметно отличается от направления «чистого» антиградиента $-\nabla f(x_1) = (-2, 16)$ — BFGS начал искажать направление шага в сторону, подсказанную накопленной кривизной, вместо того чтобы слепо идти против градиента. Именно за счёт таких искажений направления шаги BFGS перестают «дрожать» на вытянутых, плохо обусловленных ландшафтах, где градиентный спуск делает тысячи мелких зигзагов.

Почему это важно

Формула BFGS — это не абстрактная алгебра, а конкретный рецепт, который делает возможным обучение моделей, где метод Ньютона в принципе неприменим по памяти, но чистый градиентный спуск сходится неприемлемо медленно. Важное практическое свойство BFGS — доказанная теорема о сходимости за конечное число шагов на строго выпуклых квадратичных функциях (не более $n$ итераций при точном линейном поиске — тот же результат, что и у метода сопряжённых градиентов из следующего урока), и сверхлинейная сходимость вблизи минимума на достаточно гладких невыпуклых функциях — то есть быстрее любой линейной сходимости градиентного спуска, хотя формально и медленнее квадратичной сходимости настоящего метода Ньютона. На практике для функций потерь классического машинного обучения (логистическая регрессия, максимальное правдоподобие в статистических моделях) BFGS обычно требует в разы, а иногда на порядок меньше итераций, чем градиентный спуск, при этом каждая итерация стоит существенно дешевле итерации метода Ньютона.

L-BFGS: как обучаться при сотнях тысяч параметров без гигабайт памяти

Интуиция

У BFGS остаётся одна серьёзная проблема, унаследованная от метода Ньютона лишь частично, но всё ещё болезненная: матрица $H_k$ имеет размер $n \times n$, и её приходится хранить целиком между итерациями. Для $n = 10^5$ параметров (немаленькая, но вполне реалистичная классическая модель) это уже $10^{10}$ чисел — десятки гигабайт памяти под одну-единственную матрицу, которая при этом ещё и обновляется на каждом шаге. Для нейросети с миллиардом параметров такая матрица не поместится ни в какую оперативную память современного сервера.

Limited-memory BFGS (L-BFGS) решает эту проблему радикально просто: он вообще никогда не формирует и не хранит матрицу $H_k$ явно. Вместо этого он хранит только последние $m$ пар векторов $(s_i, y_i)$ — обычно $m$ выбирают между 5 и 20, независимо от того, сколько параметров $n$ в модели, — а нужное произведение $H_k \nabla f(x_k)$ вычисляет «на лету» с помощью специального алгоритма, который называется двухпроходной рекурсией (two-loop recursion). Идея похожа на то, как ты можешь заново развернуть цепочку вложенных скобок, зная только последовательность операций, а не пересчитанный заранее итоговый результат каждой вложенности.

Алгоритм: двухпроходная рекурсия

Двухпроходная рекурсия L-BFGS. Даны последние $m$ пар $(s_i, y_i)$, $i = k-m, \dots, k-1$, текущий градиент $g = \nabla f(x_k)$ и масштабирующий коэффициент $\gamma_k = \dfrac{s_{k-1}^\top y_{k-1}}{y_{k-1}^\top y_{k-1}}$ (эмпирическая оценка масштаба кривизны, заменяющая единичную матрицу $H_k^{(0)} = \gamma_k I$ на старте рекурсии).

q = g
for i = k-1, k-2, ..., k-m:
    ρ_i = 1 / (y_i^T s_i)
    α_i = ρ_i * (s_i^T q)
    q = q - α_i * y_i

r = γ_k * q            # это приближение H_k^(0) * q

for i = k-m, ..., k-2, k-1:
    β = ρ_i * (y_i^T r)
    r = r + s_i * (α_i - β)

# итог: r ≈ H_k * g, а направление шага d_k = -r

Первый цикл идёт «назад» от самой свежей пары к самой старой, второй — «вперёд» обратно к свежей, и на выходе получается ровно то же самое произведение $H_k g$, которое дала бы полная формула BFGS с полной матрицей — но без единого умножения матрицы $n \times n$ на вектор. Каждая итерация цикла — это два скалярных произведения векторов длины $n$, значит, стоимость всей рекурсии — $O(mn)$ операций и $O(mn)$ памяти на хранение пар $(s_i, y_i)$, вместо $O(n^2)$ у полного BFGS.

Примеры

Пример 1: во сколько раз L-BFGS экономнее по памяти. Пусть модель имеет $n = 200\,000$ параметров (реалистичный масштаб для модели структурированного предсказания в обработке текста). Полная матрица $H_k$ потребовала бы $n^2 = 4 \times 10^{10}$ чисел — при 8 байт на число в двойной точности это 320 гигабайт, что уже превышает память практически любой рабочей станции. L-BFGS с $m = 10$ хранит всего $2mn = 4 \times 10^6$ чисел — около 32 мегабайт. Разница в памяти — в десять тысяч раз, и именно она превращает квазиньютоновский подход из теоретической идеи в реально работающий инструмент на моделях такого масштаба.

Пример 2: трасса двухпроходной рекурсии при $m=2$. Пусть хранятся две пары: $(s_1, y_1)$ — самая старая, $(s_2, y_2)$ — самая свежая, и текущий градиент $g$. Первый цикл идёт от свежей к старой: сначала вычисляется $\alpha_2 = \rho_2 (s_2^\top q)$, где $q$ пока равен $g$, затем $q$ обновляется вычитанием $\alpha_2 y_2$; после этого вычисляется $\alpha_1 = \rho_1(s_1^\top q)$ уже с обновлённым $q$, и $q$ снова обновляется вычитанием $\alpha_1 y_1$. После этого $q$ умножается на масштаб $\gamma_k$, получая $r$. Второй цикл идёт в обратном порядке — сначала обрабатывается старая пара: $\beta = \rho_1(y_1^\top r)$, $r \mathrel{+}= s_1(\alpha_1 - \beta)$, затем свежая: $\beta = \rho_2(y_2^\top r)$, $r \mathrel{+}= s_2(\alpha_2 - \beta)$. Итоговый $r$ — это то же самое произведение $H_k g$, которое дала бы полная матричная формула BFGS, если бы её честно применили дважды подряд с этими же двумя парами. Ключевое наблюдение: ни на одном шаге не появилась ни одна матрица размера больше вектора — только скалярные произведения и покомпонентные операции над векторами.

Пример 3: что происходит, когда пар становится больше $m$. Допустим, оптимизация уже сделала 50 итераций, а хранить решили только последние $m = 10$ пар. На 51-й итерации самая старая из хранимых пар (пара номер 41) просто отбрасывается, а её место в буфере занимает свежая пара номер 51 — реализуется как классическая кольцевая очередь фиксированного размера. Информация о кривизне, накопленная очень давно, забывается, и приближение $H_k$ в каждый момент времени отражает «локальную» кривизну функции в окрестности последних $m$ шагов, а не всю историю оптимизации целиком. Это осознанный компромисс: чуть менее точное приближение гессиана ради постоянного, не растущего с числом итераций объёма памяти — и на практике даже $m$ между 5 и 20 обычно достаточно, чтобы получить почти всю практическую выгоду от квазиньютоновского подхода.

Почему это важно

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

Сравнение трёх подходов: скорость, стоимость шага и память

Таблица

Примеры

Пример 1: подсчёт операций для $n = 1\,000$. Градиентный спуск делает шаг за $O(n) = 1\,000$ операций. Метод Ньютона тратит на один шаг порядка $n^3 = 10^9$ операций на обращение гессиана (не считая ещё $O(n^2)$ на вычисление самих вторых производных). L-BFGS с $m=10$ тратит порядка $2mn = 20\,000$ операций на шаг — на пять порядков дешевле метода Ньютона и лишь в 20 раз дороже градиентного спуска, при этом качественно приближаясь к ньютоновской скорости сходимости.

Пример 2: где проходит практическая граница по числу параметров. Логистическая регрессия на 500 признаках — метод Ньютона здесь вполне применим: гессиан $500\times500$ занимает всего пару мегабайт, а его обращение — доли секунды. CRF-модель (условное случайное поле) для разметки текста на 300 000 весов — метод Ньютона здесь уже физически невозможен по памяти, а L-BFGS с $m=10$ работает быстро и устойчиво: пары векторов занимают считаные мегабайты. Нейросеть-трансформер на 7 миллиардов параметров — даже L-BFGS с $m=10$ потребовал бы хранения $2 \times 10 \times 7 \times 10^9 = 1{,}4 \times 10^{11}$ чисел (свыше терабайта), плюс полный градиент по всему датасету на каждом шаге стоил бы неприемлемо дорого — здесь единственный практичный выбор остаётся за стохастическими методами семейства SGD и Adam из урока 286, которые работают на маленьких мини-батчах и вообще не пытаются оценивать кривизну явно.

Пример 3: количество итераций до заданной точности на плохо обусловленной задаче. Рассмотрим квадратичную функцию с числом обусловленности гессиана $\kappa = 10\,000$ (то есть одно направление в 10 000 раз «круче» другого — типичная ситуация для нестандартизированных признаков). Градиентному спуску для такой задачи в худшем случае требуется число итераций порядка $\kappa \cdot \log(1/\varepsilon)$ — то есть тысячи итераций даже для скромной точности $\varepsilon$. Метод Ньютона решил бы точно такую задачу за одну итерацию, потому что квадратичная функция и её ньютоновская аппроксимация совпадают в точности. L-BFGS на той же задаче сходится за число итераций порядка $n$ (при точном линейном поиске — не более $n$ шагов для строго выпуклой квадратичной функции, как у полного BFGS), но что важнее — эмпирически он на порядки менее чувствителен к плохой обусловленности, чем градиентный спуск, поскольку накопленное приближение гессиана как раз и «выправляет» разницу масштабов между направлениями.

Почему это важно

Эта таблица — не абстрактное сравнение ради сравнения, а прямой практический инструмент выбора алгоритма под конкретную задачу. Если у тебя миллиард параметров и стохастический мини-батч — вопрос закрыт в пользу SGD/Adam ещё до того, как ты начал думать о гессиане. Если у тебя десятки или сотни параметров и точное решение критично — метод Ньютона по-прежнему хороший выбор, особенно если задача выпукла и сходимость гарантирована теоремой из урока 278. А если у тебя от нескольких тысяч до нескольких сотен тысяч параметров, датасет помещается в память целиком (не нужен мини-батч) и точность важнее максимальной скорости одной итерации — L-BFGS почти всегда будет самым разумным выбором по умолчанию, что и объясняет, почему именно он стоит решателем lbfgs в sklearn.linear_model.LogisticRegression и активно используется при обучении классических моделей структурированного предсказания в обработке естественного языка, таких как условные случайные поля (CRF) и структурные SVM.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Для точек $x_0 = 3$, $x_1 = 5$ функции $f(x) = x^2$ вычисли $s_0 = x_1 - x_0$ и $y_0 = f'(x_1) - f'(x_0)$.

Задание 2: Используя $s_0$ и $y_0$ из задания 1, проверь условие кривизны $y_0^\top s_0 > 0$ (в одномерном случае это просто произведение $y_0 \cdot s_0$).

Задание 3: Даны $s_k = (2, 1)^\top$, $y_k = (3, 4)^\top$. Вычисли $\rho_k = 1/(y_k^\top s_k)$.

Задание 4: Даны $s_k = (1, -2)^\top$, $y_k = (-1, 3)^\top$. Проверь условие кривизны и объясни, можно ли использовать эту пару для обновления BFGS.

Задание 5: При $H_k = I$ (единичная матрица) чему равно направление шага $d_k = -H_k \nabla f(x_k)$? На какой алгоритм это похоже?

Задание 6: Сколько независимых неизвестных чисел содержит симметричная матрица размера $n \times n$? Сравни это число с количеством уравнений в уравнении секущих $B_{k+1}s_k = y_k$ при $n = 4$.

Задание 7: Функция $f(x,y) = x^2 + 4y^2$ имеет постоянный гессиан $\begin{pmatrix}2&0\\0&8\end{pmatrix}$. Найди истинный обратный гессиан.

Задание 8: Для $n = 50\,000$ параметров вычисли количество чисел (не байты) в полном гессиане $n \times n$.

Задание 9: Для тех же $n = 50\,000$ и L-BFGS с $m = 10$ вычисли количество чисел, которые реально хранятся (пары $s_i, y_i$, каждая длины $n$).

Задание 10: Объясни своими словами, какую информацию использует градиентный спуск, какую — метод Ньютона, а какую — квазиньютоновский метод.

Продвинутые задания (11–20)

Задание 11: Формула обновления BFGS называется обновлением «ранга два». Объясни, почему в выражении $H_{k+1} = (I - \rho_k s_k y_k^\top) H_k (I - \rho_k y_k s_k^\top) + \rho_k s_k s_k^\top$ фигурирует именно это название.

Задание 12: Метод DFP (Дэвидон — Флетчер — Пауэлл) появился раньше BFGS, но на практике почти повсеместно вытеснен именно BFGS. Почему?

Задание 13: В разобранном в уроке примере получена матрица $H_1 = \begin{pmatrix}1{,}0377 & -0{,}0336\\-0{,}0336 & 0{,}1271\end{pmatrix}$. Проверь, что она симметрична.

Задание 14: Проверь положительную определённость матрицы $H_1$ из задания 13 через критерий угловых миноров (главных миноров).

Задание 15: Объясни, почему линейный поиск, удовлетворяющий условиям Вольфа (Wolfe conditions), автоматически гарантирует выполнение условия кривизны $y_k^\top s_k > 0$ для гладких функций.

Задание 16: Известно, что BFGS с точным линейным поиском сходится на строго выпуклой квадратичной функции от $n$ переменных не более чем за $n$ итераций. Объясни интуитивно, почему это разумно ожидать.

Задание 17: Дан буфер L-BFGS из двух пар $(s_1,y_1)$ и $(s_2,y_2)$ (где индекс 2 — самая свежая) и текущий градиент $g$. Распиши по шагам порядок вычислений двухпроходной рекурсии (без конкретных чисел, только последовательность операций).

Задание 18: Для $n = 100\,000$ параметров сравни порядок числа операций на одну итерацию метода Ньютона (обращение гессиана, $O(n^3)$) и L-BFGS с $m=10$ ($O(mn)$).

Задание 19: Объясни смысл масштабирующего коэффициента $\gamma_k = \dfrac{s_{k-1}^\top y_{k-1}}{y_{k-1}^\top y_{k-1}}$, который используют вместо единичной матрицы $H_k^{(0)} = I$ на старте двухпроходной рекурсии.

Задание 20: Логистическая регрессия обучается на 40 признаках. Обосновано ли применять здесь L-BFGS, если полный метод Ньютона тоже прекрасно справится по объёму вычислений?

Задания-челленджи (21–30)

Задание 21: Перечисли не менее двух конкретных причин, по которым L-BFGS практически не применяется для обучения нейросетей с миллионами или миллиардами параметров.

Задание 22: В примере урока после одной итерации BFGS получена матрица $H_1$, а направление следующего шага — $d_1 \approx (-2{,}613,\ 2{,}101)$. Какие векторы понадобятся, чтобы вычислить следующее обновление $H_2$?

Задание 23: Что происходит на практике в реализациях BFGS/L-BFGS, если на очередном шаге условие кривизны $y_k^\top s_k > 0$ нарушается (например, из-за невыпуклости функции потерь)?

Задание 24: Модель условного случайного поля (CRF) для разметки последовательностей в NLP имеет 500 000 весов, а обучающий датасет целиком помещается в память. Обоснуй, применим ли здесь L-BFGS.

Задание 25: На сильно плохо обусловленной задаче (число обусловленности гессиана $\kappa = 10^5$) сравни качественно, как ведут себя число итераций у градиентного спуска и у L-BFGS.

Задание 26: Объясни своими словами «самокорректирующееся» свойство BFGS, о котором говорилось в уроке, и почему оно важно при неидеальном линейном поиске.

Задание 27: Для $n = 10^7$ параметров вычисли объём памяти (в числах) для L-BFGS с $m=1000$ и с $m=10$, и объясни, почему на практике выбирают именно малые значения $m$.

Задание 28: Следующий урок курса посвящён методу сопряжённых градиентов — ещё одному способу ускорить сходимость без хранения полного гессиана. Чем метод сопряжённых градиентов концептуально похож на L-BFGS, а чем принципиально отличается по объёму хранимой информации?

Задание 29: В scikit-learn вызов LogisticRegression(solver='lbfgs') обучает модель, минимизируя функцию потерь. Опираясь на материал урока 278, объясни, почему для этой конкретной задачи L-BFGS особенно надёжен.

Задание 30: Обобщи: пройденное семейство методов первого и второго порядка — градиентный спуск (285), стохастический градиентный спуск (286), метод Ньютона (287), квазиньютоновские методы (288). Опиши в двух-трёх предложениях, какую информацию использует каждый метод и какой ценой это достигается.

Частые ошибки

Ошибка 1. Считают, что квазиньютоновские методы вычисляют настоящий гессиан, просто «более эффективным» способом.

Как выглядит: «BFGS — это быстрый способ посчитать вторые производные».

Почему возникает: название «квазиньютоновский» ассоциируется с методом Ньютона и его точным гессианом, и кажется, что речь идёт лишь об ускорении того же самого вычисления.

Как правильно: BFGS и L-BFGS никогда не вычисляют вторые производные — они строят приближение обратного гессиана исключительно из значений первой производной (градиента) в нескольких последних точках, используя уравнение секущих.

Ошибка 2. Путают BFGS и L-BFGS, считая их одним и тем же алгоритмом с разным названием.

Как выглядит: «раз это квазиньютоновский метод, значит, он всегда хранит и обновляет матрицу $n \times n$».

Почему возникает: L-BFGS математически даёт то же самое произведение $H_k g$, что и полный BFGS, а различие спрятано в реализации, а не в формуле обновления как таковой.

Как правильно: полный BFGS явно хранит и обновляет матрицу $n \times n$ ($O(n^2)$ памяти), тогда как L-BFGS вообще не формирует эту матрицу, а восстанавливает нужное произведение через двухпроходную рекурсию по последним $m$ парам векторов ($O(mn)$ памяти) — это принципиально разные по требованиям к памяти реализации одной и той же математической идеи.

Ошибка 3. Игнорируют условие кривизны $y_k^\top s_k > 0$ и пытаются применить BFGS к произвольной, в том числе невыпуклой, функции без проверки.

Как выглядит: прямое применение формулы обновления без проверки знака $y_k^\top s_k$ на каждом шаге.

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

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

Ошибка 4. Считают, что раз L-BFGS сходится быстрее градиентного спуска, его нужно применять всегда, включая обучение больших нейросетей.

Как выглядит: «зачем нам SGD и Adam, если L-BFGS сходится за меньшее число итераций».

Почему возникает: сравнение по числу итераций до заданной точности без учёта того, что квазиньютоновским методам нужен согласованный, обычно полный градиент на каждом шаге, а не дешёвый шум мини-батча.

Как правильно: при миллионах и миллиардах параметров и огромных датасетах стоимость вычисления полного градиента и требования к согласованности градиентов между итерациями делают L-BFGS практически неприменимым — здесь безоговорочно доминируют стохастические методы первого порядка из урока 286.

Ошибка 5. Путают понятие «ранг обновления» с размером самой матрицы.

Как выглядит: «обновление ранга два — значит, меняются только два числа в матрице».

Почему возникает: слово «два» в названии интуитивно связывают с количеством изменённых элементов, а не с рангом матричной поправки.

Как правильно: «ранг два» означает, что поправочная матрица к $H_k$ представима как сумма не более чем двух матриц ранга один — но при этом изменяются, вообще говоря, все $n(n+1)/2$ элементов симметричной матрицы, просто вся эта поправка имеет специальную низкоранговую структуру, которая и позволяет обновлять её экономно.

Ошибка 6. Считают, что при увеличении параметра памяти $m$ в L-BFGS сходимость всегда становится заметно быстрее.

Как выглядит: «поставим $m=200$ вместо $m=10$, чтобы алгоритм сходился быстрее».

Почему возникает: интуитивно кажется, что больше сохранённой истории — это всегда строго лучшее приближение гессиана.

Как правильно: эмпирически прирост скорости сходимости от увеличения $m$ свыше 10–20 обычно незначителен, при этом стоимость каждой итерации и требования к памяти растут линейно по $m$ — типичный практический выбор $m$ между 5 и 20 обычно даёт почти весь достижимый выигрыш ценой минимальных дополнительных затрат.

Главное запомнить

• Квазиньютоновские методы — компромисс между градиентным спуском (только градиент, дёшево, но медленно на плохо обусловленных задачах) и методом Ньютона (точный гессиан, быстро, но неподъёмно дорого по памяти и вычислениям для больших моделей).

• Идея — приближённо оценивать обратный гессиан по уравнению секущих $H_{k+1} y_k = s_k$, используя только историю уже вычисленных градиентов в нескольких последних точках, не вычисляя вторые производные напрямую.

• Уравнение секущих при $n \ge 2$ недоопределено (уравнений меньше, чем неизвестных в симметричной матрице), поэтому разные методы (DFP, BFGS) — это разные обоснованные способы выбрать одну конкретную матрицу из целого допустимого семейства.

• BFGS обновляет приближение обратного гессиана формулой ранга два $H_{k+1} = (I-\rho_k s_k y_k^\top)H_k(I-\rho_k y_k s_k^\top) + \rho_k s_k s_k^\top$ и обладает «самокорректирующимся» поведением, за что вытеснил более ранний метод DFP.

• Условие кривизны $y_k^\top s_k > 0$ обязательно для корректности обновления BFGS — оно гарантирует, что приближение $H_k$ остаётся положительно определённым, а направление шага остаётся направлением убывания функции.

• L-BFGS никогда не формирует полную матрицу $H_k$: вместо этого он хранит последние $m$ пар векторов $(s_i, y_i)$ ($m$ обычно между 5 и 20) и вычисляет произведение $H_k \nabla f(x_k)$ через двухпроходную рекурсию за $O(mn)$ операций и $O(mn)$ памяти — вместо $O(n^2)$ у полного BFGS.

• Метод Ньютона сходится квадратично, но стоит $O(n^3)$ на шаг и $O(n^2)$ по памяти; градиентный спуск стоит $O(n)$ на шаг, но сходится линейно; L-BFGS стоит $O(mn)$ на шаг и по памяти, сходясь сверхлинейно — практически лучший компромисс для моделей среднего масштаба.

• L-BFGS — решатель по умолчанию во многих реализациях логистической регрессии (solver='lbfgs' в scikit-learn) и стандартный выбор при обучении классических моделей структурированного предсказания вроде условных случайных полей (CRF) в обработке естественного языка.

• Для нейросетей с миллионами и миллиардами параметров L-BFGS практически не применяется: стохастические мини-батчи разрушают согласованность истории градиентов, необходимую для корректного накопления кривизны, — там доминируют варианты SGD/Adam из урока 286.

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

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на прошлый урок 287 про метод Ньютона: без понимания того, что такое гессиан, зачем нужна его обратная матрица в формуле шага $x_{k+1} = x_k - H^{-1}\nabla f(x_k)$ и почему её вычисление стоит $O(n^3)$, мотивация квазиньютоновского подхода — «оценить $H^{-1}$ приближённо вместо того, чтобы вычислять её точно» — повисает в воздухе. Также пригодился урок 278 про выпуклые функции: положительная определённость гессиана как критерий выпуклости — это та же самая математическая конструкция, что и требование положительной определённости приближения $H_k$ в BFGS, только применённая не к истинному гессиану, а к его квазиньютоновской оценке.

Что изучить дальше

Следующий урок 289 разбирает метод сопряжённых градиентов — ещё один способ ускорить сходимость без хранения полного гессиана, исторически даже более старый, чем BFGS, и в определённом смысле более экономный по памяти (хранит информацию только про одно предыдущее направление вместо $m$ пар векторов). Ты увидишь, что метод сопряжённых градиентов и L-BFGS решают одну и ту же практическую проблему двумя разными путями, и сравнишь их напрямую.

Где это нужно в жизни

🤖 Классическое машинное обучение. Решатель lbfgs — вариант по умолчанию для LogisticRegression в scikit-learn, а также один из стандартных решателей для MLPClassifier (небольшие полносвязные сети) и обобщённых линейных моделей в статистических пакетах — именно потому, что для выпуклых или умеренно невыпуклых задач среднего масштаба он даёт надёжную сходимость почти без ручной настройки скорости обучения.

📝 Обработка естественного языка. Классические модели структурированного предсказания — условные случайные поля (CRF) для разметки именованных сущностей или частей речи, структурные SVM — исторически обучались именно через L-BFGS: параметров достаточно много для метода Ньютона, но датасет умещается в памяти целиком, что и есть идеальные условия для квазиньютоновского подхода.

📊 Статистика и эконометрика. Оценка параметров методом максимального правдоподобия в обобщённых линейных моделях (GLM), логистических и пуассоновских регрессиях в статистических пакетах (R, statsmodels) регулярно использует BFGS или L-BFGS как решатель по умолчанию для задач с умеренным числом параметров.

🧠 Граница применимости в глубоком обучении. Понимание того, почему L-BFGS не используется для обучения больших нейросетей — несогласованность градиентов между мини-батчами, дороговизна полного градиента, дополнительные вычисления линейного поиска — объясняет, почему индустрия глубокого обучения выбрала совершенно другую ветвь методов первого порядка (SGD, Momentum, Adam) вместо того, чтобы просто масштабировать квазиньютоновский подход.

Интересные факты

• Первый квазиньютоновский метод придумал не профессиональный математик-оптимизатор, а физик-ядерщик Уильям Дэвидон в 1959 году, решая практические задачи расчёта ядерных реакторов в Аргоннской национальной лаборатории на слабых по нынешним меркам компьютерах — а его технический отчёт с описанием метода был отклонён научным журналом и официально опубликован лишь в 1991 году, более чем через тридцать лет после написания.

• Формула BFGS появилась в 1970 году сразу в четырёх независимых статьях — Чарльза Бройдена, Роджера Флетчера, Дональда Голдфарба и Дэвида Шанно, — авторы которых работали в разных университетах и не координировали исследования друг с другом. Их формулы, полученные разными математическими путями, оказались эквивалентны, и сообщество увековечило это редкое совпадение, включив в название метода первые буквы фамилий всех четверых, вместо того чтобы отдать приоритет кому-то одному.

• L-BFGS как отдельный алгоритм с ограниченной памятью представил Хорхе Ноцедаль (Jorge Nocedal) в 1980 году, а наиболее цитируемый и практически важный вариант метода описали Дон Лю и тот же Ноцедаль в статье 1989 года «On the Limited Memory BFGS Method for Large Scale Optimization» — именно она и легла в основу решателя lbfgs, который сегодня встроен в scikit-learn, SciPy и десятки других вычислительных библиотек.

• Несмотря на десятилетия развития методов оптимизации, BFGS полвека спустя после публикации остаётся решателем по умолчанию для логистической регрессии в одной из самых массово используемых библиотек машинного обучения в мире — редкий пример алгоритма 1970 года, который не устарел, а стал практическим индустриальным стандартом.

Лайфхаки

• Если функция потерь дифференцируема, но её явную вторую производную вычислять неудобно или дорого (сложная композиция слоёв, автоматическое дифференцирование не поддерживает вторые производные для какого-то узла графа), в первую очередь попробуй L-BFGS вместо ручной реализации метода Ньютона — во многих научных библиотеках (scipy.optimize.minimize(method='L-BFGS-B')) это буквально смена одного аргумента.

• Перед тем как выбирать между методом Ньютона и L-BFGS, оцени, помещается ли гессиан $n \times n$ в память: если $n^2 \cdot 8$ байт превышает разумный объём оперативной памяти твоей машины (условно говоря, уже при $n$ порядка нескольких тысяч), даже не пытайся считать точный гессиан — сразу переходи к L-BFGS.

• Значение $m$ (глубина памяти L-BFGS) в большинстве задач можно смело оставлять на значении по умолчанию у библиотеки (обычно 10) — увеличение до сотен почти никогда не окупается по времени работы, а вот попробовать снизить $m$ до 3–5 при экстремально большом $n$ иногда даёт полезный запас по памяти почти без потери в скорости сходимости.

• Если оптимизация L-BFGS «застревает» и линейный поиск начинает делать подозрительно много попыток на одном шаге, в первую очередь проверь, не связано ли это с нарушением условия кривизны $y_k^\top s_k \le 0$ — это частый симптом того, что функция потерь в этой области невыпукла или что данные плохо отмасштабированы.

• Перед обучением через L-BFGS стандартизируй признаки (приведи к нулевому среднему и единичной дисперсии) так же, как перед градиентным спуском: хотя квазиньютоновские методы заметно менее чувствительны к плохой обусловленности, чем обычный градиентный спуск, они всё равно сходятся быстрее и устойчивее на хорошо отмасштабированных данных.

• Если задача сравнительно небольшая (до нескольких тысяч параметров) и данные помещаются в память целиком, начинай эксперименты именно с L-BFGS, а не с ручной настройки learning rate и батчей для SGD/Adam — для таких масштабов L-BFGS практически всегда либо не хуже, либо заметно лучше по числу итераций и требует на порядок меньше настройки гиперпараметров.

Четыре урока назад ты начинал с самой простой идеи оптимизации — спускаться против градиента, шаг за шагом, вслепую доверяя только направлению самого крутого убывания. Потом эта идея научилась работать на миллиардах примеров через стохастичность мини-батчей. Затем ты увидел, что происходит, когда оптимизации даётся зрение — кривизна поверхности потерь в виде точного гессиана, — и насколько стремительнее становится сходимость, если эта цена по карману. А сегодня ты увидел третий, самый изящный путь: не вычислять кривизну точно и не игнорировать её полностью, а научиться восстанавливать её приближённо из истории собственных же шагов, почти бесплатно. Это красивая иллюстрация более общего принципа, который ты ещё не раз встретишь за пределами оптимизации, — зачастую самое практичное решение лежит не на одном из двух полюсов компромисса, а в осознанном, математически обоснованном компромиссе между ними. Ты прошёл путь от «дёшево и медленно» через «дорого и быстро» до «почти дёшево и почти быстро» — и теперь, столкнувшись с любой новой задачей оптимизации, сможешь осознанно спросить себя не «какой метод самый лучший», а «сколько информации о кривизне я готов оценивать ради ускорения, и какую цену за это разумно заплатить именно в этой задаче».