Résumé Technique : DPP Spectraux via NEPv

1. Énoncé du Problème

Le papier traite de l'intractabilité computationnelle de l'inférence MAP (Maximum A Posteriori) des processus de points déterminantaux (DPP) pour la sélection de données à grande échelle.

• Contexte : Sélectionner un sous-ensemble diversifié et de haute qualité de taille $k$ parmi un ensemble de base massif de $n$ candidats (où $n$ varie de millions à milliards) est crucial pour la curation de données, la sélection de co-sets et l'apprentissage actif.
• Objectif : Le but est de maximiser $\log \det(L_S)$, où $L_S$ est la sous-matrice principale d'un noyau de similitude semi-positif défini $L$ indexée par le sous-ensemble $S$.
• Défi : Ce problème d'optimisation est NP-difficile. Les solveurs discrets standards (greedy, lazy-greedy) ont une complexité superlinéaire ($O(kn^2)$ à $O(kn^3)$), ce qui les rend infaisables pour le régime « centré sur les données » où la diversité est le plus nécessaire. Les relaxations continues existantes (par exemple, les extensions softmax basées sur le simplexe) échouent souvent à imposer efficacement les contraintes de diversité ou ne passent pas bien à l'échelle avec les noyaux de faible rang courants en apprentissage automatique.

2. Méthodologie

Les auteurs proposent NEPV-DPP, un cadre qui reformule le problème discret de DPP-MAP en un problème d'optimisation continue sur la variété de Stiefel, menant à un nouveau problème de valeur propre non linéaire avec dépendance du vecteur propre (NEPV).

2.1 Relaxation sur la Variété de Stiefel

Au lieu de relaxer le vecteur d'appartenance binaire $x \in \{0,1\}^n$ en poids fractionnaires dans un simplexe (comme dans les travaux antérieurs), le papier relaxe la matrice de sélection de coordonnées discrètes $V_S \in \{0,1\}^{n \times k}$ en un cadre orthonormé arbitraire $V \in \mathbb{R}^{n \times k}$ tel que $V^\top V = I_k$.

• Objectif : Maximiser $f(V) = \log \det(V^\top L V)$ sous la contrainte $V \in \text{St}(n, k)$.
• Avantage Géométrique : La contrainte d'orthogonalité ($V^\top V = I_k$) agit comme une contrainte de diversité « dure ». Contrairement aux relaxations de simplexe où des éléments redondants peuvent recevoir des poids fractionnaires, la relaxation de Stiefel force les directions sélectionnées à être mutuellement orthogonales, pénalisant naturellement la redondance avant même que l'objectif ne soit évalué.
• Compatibilité avec le Faible Rang : Si $L = \Phi \Phi^\top$ (un noyau de faible rang courant en ML), l'algorithme ne forme jamais la matrice $n \times n$ $L$. Il opère uniquement sur la matrice $d \times k$ $\Phi^\top V$, permettant une mise à l'échelle quasi linéaire en $n$.

2.2 La Formulation NEPV

En dérivant les conditions KKT pour la relaxation de Stiefel, les auteurs montrent que les conditions d'optimalité du premier ordre forment une nouvelle classe de NEPV :
$$H(V) V = V \Lambda$$
où l'opérateur $H(V)$ dépend de $V$ à travers la matrice de Gram inverse $(V^\top L V)^{-1}$ :
$$H(V) = \frac{1}{2} \left( L P(V) + P(V)^\top L \right), \quad P(V) = V (V^\top L V)^{-1} V^\top L$$
Cette dépendance vis-à-vis de l'inverse de la matrice de Gram distingue ce travail des applications NEPV standards (par exemple, dans la théorie de la fonctionnelle de la densité) où l'opérateur dépend typiquement de $VV^\top$.

2.3 Solveur : Itération SCF avec Garanties

Le papier propose une itération de Champ Auto-Cohérent (SCF) pour résoudre ce NEPV, spécifiquement l'Algorithme 1 (NEPV-DPP) :

1. Initialisation : Partir des $k$ premiers vecteurs propres de $L$.
2. Itération :
   • Calculer la matrice de Gram $G_t = V_t^\top L V_t$.
   • Résoudre pour $A_t = L V_t G_t^{-1}$.
   • Construire l'opérateur $H(V_t)$ de manière implicite.
   • Appliquer un décalage de niveau ($\sigma$) et un amortissement ($\alpha$) pour stabiliser la convergence.
   • Mettre à jour $V_{t+1}$ en prenant les $k$ premiers vecteurs propres de l'opérateur décalé et en projetant de nouveau sur la variété de Stiefel via une rétraction polaire.
