KKT versus uneingeschränkte Formulierung der Lasso-Regression

20

Die bestrafte L1-Regression (auch bekannt als Lasso) wird in zwei Formulierungen dargestellt. Die beiden Zielfunktionen seien Dann sind die beiden unterschiedlichen Formulierungen Argminβ

Q1=12||YXβ||22Q2=12||YXβ||22+λ||β||1.
vorbehaltlich | | β | | 1t , und,äquivalenten argmin β
argminβQ1
||β||1t,
Unter Verwendung der Karush-Kuhn-Tucker (KKT) -Bedingungen ist leicht zu erkennen, wie die Stationaritätsbedingung für die erste Formulierung dem Gradienten der zweiten Formulierung entspricht und auf 0 gesetzt wird. Was ich nicht herausfinden oder herausfinden kann , istwie die komplementäre Schlaffheit Bedingung für die erste Formulierung, λ ( | | & bgr; | | 1 - t ) = 0 , ist gewährleistet durch die Lösung für die zweite Formulierung erfüllt werden.
argminβQ2.
λ(||β||1t)=0
goodepic
quelle

Antworten:

16

Die zwei Formulierungen sind äquivalent in dem Sinne, dass für jeden Wert von in der ersten Formulierung ein Wert von & lgr; für die zweite Formulierung existiert, so dass die zwei Formulierungen den gleichen Minimierer & bgr; aufweisen .tλβ

Hier ist die Begründung:

Betrachten Sie die Lasso-Formulierung: Sei der Minimiererβund seib=| | β| | 1. Meine Behauptung ist, dass, wenn Siein der ersten Formulierungt=b setzen, die Lösung der ersten Formulierung ebenfallsβ∗ ist. Hier ist der Beweis:

f(β)=12||YXβ||22+λ||β||1
βb=||β||1t=bβ

Betrachten Sie die erste Formulierung wenn möglich diese zweite Formulierung lassen hat eine Lösung β , so dass| | & bgr; | | 1<| | β| | 1=b(beachten Sie das streng weniger als Zeichen). Dann ist es leicht zu sehendassf( β )<f(β

min12||YXβ||22 s.t.||β||1b
β^||β^||1<||β||1=b der Tatsache widersprechen, dass β eine Lösung für das Lasso ist. Somit ist die Lösung für die erste Formulierung auch β * .f(β^)<f(β)ββ

Da , ist die komplementäre Schlaffheitsbedingung am Lösungspunkt β erfüllt .t=bβ

Wenn Sie also eine Lasso-Formulierung mit , konstruieren Sie eine beschränkte Formulierung mit einem t , das dem Wert der l 1 -Norm der Lasso-Lösung entspricht. Umgekehrt erhalten Sie bei einer eingeschränkten Formulierung mit t ein λ, so dass die Lösung des Lassos gleich der Lösung der eingeschränkten Formulierung ist.λtl1tλ

(Wenn Sie Subgradienten kennen, können Sie dieses indem Sie die Gleichung X T ( y - X β ) = λ z lösen , wobei z | | β | | 1 )λXT(yXβ)=λzz||β||1)

elexhobby
quelle
1
Ausgezeichnet. Sobald Sie die Lösung gefunden haben, fühlen Sie sich immer dumm, nicht selbst dorthin zu gelangen. Ich nehme an, Sie meinen, den Widerspruch zu finden, nehmen wir einen finden β , so dass | | & bgr; | | 1 < | | β | | 1 = b ? β^||β^||1<||β||1=b
Goodepic
Betrachten Sie die Antwort als richtig
bdeonovic
2
Sie warum erarbeiten f(β^)<f(β)
goofd
Dies beweist, dass die Lösung der ersten Formulierung auch eine l1-Norm von b haben muss. Wie beweist es, dass die beiden Lösungen tatsächlich gleich sind?
broncoAbierto
1
Darüber hinaus hat das Lasso nicht immer eine eindeutige Lösung, sodass wir nicht auf den Minimierer verweisen können . arxiv.org/pdf/1206.0313.pdf . Wir konnten jedoch beziehen sich auf die Menge der Minimierer und zeigen , dass einige & bgr; & ne; & bgr; * zu diesem Satz gehören. β^β
broncoAbierto
3

Ich denke, dass die Idee von elexhobby für diesen Beweis gut ist, aber ich denke nicht, dass es völlig richtig ist.

Zeigen , dass das Vorhandensein einer Lösung für die erste , so dass β< β * führt zu einem Widerspruch, können wir nur die Notwendigkeit , übernehmen von β= β * , nicht dass β = β *β^β^<ββ^=ββ^=β .

Ich schlage stattdessen vor, wie folgt vorzugehen:

Der Einfachheit halber bezeichnen wir die erste und die zweite Formulierung mit bzw. P 2 . Nehmen wir an, dass P 2 eine eindeutige Lösung β mit β = b hat . Lassen P 1 eine Lösung, & bgr; & ne; & bgr; * . Dann haben wir das ββ * (es kann nicht größer sein , weil der Zwang) und damit f ( β )P1P2P2ββ=bP1β^ββ^β . Wenn f ( β ) < f ( β * ) dann β * ist nicht die Lösung für den P 2 , die unsere Annahmen widerspricht. Wenn f ( β ) = f ( β * ) dann β = β * , da wir die Lösung eindeutig sein angenommen.f(β^)f(β)f(β^)<f(β)βP2f(β^)=f(β)β^=β

1P1

SP2β=b βS. LassenP1 eine Lösung haben, β^S. Then, we have that β^ββS and therefore f(β^)f(β)βS. If f(β^)=f(β) for some βS (and hence for all of them) then β^S, which contradicts our assumptions. If f(β^)<f(β) for some βS then S is not the set of solutions to P2. Therefore, every solution to P1 is in S, i.e. any solution to P1 is also a solution to P2. It would remain to prove that the complementary holds too.

broncoAbierto
quelle