В этом разделе мы сконцентрируемся сначала на методах, которые используют информацию о гессиане функции, а затем рассмотрим, как, сохраняя высокоуровневую идею метода Ньютона, обойтись без гессиана.
Метод Ньютона
Итак, наша задача – безусловная оптимизация гладкой функции
Как и при оптимизации методом градиентного спуска, мы будем искать направление уменьшения функционала. Но в этот раз мы будем использовать не линейное приближение, а квадратичное:
Формула Тейлора говорит нам брать . Приравняв к нулю градиент этой квадратичной аппроксимации, мы получаем направление спуска для метода Ньютона:
Обозначим . В таком случае мы можем записать итеративный алгоритм спуска:
В литературе методом Ньютона называется такой метод при , при другом размере шаге этот метод называют дэмпированным (damped) методом Ньютона.
Обсудим, в чем главная особенность метода Ньютона и в чем заключается выигрыш по сравнению с классическим градиентным спуском. Таких особенностей две.
Скорость сходимости метода Ньютона
Первая связана со скоростью его сходимости. А именно – в окрестности решения он сходится квадратично.
Теорема. Пусть функция имеет достаточно гладкий гессиан и сильно выпукла в точке оптимума . Тогда , что для всякого для метода Ньютона с верно для константы зависящей только от .
Немного поясним терминологию. Под достаточно гладким гессианом мы подразумеваем то, что он должен быть липшицевым и дифференцируемым, из чего следует, что
а также
где – результат подстановки в качестве двух первых аргументов в трилинейную форму . Под сильной выпуклостью мы подразумеваем здесь -сильную выпуклость, которую здесь строго определять излишне (подробнее см. в этой статье), но из которой следует, что гессиан отделён от нуля:
Разложим градиент по формуле Тейлора в точке с остаточным членом в форме Лагранжа:
Умножим с обеих сторон на обратный гессиан и получаем:
Воспользуемся формулой шага , тогда в левой части равенства у нас . Посчитаем норму и воспользуемся гладкостью:
Теперь воспользуемся сильной выпуклостью в точке оптимума. Поскольку мы предполагаем, что точка старта достаточно близко к точке оптимума, то по гладкости можем считать, что в точке у нас есть хотя бы -сильная выпуклость. Тогда получаем:
Метод Ньютона и плохо обусловленные задачи
Второе приятное свойство заключается в устойчивости метода Ньютона к плохой обусловленности задачи (в отличие от метода градиентного спуска). Разберёмся, что это значит. Когда мы говорим о плохой обусловленности задачи, мы имеем в виду, что гессиан в точке оптимума плохо обусловлен, то есть отношение максимального и минимального собственных чисел является большим числом. Геометрически это значит, что линии уровня функции вблизи оптимума похожи на очень вытянутые эллипсоиды; мы уже обсуждали, что в такой ситуации градиентный спуск может работать медленно. А как справится метод Ньютона? Оказывается, намного лучше. И связано это с его инвариантностью к линейным преобразованиям.
А именно, рассмотрим функцию для некоторой невырожденной матрицы . Обозначим . Посмотрим, как связаны градиент и гессиан новой функции с градиентом и гессианом старой. Воспользуемся производной сложной функции:
Рассмотрим теперь траекторию метода Ньютона, запущенного из точки для поиска минимума функции , и траекторию метода Ньютона, запущенного для поиска минимума функции . Если , то для всех будет верно , то есть траектории получаются одна из другой при помощи этого линейного преобразования, другими словами, траектории исходной и новой функции подобны.
Докажем по индукции. Для это дано по условию. Теперь докажем шаг индукции:
По предположению индукции , тогда получаем:
Вернёмся теперь к плохо обусловленной задаче минимизации функции . Рассмотрим линейное преобразование и функцию . Тогда для функции число обусловленности гессиана в точке оптимума равно в точность единице (проверьте это!), а траектории для этой новой, хорошо обусловленной функции, и старой, плохо обусловленной, подобны. В частности, метод Ньютона не будет, как градиентный спуск, долго метаться где-то на задворках вытянутой эллиптической «ямки» вокруг оптимума, а быстро ринется к центру.
Можно сказать, что метод Ньютона правильно улавливает кривизну линий уровня функции и это позволяет ему быстрее сходиться к оптимуму. Эту идею стоит запомнить, она появляется в некоторых вдохновлённых методами второго порядка модификациях SGD.
Также еще можно заметить, что свойства, которые мы требуем от функции в теореме о квадратичной сходимости, вообще говоря, не сохраняются при линейных преобразованиях: могут поменяться константы липшицевости и сильной выпуклости. Это простое замечание побудило исследователей ввести класс самосогласованных функций, более широкий и линейно инвариантный, для которого метод Ньютона также сходится. Подробнее об этом можно узнать в разделе 9.6 книги S. Boyd & L. Vandenberghe, Convex Optimization.
Слабости метода Ньютона
От хорошего переходим к плохому: к слабостям метода Ньютона. Во-первых, мы имеем квадратичную скорость сходимости только в окрестности оптимума. А если мы стартуем из произвольно удалённой точки, то нам, как и в случае градиентного спуска, требуется подбор шага при помощи линейного поиска (что нам вряд ли по карману). Если подбирать шаг не хочется, можно прибегнуть к интересному теоретическому методу получения гарантий на глобальную сходимость – добавлению кубической регуляризации.
В случае кубической регуляризации мы хотим обеспечить не просто аппроксимацию, но и оценку сверху:
По сути, мы задаем кубическую модель, которую мы можем уже оптимзировать по . Тогда мы получаем следующую итеративную процедуру проксимального вида:
В таком случае можно использовать, например, постоянный размер шага и иметь гарантии на сходимость. Этот метод в последнее время стал пользоваться популярностью в теоретических исследованиях, в том числе в распределенной оптимизации.
Также можно задаться простым вопросом: а можем ли мы пользоваться подобным разложением с регуляризацией для большего числа членов разложения по формуле Тейлора? На самом деле да, только коэффициент нужно подбирать чуть более специфично. Такие методы называются тензорными методами.
Другая проблема кроется в формуле пересчета следующей итерации: вычисление и обращение гессиана. Конечно, вместо обращения гессиана можно честно решать систему линейных уравнений, но асимптотика остается прежней: , а от затрат памяти на хранение матрицы вообще некуда деться. А это значит, что, например, решать линейную регрессию с ~10000 признаками методом Ньютона попросту невозможно.
Есть и третья, малозаметная проблема: дословно метод Ньютона не работает для невыпуклых задач, поскольку не будет положительно опредленной и перестанет быть направлением спуска. Для решения этой проблемы можно немного «подпортить» нашу аппроксимацию и рассмотреть матрицу вида , такую что станет положительно определенной, и уже её подставлять в нашу квадратичную модель. Идея подмены гессиана на что-то более подходящее – это главная идея квазиньютоновских методов, обсуждаемых далее.
Итак, общие выводы:
- Метод Ньютона – теоретически оптимальный метод, который автоматически улавливает кривизну функции в окрестности оптимума.
- Для размерности он уже не является эффективным, поскольку требует вычисления и хранения гессиана, а также решения системы линейных уравнений с его участием (что может быть в общем случае очень дорого).
Квазиньютоновские методы
Чтобы придумать, как бороться с проблемами метода Ньютона, нужно посмотреть на него с другой стороны, а для этого мы обратимся ненадолго к решению задачи нахождения нуля векторной функции.
Метод касательной
Итак, рассмотрим совершенно новую задачу. Пусть дана функция и нужно найти её ноль, то есть такое , что . Связь с оптимизацией (по крайней мере в выпуклом случае) довольно проста: если взять , то корень уравнения и будет точкой оптимума.
Сначала рассмотрим одномерный случай . Как найти ноль функции с помощью итеративной процедуры? Логично поступить следующим образом: проводим касательную к графику функции и находим точку , в которой линейная аппроксимация обнуляется:
откуда получаем формулу пересчета
Известно, что этот метод обладает квадратичной скоростью сходимости в одномерном мире, что очень перекликается с методом Ньютона для оптимизации – и не просто так.
Если рассмотреть многомерный случай, то вычисление производной заменяется на вычисление якобиана векторнозначной функции . В случае наш якобиан становится гессианом и получаем в точности обычный метод Ньютона для оптимизации:
Метод секущей и общая схема квазиньютоновских методов
Пусть мы хотим найти такую точку , что . В одномерном случае мы можем подменить вычисление вычислением её приближения . Откуда получаем формулу пересчета:
Графически, этот метод выглядит следующим образом:
Скорость сходимости этого метода несколько ниже, чем у метода Ньютона (линейная, а не квадратичная), но зато мы теперь не должны вычислять производную! В текущем виде, используя просто подмену градиента на его конечно-разностную аппроксимацию, не очевидно, как обобщить этот метод на произвольную размерность. Но, если посмотреть на название метода и на картинку, как он работает, мы видим, что мы по сути проводим через два предыдущих приближения секущую, а затем выбираем ноль этой секущей в качестве следующей точки. В многомерном случае мы можем выписать соответствующее ей уравнение , где – матрица размера , которая должна удовлетворять так называемому уравнению секущей (secant equation):
Теперь, чтобы выбрать следующую точку, нужно найти ноль секущей, то есть
А теперь рассмотрим и добавим в итеративную схему выше размер шага. Тогда мы получаем общую итеративную схему квазиньютоновских методов:
При этом необходимо выбирать такие , чтобы они
(а) были симметричными и положительно определенными и
(б) удовлетворяли уравнению секущей
Первое требование восходит к двум соображениям. Первое – должно приближать гессиан, а он в идеале в окрестности точки минимума как раз является симметричным и положительно определенным. Второе соображение проще: в противном случае попросту не будет направлением спуска. Несмотря на эти два свойства, выбор по прежнему остается достаточно широким, откуда возникает большое разнообразие квазиньютоновских методов. Мы рассмотрим один классический и широко известный метод BFGS (Broyden, Fletcher, Goldfarb, Shanno).
BFGS
Сначала заметим, что в самом алгоритме в первую очередь используется обратная матрица к , которую мы обозначим . Тогда выбирать – это тоже самое, что выбирать . Введем еще два стандартных обозначения, чтобы можно было проще записывать все последующие формулы: и . В их терминах уравнение секущей для выглядит максимально просто: .
Теперь введем некоторое искусственное требование, которое гарантирует единственность – выберем ближайшую подходящую матрицу к , удовлетворяющую описанным выше условиям:
Вообще говоря, при выборе разных норм мы будем получать разные квазиньютоновские алгоритмы. Рассмотрим один достаточно общий класс норм (аналог взвешенных норм в матричном мире):
где – это Фробениусова норма
а – некоторая симметричная и положительно определенная матрица весов, которую мы выберем таким образом, что она будет сама по себе удовлетворять уравнению секущей .
Сразу уточним, что матрица весов в таком случае меняется на каждой итерации и, по сути, на каждой итерации мы имеем разные задачи оптимизации, само же предположение задает дополнительную похожесть на обратный гессиан, поскольку можно взять в качестве весов усредненый гессиан
Решив описанную выше оптимизационную задачу, мы получаем матрицу , не зависящую явным образом от матрицы весов:
Эта формула как раз является ключевой в алгоритме BFGS. Чтобы заметить одно крайне важное свойство этой формулы, раскроем скобки:
Отсюда мы видим, что нам в этой формуле достаточно умножать матрицу на вектор и складывать матрицы, что можно делать за операций! То есть мы победили один из самых страшных минусов метода Ньютона. Воспользовавшись тем, что $ y_k^\top H_k y_k $ и – числа, перепишем формулу в более computational friendly стиле:
Общие выводы:
- Итерации BFGS вычислительно проще итераций метода Ньютона и не требуют вычисления гессиана;
- По скорости сходимости BFGS уступает методу Ньютона, но все равно является достаточно быстрым;
- По прежнему требуется памяти, что по-прежнему вызывает проблемы при большой размерности ().
- Время выполнения итерации гораздо лучше, чем метода Ньютона, но всё ещё оставляет желать лучшего.
Казалось бы, избавиться от нельзя принципиально, ведь нужно как-то взаимодействовать с матрицей размера , а она не факт что разреженная. Но и в этом случае можно добиться улучшения до линейной сложности (как у градиентных методов!).
L-BFGS
При взаимодействии с матрицами существует два основных способа хранить их дешевле, чем «по-честному». Первый способ – пользоваться разреженностью матрицы, а второй – низкоранговыми разложениями или чем-то близким. Поскольку сейчас мы не хотим добавлять предположений на задачу, которую мы решаем, то единственный выход – это пользоваться структурой , возникающей в BFGS.
Если внимательно взглянуть на формулы обновления, то их можно переписать в следующем виде:
Для того, чтобы перейти от к , можно хранить не матрицу , а набор пар из k пар и начальное приближение (например, для некоторого ), чтобы «восстановить» . Пользуясь такой структурой, мы можем хранить матрицу при помощи лишь чисел, а не . К сожалению, такая структура имеет довольно простую проблему: при затраты памяти становятся только выше.
Возникает простая идея – а давайте хранить только последние обновлений! Таким образом, мы получаем алгоритм L-BFGS, который имеет уже линейные затраты памяти и, что немаловажно, такие же линейные затраты на итерацию, ведь умножение матриц и на вектор может осуществляться за линейное время.
Общие выводы:
- L-BFGS обладает линеной сложностью итерации, линейными требованиями по дополнительной памяти и к тому же требует вычислять только градиенты!
- Производительность сильно зависит от константы , отвечающей за точность аппроксимации гессиана;
- Как и все методы из этого раздела, требует точного, а не стохастического вычисления градиентов.
Практические аспекты
Из всех перечисленных в этом разделе методов важнее всего отметить L-BFGS как самый практичный. Он реализован в любой* библиотеке, которая имеет дело с оптимизацией чего-либо и может быть эффективным, если удаётся вычислить градиенты (и значения функций для линейного поиска размера шага). К сожалению, это получается не всегда: при больших размерах датасета вычисление честного градиента и значения для функционалов вида суммы
не представляется возможным за разумное время. В таком случае мы вынуждены вернуться в мир стохастического градиентного спуска. Общая идея более тонкого учёта геометрии линий уровня функции потерь, в чём-то напоминающая происходящее в методе Ньютона, находит применение и в ряде вариаций SGD, но, конечно, порождает совершенно другие методы.
Что же касается самого метода Ньютона, его можно несколько оптимизировать, если смириться с тем, что всё вычисляется неточно. Во-первых, обратную матрицу к гессиану матрицу на самом деле не нужно ни хранить, ни даже вычислять. Давайте разберёмся, почему. Умножить на вектор – это то же самое, что решить систему с левой частью и правой частью , а для решения систем уравнений существуют эффективные итеративные методы, не меняющие левой части системы, а требующие лишь уметь умножать её на разные векторы. При этом умножать гессиан на вектор можно при помощи автоматического дифференцирования. Кроме того, можно на кажом шаге неточно решать систему, получая таким образом неточный метод Ньютона. Теория предписывает решать систему все точнее с ростом номера итерации, но на практике нередко используют фиксированное и небольшое число шагов итеративных методов решения систем линейных уравнений.