Стохастические методы Ньютона

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM GPT-5.3-mini и проверена участником ~~Dovlat Demin~~

Стохастические методы Ньютона (Stochastic Newton Methods) — семейство методов второго порядка для решения задач оптимизации, сочетающих идеи метода Ньютона и стохастической оптимизации. В отличие от классического метода Ньютона, использующего точные значения градиента и матрицы Гессе, стохастические методы строят их приближённые оценки по случайно выбранным наблюдениям или мини-батчам. Это позволяет существенно уменьшить вычислительные затраты и применять методы второго порядка при решении крупномасштабных задач машинного обучения.

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

Содержание

1 Постановка задачи
2 Классический метод Ньютона
3 Ограничения классического метода Ньютона
4 От метода Ньютона к стохастическим методам
5 Связь с квазиньютоновскими методами
6 Теоретические свойства
7 Применение в машинном обучении
8 Сравнение с другими методами оптимизации
9 Преимущества и недостатки
10 Современные направления исследований
11 См. также
12 Литература

Постановка задачи

Рассмотрим задачу безусловной минимизации

$\min_{x\in\mathbb{R}^{d}} f(x),$

где функция $f(x)$ обычно имеет структуру конечной суммы

$f(x)=\frac1n\sum_{i=1}^{n}f_i(x),$

где каждое слагаемое соответствует отдельному объекту обучающей выборки.

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

Во многих современных приложениях число объектов $n$ достигает миллионов, а размерность пространства параметров $d$ — десятков или сотен миллионов. В таких условиях основная трудность заключается не столько в вычислении значения функции, сколько в эффективном использовании информации о её производных.

Классический метод Ньютона

Метод Ньютона использует локальное квадратичное приближение функции

$f(x_k+p)\approx f(x_k)+\nabla f(x_k)^Tp+\frac12p^TH(x_k)p.$

$H(x_k)=\nabla^2f(x_k)$

— матрица Гессе.

Минимизация квадратичной модели приводит к классическому ньютоновскому шагу

$H(x_k)p_k=-\nabla f(x_k),$

или, эквивалентно,

$x_{k+1}=x_k-H(x_k)^{-1}\nabla f(x_k).$

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

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

Ограничения классического метода Ньютона

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

Главная причина заключается в высокой стоимости работы с матрицей Гессе.

Для задачи размерности $d$

вычисление полной матрицы Гессе требует порядка $O(nd^2)$ операций;
хранение требует $O(d^2)$ памяти;
обращение матрицы или решение линейной системы методом разложения Холецкого требует порядка $O(d^3)$ операций.

Даже при умеренной размерности эти величины становятся недопустимо большими.

Например, если модель содержит

$d=10^6$

параметров, то полная матрица Гессе содержит

$10^{12}$

элементов. Для хранения такой матрицы в формате двойной точности требуется около 8 ТБ памяти, что значительно превышает возможности большинства вычислительных систем.

Кроме вычислительных затрат существуют и другие проблемы.

Во-первых, вычисление Гессиана требует вторых производных, которые зачастую значительно дороже вычисления градиента.

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

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

От метода Ньютона к стохастическим методам

Аналогичная проблема ранее возникла при использовании градиентного спуска. Вычисление полного градиента

$\nabla f(x)=\frac1n\sum_{i=1}^{n}\nabla f_i(x)$

оказалось слишком дорогим для больших наборов данных. Решением стало использование случайных выборок объектов, что привело к появлению стохастического градиентного спуска (SGD), в котором вместо полного градиента используется его несмещённая оценка.

Естественным развитием этой идеи стало распространение стохастического подхода на методы второго порядка. Если градиент можно оценивать по мини-батчу, то аналогичным образом можно приближать и матрицу Гессе либо непосредственно строить приближение её обратной.

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

Hessian-Free Newton

Метод Hessian-Free Newton (HF Newton) предназначен для решения задач очень большой размерности, в которых построение или хранение матрицы Гессе невозможно. Основная идея состоит в том, что ньютоновское направление вычисляется без явного формирования Гессиана. Вместо этого используются только произведения матрицы Гессе на вектор

$H(x)v,$

которые вычисляются методом автоматического дифференцирования (алгоритм Пирлмуттера).

Полученная линейная система

$H(x_k)p_k=-g_k$

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

