Метод сопряжённых градиентов 🧭

В уроке 285 ты уже видел эту картину своими глазами: на вытянутой, плохо обусловленной поверхности потерь — узком овраге, где один параметр «крутой», а другой «пологий», — градиентный спуск начинает петлять. Он не идёт прямо ко дну оврага, а мечется от одного склона к другому мелкими перпендикулярными зигзагами, тратя сотни и тысячи итераций там, где по прямой можно было бы дойти буквально за пару шагов. Метод Ньютона из урока 287 эту проблему решает полностью — но ценой вычисления и обращения полного гессиана, которая на больших моделях становится неподъёмной. Квазиньютоновские методы из урока 288 находят компромисс, приближая гессиан по истории градиентов, но всё равно вынуждены хранить матрицу (пусть и в сжатом виде) размера, растущего вместе с числом параметров.

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

Оказывается, что для квадратичных функций такой набор направлений действительно существует, и он вычисляется на удивление дёшево — без хранения матрицы, без решения систем линейных уравнений, буквально по двум векторам и паре скалярных произведений на каждом шаге. Более того, для квадратичной функции от $n$ переменных таких «непортящих» направлений ровно $n$ штук, и, пройдя по всем им по очереди, метод гарантированно останавливается точно в минимуме — не «примерно», не «асимптотически», а точно, за конечное и заранее известное число шагов.

В этом уроке ты разберёшь, откуда берётся эта идея сопряжённых направлений и почему она устраняет зигзаги, изучишь классические формулы выбора направления — Флетчера-Ривса и Полака-Рибьера, — увидишь на полной численной трассировке, как метод сопряжённых градиентов находит точный минимум двумерной квадратичной функции ровно за два шага там, где градиентный спуск зигзагом тащится к цели, и узнаешь, где нелинейное обобщение метода реально работает на практике: внутри truncated Newton методов и при решении огромных разреженных линейных систем, где даже L-BFGS оказывается слишком прожорливым по памяти.

История

Метод сопряжённых градиентов был опубликован в 1952 году американским математиком Магнусом Хестенсом (Magnus R. Hestenes) и швейцарским математиком Эдуардом Штифелем (Eduard Stiefel) в совместной статье в журнале Journal of Research of the National Bureau of Standards. Примечательно, что оба пришли к практически идентичной идее независимо друг от друга — Хестенс работал над ней в Национальном бюро стандартов США, Штифель в это же время занимался похожей задачей в Швейцарском федеральном технологическом институте (ETH Цюрих), — и, узнав о работах друг друга, они объединили усилия в одну публикацию вместо того, чтобы соперничать за приоритет.

Важная деталь, которая часто ускользает: метод изначально создавался вовсе не как алгоритм оптимизации в современном понимании, а как точный прямой метод решения систем линейных уравнений $Ax = b$ с симметричной положительно определённой матрицей $A$ — то есть как альтернатива методу Гаусса. Идея была в том, что если правильно выбирать направления движения, минимизируя квадратичную функцию $f(x) = \frac12 x^\top A x - b^\top x$ (чей минимум и есть решение системы $Ax=b$), то в точной арифметике решение находится ровно за $n$ шагов, где $n$ — размерность системы, — то есть за конечное, заранее известное число операций, как у метода Гаусса, но заметно дешевле для разреженных матриц. Работы Хестенса и Штифеля выполнялись на одной из первых полноценных электронных вычислительных машин — SWAC (National Bureau of Standards Western Automatic Computer) — и метод сразу показал практическую пользу для задач, где матрица $A$ была разреженной (большинство элементов равны нулю), потому что каждая итерация требовала лишь умножения матрицы на вектор, а не её полного разложения.

Настоящий расцвет метода как итерационного алгоритма, а не точного за конечное число шагов, начался позже, в 1960–1970-е годы, когда стало ясно, что при работе с плавающей точкой (а не в идеальной точной арифметике) накопление ошибок округления постепенно разрушает теоретическую гарантию сходимости за ровно $n$ шагов — зато на практике метод сопряжённых градиентов, остановленный гораздо раньше, чем через $n$ итераций, уже даёт достаточно точное приближённое решение для огромных разреженных систем, где $n$ исчисляется миллионами, а прямые методы попросту неприменимы. Обобщение метода на произвольные, не обязательно квадратичные функции — то, что сегодня называют нелинейным методом сопряжённых градиентов, — предложили в 1964 году Роджер Флетчер (тот же исследователь, что стоит за BFGS из предыдущего урока) и Карл Ривз (Ryner Reeves), а в 1969 году французские математики Элайджа Полак (Elijah Polak) и Жерар Рибьер (Gérard Ribière) предложили альтернативную формулу выбора коэффициента направления, которая на практике оказалась заметно устойчивее на невыпуклых и сильно нелинейных функциях.

Проблема зигзагов и идея сопряжённых направлений

Интуиция

Вернись к картине из урока 285: на вытянутой овражной поверхности градиентный спуск с оптимально подобранной на каждом шаге длиной шага (точный линейный поиск, exact line search) движется зигзагом, а не по прямой ко дну оврага. Причина этого зигзага строгая и объяснимая: при точном линейном поиске направление следующего шага всегда оказывается перпендикулярным направлению предыдущего шага в обычном евклидовом смысле. Если предыдущий шаг был «слишком крутым» относительно узкого оврага, следующий шаг, будучи перпендикулярным ему, неизбежно снова «перелетает» через дно оврага на другую сторону — и так по кругу, пока шаги не станут исчезающе малыми.

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

Формализация

