Taux rapides pour la prédiction structurée.

Résumé Les problèmes d'apprentissage supervisé discrets tels que la classification sont souvent abordés en introduisant un problème de substitution continu semblable à la régression. Le fait de limiter l'erreur initiale, entre l'estimation et la solution, par l'erreur de substitution confère aux problèmes discrets des taux de convergence déjà démontrés pour les instances continues. Pourtant, les approches actuelles n'exploitent pas le fait que les problèmes discrets prédisent essentiellement une sortie discrète alors que les problèmes continus prédisent une valeur continue. Dans cet article, nous abordons cette question pour des problèmes de prédiction structurés généraux, ouvrant la voie à des taux "super rapides", c'est-à-dire des taux de convergence pour l'excès de risque plus rapides que n -1 , où n est le nombre d'observations, avec même des taux exponentiels avec les hypothèses les plus fortes. Nous l'illustrons d'abord pour les prédicteurs basés sur les plus proches voisins, en généralisant les taux connus pour la classification binaire à tout problème discret dans le cadre de la prédiction structurée. Nous considérons ensuite la régression ridge à noyau où nous améliorons les taux connus en n -1/4 à des taux arbitrairement rapides, dépendant d'un paramètre caractérisant la dureté du problème, permettant ainsi, sous des hypothèses de lissage, de contourner la malédiction de la dimensionnalité.