Метод Ньютона 🎯

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

Стоит сразу проговорить честный компромисс, вокруг которого построен весь этот урок. Метод Ньютона сходится к минимуму на порядки быстрее градиентного спуска и SGD — там, где градиентному спуску нужны тысячи итераций с аккуратно подобранным шагом, методу Ньютона вблизи минимума хватает буквально нескольких. Но за эту скорость приходится платить: на каждом шаге нужно вычислить полный гессиан — матрицу размером $n \times n$, где $n$ — число параметров модели, — а затем обратить эту матрицу, что стоит $O(n^3)$ арифметических операций. Для логистической регрессии с несколькими сотнями признаков это доли секунды. Для нейросети с миллионом параметров гессиан — это матрица из $10^{12}$ чисел, а её обращение потребовало бы порядка $10^{18}$ операций за один-единственный шаг оптимизации. Именно поэтому SGD и Adam, на которых обучаются современные нейросети, сознательно отказываются от этой точной, но неподъёмно дорогой информации о кривизне в пользу дешёвого, приближённого шага, использующего только градиент.

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

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

История

Метод, который сегодня называют методом Ньютона, был предложен Исааком Ньютоном около 1669 года в рукописи De analysi per aequationes numero terminorum infinitas, но изначально он решал совсем другую, более узкую задачу — численное нахождение корня многочлена, то есть точки, где функция обращается в ноль, а не точки её экстремума. Ньютон работал с конкретными числовыми примерами и не дал общей формулы в привычном сегодня виде — его изложение было громоздким и специфичным для каждого отдельного уравнения. Более простую и по существу современную итеративную формулу для нахождения корня произвольного уравнения предложил английский математик Джозеф Рафсон в 1690 году в работе Analysis Aequationum Universalis, из-за чего в математической литературе метод часто и справедливо называют методом Ньютона — Рафсона.

Применение этой же идеи к задаче поиска экстремума функции, а не корня уравнения, — на самом деле не новая идея, а прямое следствие старой: чтобы найти минимум функции $f$, достаточно найти корень её производной $f'$, ведь именно там $f'(x) = 0$. Формально применив метод Ньютона к уравнению $f'(x) = 0$, получаешь формулу, использующую вторую производную $f''(x)$, — то, что мы сегодня и называем методом Ньютона в оптимизации. Английский математик Томас Симпсон в 1740 году одним из первых явно обобщил метод на системы нескольких уравнений и на задачи нахождения максимумов и минимумов, введя в рассмотрение то, что позже назовут производными по нескольким переменным.

По-настоящему многомерная версия метода — с полноценным гессианом, матрицей вторых частных производных, — оформилась значительно позже, вместе с развитием матричного анализа в XIX веке. Но по-настоящему практичным инструментом метод Ньютона стал только с появлением электронных вычислительных машин в середине XX века: обращение матрицы вручную для более чем двух-трёх переменных было попросту непосильным трудом, а компьютер сделал это рутинной, хотя и по-прежнему дорогой операцией. Ирония судьбы в том, что именно вычислительная сторона — доступность обращения больших матриц — сначала сделала метод Ньютона практичным инструментом численной оптимизации XX века, а затем, с появлением моделей с миллионами и миллиардами параметров в глубоком обучении, снова сделала его непрактичным: кубическая стоимость $O(n^3)$ растёт быстрее, чем успевают расти вычислительные мощности, обгоняя рост размеров современных моделей на порядки.

Квадратичная аппроксимация через ряд Тейлора и формула шага

Интуиция

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

Это ровно та идея, которую ты уже разбирал в университетском курсе в уроке про формулу Тейлора (урок 193): там квадратичная аппроксимация функции потерь через градиент и гессиан выводилась как прямое следствие ряда Тейлора, оборванного на втором члене. Здесь мы применяем этот же аппарат не как абстрактное упражнение анализа, а как рабочий инструмент оптимизации.

Формула

Квадратичная модель функции потерь. Пусть $L(w)$ — функция потерь, зависящая от вектора параметров $w \in \mathbb{R}^n$, дважды непрерывно дифференцируемая в окрестности текущей точки $w_k$. Разложение по формуле Тейлора до второго члена даёт:

$$L(w) \approx L(w_k) + \nabla L(w_k)^\top (w - w_k) + \frac12 (w - w_k)^\top H(w_k) (w - w_k)$$

где $\nabla L(w_k)$ — градиент, а $H(w_k)$ — гессиан (матрица вторых частных производных) функции потерь в точке $w_k$. Минимизируя правую часть по $w$ (приравнивая её градиент по $w$ к нулю) и полагая гессиан обратимым, получаем шаг метода Ньютона:

$$w_{k+1} = w_k - H(w_k)^{-1} \nabla L(w_k)$$