A-сопряжённость (A-ортогональность). Пусть $A$ — симметричная положительно определённая матрица размера $n \times n$ (в частности, гессиан квадратичной функции). Два ненулевых вектора $d_i$ и $d_j$ называются сопряжёнными относительно $A$, если

$$d_i^\top A\, d_j = 0, \qquad i \neq j$$

Набор ненулевых векторов $d_0, d_1, \dots, d_{n-1}$, попарно сопряжённых относительно $A$, называется системой A-сопряжённых направлений. При $A = I$ (единичная матрица) сопряжённость в точности совпадает с обычной евклидовой ортогональностью — это частный случай.

Ключевое свойство, ради которого всё это затевается: если минимизировать квадратичную функцию $f(x) = \frac12 x^\top A x - b^\top x$ последовательно вдоль системы $A$-сопряжённых направлений (на каждом шаге выбирая оптимальную длину шага вдоль текущего направления), то минимизация по одному направлению не портит уже найденный минимум по всем предыдущим направлениям. Формально это означает, что задача распадается на $n$ независимых одномерных подзадач — ровно поэтому после прохода по всем $n$ направлениям алгоритм гарантированно оказывается в точном минимуме.

Примеры

Пример 1: сопряжённость как обобщение ортогональности. Возьмём $A = I$ (единичная матрица $2\times2$) и векторы $d_0 = (1, 0)^\top$, $d_1 = (0, 1)^\top$. Проверим сопряжённость: $d_0^\top A d_1 = d_0^\top d_1 = 1\cdot0 + 0\cdot1 = 0$. Условие выполнено — и это ровно обычная евклидова ортогональность, потому что при $A=I$ формула $d_i^\top A d_j$ вырождается в обычное скалярное произведение $d_i^\top d_j$. Это подтверждает, что $A$-сопряжённость — не какая-то экзотическая новая конструкция, а прямое обобщение знакомой ортогональности на случай, когда «правильная» метрика пространства задаётся не единичной, а произвольной положительно определённой матрицей.

Пример 2: сопряжённые, но не ортогональные векторы. Возьмём $A = \begin{pmatrix}2 & 0\\0 & 10\end{pmatrix}$ и вектор $d_0 = (1,1)^\top$. Найдём вектор $d_1 = (x,y)^\top$, сопряжённый с $d_0$ относительно этой матрицы: $d_0^\top A d_1 = 2x + 10y = 0 \Rightarrow y = -x/5$. Возьмём $x=5$, тогда $y=-1$, то есть $d_1 = (5,-1)^\top$. Проверим обычную ортогональность: $d_0 \cdot d_1 = 1\cdot5 + 1\cdot(-1) = 4 \neq 0$ — в привычном евклидовом смысле эти векторы вовсе не перпендикулярны! Но $A$-сопряжённость выполнена точно: $d_0^\top A d_1 = 2\cdot1\cdot5 + 10\cdot1\cdot(-1) = 10-10=0$. Этот пример наглядно показывает главную мысль раздела: сопряжённость — это не то же самое, что перпендикулярность на глаз, а перпендикулярность в метрике, которая «растягивает» пространство пропорционально кривизне функции по каждой оси.

Пример 3: почему градиентный спуск с точным линейным поиском зигзагует — численная проверка ортогональности последовательных градиентов. Возьмём функцию $f(x,y) = x^2 + 10y^2$ (гессиан $A = \begin{pmatrix}2&0\\0&20\end{pmatrix}$, число обусловленности $10$ — типичный узкий овраг) и стартуем из $x_0 = (10, 1)$. Градиент: $\nabla f(x,y) = (2x, 20y)$, значит $g_0 = \nabla f(x_0) = (20, 20)$. При точном линейном поиске оптимальная длина шага для квадратичной функции — $\alpha_0 = \dfrac{g_0^\top g_0}{g_0^\top A g_0} = \dfrac{800}{20\cdot40+20\cdot400} = \dfrac{800}{8800} = \dfrac{1}{11}$.

Тогда $x_1 = x_0 - \alpha_0 g_0 = (10,1) - \frac1{11}(20,20) = \left(\frac{90}{11}, -\frac{9}{11}\right) \approx (8{,}1818,\ -0{,}8182)$, а новый градиент $g_1 = \nabla f(x_1) = \left(\frac{180}{11}, -\frac{180}{11}\right) \approx (16{,}3636,\ -16{,}3636)$.

Проверим обычное скалярное произведение $g_0^\top g_1 = 20\cdot\frac{180}{11} + 20\cdot\left(-\frac{180}{11}\right) = \frac{3600}{11} - \frac{3600}{11} = 0$. Последовательные градиенты оказались строго перпендикулярны друг другу! Это не случайность конкретных чисел, а общее свойство точного линейного поиска на квадратичной функции: каждый следующий шаг «сбрасывает» составляющую градиента вдоль предыдущего направления в ноль, но при этом, будучи перпендикулярным именно в евклидовой, а не в $A$-метрике, снова «перелетает» через узкий овраг на другую сторону — и в этом и есть механическая причина зигзага, который ты наблюдал на графиках в уроке 285.

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

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

Формулы выбора направления: Флетчер-Ривз и Полак-Рибьер

Интуиция

