Sur la théorie de la prédiction structurée avec des pertes de substitution convexes calibrées.

Résumé Nous fournissons de nouvelles perspectives théoriques sur la prédiction structurée dans le contexte de la minimisation efficace de la perte de substitution convexe avec des garanties de cohérence. Pour toute perte de tâche, nous construisons un substitut convexe qui peut être optimisé par descente de gradient stochastique et nous prouvons des limites étroites sur la "fonction de calibration" qui relie le risque excédentaire du substitut au risque réel. Contrairement aux travaux antérieurs, nous contrôlons soigneusement l'effet du nombre exponentiel de classes sur les garanties d'apprentissage ainsi que sur la complexité de l'optimisation. Comme conséquence intéressante, nous formalisons l'intuition que certaines pertes de tâches rendent l'apprentissage plus difficile que d'autres, et que la perte 0-1 classique est mal adaptée à la prédiction structurée.