Pourquoi l'ajout de la pénalité L1 à l'optim de R ralentit-il tant les choses (par rapport à l'absence de pénalité ou à L2)?

J'exécute quelques optimisations avec l'implémentation optim de BFGS. La fonction objectif est en fait un algorithme de calcul, pas seulement des mathématiques. J'ai trouvé que lorsque j'ajoute une pénalité en L1, les choses ralentissent un peu. Pourquoi est-ce possible? Y a-t-il quelque chose dans L1 qui ralentit les choses? Alors, comment est-ce que la glmnetmise en œuvre de LASSO est si rapide?

Une recherche rapide sur Google a révélé un package appelé "lbfgs" qui "trouve l'optimum d'un objectif plus la norme L1 des paramètres du problème" avec "une mise en œuvre rapide et efficace en mémoire de ces routines d'optimisation, qui est particulièrement adaptée aux problèmes dimensionnels. " Dois-je rechercher des solutions comme celle-ci?

Je suppose que la raison pour laquelle l'ajout d'une pénalité L1 ralentit considérablement les choses est qu'une pénalité L1 n'est pas différenciable (c'est-à-dire la valeur absolue), alors que la pénalité L2 l'est. Cela signifie que la surface de la fonction ne sera pas lisse, et donc les méthodes standard de quasi-Newton auront beaucoup de mal avec ces problèmes. Rappelons qu'une façon de penser à une méthode de quasi-Newton est qu'elle fait une approximation quadratique de la fonction et alors la proposition initiale sera au maximum de cette approximation. Si l'approximation quadratique correspond assez bien à la fonction cible, nous devrions nous attendre à ce que la proposition soit proche du maximum (ou minimum, selon la façon dont vous regardez le monde). Mais si votre fonction cible n'est pas différentielle, cette approximation quadratique peut être très mauvaise,

Si vous avez trouvé un package R qui implémente BFGS pour les pénalités L1, essayez-le par tous les moyens. BFGS, en général, est un algorithme d'optimisation très générique. Comme c'est le cas avec tout algorithme générique, il y aura de nombreux cas spéciaux où il ne fonctionne pas bien. Les algorithmes spécialement adaptés à votre problème devraient clairement faire mieux (en supposant que le package est aussi bon que son auteur le prétend: je n'ai pas entendu parler de lbfgs, mais il y a beaucoup de grandes choses dont je n'ai pas entendu parler. Mise à jour : I J'ai utilisé le paquet lbfgs de R, et l'implémentation L-BFGS qu'ils ont est assez bonne! Je n'ai toujours pas utilisé son algorithme OWL-QN, ce à quoi l'OP fait référence).

Si cela ne fonctionne pas pour vous, vous voudrez peut-être essayer la méthode "Nelder-Mead" avec l'optim de R. Il n'utilise pas de dérivés pour l'optimisation. En tant que tel, il sera généralement plus lent sur une fonction lisse mais plus stable sur une fonction non lisse telle que vous l'avez.

Je ne sais pas pourquoi votre problème ralentit lorsque vous ajoutez une pénalité . Cela dépend probablement de (1) quel est le problème; (2) comment vous l'avez codé; et (3) la méthode d'optimisation que vous utilisez.$L_1$

Je pense qu'il y a une "réponse tacite" à votre question: les solutions les plus efficaces aux problèmes numériques sont souvent sur mesure. Les algorithmes à usage général ne sont que cela: à usage général. Les solutions spécialisées à des problèmes spécifiques auront tendance à mieux fonctionner, car nous pouvons apporter des observations sur la façon dont ce problème particulier est présenté et ses propriétés spécifiques qui sont connues de l'analyste. Pour votre question spécifique glmnet, il a un certain nombre "astuces" qui le rend très efficace - pour le problème particulier qu'il essaie de résoudre! Le Journal of Statistical Software papier fournit des détails:

1. Son optimisation pour tous les modèles (filet élastique, régression de crête et pas seulement LASSO) utilise la descente de coordonnées cycliques, ce qui est une assez bonne façon de résoudre ce problème.
2. Les coefficients sont calculés le long des chemins pour une plage de valeurs . Ainsi, plutôt que d'errer sur la surface de réponse pour une seule valeur du paramètre de régularisation , il passe des valeurs les plus grandes aux plus petites, en utilisant les estimations de coefficient des solutions précédentes comme points de départ. Cela exploite le fait que les estimations des coefficients passent de valeurs plus petites à des valeurs plus grandes à mesure que diminue; il n'a pas à résoudre le même problème encore et encore à partir de démarrages initialisés au hasard comme on le ferait avec une implémentation naïve d'une routine d'optimisation standard.$\lambda$$\lambda$$\lambda$

Et c'est codé en FORTRAN.

L-BFGS est un algorithme BFGS à mémoire limitée. Bien qu'il possède des astuces qui peuvent le rendre plus efficace que le BFGS standard pour certains problèmes, il n'est pas clair si les problèmes qu'il résout ont une incidence sur le problème particulier à résoudre. Le L-BFGS est également l'une des options optim, donc je ne sais pas pourquoi vous auriez besoin d'un package supplémentaire.

Notez que BFGS dépend des dérivés, qui sont calculés par différences finies lorsque les formes analytiques ne sont pas fournies. Cela pourrait être l'endroit où vous rencontrez des problèmes, car la pénalité n'est pas différenciable partout. Non seulement cela signifie que vous n'allez probablement pas estimer les coefficients LASSO à 0 précisément, mais cela pourrait perturber la mise à jour d'itération en itération.$L_1$