Для невыпуклых задач вместо истинного Гессиана часто используется обобщённая матрица Гаусса—Ньютона (Generalized Gauss–Newton Matrix), которая является положительно полуопределённой и обеспечивает более устойчивую работу алгоритма.

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

Regularized Stochastic Newton

Во многих задачах оценки матрицы Гессе оказываются плохо обусловленными. Для повышения устойчивости используется регуляризация

$(\hat H_k+\lambda I)p_k=-\hat g_k.$

Параметр $\lambda$ ограничивает влияние малых собственных значений и предотвращает чрезмерно большие ньютоновские шаги.

Во многих современных алгоритмах величина регуляризации изменяется автоматически в зависимости от качества локальной квадратичной модели.

Trust-Region Newton

Методы доверительных областей (Trust-Region Methods) заменяют задачу минимизации квадратичной модели ограниченной задачей

$\min_p \; m_k(p) = g_k^Tp+ \frac12p^TH_kp, \qquad \|p\|\le\Delta_k,$

где $\Delta_k$ — радиус доверительной области.

Если квадратичная модель хорошо описывает функцию потерь, радиус увеличивается, иначе уменьшается.

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

Cubic Regularization

Методы с кубической регуляризацией (Cubic Regularization) используют более точную локальную модель

$m_k(p)= g_k^Tp+ \frac12p^TH_kp+ \frac{\sigma}{3}\|p\|^3.$

Кубический член ограничивает слишком большие шаги и обеспечивает существование решения даже при неопределённой матрице Гессе.

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

Другие современные методы

В последние годы предложено большое число алгоритмов, сочетающих различные способы приближения Гессиана.

Наиболее известными являются

Stochastic Trust Region;
Adaptive Newton;
Incremental Newton;
Stochastic Quasi-Newton;
AdaNewton;
Shampoo;
K-FAC (Kronecker-Factored Approximate Curvature);
Sophia и Sophia-G;
Sketchy Newton;
Distributed Newton.

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

Связь с квазиньютоновскими методами

Квазиньютоновские методы занимают промежуточное положение между градиентными и ньютоновскими алгоритмами.

В отличие от стохастических методов Ньютона, они не вычисляют вторые производные напрямую. Вместо этого строится последовательность матриц

$B_k\approx H(x_k)$

или

$B_k^{-1}\approx H(x_k)^{-1},$

используя лишь информацию о предыдущих итерациях.

Наиболее известными представителями являются

Во всех этих алгоритмах приближение Гессиана обновляется по векторам

$s_k=x_{k+1}-x_k,$

$y_k=\nabla f(x_{k+1})-\nabla f(x_k).$

Стохастические варианты (Online BFGS, Stochastic BFGS, RES и другие) используют стохастические оценки градиента вместо полного градиента.

По сравнению с классическими стохастическими методами Ньютона квазиньютоновские алгоритмы обладают рядом преимуществ:

отсутствует необходимость вычисления вторых производных;
значительно меньшие требования к памяти;
хорошая масштабируемость;
высокая эффективность на задачах средней размерности.

Однако построенное приближение кривизны обычно менее точно, чем непосредственная оценка Гессиана.

Теоретические свойства

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

Для выпуклых задач доказана сходимость к глобальному минимуму.

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

Если

функция дважды непрерывно дифференцируема;
Гессиан в окрестности решения положительно определён;
ошибки аппроксимации достаточно малы,

то многие алгоритмы обладают локальной сверхлинейной или квадратичной скоростью сходимости.

Для методов Newton Sketch и Subsampled Newton получены оценки вычислительной сложности, показывающие, что число операций может быть существенно меньше, чем у классического метода Ньютона, при сохранении практически той же скорости локальной сходимости.

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

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

