Complexité d'échantillonnage de l'apprentissage de dictionnaires et d'autres factorisations de matrices.

Résumé De nombreux outils modernes d'apprentissage automatique et de traitement du signal, tels que l'apprentissage par dictionnaire clairsemé, l'analyse en composantes principales (ACP), la factorisation de matrices non négatives (NMF), le clustering $K$-means, etc., reposent sur la factorisation d'une matrice obtenue en concaténant des vecteurs de haute dimension provenant d'une collection d'apprentissage. Alors que la tâche idéalisée serait d'optimiser la qualité attendue des facteurs sur la distribution sous-jacente des vecteurs d'entraînement, elle est réalisée en pratique en minimisant une moyenne empirique sur la collection considérée. L'objectif de cet article est de fournir des estimations de la complexité de l'échantillon afin de contrôler uniformément la déviation de la moyenne empirique par rapport à la fonction de coût attendue. Des arguments standard impliquent que les performances du prédicteur empirique présentent également de telles garanties. Le niveau de généricité de l'approche englobe plusieurs contraintes possibles sur les facteurs (structure de produit tensoriel, shift-invariance, sparsité \ldots), fournissant ainsi une perspective unifiée sur la complexité d'échantillon de plusieurs schémas de factorisation de matrice largement utilisés. Les limites de généralisation dérivées se comportent de manière proportionnelle à $\sqrt{\log(n)/n}$ par rapport au nombre d'échantillons $n$ pour les techniques de factorisation matricielle considérées.