О чём раздел про онлайн-обучение, кому и зачем его читать?
Во многих случаях обучение ML-модели ― это однократный процесс, после которого она не меняется и только используется для предсказания. А что, если к нам постоянно поступает новая информация и мы должны её учитывать? Тогда модель должна уметь обновляться при поступлении нового объекта или батча объектов. Грубо говоря, этим и занимается онлайн-оптимизация. Можно заметить, что обновление модели на батче объектов проходит и в процессе стохастической оптимизации, ― и это сходство не случайно.
Оказывается, что все известные вам методы стохастической оптимизации первого порядка ― такие как SGD, AdaGrad, Adam, AMSgrad и другие ― являются в первую очередь алгоритмами онлайн-обучения. Чтобы в этом убедиться, достаточно открыть эти статьи и увидеть, для какой задачи выводятся гарантии на сходимость. Постановка задачи онлайн-обучения является одновременно математически простой и очень общей, соединяя три больших темы:
- «Классическое» онлайн обучение.
- Стохастическую оптимизацию на фиксированном датасете. Мы покажем, что любой алгоритм онлайн обучения можно переформулировать, как алгоритм стохастической оптимизации; при этом из гарантий на сходимость, полученных для онлайн обучения, автоматически будет следовать сходимость на фиксированном датасете.
- Adversarial обучение.
Данный текст является в первую очередь систематизирующим. Мы постараемся достичь следующих целей:
- Подведем единую математическую базу, необходимую для вдумчивого чтения статей по оптимизации. Это будет полезно ML-теоретикам.
- Покажем, как исторически развивались методы оптимизации, как из одного метода получался другой, какие проблемы они решали и ― главное ― актуальны ли эти проблемы сейчас.
- Разберём все «именные» методы оптимизации на набор базовых концепций и покажем, как вы можете самостоятельно их сочетать, создавая оптимальный метод для решения своей задачи. Спойлер: базовых концепций намного меньше, чем наименований методов. Эти знания будут полезны ML-инженерам.
- Пройдемся по относительно нишевым темам, таким как разреженные методы регуляризации $L_1$ и $L_{1/2}$, и рассмотрим наилучшие методы оптимизации для них. Такие методы невозможно получить в стандартной постановке стохастической оптимизации. Эти знания будут полезны ML-инженерам, занимающимся рекомендательными системами.
В параграфе «Введение в онлайн-обучение», которую вы читаете сейчас, вы познакомитесь с общей постановкой задачи онлайн-обучения, а также с семейством алгоритмов Follow the Regularized Leader (FTRL), которое включает в себя все методы первого порядка. Кроме того, вы узнаете, как сводить задачи стохастической оптимизации к задачам онлайн-обучения и увидите, что этот переход позволяет строить более эффективные методы стохастической оптимизации, особенно для разреженных регуляризаторов вроде $L_1$.
В параграфе «Адаптивный FTRL» вы узнаете, как улучшить сходимость алгоритмов стохастической оптимизации с помощью регуляризаторов и каковы гарантии сходимости для регуляризованных задач. Это позволит вывести AdaGrad как наилучший адаптивный метод для онлайн-оптимизации.
В параграфе «Регуляризация в онлайн-обучении» мы снова поговорим о регуляризации, но на этот раз речь пойдёт о регуляризаторах, которые накладывают на решение определённые органичения, например, разреженность. Вы сможете с новой стороны взглянуть на разреживающие свойства $L_1$-регуляризаторов. Кроме того, мы получим с помощью не достижимые с помощью обычных SGD/AdaGrad результаты для разреженных $L_1$ и $L_{1/2}$ регуляризаторов.
В параграфе «Стохастическая оптимизация в Deep Learning» мы перейдём к методам оптимизации в глубоких нейросетях. Вас ждёт краткий исторический обзор и мотивация появления двух важных модификаций AdaGrad ― Adam и RMSprop. Мы покажем, что эти методы ломаются вокруг критических точек, и поговорим о том, как починить это и достичь более точной сходимости (этого эффекта можно достичь либо прямой модификацией алгоритмов (AMSgrad и RAdam), либо косвенно с помощью Learning Rate Scheduler'ов).
В конце параграфа мы соберём воедино все рассмотренные концепции и покажем, как можно комбинировать лучшее из разных методов оптимизации в один новый метод.
Оглавление
Часть 3. Продвинутые методы регуляризации
Часть 4. Методы оптимизации в Deep Learning
Постановка задачи
Литература. Отсюда и далее, пока явно не скажем о переходе на другие источники информации, используется материал из книги Shai Shalev-Shwartz Online Learning and Online Convex Optimization
Онлайн-обучение ― это процесс предсказания ответов на последовательность вопросов с учётом знания (возможно, неполного) о предыдущих правильных ответах.
Представим себе следующую игру (назовём её игра (1)). На каждом раунде игры $t$ мы:
- Получаем $x_t$ ― частичную информацию о текущем «вопросе»;
- Выбираем модель $w_t$, которой будем делать прогноз;
- Прогнозируем $p_t(w_t, x_t)$;
- Получаем истинный ответ $y_t$;
- Получаем обратную связь-лосс $l(p_t, y_t)$. Лоссы обычно имеют семантику функции ошибки: больше ― хуже, меньше ― лучше.
Цель любого алгоритма онлайн обучения ― минимизация суммарной ошибки прогнозов $Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t)$ для любого количества раундов T.
Пока рассмотрим интуитивный пример: линейная регрессия (обозначения взяты из параграфа про линейные модели). Пусть у нас уже сыграны раунды $1,\ldots,t-1$ и есть выборка данных $x_1,\ldots,x_{t-1}$ и ответов $y_1,\ldots,y_{t-1}$.
- Получаем новый $x_t$. В данном случае просто получаем и пока не используем;
- Выбираем модель $w_t$, которая наилучшим образом объясняет всю предыдущую имеющуюся выборку $x_{1..t}$ (алгоритм обучения можем выбирать любой, какой нам нравится);
- Прогнозируем $p_t = <w_t, x_t>$;
- Получаем правильный ответ $y_t$;
- Считаем loss $(y_t - p_t)^2$;
Действуя таким образом, мы делаем интуитивное предположение, что ответы $y_t$ как-то зависят от наших $x_t$ и что эту зависимость мы можем выучить из предыдущей выборки, улучшив прогноз на новых объектах.
Предположения
Теория онлайн обучения выгодно отличается от классической теории статистического обучения довольно расслабленными и гораздо более простыми (с точки зрения математических формулировок) условиями. Мы не делаем предположений о некой статистической зависимости между $x_t$, $y_t$. Зависимость может быть детерминированной, стохастической или даже adversarial:
- Детерминированная: в самом начала игры делается выбор детерминированной зависимости $x_t \rightarrow y_t$
- Стохастическая: $x_t$ может быть реализациями случайной величины, зависящей от $y_t$
- Adversarial: мы играем против активного противника, который может на каждом раунде игры по своему усмотрению менять зависимость $x_t \rightarrow y_t$ и/или подбирать $l(p_t, y_t)$, имея на руках в том числе текущий ответ $y_t$, не доступный алгоритму онлайн-обучения
Adversarial постановка включает в себя все остальные как частные случаи, так что сразу будем строить теорию для наиболее общего случая.
Поведение алгоритма на шаге T
Начнем с введения метрики качества алгоритма на некотором раунде игры T, а затем расширим ее на все раунды игры.
Если у противника нет никаких ограничений, то противник всегда выигрывает. Поскольку $l(p_t, y_t)$ выбирается после нашего прогноза, он может выбрать любую функцию с сколь угодно большим штрафом.
Чтобы такого не случалось, мы предположим, что все ответы на шаге T должны быть сгенерированы некоторым отображением $h^*: X\rightarrow Y, h^* \in H$, где $H$ ― пространство возможных решений, **известное и онлайн-алгоритму, и противнику**.
С учетом введенного ограничения на поведение противника, введем понятие regret:
$$Regret_T(h) = \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h(x_t), y_t)$$
Regret ― это метрика того, насколько онлайн алгоритм работает хуже, чем некоторая фиксированная модель-бейзлайн h (regret переводится как «сожаление»: насколько мы пожалели о том, что взяли онлайн алгоритм, а не модель h). Поскольку мы работаем в adversarial случае, то логично сравнивать наш онлайн алгоритм с сильнейшим возможным противником, а именно: противник всегда выбирает не «некоторую», а наилучшую модель-бейзлайн $h^* \in H$:
$$maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right]$$
Поведение алгоритма на всей последовательности раундов игры
Вспомним, что вообще-то мы играем игру с бесконечным числом раундов. В таком случае, естественно будет анализировать поведение ряда $maxRegret(T), T \in \mathbb{N}, T \rightarrow \infty$. Здесь хочется еще раз подчеркнуть, в чем заключается adversarial поведение: на каждом шаге t maxRegret будет иметь **свою** наилучшую модель $h^*_t$ в бейзлайне:
$$maxRegret(\color{#348FEA}{T_1}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*_{\color{#348FEA}{T_1}}(x_t), y_t)$$
$$maxRegret(\color{#E06A27}{T_2}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*_{\color{#E06A27}{T_2}}(x_t), y_t)$$
Качество онлайн алгоритма на протяжении всей игры
Когда мы говорим про adversarial setting и игру с противником, мы хотим не просто как-то минимизировать кумулятивный $Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t)$, но еще и хотим быть не хуже нашего противника. Потребуем, чтобы
$$\lim\limits_{T \rightarrow \infty} \frac{1}{T}maxRegret(T) = 0$$
Такое условие означает, что regret должен расти медленнее чем линейно (в таком случае говорят, что алгоритм имеет сублинейный regret).
Сублинейности бывают разные. Так, $Regret_T$ может быть ограничен сверху рядом с асимптотикой $\sqrt{T}$ или же рядом с асимптотикой $\log{T}$
Асимптотика $\log{T}$, очевидно, приводит к намного лучшей сходимости. Но достичь этого не всегда возможно. Стандартной асимптотикой regret в большинстве используемых на практике алгоритмов является $\sqrt{T}$, для этой асимптотики условия на задачу наименее жесткие. Все рассматриваемые нами ниже алгоритмы будут иметь асимптотику $\sqrt{T}$ и отличаться в основном константами в оценках (но, конечно, отличия в константах при оценке Regret часто приводят к существенно разному поведению на практике). Любые более мощные асимптотики требуют условий, которые крайне редко выполняются в практических задачах
Online to batch conversion
В данном обзоре мы будем анализировать методы, которые гораздо чаще используются для оптимизации в классической постановке: есть фиксированный датасет $(x_i, y_i)_{i=1}^N$, модель $p_w(x)$ с обучаемыми параметрами $w$ и функция потерь $f$, задача ― найти минимум функции
$$\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i)$$
Если представить, что все наши $f(p_w(x_i), y_i)$ ― независимые одинаково распределенные случайные величины, то можно считать, что на самом деле мы оптимизируем
$$\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i) \approx \mathbb{E}_{(x,y)}f(p_w(x), y)$$
Такую постановку задачи часто называть батчевой (англ. batch). Это означает, что мы можем использовать два класса методов оптимизации:
- методы, которые на каждом шаге смотрят сразу на всю выборку (например, градиентный спуск или метод Ньютона);
- методы, которые на каждом шаге смотрят на случайное подмножество данных в надежде, что, итерируясь по таким подмножествам, мы сможем соптимизировать матожидание $\mathbb{E}f(w)$ (например, SGD). Такие методы называют стохастическими.
Существует специальный класс методов анализа сходимости, называемый online to batch conversion. Они позволяют адаптировать алгоритм онлайн-обучения к постановке задачи стохастической оптимизации на фиксированном датасете; при этом оценка на regret транслируется в асимптотику сходимости стохастической оптимизации. Математически строгий вывод этих методов обычно довольно громоздкий и не дарит более глубокого понимания идей в современных стохастических методах, это чисто технические выкладки, поэтому мы здесь ограничимся интуитивным описанием. Строгий вывод можно найти, например, в упомянутой выше книге Shai Shalev-Schwartz.
Процесс стохастической оптимизации на фиксированном датасете можно представить в виде задачи онлайн обучения, если вытянуть все эпохи (проходы по датасетам) в единую последовательность. Мы получим задачу онлайн обучения, в которой $(x_t, y_t)$ сэмплируются из фиксированного множества ${(x_1, y_1), ..., (x_N, y_N)}$. Строго говоря, тут сэмлпирование двухстадийное:
- Берем исходное множество функций
- Сэмплируем из него без возвращения, пока множество не станет пустым
- Как только оно стало пустым ― заново заполняем его
Таким образом, деление на "эпохи" отчетливо видно и в вытянутой последовательности.
Легко видеть, что эта задача является корректной задачей онлайн обучения. Тут мы активно пользуемся тем, что постановка задачи онлайн обучения математически простая и очень общая. Из корректности данной задачи следует, что все алгоритмы онлайн обучения будут иметь на такой последовательности сублинейный regret.
Следующим шагом давайте взглянем на regret в момент смены эпохи. Обозначим за $M$―число эпох, тогда:
$$maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(h^*(x_i), y_i)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right]$$
Из сходимости последовательности следует сходимость любой ее подпоследовательности, а значит, последовательность regret'ов в моменты смены эпох тоже ведет себя сублинейно:
$$\frac{1}{MN}\max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$
$$\max\limits_{h^* \in H}\left[ \frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$
$$\frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \min\limits_{h^* \in H}\left[ \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$
Последнее слагаемое уже выглядит практически как постановка задачи стохастической оптимизации на фиксированном датасете! Интуиция на данный момент подсказывает нам, что разрыв между решениями, даваемыми онлайн обучением, и точным решением задачи батч-оптимизации, будет постепенно сокращаться.
В этот момент интуицию можно выключать―остаются только строгие технические выкладки по ссылкам выше.
Выпуклая онлайн-оптимизация
Выпуклая оптимизация играет центральную роль в анализе алгоритмов онлайн-обучения и позволяет получать эффективные алгоритмы. Вот примеры задач, в которых она хорошо работает:
- Линейная оптимизация;
- Expert Advice problem;
- Линейная/логистическая регрессия.
Для задач, возникающих в глубинном обучении, мы поступим согласно рекомендациям ведущих ученых: возьмем теоретически обоснованный алгоритм выпуклой оптимизации, воткнем в нейросеть и помолимся, чтобы он сохранил свои хорошие свойства. С методами первого порядка, как правило, работает (а здесь мы будем рассматривать только такие методы)
Введём в нашу игру предположение о выпуклости, а заодно попробуем сделать вычисления менее громоздкими. Для этого определим упрощённую игру (2):
- Выбираем параметрическую модель $w_t$;
- Получаем извне выпуклую функцию потерь $f_t(w)$;
- Считаем $f_t$ в точке $w_t$ и получаем наш loss $f_t(w_t)$.
Первое упрощение состоит в тем, что прогноз $h_t$ и бейзлайн $h^*_t$ мы теперь берём не из абстрактного функционального множества $H$, а из некоторого параметризованного семейства. Говоря «модель $w_t$», мы имеем в виду «модель, заданная параметрами $w_t$». Скажем, для линейной регрессии это может быть вектор весов и bias. Regret будет записываться следующим образом:
$$maxRegret_T = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w_T^*)$$
Второе упрощение в том, что мы не думаем о признаках $x_t$ и таргетах $y_t$. Вся эта информация спрятана в определение функции $f_t(w)$. Например, для линейной регрессии $f_t(w) = (x_t^Tw - y_t)^2$. При этом теперь у нас нет частичной информации о текущем раунде игры перед выбором новой модели $w_t$: ведь мы сначала выбираем $w_t$ и лишь потом получаем $f_t(w)$.
Обратите внимание: если вы попробуете себе представить онлайн алгоритм на практике, то, как правило, частичная информация о функции $f_t(w)$ перед выбором $w_t$ вам доступна. Например, рассмотрим рекомендательную систему с онлайн-дообучаемой ранжирующей моделью:
- Пользователь пришел, мы сразу пошли в базу данных за его историей покупок и получили признаковое описание (возможно частичное) $x_t$;
- С учётом этого признакового описания мы выбираем модель $w_t$ и её с помощью оцениваем релевантность товаров этому пользователю;
- Смотрим, что купил пользователь и купил ли, это даёт нам $f_t(w_t)$.
Тем не менее, в этом параграфе мы будем считать, что частичной информации нет, потому что хотим разрабатывать наиболее общий фреймворк, а не ad-hoc алгоритмы, использующие конкретный вид этой частичной информации. Если даже для какой-то узкой проблемы можно сформулировать специфический алгоритм, учитывающий частичную информацию, с высокой вероятностью он не будет работать значимо лучше стандартного решения. Если знаете контрпримеры ― напишите, добавим сюда для полноты.
Follow the Leader
Предположим, что мы провели $t$ шагов игры (2) и теперь выбираем модель $w_{t+1}$ (как условились, без информации о $f_{t+1}(w)$). Наиболее естественным выбором будет алгоритм, минимизирующий ошибку на всех предыдущих раундах
$$w_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{t}f_s(w)$$
Такой алгоритм называется Follow The Leader (FTL), потому что мы идем вплотную за наилучшим возможным алгоритмом-бейзлайном в regret (лидером), который учитывает ещё и информацию с $(t+1)$-го шага:
$$w*_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{\color{#E06A27}{t+1}}f_s(w)$$
К сожалению, для алгоритма в таком виде есть важные примеры выпуклых задач, когда он не работает. Допустим, наши функции потерь линейны $f_t(w) = g_t^Tw$. Вам может показаться, что линейная функция не особенно похожа на функцию потерь, но, забегая вперед, именно такие функции потерь встретятся дальше при изучении градиентных онлайн-алгоритмов ($g_t = \nabla f_t(w_t)$).
Рассмотрим одномерную задачу $f_t(w) = g_tw_t$, $g_t \in \mathbb{R}$, $w_t \in[-1;1]$. Пусть
$$g_t = \begin{cases} -0.5 & t=1 \ 1 & t%2 = 0 \ -1 & t%2 = 1 \end{cases}$$
Алгоритм FTL выглядит так:
$$w_{T+1} = arg\min\limits_w\sum\limits_{t=1}^T g_tw = arg\min\limits_w w\Big(\sum\limits_{t=1}^T g_t\Big)$$
Такие осциллирующие суммы коэффициентов будут заставлять FTL выбирать наихудшее возможное решение в каждом раунде. Функция потерь в каждом раунде будет равна $0.5$, а кумулятивная функция потерь примет вид $\sum\limits_{t=1}^T0.5 = 0.5T$. При этом кумулятивная функция потерь константного решения $w^*=0$ будет равна 0. Получаем линейный regret $0.5T$ относительно бейзлайна $w_T^* = w^* = 0$, алгоритм не сходится.
Follow The Regularized Leader
Чтобы стабилизировать алгоритм, мы добавим регуляризаторы, и назовем получившийся алгоритм Follow The Regularized Leader (FTRL):
$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R(w)\Big]$$
Упражнение. Проверьте, что в примере из предыдущего параграфа добавление регуляризатора стабилизирует осцилляцию решения $w$.
Добавка $R(w)$ должна быть выпуклой и неотрицательной. При этом различный выбор $R(w)$ будет приводить к различным алгоритмам и различным оценкам на regret.
Первое, что приходит в голову ― это $L_2$ регуляризатор $R(w) = \vert\vert w\vert\vert_2^2$. Он даёт алгоритм
$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) +\frac{1}{2\lambda}\vert\vert w\vert\vert_2^2\Big]$$
Adaptive FTRL
Следующая идея―сделать регуляризатор зависящим от данных (то есть от $f_t$) и своим на каждом раунде T:
$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R_T(w)\Big]$$.
Забегая вперед―все современные градиентные алгоритмы Adam, RMSProp, AdaGrad и т.д. попадают в это семейство data-dependent регуляризаторов и работают значительно эффективнее любых алгоритмов с константными регуляризаторами $R(w)$.
Обратите внимание: регуляризаторы являются частью алгоритма FTRL, они не входят в формулу для regret, которая по-прежнему имеет вид
$$Regret_T(w^*) = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w^*)$$
Таким образом, мы не изменили постановку решаемой нами задачи, изменили лишь метод ее решения.
Обратите внимание: введение регуляризаторов влияет только на онлайн-алгоритм и выбор $w_t$. Бейзлайны $w_T^*$ выбираются как и раньше:
$$w_T^* = arg\min\limits_w \sum\limits_{t=1}^Tf_t(w)$$
Линеаризация и вычислительно эффективный FTRL
Рассмотрим пример с логистической регрессией $f_t(w) = \log(1 + e^{-y_tw_t^Tx_t})$ и константным $L_2$ регуляризатором:
$$\sum\limits_{t=1}^T \log(1 + e^{-y_tw_t^Tx_t}) + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\longrightarrow\min\limits_w$$
Классический пример использования онлайн логистической регрессии ― предсказание CTR в рекламе. Миллионы запросов в секунду => миллионы решений этой оптимизационной задачи в секунду (если разбивать на батчи ― тысячи, но сути это не меняет). Успех онлайн-алгоритма в таких задачах определяется его вычислительной эффективностью, как по памяти, так и по скорости. Увы, с этим у нашего алгоритма не всё так хорошо:
- Скорость: аналитически задача не решается => FAIL
- Память: нужно хранить все предыдущие запросы $x_t$, $t\in{1..T}$ => FAIL
Здесь нам на помощь приходит линеаризация задачи. Если фунции $f_t(w)$ выпуклые (вниз) и гладкие (на негладкие посмотрим позже), то они удовлетворяют основному свойству выпуклых функций
$$f(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t)$$
Разложим все функции $f_t(w)$ в точках $w_t$:
$$f_t(w) \geq f_t(w_t) + [\nabla f(w_t)]^T(w - w_t)$$
$$f_t(w_t) - f_t(w) \leq [\nabla f(w_t)]^T(w - w_t)$$
Просуммируем от 1 до T
$$\sum\limits_{t=1}^T \Big(f_t(w_t) - f_t(w)\Big) \leq \sum\limits_{t=1}^T \Big([\nabla f_t(w_t)]^Tw_t - [\nabla f_t(w_t)]^Tw^T\Big)$$
Теперь обозначим $g_t = \nabla f_t(w_t)$ и рассмотрим выпуклую линейную задачу онлайн обучения с функцией потерь $\widetilde{f}_t(w) = g_t^Tw$. Regret для нее выглядит как
$$LinearizedRegret_T(w^*) = \sum\limits_{t=1}^T g_t^Tw_t - \sum\limits_{t=1}^T g_t^Tw^*$$
Неравенство выше позволяет нам оценить regret исходной задачи через regret линеаризованной:
$$Regret_T(w^*) \leq LinearizedRegret_T(w^*)$$
Минимизируя правую часть неравенства, мы, безусловно, будем минимизировать и левую, так что мы можем выбирать $w_t$ алгоритмом, решающим линеаризованную задачу, и получать хорошо сходящийся метод для исходной задачи.
Посмотрим, будет ли линеаризованный алгоритм вычислительно эффективнее. Посмотрим на линеаризацию задачи с data-depedent регуляризатором:
$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla [f_t(w_t)]^Tw + R_T(w)\Big]$$
Линейные задачи имеют аналитическое решение для широкого спектра $R_T(w)$. Собственно, это и есть основное, что нужно помнить на практике ― выбирать регуляризатор так, чтобы эта задача решалась аналитически. Мы рассмотрим простейший случай $R_T(w) = R(w) = \frac{1}{2\eta}\vert\vert w\vert\vert_2^2$:
$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla f_t(w_t)^Tw + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\Big]$$
Справа дифференцируемая функция, так что мы можем найти $w_T$, приравняв к нулю градиент:
$$w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = -\eta z_T,$$
где $z_T = \sum\limits_{t=1}^T \nabla f_t(w_t)$ ― это сумма векторов, которую не нужно пересчитывать заново на каждом шаге, а можно инкрементально обновлять. Благодаря этому нам больше не нужно помнить все предыдущие объекты выборки, достаточно хранить лишь некоторую статистику.
Готово, мы построили наш первый вычислительно эффективный алгоритм онлайн обучения! В дальнейшем мы займемся тем, чтобы найти наилучший вычислительно эффективный алгоритм.
Обратите внимание: теперь вы понимете, почему пример с линейной функцией потерь был так важен: линейные функции соответствуют линеаризованному regret. При этом, как мы уже выяснили, без регуляризатора такие линеаризованные задачи нестабильны.
Обратите внимание: если переписать немного формулу для $w_T$, мы получим:
$$w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = w_{T-1} - \eta \nabla f_t(w_t)$$
Таким образом, формулы FTRL c константным регуляризатором эквивалентны формулам обычного стохастического градиентного спуска. Забегая вперед, скажем, что различия в формулах градиентного спуска и FTRL будут только в разделе Composite objective FTRL. В этих отличиях и будет заключаться преимущество FTRL перед привычным SGD.
Обратите внимание: концепции FTRL и gradient descent в литературе часто называют lazy (ленивая) и greedy (жадная) соответственно.
Gradient descent жадный, потому что алгоритм для обновления $w_{t+1}$ использует только текущий $w_t$ и текущий градиент $g_t$. Всё, что было на предыдущих шагах, алгоритм забывает.
FTRL ленивый, потому что алгоритм в явном виде сохраняет всю информацию с начала обучения и рассчитывает $w_{t+1}$, исходя из всей истории $g_1,\ldots,g_t$, и только после этого применяет все регуляризаторы. Подробнее мы расскажем об этом в разделе «Сравнение Composite Objective FTRL-Proximal и Adaptive Gradient Descent».
Субдифференциал и субградиентные методы
Выше мы рассматривали гладкие функции $f_t(w)$. Гладкость ― сильное ограничение, и оно на самом деле необязательно, можно ослабить условие, если использовать субградиенты.
Когда мы переходили от исходной задачи к линеаризованной, мы использовали основное свойство гладких выпуклых функций
$$f(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t), \quad \forall w_t$$
Гладкость обеспечивает существование $\nabla f(w_t)$ для всех $w_t$. Но нам ведь не нужно, чтобы существовал именно градиент функции. Нам достаточно, чтобы существовал какой-то вектор $g_t$, для которого выполнено неравенство
$$f(w) \geq f(w_t) + g^T(w - w_t)$$
И в этом помогают следующие два понятия.
Субдифференциалом функции $f(w)$ в точке $w_t$ называется множество
$$\partial_{w_t} f(w) = \left\{ g_t \mid f(w) \geq f(w_t) + f^T(w - w_t),\forall w\right\}$$
Субградиентом функции $f(w)$ в точке $w_t$ называется любой элемент множества $\partial f(w_t)$.
Потребуем, чтобы для любой точки был непустой субдифференциал, и дело в шляпе, можно вместо $\nabla f_t(w)$ везде подставлять субградиент $g_t$ и обобщить все выкладки выше на негладкий случай.
Примеры. Для гладких функций субдифференциал состоит из одной точки: градиента функции, а субградиент равен градиенту. В качестве примера функции с нетривиальным субградиентом рассмотрим функцию $f(x) = \vert x \vert$, где $x$ ― скаляр. Субградиент в точке $0$ ― это можество
$$\partial_0|x| = \left\{ \lambda\mid |x| \geq \alpha x \right\}$$
Легко видеть, что $\partial_0\vert x\vert $ ― это отрезок $[-1, 1]$.
Замечание. На практике субдифференциал используют не так часто. Оптимизационные задачи с популярными негладкими регуляризаторами $L_1$ решают «в лоб», без перехода к субградиентной оценке, наприер, с помощью проксимальных методов.
Обратите внимание. В литературе очень часто используется термин Online Mirror Descent. Mirror descent ― это оптимизационная процедура вида
$$w_{t+1} = arg\min\limits_w \left[\vphantom{\frac12}g_t^Tw + \lambda \psi(w) + \vert\vert w-w_t\vert\vert_2^2\right],$$
в которой $\psi$ ― дополнительный негладкий регуляризатор (например, тот же $L_1$), который мы как раз таки не заменяем на субградиентную оценку, а вместо этого оптимизируем всё «в лоб». Заметьте, что эти формулы идентичны формулам Proximal Gradient Descent. Если у нас нет регуляризатора $\psi$, то формулы эквивалентны обычному gradient descent.
Как вы увидите дальше, Mirror Descent ― это частный случай общего фреймворка, который мы описываем.
Субградиентные методы оптимизации.
Почти все градиентные методы оптимизации обобщаются на негладкие функции. Модифицируется необходимое и достаточное условие минимума для выпуклых функций: точка $w^*$ является минимумом, если субдифференциал содержит ноль: $0 \in \partial f(w^*)$. Очевидно, это прямое обобщение условия для гладких функций, где субдифференциал состоит только из градиента функции.