Descenso de coordenadas aleatorias

El método de descenso de coordenadas aleatorio (por bloques) es un algoritmo de optimización popularizado por Nesterov (2010) y Richtárik y Takáč (2011). El primer análisis de este método, aplicado al problema de minimizar una función convexa suave , fue realizado por Nesterov (2010). ^{[ 1 ]} En el análisis de Nesterov, el método debe aplicarse a una perturbación cuadrática de la función original con un factor de escala desconocido. Richtárik y Takáč (2011) proporcionan límites de complejidad iterativa que no requieren esta suposición, lo que significa que el método se aplica directamente a la función objetivo. Además, generalizan el marco al problema de minimizar una función compuesta, específicamente la suma de una función convexa suave y una función convexa separable por bloques (posiblemente no suave).

${\displaystyle F(x)=f(x)+\Psi (x),}$

dónde${\displaystyle \Psi (x)=\sum _{i=1}^{n}\Psi _{i}(x^{(i)}),}$${\displaystyle x\in R^{N}}$se descompone en${\displaystyle n}$bloques de variables/coordenadas:${\displaystyle x=(x^{(1)},\dots ,x^{(n)})}$y${\displaystyle \Psi _{1},\dots ,\Psi _{n}}$son funciones convexas (simples).

Ejemplo (descomposición en bloques): Si${\displaystyle x=(x_{1},x_{2},\dots ,x_{5})\in R^{5}}$y${\displaystyle n=3}$uno puede elegir${\displaystyle x^{(1)}=(x_{1},x_{3}),x^{(2)}=(x_{2},x_{5})}$y${\displaystyle x^{(3)}=x_{4}}$.

Ejemplo (regularizadores separables por bloques):

1. ${\displaystyle n=N;\Psi (x)=\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|}$
2. ${\displaystyle N=N_{1}+N_{2}+\dots +N_{n};\Psi (x)=\sum _{i=1}^{n}\|x^{(i)}\|_{2}}$, dónde${\displaystyle x^{(i)}\in R^{N_{i}}}$y${\displaystyle \|\cdot \|_{2}}$es la norma euclidiana estándar .

Consideremos el problema de optimización.

${\displaystyle \min _{x\in R^{n}}f(x),}$

dónde${\displaystyle f}$es una función convexa y suave.

Suavidad: Por suavidad entendemos lo siguiente: asumimos que el gradiente de${\displaystyle f}$es Lipschitz continua por coordenadas con constantes${\ Displaystyle L_ {1}, L_ {2}, \ puntos, L_ {n}}$. Es decir, asumimos que

${\displaystyle |\nabla _{i}f(x+he_{i})-\nabla _{i}f(x)|\leq L_{i}|h|,}$

a pesar de${\displaystyle x\in R^{n}}$y${\displaystyle h\in R}$, dónde${\displaystyle \nabla _{i}}$denota la derivada parcial con respecto a la variable${\displaystyle x^{(i)}}$.

Nesterov, Richtarik y Takac demostraron que el siguiente algoritmo converge al punto óptimo:

Algoritmo del método de descenso de coordenadas aleatorias Aporte:${\displaystyle x_{0}\in R^{n}}$//punto de partida Producción:${\displaystyle x}$ establecer x := x_0 para k := 1, ... elegir coordenada${\displaystyle i\in \{1,2,\dots ,n\}}$uniformemente al azar actualizar${\displaystyle x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla _{i}f(x)}$fin para

Dado que las iteraciones de este algoritmo son vectores aleatorios, un resultado de complejidad proporcionaría un límite en el número de iteraciones necesarias para que el método genere una solución aproximada con alta probabilidad . En ^{[ 2 ]} se demostró que si ${\displaystyle k\geq {\frac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)}$, dónde${\displaystyle R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|yx^{*}\|_{L}:f(y)\leq f(x)\}}$, ${\displaystyle f^{*}}$es una solución óptima (${\displaystyle f^{*}=\min _{x\in R^{n}}\{f(x)\}}$), ${\displaystyle \rho \in (0,1)}$es un nivel de confianza y${\displaystyle \epsilon >0}$es precisión del objetivo, entonces${\displaystyle {\text{Prob}}(f(x_{k})-f^{*}>\epsilon )\leq \rho }$.

La siguiente figura muestra cómo${\displaystyle x_{k}}$se desarrolla durante las iteraciones, en principio. El problema es

${\displaystyle f(x)={\tfrac {1}{2}}x^{T}\left({\begin{array}{cc}1&0.5\\0.5&1\end{array}}\right)x-\left({\begin{array}{cc}1.5&1.5\end{array}}\right)x,\quad x_{0}=\left({\begin{array}{cc}0&0\end{array}}\right)^{T}}$

Este algoritmo se puede extender naturalmente no solo a coordenadas, sino también a bloques de coordenadas. Supongamos que tenemos espacio${\displaystyle R^{5}}$. Este espacio tiene 5 direcciones de coordenadas, concretamente ${\displaystyle e_{1}=(1,0,0,0,0)^{T},e_{2}=(0,1,0,0,0)^{T},e_{3}=(0,0,1,0,0)^{T},e_{4}=(0,0,0,1,0)^{T},e_{5}=(0,0,0,0,1)^{T}}$ en el que el método de descenso de coordenadas aleatorias puede moverse. Sin embargo, se pueden agrupar algunas direcciones de coordenadas en bloques y podemos tener en lugar de esas 5 direcciones de coordenadas 3 direcciones de coordenadas de bloque (ver imagen).

• Descenso de coordenadas
• Descenso de gradiente
• Optimización matemática