Warum verlangsamt das Hinzufügen einer L1-Strafe zu Rs Optim die Dinge so sehr (relativ zu keiner Strafe oder L2)?

Ich führe einige Optimierungen mit der Implementierung von BFGS durch Optim durch. Die Zielfunktion ist eigentlich ein Rechenalgorithmus, nicht nur Mathematik. Ich habe festgestellt, dass sich die Dinge ziemlich verlangsamen, wenn ich eine L1-Strafe hinzufüge. Warum könnte das sein? Gibt es etwas an L1, das die Dinge verlangsamt? Wie ist die glmnetImplementierung von LASSO dann so schnell?

Eine schnelle Google-Suche ergab einen Paketaufruf "lbfgs", der "das Optimum eines Ziels plus die L1-Norm der Problemparameter findet" und "eine schnelle und speichereffiziente Implementierung dieser Optimierungsroutinen bietet, die besonders für Hochleistungsprogramme geeignet ist. Dimensionsprobleme. " Sollte ich nach solchen Lösungen suchen?

Ich würde vermuten, dass der Grund, warum das Hinzufügen einer L1-Strafe die Dinge erheblich verlangsamt, darin besteht, dass eine L1-Strafe nicht differenzierbar ist (dh ein absoluter Wert), während die L2-Strafe dies ist. Dies bedeutet, dass die Oberfläche der Funktion nicht glatt ist und daher Standard-Quasi-Newton-Methoden große Probleme mit diesen Problemen haben. Denken Sie daran, dass eine Möglichkeit, sich eine Quasi-Newton-Methode vorzustellen, darin besteht, dass sie eine quadratische Approximation der Funktion vornimmt und dann der ursprüngliche Vorschlag das Maximum dieser Approximation ergibt. Wenn die quadratische Näherung ziemlich gut mit der Zielfunktion übereinstimmt, sollten wir erwarten, dass der Vorschlag nahe am Maximum (oder Minimum, je nachdem, wie Sie die Welt betrachten) liegt. Wenn Ihre Zielfunktion jedoch nicht differenzierbar ist, kann diese quadratische Näherung sehr schlecht sein.

Wenn Sie ein R-Paket gefunden haben, das BFGS für L1-Strafen implementiert, versuchen Sie es auf jeden Fall. BFGS ist im Allgemeinen ein sehr allgemeiner Algorithmus zur Optimierung. Wie bei jedem generischen Algorithmus wird es viele Sonderfälle geben, in denen dies nicht gut funktioniert. Algorithmen, die speziell auf Ihr Problem zugeschnitten sind, sollten eindeutig besser funktionieren (vorausgesetzt, das Paket ist so gut, wie es der Autor behauptet: Ich habe noch nichts von lbfgs gehört, aber es gibt eine Menge großartiger Dinge, von denen ich noch nichts gehört habe. Update : I. Ich habe Rs lbfgs-Paket verwendet, und die L-BFGS-Implementierung, die sie haben, ist ziemlich gut! Ich habe immer noch nicht den OWL-QN-Algorithmus verwendet, auf den sich das OP bezieht.

Wenn es für Sie nicht funktioniert, können Sie die "Nelder-Mead" -Methode mit Rs Optim ausprobieren. Es werden keine Derivate zur Optimierung verwendet. Als solches ist es normalerweise langsamer bei einer glatten Funktion, aber stabiler bei einer nicht glatten Funktion, wie Sie sie haben.

Ich weiß nicht, warum sich Ihr Problem verlangsamt, wenn Sie eine Strafe hinzufügen . Es hängt wahrscheinlich davon ab, (1) was das Problem ist; (2) wie Sie es codiert haben; und (3) die von Ihnen verwendete Optimierungsmethode.$L_1$

Ich denke, es gibt eine "unausgesprochene Antwort" auf Ihre Frage: Die effizientesten Lösungen für numerische Probleme sind oft maßgeschneidert. Allzweckalgorithmen sind genau das: Allzweckalgorithmen. Spezielle Lösungen für bestimmte Probleme funktionieren in der Regel besser, da wir Beobachtungen darüber machen können, wie dieses bestimmte Problem dargestellt wird und welche spezifischen Eigenschaften dem Analysten bekannt sind. Für Ihre spezielle Frage glmnetgibt es eine Reihe von "Tricks", die es hocheffizient machen - für das spezielle Problem, das es zu lösen versucht! Das Papier des Journal of Statistical Software enthält Details:

1. Die Optimierung für alle Modelle (elastisches Netz, Gratregression und nicht nur LASSO) verwendet einen zyklischen Koordinatenabstieg, was ein guter Weg ist, um dieses Problem zu lösen.
2. Die Koeffizienten werden entlang von Pfaden für einen Bereich von Werten berechnet. Anstatt für einen einzelnen Wert des Regularisierungsparameters über die Antwortfläche zu wandern, wird der Wert vom größten zum kleinsten Wert verschoben, wobei Koeffizientenschätzungen aus früheren Lösungen als Ausgangspunkte verwendet werden. Dies nutzt die Tatsache aus, dass Koeffizientenschätzungen von kleineren zu größeren Werten aufsteigen, wenn abnimmt; Es muss nicht immer wieder dasselbe Problem von zufällig initialisierten Starts lösen, wie dies bei einer naiven Implementierung einer Standardoptimierungsroutine der Fall wäre.λ $\lambda$$\lambda$$\lambda$

Und es ist in FORTRAN codiert.

L-BFGS ist ein BFGS-Algorithmus mit begrenztem Speicher. Obwohl es Tricks gibt, die es für einige Probleme effizienter als Standard-BFGS machen können, ist nicht klar, ob die Probleme, die es löst, einen Einfluss auf das jeweilige Problem haben. L-BFGS ist auch eine der Optionen optim, daher bin ich mir nicht sicher, warum Sie ein zusätzliches Paket benötigen.

Beachten Sie, dass BFGS von Derivaten abhängt, die durch endliche Differenzen berechnet werden, wenn keine analytischen Formen bereitgestellt werden. Hier können Probleme auftreten, da die Strafe nicht überall differenzierbar ist. Dies bedeutet nicht nur, dass Sie die LASSO-Koeffizienten wahrscheinlich nicht auf genau 0 schätzen werden, sondern dass die Aktualisierung von Iteration zu Iteration auch zu Chaos führen kann.$L_1$