Estudio teórico de los métodos de descenso coordinado.

Estoy preparando material del curso sobre heurística para la optimización, y he estado buscando métodos de descenso coordinado. La configuración es aquí una función multivariada $f$ que desea optimizar. $f$ tiene la propiedad que se restringe a cualquier variable individual, es fácil de optimizar. Por lo tanto, el descenso de coordenadas continúa recorriendo las coordenadas, fijando todas menos la elegida y minimizando a lo largo de esa coordenada. Eventualmente, las mejoras se detienen lentamente y usted termina.

Mi pregunta es: ¿hay algún estudio teórico de métodos de descenso coordinado que hable sobre las tasas de convergencia y las propiedades de que hacen que el método funcione bien, y así sucesivamente? Obviamente, no espero respuestas totalmente generales, pero serían útiles las respuestas que iluminen los casos en que la heurística funciona bien.$f$

Aparte: la técnica de optimización alterna utilizada para los medios puede verse como un ejemplo de descenso coordinado, y el algoritmo de Frank-Wolfe parece estar relacionado (pero no es un ejemplo directo del marco)$k$

(Editar notas: reorganicé esto después de enloquecer por completo).

La literatura sobre el descenso coordinado puede ser un poco difícil de localizar. Aquí hay algunas razones para esto.

1. Muchas de las propiedades conocidas de los métodos de coordenadas se capturan en teoremas generales para métodos de descenso más generales. Dos ejemplos de esto, se dan a continuación, son la rápida convergencia bajo convexidad fuerte (HOLD para cualquier descenso más agudo), y la convergencia general de estos métodos (generalmente atribuida a Zoutendijk).$l^p$

2. Nombrar no es estándar. Incluso el término "descenso más pronunciado" no es estándar. Puede tener éxito buscando en Google cualquiera de los términos "descenso cíclico coordinado", "descenso coordinado", "Gauss-Seidel", "Gauss-Southwell". El uso no es consistente.

3. La variante cíclica rara vez recibe una mención especial. En cambio, generalmente solo se discute la mejor opción de coordenadas. Pero esto casi siempre da la garantía cíclica, aunque con un factor adicional (número de variables): esto se debe a que la mayoría de los análisis de convergencia proceden al limitar la mejora de un solo paso, y puede ignorar las coordenadas adicionales. También parece difícil decir algo general sobre lo que le compra cíclico, por lo que las personas simplemente hacen la mejor coordenada y el factor n generalmente se puede verificar.$n$$n$

Tasa bajo convexidad fuerte. El caso más simple es que su función objetivo es fuertemente convexa. Aquí, todas las variantes de descenso de gradiente tienen la tasa . Esto se demuestra en el libro de Boyd y Vandenberghe. La prueba da primero el resultado para el descenso de gradiente, y luego usa la equivalencia norma para dar el resultado para general l p descenso más agudo.$\mathcal O(\ln (1/\epsilon))$$l^p$

Restricciones Sin una fuerte convexidad, debes comenzar a ser un poco cuidadoso. No dijiste nada acerca de las restricciones y, por lo tanto, en general, el infimum puede no ser alcanzable. Diré brevemente sobre el tema de las restricciones que el enfoque estándar (con métodos de descenso) es proyectar en su restricción establecer cada iteración para mantener la viabilidad, o utilizar barreras para implementar las restricciones en su función objetivo. En el caso de la primera, no sé cómo juega con el descenso coordinado; en el caso de este último, funciona bien con descenso coordinado, y estas barreras pueden ser fuertemente convexas.

Más específicamente a los métodos de coordenadas, en lugar de proyectar, muchas personas simplemente hacen que la actualización de coordenadas mantenga la viabilidad: este es exactamente el caso con el algoritmo de Frank-Wolfe y sus variantes (es decir, usarlo para resolver SDP).

También señalaré brevemente que el algoritmo SMO para SVM se puede ver como un método de descenso de coordenadas, donde está actualizando dos variables a la vez y manteniendo una restricción de factibilidad mientras lo hace. La elección de las variables es heurística en este método, por lo que las garantías son realmente solo las garantías cíclicas. No estoy seguro de si esta conexión aparece en la literatura estándar; Aprendí sobre el método SMO de las notas del curso de Andrew Ng, y descubrí que estaban bastante limpias.

$n$

$\mathcal O(\ln(1/\epsilon))$

Hay algunos resultados más recientes sobre el descenso coordinado, he visto cosas en arXiv. Además, luo & tseng tienen algunos documentos más nuevos. Pero esto es lo principal.

$\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$$g$$(a_i)_1^m$$\lambda$$\exp(1/\epsilon^2)$$\mathcal O(1/\epsilon)$

El problema con las actualizaciones exactas. Además, es muy frecuente que no tenga una actualización de coordenadas únicas de forma cerrada. O la solución exacta puede simplemente no existir. Pero afortunadamente, hay muchos métodos de búsqueda de línea que obtienen básicamente las mismas garantías que una solución exacta. Este material se puede encontrar en textos de programación no lineal estándar, por ejemplo, en los libros Bertsekas o Nocedal & Wright mencionados anteriormente.

Vis a vis su segundo párrafo: cuando estos funcionan bien. Primero, muchos de los análisis mencionados anteriormente para el gradiente funcionan para el descenso coordinado. Entonces, ¿por qué no usar siempre el descenso coordinado? La respuesta es que para muchos problemas en los que es aplicable el descenso de gradiente, también puede usar los métodos de Newton, para los cuales se puede demostrar una convergencia superior. No sé de una manera de obtener la ventaja de Newton con el descenso coordinado. Además, el alto costo de los métodos de Newton se puede mitigar con las actualizaciones de Quasinewton (ver, por ejemplo, LBFGS).

$l^0$$k$$k$$k$$k$$f$

Sugiero mirar aquí, hemos hecho un trabajo en esta área:

http://arxiv.org/abs/1107.2848

Salud

Peter

Acabamos de publicar un artículo sobre arXiv ( http://arxiv.org/abs/1201.1214 ) que demuestra los límites inferiores genéricos para "algoritmos estadísticos" para problemas de optimización, con cada "problema" teniendo su propio límite inferior dependiendo de su Diversas propiedades.

El descenso coordinado (y casi cualquier otra cosa que podamos pensar) puede verse como un algoritmo estadístico en nuestro marco, por lo que esperamos que este documento tenga algunos resultados que sean de su interés.

Tenga en cuenta que en la optimización, "tasa de convergencia" generalmente significa un comportamiento asintótico. Es decir, la tasa solo se aplica al entorno de soluciones óptimas. En ese sentido, Luo & Tseng probó tasas de convergencia lineal para algunas funciones objetivas no fuertemente convexas en el documento "Sobre la convergencia del método de descenso coordinado para la minimización convexa diferenciable".

La tasa de convergencia no asintótica, también conocida como "complejidad de iteración", generalmente es más útil para delimitar los números de iteración de los algoritmos de minización. Para funciones objetivas fuertemente convexas, la complejidad de iteración de los métodos de descenso de coordenadas cíclicas ya se muestra en los límites de error de Luo & Tseng y el análisis de convergencia de métodos de descenso factibles: un enfoque general si se usa un límite de error global. Para problemas no fuertemente convexos, tenemos algunos resultados nuevos en la complejidad de iteración de los métodos de descenso factibles para la optimización convexa. Para ser específicos, hemos mostrado la complejidad de iteración para los métodos de descenso de coordenadas cíclicas en problemas como la forma dual de SVM y los métodos de Gauss-Seidel. Además, los resultados también cubren otros métodos de descenso factibles, incluidos el descenso por gradiente y los amigos.