Der Beweis äquivalenter Formeln der Gratregression

Ich habe die beliebtesten Bücher zum statistischen Lernen gelesen

1- Die Elemente des statistischen Lernens.

2- Eine Einführung in das statistische Lernen .

Beide erwähnen, dass die Gratregression zwei äquivalente Formeln hat. Gibt es einen nachvollziehbaren mathematischen Beweis für dieses Ergebnis?

Ich habe auch Cross Validated durchlaufen , kann dort aber keinen eindeutigen Beweis finden.

Wird LASSO darüber hinaus die gleiche Art von Beweis erhalten?

Die klassische Ridge Regression ( Tikhonov Regularization ) ist gegeben durch:

Die Behauptung oben ist, dass das folgende Problem äquivalent ist:

Lassen Sie uns definieren x als die optimale Lösung des ersten Problems und ~$\hat{x}$$\tilde{x}$ als die optimale Lösung des zweiten Problems.

Der Äquivalenzanspruch bedeutet das $\forall t, \: \exists \lambda \geq 0 : \hat{x} = \tilde{x}$ .
Sie können nämlich immer ein Paar von$t$ und haben$\lambda \geq 0$ so dass die Lösung des Problems dieselbe ist.

Wie könnten wir ein Paar finden?
Nun, indem Sie die Probleme lösen und die Eigenschaften der Lösung betrachten.
Beide Probleme sind konvex und glatt, so dass es die Dinge einfacher machen sollte.

Die Lösung für das erste Problem ist an dem Punkt gegeben, an dem der Gradient verschwindet, was bedeutet:

Die KKT-Bedingungen des zweiten Problems besagen:

und

Die letzte Gleichung legt nahe, dass entweder $\mu = 0$ oder ${\left\| \tilde{x} \right\|}_{2}^{2} = t$ .

Achten Sie darauf, dass die 2 Basisgleichungen äquivalent sind.
Das heißt , wenn x = ~ x und μ =$\hat{x} = \tilde{x}$$\mu = \lambda$ beide Gleichungen gelten.

Das bedeutet, dass für den Fall ${\left\| y \right\|}_{2}^{2} \leq t$$\mu = 0$ gesetzt werden muss, was bedeutet, dass für $t$ groß genug ist, damit beide äquivalent sind, λ = gesetzt werden muss$\lambda = 0$ .

Im anderen Fall sollte man μ finden$\mu$ wo:

Dies ist im Grunde , wenn ${\left\| \tilde{x} \right\|}_{2}^{2} = t$

Sobald Sie feststellen, dass $\mu$ die Lösungen kollidieren.

In Bezug auf den Fall ${L}_{1}$ (LASSO) funktioniert es mit der gleichen Idee.
Der einzige Unterschied ist, dass wir keine Lösung gefunden haben, weshalb es schwieriger ist, die Verbindung herzustellen.

Werfen Sie einen Blick auf meine Antwort unter StackExchange Cross Validated Q291962 und StackExchange Signal Processing Q21730 - Bedeutung von $\lambda$ in Basis Pursuit .

Bemerkung
Was ist eigentlich los?
Bei beiden Problemen versucht $x$ so nah wie möglich an $y$ .
Im ersten Fall verschwindet $x = y$ im ersten Term ( ${L}_{2}$ -Distanz) und im zweiten Fall verschwindet die Zielfunktion.
Der Unterschied besteht darin, dass man im ersten Fall die ${L}_{2}$ -Norm von $x$ ausgleichen muss . Wenn $\lambda$ höher wird, bedeutet das Gleichgewicht, dass Sie $x$ kleiner machen sollten .
Im zweiten Fall gibt es eine Mauer, die Sie $x$ immer näher bringen$y$bis Sie an die Wand stoßen, die der Norm unterliegt (By $t$ ).
Wenn die Wand weit genug ist (hoher Wert von $t$ ) und genug von der Norm von $y$ abhängt, dann hat i keine Bedeutung, genau wie $\lambda$ relevant ist, ist nur der Wert multipliziert mit der Norm von $y$ sinnvoll.
Der genaue Zusammenhang ergibt sich aus dem oben angegebenen Lagrange.

