Relaxation lagrangienne dans le contexte de la régression des crêtes

Dans "The Elements of Statistical Learning" (2nd ed), p63, les auteurs donnent les deux formulations suivantes du problème de régression des crêtes:

{\hat{β}}^{r je ré g e} = \underset{β}{argmin} {\sum_{je = 1}^{N} (y_{je} - β_{0} - \sum_{j = 1}^{p} X_{je j} β_{j})^{2} + λ \sum_{j = 1}^{p} β_{j}^{2}}

$\hat{\beta}^{ridge} = \underset{\beta}{\operatorname{argmin}} \left\{ \sum_{i=1}^N(y_i-\beta_0-\sum_{j=1}^p x_{ij} \beta_j)^2 + \lambda \sum_{j=1}^p \beta_j^2 \right\}$

{\hat{β}}^{r je ré g e} = \underset{β}{argmin} \sum_{je = 1}^{N} (y_{je} - β_{0} - \sum_{j = 1}^{p} X_{je j} β_{j})^{2}, sujet à \sum_{j = 1}^{p} β_{j}^{2} \leq t .

$\hat{\beta}^{ridge} = \underset{\beta}{\operatorname{argmin}} \sum_{i=1}^N(y_i-\beta_0-\sum_{j=1}^p x_{ij} \beta_j)^2 \text{, subject to } \sum_{j=1}^p \beta_j^2 \leq t.$

On prétend que les deux sont équivalents et qu'il existe une correspondance biunivoque entre les paramètres et . $\lambda$ $t$

Il semblerait que la première formulation soit une relaxation lagrangienne de la seconde. Cependant, je n'ai jamais eu une compréhension intuitive de comment ou pourquoi les relaxations lagrangiennes fonctionnent.

Existe-t-il un moyen simple de démontrer que les deux formulations sont effectivement équivalentes? Si je dois choisir, je préfère l'intuition à la rigueur.

Merci.

ridge-regression NPE
la source

Si vous voulez simplement une explication intuitive, allez au 1.03.26 de cette vidéo (à la fin), il y a une explication intuitive de la façon dont les contraintes sont liées à la fonction objective.

user603

Réponses:

La correspondance peut être affichée le plus facilement à l'aide du théorème de l' enveloppe .

Premièrement, le lagrangien standard aura un terme supplémentaire . Cela n'affectera pas le problème de maximisation si nous traitons simplement comme donné, donc Hastie et al le suppriment. $\lambda \cdot t$ $\lambda$

Maintenant, si vous différenciez le lagrangien complet par rapport à , le théorème de l'enveloppe dit que vous pouvez ignorer les effets indirects de à , car vous êtes au maximum. Ce qui vous restera, c'est le multiplicateur de Lagrange de . $t$ $t$ $\beta$ $\lambda \cdot t$

Mais qu'est-ce que cela signifie intuitivement? Puisque la contrainte se lie au maximum, la dérivée du lagrangien, évaluée au maximum, est la même que la dérivée de l'objectif d'origine. Le multiplicateur de Lagrange donne donc le prix fictif - la valeur en termes d'objectif - de relâcher la contrainte en augmentant . $t$

Je suppose que c'est la correspondance Hastie et al. font référence à.

Tristan
la source