Зеркальный спуск

В математике зеркальный спуск — это итерационный оптимизации алгоритм для поиска локального минимума функции дифференцируемой .

Он обобщает такие алгоритмы, как градиентный спуск и мультипликативные веса .

История

Зеркальный спуск был первоначально предложен Немировским и Юдиным в 1983 году.

Мотивация

При градиентном спуске с последовательностью скоростей обучения $(\eta _{n})_{n\geq 0}$ применительно к дифференцируемой функции $F$, начинаешь с предположения $\mathbf {x} _{0}$ за местный минимум $F,$ и рассматривает последовательность $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ такой, что

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

Это можно переформулировать, заметив, что

$\mathbf {x} _{n+1}=\arg \min _{\mathbf {x} }\left(F(\mathbf {x} _{n})+\nabla F(\mathbf {x} _{n})^{T}(\mathbf {x} -\mathbf {x} _{n})+{\frac {1}{2\eta _{n}}}\|\mathbf {x} -\mathbf {x} _{n}\|^{2}\right)$

Другими словами, $\mathbf {x} _{n+1}$ минимизирует приближение первого порядка к $F$ в $\mathbf {x} _{n}$ с добавленным условием близости $\|\mathbf {x} -\mathbf {x} _{n}\|^{2}$.

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

Формулировка

Нам дана выпуклая функция $f$ оптимизировать по выпуклому множеству $K\subset \mathbb {R} ^{n}$, и при некоторой норме $\|\cdot \|$ на $\mathbb {R} ^{n}$.

Нам также дана дифференцируемая выпуклая функция $h\colon \mathbb {R} ^{n}\to \mathbb {R}$, $\alpha$- сильно выпуклая относительно заданной нормы. Это называется функцией, производящей расстояние , а ее градиент $\nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ известна как зеркальная карта .

Начиная с начального $x_{0}\in K$, в каждой итерации Mirror Descent:

• Карта двойного пространства: $\theta _{t}\leftarrow \nabla h(x_{t})$
• Обновите двойное пространство, используя шаг градиента: $\theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})$
• Вернитесь к первоначальному пространству: $x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})$
• Проект обратно в допустимую область $K$: $x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})$, где $D_{h}$ – это расхождение Брегмана .

Расширения

Зеркальный спуск в настройках онлайн-оптимизации известен как Online Mirror Descent (OMD).

См. также

• Градиентный спуск
• Мультипликативный метод обновления веса
• Алгоритм хеджирования
• Дивергенция Брегмана