Descenso estocástico de coordenadas para $\ell_1$ regularización

Question

Hace poco me encontré con el siguiente documento: " Métodos estocásticos para $\ell_1$ Minimización de pérdidas regularizada ", por Shai Shalev-Shwartz y Ambuj Tewari, ICML 2009.

En el trabajo, los autores proponen una modificación del algoritmo de descenso de coordenadas para el LASSO en el que las coordenadas (el $\beta$ s) se actualizan en un orden aleatorio. Esta modificación parece tener un mejor rendimiento en tiempo de ejecución que el descenso de coordenadas determinista.

¿Puedes ofrecer alguna intuición de por qué esa modificación haría el algoritmo más rápido en la práctica?

Answer 1

Me imagino que esto podría estar relacionado con los problemas que más brusco descenso del gradiente conjugado método corrige.

Answer 2

Creo que en el caso concreto de la pérdida L2 (regresión lineal ordinaria), la tasa de convergencia del descenso de coordenadas dependerá de la estructura de correlación de los predictores ( $X_i$ 's). Consideremos el caso en el que no están correlacionados. Entonces el descenso cíclico de coordenadas converge después de un ciclo.

Otra heurística que ha tenido más pruebas empíricas a su favor es la idea de la convergencia de conjuntos activos. En lugar de recorrer todas las coordenadas, sólo se recorren las que están activas ( $i$ donde $\beta_i$ es distinto de cero) hasta la convergencia, entonces barre a través de todas las coordenadas para actualizar el conjunto activo. La convergencia se produce cuando el conjunto activo no cambia.