Descenso de coordenadas frente a descenso de gradiente

Question

Me preguntaba cuáles son los diferentes casos de uso de los dos algoritmos, Descenso de coordenadas y Descenso gradual .

Sé que el descenso por coordenadas tiene problemas con las funciones no suaves, pero se utiliza en algoritmos populares como SVM y LASSO.

Sin embargo, creo que el descenso gradual se utiliza más ampliamente, especialmente con el resurgimiento de las RNA, y para muchas otras tareas de aprendizaje automático.

Mi pregunta es: ¿Qué tipo de problemas se ajustan a uno pero no a otro, y en ese sentido qué hace que el descenso de coordenadas se ajuste a las SVM y LASSO, pero el descenso de gradiente se ajuste a las RNA?

¿Cómo hay que elegir entre los dos a la hora de escoger un algoritmo de optimización?

Answer 1

Coordinar las actualizaciones del descenso un parámetro a la vez, mientras que el descenso de gradiente intenta actualizar todos los parámetros a la vez.

Es difícil especificar exactamente cuando un algoritmo lo hará mejor que el otro. Por ejemplo, me sorprendió mucho saber que el descenso por coordenadas era lo más avanzado para LASSO. Y no fui el único; véase diapositiva 17 .

Dicho esto, hay algunas características que pueden hacer que un problema sea más enmendable para el descenso por coordenadas:

(1) Actualizaciones condicionales rápidas. Si, por alguna razón, el problema permite optimizar individualmente los parámetros muy rápidamente, el descenso por coordenadas puede hacer uso de esto. Por ejemplo, uno puede ser capaz de actualizar ciertos parámetros utilizando sólo un subconjunto de los datos, reduciendo en gran medida el coste computacional de estas actualizaciones. Otro caso es que exista una solución de forma cerrada para un parámetro individual, condicionada a los valores de todos los demás parámetros.

(2) Modos relativamente independientes para los parámetros. Si el valor óptimo de un parámetro es completamente independiente de los valores de los otros parámetros, entonces una ronda de descenso de coordenadas conducirá a la solución (suponiendo que cada actualización de coordenadas encuentra el modo actual). Por otro lado, si el modo de un parámetro determinado depende en gran medida de los valores de otros parámetros, es muy probable que el descenso por coordenadas avance lentamente, con actualizaciones muy pequeñas en cada ronda.

Desgraciadamente, para la mayoría de los problemas, (2) no se cumple, por lo que es raro que el descenso por coordenadas salga bien parado en comparación con los algoritmos alternativos. Creo que la razón por la que funciona bien para LASSO es que hay un montón de trucos que se pueden utilizar para promulgar la condición (1).

Para el descenso del gradiente, este algoritmo funcionará bien si la segunda derivada es relativamente estable, una buena $\alpha$ se selecciona y la fuera de la diagonal del hessiano es relativamente pequeña en comparación con las entradas diagonales. Estas condiciones también son poco frecuentes, por lo que su rendimiento suele ser peor que el de algoritmos como L-BFGS.

Answer 2

Creo que suele ser una cuestión de lo simple/fácil que sea calcular el gradiente de la parte suave de la función y/o el operador proximal de la penalización.

A veces, es mucho más sencillo encontrar una solución exacta del problema en el caso con una sola variable (o un bloque o variables), que resolverlo para todas las variables simultáneamente. Otras veces es demasiado caro calcular el gradiente en comparación con las derivadas individuales. Además, la convergencia del descenso por coordenadas es la misma que para la ista, $1/k^2$ , donde $k$ es el número de iteraciones, pero a veces puede funcionar mejor en comparación con ISTA y FISTA, véase Por ejemplo http://statweb.stanford.edu/~tibs/comparison.txt .

Estas cosas influirán en la elección del descenso de coordenadas frente a ISTA/FISTA, por ejemplo.

Answer 3

Me doy cuenta de que esta es una pregunta antigua y que tiene muy buenas respuestas. Me gustaría compartir alguna experiencia personal práctica.

Cuando se trabaja con técnicas de aprendizaje automático generativo, se suele trabajar con algún tipo de probabilidades. Un ejemplo pueden ser las probabilidades de mezcla de los $k$ componentes en un modelo de mezcla. Tienen las siguientes restricciones:

• Todas las probabilidades deben ser positivas.
• Todos los elementos del conjunto de probabilidad deben sumar uno

En realidad, esto es pedir mucho. Con el descenso de gradiente se suelen tratar las restricciones a través de una función de penalización. Aquí no funcionará. Tan pronto como un valor viola una de estas restricciones, su código típicamente levantará un error numérico de tipo. Así que uno tiene que lidiar con las restricciones por nunca permitir que el algoritmo de optimización para atravesar.

Existen numerosas transformaciones que puede aplicar a su problema para satisfacer las restricciones con el fin de permitir el descenso de gradiente. Sin embargo, si buscas la manera más fácil y perezosa de implementar esto, entonces el descenso por coordenadas es el camino a seguir:

Para cada probabilidad $p_i$ :

• $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
• $p_i = \min(\max(p_i,0),1)$
• Actualiza todos los p_i: $\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i} $

Para alguien como yo que trabaja en Python, esto suele significar que tengo que usar un bucle for adicional que impacta bastante negativamente en el rendimiento. El descenso gradual me permite utilizar Numpy, que está optimizado para el rendimiento. Uno puede obtener muy buena velocidad con él, sin embargo, esto no es alcanzable con el descenso de coordenadas por lo que suelo utilizar alguna técnica de transformación.

Así que la conclusión realmente es que el descenso por coordenadas es la opción más fácil para tratar con restricciones muy estrictas como el parámetro de la tasa en la distribución de Poisson. Si se vuelve negativo, el código se queja, etc.

Espero que esto haya aportado un poco de información.