Descenso del espejo

En matemáticas, el descenso de espejo es un algoritmo de optimización iterativo para encontrar un mínimo local de una función diferenciable .

Generaliza algoritmos como el descenso de gradiente y los pesos multiplicativos .

Historia

El descenso por espejo fue propuesto originalmente por Nemirovski y Yudin en 1983. ^[1]

Motivación

En el descenso de gradiente con la secuencia de tasas de aprendizaje aplicadas a una función diferenciable , se comienza con una estimación de un mínimo local de y se considera la secuencia tal que ${\displaystyle (\eta _{n})_{n\geq 0}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle F,}$ ${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$

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

Esto se puede reformular señalando que

${\displaystyle \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)}$

En otras palabras, minimiza la aproximación de primer orden a at con el término de proximidad agregado . ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle \|\mathbf {x} -\mathbf {x} _{n}\|^{2}}$

Este término de distancia euclidiana al cuadrado es un ejemplo particular de una distancia de Bregman . El uso de otras distancias de Bregman dará como resultado otros algoritmos como Hedge , que pueden ser más adecuados para la optimización en geometrías particulares. ^{[2] [3]}

Formulación

Se nos da una función convexa para optimizar sobre un conjunto convexo , y se nos da una norma en . ${\displaystyle f}$ ${\displaystyle K\subset \mathbb {R} ^{n}}$ ${\displaystyle \|\cdot \|}$ ${\displaystyle \mathbb {R} ^{n}}$

También se nos da una función convexa diferenciable , fuertemente convexa con respecto a la norma dada. Esta se llama función generadora de distancia y su gradiente se conoce como mapa especular . ${\displaystyle h\colon \mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \alpha }$ ${\displaystyle \nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$

A partir del valor inicial , en cada iteración de Mirror Descent: ${\displaystyle x_{0}\in K}$

• Mapa del espacio dual: ${\displaystyle \theta _{t}\leftarrow \nabla h(x_{t})}$
• Actualización en el espacio dual mediante un paso de gradiente: ${\displaystyle \theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})}$
• Regrese al espacio primordial: ${\displaystyle x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})}$
• Proyecto de regreso a la región factible : , donde es la divergencia de Bregman . ${\displaystyle K}$ ${\displaystyle x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})}$ ${\displaystyle D_{h}}$

Extensiones

El descenso de espejo en el entorno de optimización en línea se conoce como Descenso de Espejo en Línea (OMD). ^[4]

Véase también

• Descenso de gradiente
• Método de actualización de peso multiplicativo
• Algoritmo de cobertura
• Divergencia de Bregman

Referencias

1. Arkadi Nemirovsky y David Yudin. Complejidad de problemas y eficiencia de métodos en optimización. John Wiley & Sons, 1983
2. Nemirovski, Arkadi (2012) Tutorial: algoritmos de descenso de espejo para optimización convexa determinista y estocástica a gran escala. https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf
3. "Algoritmo de descenso de espejo". tlienart.github.io . Consultado el 10 de julio de 2022 .
4. Fang, Huang; Harvey, Nicholas JA; Portella, Victor S.; Friedlander, Michael P. (3 de septiembre de 2021). "Descenso de espejo en línea y promedio dual: manteniendo el ritmo en el caso dinámico". arXiv : 2006.02585 [cs.LG].