Построить полную систему из $n$ сопряжённых направлений «в лоб» можно было бы, например, процессом Грама-Шмидта, ортогонализуя произвольный набор из $n$ векторов относительно матрицы $A$, — но это потребовало бы хранить и обновлять все ранее построенные направления, что стоит $O(n^2)$ памяти и операций, ровно ту же цену, от которой мы пытались уйти в предыдущем уроке. Настоящее чудо метода сопряжённых градиентов в том, что для квадратичных функций этого не нужно: следующее сопряжённое направление можно построить по совсем короткой формуле, используя только текущий антиградиент и одно-единственное предыдущее направление, а не всю их историю. Это называется двучленной рекуррентностью (two-term recurrence), и именно она делает метод настолько дешёвым по памяти — $O(n)$, столько же, сколько нужно обычному градиентному спуску.

Формализация

Направление в методе сопряжённых градиентов. Обозначим $g_k = \nabla f(x_k)$. Направление шага строится по формуле

$$d_k = -g_k + \beta_k\, d_{k-1}, \qquad d_0 = -g_0$$

Классические формулы коэффициента $\beta_k$:

Флетчер-Ривз (Fletcher–Reeves, 1964):

$$\beta_k^{FR} = \frac{g_k^\top g_k}{g_{k-1}^\top g_{k-1}}$$

Полак-Рибьер (Polak–Ribière, 1969):

$$\beta_k^{PR} = \frac{g_k^\top (g_k - g_{k-1})}{g_{k-1}^\top g_{k-1}}$$

На практике часто используют модификацию $\beta_k^{PR+} = \max\bigl(0,\ \beta_k^{PR}\bigr)$, гарантирующую, что направление $d_k$ остаётся направлением убывания даже тогда, когда «чистый» Полак-Рибьер выдал бы отрицательное значение.

Для строго квадратичной функции при точном линейном поиске обе формулы дают в точности одинаковый результат — это прямое следствие ортогональности последовательных градиентов, которую ты только что проверил численно ($g_k^\top g_{k-1} = 0$, а значит, $g_k^\top(g_k-g_{k-1}) = g_k^\top g_k$, и формулы Флетчера-Ривза и Полака-Рибьера совпадают). Расхождение между ними проявляется только на нелинейных, невыпуклых функциях, где линейный поиск неточен, а гессиан по факту меняется от точки к точке.

Примеры

Пример 1: подтверждение эквивалентности формул на квадратичном примере. Продолжим трассировку из предыдущего раздела: $g_0 = (20,20)$, $g_1 = \left(\frac{180}{11}, -\frac{180}{11}\right)$. Вычислим $\beta_0^{FR} = \dfrac{g_1^\top g_1}{g_0^\top g_0}$. Числитель: $g_1^\top g_1 = 2\cdot\left(\frac{180}{11}\right)^2 = \frac{64800}{121} \approx 535{,}54$. Знаменатель: $g_0^\top g_0 = 800$. Итого $\beta_0^{FR} = \dfrac{64800/121}{800} = \dfrac{81}{121} \approx 0{,}6694$.

Теперь $\beta_0^{PR} = \dfrac{g_1^\top(g_1-g_0)}{g_0^\top g_0}$. Поскольку мы уже проверили $g_1^\top g_0 = 0$, числитель $g_1^\top(g_1-g_0) = g_1^\top g_1 - g_1^\top g_0 = g_1^\top g_1 - 0 = \frac{64800}{121}$ — в точности то же самое значение, что и у Флетчера-Ривза. Значит, $\beta_0^{PR} = \beta_0^{FR} = \frac{81}{121} \approx 0{,}6694$. Формулы совпали, как и обещано теорией для квадратичного случая.

Пример 2: расхождение формул на нелинейном шаге. Представим, что на некотором шаге нелинейной оптимизации (где линейный поиск неточен) получены градиенты $g_{k-1} = (1, 2)$ и $g_k = (1{,}1,\ 1{,}8)$ — направление почти не изменилось, но не в точности повторило квадратичный сценарий. Тогда $g_{k-1}^\top g_{k-1} = 1+4=5$. Флетчер-Ривз: $\beta_k^{FR} = \dfrac{1{,}1^2+1{,}8^2}{5} = \dfrac{1{,}21+3{,}24}{5} = \dfrac{4{,}45}{5} = 0{,}89$. Полак-Рибьер: $g_k - g_{k-1} = (0{,}1,\ -0{,}2)$, числитель $g_k^\top(g_k-g_{k-1}) = 1{,}1\cdot0{,}1 + 1{,}8\cdot(-0{,}2) = 0{,}11-0{,}36=-0{,}25$, значит $\beta_k^{PR} = \dfrac{-0{,}25}{5} = -0{,}05$.

Разница разительная: Флетчер-Ривз выдаёт $\beta_k^{FR}\approx0{,}89$ — новое направление почти на девять десятых состоит из старого направления $d_{k-1}$, то есть метод продолжает двигаться примерно туда же, куда двигался раньше. Полак-Рибьер выдаёт $\beta_k^{PR} \approx -0{,}05$ — почти ноль и даже слегка отрицательное, то есть метод фактически сбрасывает накопленную историю направлений и почти возвращается к чистому антиградиенту. Именно эта чувствительность к малым изменениям градиента и есть источник «самокорректирующегося» поведения Полака-Рибьера: если направление перестало быть информативным, формула сама почти обнуляет его вклад, тогда как Флетчер-Ривз слепо продолжает опираться на старое направление.

