Agnostic learning in (almost) optimal time via Gaussian surface area
Ce papier améliore l'analyse de Klivans et al. en démontrant que le degré polynomial nécessaire pour l'apprentissage agnostique de classes de concepts à surface de Gauss bornée est de , établissant ainsi des bornes quasi-optimales pour l'apprentissage des fonctions de seuil polynomial dans le modèle des requêtes statistiques.