📊 statistics

Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

Cet article propose un algorithme de plus proche voisin bilatéral pour la complétion de matrices sous des modèles de facteurs non linéaires latents avec une faible régularité et une forte proportion de données manquantes, prouvant qu'il atteint des taux d'erreur minimax optimaux s'adaptant à la régularité de la fonction sous-jacente et égalant les performances de l'oracle même avec des entrées manquantes déterministes.

Auteurs originaux : Tathagata Sadhukhan, Manit Paul, Raaz Dwivedi

Publié 2026-08-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tathagata Sadhukhan, Manit Paul, Raaz Dwivedi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

À l'ère du numérique, nous sommes constamment entourés de vastes grilles d'informations, des films qu'un service de streaming recommande aux pas quotidiens suivis par une application de santé. Ces grilles sont rarement complètes ; les utilisateurs omettent de donner des notes, les capteurs ne parviennent pas à enregistrer des données, et des personnes ne se présentent tout simplement pas à chaque rendez-vous prévu. Le défi pour les scientifiques est de combler ces pièces manquantes avec précision sans inventer de fausses informations. Ce problème, connu sous le nom de complétion de matrice, repose sur l'idée que des motifs cachés relient les données que nous voyons à celles que nous ne voyons pas. Si une personne qui aime les films d'action a également tendance à apprécier la science-fiction, un système peut utiliser ce lien pour deviner ce qu'elle pourrait penser d'un nouveau film qu'elle n'a pas encore vu. Cependant, les données du monde réel sont désordonnées. L'information manquante n'est souvent pas aléatoire ; un utilisateur peut ne pas noter un film uniquement parce qu'il ne l'a pas aimé au point de ne pas s'en donner la peine, ou un capteur peut échouer uniquement dans des conditions spécifiques. De plus, les relations entre les utilisateurs et les objets sont souvent complexes et non linéaires, ce qui signifie que des règles simples en ligne droite ne peuvent capturer l'image complète.

Une équipe de chercheurs de l'Université Cornell et de l'Université de Pennsylvanie a développé une nouvelle méthode pour s'attaquer à ce casse-tête difficile, spécifiquement lorsque les données sont manquantes de manière biaisée et que les motifs sous-jacents sont complexes. Ils se sont concentrés sur une technique appelée « plus proches voisins », qui fonctionne en trouvant des lignes et des colonnes similaires dans une grille de données pour faire des prédictions. Bien que cette approche ait été étudiée auparavant, les théories précédentes supposaient souvent que les données manquaient de manière aléatoire ou que les relations entre les points de données étaient fluides et simples. Les chercheurs se sont demandé si cette méthode pouvait toujours fonctionner lorsque les données sont manquantes à cause des valeurs qu'elles contiennent elles-mêmes, et lorsque les connexions entre les utilisateurs et les objets sont dentelées et irrégulières plutôt que fluides.

Pour répondre à cela, l'équipe a analysé un algorithme de plus proches voisins à deux côtés. Imaginez une grille où les lignes représentent des personnes et les colonnes représentent des moments dans le temps ou des événements spécifiques. L'algorithme recherche des personnes qui se comportent de manière similaire à la personne en question, et il recherche également des moments qui sont similaires au moment en question. En faisant la moyenne des résultats connus de ces personnes et de ces moments similaires, la méthode estime la valeur manquante. Les chercheurs ont prouvé mathématiquement que cette approche s'adapte à la complexité des données. Si les motifs cachés sont très rugueux et irréguliers, la méthode ajuste sa recherche pour trouver le bon degré de similitude. Si les motifs sont plus fluides, elle affine sa recherche en conséquence. Crucialement, ils ont montré que cette méthode est aussi performante qu'un système parfait et omniscient qui posséderait déjà les facteurs cachés qui régissent les données, même si l'algorithme lui-même ne connaît pas ces facteurs.

L'étude a également démontré que la méthode reste robuste même lorsqu'une partie importante des données est manquante de manière déterministe. Par exemple, dans un scénario où vingt pour cent des données sont garanties comme manquantes en raison d'une règle spécifique — comme un utilisateur ne recevant jamais de notification s'il est indisponible — l'algorithme réussit tout de même. Il ne s'effondre pas lorsque l'absence de données n'est pas aléatoire mais liée à la structure sous-jacente du système. Les chercheurs ont validé ces conclusions théoriques par des simulations informatiques approfondies, testant la méthode contre diverses autres techniques. Dans ces tests, leur approche à deux côtés a systématiquement surpassé les méthodes standards, maintenant une baisse constante des taux d'erreur à mesure que davantage de données devenaient disponibles, tandis que d'autres méthodes peinaient ou échouaient à s'améliorer.