Пример 3: зачем нужна модификация PR+. Допустим, на очередном шаге неудачно завершившегося линейного поиска получено $\beta_k^{PR} = -0{,}4$ (отрицательное значение может возникнуть, когда функция локально повела себя настолько нестандартно, что новый градиент оказался почти противоположен предыдущему). Формула $d_k = -g_k + \beta_k d_{k-1}$ с отрицательным $\beta_k$ означает, что направление $d_{k-1}$ вычитается, а не прибавляется, — в невыгодных случаях это может привести к тому, что $d_k$ перестанет быть направлением убывания функции (направление, вдоль которого $f$ гарантированно уменьшается хотя бы немного при малом шаге). Модификация $\beta_k^{PR+} = \max(0, -0{,}4) = 0$ в этом случае превращает шаг в чистый антиградиентный шаг ($d_k = -g_k$) — самый безопасный откат, гарантированно являющийся направлением убывания при $g_k \neq 0$. Это стандартный практический приём, без которого «чистый» Полак-Рибьер на сложных невыпуклых функциях иногда может расходиться.

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

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

Гарантия сходимости за n шагов

Интуиция

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

Формализация

Теорема о конечной сходимости метода сопряжённых градиентов. Пусть $f(x) = \frac12 x^\top A x - b^\top x$, где $A \in \mathbb{R}^{n\times n}$ — симметричная положительно определённая матрица. Метод сопряжённых градиентов, стартовавший из произвольной точки $x_0$ и строящий направления по формуле $d_k = -g_k + \beta_k d_{k-1}$ с оптимальной длиной шага $\alpha_k = \dfrac{g_k^\top g_k}{d_k^\top A d_k}$ на каждой итерации, находит точный минимум $x^* = A^{-1}b$ не более чем за $n$ итераций в точной арифметике. При этом построенные направления $d_0, d_1, \dots$ попарно $A$-сопряжены, а градиенты $g_0, g_1, \dots$ попарно ортогональны в обычном евклидовом смысле.

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

Примеры

Пример 1: полная трассировка на квадратичной функции двух переменных. Возьмём $f(x,y) = x^2 + 10y^2$ (гессиан $A = \begin{pmatrix}2&0\\0&20\end{pmatrix}$, число обусловленности $10$) и стартуем из $x_0 = (10, 1)$ — тот же пример, что и выше.

Шаг 0: $g_0 = \nabla f(x_0) = (20, 20)$, $d_0 = -g_0 = (-20,-20)$. Длина шага: $\alpha_0 = \dfrac{g_0^\top g_0}{d_0^\top A d_0} = \dfrac{800}{8800} = \dfrac1{11}$. Новая точка: $x_1 = x_0 + \alpha_0 d_0 = (10,1) + \frac1{11}(-20,-20) = \left(\frac{90}{11},\ -\frac{9}{11}\right) \approx (8{,}1818,\ -0{,}8182)$.

Шаг 1: $g_1 = \nabla f(x_1) = \left(\frac{180}{11}, -\frac{180}{11}\right) \approx (16{,}3636,\ -16{,}3636)$. Коэффициент $\beta_0 = \dfrac{g_1^\top g_1}{g_0^\top g_0} = \dfrac{64800/121}{800} = \dfrac{81}{121} \approx 0{,}6694$ (уже вычислен выше). Новое направление:

Длина шага: $\alpha_1 = \dfrac{g_1^\top g_1}{d_1^\top A d_1} \approx \dfrac{535{,}54}{1947{,}55} \approx 0{,}2749$.

Новая точка: $x_2 = x_1 + \alpha_1 d_1 \approx (8{,}1818,\ -0{,}8182) + 0{,}2749\cdot(-29{,}7521,\ 2{,}9752) \approx (8{,}1818 - 8{,}1815,\ -0{,}8182+0{,}8180) \approx (0{,}0003,\ -0{,}0002)$

Практически ровно $(0,0)$ — истинный минимум функции $f(x,y)=x^2+10y^2$ (крошечная невязка $\sim 10^{-4}$ — исключительно следствие округления промежуточных десятичных вычислений, в точной арифметике с дробями получился бы ровно ноль). Функция двумерная ($n=2$), и метод точно сошёлся ровно за $n=2$ шага — именно то, что обещает теорема.

Пример 2: тот же старт, но обычный градиентный спуск — зигзаг во плоти. Возьмём ту же функцию и ту же стартовую точку $x_0=(10,1)$, но теперь применим обычный градиентный спуск (метод наискорейшего спуска) с точным линейным поиском на каждом шаге — самый благоприятный для градиентного спуска сценарий, без всякого «неудачного» ручного подбора шага. Первый шаг у него в точности совпадает с шагом метода сопряжённых градиентов (потому что $d_0 = -g_0$ в обоих методах): $x_1 = \left(\frac{90}{11},-\frac{9}{11}\right)$, как и выше.

А вот второй шаг принципиально другой: градиентный спуск снова идёт строго против нового градиента $g_1$, без всякой поправки на предыдущее направление ($\beta=0$ всегда). Оптимальная длина шага вдоль $-g_1$: $\alpha_1 = \dfrac{g_1^\top g_1}{g_1^\top A g_1} = \dfrac{64800/121}{712800/121} = \dfrac{64800}{712800} = \dfrac1{11}$.

Ответ: метод сопряжённых градиентов после двух шагов оказался точно в минимуме $(0,0)$. Градиентный спуск с той же самой, максимально благоприятной для него стратегией (точный линейный поиск на каждом шаге) после тех же двух шагов всё ещё находится в точке $(6{,}6942,\ 0{,}6694)$ — на расстоянии больше $6{,}7$ от минимума! Дальнейшие шаги градиентного спуска продолжат зигзагом, медленно приближаясь к нулю (координаты продолжат менять знак и уменьшаться по модулю каждые два шага) — это и есть та самая петляющая траектория из урока 285, представленная не качественно, а в конкретных числах.

