¿Por qué agregar la penalización L1 a la optimización de R ralentiza tanto las cosas (en relación con ninguna penalización o L2)?

Estoy ejecutando algunas optimizaciones con la implementación de BFGS de optim. La función objetivo es en realidad un algoritmo computacional, no solo matemático. Descubrí que cuando agrego una penalización L1, las cosas se ralentizan bastante. ¿Por qué podría ser esto? ¿Hay algo en L1 que ralentiza las cosas? Entonces, ¿cómo es la glmnetimplementación de LASSO tan rápido?

Una búsqueda rápida en Google arrojó un paquete llamado "lbfgs" que "encuentra el óptimo de un objetivo más la norma L1 de los parámetros del problema" con "una implementación rápida y eficiente en memoria de estas rutinas de optimización, que es particularmente adecuada para problemas dimensionales ". ¿Debería buscar soluciones como esta?

Supongo que la razón por la que agregar una penalización L1 ralentiza las cosas significativamente es que una penalización L1 no es diferenciable (es decir, valor absoluto), mientras que la penalización L2 sí lo es. Esto significa que la superficie de la función no será suave y, por lo tanto, los métodos estándar de cuasi-Newton tendrán muchos problemas con estos problemas. Recuerde que una forma de pensar en un método cuasi-Newton es que hace una aproximación cuadrática de la función y luego la propuesta inicial será el máximo de esa aproximación. Si la aproximación cuadrática coincide bastante bien con la función objetivo, deberíamos esperar que la propuesta sea cercana al máximo (o mínimo, dependiendo de cómo se mire el mundo). Pero si su función objetivo no es diferenciable, esta aproximación cuadrática puede ser muy mala,

Si ha encontrado un paquete R que implementa BFGS para penalizaciones L1, pruébelo. BFGS, en general, es un algoritmo muy genérico para la optimización. Como es el caso con cualquier algoritmo genérico, habrá muchos casos especiales en los que no funcionará bien. Los algoritmos que se adaptan especialmente a su problema claramente deberían mejorar (suponiendo que el paquete sea tan bueno como lo afirma el autor: no he oído hablar de lbfgs, pero hay muchas cosas buenas de las que no he oído hablar. Actualización : I He usado el paquete lbfgs de R, ¡y la implementación de L-BFGS que tienen es bastante buena! Todavía no he usado su algoritmo OWL-QN, que es a lo que se refiere el OP).

Si no funciona para ti, quizás quieras probar el método "Nelder-Mead" con la optimización de R. No utiliza derivados para la optimización. Como tal, generalmente será más lento en una función suave pero más estable en una función suave como la que tiene usted.

No sé por qué su problema se ralentiza cuando agrega un $L_1$multa. Probablemente depende de (1) cuál es el problema; (2) cómo lo ha codificado; y (3) el método de optimización que está utilizando.

Creo que hay una "respuesta tácita" a su pregunta: las soluciones más eficientes para los problemas numéricos a menudo están hechas a medida. Los algoritmos de propósito general son solo eso: propósito general. Las soluciones especializadas a problemas específicos tenderán a funcionar mejor, porque podemos aportar observaciones sobre cómo se presenta ese problema en particular y sus propiedades específicas que el analista conoce. Para su pregunta específica sobre glmnet, tiene una serie de "trucos" que lo hacen altamente eficiente, ¡para el problema particular que está tratando de resolver! El Journal of Statistical Software papel en la proporciona detalles:

1. Su optimización para todos los modelos (red elástica, regresión de cresta y no solo LASSO) utiliza el descenso de coordenadas cíclicas, que es una muy buena manera de resolver este problema.
2. Los coeficientes se calculan a lo largo de las rutas para un rango de $\lambda$valores. Entonces, en lugar de deambular por la superficie de respuesta para un solo valor del parámetro de regularización$\lambda$, se mueve de mayor a menor valor, utilizando estimaciones de coeficientes de soluciones anteriores como puntos de partida. Esto explota el hecho de que las estimaciones de coeficientes ascienden de valores más pequeños a más grandes como$\lambda$disminuye no tiene que volver a resolver el mismo problema una y otra vez desde inicios aleatorios como se haría con una implementación ingenua de una rutina de optimización estándar.

Y está codificado en FORTRAN.

L-BFGS es un algoritmo BFGS de memoria limitada. Si bien tiene trucos que pueden hacerlo más eficiente que el BFGS estándar para algunos problemas, no está claro si los problemas que resuelve tienen alguna relación con el problema en particular. L-BFGS también es una de las opciones optim, así que no estoy seguro de por qué necesitarías un paquete adicional.

Tenga en cuenta que BFGS depende de derivados, que se calculan por diferencias finitas cuando no se proporcionan formas analíticas. Esto podría ser donde tienes problemas, porque el$L_1$La pena no es diferenciable en todas partes. Esto no solo significa que probablemente no va a estimar los coeficientes de LASSO exactamente a 0, sino que podría causar estragos en la actualización de iteración a iteración.