Learning with a linear loss function : excess risk and estimation bounds for ERM and minimax MOM estimators, with applications.
Apprentissage avec une fonction de perte linéaire : bornes générales pour les estimateurs ERM et minimax MOM, avec applications.
Résumé
Community detection, phase recovery, signed clustering, angular group synchronization, Maxcut, sparse PCA, the single index model, and the list goes on, are all classical topics within the field of machine learning and statistics. At first glance, they are pretty different problems with different types of data and different goals. However, the literature of recent years shows that they do have one thing in common: they all are amenable to Semi-Definite Programming (SDP). And because they are amenable to SDP, we can go further and recast them in the classical machine learning framework of risk minimization, and this with the simplest possible loss function: the linear loss function. This, in turn, opens up the opportunity to leverage the vast literature related to risk minimization to derive excess risk and estimation bounds as well as algorithms to unravel these problems. The aim of this work is to propose a unified methodology to obtain statistical properties of classical machine learning procedures based on the linear loss function, which corresponds, for example, to the case of SDP procedures that we look as ERM procedures. Embracing a machine learning view point allows us to go into greater depth and introduce other estimators which are effective in handling two key challenges within statistical learning: sparsity, and robustness to adversarial contamination and heavy-tailed data. We attack the structural learning problem by proposing a regularized version of the ERM estimator. We then turn to the robustness problem and introduce an estimator based on the median of means (MOM) principle, which we call the minmax MOM estimator. This latter estimator addresses the problem of robustness and can be constructed whatever the loss function, including the linear loss function. We also present a regularized version of the minmax MOM estimator. For each of those estimators we are able to provide excess risk and estimation bounds, which are derived from two key tools: local complexity fixed points and curvature equations of the excess risk function. To illustrate the relevance of our approach, we apply our methodology to five classical problems within the frame of statistical learning, for which we improve the state-of-the-art results.
La détection de communautés sur des graphes, la récupération de phase, le clustering signé, la synchronisation angulaire, le problème de la coupe maximale, la sparse PCA, ou encore le single index model, sont des problèmes classiques dans le domaine de l'apprentissage statistique. Au premier abord, ces problèmes semblent très dissemblables, impliquant différents types de données et poursuivant des objectifs distincts. Cependant, la littérature récente révèle qu'ils partagent un point commun : ils peuvent tous être formulés sous la forme de problèmes d'optimisation semi-définie positive (SDP). En utilisant cette modélisation, il devient possible de les aborder du point de vue classique du machine learning, en se basant sur la minimisation du risque empirique (ERM) et en utilisant la fonction de perte la plus élémentaire: la fonction de perte linéaire. Cela ouvre la voie à l'exploitation de la vaste littérature liée à la minimisation du risque, permettant ainsi d'obtenir des bornes d'estimation et de développer des algorithmes pour résoudre ces problèmes. L'objectif de cette thèse est de présenter une méthodologie unifiée pour obtenir les propriétés statistiques de procédures classiques en machine learning basées sur la fonction de perte linéaire. Cela s'applique notamment aux procédures SDP, que nous considérons comme des procédures ERM. L'adoption d'un “point de vue machine learning” nous permet d'aller plus loin en introduisant d'autres estimateurs performants pour relever deux défis majeurs en apprentissage statistique : la parcimonie et la robustesse face à la contamination adversaire et aux données à distribution à queue lourde. Nous abordons le problème des données parcimonieuses en proposant une version régularisée de l'estimateur ERM. Ensuite, nous nous attaquons au problème de la robustesse en introduisant un estimateur basé sur le principe de la "Médiane des Moyennes" (MOM), que nous nommons l'estimateur minmax MOM. Cet estimateur permet de faire face au problème de la robustesse et peut être utilisé avec n'importe quelle fonction de perte, y compris la fonction de perte linéaire. Nous présentons également une version régularisée de l'estimateur minmax MOM. Pour chacun de ces estimateurs, nous sommes en mesure de fournir un “excès de risque” ainsi que des bornes d'estimation, en utilisant deux outils clés : les points fixes de complexité locale et les équations de courbure de la fonction d'excès de risque. Afin d'illustrer la pertinence de notre approche, nous appliquons notre méthodologie à cinq problèmes classiques en machine learning, pour lesquels nous améliorons l'état de l'art.
Origine : Version validée par le jury (STAR)