Compromis performance-complexité pour les statistiques en grande dimension

This paper introduces a random matrix framework to analyze the trade-off between performance and complexity in a class ofmachine learning algorithms, under a high-dimensional data regime. More precisely, we analyse the spectral properties of Kij , for a randommatrix with kernel Kij ∈ Rn×n on which we apply a sparsity mask B ∈ {0, 1}n×n : this reduces the number of Kij to be evaluated, andlowers the complexity, while weakening the power of statistical inference on K. Under realistic assumptions, we demonstrate a surprisingly lowperformance decay even under severe sparsity levels.
Cet article introduit un cadre de matrices aléatoires pour l'analyse du compromis entre performance et complexité dans une classe d'algorithmes d'apprentissage automatique, sous un régime de données de grande dimension. Plus précisément, nous analysons les propriétés spectrales de K ⊙ B ∈ R n×n , pour une matrice aléatoire à noyau K ∈ R n×n sur laquelle on applique un masque de parcimonie B ∈ {0, 1} n×n : cela réduit le nombre des Kij à évaluer, et fait baisser la complexité, tout en affaiblissant la puissance de l'inférence statistique sur K. De manière surprenante nous montrons que, sous des hypothèses réalistes, les performances ne sont que marginalement altérées.