Пример 3: гарантия не зависит от степени обусловленности. Возьмём ту же функцию, но с числом обусловленности не $10$, а $10^6$ — например, $f(x,y) = x^2 + 10^6 y^2$. Для градиентного спуска, у которого число итераций до заданной точности растёт пропорционально числу обусловленности $\kappa$ (или, в лучшем случае, $\sqrt{\kappa}$ для ускоренных вариантов), такая задача потребовала бы сотен тысяч, а то и миллионов итераций. Для метода сопряжённых градиентов теорема о конечной сходимости не зависит от числа обусловленности вообще: функция по-прежнему двумерна ($n=2$), значит, метод по-прежнему гарантированно сходится не более чем за $2$ шага в точной арифметике — какой бы «злой» ни была вытянутость оврага. Ответ: гарантия $n$ шагов метода сопряжённых градиентов — это утверждение о размерности задачи, а не о её обусловленности, и в этом смысле она принципиально сильнее асимптотических оценок скорости сходимости градиентного спуска. (На практике плохая обусловленность всё же не проходит бесследно: при вычислениях с плавающей точкой сильно вытянутые задачи накапливают больше ошибок округления, из-за чего реальное число итераций для приемлемой точности может оказаться немного больше $n$ — но принципиальное отличие от градиентного спуска, чьё число итераций растёт вместе с $\kappa$ практически без ограничения, остаётся в силе.)

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

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

Нелинейный метод сопряжённых градиентов и практическое применение

Интуиция

Всё, что было сказано выше, строго верно для квадратичных функций — а функция потерь реального машинного обучения почти никогда не бывает в точности квадратичной. Нелинейный метод сопряжённых градиентов — это прямое обобщение идеи на произвольную гладкую функцию $f$: вместо точного вычисления оптимальной длины шага по явной формуле (которая опиралась на постоянство матрицы $A$) используется обычный линейный поиск, как в квазиньютоновских методах, а формула направления $d_k = -g_k + \beta_k d_{k-1}$ остаётся той же самой, только $\beta_k$ теперь вычисляется по формуле Флетчера-Ривза или Полака-Рибьера с настоящими градиентами $\nabla f(x_k)$ произвольной функции.

Расплата за этот переход в том, что свойство $A$-сопряжённости, строго доказанное для квадратичного случая, на нелинейной функции постепенно «протекает»: эффективная локальная матрица кривизны (локальный гессиан) меняется от точки к точке, и направления, построенные по старой формуле, со временем перестают быть по-настоящему сопряжёнными. Практическое решение — периодически перезапускать направление, полагая $d_k = -g_k$ (то есть сбрасывая накопленную историю и на секунду возвращаясь к чистому градиентному спуску) каждые $n$ итераций или всякий раз, когда коэффициент $\beta_k$ становится отрицательным.

Формализация

Нелинейный метод сопряжённых градиентов.

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

где $\alpha_k$ подбирается линейным поиском, удовлетворяющим условиям Вольфа (как и в BFGS из прошлого урока), а $\beta_k$ вычисляется по формуле Флетчера-Ривза или (чаще на практике) по устойчивой версии Полака-Рибьера $\beta_k^{PR+} = \max(0, \beta_k^{PR})$. Направление периодически перезапускается ($d_k \leftarrow -g_k$) каждые $n$ итераций или при $\beta_k \le 0$.

Примеры

Пример 1: truncated Newton — метод сопряжённых градиентов внутри метода Ньютона. В уроке 287 ты уже встречал решатель newton-cg в scikit-learn — теперь можно объяснить его название до конца. Шаг метода Ньютона требует решить линейную систему $H(x_k)\,p = -\nabla f(x_k)$ относительно направления $p$, где $H$ — гессиан. При большом числе параметров $n$ вычисление и хранение полного гессиана стоит $O(n^2)$ памяти, а прямое решение системы — $O(n^3)$ операций, что для $n=10^6$ физически невозможно (те же числа, что ты видел в уроке 287). Ключевое наблюдение truncated Newton методов: линейный метод сопряжённых градиентов для решения этой самой системы $Hp=-g$ вообще не требует хранить матрицу $H$ целиком — на каждой итерации ему нужно лишь произведение матрицы на вектор, $Hv$, а такое произведение для многих моделей (в том числе через автоматическое дифференцирование) можно вычислить за $O(n)$ операций, вообще ни разу не построив полную матрицу $H$ в памяти — так называемый matrix-free подход. Запустив внутри одного шага Ньютона всего $20$–$30$ итераций линейного CG (а не все $n$, которые гарантирует теорема, — отсюда и слово «truncated», усечённый), получаем приближённое, но достаточно точное направление Ньютона за $O(20n)$–$O(30n)$ операций вместо $O(n^3)$ — колоссальная экономия для больших моделей при сохранении почти всех преимуществ ньютоновской скорости сходимости.

Пример 2: большие разреженные линейные системы в научных вычислениях. Метод конечных элементов (finite element method) для моделирования физических процессов — распределения температуры, механических напряжений, течения жидкости — регулярно порождает системы линейных уравнений $Ax=b$ с $n=10^7$ неизвестными, где матрица $A$ симметрична, положительно определена и разрежена: в каждой строке лишь несколько (скажем, $7$–$10$) ненулевых элементов, потому что физическое взаимодействие в дискретизированной модели затрагивает только соседние узлы сетки. Прямые методы вроде разложения Холецкого для такой матрицы потребовали бы неприемлемого объёма памяти из-за эффекта заполнения (fill-in: обнуление структуры разреженности при факторизации). Метод сопряжённых градиентов решает эту же систему, используя на каждой итерации только разреженное умножение матрицы на вектор стоимостью $O(\text{nnz})\approx O(7n)$ (где $\text{nnz}$ — число ненулевых элементов), и для хорошо обусловленных систем (или же для плохо обусловленных, но с хорошим предобуславливателем — preconditioner) сходится к точности, достаточной для инженерных нужд, за несколько сотен итераций вместо теоретических $10^7$. Это ровно тот класс задач, для которого метод изначально и был придуман Хестенсом и Штифелем.