3. Arrondi (Rounding) : Convertir la solution continue $V^\star$ en un sous-ensemble discret $S$ en utilisant l'échantillonnage par score de levier suivi d'un raffinement greedy local.

2.4 Théorie de la Convergence

Les auteurs prouvent un théorème de contraction locale pour l'itération SCF.

• Lemme Clé : Ils établissent une borne de perturbation pour la matrice de Gram inverse $(V^\top L V)^{-1}$ sur la variété de Stiefel, montrant que de petits changements dans le sous-espace (mesurés par la distance chordale $\|\sin \Theta\|_F$) entraînent des changements bornés dans la matrice de Gram inverse.
• Résultat : Sous une hypothèse de gap spectral ($\lambda_k(L) > \lambda_{k+1}(L)$) et avec un décalage de niveau suffisant, l'itération converge linéairement (géométriquement) vers un point critique local. Le taux de convergence dépend de l'écart spectral (eigengap) et du paramètre de décalage de niveau.

3. Contributions Clés

1. Nouveauté Mathématique : Le papier identifie que la relaxation continue de DPP-MAP sur la variété de Stiefel produit un NEPV jusqu'alors non étudié, où l'opérateur dépend de l'inverse du noyau projeté. Cela nécessite une nouvelle analyse de perturbation pour les matrices de Gram inverses.
2. Scalabilité Algorithmique : L'algorithme NEPV-DPP résultant ne nécessite que des produits matrice-vecteur avec le noyau (ou ses facteurs de faible rang), avec une complexité de $O((ndk + nk^2)t)$ pour $t$ itérations. Cela le rend réalisable pour $n$ de l'ordre du million, contrairement aux méthodes discrètes en $O(kn^3)$.
3. Contraintes de Diversité Supérieures : La relaxation de Stiefel impose la diversité via l'orthogonalité $L_2$, ce qui est montré être plus robuste contre la redondance que les relaxations basées sur le simplexe.
4. Validation Empirique (Synthétique) : Le papier fournit des benchmarks synthétiques démontrant que NEPV-DPP surpasse les extensions softmax et les relaxations de simplexe D-optimales dans les régimes de haute redondance (doublons proches) et de structures de faible rang, atteignant une meilleure couverture de clusters distincts et des valeurs de log-déterminant plus élevées.

4. Résultats et Revendications

• Performance Synthétique : Dans les expériences avec $n=1000$ à $n=450$ et des structures de clusters variables :
  • Régime de Redondance : NEPV-DPP a sélectionné avec succès un représentant de chacun des 5 clusters de doublons (couverture 5/5), tandis que l'extension softmax a sélectionné des doublons (couverture 3/5) et la relaxation de simplexe D-optimale a totalement échoué (couverture 0/5).
  • Régime Uniforme : NEPV-DPP a obtenu la plus grande distance minimale par paire et la valeur de log-déterminant la plus élevée par rapport aux bases, évitant le comportement de « regroupement aux coins » (corner-clumping) des méthodes de simplexe.
• Scalabilité : La méthode s'intègre directement avec les noyaux de faible rang et les cartes de caractéristiques (feature maps), évitant la formation de la matrice noyau complète $n \times n$.
• Portée Modeste : Le papier précise explicitement que le benchmarking complet sur des données réelles, les mesures de qualité en aval et les comparaisons de temps d'exécution à l'échelle de la production sont laissés pour une étude empirique prévue. Le travail actuel se concentre sur la relaxation, le solveur et l'analyse de scalabilité.

5. Signification

Le papier revendique avoir levé la barrière algorithmique empêchant l'utilisation d'une sélection basée sur les DPP de manière principled sur de grandes échelles de données. En transformant un problème discret NP-difficile en un NEPV continu traitable avec un solveur prouvablement convergent, il permet la sélection de sous-ensembles diversifiés et de haute qualité à partir de pools de candidats massifs (millions à milliards) là où les méthodes précédentes étaient computationnellement prohibitives. Ce travail comble le fossé entre l'attrait théorique des DPP et les contraintes pratiques des pipelines d'apprentissage automatique modernes.