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

Мы налагаем разумное структурное предположение, что функция является выпуклой, поскольку она обладает удобным свойством, состоящим в том, что все локальные минимумы также являются глобальными минимумами. Рассматривая выпуклую и дифференцируемую функцию f, наша задача оптимизации состоит в том, чтобы минимизировать f, где X_★ – это минимизатор. (если существует), а f_★ — оптимальное значение задачи.

Градиентный спуск — базовый алгоритм первого порядка решения этой задачи выпуклой оптимизации. Однако наивный градиентный спуск развивает множество зигзагообразных моделей обновлений и имеет медленную скорость сходимости.

Разработка эффективных методов первого порядка с более высокой скоростью сходимости вызвала большой интерес в выпуклой оптимизации, что привело к многочисленным модификациям градиентного спуска. Знаменитый метод ускоренного градиента (AGM) Нестерова (1983) позволяет уменьшать значение функции с ускоренной скоростью O(1/k²). То есть ошибка в k-й точке последовательности x_k (LHS) ограничена функцией от k (RHS) с порядком O(1/k²).

Как мы можем прийти к такому доказательству скорости сходимости? Широко используемый метод заключается в построении функции Ляпунова и использовании того факта, что это невозрастающая функция. В контексте выпуклой оптимизации первого порядка типичный пример функции Ляпунова V(k) может быть сформирован следующим образом, где C(k) — некоторая положительная функция. Основная работа в этой процедуре посвящена упорядочению членов, составляющих функцию C(k).

Анализ методов ускоренного градиента с непрерывной точки зрения

Алгоритм градиента, рассмотренный выше, проиллюстрирован в дискретной настройке, поскольку мы анализируем последовательность чисел с помощью рекурсивного правила. С другой стороны, непрерывная модель описывает динамически изменяющиеся величины, такие как время, используя соответствующее обыкновенное дифференциальное уравнение (ОДУ) в качестве математического инструмента. Непрерывные модели времени намного проще анализировать, чем их дискретные аналоги (одна из причин заключается в том, что мы можем использовать дифференциалы и интегралы), а широко изученные идеи моделирования ОДУ в математической физике могут способствовать наша интуиция для более эффективных методов оптимизации.

Используя преимущества непрерывной структуры, анализ ускоренных градиентных методов в непрерывном времени состоит из следующих шагов:

  1. Смоделируйте ОДУ с высокой скоростью сходимости.
  2. Проанализируйте и докажите скорость сходимости ОДУ в непрерывном режиме с помощью функции Ляпунова.
  3. Дискретизировать или перевести ОДУ в его дискретный аналог, чтобы реализовать алгоритм для реальных вычислений.
  4. Выполните также анализ сходимости к дискретизированной версии.

Несмотря на упрощенную по своей природе процедуру, анализ сходимости в непрерывном времени по-прежнему страдает от узкого места в поиске подходящей функции Ляпунова. Анализ предыдущей работы часто начинается с определения функции Ляпунова неясного происхождения. По правде говоря, эти функции Ляпунова получены в результате многих часов проб и ошибок.

В статье, принятой на ICML 2022, мы предлагаем систематическую методологию получения таких функций Ляпунова. Используя новую методологию, мы делаем следующие вклады:

  1. Мы восстанавливаем многие известные анализы нестеровского ускорения в непрерывном времени упрощенным способом.
  2. Мы выполняем первый непрерывный анализ OGM-G, механизма ускорения, который был понят гораздо меньше, чем механизм AGM Нестерова.
  3. Мы показываем, что центральная идея нашего метода обеспечивает прямую и естественную дискретизацию на основе численного анализа, а также сохраняет ускоренную скорость сходимости.

В этом сообщении блога мы дадим пошаговое объяснение нашей основной методологии и покажем, как она работает для OGM-G.

Наша идея: законы сохранения из расширенных координат

Предлагаемый нами рецепт непрерывного анализа состоит в том, чтобы (1) выполнить замену координат, а затем (2) получить закон сохранения. Мы объясним наш подход, применив его к классической ODE AGM, модели ODE AGM Нестерова, инициированной Su et al. (2014).

(1) Выполнить изменение координат

1. Заданное ОДУ AGM в координате X выглядит следующим образом, для r = 3 (числитель коэффициента при Ẋ) и t ∈ (0, ∞).

