Highly Adaptive Principal Component Regression

Résumé technique : Régression en composantes principales hautement adaptative

Énoncé du problème
Le Lasso Hautement Adaptatif (HAL) est une méthode de régression non paramétrique capable d'atteindre des taux de convergence indépendants de la dimension sous des hypothèses de régularité minimales (norme de variation sectionnelle bornée). Cependant, sa mise en œuvre directe est computationnellement prohibitive en haute dimension. La matrice de design HAL $H$ a des dimensions $n \times p$, où $p = n(2^d - 1)$ pour $d$ covariables. La construction de cette matrice et la résolution du problème d'optimisation pénalisé en $\ell_1$ de haute dimension qui en résulte (même avec une descente de coordonnées efficace) deviennent irréalisables lorsque $n$ et $d$ augmentent. Bien que l'estimateur de Ridge Hautement Adaptatif (HAR) offre une alternative noyau en remplaçant la pénalité $\ell_1$ par une pénalité $\ell_2$, il nécessite toujours de travailler avec une matrice noyau $K = HH^\top$ de taille $n \times n$, ce qui peut être intensif en calcul pour de grands $n$ et ne possède pas les propriétés d'induction de parcimonie du Lasso.

Méthodologie
Les auteurs proposent deux nouveaux estimateurs, le Lasso Hautement Adaptatif en Composantes Principales (PCHAL) et le Ridge Hautement Adaptatif en Composantes Principales (PCHAR), qui répondent à ces goulots d'étranglement computationnels par une réduction de dimension aveugle à la réponse de la base HAL.