Пример 3: когда даже L-BFGS слишком дорог. Вернёмся к сравнению памяти из прошлого урока. Для модели с $n = 10^9$ параметров (масштаб больших языковых моделей) L-BFGS с $m=10$ хранимыми парами векторов требует $2mn = 2\times10\times10^9 = 2\times10^{10}$ чисел — при 4 байтах на число (float32) это около $80$ гигабайт, что уже проблематично разместить в памяти даже мощного ускорителя, если она нужна ещё и для самой модели, активаций и оптимизатора. Нелинейный метод сопряжённых градиентов при этом же $n$ хранит буквально пару векторов постоянной длины — текущий градиент $g_k$ и предыдущее направление $d_{k-1}$, то есть $O(n) = 2\times10^9$ чисел, около $8$ гигабайт — на порядок меньше, чем у L-BFGS. Ответ: ценой обычно более медленной, чем у L-BFGS, практической сходимости (нелинейный CG в среднем требует больше итераций до той же точности, потому что использует меньше накопленной информации о кривизне) метод сопряжённых градиентов остаётся рабочим вариантом именно там, где даже экономная по памяти L-BFGS перестаёт помещаться, — граница, за которой начинается царство чисто стохастических методов первого порядка (SGD, Adam) из урока 286, если задачу вообще можно решать по мини-батчам, либо специализированных truncated Newton и matrix-free подходов, если нужна точность второго порядка при ограниченной памяти.

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

Нелинейное обобщение метода сопряжённых градиентов — это не абстрактное теоретическое расширение ради полноты картины, а мост между красивой теорией конечной сходимости на квадратичных функциях и реальными задачами, где функция потерь почти никогда не квадратична. Именно этот мост объясняет, почему метод сопряжённых градиентов сегодня встречается не как самостоятельный «главный» оптимизатор в машинном обучении (эту роль в основном делят между собой SGD/Adam для больших нейросетей и L-BFGS для средних классических моделей), а как рабочий компонент внутри других методов — прежде всего внутри truncated Newton решателей вроде newton-cg, — и как основной инструмент для по-настоящему гигантских, но разреженных или крайне ограниченных по памяти задач в научных вычислениях и оптимизации с ограничениями.

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

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

Задание 1: Даны векторы $d_0 = (1,0)^\top$, $d_1 = (0,1)^\top$ и матрица $A = \begin{pmatrix}5&0\\0&3\end{pmatrix}$. Проверь, являются ли эти векторы сопряжёнными относительно $A$.

Задание 2: Даны $A = \begin{pmatrix}4&0\\0&1\end{pmatrix}$, $d_0=(1,1)^\top$. Найди вектор $d_1=(x,y)^\top$, сопряжённый с $d_0$ относительно $A$, при условии $x=1$.

Задание 3: Проверь, ортогональны ли в обычном евклидовом смысле векторы $d_0=(1,1)^\top$ и $d_1=(1,-4)^\top$ из задания 2.

Задание 4: Для функции $f(x,y)=x^2+10y^2$ найди градиент в точке $(4,2)$.

Задание 5: Для $g_0=(8,40)$ вычисли направление первого шага метода сопряжённых градиентов $d_0$.

Задание 6: Даны $g_{k-1}^\top g_{k-1} = 10$, $g_k^\top g_k = 4$. Вычисли $\beta_k^{FR}$ по формуле Флетчера-Ривза.

Задание 7: Даны $g_{k-1}=(2,0)$, $g_k=(1,1)$. Вычисли $\beta_k^{PR}$ по формуле Полака-Рибьера.

Задание 8: Объясни своими словами, почему $\beta_0$ (коэффициент для самого первого шага метода) не определяется ни по одной из формул Флетчера-Ривза или Полака-Рибьера.

Задание 9: Функция $f(x,y)=x^2+10y^2$ имеет 2 переменные. Сколько шагов в точной арифметике гарантированно потребуется методу сопряжённых градиентов, чтобы найти точный минимум?

Задание 10: Сравни объём хранимой информации между L-BFGS с $m=10$ и методом сопряжённых градиентов для модели с $n=200\,000$ параметров (число хранимых чисел, без учёта самого вектора параметров).

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

Задание 11: Для $f(x,y)=x^2+10y^2$, $x_0=(10,1)$, $g_0=(20,20)$, $d_0=(-20,-20)$, гессиан $A=\begin{pmatrix}2&0\\0&20\end{pmatrix}$ вычисли длину шага $\alpha_0 = \dfrac{g_0^\top g_0}{d_0^\top A d_0}$.

Задание 12: Используя $\alpha_0=1/11$ из задания 11, вычисли точку $x_1 = x_0+\alpha_0 d_0$.

Задание 13: Вычисли градиент $g_1=\nabla f(x_1)$ в точке $x_1\approx(8{,}1818,-0{,}8182)$ для той же функции $f(x,y)=x^2+10y^2$.

Задание 14: Проверь, что $g_0=(20,20)$ и $g_1\approx(16{,}3636,-16{,}3636)$ из задания 13 ортогональны в обычном евклидовом смысле.