2. Выполните следующее изменение координаты с X на W, где W — это расширенная координата, поскольку мы умножаем время t — возрастающее значение — к исходному.

3. Мы выбираем 𝛼 = 2 в ожидании скорости O(1/t²), представленной AGM. Это приводит к следующему ODE AGM в координате W.

(2) Получить закон сохранения

Наша цель состоит в том, чтобы систематически сформировать функции Ляпунова, используемые в предыдущих анализах. Мы обнаруживаем, что после получения закона сохранения из ОДУ в расширенной системе координат результирующая постоянная функция содержит точные члены, составляющие функцию Ляпунова.

В физике закон сохранения механической энергии гласит, что полная энергия — сумма кинетической энергии и потенциальной энергии — остается постоянной. И такое отношение получается из дифференциального уравнения путем взятия скалярного произведения со скоростью и интегрирования от t_0 до t с обеих сторон. В том же духе мы берем скалярное произведение со «скоростью» Ẋ и интегрируем по времени, получая в результате константу.

Продолжая наш пример,

4. Возьмите внутреннее произведение между Ẇ («скорость») и ОДУ AGM в координате W. Обратите внимание, что цепное правило применяется ко второму члену.

5. Проинтегрируйте от t_0 до t с обеих сторон, чтобы получить соответствующий закон сохранения. Первые два члена закона сохранения образуют точную функцию Ляпунова, представленную авторами AGM ODE.

6. Поскольку f выпукла, подынтегральная функция неотрицательна, и мы заключаем с обещанной скоростью сходимости O(1/t²).

Общая форма законов сохранения

Мы проверили нашу методологию, используя обобщенную форму закона сохранения для восстановления анализов в предыдущих работах. Фактически, мы могли бы упростить анализ AGM ODE r › 3 с помощью Attouch et al. (2018), AGM ODE r ‹ 3 от Attouch et al. (2019), AGM ODE с условием роста по Aujol et al. (2019), SC-AGM Wilson et al. (2021), и ОДУ градиентного потока.

Новый непрерывный анализ OGM-G

Теперь мы представляем новую модель ОДУ OGM-G Кима и Фесслера, которая оптимальным образом уменьшает квадрат величины градиента (а не значение функции) для гладкой выпуклой минимизации.

1. Получите OGM-G ODE.

2. Выберите расширенную координату W=(T-t)^𝛼 (X-X _c) для некоторого X_c ∈ ℝ^n. Выберите 𝛼 = -2 в ожидании скорости O(1/T²).

3. Получить соответствующий закон сохранения.

Обратите внимание, что в знаменателе каждого члена закона сохранения есть вычитание.

4. Чтобы избежать любого неопределенного члена из-за деления на ноль, мы характеризуем динамику решения X OGM-G вблизи конечного момента времени t = Т.

5. Определить функцию Ляпунова Φ(t) из первых трех членов закона сохранения с X_c = X(Т). Это монотонно не возрастает.

6. Используя предел Φ(t) после применения правила Лопиталя, мы доказываем, что расширенное решение X демонстрирует обещанную скорость сходимости.

7. Аналогичным образом расширьте анализ для r ‹ -3, чтобы получить обобщенное доказательство OGM-G.

Выводы

В этом посте мы обрисовали в общих чертах предварительные сведения для доказательства скорости сходимости в методах выпуклой оптимизации. Также мы обсудили направление, в котором исследование моделей с непрерывным временем анализирует ускоренные градиентные методы. Мотивируясь сложностью получения функции Ляпунова в ходе анализа, мы представили методологию, выводящую законы сохранения в растянутых системах координат. Используя эту методологию, можно провести новый анализ OGM-G в непрерывном времени. Мы предполагаем, что наши расширенные координаты могут упростить анализ других установок, выходящих за рамки нашего исследования, например, в стохастических дифференциальных уравнениях, моделирующих стохастическую оптимизацию.

автор Сью Хён Пак

Подтверждение

Этот пост в блоге охватывает следующую статью из Сеульского национального университета:

Спасибо Jaewook Suh за предоставленную информацию и ценные отзывы об этом сообщении в блоге. Взгляды и мнения, выраженные в этом посте, принадлежат исключительно авторам.