1. Décomposition noyau et spectrale :
   La méthode exploite la représentation noyau de HAL/HAR. Soit $H \in \{0, 1\}^{n \times p}$ la matrice de design HAL. La matrice de Gram (noyau) associée est $K = HH^\top \in \mathbb{R}^{n \times n}$. Les entrées de $K$ admettent une évaluation sous forme fermée :
   $$K(x, x') = \sum_{i=1}^n (2^{|S_i(x, x')|} - 1)$$
   où $S_i(x, x')$ est l'ensemble des coordonnées actives pour la paire de points $(x, x')$.

2. Réduction par composantes principales :
   Au lieu de travailler dans l'espace des caractéristiques complet de dimension $p$ ou dans l'espace noyau complet de dimension $n$, les auteurs approximent $K$ en utilisant ses $k$ premières composantes principales. Soit $H = U D^{1/2} V^\top$ la décomposition en valeurs singulières (SVD) de $H$. La méthode projette le problème de régression sur l'espace orthogonal des scores de dimension $k$ défini par les $k$ premières colonnes de $U$ (notées $U_k$) et les valeurs singulières correspondantes $D_k$.
   La carte de caractéristiques PC est définie par $z_k(x) = V_k^\top h(x)$, où $h(x)$ est le vecteur de caractéristiques HAL. Crucialement, $z_k$ peut être calculé directement à partir de la matrice noyau $K$ sans former explicitement $H$ ou $V$.

3. Estimateurs :

   • PCHAR : Un estimateur pénalisé en $\ell_2$ dans l'espace PC de dimension $k$. En raison de l'orthogonalité des scores PC, cela admet une solution de ridge sous forme fermée :
     $$\hat{\beta}_{PCHAR} = (D_k + n\lambda I_k)^{-1} D_k^{1/2} U_k^\top Y$$
   • PCHAL : Un estimateur pénalisé en $\ell_1$ dans l'espace PC de dimension $k$. Parce que la matrice de design dans l'espace PC ($Z_k = U_k D_k^{1/2}$) a des colonnes orthogonales, le problème Lasso se découple en un seuillage doux composante par composante :
     $$\hat{\beta}_{PCHAL, j} = \frac{\text{sign}(Z_{k,j}^\top Y)}{d_j} (|Z_{k,j}^\top Y| - n\lambda)_+$$
     Ces solutions sous forme fermée éliminent le besoin d'optimisation itérative lors de l'ajustement du modèle et de la validation croisée.

4. Variantes de régularisation :
   L'article introduit également une variante de descente de gradient arrêtée prématurément. Au lieu de sélectionner un seuil dur $k$, cette méthode utilise toutes les composantes principales et régularise en arrêtant la descente de gradient à une itération spécifique $t$. Cela induit un chemin de régularisation spectrale lisse où les directions à grande valeur propre entrent rapidement dans l'ajustement, tandis que les directions à petite valeur propre (susceptibles au bruit) sont retardées.

5. Prédiction :
   Pour prédire sur de nouvelles données sans construire la matrice massive $H'$, la méthode utilise la matrice de noyau croisé $K' = H' H^\top$. La prédiction est calculée comme $\hat{f}' = K' U_k D_k^{-1/2} \hat{\beta}$, évitant ainsi la construction explicite de caractéristiques de haute dimension.

Contributions clés

• Efficacité computationnelle : PCHAL et PCHAR réduisent le coût computationnel de HAL/HAR en projetant le problème dans un espace orthogonal de faible rang. Cela permet des solutions sous forme fermée et évite l'optimisation itérative, accélérant considérablement la validation croisée.
• Structure aveugle à la réponse : L'encodage en composantes principales est déterminé entièrement par les covariables (via la géométrie de la base HAL) et est indépendant de la réponse $Y$. Cela fournit une reparamétrisation universelle et guidée par la géométrie de l'échantillon.
• Lien théorique avec le mouvement brownien : Les auteurs découvrent que dans des circonstances particulières (spécifiquement lorsque l'échantillon peut être totalement ordonné composante par composante), la matrice de Gram HAL d'ordre zéro est un multiple scalaire de la matrice $A_{ij} = \min(i, j)$. Cette matrice est la covariance discrète d'une marche aléatoire, et ses vecteurs propres sont des fonctions sinus discrètes, correspondant à l'expansion de Karhunen–Loève du mouvement brownien.
• Optimalité oracle : L'article établit que pour une bibliothèque fixe d'ordres d'interaction et de paramètres de régularisation, le sélecteur validé par croisement est asymptotiquement optimal au sens de l'oracle en termes de risque.

Résultats empiriques
Les auteurs évaluent PCHAL et PCHAR sur un ensemble de jeux de données de régression réels (par exemple, blog, boston, energy, kin8nm, naval, yearmsd) par rapport à des références incluant le ridge à noyau HAR, le ridge standard, le ridge à noyau gaussien, les k-plus proches voisins, les forêts aléatoires, les GAM, les MARS et XGBoost.

• Performance : Les estimateurs basés sur les PC se comportent de manière stable à travers les jeux de données. Bien qu'ils soient rarement la seule meilleure méthode, ils évitent systématiquement des dégradations sévères de performance et restent proches des références complètes HAL/HAR.
• Comparaison : Contrairement à certains apprenants concurrents (par exemple, les méthodes basées sur les arbres) qui montrent une forte variabilité à travers les jeux de données, PCHAL/PCHAR maintiennent une performance robuste. Sur les jeux de données où HAL/HAR est computationnellement irréalisable à exécuter directement, ces méthodes offrent une alternative viable avec des performances empiriques comparables.

Signification et affirmations
L'article affirme que PCHAL et PCHAR offrent une voie pratique pour exploiter les avantages statistiques de HAL (taux indépendants de la dimension et adaptabilité à une faible régularité) sans les coûts computationnels prohibitifs de la base complète. En exploitant la structure spectrale du noyau HAL, la méthode atteint :

1. Évolutivité : Elle rend la régression de type HAL réalisable pour des tailles d'échantillon plus grandes et des dimensions plus élevées en réduisant le problème à un espace orthogonal de faible dimension.
2. Efficacité statistique : Les résultats théoriques suggèrent que la réduction par composantes principales ne sacrifie pas les taux de convergence qui motivent HAL, sous réserve que des hypothèses appropriées de contrôle de complexité soient satisfaites.
3. Interprétabilité : Le lien avec le mouvement brownien et le chemin de régularisation spectrale lisse offrent de nouvelles perspectives théoriques sur le comportement des estimateurs non paramétriques adaptatifs.

Les auteurs soulignent que la méthode est « aveugle à la réponse », ce qui signifie que la réduction des caractéristiques est pilotée uniquement par la géométrie des covariables, ce qui simplifie le processus d'ajustement et permet des solutions efficaces et sous forme fermée qui ne sont pas disponibles dans les implémentations HAL standard.