Descenso coordinado - Coordinate descent

El descenso de coordenadas es un algoritmo de optimización que minimiza sucesivamente a lo largo de las direcciones de las coordenadas para encontrar el mínimo de una función. En cada iteración, el algoritmo determina una coordenada o un bloque de coordenadas a través de una regla de selección de coordenadas, luego minimiza exacta o inexactamente sobre el hiperplano de coordenadas correspondiente mientras fija todas las demás coordenadas o bloques de coordenadas. Se puede realizar una búsqueda de línea a lo largo de la dirección de las coordenadas en la iteración actual para determinar el tamaño de paso apropiado. La descendencia coordinada es aplicable tanto en contextos diferenciables como libres de derivadas.

Descripción

El descenso de coordenadas se basa en la idea de que la minimización de una función multivariable se puede lograr minimizándola en una dirección a la vez, es decir, resolviendo problemas de optimización univariados (o al menos mucho más simples) en un bucle. En el caso más simple de descenso cíclico de coordenadas , uno itera cíclicamente a través de las direcciones, una a la vez, minimizando la función objetivo con respecto a cada dirección de coordenadas a la vez. Es decir, comenzando con los valores iniciales de las variables. ${\ Displaystyle F (\ mathbf {x})}$

${\ Displaystyle \ mathbf {x} ^ {0} = (x_ {1} ^ {0}, \ ldots, x_ {n} ^ {0})}$,

round define de resolviendo iterativamente los problemas de optimización de una sola variable ${\ Displaystyle k + 1}$${\ Displaystyle \ mathbf {x} ^ {k + 1}}$${\ Displaystyle \ mathbf {x} ^ {k}}$

${\ Displaystyle x_ {i} ^ {k + 1} = {\ underset {y \ in \ mathbb {R}} {\ operatorname {arg \, min}}} \; f (x_ {1} ^ {k + 1}, \ dots, x_ {i-1} ^ {k + 1}, y, x_ {i + 1} ^ {k}, \ dots, x_ {n} ^ {k})}$

para cada variable de , de 1 a . ${\ Displaystyle x_ {i}}$${\ Displaystyle \ mathbf {x}}$${\ Displaystyle i}$${\ Displaystyle n}$

Por lo tanto, uno comienza con una suposición inicial para un mínimo local de y obtiene una secuencia de forma iterativa. ${\ Displaystyle \ mathbf {x} ^ {0}}$${\ Displaystyle F}$${\ Displaystyle \ mathbf {x} ^ {0}, \ mathbf {x} ^ {1}, \ mathbf {x} ^ {2}, \ dots}$

Al hacer una búsqueda de línea en cada iteración, uno tiene automáticamente

${\ Displaystyle F (\ mathbf {x} ^ {0}) \ geq F (\ mathbf {x} ^ {1}) \ geq F (\ mathbf {x} ^ {2}) \ geq \ dots.}$

Se puede demostrar que esta secuencia tiene propiedades de convergencia similares a las del descenso más pronunciado. Ninguna mejora después de un ciclo de búsqueda de líneas a lo largo de las direcciones de las coordenadas implica que se alcanza un punto estacionario.

Este proceso se ilustra a continuación.

Caso diferenciable

En el caso de una función F continuamente diferenciable , un algoritmo de descenso de coordenadas se puede esbozar como:

El tamaño del paso puede elegirse de varias maneras, por ejemplo, mediante la resolución de la minimizador exacto de f ( x _i ) = F ( x ) (es decir, F con todas las variables pero x _i fijo), o por criterios de búsqueda de línea tradicionales.

Limitaciones

El descenso coordinado tiene dos problemas. Uno de ellos tiene una función multivariable no uniforme . La siguiente imagen muestra que la iteración de descenso de coordenadas puede atascarse en un punto no estacionario si las curvas de nivel de una función no son suaves. Suponga que el algoritmo está en el punto (-2, -2) ; luego hay dos direcciones alineadas con el eje que puede considerar para dar un paso, indicadas por las flechas rojas. Sin embargo, cada paso a lo largo de estas dos direcciones aumentará el valor de la función objetivo (asumiendo un problema de minimización), por lo que el algoritmo no dará ningún paso, aunque ambos pasos juntos acercarían el algoritmo al óptimo. Si bien este ejemplo muestra que el descenso de coordenadas no es necesariamente convergente al óptimo, es posible mostrar una convergencia formal en condiciones razonables.

