Estimation Éparse Robuste pour les Gaussiens avec Erreur Optimale sous Contamination de Huber

Nous étudions les tâches d'estimation éparse gaussienne dans le modèle de contamination de Huber, en nous concentrant sur l'estimation de la moyenne, l'ACP et la régression linéaire. Pour chacune de ces tâches, nous proposons les premiers estimateurs robustes échantillonnés et computationnellement efficaces avec des garanties d'erreur optimales, dans des facteurs constants. Tous les algorithmes efficaces antérieurs pour ces tâches entraînent une erreur quantitativement sous-optimale. Concrètement, pour l'estimation de la moyenne k-sparse robuste gaussienne sur Rᵈ avec un taux de corruption >0, notre algorithme a une complexité d'échantillon (k²/²) polylog (d/), fonctionne en temps polynôme d'échantillon et approxime la moyenne cible avec une erreur O (₂- erreur). Les algorithmes efficaces précédents entraînent intrinsèquement une erreur ( (1/) ). À un niveau technique, nous développons une nouvelle méthode de filtrage multidimensionnelle dans le régime éparse qui pourrait avoir d'autres applications.