Pour voir comment cela fonctionne dans le monde réel, l'équipe a appliqué sa méthode aux données d'une étude de santé mobile appelée HeartSteps. Cette étude impliquait trente-sept participants qui recevaient des notifications sur leurs téléphones pour les encourager à marcher. Le but était d'estimer le nombre de pas qu'une personne aurait effectué si elle avait reçu un type spécifique de notification, même lorsqu'une telle notification n'a pas été réellement envoyée. Comme les participants n'étaient pas disponibles à chaque instant, et parce que les notifications n'étaient envoyées qu'avec une certaine probabilité, les données étaient incomplètes et biaisées. Les chercheurs ont traité les utilisateurs comme des lignes et les moments de décision comme des colonnes, créant une grille avec des entrées manquantes. Lorsqu'ils ont comparé leur méthode à d'autres, l'approche des plus proches voisins à deux côtés a produit les estimations les plus précises, avec les erreurs les plus faibles et les résultats les plus cohérents. Elle a réussi à naviguer à travers les données manquantes pour révéler les résultats probables des interventions.

La portée de ce travail réside dans sa capacité à gérer la réalité désordonnée du comportement humain et des données de capteurs. En prouvant qu'une stratégie de recherche adaptative relativement simple peut égaler la performance d'un système idéal doté d'une connaissance totale, les chercheurs ont fourni un outil puissant pour des domaines allant des moteurs de recommandation aux essais médicaux. Ils ont montré que même lorsque les données sont manquantes de manière non aléatoire et que les relations sont complexes, nous n'avons pas besoin de connaître les causes cachées pour faire des prédictions précises. Nous avons simplement besoin de regarder les voisins dans les deux directions — à travers les personnes et à travers le temps — et de laisser les motifs émerger. Cette découverte suggère que dans un monde d'informations incomplètes, le bon type de moyenne peut révéler la vérité sans avoir besoin de résoudre l'intégralité du mystère d'abord.

Résumé Technique : Voisins les plus Proches Bilatéraux pour la Complétion de Matrices

Énoncé du Problème

L'article traite du problème de la complétion de matrices dans le contexte des modèles à facteurs latents, en se concentrant spécifiquement sur les configurations où la matrice de vérité terrain sous-jacente $\Theta$ est générée par une fonction latente non linéaire $f$ agissant sur des facteurs latents de lignes et de colonnes inconnus. Le modèle est défini par :
$\theta_{i,j} = f(u_i, v_j)$
où $u_i \in \mathbb{R}^{d_1}$ et $v_j \in \mathbb{R}^{d_2}$ sont des facteurs latents, et $f$ appartient à une classe de fonctions de Hölder avec un paramètre de lissage $\lambda \in (0, 1]$ . Ce cadre généralise les modèles bilinéaires standards (où $f(u,v) = \langle u, v \rangle$ ) à des fonctions non paramétriques, potentiellement moins lisses (moins lisses que Lipschitz).