El otro problema es la dificultad en el paralelismo. Dado que la naturaleza del descenso de coordenadas es recorrer las direcciones y minimizar la función objetivo con respecto a cada dirección de coordenadas, el descenso de coordenadas no es un candidato obvio para el paralelismo masivo. Trabajos de investigación recientes han demostrado que el paralelismo masivo es aplicable al descenso de coordenadas relajando el cambio de la función objetivo con respecto a cada dirección de coordenadas.

Aplicaciones

Los algoritmos de descenso coordinado son populares entre los profesionales debido a su simplicidad, pero la misma propiedad ha llevado a los investigadores de optimización a ignorarlos en gran medida en favor de métodos más interesantes (complicados). Una de las primeras aplicaciones de la optimización del descenso de coordenadas fue en el área de la tomografía computarizada, donde se ha encontrado que tiene una rápida convergencia y posteriormente se utilizó para la reconstrucción clínica por tomografía computarizada de exploración helicoidal de múltiples cortes. Se ha aplicado un algoritmo de descenso de coordenadas cíclicas (CCD) en la predicción de la estructura de proteínas. Además, ha aumentado el interés en el uso del descenso de coordenadas con el advenimiento de problemas a gran escala en el aprendizaje automático , donde el descenso de coordenadas ha demostrado ser competitivo con otros métodos cuando se aplica a problemas como el entrenamiento de máquinas de vectores de soporte lineal (ver LIBLINEAR ) y factorización matricial no negativa . Son atractivos para problemas en los que no es factible calcular gradientes, tal vez porque los datos necesarios para hacerlo se distribuyen a través de las redes informáticas.

Ver también

• Descenso de coordenadas adaptativo
• Gradiente conjugado
• Descenso de gradiente
• Búsqueda de línea
• Optimización matemática
• Método de Newton
• Descenso de gradiente estocástico : utiliza un ejemplo a la vez, en lugar de una coordenada

Referencias

• Bezdek, JC; Hathaway, RJ; Howard, RE; Wilson, CA; Windham, MP (1987), "Análisis de convergencia local de una versión de variable agrupada del descenso de coordenadas", Journal of Optimization Theory and Applications , Kluwer Academic / Plenum Publishers, 54 (3), págs. 471–477, doi : 10.1007 / BF00940196 , S2CID  120052975
• Bertsekas, Dimitri P. (1999). Programación no lineal, segunda edición Athena Scientific, Belmont, Massachusetts. ISBN  1-886529-00-0 .
• Luo, Zhiquan; Tseng, P. (1992), "Sobre la convergencia del método de descenso de coordenadas para la minimización diferenciable convexa", Journal of Optimization Theory and Applications , Kluwer Academic / Plenum Publishers, 72 (1), págs. 7-35, doi : 10.1007 / BF00939948 , hdl : 1721.1 / 3164 , S2CID  121091844.
• Wu, TongTong; Lange, Kenneth (2008), "Algoritmos de descenso coordinado para regresión penalizada por Lasso", The Annals of Applied Statistics , Institute of Mathematical Statistics, 2 (1), págs. 224–244, arXiv : 0803.3876 , doi : 10.1214 / 07-AOAS147 , S2CID  16350311.
• Richtarik, Peter; Takac, Martin (abril de 2011), "Complejidad de iteración de métodos de descenso de coordenadas de bloques aleatorios para minimizar una función compuesta", Programación matemática , Springer, 144 (1–2), págs. 1–38, arXiv : 1107.2848 , doi : 10.1007 / s10107-012-0614-z , S2CID  16816638.
• Richtarik, Peter; Takac, Martin (diciembre de 2012), "Métodos de descenso de coordenadas paralelas para la optimización de big data", ArXiv: 1212.0873 , arXiv : 1212.0873.