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

Dual norm:

Определение: Сопряженной нормой к данной называется:

Пример:

Доказательство:

Неравенство Гельдера:

Свойства:

  • Двойственная норма является нормой
  • норма сопряжена сама себе
  • Двойственная норма к двойственной норме - исходная норма
  • Обобщенное неравенство Коши Шварца: , следствие:

Bregman divergence

Попробуем интуитивно ввести понятие обобщенного расстояния, именуемого расстоянием Брэгмана. Для каждой точки она возвращает расстояние этой точки до - . В самом простом случае можно взять . Рассмотрим уже классическую запись:

Для вводимого обобщенного расстояния будем требовать выполнения (Req1), кроме того (как будет видно при получении оценок), приятным свойством было бы еще следующее требование:

Определение: Дивергенцией (расстоянием) Брэгмана называется функция следующая . Пусть - замкнутое выпуклое множество, тогда функция называется прокс-функцией (distance generating function), если является - сильно выпуклой, т.е.:

Тогда прокс-функцией индуцируется расстояние Брэгмана:

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

Examples

  • Выберем норму в прямом пространстве , пусть , тогда расстояние Брэгмана . Такой выбор совпадает с тем, что мы видели ранее в методе проекции субградиента
  • Выберем теперь другую норму , пусть - антиэнтропия. Тогда эта функция будет сильно выпукла на выпуклом множестве (вероятностном симплексе), а соответствующая ей дивергенция Брэгмана: - расстояние Кульбака - Ляйблера.
  • Еще немного примеров отсюда:

Свойства

  • Аксиома тождества
  • Совместимость с Евклидовой нормой:
  • (Не)равенство треугольника:

Первые два свойства очевидны из определения. Докажем третье:

Возвращение к истокам

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

Просуммируем полученные равенства:

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

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

Попробуем теперь получить наше базовое неравенство, используя (baseMD):

ТЕЛЕСКОПИРУЕМ

Здесь мы подразумеваем равномерно по , а . В итоге:

Выбирая шаг

Алгоритм зеркального спуска (mirror descent):

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

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

Онлайн версия

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

Еще одна интерпретация

Давайте покажем, что полученный алгоритм имеет еще одну очень интуитивную интерпретацию:

  1. Отображение в сопряженное пространство с помощью функции
  2. Градиентный шаг в сопряженном пространстве
  3. Обратное отображение с помощью функции и проекция на бюджетное множество

Для доказательства эквивалентности таких записей, следует сначала доказать факт того, что:

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

Доказательство:

В последней строчке мы пришли к той формулировке, которую писали раньше. Заметим так же, еще одну интересную концепцию:

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

НАФИГА?

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

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

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

А оценки с учетом того, что запишутся, как:

import numpy as np
from matplotlib import pyplot as plt
%matplotlib inline
import seaborn as sns
sns.set()


Ts = np.logspace(0,4, 10)

m = 10
n = 1000
A = np.random.randn(m, n)
x_true = np.random.randn(n)
x_true[x_true < 0] = 0
x_true = x_true/(np.linalg.norm(x_true, 1))

b = A@x_true

x0 = np.ones(n)/n


def f(x):
    return np.linalg.norm(A@x - b, 1)

def grad(x):
    return np.sum(A.T * np.sign(A@x - b), axis=1)

def mirror_descent(x0, grad, T):
    n = len(x0)
    M = np.log(n)
#     G = np.linalg.norm(A,np.inf)*1+np.linalg.norm(b,np.inf)
#     alpha = np.sqrt(2*M/(G**2*T))
    alpha = 0.0001
    xk = x0
    sequence = []
#     print('MD %.3f'%alpha)
    for i in range(int(T)):
        sequence.append(xk)
        g = grad(xk)
        xk = xk * np.exp(-alpha * g) / np.sum(xk * np.exp(-alpha * g))
    return sequence

def projection_subgradient_descent(x0, grad, T):
    n = len(x0)
    M = 0.5
#     G = np.linalg.norm(A,2)*1+np.linalg.norm(b,2)
#     alpha = np.sqrt(2*M/(G**2*T))
    alpha = 0.0001
#     print('GD %.3f'%alpha)
    xk = x0
    sequence = []
    for i in range(int(T)):
        sequence.append(xk)
        g = grad(xk) 
        xk = xk - alpha*g
        xk[xk<0] = 0
        xk = xk/(np.linalg.norm(xk, 1))
    return sequence

result_md = []
result_gd = []

for T in Ts:
    print(T)
    md_T = mirror_descent(x0, grad, T)
    gd_T = projection_subgradient_descent(x0, grad, T)
    
    x_md = np.mean(md_T, axis = 0)
    x_gd = np.mean(gd_T, axis = 0)
    
    result_md.append(f(x_md) - f(x_true))
    result_gd.append(f(x_gd) - f(x_true))

    
plt.loglog(Ts, result_gd, label = 'GD')
plt.loglog(Ts, result_md, label = 'MD')
plt.xlabel('T')
plt.ylabel(r'$f(\overline{x}) - f(x^*)$')
plt.legend()

png