```

Применение в машинном обучении

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

Логистическая регрессия

Одной из классических областей применения является Логистическая регрессия. Для логистической функции потерь матрица Гессе положительно полуопределена, а её структура позволяет эффективно вычислять произведения вида $Hv$ . В результате методы Newton, Subsampled Newton и Newton Sketch часто превосходят градиентные методы по числу итераций, особенно на плохо обусловленных задачах.

Обучение глубоких нейронных сетей

При обучении глубоких нейронных сетей функции потерь являются невыпуклыми, а число параметров может достигать миллиардов. В таких условиях вычисление полного Гессиана невозможно, однако методы Hessian-Free Newton, K-FAC, Shampoo и Sophia используют различные приближения информации о кривизне.

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

Крупномасштабная оптимизация

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

Распределённое обучение

Во многих современных системах обучение выполняется одновременно на десятках или сотнях вычислительных узлов. Стохастические оценки Гессиана могут вычисляться независимо на различных подвыборках данных, после чего объединяться для построения общего направления поиска.

Подобный подход лежит в основе распределённых вариантов Subsampled Newton, Distributed Newton и ряда современных методов федеративного обучения.

Сравнение с другими методами оптимизации

Метод	Использование Гессиана	Стоимость одной итерации	Память	Локальная скорость сходимости	Масштабируемость	Типичные применения
SGD	Нет	Низкая	$O(d)$	Линейная	Очень высокая	Глубокое обучение
Adam	Нет	Низкая	$O(d)$	Линейная	Очень высокая	Нейронные сети
L-BFGS	Приближённо	Средняя	$O(md)$	Сверхлинейная	Высокая	Средние задачи
Hessian-Free Newton	Произведения $Hv$	Средняя–высокая	$O(d)$	Сверхлинейная	Высокая	Глубокие сети
Subsampled Newton	Приближённый	Средняя	$O(d^2)$	Близка к квадратичной	Высокая	Крупномасштабная оптимизация
Newton Sketch	Случайная проекция	Средняя	Ниже $O(d^2)$	Сверхлинейная	Высокая	Большие выпуклые задачи
Классический Newton	Полный	Очень высокая	$O(d^2)$	Квадратичная	Низкая	Задачи небольшой размерности

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

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

Преимущества и недостатки

Преимущества

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

Недостатки

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

Современные направления исследований

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

Наибольшее внимание уделяется следующим направлениям:

случайные проекции (Sketching) и методы сжатия матриц;
приближённые инверсии матрицы Гессе;
распределённые и федеративные методы второго порядка;
алгоритмы с кубической регуляризацией;
методы для невыпуклой оптимизации;
адаптивные схемы выбора размера мини-батча;
комбинирование методов второго порядка с алгоритмами глубокого обучения;
использование низкоранговых и блочных аппроксимаций Гессиана;
ускорение вычислений на GPU и специализированных ускорителях.

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

См. также

Литература

Nocedal J., Wright S. Numerical Optimization. 2nd ed. Springer, 2006.
Boyd S., Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.
Bottou L., Curtis F. E., Nocedal J. Optimization Methods for Large-Scale Machine Learning // SIAM Review. 2018. Vol. 60. No. 2. P. 223–311.
Martens J. Deep Learning via Hessian-Free Optimization // Proceedings of ICML. 2010.
Pearlmutter B. A. Fast Exact Multiplication by the Hessian // Neural Computation. 1994. Vol. 6. No. 1. P. 147–160.
Roosta-Khorasani F., Mahoney M. W. Sub-Sampled Newton Methods I: Globally Convergent Algorithms // Mathematical Programming. 2019.
Roosta-Khorasani F., Mahoney M. W. Sub-Sampled Newton Methods II: Local Convergence Rates // Mathematical Programming. 2019.
Pilanci M., Wainwright M. J. Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence // SIAM Journal on Optimization. 2017.
Byrd R. H., Chin G. M., Nocedal J., Wu Y. Sample Size Selection in Optimization Methods for Machine Learning // Mathematical Programming. 2012.
Bubeck S. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning. 2015.
Conn A. R., Gould N. I. M., Toint P. L. Trust Region Methods. SIAM, 2000.
Nesterov Y., Polyak B. Cubic Regularization of Newton Method and Its Global Performance // Mathematical Programming. 2006.
Agarwal N., Bullins B., Hazan E. Second-Order Stochastic Optimization for Machine Learning // Foundations and Trends in Machine Learning. 2017.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0»

Категории: Оптимизация | Численные методы | Математическая оптимизация | Машинное обучение

@@ Строка 28: / Строка 28: @@
 [[Метод Ньютона]] использует локальное квадратичное приближение функции
-<tex>
+<tex>f(x_k+p)\approx f(x_k)+\nabla f(x_k)^Tp+\frac12p^TH(x_k)p.</tex>
-f(x_k+p)\approx
-f(x_k)+
-\nabla f(x_k)^T p+
-\frac{1}{2}p^TH(x_k)p.
-</tex>
-где
 <tex>