Сравни эту формулу с формулой шага градиентного спуска из урока 285, $w_{k+1} = w_k - \eta \nabla L(w_k)$: единственная, но принципиальная разница — вместо скалярной скорости обучения $\eta$, которую ты подбираешь заранее и вручную, здесь стоит матрица $H(w_k)^{-1}$, обратный гессиан, которая вычисляется автоматически из самой функции потерь и «знает», насколько длинным должен быть шаг в каждом направлении.

Разбор примеров

Пример 1 (лёгкий, точное попадание на квадратичной функции). Найти минимум функции $L(w) = (w-3)^2 + 1$ методом Ньютона, стартуя из точки $w_0 = 0$, и сравнить с числом итераций градиентного спуска из урока 285 для той же функции.

Вычислим производные: $L'(w) = 2(w-3)$, $L''(w) = 2$ (гессиан для функции одной переменной — это просто число, вторая производная).

Ответ: метод Ньютона находит точный минимум $w=3$ за один-единственный шаг. Это не совпадение, а прямое следствие того, что $L(w)$ уже сама является квадратичной функцией: квадратичная аппроксимация функции по ряду Тейлора для квадратичной функции совпадает с самой функцией без всякой погрешности, поэтому «прыжок в минимум параболоида» и есть прыжок в истинный минимум. Для сравнения, в уроке 285 обычному градиентному спуску с $\alpha=0{,}1$ для этой же функции потребовалось несколько итераций ($x_0=0 \to x_1=0{,}6 \to x_2=1{,}08 \to x_3=1{,}464 \to \ldots$), медленно приближаясь к тройке, а не попадая в неё сразу.

