descenso del espejo

En matemáticas, el descenso de espejos 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 del 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 suposició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 con un 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 distancia de Bregman . El uso de otras distancias de Bregman generará otros algoritmos, como Hedge , que pueden ser más adecuados para la optimización de geometrías particulares. ^{[2] [3]}

Formulación

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

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

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

• Mapa al espacio dual: ${\displaystyle \theta _{t}\leftarrow \nabla h(x_{t})}$
• Actualice en el espacio dual usando un paso de gradiente: ${\displaystyle \theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})}$
• Mapa de regreso al espacio primordial: ${\displaystyle x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})}$
• Proyecto de regreso a la región factible : , donde está 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 espejos en la configuración de optimización en línea se conoce como descenso de espejos en línea (OMD). ^[4]

Ver 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 del problema y eficiencia del método en optimización. John Wiley e hijos, 1983
2. Nemirovski, Arkadi (2012) Tutorial: algoritmos de descenso de espejos para optimización convexa estocástica y determinista a gran escala. https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf
3. "Algoritmo de descenso de espejos". tlienart.github.io . Consultado el 10 de julio de 2022 .
4. Colmillo, Huang; Harvey, Nicolás JA; Portella, Víctor S.; Friedlander, Michael P. (3 de septiembre de 2021). "Descenso de espejos en línea y promediado dual: mantener el ritmo en el caso dinámico". arXiv : 2006.02585 [cs.LG].