Задание 15: Используя $g_0^\top g_0=800$ и $g_1^\top g_1\approx535{,}54$, вычисли $\beta_0$ по формуле Флетчера-Ривза.

Задание 16: Используя $g_1\approx(16{,}3636,-16{,}3636)$, $\beta_0\approx0{,}6694$ и $d_0=(-20,-20)$, вычисли направление $d_1 = -g_1+\beta_0 d_0$.

Задание 17: Объясни, почему в примере из урока на функции $f(x,y)=x^2+10y^2$ первый шаг метода сопряжённых градиентов и первый шаг обычного градиентного спуска (с точным линейным поиском) из одной и той же точки всегда совпадают.

Задание 18: На той же функции градиентный спуск (без учёта предыдущих направлений) после двух шагов с точным линейным поиском оказался в точке $\approx(6{,}6942,\ 0{,}6694)$, а метод сопряжённых градиентов — в точке $\approx(0,0)$. Оцени, во сколько раз метод сопряжённых градиентов ближе к минимуму по евклидовому расстоянию после двух шагов.

Задание 19: Функция потерь зависит от $n=50$ параметров и строго квадратична. Сколько итераций гарантированно потребуется методу сопряжённых градиентов в точной арифметике?

Задание 20: Объясни, почему на практике (в вычислениях с плавающей точкой) число итераций метода сопряжённых градиентов иногда превышает теоретическую границу $n$.

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

Задание 21: Объясни, почему метод сопряжённых градиентов способен строить систему из $n$ сопряжённых направлений, храня на каждом шаге только текущий градиент и одно предыдущее направление, а не всю историю направлений (в отличие от общего процесса Грама-Шмидта).

Задание 22: В уроке 287 упоминался решатель newton-cg в scikit-learn. Объясни, какую роль в нём играет метод сопряжённых градиентов и почему это избавляет от необходимости хранить полный гессиан.

Задание 23: Даны $\beta_k^{PR} = -0{,}3$. Что предпримет реализация с модификацией PR+ на этом шаге, и почему это важно для гарантии направления убывания?

Задание 24 (ML): Модель структурного предсказания для физической симуляции (метод конечных элементов) даёт систему $Ax=b$ с $n=5\,000\,000$ переменных, где матрица $A$ разрежена — в каждой строке $8$ ненулевых элементов. Оцени стоимость одной итерации метода сопряжённых градиентов и сравни её со стоимостью хранения полного гессиана.

Задание 25 (ML): Модель с $n=10^9$ параметров обучается, и даже L-BFGS с $m=10$ занимает слишком много памяти. Оцени объём памяти (в гигабайтах, float32) для метода сопряжённых градиентов, хранящего только текущий градиент и предыдущее направление, и сравни с L-BFGS.

Задание 26: Объясни, почему нелинейный метод сопряжённых градиентов требует периодических перезапусков направления ($d_k=-g_k$), тогда как линейный метод сопряжённых градиентов для квадратичной функции в этом не нуждается.

Задание 27: Сравни метод сопряжённых градиентов и L-BFGS по количеству итераций, обычно требуемых для достижения заданной точности на одной и той же нелинейной задаче, и объясни первопричину этой разницы.

Задание 28: Объясни, почему стохастический (мини-батчевый) градиентный шум плохо совместим с идеей метода сопряжённых градиентов, в отличие от полного (батчевого) градиента.

Задание 29: Дана квадратичная функция от $n=100$ переменных с числом обусловленности гессиана $\kappa=10^8$ (экстремально плохо обусловленная задача). Сравни качественно поведение градиентного спуска и метода сопряжённых градиентов.

Задание 30: Обобщи одним связным рассуждением: почему метод сопряжённых градиентов заслуженно называют «третьим путём» между градиентным спуском и методом Ньютона, а не просто ещё одним вариантом одного из них.

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

• Путают A-сопряжённость с обычной ортогональностью. Условие $d_i^\top A d_j = 0$ — это не то же самое, что $d_i^\top d_j = 0$: как показано в примере 2 первого раздела, векторы могут быть $A$-сопряжёнными и совершенно не перпендикулярными в обычном евклидовом смысле, и наоборот.

• Не перезапускают направление на нелинейных задачах. Без периодического сброса $d_k=-g_k$ (каждые $n$ итераций или при $\beta_k \le 0$) накопленная история направлений на неквадратичной функции постепенно перестаёт быть сопряжённой относительно меняющегося локального гессиана, и метод может застревать или сходиться заметно медленнее.

• Используют «чистый» Полак-Рибьер без клиппинга $\max(0,\cdot)$. Отрицательное значение $\beta_k^{PR}$ может привести к направлению, которое перестаёт быть направлением убывания функции — это ломает дальнейший линейный поиск. Стандартная защита — модификация PR+.

• Путают линейный и нелинейный варианты метода. В линейном методе сопряжённых градиентов (для решения $Ax=b$) длина шага $\alpha_k$ вычисляется по точной замкнутой формуле; в нелинейном варианте матрицы $A$ явно нет, и $\alpha_k$ обязательно подбирается линейным поиском — попытка применить формулу линейного случая к произвольной нелинейной функции даёт бессмысленный результат.

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

• Путают метод сопряжённых градиентов с квазиньютоновскими методами. В отличие от BFGS/L-BFGS, метод сопряжённых градиентов никогда не строит и не хранит (даже приближённо) никакой матрицы — только векторы текущего градиента и предыдущего направления, память $O(n)$ вместо $O(mn)$ или $O(n^2)$.

