Afficher l'équivalence entre le Norm régularisées régression et Norm Constrained régression en utilisant KKT

Selon les références Livre 1 , Livre 2 et papier .

Il a été mentionné qu'il existe une équivalence entre la régression régularisée (Ridge, LASSO et Elastic Net) et leurs formules de contraintes.

J'ai également examiné Cross Validated 1 et Cross Validated 2 , mais je ne vois pas de réponse claire pour montrer que l'équivalence ou la logique.

Ma question est

Comment montrer cette équivalence en utilisant Karush – Kuhn – Tucker (KKT)?

Les formules suivantes concernent la régression Ridge.

REMARQUE

Cette question n'est pas un devoir. C'est seulement pour augmenter ma compréhension de ce sujet.

MISE À JOUR

Je n'ai pas encore l'idée.

La réponse plus technique est parce que le problème d'optimisation contraint peut être écrit en termes de multiplicateurs de Lagrange. En particulier, le lagrangien associé au problème d'optimisation contraint est donné par

$$\mathcal L(\beta) = \underset{\beta}{\mathrm{argmin}}\,\left\{\sum_{i=1}^N \left(y_i - \sum_{j=1}^p x_{ij} \beta_j\right)^2\right\} + \mu \left\{(1-\alpha) \sum_{j=1}^p |\beta_j| + \alpha \sum_{j=1}^p \beta_j^2\right\}$$ où$\mu$est un multiplicateur choisi pour satisfaire les contraintes du problème. Les conditions de premier ordre (qui suffisent puisque vous travaillez avec de belles fonctions convexes propres) pour ce problème d'optimisation peuvent ainsi être obtenues en différenciant le lagrangien par rapport à $\beta$ et en fixant les dérivées égales à 0 (c'est un peu plus nuancé depuis le LASSO La partie a des points indifférenciables, mais il existe des méthodes d'analyse convexe pour généraliser la dérivée pour que la condition du premier ordre fonctionne toujours). Il est clair que ces conditions de premier ordre sont identiques aux conditions de premier ordre du problème non contraint que vous avez noté.

$$\max_x f(x) + \lambda g(x)$$ $$\max_x f(x) + \lambda g(x) = \max_t \left(\max_x f(x)\ \mathrm{ s.t }\ g(x) = t\right) + \lambda t$$ $\lambda$$t^*$qui résout le problème d'optimisation externe. Cela nous donne une sorte de mappage des problèmes d'optimisation non contraints aux problèmes contraints. Dans votre contexte particulier, comme tout se comporte bien pour la régression élastique nette, ce mappage devrait en fait être un à un, il sera donc utile de pouvoir basculer entre ces deux contextes en fonction de celui qui est le plus utile pour une application particulière. En général, cette relation entre les problèmes contraints et non contraints peut se comporter moins bien, mais il peut être utile de réfléchir à la mesure dans laquelle vous pouvez vous déplacer entre le problème contraint et le problème non contraint.

Edit: Comme demandé, j'inclurai une analyse plus concrète de la régression des crêtes, car elle capture les idées principales tout en évitant d'avoir à traiter les aspects techniques associés à la non-différentiabilité de la pénalité LASSO. Rappelons que nous résolvons un problème d'optimisation (en notation matricielle):

$$\underset{\beta}{\mathrm{argmin}} \left\{\sum_{i=1}^N y_i - x_i^T \beta\right\}\quad\mathrm{s.t.}\, ||\beta||^2 \leq M$$

$\beta^{OLS}$$M < \left|\left|\beta^{OLS}\right|\right|$

$$\mathcal L(\beta) = \underset{\beta}{\mathrm{argmin}} \left\{\sum_{i=1}^N y_i - x_i^T \beta\right\} - \mu\cdot||\beta||^2 \leq M$$ $$0 = -2 \left(\sum_{i=1}^N y_i x_i + \left(\sum_{i=1}^N x_i x_i^T + \mu I\right) \beta\right)$$ $$\hat\beta = \left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)$$ $\mu$

$$\left(\left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)\right)^T\left(\left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)\right) = M$$ $\mu$$\mu \in (0,\infty)$$M \in \left(0, \left|\left|\beta^{OLS}\right|\right|\right)$ $$\lim_{\mu\to 0} M(\mu) = \left|\left|\beta^{OLS}\right|\right|$$ $$\lim_{\mu \to \infty} M(\mu) = 0$$ $\mu(M)$$M$$\mu \to 0$$M \to \left|\right|\beta^{OLS}\left|\right|$

Il y a une grande analyse par stats_model dans sa réponse .

J'ai essayé de répondre à une question similaire à The Proof of Equivalent Formulas of Ridge Regression .

$t$$\lambda$

Comme je l'ai écrit et comme le montre stats_model dans son analyse, la cartographie dépend des données. Nous choisirons donc une réalisation spécifique du problème. Pourtant, le code et l'esquisse de la solution ajouteront de l'intuition à ce qui se passe.

Nous comparerons les 2 modèles suivants:

$$\text{The Regularized Model: } \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2}$$

$$\text{The Constrained Model: } \begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$$

$\hat{x}$$\tilde{x}$

$t$$\lambda$$\hat{x} = \tilde{x}$
$\lambda$$t$${L}_{2}$

$t$$\lambda$

Le solveur résout essentiellement:

$$\begin{align*} \arg_{\lambda} \quad & \lambda \\ \text{subject to} \quad & {\left\| {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b \right\|}_{2}^{2} - t = 0 \end{align*}$$

Voici donc notre matrice:

mA =

   -0.0716    0.2384   -0.6963   -0.0359
    0.5794   -0.9141    0.3674    1.6489
   -0.1485   -0.0049    0.3248   -1.7484
    0.5391   -0.4839   -0.5446   -0.8117
    0.0023    0.0434    0.5681    0.7776
    0.6104   -0.9808    0.6951   -1.1300

Et voici notre vecteur:

vB =

    0.7087
   -1.2776
    0.0753
    1.1536
    1.2268
    1.5418

Voici la cartographie:

$t$$\lambda = 0$

Zoom avant sur la plage [0, 10]:

Le code complet est disponible sur mon référentiel GitHub Q401212 à validation croisée StackExchange .