В данном разделе мы рассмотрим широкое семейство алгоритмов, позволяющее делать улучшения в способах введения регуляризации, которые невозможно добиться в классическом градиентном спуске.
Полезные ссылки
Все написанное ниже (за исключением вывода AdaGrad) — сокращенный пересказ обзора H. Brendan McMahan A Survey of Algorithms and Analysis for Adaptive Online Learning. Везде, где мы обозначаем Lemma 4, Theorem 10 и т.д. — мы ссылаемся на соответствующие теоремы из этой статьи. То же самое с доказательствами: если мы что-то опускаем, подробности можно найти в обзоре
Интуитивный вывод AdaGrad взят из статьи Adaptive Subgradient Methods for Online Learning and Stochastic Optimization . Вместо оригинальных оценок на метод Regularized Dual Averaging, требующих дополнительных понятий вроде двойственности по Фенхелю, мы использовали аналогичную оценку из обзора выше, сохранив все рассуждения автора. Опять же — строгое доказательство оценок на regret для AdaGrad есть в этом обзоре.
Синтаксический сахар
В выкладках очень часто используются суммы, и без сокращенных обозначений читать их невозможно. В литературе про онлайн-обучение приняты вот такие сокращения:
- ;
- Особо отметим обозначение , т.е. точка фиксирована и не меняется с индексацией в сумме;
- (обычно это будет сумма функции потерь и регуляризатора);
- — субградиент функции в точке .
Аддитивные регуляризаторы
В новых обозначениях описанные выше алгоритмы примут вид:
- Adaptive FTRL:
- Adaptive Linearized FTRL:
Опишем условия, накладываемые нами на алгоритм. В обзоре они называются Setting 1.
Setting 1
От функций мы потребуем, чтобы они представлялись в виде:
Слагаемые должны удовлетворять следующим условиям:
- Все выпуклы (вниз);
- ;
- .
Также наложим следующие требования на :
- Область определения — непустое множество. Это требование может показаться странным, но при желании можно придумать пример с пустой областью определения: достаточно взять несколько регуляризаторов-проекций на непересекающиеся выпуклые множества (подробнее о таких регуляризаторах мы расскажем в одном из следующих разделов);
- Субдифференциал в точке непуст.
Классы алгоритмов FTRL
Будем рассматривать аддитивные регуляризаторы из двух семейств в зависимости от того, где у них минимум:
- FTRL-Centered: ;
- FTRL-Proximal: ;
- Composite Objective: смешение первых двух семейств.
Обратите внимание: название Proximal напрямую связано с проксимальным градиентным спуском (ссылка на учебник с проксимальными методами). В обоих случаях мы накладываем регуляризатор в текущей точке .
Обратите внимание: для Proximal регуляризаторов зачастую требуют выполнения более сильного условия: . Это не такое уж и серьёзное ограничение: все разумные Proximal регуляризаторы (например, ) ему удовлетворяют.
Обратите внимание: у обоих семейств есть значимые высокоцитируемые статьи
- FTRL-Centered: метод Regularized Dual Averaging. Статья получила премию Test of Time Award на NeurIPS 2021, так как огромное количество последующих громких результатов (тот же AdaGrad) напрямую основывались на этих результатах. В названии Dual Averaging под dual average имеется в виду , то есть среднее по градиентам. Кардинально других техник оценок regret там нет, обзор McMahan строго улучшает все доступные там результаты.
- FTRL-Proximal: самая известная статья от гугла Ad Click Prediction. Известна она скорее потому, что там выписаны формулы и объяснено, как правильно реализовывать метод для large-scale задач с результатами применения различных дополнительных инженерных идей. Это хороший инженерный обзор, а не математическая статья.
Рассмотрим отдельно каждую из разновидностей алгоритмов
FTRL-Centered
Задача оптимизации имеет вид
где таковы, что
Пример: Рассмотрим SGD с фиксированным learning rate и стартом в точке . Положим
Как мы уже знаем, итеративное обновление весов будет иметь вид
FTRL-Proximal
Задача имеет похожий вид
но выбираются так, чтобы
Пример: Рассмотрим SGD с убывающим learning rate:
Подробный вывод связи и мы приведём в одном из следующих разделов, а сейчас просто приведём результат:
Обратите внимание: как правило, на практике Proximal методы работают лучше. Интуитивно, центрирование в недавних точках вместо
Composite-Objective FTRL
Рассмотрим смесь центрированных и проксимальных регуляризаторов:
где и таковы, что
Пример: FTRL-Proximal с L1 и L2 регуляризацией
Обратите внимание: как правило, центрированные регуляризаторы в довесок к проксимальным вводят уже не для «дополнительной стабилизации» алгоритма, а для наложения ограничений на решение .
Обратите внимание: наиболее правильные и хорошо работающие на практике способы подбора коэффициентов и мы приведём в параграфе про учет дополнительной и регуляризации.
Гарантии сходимости для алгоритмов FTRL
В этом разделе мы обсудим теоретические оценки на скорость сходимости алгоритма FTRL или, что то же самое, на скорость убывания maxRegret.
Напомним формулу:
Чтобы делать оценки на maxRegret, нужно пытаться оценить асимптотику ряда, каждое слагаемое которого — это решение сложной оптимизационной задачи с произвольными функциями . Работать с такой сущностью крайне сложно. Наша основная цель — сделать верхнюю оценку на regret, в которой не будет этого члена.(???)
Strong FTRL Lemma (Lemma 4)
- Пусть — последовательность произвольных (не обязательно) функций;
- Пусть — последовательность выпуклых неотрицательных регуляризаторов;
- Пусть также всегда определен (относительно слабые условия 1-2 требуют от нас это явно проговорить);
Тогда алгоритм, выбирающий по правилу (3), удовлетворяет неравенству
Из чего состоит эта лемма?
-
Слагаемое — это суммарная регуляризация в точке . Совсем избавиться от вхождения не получится, но мы можем выбирать регуляризатор так, чтобы оценить сверху было не очень сложно.
-
Каждое слагаемое суммы $\sum\limits_{t=1}^T \left[h_{0:t}(w_t) - h_{0:t}(w_{t+1})\vphantom{\frac12}\right] $ отражает, насколько улучшается -й лосс при замене на . Поведение разностей характеризует стабильность алгоритма. Мы ожидаем, что при больших у хорошо сходящегося алгоритма на очередном шаге будет достаточно близок к оптимуму , то есть вся сумма будет меняться всё медленнее, и её получится разумно оценить. Пример ситуации, когда это не так, мы уже видели, когда рассматривали FTL без регуляризации для линейной функции потерь (там всё было максимально нестабильно и расходилось). К счастью, введение регуляризации обычно помогает добиться стабильности.
Обе компоненты неразрывно связаны. Добавляя регуляризацию, мы увеличиваем первую компоненту, но улучшает стабильность алгоритма, чем уменьшаем вторую, и наоборот.
Обратите внимание: в условиях леммы допускаются невыпуклые , и это позволяет применять её в весьма общей ситуации. Впрочем, все наши последующие выкладки все-таки будут опираться на выпуклость .
Доказательство Strong FTRL Lemma
Преобразуем выражение для regret:
Вспомним, что
откуда
Поэтому выражение выше мы можем оценить как
Теперь займёмся первыми двумя компонентами
Посмотрим повнимательнее на рыжие слагаемые:
Подставим это:
Здесь мы снова воспользовались тем, что , а также сократили .
Лемма доказана.
Теоретические оценки на Regret (regret bounds)
Ниже мы представим теоремы 1,2 и 10 из обзора McMahan. Они дают оценки на regret в немного разных исходных предположениях и для разных типов регуляризаторов; асимптотика regret в каждом из случаев , хотя константы будут различными. О важности констант в сходимости мы поговорим в одной из следующих параграфов, когда будем разбирать метод AdaGrad. В самом конце параграфа мы обсудим, какие оценки получаются для линеаризованного regret. А в следующем параграфе мы займёмся выводом конкретных алгоритмов FTRL для разных видов регуляризаторов.
Мы не будем полностью пересказывать обзор (если вам стало интересно, рекомендуем прочитать его самостоятельно) и докажем в качестве примера теорему 2, а для остальных приведём лишь формулировки.
Напоминание из выпуклого анализа
Определение Выпуклая функция называется -сильно выпуклой по отношению к некоторой норме $\vert\vert \cdot\vert\vert $, если выполнено
Определение Двойственной нормой по отношению к норме $\vert\vert \cdot\vert\vert $ называется
Физический смысл
Эта норма у нас возникнет в контексте работы с градиентами. С одной стороны, конечно, градиент — это вектор, но по сути он играет роль линейной функции , и кажется логичным определять для него норму именно как для линейной функции, то есть как для элемента двойственного пространства, состоящего из ограниченных линейных функций на исходном пространстве.
Как можно определить норму отображения? Самый, пожалуй, естественный вариант — это рассмотреть операторую норму относительно $\vert\vert \cdot\vert\vert $:
Это формула верна, если пространство, в котором живут и ненулевое (впрочем, нулевое мы вряд ли рассматриваем). Можно показать, что это выражение равно .
Построенная норма называется двойственной к норме на исходном пространстве.
Более подробно о -сильной выпуклости и двойственных нормах вы можете почитать, например, в книге Boyd, 2004, Convex Optimization.
Теорема 1. General FTRL Bound
Пусть
- Обновление параметров происходит по правилу
- Выполнены все условия Setting 1;
- Регуляризатор выбирается так, чтобы выражение было 1-сильно выпукло по отношению к некоторой норме (возможно, своей на каждом шаге).
Тогда
где — норма, двойственная к норме .
Теорема 2. FTRL-Proximal Bound
Пусть
- Обновление параметров происходит по правилу
- Выполнены все условия Setting 1;
- Все регуляризаторы лежат в семействе FTRL-Proximal, причём для всех ;
- выбирается так, чтобы выражение было 1-сильно выпукло по отношению к некоторой норме (возможно, своей на каждом шаге).
Тогда
где — норма, двойственная к норме .
Теорема 10. Composite Objective FTRL-Proximal Bound
Пусть
- Обновление параметров происходит по правилу
- Выполнены все условия Settning 1;
- ;
- — неубывающая последовательность;
- — Centered регуляризатор с минимумом в точке ;
- — Proximal регуляризаторы;
- выбирается так, чтобы выражение было 1-сильно выпукло по отношению к некоторой норме (возможно, своей на каждом шаге).
Тогда
- Если мы рассматриваем regret относительно , то
- Если мы рассматриваем regret относительно , то
где — норма, двойственная к норме .
Обратите внимание. Оценки Proximal и General отличаются индексацией: до или до соответственно. Это чисто техническое различие, однако именно из-за него с Proximal регуляризаторами удобнее работать как в теоретических выкладках, так и при выведении практических методов.
Обратите внимание. На мы не хотим накладывать ограничения сильной выпуклости, но сильную выпуклость функции можно обеспечить за счет выбора сильно выпуклых регуляризаторов. В самом деле, сумма выпуклой и сильно выпуклой функций сильно выпукла. Если
и
то
Обратите внимание. Норма является сопряженной к норме, относительно которой 1-сильно выпукла функция . Это значит, что норму мы будем выбирать по сумме регуляризаторов , а не просто по .
Доказательство на примере теоремы 2
Нам понадобится следующая чисто техническая лемма, доказательство которой мы опустим. Желающие могут прочитать Appendix B в обзоре.
Lemma 7. Пусть
- — выпуклая функция , для которой существует ;
- — выпуклая функция;
- — выпуклая функция, для которой существует и которая, кроме того, 1-сильно выпукла по норме $\vert\vert \cdot\vert\vert $.
Тогда, для любого элемента субдифференциала имеет место неравенство
и для любого имеет место неравенство
Доказательство теоремы 2
Рассмотрим соседние раунды и . Имеем
Обозначим . Поскольку одновременно минимизирует и (т.к. это proximal регуляризатор), и , имеем
Далее,
Выпишем оценку из Strong FTRL Lemma и постараемся оценить отмеченные рыжим слагаемые
Так как по условию теоремы , мы можем убрать это слагаемое:
Обозначим . Применив Лемму 7, получаем
О связи оценок на regret для обычного и линеаризованного FTRL
Вспомним, что для линеаризованного FTRL имеет место неравенство:
Увы, верхняя оценка на левую часть неравенства не помогает оценить правую. Поэтому рассмотрим линеаризованный алгоритм более подробно. Он работает с последовательностью функций , где . Субдифференциал состоит из одного вектора (градиента это функции)
Применим приведённые выше оценки на regret для исходного и для линеаризованного алгоритма:
Легко убедиться, что оценки regret для обычного и линеаризованного FTRL совпадают и выполнено соотношение
Таким образом, для линеаризованного варианта любого алгоритма FTRL не нужно доказывать собственные оценки. А поскольку линеаризованный FTRL намного эффективнее, в дальнейшем мы всегда будем сразу переходить от исходного алгоритма к линеаризованному.
Построение эффективного адаптивного FTRL
Теперь, когда мы получили теоретические оценки на качество работы адаптивного FTRL, настала пора рассмотреть несколько конкретных примеров алгоритмов из этого класса.
Семейство квадратичных регуляризаторов
Во всех дальнейших выкладках мы сразу ограничим себя семейством квадратичных регуляризаторов:
- Для FTRL-Centered алгоритмов: ,
- Для FTRL-Proximal алгоритмов: ,
где — некоторая симметричная положительно определённая матрица (возможно, своя для каждого шага).
Помимо того, что они удобны и привычны, таки регуляризаторы позволяют достаточно просто выписывать оценки на regret. Чтобы в этом убедиться, вспомним, какие нетривиальные сущности возникают в теоремах:
- на каждом шаге нам нужно выбрать норму , по отношение к которой выражение было бы 1-сильно выпуклым;
- во всех оценках участвует (или ), и его хорошо бы уметь оценивать сверху;
- также в оценках фигурирует норма, двойственная к , и её нужно уметь выводить.
Давайте разберёмся с каждым из пунктов и поймём, почему для квадратичных регуляризаторов всё довольно хорошо.
Выбор нормы
Тут всё просто:
- Регуляризатор является 1-сильно выпуклым относительно нормы (т.е. относительно себя же);
- Регуляризатор является 1-сильно выпуклым относительно той же самой нормы .
Нам, впрочем, нужна 1-сильная выпуклость всей суммы , но легко убедиться, что 1-сильно выпукло относительно суммарной нормы . Поскольку — тоже симметричная положительно определенная матрица, мы остаёмся в том же классе норм Махаланобиса.
Двойственная норма
Оказывается, что
Доказательство
По определению
Для начала заметим, что ограничение-неравенство можно заменить на ограничение-равенство. А именно, если , то, взяв , мы получим . Значит, супремум можно искать на границе.
Далее, заметим, что мы работаем с конечномерными пространствами (вряд ли у вектора весов бесконечное число компонент), поэтому единичный шар является компактом и, стало быть, супремум на нём достигается. Таким образом, мы можем решать привычную задачу оптимизации с ограничениями и применить для неё метод множителей Лагранжа.
Выпишем функцию Лагранжа:
Продифференцируем её и приравняем градиент к нулю:
Так как матрица симметрична, имеем и, следовательно,
Подставим его в граничное условие-равенство и выразим :
Отсюда
Транспонировав обе части, получаем
Подставим найденное обратно в выражение :
а полученное решение подставим в исходную функцию :
Ограничение сверху для
Строго говоря, здесь никаких гарантий нет, и, например, очень плохая инициализация может всё сильно испортить. На практике, впрочем, всё работает нормально, но авторы статей не могут себе позволить надеяться на благосклонность судьбы. Поэтому в статьях часто встречается следующий костыль. Для вывода оценок на regret вводится регуляризатор , где
это проекция на шар. Тогда можно доказать, что .
Семейство логарифмических регуляризаторов
Для ряда частных задач вроде expert advice problem и оптимизаций по вероятностным распределениям используется также семейство энтропийных регуляризаторов
Более подробно о нём можно почитать в обзоре Shai-Shalev Schwartz, пример 2.5.
Constant learning rate FTRL
Простейший пример — это константный регуляризатор
Легко показать, что .
Соответствующий итерационный процесс оптимизации имеет вид
Как мы уже наблюдали ранее, этот метод эквивалентен методу стохастического градиентного спуска с константным learning rate. А именно, шаг обновления весов можно сформулировать двумя способами:
-
на языке FTRL: ;
-
на языке градиентного спуска: .
Оценка на Regret (3.1 Constant Learning Rate Online Gradient Descent). Пусть
- ;
- .
Тогда, если взять , то для любого
В целом, такая стратегия регуляризации не самая оптимальная. Интуитивно, наш регуляризатор фиксирован вне зависимости от того, сколько мы уже сыграли раундов, и со временем может перестать компенсировать член , и тогда стабильность алгоритма может падать.
FTRL с learning rate scheduling
Чтобы исправить нестабильность алгоритма, возьмём -регуляризатор, не равный нулю на каждом шаге.
Процесс оптимизации примет вид:
- Для FTRL-Proximal: ;
- Для FTRL-Centered: .
Посмотрим, какое обличье примет алгоритм FTRL-Proximal, если его изложить на языке градиентного спуска. Для этого продифференцируем и приравниваем нулю выражение, которое мы минимизируем:
Попробуем получить рекуррентную формулу для выражения через :
Если теперь положить , мы получаем формулу градиентного спуска:
Таким образом, темп обучения градиентного спуска равен обратной сумме коэффициентов регуляризации ftrl. Точно так же можно выразить
В качестве классической непокоординатной последовательности learning rate обычно берут
Оценка на Regret (3.2, Dual Averaging) Пусть
- ,
- .
Тогда, если выбрать , то
Как и в случае с константным learning rate, константа в на практике никому не известна, так что ее подменяют на и перебирают руками с learning rate, равным .
Data-Adaptive FTRL
До сих пор мы рассматривали в качестве нормы $\vert\vert \cdot\vert\vert $ стандартное скалярное произведение, в которое различные компоненты вектора весов (которые, грубо говоря, соответствуют различным признакам) вносят равный вклад. Такой подход может быть слишком наивным для «боевых» задач, где геометрия оптимизации имеет форму, например, вытянутого эллипса.
Нетрудно обобщить предыдущие рассуждения на случай произвольного скалярного произведения
Коэффициенты в этом выражении теперь спрятались в . Найдем точку минимума:
Но сразу возникают проблемы:
- Нужно хранить , в общем случае это квадрат по памяти от числа параметров. Ни в какой реальной задаче мы не сможем себе этого позволить;
- На каждой итерации метода нужно решать гигантскую систему линейных уравнений для поиска . Есть все шансы состариться, так и не успев увидеть решение задачи оптимизации.
Упростим себе жизнь и предположим, что все матрицы диагональны. Тогда можно хранить в виде вектора диагональных элементов того же размера, что и , а система на каждой итерации будет решаться за линию.
AdaGrad: наилучший адаптивный метод
Разрешив себе брать нормы с диагональными матрицами , мы сделали алгоритм более гибким, но при этом приобрели дополнительные степени свободы (выбор диагональных элементов). Попробуем ответить на два вопроса:
- Можно ли матрицы не угадывать, а настраивать по доступной на очередном шаге информации?
- Как выбирать матрицы так, чтобы минимизировать оценки на regret?
В процессе поисков ответов на них мы придём к известному методу оптимизации AdaGrad.
Помня, что , выпишем общий вид оценки на regret:
Чтобы упростить выкладки, введем новую симметричную положительно определенную матрицу и перепишем формулы
С членом явно будет очень сложно работать: чтобы им пользоваться, нужно иметь на руках оптимальное решение для всей предыдущей выборки. Более перспективным выглядит слагаемое : вычислять их одно удовольствие. Идея метода AdaGrad как раз в том, чтобы не пытаться работать с первым членом и минимизировать второй, надеясь, что итоговые оценки на regret при этом тоже улучшатся.
Для начала выведем диагональный AdaGrad как более простой случай. Если все диагональны, то матрица тоже диагональна и представляется набором диагональных элементов (уберем индекс для сокращения выкладок, так как мы рассматриваем фиксированный раунд).
Распишем второе слагаемое в regret
Попробуем минимизировать его
Условие возникает из неотрицательной определенности матрицы . Решеним такой задачи, очевидно, является . Однако в этом случае член из оценки на regret станет, наоборот, бесконечно большим, и нужен какой-то компромисс. Введем довольно слабое ограничение на положительные коэффициенты
и найдём оптимум с помощью метода множителей Лагранжа. Функция Лагранжа имеет вид
Отметим, что здесь — это вектор, а — число.
Приравняем к нулю частные производные:
Вспомним про условия дополняющей нежесткости, требующие, чтобы . Так как мы нулю приравнять здесь не можем, получаем, что :
Теперь вспомним про условие . Можно показать, что оптимум достигается на границе (то есть когда неравенство превращается в равенство). Тогда
Вернемся к оценке на regret. Чему равно мы не знаем, поэтому мы просто констатируем, что оптимальные коэффициенты пропорциональны :
Теперь — диагональная матрица с диагональными элементами . Следовательно, - тоже диагональная матрица с диагональными элементами :
и легко убедиться, что
Теперь вспомним, что эти формулы в точности повторяют то, что мы получили выше для соотношения , только вместо общего коэффициента у нас теперь покоординатные коэффициенты :
Получаем формулы для метода AdaGrad в градиентной постановке:
где коэффициент приобретает значение learning rate.
Оценка на Regret (3.4, FTRL-Proximal with Diagonal Matrix Learning Rates)
Если использовать AdaGrad с покоординатными learning rate, то
Отметим, что это оценка отличается от предыдущей тем, что вместо используется . Таким образом, если у градиента на какой-то из позиций стоит что-то большое, это повлияет лишь на одно из слагаемых под корнем вместо того, чтобы умножиться на .
Эффективный размер шага. Предположим, что градиенты ограничены по норме . Перепишем наши формулы в виде
Из этих формул следует, что в среднем learning rate в AdaGrad убывает как , то есть так же, как в предыдущем методе. Отличие состоит лишь в более правильной покоординатной нормировке, которая улучшает сходимость.