Apprentissage impropre efficace pour la régression logistique en ligne.

Résumé Nous considérons le cadre de la régression logistique en ligne et considérons le regret par rapport à la 2-boule de rayon B. Il est connu (voir [Hazan et al., 2014]) que tout algorithme propre qui a un regret logarithmique en nombre d'échantillons (noté n) souffre nécessairement d'une constante multiplicative exponentielle en B. Dans ce travail, nous concevons un algorithme impropre efficace qui évite cette constante exponentielle tout en préservant un regret logarithmique. En effet, [Foster et al, 2018] ont montré que la borne inférieure ne s'applique pas aux algorithmes impropres et ont proposé une stratégie basée sur des poids exponentiels avec une complexité de calcul prohibitive. Notre nouvel algorithme basé sur la minimisation empirique régularisée du risque avec des pertes de substitution satisfait un regret s'échelonnant comme O(B log(Bn)) avec une complexité temporelle par tour d'ordre O(d^2).