Пример 2 (средний, не квадратичная функция — явная демонстрация превосходства в скорости). Найти минимум функции $L(w) = e^w - w$ (минимум при $w=0$, так как $L'(w) = e^w - 1 = 0 \iff w=0$), стартуя из $w_0 = 1$, методом Ньютона и сравнить с градиентным спуском с $\eta = 0{,}3$ на той же функции и с той же стартовой точки.

Производные: $L'(w) = e^w - 1$, $L''(w) = e^w$. Формула шага: $w_{k+1} = w_k - \dfrac{e^{w_k}-1}{e^{w_k}} = w_k - 1 + e^{-w_k}$.

Метод Ньютона, шаг за шагом:

w0 = 1
w1 = 1 - (e^1 - 1)/e^1        = 1 - 1,71828/2,71828 = 0,367879
w2 = 0,367879 - (e^0,367879 - 1)/e^0,367879 = 0,060074
w3 = 0,060074 - (e^0,060074 - 1)/e^0,060074 = 0,001789
w4 = 0,001789 - ...                              ≈ 0,0000016

Градиентный спуск с $\eta=0{,}3$ на той же функции ($w_{k+1} = w_k - 0{,}3 \cdot (e^{w_k}-1)$), шаг за шагом:

w0 = 1
w1 = 1 - 0,3 * (e^1 - 1)      = 1 - 0,515484 = 0,484516
w2 = 0,484516 - 0,3 * (e^0,484516 - 1) = 0,297489
w3 = 0,297489 - 0,3 * (e^0,297489 - 1) = 0,193549
w4 = 0,193549 - 0,3 * (e^0,193549 - 1) = 0,129487

Ответ: за 3 шага метод Ньютона добрался до $w_3 \approx 0{,}0018$, практически неотличимо от истинного минимума $w^*=0$. Градиентный спуск за те же 4 шага дошёл только до $w_4 \approx 0{,}129$ — ему потребовалось бы ещё немало итераций, чтобы приблизиться настолько же близко. Это уже не случай точной квадратичной функции, как в примере 1, — здесь $L(w) = e^w - w$ не квадратична, и всё же метод Ньютона обгоняет градиентный спуск на порядок за одинаковое число шагов, потому что учитывает кривизну функции, а не только направление её роста.

Пример 3 (сложный, ML — многомерный случай, точный прыжок и невыпуклый провал). Дана квадратичная функция потерь двух параметров $L(w_1, w_2) = w_1^2 + 2w_2^2 - 4w_1 - 4w_2$. Найти минимум методом Ньютона за один шаг из точки $(0,0)$, а затем показать, что для невыпуклой функции $L(w_1,w_2) = w_1^2 - w_2^2$ (седловая точка в начале координат) метод Ньютона из точки $(0{,}1;\ 0{,}1)$ прыгает не в минимум, а прямиком в седловую точку.

Для первой функции: $\nabla L = (2w_1 - 4,\ 4w_2 - 4)$, гессиан $H = \begin{pmatrix}2 & 0\\0 & 4\end{pmatrix}$, обратный гессиан $H^{-1} = \begin{pmatrix}0{,}5 & 0\\0 & 0{,}25\end{pmatrix}$ (гессиан постоянный, не зависит от точки, потому что функция квадратичная).

Проверка напрямую: $\partial L/\partial w_1 = 2w_1-4=0 \Rightarrow w_1=2$, $\partial L/\partial w_2 = 4w_2-4=0 \Rightarrow w_2=1$ — метод Ньютона нашёл точный минимум $(2,1)$ за один шаг, как и в примере 1, в силу той же причины: функция сама квадратична.

Для второй, невыпуклой функции: $\nabla L = (2w_1,\ -2w_2)$, гессиан $H=\begin{pmatrix}2 & 0\\0 & -2\end{pmatrix}$ — эта матрица не положительно определена (у неё есть отрицательное собственное значение $-2$). Обратный гессиан $H^{-1}=\begin{pmatrix}0{,}5 & 0\\0 & -0{,}5\end{pmatrix}$.

Ответ: в первом случае метод Ньютона за один шаг попал в истинный минимум $(2,1)$. Во втором случае он тоже сходится за один шаг — но в точку $(0,0)$, которая является не минимумом, а седловой точкой (минимум по $w_1$, максимум по $w_2$): вдоль оси $w_2$ шаг метода Ньютона фактически увеличивает функцию потерь, а не уменьшает. Это прямая иллюстрация того, что формула шага метода Ньютона сама по себе «не знает», минимум перед ней или седло — она просто находит стационарную точку квадратичной модели, а с отрицательными собственными значениями гессиана эта стационарная точка запросто может оказаться максимумом или седлом.

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

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

Геометрическая интуиция: аппроксимация параболоидом

Интуиция

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

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

Формула

Геометрический смысл шага метода Ньютона. Квадратичная модель $Q(w) = L(w_k) + \nabla L(w_k)^\top(w-w_k) + \frac12(w-w_k)^\top H(w_k)(w-w_k)$ — это уравнение параболоида (в общем случае — эллиптического параболоида, если $H(w_k)$ положительно определена), касающегося графика $L(w)$ в точке $w_k$ с той же первой и второй производной. Шаг метода Ньютона $w_{k+1} = w_k - H(w_k)^{-1}\nabla L(w_k)$ — это координаты вершины (минимума) этого параболоида.

Разбор примеров

Пример 1 (лёгкий, одномерная парабола как аппроксимация). Функция потерь $L(w) = \ln(1+w^2)$ имеет минимум при $w=0$. Построить квадратичную аппроксимацию (параболу) в точке $w_0 = 1$ и найти вершину этой параболы — то есть шаг метода Ньютона.

$L'(w) = \dfrac{2w}{1+w^2}$, $L'(1) = 1$. $L''(w) = \dfrac{2(1+w^2) - 2w\cdot 2w}{(1+w^2)^2} = \dfrac{2-2w^2}{(1+w^2)^2}$, $L''(1) = \dfrac{0}{4} = 0$.

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

Пример 2 (средний, параболоид в двух измерениях). Для функции $L(w_1,w_2) = 3w_1^2 + w_2^2$ построить квадратичную аппроксимацию в точке $(1,1)$ и явно показать, что она совпадает с самой функцией (поскольку функция уже квадратична), а вершина параболоида — это истинный минимум.

$\nabla L(1,1) = (6w_1, 2w_2)\big|_{(1,1)} = (6,2)$, гессиан $H = \begin{pmatrix}6&0\\0&2\end{pmatrix}$ (постоянный). Квадратичная модель:

Раскрыв скобки, получишь ровно $Q(w) = 3w_1^2 + w_2^2 = L(w)$ — аппроксимация совпадает с оригиналом без остатка. Вершина параболоида: $H^{-1}\nabla L(1,1) = \begin{pmatrix}1/6 & 0\\0 & 1/2\end{pmatrix}(6,2) = (1,1)$, значит $w^{(1)} = (1,1) - (1,1) = (0,0)$ — истинный минимум функции. Ответ: параболоид-аппроксимация здесь не приближение, а точная копия функции, поэтому «прыжок в вершину параболоида» буквально означает «прыжок в истинный минимум» — предельный, самый благоприятный случай для метода Ньютона.

Пример 3 (сложный, ML — асимметричная кривизна и разная длина шага по осям). Функция потерь $L(w_1,w_2) = 10w_1^2 + 0{,}1w_2^2$ моделирует ситуацию, часто встречающуюся на практике: один параметр модели ($w_1$) сильно влияет на ошибку (крутой овраг), а другой ($w_2$) — слабо (пологое направление). Сравнить длину шага метода Ньютона и градиентного спуска (с единым $\eta$ для обоих направлений) из точки $(1,1)$.

Гессиан $H = \begin{pmatrix}20 & 0\\0 & 0{,}2\end{pmatrix}$, обратный $H^{-1} = \begin{pmatrix}0{,}05 & 0\\0 & 5\end{pmatrix}$. Градиент в $(1,1)$: $(20, 0{,}2)$.

Шаг Ньютона: $H^{-1}\nabla L = (0{,}05 \cdot 20,\ 5 \cdot 0{,}2) = (1, 1)$, значит $w^{(1)} = (1,1)-(1,1) = (0,0)$ — точный минимум за один шаг, потому что метод Ньютона автоматически растягивает шаг в пологом направлении ($w_2$, множитель $5$) и сжимает его в крутом направлении ($w_1$, множитель $0{,}05$), компенсируя разную кривизну по разным осям.

Градиентный спуск с единым $\eta$ вынужден выбирать компромисс: если взять $\eta$ достаточно большим, чтобы быстро двигаться по пологому направлению $w_2$, шаг по крутому направлению $w_1$ станет слишком большим и алгоритм начнёт «скакать» через минимум (расходиться); если взять $\eta$ достаточно малым, чтобы не разойтись по $w_1$, движение по $w_2$ станет мучительно медленным. Например, при $\eta = 0{,}05$ (безопасно для $w_1$) шаг по $w_2$: $w_2^{(1)} = 1 - 0{,}05\cdot0{,}2 = 0{,}99$ — почти не сдвинулся. Ответ: это классическая проблема «оврагов» в градиентном спуске (её ты уже видел качественно в уроке 285), и метод Ньютона решает её геометрически ровно потому, что параболоид-аппроксимация «знает» о разной кривизне по разным направлениям и учитывает её в форме матрицы, а не одного скалярного числа.

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

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

Квадратичная скорость сходимости

Интуиция

Термины «линейная» и «квадратичная» сходимость описывают, насколько быстро уменьшается ошибка $e_k = w_k - w^*$ (расстояние до истинного минимума) от итерации к итерации. При линейной сходимости, характерной для градиентного спуска, ошибка на каждом шаге умножается примерно на одну и ту же константу меньше единицы — она убывает как геометрическая прогрессия, то есть довольно медленно с ростом требуемой точности. При квадратичной сходимости, характерной для метода Ньютона вблизи минимума, каждая новая ошибка примерно пропорциональна квадрату предыдущей — а значит, если ошибка была $0{,}1$, следующая будет порядка $0{,}01$, затем порядка $0{,}0001$, затем $0{,}00000001$: количество верных знаков после запятой на каждом шаге примерно удваивается.

Формула

Теорема (квадратичная сходимость метода Ньютона). Пусть $L$ дважды непрерывно дифференцируема, $w^*$ — точка строгого минимума с $\nabla L(w^*) = 0$ и обратимым положительно определённым гессианом $H(w^*)$, а гессиан липшицев (то есть не меняется слишком резко) в окрестности $w^*$. Тогда для достаточно близких к $w^*$ начальных точек существует константа $C > 0$, такая что

$$\|w_{k+1} - w^*\| \le C\,\|w_k - w^*\|^2$$

Этот результат ты уже выводил в уроке 193 при разборе формулы Тейлора: он получается разложением градиента $\nabla L(w_k)$ вокруг $w^*$ по формуле Тейлора и подстановкой в шаг метода Ньютона — линейная часть ошибки полностью уничтожается конструкцией самого шага, и остаётся только член следующего порядка малости.

Разбор примеров

Пример 1 (лёгкий, числовая демонстрация удвоения точности). Взять последовательность ошибок из примера 2 первого раздела ($L(w)=e^w-w$, метод Ньютона от $w_0=1$): $e_0=1$, $e_1=0{,}367879$, $e_2=0{,}060074$, $e_3=0{,}001789$. Проверить, выполняется ли для этой последовательности примерное правило $e_{k+1} \approx C \cdot e_k^2$ с постоянной $C$.

Ответ: отношение $e_{k+1}/e_k^2$ стабилизируется около константы $\approx 0{,}5$ — это и есть числовое подтверждение квадратичной сходимости: как только метод «зашёл в окрестность минимума», число верных десятичных знаков в приближении на каждом шаге примерно удваивается (от одного верного знака у $e_1$ к трём у $e_2$ и к пяти-шести у $e_3$).

Пример 2 (средний, прямое сравнение числа итераций до заданной точности). Оценить, сколько итераций потребуется методу Ньютона и сколько — градиентному спуску с линейной скоростью сходимости $e_{k+1} = 0{,}7\,e_k$ (типичная для не самой удачно подобранной скорости обучения), чтобы уменьшить начальную ошибку $e_0 = 1$ до уровня $e_k < 10^{-6}$.

Для линейной сходимости: $0{,}7^k < 10^{-6} \Rightarrow k > \dfrac{-6}{\log_{10}0{,}7} = \dfrac{-6}{-0{,}1549} \approx 38{,}7$, то есть нужно около 39 итераций.

Для квадратичной сходимости с константой $C\approx0{,}5$: $e_1 \approx 0{,}5$, $e_2 \approx 0{,}5\cdot0{,}25=0{,}125$, $e_3\approx0{,}5\cdot0{,}015625\approx0{,}0078$, $e_4\approx0{,}5\cdot0{,}000061\approx0{,}0000305$, $e_5\approx0{,}5\cdot(3{,}05\times10^{-5})^2\approx4{,}65\times10^{-10}$ — уже меньше $10^{-6}$.

Ответ: методу Ньютона хватает 5 итераций, чтобы дойти туда, куда градиентному спуску с разумной, но не идеальной скоростью обучения требуется около 39 итераций. Разница растёт ещё сильнее, если запросить более высокую точность: чтобы дойти до $10^{-12}$, линейной сходимости потребуется вдвое больше итераций (около 77), а квадратичной — буквально на одну-две итерации больше, чем для $10^{-6}$, потому что число верных знаков удваивается на каждом шаге.

Пример 3 (сложный, ML — где именно «включается» квадратичная сходимость). Объяснить, почему на первых итерациях обучения логистической регрессии решателем newton-cg (вдали от оптимальных весов) метод Ньютона может сходиться совсем не так эффектно, как в примерах выше, а иногда делать шаги, которые почти не уменьшают функцию потерь, и лишь позже, ближе к минимуму, резко ускоряется.

Теорема о квадратичной сходимости, которую мы сформулировали выше, — локальный результат: она гарантированно работает только «для достаточно близких к $w^*$ начальных точек», то есть в некоторой окрестности минимума, размер которой заранее не известен и зависит от того, насколько сильно гессиан меняется на этом участке. Вдали от минимума гессиан текущей точки $H(w_k)$ может сильно отличаться от гессиана в оптимуме $H(w^*)$, и приближение $\nabla L(w_k) \approx H(w^*)\,e_k$, на которое опирается доказательство квадратичной сходимости, попросту не работает — ошибка на следующем шаге может убывать медленно, оставаться почти неизменной или даже расти. Ответ: это ровно та причина, по которой практические реализации метода Ньютона (включая newton-cg) почти никогда не используют формулу шага в чистом виде: они добавляют механизмы контроля шага (line search — линейный поиск оптимальной длины шага вдоль направления Ньютона, доверительные области), которые обеспечивают устойчивое поведение вдали от минимума, а квадратичная сходимость проявляется во всей красе уже ближе к финалу оптимизации, когда текущая точка попадает в ту самую «локальную окрестность», где работает теорема.

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

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

Проблема гессиана: стоимость $O(n^3)$ и невыпуклый случай

Интуиция

Всё, что ты видел до сих пор, работало на функциях одной-двух переменных, где гессиан — это число или матрица $2\times2$, а обращение такой матрицы — тривиальная операция. Реальные модели машинного обучения устроены иначе: логистическая регрессия с сотнями признаков — это уже гессиан размера сотни на сотни, а нейросеть с миллионом весов — это гессиан размера миллион на миллион. Здесь начинается настоящая, практическая проблема метода Ньютона, из-за которой его почти никогда не применяют напрямую для больших моделей: и сам гессиан, и операция его обращения становятся вычислительно неподъёмными задолго до того, как модель дорастает до масштабов современных нейросетей.

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

Формула

Стоимость шага метода Ньютона для $n$ параметров. Вычисление полного гессиана функции потерь для модели с $n$ параметрами требует хранения $O(n^2)$ чисел (все элементы симметричной матрицы $n\times n$). Решение системы линейных уравнений $H(w_k)\,\Delta w = \nabla L(w_k)$ (что эквивалентно обращению гессиана и умножению на градиент) методами прямого решения, такими как разложение Холецкого или Гаусса, требует $O(n^3)$ арифметических операций.

Условие корректности шага. Шаг метода Ньютона $w_{k+1}=w_k-H(w_k)^{-1}\nabla L(w_k)$ является направлением убывания функции потерь только тогда, когда гессиан $H(w_k)$ положительно определён. Если у $H(w_k)$ есть хотя бы одно отрицательное собственное значение, шаг метода Ньютона может увеличивать значение функции потерь вдоль соответствующего направления.

Разбор примеров

Пример 1 (лёгкий, числовая иллюстрация роста $n^3$). Сравнить число операций, необходимых для одного шага метода Ньютона, для логистической регрессии со $100$ признаками и для небольшой полносвязной нейросети с $10\,000$ параметрами.

При $n=100$: $O(n^3) = 100^3 = 10^6$ операций — на современном компьютере это доли миллисекунды, абсолютно приемлемая цена за один шаг оптимизации.

При $n=10\,000$: $O(n^3) = 10\,000^3 = 10^{12}$ операций — уже заметная вычислительная нагрузка (секунды-десятки секунд на один шаг), и это для сети, которая по меркам современного глубокого обучения считается крошечной.

Ответ: увеличение числа параметров в $100$ раз (с $100$ до $10\,000$) увеличило стоимость одного шага метода Ньютона не в $100$, а в $100^3 = 10^6$ раз — это и есть суть кубической зависимости: она растёт настолько быстро, что даже умеренный рост модели делает метод практически неприменимым.

Пример 2 (средний, масштаб современных моделей). Оценить стоимость и объём памяти одного шага метода Ньютона для модели с $n = 10^8$ параметров (сравнимо с некоторыми компактными языковыми моделями) и объяснить, почему это физически неосуществимо.

Хранение гессиана: $O(n^2) = (10^8)^2 = 10^{16}$ чисел. При хранении в формате float32 (4 байта на число) это $4\times10^{16}$ байт $= 4\times10^7$ терабайт — на много порядков больше памяти любого существующего суперкомпьютера.

Стоимость обращения: $O(n^3) = 10^{24}$ операций — при производительности современного суперкомпьютера порядка $10^{18}$ операций в секунду (одна экзафлопс-система) это заняло бы порядка $10^6$ секунд, то есть около 11 дней, причём только на один шаг оптимизации, а обучение требует множества шагов.

Ответ: уже при ста миллионах параметров — скромной величине по меркам современных языковых моделей, у которых параметров миллиарды, — прямое применение метода Ньютона невозможно ни по памяти, ни по времени вычислений ни на каком существующем оборудовании. Это не гипербола ради драматического эффекта, а прямое следствие арифметики $O(n^2)$ и $O(n^3)$: именно эта арифметика и есть главная, самая практическая причина, по которой SGD и Adam обходятся приближённой информацией только первого порядка.

Пример 3 (сложный, ML — где метод Ньютона всё же используется и что происходит на невыпуклой функции). Логистическая регрессия с $n=50$ признаками обучается решателем newton-cg в scikit-learn. Функция потерь логистической регрессии (кросс-энтропия) выпукла (это доказывалось в уроке 278), поэтому её гессиан всегда положительно полуопределён, и метод Ньютона работает надёжно. Показать на числах, почему то же самое рассуждение не спасает метод Ньютона при обучении многослойной нейросети, и что конкретно происходит с шагом, если гессиан индефинитен (пример из первого раздела, функция $w_1^2-w_2^2$, повторим вывод содержательно).

Для логистической регрессии при $n=50$ стоимость шага $O(n^3) = 50^3 = 125\,000$ операций — тривиально дёшево, а выпуклость гарантирует, что гессиан положительно определён в каждой точке (это прямое следствие доказанной в уроке 278 теоремы: у выпуклой функции гессиан положительно полуопределён всюду), поэтому шаг метода Ньютона всегда указывает в сторону убывания функции потерь. Именно из-за сочетания «небольшая размерность» + «гарантированная выпуклость» метод Ньютона (через newton-cg) — рабочий, часто рекомендуемый выбор для логистической регрессии на некрупных и средних датасетах.

У функции потерь многослойной нейросети, в отличие от логистической регрессии, нет теоремы о выпуклости — наоборот, как обсуждалось в уроке 213 про экстремумы функций нескольких переменных, в высокоразмерных пространствах подавляющее большинство критических точек — это седловые точки, где гессиан индефинитен (имеет и положительные, и отрицательные собственные значения), а не настоящие минимумы. В таких точках, как ты видел на примере $L(w_1,w_2)=w_1^2-w_2^2$ выше, шаг метода Ньютона перестаёт быть надёжным направлением спуска: он сходится к стационарной точке квадратичной модели, но эта точка может оказаться седлом, а не минимумом, и движение к ней вдоль «неправильного» собственного направления гессиана фактически увеличивает функцию потерь.

Ответ: метод Ньютона надёжен там, где сочетаются небольшая размерность и выпуклость (классическая логистическая регрессия — пример 3), и ненадёжен там, где выпуклости нет, а параметров миллионы (нейросети) — по двум независимым причинам сразу: вычислительной ($O(n^3)$) и математической (индефинитный гессиан на седловых точках). Это и есть тот самый честный компромисс, вокруг которого построен весь урок: SGD и Adam жертвуют точностью локальной модели ради вычислительной посильности и заодно избегают части проблем с индефинитным гессианом, поскольку вообще его не используют.

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

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

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

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

Задание 1: Для функции $L(w) = (w-5)^2 + 2$ найти $L'(w)$ и $L''(w)$, а затем сделать один шаг метода Ньютона из точки $w_0 = 0$.

Задание 2: Для функции $L(w) = 3w^2 - 12w + 7$ найти минимум методом Ньютона из любой стартовой точки $w_0$ и объяснить, почему ответ не зависит от выбора $w_0$.

Задание 3: Записать формулу шага метода Ньютона для многомерного случая и объяснить, чем она отличается от формулы шага градиентного спуска.

Задание 4: Для функции $L(w_1,w_2) = 2w_1^2 + 5w_2^2$ вычислить гессиан и его обратную матрицу.

Задание 5: Используя гессиан из задания 4, сделать один шаг метода Ньютона из точки $(1,1)$ для функции $L(w_1,w_2)=2w_1^2+5w_2^2$.

Задание 6: Объяснить, почему для функции $L(w) = w^2$ метод Ньютона сходится за один шаг из любой точки, а градиентный спуск с $\alpha=0{,}1$ — нет.

Задание 7: Для функции $L(w) = w^2 - 6w + 10$ выполнить 2 шага метода Ньютона из $w_0=10$ и объяснить результат.

Задание 8: Дана диагональная матрица гессиана $H = \begin{pmatrix}8&0\\0&2\end{pmatrix}$ и градиент $\nabla L = (16, 4)$ в точке $(2,2)$. Найти шаг метода Ньютона.

Задание 9: Объяснить своими словами, почему формулу шага метода Ньютона нельзя применить, если гессиан в текущей точке равен нулю.

Задание 10: Функция потерь логистической регрессии с $n=20$ признаками обучается методом Ньютона. Оценить порядок числа операций на один шаг ($O(n^3)$) и сравнить с $n=2000$.

Средние задания (11–20)

Задание 11: Для функции $L(w) = e^{w} - w$ вывести формулу одного шага метода Ньютона в общем виде (в терминах $w_k$) и вычислить $w_1$, стартуя из $w_0=2$.

Задание 12: Продолжить вычисления из задания 11 ещё на 2 шага ($w_2$, $w_3$) и проверить, выполняется ли примерное правило квадратичной сходимости $e_{k+1}\approx C\,e_k^2$.

Задание 13: Для квадратичной формы $L(w_1,w_2)=w_1^2+9w_2^2-2w_1-18w_2$ найти минимум методом Ньютона из точки $(0,0)$ за один шаг.

Задание 14: Функция $L(w_1,w_2)=w_1^2-w_2^2$ имеет седловую точку в $(0,0)$. Стартуя из $(0{,}2;\,0{,}2)$, сделать один шаг метода Ньютона и объяснить результат.

Задание 15: Оценить объём памяти в гигабайтах, необходимый для хранения полного гессиана (в float32) модели с $n=1\,000\,000$ параметров.

Задание 16: Функция потерь $L(w)=\ln(1+w^2)$. Показать, что в точке $w_0=1$ гессиан (вторая производная) равен нулю, и объяснить, что это означает для шага метода Ньютона.

Задание 17: Для функции $L(w_1,w_2)=10w_1^2+0{,}1w_2^2$ вычислить шаг метода Ньютона из точки $(1,1)$ и явно показать, как метод компенсирует разную кривизну по осям.

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

Задание 19 (ML): Оценить, во сколько раз увеличится стоимость одного шага метода Ньютона ($O(n^3)$), если число признаков в логистической регрессии выросло с $n=200$ до $n=1000$ (в 5 раз).

Задание 20 (ML): Объяснить, почему седловые точки (урок 213) представляют особую опасность именно для метода Ньютона, а не только для градиентного спуска, используя рассуждение о собственных значениях гессиана.

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

Задание 21: Вывести формулу шага метода Ньютона из квадратичной аппроксимации функции потерь по ряду Тейлора (повторить вывод из первого раздела своими словами и выкладками).

Задание 22: Для функции $L(w)=w^4$ показать, что классическая теорема о квадратичной сходимости неприменима в точке минимума $w^*=0$, и объяснить, почему.

Задание 23: Для функции $L(w_1,w_2,w_3) = w_1^2+2w_2^2+3w_3^2-2w_1-8w_2-18w_3$ найти минимум методом Ньютона из $(0,0,0)$ за один шаг.

Задание 24: Оценить, во сколько раз метод Ньютона (5 итераций до точности $10^{-6}$ по грубой оценке из теории урока) быстрее градиентного спуска с линейной сходимостью $e_{k+1}=0{,}9\,e_k$ (медленно сходящийся случай) до той же точности $10^{-6}$, если стартовая ошибка $e_0=1$.

Задание 25 (ML): Объяснить, почему стоимость $O(n^3)$ метода Ньютона сравнивают именно со стоимостью $O(n)$ одного шага SGD, и оценить отношение этих стоимостей при $n=10^6$.

Задание 26: Для функции $L(w_1,w_2)=4w_1^2-w_2^2$ (седловая точка в $(0,0)$) сделать шаг метода Ньютона из точки $(1,1)$ и явно указать, в каком направлении шаг увеличивает функцию потерь.

Задание 27: Сформулировать своими словами, почему методы вроде BFGS (квазиньютоновские методы, тема следующего урока) вообще существуют, опираясь на две проблемы метода Ньютона, разобранные в этом уроке.

Задание 28 (ML): Функция потерь логистической регрессии на датасете из $n=500$ признаков имеет положительно определённый гессиан во всех точках (следствие выпуклости кросс-энтропии). Объяснить, почему для этой задачи метод Ньютона предпочтительнее SGD, а не наоборот.

Задание 29 (ML): На числовом примере объяснить, почему сравнение «метод Ньютона всегда лучше градиентного спуска, потому что сходится быстрее» — некорректное упрощение, если не учитывать стоимость одного шага, а не только их количество.

Задание 30 (ML): Обобщить весь урок: сформулировать, при каком сочетании условий (размер модели, выпуклость) метод Ньютона стоит использовать напрямую, а при каком — нет, и что выбирают вместо него в каждом случае.

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

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

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

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

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

Недооценивать стоимость обращения гессиана, полагая, что раз гессиан «всего лишь» матрица вторых производных, её обращение — такая же дешёвая операция, как вычисление градиента, — на самом деле обращение матрицы размера $n\times n$ стоит $O(n^3)$, что принципиально дороже вычисления градиента, требующего $O(n)$ операций.

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

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

Метод Ньютона использует не только градиент, но и вторую производную (гессиан) — информацию о кривизне функции потерь, а не только о направлении её роста.

Формула шага: $w_{k+1} = w_k - H(w_k)^{-1}\nabla L(w_k)$ — в отличие от градиентного спуска $w_{k+1}=w_k-\eta\nabla L(w_k)$, здесь скалярная скорость обучения заменена матрицей обратного гессиана.

Формула выводится из минимизации квадратичной аппроксимации функции потерь по ряду Тейлора, оборванному на втором члене, — тот же аппарат, что разбирался в университетском уроке про формулу Тейлора (урок 193).

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

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

Главная практическая проблема — стоимость: вычисление и обращение гессиана для $n$ параметров стоит $O(n^3)$ операций и $O(n^2)$ памяти, что делает метод неприменимым напрямую для моделей с миллионами и миллиардами параметров.

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

Метод Ньютона активно используется на практике там, где обе проблемы не критичны — например, решатель newton-cg в scikit-learn для обучения логистической регрессии (выпуклая функция потерь, умеренная размерность).

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

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

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

Этот урок напрямую опирается на формулу Тейлора (университетский урок 193): формула шага метода Ньютона — это не отдельно придуманная конструкция, а прямое следствие минимизации квадратичной аппроксимации функции по ряду Тейлора, оборванному на втором члене, — то же самое разложение через градиент и гессиан, которое уже выводилось и доказывалось там.

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

Урок опирается на градиентный спуск и стохастический градиентный спуск (уроки 285–286) как на точку отсчёта для сравнения: все числовые примеры этого урока явно сопоставляли скорость сходимости метода Ньютона с уже знакомыми методами первого порядка.

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

Урок открывает дорогу к квазиньютоновским методам (следующий урок 288) — прямому практическому ответу на две проблемы, разобранные здесь: как получить часть преимуществ учёта кривизны функции, не оплачивая полную стоимость $O(n^3)$ точного гессиана.

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

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

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

Квадратичная скорость сходимости метода Ньютона означает, что теоретически, при идеальных условиях (гладкая функция, стартовая точка достаточно близко к минимуму), число верных десятичных знаков в приближении может удвоиться буквально за один шаг — на практике это означает, что для многих задач хватает 4–6 итераций там, где градиентному спуску нужны тысячи.

Решатель newton-cg в scikit-learn не вычисляет и не обращает гессиан целиком напрямую — вместо этого он приближённо решает линейную систему $H\Delta w=\nabla L$ методом сопряжённых градиентов, что дешевле полного обращения матрицы, но всё равно опирается на ту же самую идею шага метода Ньютона, разобранную в этом уроке.

Лайфхаки

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

Используй метод Ньютона (или решатели вроде newton-cg) как «эталон» скорости сходимости на небольших выпуклых задачах — если у тебя есть логистическая регрессия с разумным числом признаков, попробуй обучить её и методом Ньютона, и SGD, и сравни не только скорость, но и итоговое качество: это отличная практическая интуиция для дальнейшей работы с оптимизацией.

Помни правило больших пальцев: если число параметров модели измеряется тысячами и больше — метод Ньютона в чистом виде, скорее всего, уже неприменим по стоимости; если сотнями и меньше — стоит хотя бы попробовать.

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

Когда встретишь в документации библиотеки термин «second-order method» или «second-order optimizer», сразу задавай себе вопрос из этого урока: как именно метод обходит проблему $O(n^3)$ — вычисляет ли он гессиан целиком (тогда применим только для небольших моделей), приближает ли его (квазиньютоновский метод), или использует только его часть (диагональ, малоранговое приближение)?

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

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