Напоминания
Определение Критической точкой гладкой функции называется точка , для которой
В выпуклой оптимизации такая точка обязательно будет точкой глобального минимума. В невыпуклой оптимизации все сильно сложнее:
- Бывает много локальных минимумов
- Бывают седловые точки
Локальный минимум — это критическая точка , в которой Гессиан положительно определён. Отметим, что часто в методах глобальной оптимизации рассматривается так называемая «локальная выпуклость», для которой требуется, чтобы функция была выпуклой внутри некоторого шара радиуса с центром в точке . Критические точки, в которых гессиан не является знакоопределённым, называются седловыми.
Пример: функция имеет седловую точку . Гессиан в точке 0
Обратите внимание: во многих современных статьях про сходимость методов оптимизации первого порядка на невыпуклых функциях (пример) в качестве критерия сходимости рассматривают сходимость по норме градиента: при некотором заранее фиксированном .
В выпуклой оптимизации этот критерий сходимости эквивалентен двум другим:
- сходимости по расстоянию до оптимума в пространстве параметров: ;
- сходимости по расстоянию до оптимума по значениям функции .
В невыпуклой оптимизации всё не так просто и поиск глобального минимума является в общем случае NP-трудной задачей. Критерий даёт возможность исследовать сходимость к любой критической точке, но если речь об обучении нейронных сетях, то остается лишь надеяться, что эта критическая точка будет хорошим локальным минимумом.
Скользящее среднее в знаменателе AdaGrad. Методы RMSprop и Adam
Мотивация
В далекие 2012-2014е в мире было не так много опыта по построению хороших нейросетевых архитектур. «Канонические» методы оптимизации нейросетей RMSprop и Adam появлялись во времена, когда ещё не придумали основополагающих вещей вроде:
- Residual connection и Dense connection (статьи опубликованы в 2015/2016 соответственно, во всех экспериментах используется SGD, в статье и в ссылках не упоминаются методы Adam/RMSprop), плохо решались проблемы взрывов/затуханий градиентов и т.д.
- Batch Normalization и Layer Normalization (2015/2016 соответственно)
Также люди не умели правильно инициализировать нейросети гигантской глубины. статьи вроде 1000+ layer fully connected и 10000+ layer CNN позже. Кстати, этот цикл статей хочется особо отметить за интересную технику анализа распространения сигнала по нейронной сети.
В общем, в те времена царило архитектурное средневековье со всеми родовыми проблемами нейронных сетей:
- Взрывы градиентов;
- Затухания градиентов;
- Взрывы-затухания сигнала на прямом проходе;
- Плохие начальные инициализации, нестабильный старт обучения.
При попытках применять метод AdaGrad особо остро стояли проблемы 1 и 4. AdaGrad аккумулирует всю прошедшую историю без затухания. Если в какой-то момент возникает одна из указанных проблем, знаменатель резко возрастает и больше не выправляется.
Чтобы побороть проблемы 1-4, решили поработать над оптимизатором и сделать так, чтобы история в AdaGrad аккумулировалась с затуханием и метод оптимизации мог со временем забыть плохие точки. Самый популярный и простой в реализации метод — экспоненциальное скользящее среднее.
RMSProp
Самая первая и самая простая модификация метода AdaGrad — метод RMSprop — вместо суммы использует экспоненциальное скользящее среднее в знаменателе:
Методу RMSprop не было посвящено ни одной специализированной статьи, равно как и не было никаких доказательств его сходимости даже для выпуклых задач.
Adam
Авторы Adam в статье Adam: A Method For Stochastic Optimization вводят два новшества по сравнению с RMSprop. Во-первых, это Momentum. Во вторых — Bias correction term. Напомним, как работает этот метод.
Применяем bias correction
Сразу перепишем и в нерекурсивной форме с зависимостью только от :
Мотивация для bias correction
Авторы статьи пишут, что для правильной работы метода и должны быть несмещенными оценками и соответственно. Допустим, все — независимые одинаково распредёленные случайные величины. Это довольно сильное предположение, но иначе не получатся красивые формулы. Рассмотрим на примере :
Отсюда очевидно, что исходные и смещены на множитель , поэтому авторы Adam делят на него и . Так как при , эффект смещения сильнее всего заметен в начале итерационного процесса. Например, при классическом мы получаем смещение в 0.001 раз.
В начале обучения bias correction призван уменьшить слишком большие шаги оптимизатора.
Доказательство сходимости метода
В оригинальной статье приводится теорема с доказательством сублинейного Regret. Доказательство содержало ошибку, в новой работе 2018 года было доказано, что для любого набора гиперпараметров Adam существует выпуклая задача, на которой он не сходится. Проблемы со сходимостью, впрочем, не являются специфичными для выпуклых задач: в нейронных сетях Adam тоже может вести себя странно, и об этом мы поговорим ниже в разделе «Как сломать адаптивные методы».
Разбирать доказательство исходной статьи мы не будем, зато обратим внимание на пару неприятных фактов о различиях между «продаваемой» частью статьи и бекендом с экспериментами и доказательствами теорем.
Почему Adam стали считать лучшим методом стохастической оптимизации?
После успешного введения метода Adam в эксплуатацию в нейросети его окрестили «method of choice» в задачах стохастической оптимизации. Это было на 100% обусловлено его успехом в обучении нейронных сетей с нестабильными архитектурами.
Структура статьи выглядит следующим образом:
- Выделенный в большую красивую видную рамочку алгоритм с дефолтными настройками вроде ;
- Формулировка теоремы в разделе про доказательства;
- Эксперименты на нейросетях и выпуклых задачах.
В пункте 1 описан алгоритм, который все нынче знают, как Adam. Мало кто знает, что в доказательствах сходимости и в экспериментах на выпуклых задачах использовался немного другой алгоритм: вместо константного авторы статьи взяли . Сравним эти learning rate с AdaGrad:
| Метод | Формулы |
|---|---|
| AdaGrad | |
| Adam |
Авторы в экспериментах на логистической регрессии убили основное свойство Adam — неубывающие learning rate. Вспомним, как в разделе про вывод AdaGrad мы анализировали порядок убывания learning rate — он был . Отсюда следует, что у такого Adam learning rate убывают так же, как в AdaGrad. Словом, будьте внимательны при чтении статей: смотрите не только в описание алгоритмов, но и в их реализацию.
Настоящий Adam, который в pytorch и tensorflow реализован без множителя , в выпуклой задаче разреженной логистической регрессии обычно работает намного хуже AdaGrad. Это справедливо как для чисто линейных моделей, так и для комбинированных Wide & Deep архитектур, из-за чего в одной и той же нейросети приходится использовать разные методы оптимизации для разных параметров.
Промежуточный итог по Adam/RMSProp
Тут нужно запомнить три идеи:
- Momentum
- Скользящее среднее в learning rate
- Bias correction
На практике, часто почему-то рассматривают методы RMSprop и Adam как нечто отлитое в граните и не пытаются брать от них лучшее. Например, методу RMSprop обычно идет на пользу добавление bias correction от adam. Так что полезно помнить идеи, стоящие за методами оптимизации, и уметь их комбинировать.
Как сломать адаптивные методы со скользящим средним
Как и когда ломаются адаптивные методы
Все диагональные адаптивные методы так или иначе используют покоординатный learning rate . Методы отличаются лишь формулировкой и :
| Метод | Рекуррентные формулы | Развернутые формулы | |
|---|---|---|---|
| AdaGrad | |||
| RMSprop | |||
| Adam |
Все эти методы имеют единый вид формул FTRL, аналогичный формулам FTRL-AdaGrad:
Вспомним теоретические ограничения на :
- — выпуклый;
- .
Адаптивные методы с регуляризаторами будут удовлетворять этим условиям, если все . В этом месте и локаются методы со скользящим средним: никто не обещал, что последовательность будет монотонно неубывать. Если же
то метод может ломаться
Обратите внимание. Momentum в методе Adam никак не повлияет на справедливость наших рассуждений, поскольку в формулах для адаптивных learning rate он не используется. Адаптивные методы с такими learning rate сломаются и с momentum, и без него.
Обратите внимание. Bias correction в методе Adam уменьшает learning rate в начале обучения, заставляя метод делать меньшие шаги.
Все рекуррентные формулы из таблицы можно переписать в виде
Тогда неравенство можно записать в виде
Здесь мы можем подвести общую черту и сказать, что методы Adam и RMSprop дают , когда становится меньше предыдущей накопленной истории с точностью до некоторой константы.
А когда такое бывает? Уменьшение , как правило, означает приближение к критическим точкам. Добавление квадратичных регуляризаторов с отрицательным коэффициентом приводит к тому, что метод оптимизации штрафует за близость к критическим точкам, заставляя убегать от них. Это приводит к тому, что метод не может нормально сойтись к локальным минимумам (в выпуклых задачах — просто к минимумам, что намного более критично).
Отметим, что по разным координатам могут вести себя по-разному. Таким образом, можно получить ситуацию, когда мы поощряем близость по одним координатам и штрафуем за близость по другим.
Вывод условий поломок для конкретных методов
AdaGrad
AdaGrad невозможно сломать таким способом: для него гарантируется, что .
RMSprop
Подставим в условие , сразу сократив константный :
Adam
Чисто технически, при выведении формул можно подумать, что Adam страдает от указанных эффектов гораздо сильнее RMSprop, но на самом деле это не так.
Переобозначим из статьи про Adam как просто для общности обозначений.
Распишем неравенство для метода Adam:
В отличие от RMSprop, у нас появился дополнительный множитель . С одной стороны, можно подумать, что метод строго хуже. Однако, этот множитель сильно больше нуля только во время первых шагов оптимизации, тогда как рассматриваемая нами проблема играет роль только на поздних стадиях оптимизации при приближении к критическим точкам. А к тому моменту, этот множитель будет практически равен единице и мы получим формулы выше от RMSprop.
Поэтому, на самом деле, методы в одинаковой степени страдают от этих эффектов, но bias correction добавляет стабильности в начале.
Интерпретации
Избегание локальных минимумов или седловых точек
Если представить, что нейросеть — очень плохая и жутко невыпуклая задача, то можно рассматривать подобное поведение как «защиту» от промежуточных плохих критических точек, позволяющую нам «убегать» от них.
Данная интерпретация, к сожалению, имеет множество недостатков:
- Никто не обещал, что новая критическая точка будет лучше старой и что мы, прыгая таким образом, будем улучшать качество модели.
- Не каждый локальный минимум плохой. Если текущая критическая точка — хороший локальный минимум с хорошей обобщающей способностью, то мы просто нормально не сойдемся к нему и не достигнем хорошего качества модели.
- Общественность уже идентифицировала такое поведение как проблему и решила ее в более поздних популярных оптимизаторах (см.раздел про AMSgrad).
- Большинство современных рекомендаций по обучению больших неонлайновых моделей вроде GPT или картиночных моделей содержат в себе learning rate scheduler'ы как обязательный для успеха ингредиент. Эти рекомендации нивелируют проблему отрицательных регуляризаторов.
- Все learning rate scheduler'ы заставляют learning rate убывать, что позволяет достигать лучших результатов, чем с помощью обычных Adam и RMSprop.
- В параграфе про FTL мы узнали, что градиентный метод без регуляризации отвратительно работает даже на выпуклых задачах, а если мы начнём вводить отрицательную регуляризацию, да еще и на сложных невыпуклых задачах, то все может стать еще хуже.
В целом, мировой опыт говорит, что полагаться на подобные интерпретации при тюнинге модели не стоит.
Нестабильность в выпуклых задачах
Итак, методы RMSprop и Adam плохо работают для выпуклых задач, особенно для разреженных задач, и могут приводить к субоптимальным решениям на train. Тем не менее, есть искушение заявить, что «это такая регуляризация в классическом смысле: не слишком хорошо сходимся к оптимальной точке, не слишком сильно переобучаемся под датасет и можем лучше работать на тесте». Это искушение особенно опасно потому, что подобные эффекты действительно могут иметь место, особенно в классической (не онлайновой) постановке задачи. Любая регуляризация направлена на то, чтобы сдвинуть оптимум решения исходной некорректно поставленной задачи в надежде, что точка оптимума измененной задачи будет обладать лучшей обобщающей способностью на тесте. В частности, такой эффект может иметь ранняя остановка методов оптимизации до их сходимости к точке оптимума.
Однако здесь есть одно очень важное «но». Если введение регуляризации в некорректно поставленную задачу — это полностью осмысленный и контролируемый гиперпараметрами процесс, то хаотично разваливающийся вокруг точки оптимума метод оптимизации — нет. Подумайте: вдруг ваша задача фактически не является некорректно поставленной? Вдруг у вас огромный и очень репрезентативный датасет, благодаря чему оптимум на train всегда отлично работает в проде? В этом случае кривой метод оптимизации способен подпортить качество вашей модели.
Нестабильность в разреженных задачах
В задачах с разреженными параметрами ситуацию получить еще легче. Допустим, у нас есть некоторый параметр , который встречается в 0.1% объектов выборки. В такой ситуации между появлениями этого объекта в выборке и очередным расчетом градиентов для него проходит значительное время. За это значительное время модель дообучалась, и за счет других, менее разреженных параметров могла научиться лучше прогнозировать очередной объект с этим параметром . Тогда уменьшается и, следовательно, больше шансов попасть в плохую ситуацию.
Ниже мы рассмотрим метод AMSgrad и наперёд скажем, что для оптимизации разреженных параметров Adam/RMSprop добавление AMSgrad очень часто дает прибавку в качестве.
Зависимость нестабильности в регуляризаторе от learning rate
На первый взгляд, парадоксальным кажется следующий факт: чем меньше learning rate, тем в бОльшую сторону может отклониться отрицательный регуляризатор:
Однако в «жадных» формулах все с точностью до наоборот:
Из жадных формул очевидно, что уменьшение ведет к уменьшению шага и, как следствие, увеличению стабильности алгоритма.
Чтобы разрешить парадокс, надо вспомнить, что в FTRL решающее значение имеет не один отдельный регуляризатор, а сумма . В начале процесса оптимизации , первый регуляризатор точно не сломается. Чем меньше learning rate, тем меньшие шаги мы делаем от начальной точки и, следовательно, тем меньше должна отличаться норма градиентов.
Если от шага к шагу норма градиента меняется не слишком сильно, то мы накопим огромную кумулятивную регуляризацию к моменту, когда регуляризатор решит отклониться в отрицательную сторону. При бОльшем learning rate мы шагаем быстрее, и точки, когда ломается регуляризатор, достигаем тоже быстрее, накопив гораздо меньшую сумму . Если теперь для очередной точки мы получили отрицательный регуляризатор, то насколько сильно он может всё поломать?
Окей, допустим, мы шагнули к критической точке. А насколько сильно может расколбасить одна плохая точка в регуляризаторе? Так, чтобы он перекрыл всю предыдущую сумму ? Если градиенты ограничены по норме, то катастрофы, очевидно, не будет. Ограниченность градиентов по норме мы, с одной стороны, гарантировать не можем, с другой — проблемам взрыва/затухания градиентов в архитектурах уделяется столько внимания, что на практике это условие зачастую выполняется.
Чиним RMSprop и Adam
Мотивация
Время шло, люди учились строить хорошо обучаемые архитектуры. Стали даже появляться революционные идеи вроде ReZero (не путать с аниме) с полным отказом от batchnorm/layernorm нормализаций в глубоких сетях и с улучшением качества работы и скорости сходимости. Ситуация со стабильностью обучения нейросетей кардинально изменилась.
Несмотря на улучшение стабильности обучения, люди стали замечать, что при длительном процессе оптимизации Adam начинает сбоить. Авторы метода AMSgrad в статье On the Convergence of Adam and Beyond были одними из первых, кто провел почти аналогичный нашему анализ и добавили в Adam костыль, который обеспечивает выполнение условия и исключает отрицательные регуляризаторы.
Обратите внимание: в разделее про Learning Rate Scheduling vs AdaGrad мы поговорим о «цикличности истории» развития методов оптимизации в deep learning.
AMSgrad
Авторы статьи On the Convergence of Adam and Beyond анализируют последовательность
и говорят, что отрицательные значения в ней вызывают проблемы с процессом оптимизации. Их анализ в целом аналогичен приведённому выше, поэтому мы не будем его здесь дублировать.
Авторы статьи не стали предлагать новых схем learning rate и просто модифицировали старую: выполнение обеспечивается «в лоб» при помощи .
Итоговое правило апдейта без momentum и без bias correction (оригинальный Algorithm 2 из статьи bias correction не использует):
Если нужен метод с momentum, то можно просто заменить в последней формуле на
Реализация без дополнительной памяти
Оригинальные формулы из статьи предполагают, что для расчета мы держим два параметра: и . RMSprop и Adam хранят только один параметр . Таким образом, включение метода требует дополнительных расходов памяти (х1.5 относительно RMSprop и x1.33 относительно Adam). Выше при разборе методов RMSprop/Adam мы сказали, что на практике AMSgrad помогает разреженным параметрам. Для разреженных моделей потребление памяти — краеугольный камень, поэтому простое включение дефолтной реализации amsgrad из статьи может быть болезненным и, к сожалению, не оправданным.
На практике же эвристика вида для разреженных параметров обычно работает так же хорошо и не требует дополнительной памяти. Никаких теоретических гарантий для нее нет, но на практике она работает.
Добавление bias correction
Оригинальная статья (и следующие букве оригинала стандартные реализации алгоритма, например, в PyTorch) предполагает убирание bias correction. Эксперименты на разреженных данных показывают, что убирание bias correction вредит сходимости, это полезная вещь.
С практической точки зрения, есть два способа реализовать bias correction в AMSgrad:
- Post-correction: ,
- Pre-correction: .
С точки зрения корректности метода AMSgrad, правильный вариант — pre-correction, так как он не ломает максимум. А вот эксперименты показывают, что добавление pre-correction ничего не даёт, а вот post-correction действительно помогает в том смысле, что AMSgrad + post-bias correction лучше, чем просто RMSProp/Adam с bias correction.
Соединяем эвристику + bias correction
Итоговые формулы можно использовать такие:
Learning Rate Scheduling
Другим способом улучшения сходимости методов RMSprop/Adam/SGD является learning rate scheduling (расписание learning rate, шедулер). Learning rate scheduler — это мета-алгоритм: они берёт любой стандартный метод оптимизации с константным параметром learning rate и предписывает схему изменения на каждом шаге , или на каждой эпохе, или на любом другом заданном периоде.
Поскольку мы работаем с одним параметром , мы можем с ним делать всего две вещи: увеличивать или уменьшать. Эти два варианта имеют свои названия:
- Learning rate decay — уменьшение learning rate с течением времени с целью нивелировать осцилляцию RMSprop/Adam около критических точек.
- (Warm)Restart — обычно резкое увеличение learning rate. Warm — потому что мы уже сошлись в какую-то хорошую точку и сбрасываем только состояние оптимизатора в ней, но не переинициализируем сами параметры. WarmRestart может заключаться не только в увеличении , но и, например, в дополнительном сбросе состояния оптимизатора (обнуление momentum или ), хотя автор статьи такой подход встречали достаточно редко
Существует огромное количество вариантов расписания, каждый со своим графиком изменения и со своим любовно подобранным множеством задач, на которых данный метод показывает себя лучше других. Приводить здесь их список особого смысла нет, лучше просто откройте документацию любого фреймворка и наслаждайтесь разнообразием вариантов.
Мы же обсудим влияние learning rate decay на осцилляцию вокруг критических точек и дадим практические рекомендации по подбору расписаний.
Влияние learning rate decay на сходимость
Для выпуклых задач в разделе про схемы убывания learning rate для FTRL-методов (константный регуляризатор, и AdaGrad) мы буквально на оценках на regret видели, что это важный аспект для асимптотики сходимости.
В выпуклом случае, при приближении к минимуму мы должны оптимизировать решение с куда большей точностью. Норма градиентов при приближении к минимуму тоже уменьшаются, поэтому даже с константным learning rate шаги будут становиться меньше, но — как показывают и теоретические оценки на regret, и многочисленные их валидации в статьях — этого недостаточно. Уменьшение learning rate с правильной асимптотикой уменьшения дает куда более хорошие результаты. Для глубинного обучения и оптимизации к каким-то локальным минимумам эта логика тоже применима.
Возвращаясь к методам Adam/RMSprop — напомним, что у них асимптотика learning rate . Им в любом случае пойдет на пользу уменьшение learning rate, даже если не брать во внимание их проблемы вокруг критических точек и взять метод AMSgrad, который от этих проблем не страдает.
Отсюда же очевидно, что проблемы adam/rmsprop начинают стрелять гораздо меньше. Learning rate уменьшается => от критической точки мы в плохих ситуациях шагаем на гораздо меньшее расстояние => область, вокруг которой мы будем «прыгать», сужается => мы худо-бедно, но сходимся.
Практические рекомендации
Как мы уже отмечали выше, шедулеров существует поистине фантастическое количество, гораздо больше, чем базовых оптимизаторов, к которым они применяются. Без структуризации подхода к ним работать становится сложно.
Мы хотели бы дать вам следующие рекомендации:
- Выучите свою модель без learning rate scheduling со стандартными методами оптимизации и посмотрите, как ведёт себя loss для различных learning rate. Обязательно переберите learning rate на этом шаге.
- Начинать внедрение расписаний рекомендуем с шедулеров, которые только уменьшают learning rate. Классические варианты — ReduceOnPlateou или linear decay. Правильный подбор learning rate и темпа его уменьшения очень важны в любой задаче стохастической оптимизации.
- Только после того, как вы хорошенько потюните learning rate decay, можно смотреть в сторону WarmRestart. Иногда рестарты могут помочь. Автор статьи занимается в основном рекомендательными моделями и там эту технику практически никто не применяет.
Learning rate scheduling vs AdaGrad
У методов SGD/RMSprop/Adam последовательность не является асимптотически убывающей, и для того, чтобы это скомпенсировать, используется расписание learning rate. А вот у AdaGrad с и так всё в порядке.
Давайте восстановим хронологию событий:
- Метод AdaGrad пытаются применять к нейросетям в 2012+ годах, но тогда архитектуры были нестабильны, градиенты взрывались и навсегда портили знаменатель AdaGrad, сильно уменьшая learning rate.
- Появляются методы RMSprop/Adam (2013/2014) со скользящим средним в знаменателе, которые могут оправиться от взрыва градиента.
- Развитие архитектур нейронных сетей не стоит на месте, появляются разные виды residual connection (2015), LayerNorm/BatchNorm (2015-2016), крутые методы начальной инициализации — огромное количество способов улучшения стабильности обучения.
- С развитием архитектур люди замечают, что RMSProp/Adam умеют застревать на одном уровне значений функции потерь, и начинают применять техники для уменьшения learning rate.
- В дальнейших работах метод AdaGrad часто рассматривается наравне с Adam/RSMprop и дает очень похожее, либо даже лучшее качество (см, например, статью про Shampoo). А дело в том, что архитектуры уже очень хорошо инициализируются и правильно проектируются так, чтобы не было взрывов/затуханий градиентов ни на какой стадии оптимизации.
Развитие методов оптимизации в deep learning сделало небольшой круг, и мы рекомендуем об этом помнить. Порой люди могут одновременно рассуждать о бесценной пользе learning rate decay (особенно с линейным убыванием как ) и корить AdaGrad за бесконечное аккумулирование квадратов градиентов (которые убывают как ). Так что если у вас вдруг хорошо заработал шедулер с — возможно, обычный AdaGrad будет лучше?
SGD vs Adam
В последнее время в литературе часто появляются заявления, что решения, полученные адаптивными методами в нейросетях, обладают худшей обобщающей способностью. Сразу хотим отметить, что большинство этих статей исследуют эти эффекты только на задачах Computer Vision на одних и тех же датасетах MNIST/CIFAR/ImageNet. В реальной жизни куда большее разнообразие постановок задач и датасетов, что сразу заставляет сомневаться в воспроизводимости этих эффектов. Рекомендация тут одна, как и всегда — досконально сами все проверяйте.
AdamW, SGDW
Данные методы предложены авторами в статье Decoupled Weight Decay Regularization, которую мы подробно разобрали в разделее про продвинутую регуляризацию. Методы AdamW и SGDW — это просто модификации методов Adam и SGD с momentum, которые используют линеаризованный decoupled .
Авторы статьи изучали проблему, почему в их экспериментах SGD обобщает лучше Adam (но учится дольше и требует более аккуратной настройки). Они пришли к выводу, что дело не в магии SGD, а в том, что -регуляризация у этих двух методов работает по-разному. Добавив decoupling, авторы сумели показать, что decoupled Adam обгоняет SGD.
Эти эффекты, повторимся, были уже рассмотрены ранее в разделее про продвинутую регуляризацию. Единственное, что мы не обсудили тогда — это momentum. В постановке Proximal Gradient Descent градиент заменяется на momentum
Покоординатные могут рассчитываться любыми методами: AdaGrad, RMSprop или Adam, не принципиально.
На всякий случай напомним, что мы вывели потенциально более правильные формулы
Метод SGDW получается из формул выше, если убрать покоординатность
К сожалению, здесь мы не почерпнули новых идей, так как выяснили, что это просто очередная инкарнация Proximal методов оптимизации.
RAdam
Этот метод заключается в том, чтобы стартовать с адаптивного метода Adam и в некоторый момент переключиться на SGD. «Некоторый момент» — это, интуитивно, момент стабилизации всех статистик в Adam, когда мы выжали все из ускоренного старта адаптивных методов и хотим получше сойтись к хорошему оптимуму в найденной им окрестности.
Отметим, что позднее переключение на SGD с неубывающими learning rate автоматически починит проблемы расходимости Adam ровно там, где они чаще всего и возникают: при хорошем приближении к локальным минимумам.
Мы не будем здесь подробно рассматривать их анализ, вы можете сами познакомиться с ним в статье On The Variance Of The Adaptive Learning Rate And Beyond
Online RMSprop
Особняком стоит метод, описанный в статье Variants of RMSProp and Adagrad with Logarithmic Regret Bounds. Авторы не придумывали очередной хотфикс, а аккуратно заново выводили формулы. Также важно, что данный метод является строгим обобщением метода AdaGrad.
В работе есть два нововведения:
- Переформулировка метода RMSprop так, чтобы:
— Осталось экспоненциальное скользящее среднее;
— Не было проблемы с отрицательными регуляризаторами и взрывающимися learning rate;
— Метод AdaGrad являлся частным случаем нового метода;
— Чтобы все эмпирически хорошо работало в т.ч. на глубоких моделях - Формулировка новых алгоритмов оптимизации SC-AdaGrad и SC-RMSprop для сильно выпуклых функций с логарифмическими гарантиями на regret. SC в названии — Strongly Convex.
Пока рассмотрим только первый пункт. Авторы вводят следующий общий метод:
Нововведение здесь в том, что вместо фиксированного мы будем рассматривать последовательность . Авторы доказывают сублинейный regret для любых последовательностей, удовлетворяющих
AdaGrad как частный случай
Докажем, что метод Adagrad — это метод OnlineRMSprop с . Аналогично выводам momentum в FTRL, перепишем рекуррентное выражение для :
Подставив , получим
Далее, подставляя это в формулу , получаем
Анализ OnlineRMSprop с в стиле FTRL. Пригодность для выпуклых задач
Докажем, что OnlineRMSprop не может сломать регуляризаторы в regret. Для этого преобразуем неравенство
Из условия получаем, что правая часть неравенства неположительна, а левая неотрицательно. Значит, последнее неравенство невозможно, то есть все . Таким образом, регуляризаторы не сломаются, сходимость будет иметь место и данный метод можно использовать в выпуклых задачах. Строгое доказательство сходимости и оценки на Regret можно прочитать в исходной статье.
Эффективный learning rate
Как и ранее в методе AdaGrad, допустим, что . Тогда
При выполнено
Докажем, что все элементы предела < 1. Из этого, в частности, будет следовать, что learning rate у OnlineRMSprop не меньше, чем learning rate в AdaGrad.
Если все все , то итерационный процесс OnlineRMSprop превращается в
Предположим, что . Тогда:
По индукции разворачиваем вплоть до , получаем противоречие.
Полное доказательство предела оставляем читателям. Надо бы чем-нибудь снизу подпереть, что тоже к 1 сходится. Автор сдавал матан почти 10 лет назад и ему было очень неохота откапывать все эти прекрасные пределы, поэтому ответ был получен с помощью wolfram.
Вывод: learning rate у OnlineRMSprop убывает со скоростью . Мы исправили ошибку предыдущего RMSprop, изменив только перевзвешивание, но не асимптотику в . Такой RMSprop можно пробовать использовать в выпуклых задачах
Momentum
Попробуем расписать классический momentum с константным learning rate в стиле FTRL:
Всё, что нам нужно сделать — это взять все рекурсивные зависимости от предыдущей итерации и «размотать» их, получив явное выражение.
Зависимость от переписать довольно просто, мы это уже делали для обычного градиентного спуска:
Теперь надо размотать
Теперь будет чуть сложнее. Подставим это и попробуем расписать, как сумму с определенными коэффициентами:
Множитель сразу выносим за сумму и пока забываем.
Отлично, а теперь нам нужно получить последовательность функций. В линеаризованной задаче это фактически эквивалентно получению зависимости от , где, напомним, — это сумма градиентов.
Теперь мы можем записать функцию, градиент которой равен и онлайн-оптимизация которой эквивалентна процедуре с моментумом:
Получаем, что для онлайн-обучения мы на самом деле каждую итерацию скармливаем экспоненциально взвешенную последовательность всех предыдущих функций исходной последовательности. В принципе, нечто такое мы и ожидали увидеть. Функции , очевидно, выпуклы, так что для данной измененной последовательности функций будет сублинейный regret.
Nesterov Momentum
Рассмотрим классический SGD с momentum, для всех adaptive методов рассуждения аналогичны.
Градиент функции посчитан в предыдущей точке . Идея nesterov momentum в том, чтобы применить momentum на параметры до вычисления градиента:
У метода много всяких «интуитивных объяснений», но изначально Nesterov Momentum был выведен сугубо аналитическими методами. Увы, попытки добавлять его в стохастическую оптимизацию «в лоб» обычно улучшением качества не заканчиваются. Анализ того, почему так нельзя и делать и как можно сделать правильно, проводится в работах Katyusha: The First Direct Acceleration of Stochastic Gradient Methods и Natasha-2 (мотивация их автора Zeyuan Allen-Zhu для выбора таких наименований доподлинно неизвестна). Katuysha правильным образом использует nesterov momentum для выпуклого случая, Natasha — для невыпуклого. Данные методы используют подход SVRG для улучшения сходимости и ускорение оптимизации происходит только при приближении к точке оптимума.
Adan
До недавнего времени громких историй успеха для nesterov momentum в глубоком обучении не было. Метод Natasha распространения не нашел. Наконец, авторы статьи Adan (2022) нашли способ правильной обработки Nesterov Momentum. Метод показал отличные результаты и обновил SOTA метрики на широком спектре задач.
Собираем все идеи воедино
Авторы данного обзора очень хотят, чтобы читатель ушел не с знанием набора наименований методов оптимизации, а с знанием набора концепций, которые тот или иной метод реализует, и при случае мог сам подстроить метод под свои нужды. Тюнинг методов оптимизации — один из главных способов улучшения качества модели на фиксированном датасете.
- Adaptive learning rate — автоматическое подстраивание метода под геометрию задачи оптимизации. Крайне важный класс методов для выпуклых/невыпуклых задач. Must-have для разреженных моделей. Методы: AdaGrad/RMSprop/Adam.
- Скользящее среднее в adaptive learning rate представлено в методах RMSprop/Adam. Не забывайте про их плохое поведение вокруг критических точек и проблемы со сходимостью на финальных этапах оптимизации.
- BiasCorrection: стабилизация обучения на старте для адаптивных методов со скользящим средним. Большинство экспериментов показывают, что это крайне полезная штука и стоит всегда её использовать. В том числе стоит использовать RMSprop с bias correction, если вам не нужны momentum и Adam.
- AMSgrad: способ починить сходимость RMSprop/Adam. Не забывайте, что стандартные реализации при использовании AMSgrad отключают bias correction, а это на самом деле может навредить, а также о том, что можно реализовать AMSgrad без дополнительной памяти, и всё будет хорошо работать.
- Learning rate decay: убывание learning rate зачастую является очень важной деталью в стохастической оптимизации. Помните, что можно брать как AdaGrad, в котором это есть из коробки со скоростью (но архитектура нейросети должна быть хорошей), так и комбинацию RMSProp/Adam + learning rate scheduler.
- WarmRestart: эвристика, резко увеличивающая learning rate после достижения некоторой точки в процессе оптимизации. Практически всегда идет бок о бок с learning rate decay. Где-то помогает
- Проксимальные методы для функций потерь с регуляризаторами: ProximalGD/AdamW/SGDW/FTRL-Proximal. Must-have для -регуляризаторов, без проксимальности они вообще не работают.
- FTRL-Proximal: lazy vs greedy представление. Переписываем представление любого метода оптимизации в не-жадный вид. Позволяет по-новому взглянуть на любые регуляризаторы, особенно негладкие. Must-have для -регуляризации.
- -регуляризация в FTRL-Proximal: Incremental/Fixed/SquareIncremental. Все три имеют разные свойства и разную область применения. Fixed является наилучшим для отбора разреженных признаков/эмбеддингов.
- -регуляризатор для отбора эмбеддингов или автоматического подбора размерности. Можно использовать как аналог FSTR. Крайне полезный подход для разреженных нейросетей в рекомендательных системах, для которых рекомендуется использовать адаптивную схему SquareIncremental.
- Heavy-ball Momentum: используется для ускорения процесса оптимизации. В выпуклых задачах имеет доказанные оценки на улучшение скорости сходимости, в нейросетях используется как эвристика (зачастую опциональная).
- Nesterov momentum: в выпуклом случае гораздо мощнее для batch gradient descent, чем обычный momentum, и это подверждается теоретическими гарантиями. В стохастических методах оптимизации и в онлайн обучении «в лоб» применять нельзя: для выпуклого случая подойдет Katyusha, для нейросетей — Adan.
Главное, что мы хотим подчеркнуть, — эти идеи друг другу не противоречат и их можно свободно комбинировать друг с другом. Например, можно собрать себе FTRL-Proximal метод с -регуляризацией, любым momentum и RMSprop learning rate с AMSgrad. Или любую другую комбинацию. Всегда можно выбрать оптимальный набор под задачу.
Пример таблицы с общими формулами
Эти формулы используют все подходы выше в едином фреймворке, чтобы наглядно убедиться в том, что все можно друг с другом комбинировать.
Generic FTRL-Proximal
Generic Mirror (Proximal) Gradient Descent
Связь:
|
Идея |
FTRL (lazy) |
Gradient Descent (greedy) |
Комментарии |
|
|
Momentum |
|
То же самое |
Не влияет на adaptive |
|
|
Константный learning rate |
, |
|
||
|
Убывающий непокоординатный learning rate |
|
|
Обычно берут |
|
|
Generic Adaptive learning rate |
|
|
и — векторы, везде ниже умножение означает покоординатное умножение |
|
|
Generic Adaptive learning rate с scheduler |
|
|
Например, в Adam: |
|
|
Adaptive learning rate: AdaGrad |
|
|
|
|
|
Adaptive learning rate: RMSprop |
, |
То же самое |
, ломается у критических точек |
|
|
Adaptive learning rate: Online RMSprop |
, , |
То же самое |
|
|
|
Adaptive learning rate: Adam |
, |
То же самое |
, ломается у критических точек |
|
|
Adaptive learning rate: AMSgrad |
, |
То же самое |
|
|
|
Adaptive learning rate: RAdam |
Многобукв |
Многобукв |
|
|
|
Классическая регуляризация |
|
|
||
|
Decoupled регуляризация |
|
|
||
|
Инкрементальная регуляризация |
|
|
||
|
Фиксированная регуляризация |
|
Отсутствует |