Ressourcen

Ich habe diesen Artikel heute (03/04/2019) gefunden:

• Approximationshärte für eine Klasse von spärlichen Optimierungsproblemen .

Ein weniger mathematisch strenger, aber möglicherweise intuitiverer Ansatz zum Verstehen der Vorgänge besteht darin, mit der Einschränkungsversion (Gleichung 3.42 in der Frage) zu beginnen und sie mit den Methoden des "Lagrange-Multiplikators" ( https: //en.wikipedia ) zu lösen .org / wiki / Lagrange_multiplier oder Ihren bevorzugten multivariablen Kalkültext). Denken Sie daran, dass x im Kalkül der Vektor von Variablen ist, aber in unserem Fall ist x konstant und β ist der variable Vektor. Sobald Sie die Lagrange - Multiplikator - Technik anwenden Sie mit der ersten Gleichung am Ende (3,41) (nach dem zusätzlichen Wegwerfen - λ t , die zur Minimierung konstant ist relativ und kann ignoriert werden).$x$$x$$\beta$$-\lambda t$

Dies zeigt auch, dass dies für Lasso und andere Einschränkungen funktioniert.

It's perhaps worth reading about Lagrangian duality and a broader relation (at times equivalence) between:

• optimization subject to hard (i.e. inviolable) constraints
• optimization with penalties for violating constraints.

Quick intro to weak duality and strong duality

Assume we have some function $f(x,y)$ of two variables. For any $\hat{x}$ and $\hat{y}$, we have:

Since that holds for any $\hat{x}$ and $\hat{y}$ it also holds that:

This is known as weak duality. In certain circumstances, you have also have strong duality (also known as the saddle point property):

When strong duality holds, solving the dual problem also solves the primal problem. They're in a sense the same problem!

Lagrangian for constrained Ridge Regression

Let me define the function $\mathcal{L}$ as:

The min-max interpretation of the Lagrangian

The Ridge regression problem subject to hard constraints is:

You pick $\mathbf{b}$ to minimize the objective, cognizant that after $\mathbf{b}$ is picked, your opponent will set $\lambda$ to infinity if you chose $\mathbf{b}$ such that $\sum_{j=1}^p b_j^2 > t$.

If strong duality holds (which it does here because Slater's condition is satisfied for $t>0$), you then achieve the same result by reversing the order:

Here, your opponent chooses $\lambda$ first! You then choose $\mathbf{b}$ to minimize the objective, already knowing their choice of $\lambda$. The $\min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ part (taken $\lambda$ as given) is equivalent to the 2nd form of your Ridge Regression problem.

As you can see, this isn't a result particular to Ridge regression. It is a broader concept.

References

(I started this post following an exposition I read from Rockafellar.)

Rockafellar, R.T., Convex Analysis

You might also examine lectures 7 and lecture 8 from Prof. Stephen Boyd's course on convex optimization.

They are not equivalent.

For a constrained minimization problem

we solve by minimize over $\mathbf b$ the corresponding Lagrangean

Here, $t$ is a bound given exogenously, $\lambda \geq 0$ is a Karush-Kuhn-Tucker non-negative multiplier, and both the beta vector and $\lambda$ are to be determined optimally through the minimization procedure given $t$.

Comparing $(2)$ and eq $(3.41)$ in the OP's post, it appears that the Ridge estimator can be obtained as the solution to

Since in $(3)$ the function to be minimized appears to be the Lagrangean of the constrained minimization problem plus a term that does not involve $\mathbf b$, it would appear that indeed the two approaches are equivalent...

But this is not correct because in the Ridge regression we minimize over $\mathbf b$ given $\lambda >0$. But, in the lens of the constrained minimization problem, assuming $\lambda >0$ imposes the condition that the constraint is binding, i.e that

The general constrained minimization problem allows for $\lambda = 0$ also, and essentially it is a formulation that includes as special cases the basic least-squares estimator ($\lambda ^*=0$) and the Ridge estimator ($\lambda^* >0$).

So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.