Apprentissage en ligne efficace avec des noyaux pour les problèmes adversariens à grande échelle.

Résumé Nous nous intéressons à un cadre d'apprentissage en ligne avec des noyaux pour des ensembles de données de faible dimension mais à grande échelle et potentiellement adversaires. Nous étudions les performances informatiques et théoriques de variations en ligne de la régression de Ridge à noyau. Malgré sa simplicité, l'algorithme que nous étudions est le premier à atteindre le regret optimal pour une large gamme de noyaux avec une complexité par tour d'ordre $n^\alpha$ avec $\alpha < 2$. L'algorithme que nous considérons est basé sur l'approximation du noyau avec l'étendue linéaire des fonctions de base. Nos contributions sont de deux ordres : 1) Pour le noyau gaussien, nous proposons de construire la base au préalable (indépendamment des données) par expansion de Taylor. Pour des entrées de $d$-dimensions, nous fournissons un regret (proche de) optimal d'ordre $O((\log n)^{d+1})$ avec une complexité temporelle par tour et une complexité spatiale $O((\log n)^{2d})$. Cela fait de l'algorithme un choix approprié dès que $n \gg e^d$, ce qui est susceptible de se produire dans un scénario avec des données de petite dimension et à grande échelle. 2) Pour les noyaux généraux à faible dimension effective, les fonctions de base sont mises à jour séquentiellement de manière adaptée aux données par échantillonnage de points de Nyström. Dans ce cas, notre algorithme améliore le compromis de calcul connu pour la régression par noyau en ligne.