• Игнорируют влияние округления на теоретическую гарантию. Для больших и плохо обусловленных систем накопленные ошибки округления в вычислениях с плавающей точкой могут нарушить точную $A$-сопряжённость направлений, из-за чего реальное число итераций для достижения нужной точности может заметно превысить $n$ — в таких случаях помогает предобуславливание (preconditioning).

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

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

• Метод сопряжённых градиентов выбирает направления, сопряжённые относительно гессиана $A$ (условие $d_i^\top A d_j = 0$), а не просто ортогональные в обычном смысле — движение вдоль таких направлений не портит уже достигнутый прогресс по предыдущим направлениям.

• $A$-сопряжённость — это ортогональность в «искажённой» метрике, задаваемой матрицей $A$, а не обычная евклидова перпендикулярность: сопряжённые векторы вовсе не обязаны выглядеть перпендикулярными на глаз.

• Направление на шаге $k$ строится по короткой двучленной формуле $d_k = -g_k + \beta_k d_{k-1}$ — методу не нужно хранить всю историю предыдущих направлений, достаточно одного последнего.

• Формулы Флетчера-Ривза и Полака-Рибьера совпадают для квадратичной функции при точном линейном поиске, но расходятся на нелинейных функциях — Полак-Рибьер (особенно версия PR+) обычно устойчивее на практике.

• Для строго выпуклой квадратичной функции размерности $n$ метод сопряжённых градиентов гарантированно сходится точно не более чем за $n$ шагов в точной арифметике — конечная, а не асимптотическая гарантия.

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

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

• На практике метод сопряжённых градиентов чаще встречается не как самостоятельный оптимизатор, а внутри truncated Newton методов (например, newton-cg) — там он приближённо и matrix-free решает линейную систему Ньютона, ни разу не построив полный гессиан.

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

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

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

Связь с методом Ньютона из урока 287 двойная. Во-первых, обе теоремы о финальной сходимости — квадратичная сходимость метода Ньютона и конечная сходимость за $n$ шагов метода сопряжённых градиентов — описывают точные, а не асимптотические гарантии на квадратичных функциях, только достигают их принципиально разными средствами: метод Ньютона напрямую вычисляет кривизну, метод сопряжённых градиентов вообще её не вычисляет. Во-вторых, и практичнее: метод сопряжённых градиентов буквально встроен внутрь решателя newton-cg, упомянутого в уроке 287, — именно он приближённо и без явного построения гессиана решает линейную систему Ньютона $Hp=-g$ на каждом шаге, делая метод Ньютона применимым там, где прямое обращение гессиана было бы неподъёмным.

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

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

• Метод сопряжённых градиентов изначально создавался вовсе не как алгоритм оптимизации, а как точный (не итерационный) метод решения систем линейных уравнений — конкурент методу Гаусса, дешёвый именно для разреженных матриц. Итерационное использование, остановленное задолго до $n$-го шага, стало основным способом применения метода лишь позже, когда стало ясно, насколько хорошо он приближает решение уже за малое число итераций.

• Хестенс и Штифель работали над методом независимо друг от друга — один в Национальном бюро стандартов США, другой в ETH Цюрих — и объединили результаты в одну совместную публикацию 1952 года вместо того, чтобы состязаться за приоритет, что было по тем временам довольно редким научным жестом.

• Метод сопряжённых градиентов математически тесно связан с алгоритмом Ланцоша (Lanczos algorithm) для приближённого вычисления собственных значений больших разреженных матриц — оба метода строят один и тот же тип крыловских подпространств (Krylov subspaces) с помощью очень похожей трёхчленной рекуррентности.

• За пределами машинного обучения метод (и его варианты, включая предобусловленный CG) остаётся одним из основных инструментов вычислительной физики: расчёт молекулярной динамики, электронной структуры вещества, механики сплошных сред методом конечных элементов и вычислительной гидродинамики регулярно опираются именно на него для решения систем с миллионами и десятками миллионов неизвестных.

Лайфхаки

• Если формула Полака-Рибьера выдаёт отрицательное $\beta_k$, используй модификацию PR+ ($\beta_k = \max(0,\beta_k^{PR})$) вместо «чистого» Полака-Рибьера — это дёшево и надёжно защищает от потери направления убывания.

• На нелинейных задачах периодически перезапускай направление ($d_k=-g_k$) каждые $n$ итераций, даже если формально $\beta_k$ остаётся положительным, — это заметно повышает устойчивость на практике.

• Для решения линейных систем всегда рассматривай предобусловленный метод сопряжённых градиентов (preconditioned CG, PCG): хороший предобуславливатель может резко сократить эффективное число обусловленности задачи, а вместе с ним и число нужных итераций — иногда на порядки.

• Не пытайся напрямую применять метод сопряжённых градиентов к стохастическому (мини-батчевому) обучению нейросетей — шум между итерациями разрушает согласованность градиентов, на которой держатся формулы $\beta_k$; для стохастической оптимизации остаются SGD и Adam из урока 286.

• Если нужна ньютоновская скорость сходимости при ограниченной памяти — не строй гессиан напрямую, а решай систему Ньютона приближённо линейным CG в matrix-free режиме, используя только произведения гессиана на вектор (Hessian-vector products), которые для многих моделей вычисляются автоматическим дифференцированием за $O(n)$.

• При отладке реализации проверяй промежуточное свойство $A$-сопряжённости построенных направлений на небольшой квадратичной тестовой задаче (например, $2$–$3$ переменные, как в разобранных примерах урока) — если $d_i^\top A d_j$ заметно отличается от нуля, ошибка почти наверняка в формуле $\beta_k$ или в вычислении градиента.

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