Un défi critique abordé est le régime MNAR (Manquant Non Aléatoirement). Contrairement au régime MCAR (Manquant Complètement Aléatoirement), où l'absence est indépendante des données, le MNAR suppose que la probabilité qu'une entrée soit observée dépend des facteurs latents non observés. De plus, les auteurs considèrent des scénarios où les entrées peuvent être déterministiquement manquantes (c'est-à-dire manquantes avec une probabilité de 0 pour des configurations spécifiques), un phénomène courant dans les systèmes réels comme les moteurs de recommandation où les préférences des utilisateurs dictent la visibilité.

L'objectif est d'estimer la vérité terrain $\theta_{i,j}$ pour les entrées observées et manquantes sans connaissance préalable des facteurs latents $U$ et $V$ ou de la fonction $f$ , tout en atteignant des taux minimax optimaux.

Méthodologie : Voisins les plus Proches Bilatéraux (TS-NN)

Les auteurs proposent l'algorithme Two-Sided Nearest Neighbor (TS-NN). L'intuition centrale est d'approximer les distances latentes entre les lignes et les colonnes à l'aide des données observées, puis de moyenner les résultats sur les voisinages résultants.

Estimation des Distances : Puisque la fonction latente $f$ est inconnue, l'algorithme construit des proxys fondés sur les données pour les distances au carré $L_2$ entre les facteurs de lignes ( $d^2_{row}$ ) et de colonnes ( $d^2_{col}$ ).
- L'algorithme estime la distance entre la ligne $i$ et $i'$ en moyennant les différences au carré de leurs entrées observées à travers les colonnes communes, corrigées pour la variance du bruit ( $2\sigma^2$ ).
- De même, les distances de colonnes sont estimées en utilisant les lignes communes.
- Formellement, la distance de ligne estimée est :
  $\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$
  (Une formule symétrique s'applique pour les colonnes).
Construction des Voisinages : En utilisant des paramètres de réglage $\eta_{row}$ et $\eta_{col}$ , l'algorithme définit des voisinages :
- $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
- $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$
Estimation : L'estimateur $\hat{\theta}_{i,j}$ est la moyenne de toutes les entrées observées $X_{i',j'}$ où $i' \in N_{row}(i)$ et $j' \in N_{col}(j)$ .

Contributions Clés et Résultats Théoriques

1. Adaptativité au Lissage et Optimalité Minimax

La principale découverte théorique est que le TS-NN s'adapte au lissage $\lambda$ de la fonction latente $f$ .

Régime MCAR : Sous les hypothèses MCAR standards, les auteurs prouvent qu'avec un réglage approprié ( $\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$ ), l'erreur quadratique moyenne (MSE) atteint le taux minimax non paramétrique optimal :
$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$
Ce taux correspond à celui d'un algorithme "oracle" qui a accès aux véritables facteurs latents $U$ et $V$ .
Régime MNAR : L'article établit que cette optimalité est maintenue même sous les conditions MNAR, à condition qu'une condition de régularité (Hypothèse 6) soit remplie. Cette condition exige essentiellement que le nombre d'entrées observées dans l'intersection des voisinages de lignes et de colonnes soit suffisamment grand par rapport au produit des tailles de voisinage, même si certaines entrées sont détermisquement manquantes.

2. Robustesse au Manquant Déterministe

Une contribution significative est la démonstration que le TS-NN produit des taux d'erreur non triviaux même lorsqu'une partie importante de la matrice est déterministement manquante (par exemple, 50 % des entrées manquantes pour des paires utilisateur-article spécifiques). Les bornes théoriques montrent que tant que la probabilité de manquant "effective" au sein des voisinages reste éloignée de zéro, le taux minimax est préservé.

3. Garanties Ponctuelles et Normalité Asymptotique

Bornes Ponctuelles : L'article fournit des bornes d'erreur ponctuelles non asymptotiques pour les entrées individuelles $\hat{\theta}_{i,j}$ . Ces bornes présentent une "malédiction de la dimensionnalité" par rapport aux paramètres de réglage et aux dimensions de la matrice, laquelle s'estompe lorsqu'elle est moyennée au niveau de la population (MSE).
Normalité Asymptotique : Sous des conditions spécifiques sur la taille du voisinage, les auteurs prouvent que l'estimateur ponctuel est asymptotiquement normal :
$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$
Ce résultat permet la construction d'intervalles de confiance valides pour les estimations contrefactuelles.

Résultats Empiriques

Les auteurs valident leurs découvertes théoriques via :

Simulations Synthétiques :
- Les expériences comparent le TS-NN à des bases de référence incluant Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT) et SoftImpute.
- Résultats : Le TS-NN atteint systématiquement les meilleurs taux de décroissance de la MSE, égalant l'Oracle-TS-NN (qui connaît les facteurs latents) dans les contextes MCAR. Crucialement, le TS-ments maintient des performances robustes dans les contextes MNAR où d'autres méthodes (comme DR-NN) se dégradent considérablement.
- Adaptativité au Lissage : Les taux de décroissance empiriques du TS-NN s'alignent sur les prédictions théoriques à mesure que le paramètre de lissage $\lambda$ varie.
- Intervalles de Confiance : Les intervalles de confiance construits atteignent une couverture quasi-nominale (95 %) pour des tailles d'échantillon modérées, validant le résultat de normalité asymptotique.
Étude de Cas Réelle (HeartSteps) :
- La méthode est appliquée au jeu de données de santé mobile HeartSteps, un essai micro-randomisé impliquant 37 utilisateurs et des points de décision sur 6 semaines.
- Le jeu de données présente des caractéristiques MNAR (les utilisateurs sont indisponibles environ 20 % du temps, et les notifications ne sont envoyées que s'ils sont disponibles).
- Résultats : Dans un cadre de validation croisée à 5 plis, le TS-NN surpasse les variantes de NN à un seul côté (Row-NN, Col-NN) et les bases comme "All-Row-NN" pour estimer les pas contrefactuels, démontrant l'utilité pratique de l'approche bilatérale pour gérer le manquant déterministe.

Signification et Revendications

L'article affirme unifier deux domaines de recherche distincts : la complétion de matrices non paramétrique et l'analyse des données manquantes MNAR.

Analyse Inédite : Les auteurs déclarent qu'il s'agit de la première analyse théorique d'une méthode gérant simultanément des facteurs latents de lignes et de colonnes inconnus, une fonction Hölder-continue non linéaire (avec $\lambda < 1$ ) et un manquant MNAR.
Équivalence Oracle : Le travail démontre que le manque de connaissance des facteurs latents ne pénalise pas le taux de convergence ; le TS-NN est aussi performant qu'un oracle ayant une connaissance complète de $U$ et $V$ dans le régime intermédiaire.
Robustesse : La méthodologie est montrée comme robuste aux schémas de manquant déterministe, une caractéristique souvent ignorée dans la littérature standard de la complétion de matrices mais critique pour les applications réelles comme les systèmes de recommandation.

Les auteurs concluent que le TS-NN fournit une solution théoriquement fondée, adaptative et robuste pour la complétion de matrices dans des environnements complexes, non lisses et à manquant non aléatoire.