Warum proximaler Gradientenabstieg anstelle einfacher Subgradientenmethoden für Lasso?

Ich dachte daran, Lasso mit Vanille-Subgradienten-Methoden zu lösen. Aber ich habe Leute gelesen, die vorschlagen, den proximalen Gradientenabstieg zu verwenden. Kann jemand hervorheben, warum für Lasso proximale GD anstelle von Vanille-Subgradienten-Methoden verwendet werden?

In der Tat kann eine ungefähre Lösung für Lasso unter Verwendung von Subgradientenmethoden gefunden werden. Angenommen, wir möchten die folgende Verlustfunktion minimieren:

$$f(w; \lambda) = \| y - Xw \|_2^2 + \lambda \|w\|_1$$

Der Gradient des Strafzeitraums ist für und für , aber der Strafzeitraum ist bei differenzierbar . Stattdessen können wir die Subgradienten verwenden , die die gleiche ist , aber einen Wert von für .$-\lambda$$w_i < 0$$\lambda$$w_i > 0$$0$$\lambda \text{sgn}(w)$$0$$w_i = 0$

Der entsprechende Subgradient für die Verlustfunktion ist:

$$g(w; \lambda) = -2X^T (y - X w) + \lambda \text{sgn}(w)$$

Wir können die Verlustfunktion mit einem Ansatz minimieren, der dem Gradientenabstieg ähnelt, aber den Subgradienten verwendet (der überall dem Gradienten entspricht, außer , wo der Gradient undefiniert ist). Die Lösung kann der tatsächlichen Lasso-Lösung sehr nahe kommen, enthält jedoch möglicherweise keine exakten Nullen. Wenn die Gewichte Null sein sollten, werden stattdessen extrem kleine Werte verwendet. Dieser Mangel an wahrer Sparsamkeit ist ein Grund, keine Subgradientenmethoden für Lasso zu verwenden. Engagierte Löser nutzen die Problemstruktur, um auf rechnerisch effiziente Weise wirklich spärliche Lösungen zu erstellen. Dieser Beitrag$0$sagt, dass dedizierte Methoden (einschließlich proximaler Gradientenmethoden) nicht nur spärliche Lösungen produzieren, sondern auch schnellere Konvergenzraten aufweisen als subgradiente Methoden. Er gibt einige Referenzen.