La mixité rendue efficace : Régression logistique multiclasse en ligne rapide.

Résumé Il a été démontré que la mixité est un outil puissant pour obtenir des algorithmes avec un regret optimal. Cependant, les méthodes résultantes souffrent souvent d'une complexité de calcul élevée qui a réduit leur applicabilité pratique. Par exemple, dans le cas de la régression logistique multiclasse, le prévisionniste agrégatif (Foster et al. (2018)) atteint un regret de $O(\log(Bn))$ alors que Online Newton Step atteint $O(e^B\log(n))$ obtenant un gain doublement exponentiel en $B$ (une borne sur la norme des fonctions comparatives). Cependant, cette haute performance statistique est au prix d'une complexité computationnelle prohibitive $O(n^{37})$.