Introduction

Рассматривается классическая задача выпуклой оптимизации:

Подразумевается, что - выпуклая функция на выпуклом множестве . Для начала будем рассматривать задачу безусловной минимизации (БМ),

Вектор называется субградиентом функции в точке , если :

Градиентный спуск предполагает, что функция является дифференцируемой в каждой точке задачи. Теперь же, мы будем предполагать лишь выпуклость.

Итак, мы имеем оракул первого порядка:

Вход:

Выход: и

Algorithm

где - произвольный субградиент функции в т. ,

Bounds

Vanilla version

Запишем как близко мы подошли к оптимуму на последней итерации:

Для субградиента: . Из написанного выше:

Просуммируем полученное неравенство для

Здесь мы предположили . Предполагая (постоянный шаг), имеем:

Минимизация правой части по дает

Тогда (используя неравенство Йенсена и свойство субградиента ) запишем оценку на т.н. Regret, а именно:

Важные моменты:

  • Получение оценок не для , а для среднего арифметического по итерациям - типичный трюк при получении оценок для методов, где есть выпуклость, но нет удобного убывания на каждой итерации. Нет гарантий успеха на каждой итерации, но есть гарантия успеха в среднем
  • Для выбора оптимального шага необходимо знать (предположить) число итераций заранее. Возможный выход: инициализировать небольшим значением, после достижения этого количества итераций удваивать и рестартовать алгоритм. Более интеллектуальный способ: адаптивный выбор длины шага.

Steepest subgradient descent

Попробуем выбирать на каждой итерации длину шага более оптимально. Тогда:

Минимизируя выпуклую правую часть по , получаем:

Оценки изменятся следующим образом:

Значит,

Что приводит к абсолютно такой же оценке на невязку по значению функции. На самом деле, для такого класса функций нельзя получить результат лучше, чем или по итерациям

Online learning

Рассматривается следующая игра: есть игрок и природа. На каждом из шагов:

  • Игрок выбирает действие
  • Природа (возможно, враждебно) выбирает выпуклую функцию , сообщает игроку значение
  • Игрок вычисляет следующее действие, чтобы минимизировать регрет:

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

Несмотря на весьма сложную (на первый взгляд) постановку задачи, существует стратегия, при которой регрет растет как , что означает, что усредненный регрет падает, как

Если мы возьмем оценку (Subgradient Bound) для субградиентного метода, полученную выше, мы имеем:

Однако, в её выводе мы нигде не использовали тот факт, что . Более того, мы вообще не использовали никакой специфичности точки . Тогда можно записать это для произвольной точки :

Запишем тогда оценки для регрета, взяв :

Итого мы имеем для нашей стратегии с постоянным шагом:

Examples

Least squares with regularization

Algorithm will be written as:

where signum function is taken element-wise.

Support vector machines

Let

We need to find and such that

Code

Open In Colab

References