Introduction

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

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

Однако, в нашем случае мы можем лишь получить (будет показано ниже) оценки следующего вида:

Это связано с тем, что нам легче контролировать при построении условного метода, а значит, легче записать на него оценку. К сожалению, привычной телескопической (сворачивающейся) суммы при таком неравенстве не получится. Однако, если неравенство (Forward Target) выполняется, то из него следует следующее неравенство:

Для того, чтобы доказать его, запишем (Forward Target Fix):

Переписывая его еще раз, получаем:

Итак, пускай мы имеем неравенство (Forward Target) - напомню, что мы его пока не доказали. Теперь покажем, как с его помощью получить оценки на сходимость метода. Для этого запишем неравенство (Forward Target Fix):

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

Можем сразу получить оценки:

Таким образом, мы показали, что для метода проекции субградиента справедлива точно такая же оценка на число итераций, если выполняется неравенство (Forward Target) :) Давайте разбираться с ним

Нам следует доказать, что:

В более общем случае :

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

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

Рассмотрим теперь следующую функцию :

И давайте теперь строить условный алгоритм как минимизацию этой функции:

Тогда из условия оптимальности:

Полученное неравенство в точности совпадает с неравенством (Forward Target), которое нам как раз таки и следовало доказать. Таким образом, мы получаем

Algorithm

Интересные фишки:

  • Такая же скорость сходимости, как и для безусловного алгоритма. (Однако, стоимость каждой итерации может быть существенно больше из за необходимости решать задачу оптимизации на каждом шаге)
  • В частном случае в точности совпадает с безусловным алгоритмом (убедитесь)

Adaptive stepsize (without )

Разберем теперь одну из стратегий того, как избежать знания количества шагов заранее для подбора длины шага . Для этого зададим “диаметр” нашего множества :

Теперь зададим длину шага на - ой итерации, как: . Константу подберем чуть позже.

Для начала легко заметить, что:

см. геометрический смысл неравенства ниже:

Возьмем теперь равенство для классического субградиентного метода (БМ) (или неравенство в случае метода проекции субгадиента (УМ)):

Где - выбран путем минимизации данной оценки по .

Таким образом, мы получили, что в случае, если количество шагов не надо знать заранее (весьма важное свойство), то оценка ухудшилась в раз. Такие оценки называют anytime bounds.

Online learning:

PSD - Projected Subgradient Descent

Examples

Least squares with regularization

Nonnegativity

- ball

Linear equality constraints

Bounds

Conditions Convergence rate Iteration complexity Type of convergence
Convex
Lipschitz-continious function($G$)
$\mathcal{O}\left(\dfrac{1}{\sqrt{k}} \right)$ $\mathcal{O}\left(\dfrac{1}{\varepsilon^2} \right)$ Sublinear
Strongly convex
Lipschitz-continious function($G$)
$\mathcal{O}\left(\dfrac{1}{k} \right)$ $\mathcal{O}\left(\dfrac{1}{\varepsilon} \right)$ Sublinear

References