Прежде всего напомним определение проекции на замкнутое множество W.

Помните, что правило обновления OSG было следующим.

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

С этой точки зрения становится понятно, что правило обновления OSD условно связано с определением L2-нормы. Можем ли мы полагаться на общее понятие близости вместо того, чтобы зависеть от конкретного выбора? Ответ положительный.

Это определение дивергенции Брегмана, где psi — строго выпуклая и непрерывно дифференцируемая функция. В силу строгой выпуклости psi дивергенция Брегмана всегда положительна и равна нулю тогда и только тогда, когда аргументы x и y совпадают. Это означает, что мы можем использовать его, чтобы указать, чем x отличается от y. Ура!

Замените норму L2 расхождением Брегмана в обновлении OSD.

Это новое правило обновления эквивалентно старому, когда psi является L2-нормой (деленной на 2). С этим правилом, вставленным в OSD вместо старого, мы получаем класс алгоритмов, известный как Online Mirror Descent (OMD). Каждый алгоритм в классе идентифицируется различным выбором функции psi.

Экспоненциальный градиент

Мы готовы вывести алгоритм экспоненциального градиента. С этого момента я буду пренебрегать некоторыми математическими тонкостями и постараюсь дать вам общие идеи.

Скажем, у нас есть общая вещественная многомерная и вещественная функция f. Его сопряженная функция Фенхеля - это функция, определяемая следующим образом:

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

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

определено на множестве

(определить 0 ln(0) = 0).

Сопряжение Фенхеля пси

Решая по x (что возможно с использованием условий ККТ), получаем такое выражение для компонент x:

Подставив в выражение сопряженное выражение Фенхеля, мы получим:

Как вы можете легко вывести, градиент сопряжения Фенхеля и градиент psi удовлетворяют этим двум выражениям соответственно:

Если вы до сих пор следили за аргументом, пришло время собрать все воедино.

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

EG удовлетворяет границе сожаления, заданной следующим образом (где эта фиксирована):

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

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

Выводы

В этом посте мы разработали алгоритм экспоненциального градиента, фундаментальный инструмент онлайн-обучения. Это конец этой серии статей об онлайн-обучении. Надеюсь тебе понравилось! 👋🏻

Рекомендации

  • Орабона, Ф. (2019). Современное введение в онлайн-обучение. ArXiv, абс/1912.13213.
  • Шалев-Шварц, С. (2012). Онлайн-обучение и выпуклая онлайн-оптимизация. Найдено. Тенденции Маха. Учись., 4, 107–194.
  • Баушке, Х.Х., и Комбеттс, П.Л. (2011). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах. Книги CMS по математике.
  • Кивинен, Дж., и Вармут, М.К. (1997). Экспоненциальный градиент по сравнению с градиентным спуском для линейных предикторов. Инф. Вычисл., 132, 1–63.